1 import java.io.*;
  2 import java.util.ArrayList;
  3 
  4 /*
  5  * This is a helper class
  6  * used to support file operation
  7  */
  8 public class FileOperator {
  9 
 10     //Input Stream
 11     FileInputStream fis;
 12     FileOutputStream fos;
 13     
 14     //Output Stream
 15     ObjectInputStream ois;
 16     ObjectOutputStream oos;
 17     
 18     String filename;
 19     
 20     public  FileOperator(String filename)
 21     {
 22         this.filename = filename;
 23     }
 24         
 25     /*
 26      * Get the entry in the position
 27      */
 28     public Object getObjectAt(long position)
 29     {
 30         int count = 0;
 31         try
 32         {
 33             fis = new FileInputStream(filename);
 34             ois = new ObjectInputStream(fis);
 35             
 36             Object temp = ois.readObject();
 37             while (count < position)
 38             {
 39                 temp = ois.readObject();
 40                 count++;
 41             }
 42             return temp;
 43         }
 44         catch (Exception e)
 45         {
 46             e.printStackTrace();        
 47         }
 48         
 49         //Close the stream
 50         try {
 51             fis.close();
 52             ois.close();            
 53         } catch (IOException e) {
 54             // TODO Auto-generated catch block
 55             e.printStackTrace();
 56         }
 57         return null;
 58     }
 59         
 60     /*
 61      * Append a new object into the file
 62      * just follow the last entry
 63      */
 64     public void appendObject(Object addin)
 65     {
 66         ArrayList<Object> arrayList = new ArrayList<Object>();
 67         try {
 68             fis = new FileInputStream(filename);
 69             ois = new ObjectInputStream(fis);
 70             
 71             Object temp;
 72             do
 73             {
 74                 temp = ois.readObject();
 75                 arrayList.add(temp);
 76             }
 77             while (temp!=null);
 78 
 79         } catch (Exception e) {
 80         }
 81         //Close the file
 82         try {
 83             fis.close();
 84             ois.close();
 85         } catch (Exception e) {
 86         }
 87         
 88         //Add the new object into the file
 89         try {
 90             fos = new FileOutputStream(filename);
 91             oos = new ObjectOutputStream(fos);
 92             for(Object i : arrayList)
 93             {
 94                 oos.writeObject(i);
 95             }
 96             oos.writeObject(addin);
 97         } catch (IOException e) {
 98             // TODO Auto-generated catch block
 99             e.printStackTrace();
100         }                
101         
102         //Close the file
103         try {
104             fos.close();
105             oos.close();
106         } catch (Exception e) {
107             e.printStackTrace();
108         }
109     }
110     
111     /*
112      * List the content of the file
113      * print the object using the toString method
114     */
115     public long fileContent()
116     {
117         long count = 0;
118         try {
119             fis = new FileInputStream(filename);
120             ois = new ObjectInputStream(fis);
121             
122             Object temp;
123             do
124             {
125                 temp = ois.readObject();
126                 count++;
127             // System.out.println(temp.toString());
128             }
129             while (temp!=null);
130         } catch (Exception e) {
131         }
132         return count;
133     }
134 }
135 

 1 /*
 2  * This class is used to describe 1-D Space
 3  */
 4 public class Interval<Key extends Comparable> { 
 5     public final Key low;      // left endpoint
 6     public final Key high;     // right endpoint
 7    
 8     public Interval(Key low, Key high) {
 9         if (less(high, low)) throw new RuntimeException("Illegal argument");
10         this.low  = low;
11         this.high = high;
12     }
13 
14     // is x between low and high
15     public boolean contains(Key x) {
16         return !less(x, low) && !less(high, x);
17     }
18 
19     // does this interval intersect that interval?
20     public boolean intersects(Interval<Key> that) {
21         if (less(this.high, that.low)) return false;
22         if (less(that.high, this.low)) return false;
23         return true;
24     }
25 
26     // does this interval equal that interval?
27     public boolean equals(Interval<Key> that) {
28         return this.low.equals(that.low) && this.high.equals(that.high);
29     }
30 
31 
32     // comparison helper functions
33     private boolean less(Key x, Key y) {
34         return x.compareTo(y) < 0;
35     }
36 
37     // return string representation
38     public String toString() {
39         return "[" + low + ", " + high + "]";
40     }
41 }

 1 /*
 2  * This class is used to describe 2-D Space
 3  */
 4 public class Interval2D<Key extends Comparable> { 
 5     public final Interval<Key> intervalX;   // x-interval
 6     public final Interval<Key> intervalY;   // y-interval
 7    
 8     public Interval2D(Interval<Key> intervalX, Interval<Key> intervalY) {
 9         this.intervalX = intervalX;
10         this.intervalY = intervalY;
11     }
12 
13     // does this 2D interval a intersect b?
14     public boolean intersects(Interval2D<Key> b) {
15         if (intervalX.intersects(b.intervalX)) return true;
16         if (intervalY.intersects(b.intervalY)) return true;
17         return false;
18     }
19 
20     // does this 2D interval contain (x, y)?
21     public boolean contains(Key x, Key y) {
22         return intervalX.contains(x) && intervalY.contains(y);
23     }
24 
25     // return string representation
26     public String toString() {
27         return intervalX + " x " + intervalY;
28     }
29 }

  1 import java.io.FileInputStream;
  2 import java.io.FileOutputStream;
  3 import java.io.ObjectInputStream;
  4 import java.io.ObjectOutputStream;
  5 import java.io.Serializable;
  6 import java.util.*;
  7 /*
  8  * The Quadtree built in this class is Point-Quadtree 
  9  *             |
 10  *      SW        |    SE
 11  *             |
 12  * -------------------
 13  *             |
 14  *     NW        |    NE
 15  *            |
 16  */
 17 public class QuadTree<Key extends Comparable, Value>  implements Serializable {
 18 
 19     private static final long serialVersionUID = 2478226174742279217L;
 20     //The root of the quadtree, the variable here is to represent the whole quadtree
 21     private Node root;
 22     //The page size as required
 23     public static int PageSize = 4;
 24     
 25     private ArrayList<IndexEntry> pointarray;
 26     
 27     private long pointposition = -1;
 28     
 29     public static long dataID = 0;
 30     
 31     //The data class type
 32     private class IndexEntry implements Serializable{
 33         private static final long serialVersionUID = 5520800067960787705L;
 34         Key x,y;
 35         long id;
 36         
 37         public IndexEntry(Key x, Key y, long id) {
 38             // TODO Auto-generated constructor stub
 39             this.x = x;
 40             this.y = y;
 41             this.id = id;
 42         }
 43         
 44         public boolean equals(IndexEntry that)
 45         {
 46             if ( this.x.equals(that.x) && this.y.equals(this.y) && this.id==that.id)       
 47                 return true;
 48             else
 49                 return false;
 50         }            
 51     }
 52     
 53     // helper node data type
 54     private class Node implements Serializable{ 
 55 
 56         private static final long serialVersionUID = 5226775272372026596L;
 57         //A node contains a few data entries 
 58         ArrayList<IndexEntry> indexArrayList; 
 59         int DataCount;
 60         private boolean split;
 61         //If the node has been split, then it should contain 4 branches
 62         Node NW, NE, SE, SW;   // four subtrees
 63         
 64         
 65         //The value that belongs to the node
 66         //and we use this x,y as a standard to dispatch other nodes
 67         Key x,y;
 68         long id;
 69         
 70         //Constructor
 71         Node() {
 72             indexArrayList = new ArrayList<IndexEntry>(PageSize);
 73             DataCount = 0;
 74             split = false;
 75         }
 76         
 77         public boolean isSplit()
 78         {
 79             return split;
 80         }
 81         
 82         public void setSplit()
 83         {
 84             split = true;
 85         }
 86         
 87         public void assignvalue(IndexEntry input)
 88         {
 89             this.x = input.x;
 90             this.y = input.y;
 91             this.id = input.id;
 92         }
 93     }
 94 
 95     
 96     public QuadTree()
 97     {
 98         importIndex();
 99     }
100     
101     public void exportIndex()
102     {
103         ObjectOutputStream out;     
104         try {
105             out = new ObjectOutputStream(new FileOutputStream("index.dat"));
106             out.writeObject(root);
107             out.close();
108         }
109         catch (Exception e){
110             e.printStackTrace();           
111         }
112     }
113     
114     public void importIndex()
115     {
116         ObjectInputStream in;
117         try
118         {
119             in = new ObjectInputStream(new FileInputStream("index.dat"));
120             root =  (Node) in.readObject();
121             in.close();
122         }
123         catch (Exception e){
124             e.printStackTrace();
125         }
126     }
127   /***********************************************************************
128     *  Insert (x, y) into appropriate quadrant
129     ***********************************************************************/
130     public void insert(Key x, Key y, Value value) {
131                 
132         //found the number of the data entries
133         FileOperator fo = new FileOperator("data.dat");
134         dataID = fo.fileContent();
135         
136         //Insert
137         root = insert(root, x, y, dataID);
138         
139         exportIndex();
140         
141         //update the data file
142         fo.appendObject(value);
143     }
144 
145     private Node insert(Node h, Key x, Key y, long ID) {
146         //if there is a slot for the value, then insert it
147         
148         if (h==null)
149         {
150             Node tempnode = new Node();
151             IndexEntry tempdata = new IndexEntry(x,y,ID);
152             tempnode.indexArrayList.add(tempdata);
153             tempnode.DataCount++;
154             return tempnode;
155         }
156         else 
157         {        
158             if (h.isSplit())
159             {  
160                     if ( less(x, h.x) &&  less(y, h.y)) h.SW = insert(h.SW, x, y, ID);
161                     else if ( less(x, h.x) && !less(y, h.y)) h.NW = insert(h.NW, x, y, ID);
162                     else if (!less(x, h.x) &&  less(y, h.y)) h.SE = insert(h.SE, x, y, ID);
163                     else if (!less(x, h.x) && !less(y, h.y)) h.NE = insert(h.NE, x, y, ID);
164             }
165             else
166             {
167                 if (h.DataCount<PageSize)
168                 {
169                     //create an object containing the value
170                     IndexEntry tempDataEntry = new IndexEntry(x,y,ID);
171                     //put the new object into the node
172                     h.indexArrayList.add(tempDataEntry);
173                     //count number ++
174                     h.DataCount++;
175                 }
176                 //need to split
177                 else
178                 {
179                     //Set the standard
180                     IndexEntry temp = new IndexEntry(x,y,ID);
181                     h.assignvalue(temp);
182                     
183                     //Mark the flag that the node has already been split
184                     h.setSplit();
185                     
186                     for (IndexEntry i: h.indexArrayList)
187                     {    
188                         if ( less(i.x, h.x) &&  less(i.y, h.y)) h.SW = insert(h.SW, i.x, i.y, i.id);
189                         else if ( less(i.x, h.x) && !less(i.y, h.y)) h.NW = insert(h.NW, i.x, i.y, i.id);
190                         else if (!less(i.x, h.x) &&  less(i.y, h.y)) h.SE = insert(h.SE, i.x, i.y, i.id);
191                         else if (!less(i.x, h.x) && !less(i.y, h.y)) h.NE = insert(h.NE, i.x, i.y, i.id);
192                     }
193                     
194                     //Clear the data array
195                     h.indexArrayList.clear();
196                     h.DataCount = 0;
197                 }
198             }
199          return h;
200         }
201     }
202 
203   /***********************************************************************
204     *  Point search.
205     ***********************************************************************/
206    public void queryPoint(Key x, Key y)
207    {
208 
209        long position = queryPoint(root,x,y);
210        
211        FileOperator fo = new FileOperator("data.dat");
212        
213        System.out.println("********************************");
214        System.out.println(position);
215        System.out.println("The value at (" + x + "," + y + ") is " + fo.getObjectAt(position).toString());
216        System.out.println("********************************");       
217    }
218    
219    private long queryPoint(Node h, Key x, Key y)
220    {
221        //the base condition
222        if (h==null) return -1;
223        //found the value
224        if (h.isSplit())
225        {
226               if (h.x.equals(x) && h.y.equals(y)) 
227               {
228                   System.out.println(h.id);
229                   pointposition = h.id;
230               }       
231               else if ( less(x, h.x) &&  less(y, h.y)) queryPoint(h.SW, x,y);
232               else if ( less(x, h.x) && !less(y, h.y)) queryPoint(h.NW, x,y);
233               else if (!less(x, h.x) &&  less(y, h.y)) queryPoint(h.SE, x,y);
234               else if (!less(x, h.x) && !less(y, h.y)) queryPoint(h.NE, x,y);              
235        }
236        else {
237           for (IndexEntry i: h.indexArrayList)
238           {
239               if (i.x.equals(x) && i.y.equals(y))
240                   {
241                       System.out.println(i.id);
242                       pointposition = i.id;
243                   }
244           }
245        }
246     return pointposition;
247    }
248    
249   /***********************************************************************
250     *  Range search.
251     ***********************************************************************/
252 
253     public void query2D(Interval2D<Key> rect) {
254         pointarray = new ArrayList<IndexEntry>();
255         query2D(root, rect);
256         
257         FileOperator fo = new FileOperator("data.dat");
258            
259         System.out.println("********************************");
260         
261         for (IndexEntry i: pointarray)
262         {
263                System.out.println("   The value at (" + i.x + "," + i.y + ") is " + fo.getObjectAt(i.id).toString());
264         }
265         System.out.println("********************************");    
266     }
267 
268     private void query2D(Node h, Interval2D<Key> rect) {
269         if (h == null) return;
270         Key xmin = rect.intervalX.low;
271         Key ymin = rect.intervalY.low;
272         Key xmax = rect.intervalX.high;
273         Key ymax = rect.intervalY.high;
274         
275         //found one
276        if (h.isSplit())
277            {
278            if (rect.contains(h.x, h.y))
279                {
280                        //System.out.println("    (" + h.x + ", " + h.y + ") " + h.id);                       
281                        pointarray.add(new IndexEntry(h.x,h.y,h.id));
282                }
283 
284             //search the points in the four partitions
285             if ( less(xmin, h.x) &&  less(ymin, h.y)) query2D(h.SW, rect);
286             if ( less(xmin, h.x) && !less(ymax, h.y)) query2D(h.NW, rect);
287             if (!less(xmax, h.x) &&  less(ymin, h.y)) query2D(h.SE, rect);
288             if (!less(xmax, h.x) && !less(ymax, h.y)) query2D(h.NE, rect);
289            }
290        else
291        {
292            for (IndexEntry i: h.indexArrayList)
293            {
294                if (rect.contains(i.x, i.y))
295                    {
296                            //System.out.println("    (" + i.x + ", " + i.y + ") " + i.id);
297                            pointarray.add(i);
298                    }
299            }
300        }
301     }
302 
303 
304    /*************************************************************************
305     *  helper comparison functions
306     *************************************************************************/
307 
308     private boolean less(Key k1, Key k2) { return k1.compareTo(k2) <  0; }
309     private boolean eq  (Key k1, Key k2) { return k1.compareTo(k2) == 0; }
310 }

 1 import java.io.IOException;
 2 
 3 import junit.framework.TestCase;
 4 
 5 
 6 public class QuadTreeTest extends TestCase {
 7     QuadTree<Integer, String> qt;
 8     
 9     protected void setUp() throws Exception {
10         super.setUp();
11     }
12 
13     protected void tearDown() throws Exception {
14         super.tearDown();
15     }
16 
17     public void testInsert() throws IOException {
18         qt = new QuadTree<Integer, String>();
19         for (int i = 0; i < 20; i++)
20             for (int j = 0; j < 20; j++)
21             {
22                 qt.insert(i, j, "Point " + i + j);
23             }
24     }
25 
26     public void testQueryPoint() throws IOException {
27         qt = new QuadTree<Integer, String>();
28         
29         for (int i = 0; i < 20; i++)
30             for (int j = 0; j < 20; j++)
31                 {            
32                     qt.queryPoint(i*2,j*2);
33                 }
34     }
35 
36     public void testQuery2D() throws IOException {
37         qt = new QuadTree<Integer, String>();
38         
39         for (int i = 0; i < 1000; i++)
40         {
41                 Integer xmin = (int) (20 * Math.random());
42                 Integer ymin = (int) (20 * Math.random());
43                 Integer xmax = xmin + (int) (10 * Math.random());
44                 Integer ymax = ymin + (int) (10 * Math.random());
45                 Interval<Integer> intX = new Interval<Integer>(xmin, xmax);
46                 Interval<Integer> intY = new Interval<Integer>(ymin, ymax);
47                 Interval2D<Integer> rect = new Interval2D<Integer>(intX, intY);
48                 qt.query2D(rect);
49         }
50     }
51 
52 }
53