1 // A part of the 2D Orth. Search
2
3
4 class Tree
5 {
6 Leaf root=null;
7 int el=0;
8
9 //constructors
10
11 public Tree() {;}
12
13 public Tree(Point[] A,int dim)
14 {
15 if (dim==0) root=build(A,0,A.length-1); else root=build1D(A,0,A.length-1);
16 root.setEl(A[A.length/2].get(dim));
17 }
18
19 public Tree(Point[] A)
20 {
21 this(A,0);
22 }
23
24 //functions
25
26 public boolean isEmpty()
27 {
28 return (root==null);
29 }// isEmpry
30
31 public Leaf getRoot()
32 {
33 return this.root;
34 }
35
36 public int getEl()
37 {
38 return root.getEl();
39 }
40
41 public Leaf build1D(Point[] A,int start,int end) //this will build a 1D tree.
42 { // Assuming the A is sorted by Y.
43 int mid=(start+end)/2;
44 Leaf tmp=new Leaf(A[mid]);
45 tmp.setEl(A[mid].get(1));// this will set the elemnt of the leaf(Y is the apropriate)
46
47 if (start!=end)
48 {
49 tmp.setLeft(build1D(A,start,mid));
50 tmp.setRight(build1D(A,mid+1,end));
51 }//if start!=end
52 return tmp;
53 }//build1D
54
55 public Leaf build(Point[] A,int start,int end) //this will build a 2D tree, assuming A
56 { // is sorted by X.
57 int mid=(start+end)/2;
58 Point[] B=new Point[end-start+1];// build an array for the assoc. tree.
59
60 for (int i=start;i<=end;i++) B[i-start]=(Point)A[i].clone();
61 mergeSort(B,1);//sorting by Y.
62
63 Leaf tmp=new Leaf(new Tree(B,1));//creating an associated tree by build1D.
64 tmp.setEl(A[mid].get(0));//set elemnt (apropriate is X coordinate.)
65
66 if (start!=end)
67 {
68 tmp.setLeft(build(A,start,mid));//seting children
69 tmp.setRight(build(A,mid+1,end));
70 }
71
72 return tmp;
73 }// build 2D
74
75 private Leaf findSplitLeaf(int low,int high){ //finding split leaf, in this tree.
76 Leaf v=this.root;
77 if(v!=null)
78 {
79 while (!v.childless()&&(v.getEl()<low||v.getEl()>high))
80 {
81 if(v.getEl()<low) v=v.getRc(); else v=v.getLc();
82 }//while
83 }//if
84
85 return v;
86 }//findSplitLeaF
87
88 public Point[] query2D(int xlow, int xhigh, int ylow, int yhigh)
89 { //this will query in 2D range
90 Point[] ans=null; // and array for points found.
91
92 Leaf v=this.findSplitLeaf(xlow,xhigh); //to start from?
93 if (v.childless()){
94 Leaf l=(Leaf)(v.getData());
95 Tree t=(Tree)(l.getData());
96 if ((v.getEl()>=xlow)&&(v.getEl()<=xhigh)) ans=concat(ans,t.query1D(ylow,yhigh));
97 //^^ found a childless point? > check in Y dim.
98 } else
99 {
100 Tree t;
101 Leaf l=v.getLc();// check left side of split leaf
102 while(!l.childless()){
103 if(l.getEl()>=xlow) //if left is good, then all the right side is good too.
104 {
105 t=(Tree)(l.getRc().getData());
106 ans=concat(ans,t.query1D(ylow,yhigh));//now check Y dim.
107 l=l.getLc();
108 } else l=l.getRc();//if left is not good, go alittle right.
109 }//while
110 t=(Tree)(l.getData());
111 if ((l.getEl()>=xlow)&&(l.getEl()<=xhigh)) ans=concat(ans,t.query1D(ylow,yhigh));
112 //check last leaf.
113
114 l=v.getRc(); //now check in the same method, the right side.
115 while(!l.childless()){
116 if(l.getEl()<=xhigh)
117 {
118 t=(Tree)(l.getLc().getData());
119 ans=concat(ans,t.query1D(ylow,yhigh));
120 l=l.getRc();
121 } else l=l.getLc();
122 }//while
123 t=(Tree)(l.getData());
124 if ((l.getEl()>=xlow)&&(l.getEl()<=xhigh)) ans=concat(ans,t.query1D(ylow,yhigh));
125 }//else
126
127 if (ans!=null) return checkPoints(ans,xlow,xhigh,ylow,yhigh);//will return only good points
128 else return null;
129 }//query2D
130
131 private Point[] checkPoints(Point[] A,int xlow, int xhigh, int ylow, int yhigh)
132 { //this will check each point in the array and return only good points array.
133 int count=0;
134 for (int i=0;i<A.length;i++) if ((A[i].get(0)>=xlow)&&(A[i].get(0)<=xhigh)&&
135 (A[i].get(1)>=ylow)&&(A[i].get(1)<=yhigh)) count++;
136 Point[] tmp=new Point[count];
137 count=0;
138
139 for (int i=0;i<A.length;i++) if ((A[i].get(0)>=xlow)&&(A[i].get(0)<=xhigh)&&
140 (A[i].get(1)>=ylow)&&(A[i].get(1)<=yhigh))
141 {
142 tmp[count]=(Point)A[i].clone();
143 count++;
144 }
145 return tmp;
146 }//checkPoints
147
148 private Point[] query1D(int ylow,int yhigh) //this will query in Y dim.
149 {
150 Point[] tmp=null;
151 Leaf v=this.findSplitLeaf(ylow,yhigh);
152
153 if (v.childless()&&(v.getEl()<=yhigh)&&(v.getEl()>=ylow))
154 { //^^ a childless leaf that is good?
155 tmp=new Point[1];
156 Point p=(Point)(v.getData());
157 tmp[0]=(Point)p.clone();
158 return tmp;
159 }
160
161 if (!v.childless())
162 { //same algorithm as explained in query2D function.
163 Leaf l=v.getLc();
164
165 while(!l.childless())
166 {
167 if (l.getEl()>=ylow)
168 {
169 tmp=concat(tmp,reportSubTree(l.getRc()));
170 l=l.getLc();
171 }//if
172 else l=l.getRc();
173 }//while
174 if (l.getEl()>=ylow) tmp=concat(tmp,reportSubTree(l));
175
176 l=v.getRc();
177 while(!l.childless())
178 {
179 if(l.getEl()<=yhigh)
180 {
181 tmp=concat(tmp,reportSubTree(l.getLc()));
182 l=l.getRc();
183 }//if
184 else l=l.getLc();
185 }//while
186 if (l.getEl()<=yhigh) tmp=concat(tmp,reportSubTree(l));
187 } // if !childless
188 return tmp;
189 }//query1D
190
191 private static Point[] reportSubTree(Leaf l)
192 { //will report all the leaf below the Leaf 'l'.
193 Point[] tmp=null;
194
195 if (l.childless())
196 {
197 tmp=new Point[1];
198 tmp[0]=(Point)((Point)(l.getData())).clone();
199 } else
200 {
201 if (l.getLc()!=null) tmp=concat(tmp,reportSubTree(l.getLc()));
202 if (l.getRc()!=null) tmp=concat(tmp,reportSubTree(l.getRc()));
203 }
204
205 return tmp;
206 }// reportSubTree
207
208 public static void mergeSort(Point[] A,int dim)
209 { //regular mergeSort algorithm
210 //added as a static method, so no additional class is needed.
211 ms_divide(A,0,A.length/2,dim);
212 ms_divide(A,(A.length/2)+1,A.length-1,dim);
213 ms_conq(A,0,A.length/2,A.length-1,dim);
214 } //mergeSort
215
216 private static void ms_divide(Point[] A, int start,int end,int dim)
217 {
218 if (start<end)
219 {
220 ms_divide(A,start,(start+end)/2,dim);
221 ms_divide(A,((start+end)/2)+1,end,dim);
222 ms_conq(A,start,(start+end)/2,end,dim);
223 }
224 } // ms_divide;
225
226 private static void ms_conq(Point[] A,int start,int mid,int end,int dim)
227 {
228 Point[] tmp=new Point[end-start+1];
229 int a=start;
230 int b=mid+1;
231 int c=0;
232 for (int i=0;i<tmp.length;i++)
233 {
234 if ((b>end)||((a<=mid)&&(A[a].get(dim)<A[b].get(dim))))
235 {
236 tmp[i]=(Point)A[a].clone();
237 a++;
238 } else
239 {
240 tmp[i]=(Point)A[b].clone();
241 b++;
242 }
243 }//for
244
245 for (int i=0;i<tmp.length;i++) A[i+start]=(Point)tmp[i].clone();
246 }//ms_conq
247
248 private static Point[] concat(Point[] A,Point[] B)
249 { // this will merge two Point arrays to one.
250 if ((A==null)&&(B==null)) return null;
251 if (A==null) return B;
252 if (B==null) return A;
253
254 Point[] tmp=new Point[A.length+B.length];
255 for (int i=0;i<A.length;i++) tmp[i]=(Point)A[i].clone();
256 for (int i=0;i<B.length;i++) tmp[i+A.length]=(Point)B[i].clone();
257
258 return tmp;
259 }//concat
260
261 }//class Tree