The problem of computing a set of equivalent elements arises in many applications. Recall that an equivalence relation defined on a set of elements is a relation that is reflexive, symmetric and transitive. One application of an equivalence relation appears when designing VLSI chips. When manufacturing chips material is laided down in layers. If material is placed in two overlapping regions of the chip within the same layer, the two regions have the same electrical properties.
In this problem, you will be given a data file containing a set of points defining a collection of rectangular regions. Each region will be consist of four nonnegative integer values that represent the lower-left and upper-right corners of a rectangle. Your task is to determine which rectangles overlap and then compute an equivalence relation that assigns the rectangles to equivalence classes. For simplicity we will assume that all the rectangle resides in the same layer of the chip. The following example illustrates the problem.
Contents of the data file:
|
0
|
5
|
3
|
6
|
<=
|
region
|
0
|
|
2
|
7
|
8
|
9
|
<=
|
region
|
1
|
|
2
|
2
|
4
|
8
|
<=
|
region
|
2
|
|
1
|
0
|
7
|
1
|
|
.
|
|
|
5
|
0
|
6
|
3
|
|
.
|
|
|
7
|
5
|
10
|
8
|
|
.
|
|
|
8
|
2
|
18
|
3
|
|
|
|
|
12
|
0
|
14
|
6
|
|
|
|
|
16
|
1
|
17
|
6
|
|
|
|
|
13
|
4
|
17
|
5
|
|
|
|
|
12
|
8
|
14
|
10
|
|
|
|
|
11
|
8
|
17
|
9
|
|
|
|
|
15
|
7
|
18
|
10
|
<=
|
region
|
12
|
Assume the regions are numbered in the order they appear in the data file from 0 to N-1. Use the union-find algorithm and the general tree class defined in section 6.2 of your textbook to locate the equivalence classes. Your program should read the data file, compute the equivalence classes, and display a table on the screen of the form:
Eqivalence Class Regions
1 { 0, 1, 2, 5 }
2 { 3, 4 }
3 { 10, 11, 12 }
4 { 6, 7, 9, 8 }
The equivalence classes can be numbered in any order and the regions within the sets can be displayed in any order. At minimum, your solution should have classes for a data point, rectangle, and the union-find operation. You may create any additional classes that you need to implement your solution. On the assigned due date, submit all source files (.cpp and .h) needed to compile your solution. We will test your solution be executing the command: project2 < datafile so make sure to name your executable file project2 and read data from cin.
Attachment:- cp.zip