# VLSI.java

Below is the syntax highlighted version of VLSI.java from §9.3 Geometric Intersection.

```/******************************************************************************
*  Compilation:  javac VLSI.java
*  Execution:    java VLSI N
*  Dependencies: IntervalST.java Interval1D.java Interval2D.java
*
*  Generate N random 2D intervals and print out all pairwise intersections
*  between them. Application = VLSI rules check.
*
*  Limitations
*  -----
*   - Assumes no two y-intervals are identical. This is because
*     interval search tree disallows duplicates. To fix, create
*     a helper interval data type that uses x-interval to break ties.
*
******************************************************************************/

public class VLSI {

// helper class for events in sweep line algorithm
public static class Event implements Comparable<Event> {
int time;
Interval2D rect;

public Event(int time, Interval2D rect) {
this.time = time;
this.rect = rect;
}

public int compareTo(Event that) {
if      (this.time < that.time) return -1;
else if (this.time > that.time) return +1;
else                            return  0;
}
}

// the sweep-line algorithm
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);

// generate N random intervals
Interval2D[] rects = new Interval2D[N];
for (int i = 0; i < N; i++) {
int xmin = (int) (100 * Math.random());
int ymin = (int) (100 * Math.random());
int xmax = xmin + (int) (10 * Math.random());
int ymax = ymin + (int) (20 * Math.random());
rects[i] = new Interval2D(new Interval1D(xmin, xmax), new Interval1D(ymin, ymax));
StdOut.println(rects[i]);
}
StdOut.println();

// create events
MinPQ<Event> pq = new MinPQ<Event>();
for (int i = 0; i < N; i++) {
Event e1 = new Event(rects[i].intervalX.min, rects[i]);
Event e2 = new Event(rects[i].intervalX.max, rects[i]);
pq.insert(e1);
pq.insert(e2);
}

// run sweep-line algorithm
IntervalST<Interval2D> st = new IntervalST<Interval2D>();
while (!pq.isEmpty()) {
Event e = pq.delMin();
int time = e.time;
Interval2D rect = e.rect;

// next event is the right endpoint of interval i
if (time == rect.intervalX.max)
st.remove(rect.intervalY);

// next event is the left endpoint of interval i
else {
for (Interval1D x : st.searchAll(rect.intervalY)) {
StdOut.println("Intersection:  " + rect + ", " + st.get(x));
}
st.put(rect.intervalY, rect);
}
}

}

}
```