001package algs12;
002import stdlib.*;
003import java.util.Arrays;
004import java.util.Comparator;
005
006/* ***********************************************************************
007 *  Compilation:  javac Interval1D.java
008 *  Execution:    java Interval1D
009 *
010 *  1-dimensional interval data type.
011 *
012 *************************************************************************/
013
014public class Interval1D {
015        public static final Comparator<Interval1D> LEFT_ENDPOINT_ORDER  = new LeftComparator();
016        public static final Comparator<Interval1D> RIGHT_ENDPOINT_ORDER = new RightComparator();
017        public static final Comparator<Interval1D> LENGTH_ORDER         = new LengthComparator();
018
019        private final double left;
020        private final double right;
021
022        public Interval1D(double left, double right) {
023                if (left <= right) {
024                        this.left  = left;
025                        this.right = right;
026                }
027                else throw new IllegalArgumentException("Illegal interval");
028        }
029
030        // left endpoint
031        public double left() {
032                return left;
033        }
034
035        // right endpoint
036        public double right() {
037                return right;
038        }
039
040        // does this interval intersect that one?
041        public boolean intersects(Interval1D that) {
042                if (this.right < that.left) return false;
043                if (that.right < this.left) return false;
044                return true;
045        }
046
047        // does this interval contain x?
048        public boolean contains(double x) {
049                return (left <= x) && (x <= right);
050        }
051
052        // length of this interval
053        public double length() {
054                return right - left;
055        }
056
057        // string representation of this interval
058        public String toString() {
059                return "[" + left + ", " + right + "]";
060        }
061
062
063
064        // ascending order of left endpoint, breaking ties by right endpoint
065        private static class LeftComparator implements Comparator<Interval1D> {
066                public int compare(Interval1D a, Interval1D b) {
067                        if      (a.left  < b.left)  return -1;
068                        else if (a.left  > b.left)  return +1;
069                        else if (a.right < b.right) return -1;
070                        else if (a.right > b.right) return +1;
071                        else                        return  0;
072                }
073        }
074
075        // ascending order of right endpoint, breaking ties by left endpoint
076        private static class RightComparator implements Comparator<Interval1D> {
077                public int compare(Interval1D a, Interval1D b) {
078                        if      (a.right < b.right) return -1;
079                        else if (a.right > b.right) return +1;
080                        else if (a.left  < b.left)  return -1;
081                        else if (a.left  > b.left)  return +1;
082                        else                        return  0;
083                }
084        }
085
086        // ascending order of length
087        private static class LengthComparator implements Comparator<Interval1D> {
088                public int compare(Interval1D a, Interval1D b) {
089                        double alen = a.length();
090                        double blen = b.length();
091                        if      (alen < blen) return -1;
092                        else if (alen > blen) return +1;
093                        else                  return  0;
094                }
095        }
096
097
098
099
100        // test client
101        public static void main(String[] args) {
102                Interval1D[] intervals = new Interval1D[4];
103                intervals[0] = new Interval1D(15.0, 33.0);
104                intervals[1] = new Interval1D(45.0, 60.0);
105                intervals[2] = new Interval1D(20.0, 70.0);
106                intervals[3] = new Interval1D(46.0, 55.0);
107
108                StdOut.println("Unsorted");
109                for (int i = 0; i < intervals.length; i++)
110                        StdOut.println(intervals[i]);
111                StdOut.println();
112
113                StdOut.println("Sort by left endpoint");
114                Arrays.sort(intervals, Interval1D.LEFT_ENDPOINT_ORDER);
115                for (int i = 0; i < intervals.length; i++)
116                        StdOut.println(intervals[i]);
117                StdOut.println();
118
119                StdOut.println("Sort by right endpoint");
120                Arrays.sort(intervals, Interval1D.RIGHT_ENDPOINT_ORDER);
121                for (int i = 0; i < intervals.length; i++)
122                        StdOut.println(intervals[i]);
123                StdOut.println();
124
125                StdOut.println("Sort by length");
126                Arrays.sort(intervals, Interval1D.LENGTH_ORDER);
127                for (int i = 0; i < intervals.length; i++)
128                        StdOut.println(intervals[i]);
129                StdOut.println();
130        }
131}