node.java

用java语言实现的rtree空间索引技术

/*
	COMP 630C project
	Re-implementation of R+ tree

	Group member:
	Cheng Wing Hang, Nelson
	Cheung Kwok Ho, Steven
	Ngai Ming Wai, Ryan
	Shiu Hoi Nam
	Tsui Chi Man
*/


import java.*;
import java.util.Random;

public class node {

	CELL head;
	CELL parent ;	
	
	// constructor function
	public node()
	{
		this.head = null;
		this.parent = null;
	}

// Wai: I added this

	public node(CELL newHead, CELL newParent)
	{
		CELL	tmp, newCell ;

		this.parent = newParent ;
		tmp = newHead ;
		while (tmp != null)
		{
			newCell = new CELL(tmp.current) ;	
			newCell.child = tmp.child ;

			if ( this.head != null )
			{
				this.head.prev = newCell ;
			}
			newCell.next = this.head ;
			this.head = newCell ;
			tmp = tmp.next ;
		}	
	}

	// ofcreate creats an overflown node.
	void ofcreate(int ff, int oid) {

		int     counter;
		int     total;
		int     curr_id;

		total = 2 * ff + 1;
		curr_id = oid;
		this.head = null;

		// Create a number of cells and insert them to the cell list.

		for (counter = 0; counter < total; counter++) {

			MBR     temp_mbr = new MBR(curr_id);
			CELL    temp_cell = new CELL(temp_mbr);
			
			temp_cell.next = this.head;
			if (this.head == null) {
				this.head = temp_cell;
			}
			else {
				this.head.prev = temp_cell;
				this.head = temp_cell;
			}

			curr_id++;

		}

	}


	// Sweep the called node.  axis specifies
	// the axis for sweeping while ff specifies
	// the fill factor.
	Cut_info sweep(char axis, int ff)
	{

		float	   curr_cost, min_cost;    
		float	   curr_cut, min_cut;;
		node		new_node1 = new node();
		node		new_node2 = new node();
		int	     len1, len2;
		Cut_info	i;
                RECT pmbr;

                pmbr=new RECT();
                if (this.parent!=null)
                {
                        pmbr=this.parent.current.mbr;
                }
                else
                {
                        pmbr=this.getnodesize();
                }
		min_cost = -1f;
		min_cut = -1f;


		// Split the cells, which are sorted in ascending order. 
		curr_cut = split_cells(axis, 'a', ff, new_node1, new_node2);

		// Get the length of the two cell lists.
		len1 = new_node1.getlength();
		len2 = new_node2.getlength();

		if (len1 != 0) {

			// Evaluate the cost.
			curr_cost = evaluate(axis, new_node1, new_node2, curr_cut, pmbr);

			if (min_cost < 0) {
				min_cost = curr_cost;
				min_cut = curr_cut;
			}
			else if (curr_cost < min_cost) {
				min_cost = curr_cost;
				min_cut = curr_cut;
			}
		}

		i = new Cut_info(min_cost, min_cut, new_node1.head, new_node2.head);
		return(i);

	}

	// Split the cells of a node into two nodes.  The function returns
	// the point where splitting occurs.

	float split_cells(char axis, char order, int ff, node new_node1, node new_node2) {

		int     si, finished;
		int     counter, temp_counter;
		float   curr_cut, max;
		node    curr_node;
		CELL    curr_cell, temp_cell;

	       
		// Set the sweeping index.
		if (axis == 'x') {
			si = 0;
		}
		else {
			si = 1;
		}


		// Get a node with sorted cells and initialize the
		// variables.
		curr_node = this.sort(axis, order);
		curr_cell = curr_node.head;
                curr_cut = curr_cell.current.mbr.low[si];
		max = curr_cell.current.mbr.high[si];

		counter = 0;

		if (order == 'a') {

			finished = 0;

			// Put at most ff cells in one node.
                        while ((curr_cell != null) && (finished == 0)) {
                                temp_cell = curr_cell;
                                temp_counter = 0;
                                while (curr_cut == curr_cell.current.mbr.low[si]) {
                                	curr_cell = curr_cell.next;
					temp_counter++;
					if (curr_cell == null) {
                                                break;
					}
				}

				if (counter + temp_counter <= ff) {
					while (temp_cell != curr_cell) {
                                                new_node1.insert(temp_cell.current);
						if (max < temp_cell.current.mbr.high[si]) {
							max = temp_cell.current.mbr.high[si];
						}
						temp_cell = temp_cell.next;
					}
					counter += temp_counter;
					if (counter == ff) {
						finished = 1;
					}
                                        temp_cell = curr_cell;
                                }
				else {
					while (temp_cell != curr_cell) {
						new_node2.insert(temp_cell.current);
						temp_cell = temp_cell.next;
					}
					finished = 1;
				}	

				if (curr_cell != null) {
			       		curr_cut = curr_cell.current.mbr.low[si];
				}
			}

			// Put the remaining cells in another node.
			while (curr_cell != null) {
				new_node2.insert(curr_cell.current);
				curr_cell = curr_cell.next;
			}

			curr_cell = new_node1.head;

			// Add those cells in the first node that are
			// overlapped with the area covered by the second
			// node to the second node.
			if (new_node2.getlength() != 0) {
				while (curr_cell != null) {
					if (curr_cut < curr_cell.current.mbr.high[si]) {
						new_node2.insert(curr_cell.current);
					}
					curr_cell = curr_cell.next;
				}
			}
				

			// Change the value of cut if no cut is carried at all.
			if (new_node2.getlength() == 0) {
				curr_cut = max;
			}
		}

		// Return the partition point.
		return(curr_cut);

	}

	// Evaluate the partition cost by considering the areas covered
	// by the new sub-regions.
	float evaluate(char axis, node new_node1, node new_node2, float curr_cut, RECT pmbr) {

		int   si, ci;
		float min[] = new float[2];
		float max[] = new float[2];
		float area;
		CELL  curr_cell;
		RECT  r1, r2;

		// Set the sweeping index.
		if (axis == 'x') {
			si = 0;
			ci = 1;
		}
		else {
			si = 1;
			ci = 0;
		}
			
		if (new_node1.getlength() != 0) {
			// Find the coordinates of the mbr of the first sub-region.
			curr_cell = new_node1.head;

			// Initialize the coordinates.
			min[si] = curr_cell.current.mbr.low[si];
			min[ci] = curr_cell.current.mbr.low[ci];
			if (curr_cell.current.mbr.high[si] < curr_cut) {
				max[si] = curr_cell.current.mbr.high[si];
			}
			else {
				max[si] = curr_cut;
			}
			max[ci] = curr_cell.current.mbr.high[ci];

			curr_cell = curr_cell.next;

			// Update the coordinates of the mbr by considering the
			// cells one by one.
			while (curr_cell != null) {

				if (curr_cell.current.mbr.low[si] < min[si]) {
       					min[si] = curr_cell.current.mbr.low[si];
				}

				if (curr_cell.current.mbr.low[ci] < min[ci]) {
					min[ci] = curr_cell.current.mbr.low[ci];
				}

				if (curr_cell.current.mbr.high[si] >= curr_cut ) {
					max[si] = curr_cut;
				}
				else if (curr_cell.current.mbr.high[si] > max[si]) {
					max[si] = curr_cell.current.mbr.high[si];
				}

				if (curr_cell.current.mbr.high[ci] > max[ci]) {
					max[ci] = curr_cell.current.mbr.high[ci];
				}

				curr_cell = curr_cell.next;

			}
		}
		else {
			min[si] = 0;
			min[ci] = 0;
			max[si] = 0;
			max[si] = 0;
		}

		// Calculate the area covered by the first sub-region.
		r1 = new RECT(min[0], min[1], max[0], max[1]);
		r2 = r1.intersect(pmbr);
		area = r2.area();


		if (new_node2.getlength() != 0) {

			// Find the coordinates of the mbr of the second sub-region.
       			curr_cell = new_node2.head;

			// Initialize the coordinates.
			if (curr_cell.current.mbr.low[si] > curr_cut) {
				min[si] = curr_cell.current.mbr.low[si];
			}
			else {
				min[si] = curr_cut;
			}
			min[ci] = curr_cell.current.mbr.low[ci];
			max[si] = curr_cell.current.mbr.high[si];
			max[ci] = curr_cell.current.mbr.high[ci];

			curr_cell = curr_cell.next;

			// Update the coordinates of the mbr by considering the
			// cells one by one.
			while (curr_cell != null) {

				if (curr_cell.current.mbr.low[si] <= curr_cut) {
					min[si] = curr_cut;
				}
				else if (curr_cell.current.mbr.low[si] < min[si]) {
					min[si] = curr_cell.current.mbr.low[si];
				}

				if (curr_cell.current.mbr.low[ci] < min[ci]) {
					min[ci] = curr_cell.current.mbr.low[ci];
				}

				if (curr_cell.current.mbr.high[si] > max[si]) {
					max[si] = curr_cell.current.mbr.high[si];
				}

				if (curr_cell.current.mbr.high[ci] > max[ci]) {
					max[ci] = curr_cell.current.mbr.high[ci];
				}

				curr_cell = curr_cell.next;

                        }     
		}
		else {
			min[si] = 0;
			min[ci] = 0;
			max[si] = 0;
			max[ci] = 0;
		}

		// Add the area covered by the second region to the
		// previous result.

		r1 = new RECT(min[0], min[1], max[0], max[1]);
		r2 = r1.intersect(pmbr);
		area += r2.area();