sortbuffer.java

derby database source code.good for you.

		{
			//debug("A7 (ii). The tree has gotten more balanced");
			s.balance = 0;
			return INSERT_OK;
		}

		//debug("A7 (iii). The tree has gotten more out of balance");

		// s.balance == a
		if (r.balance == a)
		{
			//debug("A8. Single rotation");
			p = r;
			s.setLink(a, r.link(-a));
			r.setLink(-a, s);
			s.balance = 0;
			r.balance = 0;
		}
		else // r.balance == -a
		{
			//debug("A8. Double rotation");
			p = r.link(-a);
			r.setLink(-a, p.link(a));
			p.setLink(a, r);
			s.setLink(a, p.link(-a));
			p.setLink(-a, s);

			if (p.balance == a)
			{
				s.balance = -a;
				r.balance = 0;
			}
			else if (p.balance == 0)
			{
				s.balance = 0;
				r.balance = 0;
			}
			else // p.balance == -a
			{
				s.balance = 0;
				r.balance = a;
			}

			p.balance = 0;
		}

		// [A10. Finishing touch]
		if (s == t.rightLink)
			t.rightLink = p;
		else
			t.leftLink = p;

		return INSERT_OK;
	}

	/**
	Return the lowest key and delete it from 
	the tree, preserving the balance of the tree.
	**/
	public DataValueDescriptor[] removeFirst()
	{
		if (head.rightLink == null)
			return null;
		head.rightLink = deleteLeftmost(head.rightLink);
		if (this.subtreeShrunk)
			height--;
		return this.deletedKey;
	}

	/**
	Delete the node with the lowest key from the subtree defined
	by 'thisNode', maintaining balance in the subtree.  Returns
	the node that should be the new root of the subtree.  This
	method sets this.subtreeShrunk if the subtree of thisNode
	decreased in height. Saves the key that was in the deleted
	node in 'deletedKey'.
	**/
	private Node deleteLeftmost(Node thisNode)
	{
		// If this node has no left child, we've found the
		// leftmost one, so delete it.
		if (thisNode.leftLink == null)
		{

			// See if the current node has duplicates.  If so, we'll
			// just return one of them and not change the tree.
			if (thisNode.dupChain != null)
			{
				Node dupNode = thisNode.dupChain;

				//System.out.println("deleteLeftmost(" + thisNode + "): found dup: " + dupNode);

				// Return the key from the duplicate.  Note that even
				// though the keys compare equal they may not be equal,
				// depending on how the column ordering was specified.
				this.deletedKey = dupNode.key;
				lastAux = dupNode.aux;

				// Unlink the dup node and free it.
				thisNode.dupChain = dupNode.dupChain;
				allocator.freeNode(dupNode);
				dupNode = null;

				// Tree is not changing height since we're just removing
				// a node from the duplicate chain.
				this.subtreeShrunk = false;

				// Preserve the current node as the root of this subtree..
				return thisNode;
			}
			else // thisNode.dupChain == null
			{
				//System.out.println("deleteLeftmost(" + thisNode + "): found key");

				// Key to return is this node's key.
				this.deletedKey = thisNode.key;
				lastAux = thisNode.aux;

				// We're removing this node, so it's subtree is shrinking
				// from height 1 to height 0.
				this.subtreeShrunk = true;

				// Save this node's right link which might be cleared
				// out by the allocator.
				Node newRoot = thisNode.rightLink;

				// Free the node we're deleting.
				allocator.freeNode(thisNode);

				// Rearrange the tree to put this node's right subtree where
				// this node was.
				return newRoot;
			}
		}

		// Since this wasn't the leftmost node, delete the leftmost
		// node from this node's left subtree.  This operation may
		// rearrange the subtree, including the possiblility that the
		// root note changed, so set the root of the left subtree to
		// what the delete operation wants it to be.
		thisNode.leftLink = deleteLeftmost(thisNode.leftLink);

		// If the left subtree didn't change size, then this subtree
		// could not have changed size either.
		if (this.subtreeShrunk == false)
			return thisNode;

 		// If the delete operation shrunk the subtree, we may have
		// some rebalancing to do.

		if (thisNode.balance == 1)
		{
			// Tree got more unbalanced.  Need to do some
			// kind of rotation to fix it.  The rotateRight()
			// method will set subtreeShrunk appropriately
			// and return the node that should be the new
			// root of this subtree.
			return rotateRight(thisNode);
		}

		if (thisNode.balance == -1)
		{
			// Tree became more balanced
			thisNode.balance = 0;

			// Since the left subtree was higher, and it
			// shrunk, then this subtree shrunk, too.
			this.subtreeShrunk = true;
		}
		else // thisNode.balance == 0
		{
			// Tree became acceptably unbalanced
			thisNode.balance = 1;

			// We had a balanced tree, and just the left
			// subtree shrunk, so this subtree as a whole
			// has not changed in height.
			this.subtreeShrunk = false;
		}

		// We have not rearranged this subtree.
		return thisNode;
	}

	/**
	Perform either a single or double rotation, as appropriate, 
	to get the subtree 'thisNode' back in balance, assuming
	that the right subtree of 'thisNode' is higher than the
	left subtree.  Returns the node that should be the new
	root of the subtree.
	<P>
	These are the cases depicted in diagrams (1) and (2) of
	Knuth (p. 454), and the node names reflect these diagrams.
	However, in deletion, the single rotation may encounter
	a case where the "beta" and "gamma" subtrees are the same
	height (b.balance == 0), so the resulting does not always
	shrink.
	<P>
    Note: This code will not do the "mirror image" cases.
	It only works when the right subtree is the higher one
	(this is the only case encountered when deleting leftmost
	nodes from the tree).
	**/
	private Node rotateRight(Node thisNode)
	{
		Node a = thisNode;
		Node b = thisNode.rightLink;

		if (b.balance >= 0)
		{
			// single rotation

			a.rightLink = b.leftLink;
			b.leftLink = a;

			if (b.balance == 0)
			{
				a.balance = 1;
				b.balance = -1;
				this.subtreeShrunk = false;
			}
			else // b.balance == 1
			{
				a.balance = 0;
				b.balance = 0;
				this.subtreeShrunk = true;
			}

			return b;
		}
		else // b.balance == -1
		{
			// double rotation

			Node x = b.leftLink;

			a.rightLink = x.leftLink;
			x.leftLink = a;
			b.leftLink = x.rightLink;
			x.rightLink = b;

			if (x.balance == 1)
			{
				a.balance = -1;
				b.balance = 0;
			}
			else if (x.balance == -1)
			{
				a.balance = 0;
				b.balance = 1;
			}
			else // x.balance == 0
			{
				a.balance = 0;
				b.balance = 0;
			}
			x.balance = 0;

			this.subtreeShrunk = true;

			return x;
		}
	}

	public void check()
	{
        if (SanityManager.DEBUG)
        {
            String error = null;
            if (head.rightLink == null)
            {
                if (height != 0)
                    error = "empty tree with height " + height;
            } 
            else
            {
                if (depth(head.rightLink) != height)
                    error = "tree height " + height + " != depth " + depth(head.rightLink);
                else
                    error = checkNode(head.rightLink);
            }
            if (error != null)
            {
                System.out.println("ERROR: " + error);
                print();
                System.exit(1);
            }
        }
	}

	private String checkNode(Node n)
	{
        if (SanityManager.DEBUG)
        {
            if (n == null)
                return null;
            int ld = depth(n.leftLink);
            int rd = depth(n.rightLink);
            if (n.balance != (rd - ld))
                return "node " + n + ": left height " + ld + " right height " + rd;
            
            String e;
            e = checkNode(n.rightLink);
            if (e == null)
                e = checkNode(n.leftLink);
            return e;
        }
        else
        {
            return(null);
        }
	}

	private int depth(Node n)
	{
		int ld = 0;
		int rd = 0;
		if (n == null)
			return 0;
		if (n.leftLink != null)
			ld = depth(n.leftLink);
		if (n.rightLink != null)
			rd = depth(n.rightLink);
		if (rd > ld)
			return rd + 1;
		else
			return ld + 1;
	}

	public void print()
	{
		Node root = head.rightLink;
		System.out.println("tree height: " + height
			+ " root: " + ((root == null) ? -1 : root.id));
		if (root != null)
			printRecursive(root, 0);
	}

	private void printRecursive(Node n, int depth)
	{
		if (n.rightLink != null)
			printRecursive(n.rightLink, depth + 1);
		for (int i = 0; i < depth; i++)
			System.out.print("       ");
		System.out.println(n);
		if (n.leftLink != null)
			printRecursive(n.leftLink, depth + 1);
	}

	private void debug(String s)
	{
        if (SanityManager.DEBUG)
        {
            System.out.println(" === [" + s + "] ===");
        }
	}
}