node.java

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

		return(area);

	}

        // Function called by to redistribute nodes in the list
	// by Nelson
	Split_info redistribute_node(int ff, Cut_info cut)
	{
		node tmp,tmp2;
                Split_info info,info2;
		MBR tmpmbr;
		CELL ptr;
                RECT R1,R2, ns1, ns2;
                RECT parent, par2;
                int check1, check2;

		info=new Split_info();
                parent=new RECT();
                if (this.parent!=null)
                {
                        parent.low[0]=this.parent.current.mbr.low[0];
                        parent.low[1]=this.parent.current.mbr.low[1];
                        parent.high[0]=this.parent.current.mbr.high[0];
                        parent.high[1]=this.parent.current.mbr.high[1];
                }
                else
                {
                        parent=this.getnodesize();
                }
                par2=this.getnodesize();
                tmp=new node();
                tmp2=new node();
		tmp.parent=this.parent;
		tmp2.parent=this.parent;
		if (cut.dir=='x')
		{
                        R1=new RECT(parent.low[0],
                                    parent.low[1],
				    cut.cut,
                                    parent.high[1]);
                        R2=new RECT(cut.cut,
                                    parent.low[1],
                                    parent.high[0],
                                    parent.high[1]);
                        info.xcut=cut.cut;
		}
		else
		{
                        R1=new RECT(parent.low[0],
                                    parent.low[1],
                                    parent.high[0],
				    cut.cut);
                        R2=new RECT(parent.low[0],
				    cut.cut,
                                    parent.high[0],
                                    parent.high[1]);
                        info.ycut=cut.cut;
		}

		ptr=this.head;
		while (ptr!=null)
		{
                        check1=ptr.current.check_overlap(R1);
                        check2=ptr.current.check_overlap(R2);

                        if (check1==1 && check2!=1)
                        {
				tmp.insert(ptr.current);
				tmp.head.child=ptr.child;
                                if (tmp.head.child!=null)
                                        tmp.head.child.parent=tmp.head;
			}
                        else if (check1!=1 && check2==1)
                        {
				tmp2.insert(ptr.current);
				tmp2.head.child=ptr.child;
                                if (tmp2.head.child!=null)
                                        tmp2.head.child.parent=tmp2.head;
			}
			else
			{
                                if (ptr.child!=null)
                                {
                                        info2=ptr.child.splitnode(ff, cut);
                                        tmp.insert(ptr.current);
                                        tmp.head.child=ptr.child;
                                        tmp.head.child.parent=tmp.head;

                                        tmpmbr=new MBR(info2.mbr);
                                        tmp2.insert(tmpmbr);
                                        tmp2.head.child=info2.newnode;
                                        tmp2.head.child.parent=tmp2.head;

                                }
                                else
                                {
                                        tmp.insert(ptr.current);
                                        tmp.head.child=ptr.child;
                                        tmp.parent=this.parent;

                                        tmp2.insert(ptr.current);
                                        tmp2.head.child=ptr.child;
                                        tmp2.parent=this.parent;
                                }
			}
			ptr=ptr.next;
		}
		this.head=tmp.head;
		if (this.parent!=null)
		{
			this.parent.current.mbr=R1;
                        info.cutxl=this.parent.current.cutxl;
                        info.cutyl=this.parent.current.cutyl;
                        info.cutxh=this.parent.current.cutxh;
                        info.cutyh=this.parent.current.cutyh;
		}
                info.mbr2=R1;
                info.mbr=R2;
		info.newnode=tmp2;
		return info;
	}

	// Split the called node.  "this" object points to one node, return the new node created
	Split_info  splitnode(int fillfactor, Cut_info input_cut)
	{
		return redistribute_node(fillfactor, input_cut);
	}

        Split_info splitnode(int fillfactor)                     
	{
		Cut_info cut,cut2;


                cut=sweep('x',fillfactor);
		cut.dir='x';
		cut2=sweep('y',fillfactor);
		cut2.dir='y';

                if (cut.cut==-1 && cut2.cut==-1)
                {
                        System.out.println("Cannot split node!  Terminated!");
                        System.exit(1);
                }
                else if (cut.cut==-1)
                {
                        if (cut2.S2.head.getselflength()>fillfactor)
                        {
                                System.out.println("Cannot split node!  Terminated!");
                                System.exit(1);
                        }
                        return redistribute_node(fillfactor, cut2);
                }
                else if (cut2.cut==-1)
                {
                        if (cut.S2.head.getselflength()>fillfactor)
                        {
                                System.out.println("Cannot split node!  Terminated!");
                                System.exit(1);
                        }
                        return redistribute_node(fillfactor, cut);
                }
                else if (cut.cost<=cut2.cost)
		{
                        if (cut.S2.head.getselflength()>fillfactor)
                        {
                                System.out.println("Cannot split node!  Terminated!");
                                System.exit(1);
                        }
			return redistribute_node(fillfactor, cut);
		}

                if (cut2.S2.head.getselflength()>fillfactor)
                {
                        System.out.println("Cannot split node!  Terminated!");
                        System.exit(1);
                }
                return redistribute_node(fillfactor, cut2);
	}

	// Partition.  	return partition_info, a new node R and a list of
	//	     	MBRs in S
	       
	Partition_info  partition(node N, int fillfactor)
	{
		Partition_info result;
		Cut_info xsweep, ysweep ;
		Cut_info select ;
		CELL	tmp, cur, cur_cell ;

		result=new Partition_info();
		result.R.parent = N.parent ;
                if ( N.getlength() <= fillfactor )
		{
                        result.R.head = N.head ; 
			return result;
		}
                xsweep = N.sweep('x', fillfactor) ;
                ysweep = N.sweep('y', fillfactor) ;

                cur=new CELL();
                select=new Cut_info();
                if (xsweep.cost==-1 && ysweep.cost==-1)
                {
                        System.out.println("ERROR : Cannot Split node!!");
                        System.exit(1);
                }
                else if (xsweep.cost==-1 || (xsweep.cost>ysweep.cost && ysweep.cost!=-1))
                {
			select = ysweep ;
			result.xy = 'y' ;
                }
                else
		{
			select = xsweep ;
			result.xy = 'x' ;
		}

		//	create the new node R
                cur = select.S1.head;
                
		while ( cur != null )
		{
			cur_cell = new CELL(cur.current) ;
			
			//	find the child node
			tmp = N.head ;
                        if (tmp!=null)
                        {
                                while ( tmp.current.mbr.low[0] != cur_cell.current.mbr.low[0] ||
                                        tmp.current.mbr.low[1] != cur_cell.current.mbr.low[1] ||
                                        tmp.current.mbr.high[0] != cur_cell.current.mbr.high[0] ||
                                        tmp.current.mbr.high[1] != cur_cell.current.mbr.high[1] )
                                {
                                        tmp = tmp.next ;
                                }
                      
                                cur_cell.child = tmp.child ;
                                cur_cell.current = tmp.current;

                                //      insert into the node
                                if (result.R.head != null)
                                {
                                        result.R.head.prev = cur_cell ;
                                        cur_cell.next = result.R.head ;
                                }
                                result.R.head = cur_cell ;
                        }
                        cur = cur.next ;
                }

                //      create the list S
                cur = select.S2.head ;
		while ( cur != null )
		{
			cur_cell = new CELL(cur.current) ;
			cur_cell.child = cur.child ;
			result.S.insertList(cur_cell) ;
			cur = cur.next ;	
		}
                if (result.xy=='x')
                {
                        result.xcut=select.cut;
                }
                else if (result.xy=='y')
                {
                        result.ycut=select.cut;
                }
		return result;
	}

	//  Delete W from the list of cells in leaf node.
        int     delete_leaf(int oid)
        {
                CELL  curr_cell;

                if (this != null) {
                        for (curr_cell = this.head;
                             curr_cell != null;
                             curr_cell = curr_cell.next) {

                                if (curr_cell.current.oid == oid) {
                                        this.delOneCell(curr_cell);
                                        return(1);
                                }
                        }
                        return(0);
                }
                else {
                        System.out.println("Error: Null leaf node.");
                        return(0);
                }
        }


	// attach new child to node
	void	attach(MBR obj) {
		CELL	new_cell;	// new cell inserted to list

		// create new cell
		new_cell = new CELL(obj);

		// insert into list of cells
		new_cell.next = head;
		if (head == null) {
			head = new_cell;
		} else {
			head.prev = new_cell;
			head	  = new_cell;
		}
	}

	void  insert(MBR W)
	{
		CELL ins_cell;

		ins_cell = new CELL(W);
		ins_cell.next = this.head;
		this.head = ins_cell;
		if (this.head.next != null)
			this.head.next.prev = this.head;
	}

	// insert new node to subtree of this node
	// return number of nodes inserted
        Split_info insert_obj(MBR obj, int fillfactor) {
		int	counter = 0;	// number of nodes inserted
		Split_info sp;
		CELL tmp;
		MBR tmpmbr;

		sp=new Split_info();
		// try to insert data object to children
		for (CELL curr_cell = head;
			  curr_cell != null;
			  curr_cell = curr_cell.next) {
			// check children for overlapping with data object
                        if (curr_cell.current.check_overlap(obj.mbr) == 1 && curr_cell.current.oid ==0) {
				// check if curr_cell is data cell
				if (curr_cell.child != null) {
					// non-data node
					// insert into subtree
					sp=curr_cell.child.insert_obj(obj,fillfactor);
					if (sp.newnode!=null)
                                        {
                                                curr_cell.current.mbr=sp.mbr2;
                                                if (sp.xcut>=0 && (curr_cell.current.cutxh==-1 || sp.xcut<curr_cell.current.cutxh))
                                                        curr_cell.current.cutxh=sp.xcut;
                                                if (sp.ycut>=0 && (curr_cell.current.cutyh==-1 || sp.ycut<curr_cell.current.cutyh))
                                                        curr_cell.current.cutyh=sp.ycut;
                                                curr_cell.resize();
                                                tmpmbr=new MBR(sp.mbr);
						this.insert(tmpmbr);
						this.head.child=sp.newnode;
                                                this.head.child.parent=this.head;
                                                this.head.current.cutxl=sp.cutxl;
                                                this.head.current.cutyl=sp.cutyl;
                                                this.head.current.cutxh=sp.cutxh;
                                                this.head.current.cutyh=sp.cutyh;

                                                if (sp.xcut>=0 && (this.head.current.cutxl==-1 || sp.xcut>this.head.current.cutxl))
                                                        this.head.current.cutxl=sp.xcut;
                                                if (sp.ycut>=0 && (this.head.current.cutyl==-1 || sp.ycut>this.head.current.cutyl))
                                                        this.head.current.cutyl=sp.ycut;
                                                this.head.resize();
					}
                                        else
                                        {
                                                curr_cell.resize();
                                        }
                                        counter++;
				}
			}
		}

		sp=new Split_info();
		if (counter == 0) {
			// attach new child to this node
			attach(obj);
		}