node.java

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

		if (this.getlength()>fillfactor)
		{
			sp=this.splitnode(fillfactor);
		}
                if (this.parent!=null)
                {
                        this.parent.resize();
                }
		return sp;
	}

	// delete nodes of subtree in delete window
        void delete(int oid) {
                int counter = 0;    // number of nodes deleted

                if (this != null) {
                        // check each children against delete window
                        for (CELL curr_cell = this.head;
                             curr_cell != null;
                             curr_cell = curr_cell.next) {

                                if (curr_cell.child != null) {
                                        // search subtree
                                        curr_cell.child.delete(oid);
                                        if (curr_cell.child.head == null) {
                                                if (curr_cell.prev != null) {
                                                        curr_cell.prev.next = curr_cell.next;
                                                }
                                                else {
                                                        head = curr_cell.next;
                                                }
                                                if (curr_cell.next != null) {
                                                        curr_cell.next.prev = curr_cell.prev;
                                                }
                                        }
                                } else {
                                        // search leaf
                                        counter += delete_leaf(oid);
                                }
                        }
                        if (counter > 0) {
                                // some children deleted
                                if (parent != null) {
                                        // resize MBR of parent cell
                                        parent.resize();
                                }
                        }
                }
                else {
                        System.out.println("Error: Null node.");
                }
        }


        //  Delete the first occurence of W from a cell
        void delOneCell(CELL C)
        {
                if (C == this.head)
                        this.head = C.next;
                else
                        C.prev.next = C.next;

                if (C.next != null)
                        C.next.prev = C.prev;

                C.next = null;
                C.prev = null;
        }


	// Sort the MBRs along the given axis.
	node sort(char axis, char order) {

                CELL   pt,pt2;
		CELL   temp_cell;
		node   temp_node, result;
		MBR    targetmbr;

		temp_node = new node();
		temp_cell = this.head;


		// Copy the cells to a temporary list.
		while (temp_cell != null) {
			temp_node.insert(temp_cell.current);
			temp_cell = temp_cell.next;
		}

		result=new node();

		if (order == 'a') {

			// A selection sort is applied.
			while (temp_node.head != null) {
				targetmbr = temp_node.head.current;
			
				pt = temp_node.head;
                                pt2=pt;

				while (pt != null) {
					if (axis=='x' && pt.current.mbr.low[0]>targetmbr.mbr.low[0]) {
						targetmbr=pt.current;
                                                pt2=pt;
					}
					else if (axis=='y' && pt.current.mbr.low[1]>targetmbr.mbr.low[1]) {
						targetmbr=pt.current;
                                                pt2=pt;
					}
					pt=pt.next;
				}
			
                                if (pt2==temp_node.head)
                                {
                                        temp_node.head=temp_node.head.next;
                                }
                                else
                                {
                                        pt2.prev.next=pt2.next;
                                }
                                if (pt2.next!=null)
                                {
                                        pt2.next.prev=pt2.prev;
                                }
				result.insert(targetmbr);
			}
		}
		else if (order == 'd') {

			// A selection sort is applied.
			while (temp_node.head != null) {
				targetmbr = temp_node.head.current;
				pt = temp_node.head;
                                pt2=pt;

				while (pt != null) {
					if (axis=='x' && pt.current.mbr.high[0]<targetmbr.mbr.high[0]) {
						targetmbr=pt.current;
                                                pt2=pt;
					}
					else if (axis=='y' && pt.current.mbr.high[1]<targetmbr.mbr.high[1]) {
						targetmbr=pt.current;
                                                pt2=pt;
					}
					pt=pt.next;
				}

                                if (pt2==temp_node.head)
                                {
                                        temp_node.head=temp_node.head.next;
                                }
                                else
                                {
                                        pt2.prev.next=pt2.next;
                                }
                                if (pt2.next!=null)
                                {
                                        pt2.next.prev=pt2.prev;
                                }
				result.insert(targetmbr);
			}
		}

		return(result);

	}


	// Return the number of cell in node.
	int   getlength()
	{
		CELL  tmp=this.head;
		int   len=0;

		while (tmp != null)
		{
			len++;
			tmp=tmp.next;
		}
		return len;
	}

	// Concate 2 nodes (MBR list) together 
	void    concate(node concat_node)
	{
		CELL  tail;

		if (this.head == null) 
		{
			this.head = concat_node.head;
			return;
		}
		if (concat_node.head == null)
			return;

		tail = this.head;
		while (tail.next != null)
			tail = tail.next;
		tail.next = concat_node.head;
		concat_node.head.prev = tail;
	}

	// Search all the MBR in a leaf node that overlaps with the query window W.
	node    search_leaf(RECT W)
	{
		node   rs;
		CELL   curr_cell;
		MBR    new_mbr;
		
		if ((this.head != null) &&	     // MBR list not empty
			 (this.head.child == null) )   // leaf
		{
			rs = new node();
			curr_cell = this.head;

			while (curr_cell != null)
			{
				if (curr_cell.current.check_overlap(W) == 1)
				{
						new_mbr=new MBR(curr_cell.current.mbr,curr_cell.current.oid);
						rs.insert(new_mbr);
				}
				curr_cell = curr_cell.next;
			}

			return rs;
		}
		else 
		{
			System.out.println("ERROR: Empty MBR List or Not Leaf Node\n");
			return null;
		}
	}

	//  Recursive search for a given query window W that overlap with 
	//  the intermediate node of a R+ tree
	node search_int(RECT W)
	{
		node rs, curr_node;
		CELL curr_cell;

		rs = new node();
		if (this.head.child == null)  // leaf
		{
			rs = this.search_leaf(W);
			return rs;
		}
		else 
		{
			curr_cell = this.head;
			while (curr_cell != null)
			{
				if (curr_cell.current.check_overlap(W) == 1)
				{
					rs.concate(curr_cell.child.search_int(W));
				}
				curr_cell = curr_cell.next;
			}
			return rs;
		}
	}

	void  print()
	{
		CELL  curr_cell;

		curr_cell = this.head;
		while (curr_cell != null)
		{
			curr_cell.current.print();
			curr_cell = curr_cell.next;
		}
	}

        public void recursive_print(int lvl)
	{
		CELL cur_cell;
		node cur_node;

		cur_cell=this.head;

		if (this!=null)
		{
                        while (cur_cell!=null)
			{
                                System.out.print("LEVEL "+lvl+" ");
				cur_cell.current.print();
                                if (cur_cell.child!=null)
                                {
                                        cur_cell.child.recursive_print(lvl+1);
                                }
				cur_cell=cur_cell.next;
			}
		}
	}

	RECT getnodesize()
	{
		CELL ptr=this.head;
		float low[]=new float[2];
		float high[]=new float[2];
		RECT rect;

                rect=new RECT();
                if (ptr!=null)
                {
                        rect=new RECT(ptr.current.mbr.low[0],ptr.current.mbr.low[1],ptr.current.mbr.high[0],ptr.current.mbr.high[1]);
                        ptr=ptr.next;
                        while (ptr!=null)
                        {
                                if (ptr.current.mbr.low[0]<rect.low[0])
                                        rect.low[0]=ptr.current.mbr.low[0];
                                if (ptr.current.mbr.low[1]<rect.low[1])
                                        rect.low[1]=ptr.current.mbr.low[1];
                                if (ptr.current.mbr.high[0]>rect.high[0])
                                        rect.high[0]=ptr.current.mbr.high[0];
                                if (ptr.current.mbr.high[1]>rect.high[1])
                                        rect.high[1]=ptr.current.mbr.high[1];
                                ptr=ptr.next;
                        }
		}
		return rect;
	}

        node pack(node input, int fillfactor)
	{
		node result;
		Partition_info info;
		MBR mbr;
		RECT rect;
                float xcut=0, ycut=0;

		result=new node();
		while (input.head!=null)
		{
                        info=new Partition_info();
			info=this.partition(input, fillfactor);
                        rect=new RECT(info.R.getnodesize());
			mbr=new MBR(rect);
			result.insert(mbr);
                        if (result.head.current.mbr.low[0]<xcut && xcut>0)
                        {
                                result.head.current.mbr.low[0]=xcut;
                                result.head.current.cutxl=xcut;
                        }
                        if (result.head.current.mbr.low[1]<ycut && ycut>0)
                        {
                                result.head.current.mbr.low[1]=ycut;
                                result.head.current.cutyl=ycut;
                        }
                        if (result.head.current.mbr.high[0]>info.xcut && info.xy=='x')
                        {
                                result.head.current.mbr.high[0]=info.xcut;
                                result.head.current.cutxh=info.xcut;
                        }
                        if (result.head.current.mbr.high[1]>info.ycut && info.xy=='y')
                        {
                                result.head.current.mbr.high[1]=info.ycut;
                                result.head.current.cutyh=info.ycut;
                        }
                        if (info.xy=='x')
                        {
                                xcut=info.xcut;
                        }
                        if (info.xy=='y')
                        {
                                ycut=info.ycut;
                        }
			result.head.child=info.R;
                        input.head=info.S.head;
		}
                if (result.getlength()<=fillfactor)
                {
                        return result;
                }

		return this.pack(result, fillfactor);
	}

}