private void swapPosition(final Node x, final Node y, final int index)
{//交换树中两个节点
// Save initial values.
NodexFormerParent = x.getParent(index);
NodexFormerLeftChild= x.getLeft(index);
NodexFormerRightChild = x.getRight(index);
NodeyFormerParent = y.getParent(index);
NodeyFormerLeftChild= y.getLeft(index);
NodeyFormerRightChild = y.getRight(index);
boolean xWasLeftChild =
(x.getParent(index) != null)
&& (x == x.getParent(index).getLeft(index));
boolean yWasLeftChild =
(y.getParent(index) != null)
&& (y == y.getParent(index).getLeft(index));
// Swap, handling special cases of one being the other’s parent.
if (x == yFormerParent) {// x was y’s parent
x.setParent(y, index);
if (yWasLeftChild) {
y.setLeft(x, index);
y.setRight(xFormerRightChild, index);
} else {
y.setRight(x, index);
y.setLeft(xFormerLeftChild, index);
}
} else {
x.setParent(yFormerParent, index);
if (yFormerParent != null) {
if (yWasLeftChild) {
yFormerParent.setLeft(x, index);
} else {
yFormerParent.setRight(x, index);
}
}
y.setLeft(xFormerLeftChild, index);
y.setRight(xFormerRightChild, index);
}
if (y == xFormerParent) {// y was x’s parent
y.setParent(x, index);
if (xWasLeftChild) {
x.setLeft(y, index);
x.setRight(yFormerRightChild, index);
} else {
x.setRight(y, index);
x.setLeft(yFormerLeftChild, index);
}
} else {
y.setParent(xFormerParent, index);
if (xFormerParent != null) {
if (xWasLeftChild) {
xFormerParent.setLeft(y, index);
} else {
xFormerParent.setRight(y, index);
}
}
x.setLeft(yFormerLeftChild, index);
x.setRight(yFormerRightChild, index);
}
// Fix children’s parent pointers
if (x.getLeft(index) != null) {
x.getLeft(index).setParent(x, index);
}
if (x.getRight(index) != null) {
x.getRight(index).setParent(x, index);
}
if (y.getLeft(index) != null) {
y.getLeft(index).setParent(y, index);
}
if (y.getRight(index) != null) {
y.getRight(index).setParent(y, index);
}
x.swapColors(y, index);
// Check if root changed
if (rootNode[index] == x) {
rootNode[index] = y;
} else if (rootNode[index] == y) {
rootNode[index] = x;
}
}
public Object put(final Object key, final Object value)
throws ClassCastException, NullPointerException,
IllegalArgumentException {
checkKeyAndValue(key, value);
Node node = rootNode[KEY];
if (node == null) {//空树
Node root = new Node((Comparable) key, (Comparable) value);
rootNode[KEY] = root;
rootNode[VALUE] = root;
grow();
} else {
while (true) {
int cmp = compare((Comparable) key, node.getData(KEY));
if (cmp == 0) {
throw new IllegalArgumentException(
"Cannot store a duplicate key ("" + key
+ "") in this Map");
} else if (cmp < 0) {
if (node.getLeft(KEY) != null) {
node = node.getLeft(KEY);
} else {
Node newNode = new Node((Comparable) key,
(Comparable) value);
insertValue(newNode);
node.setLeft(newNode, KEY);
newNode.setParent(node, KEY);
doRedBlackInsert(newNode, KEY);
grow();
break;
}
} else {// cmp > 0
if (node.getRight(KEY) != null) {
node = node.getRight(KEY);
} else {
Node newNode = new Node((Comparable) key,
(Comparable) value);
insertValue(newNode);
node.setRight(newNode, KEY);
newNode.setParent(node, KEY);
doRedBlackInsert(newNode, KEY);
grow();
break;
}
}
}
}
return null;
}
private abstract class DoubleOrderedMapIterator implements Iterator
{
private intexpectedModifications;
protected Node lastReturnedNode;//上次访问的节点
private Node nextNode;//下一个节点(最左子节点)
private intiteratorType;
DoubleOrderedMapIterator(final int type)
{
iteratorType= type;
expectedModifications = DoubleOrderedMap.this.modifications;
lastReturnedNode= null;
nextNode= leastNode(rootNode[iteratorType],
iteratorType);
}
protected abstract Object doGetNext();
public final boolean hasNext() {
return nextNode != null;
}
public final Object next()
throws NoSuchElementException,
ConcurrentModificationException {
if (nextNode == null) {
throw new NoSuchElementException();
}
if (modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
lastReturnedNode = nextNode;
nextNode = nextGreater(nextNode, iteratorType);
return doGetNext();
}
public final void remove()
throws IllegalStateException,
ConcurrentModificationException {
if (lastReturnedNode == null) {
throw new IllegalStateException();
}
if (modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
doRedBlackDelete(lastReturnedNode);
expectedModifications++;
lastReturnedNode = null;
}
}
//内部节点类
private static final class Node implements Map.Entry, KeyValue
{
private Comparable[] data;//数据域（key和value）
private Node[] leftNode;//左子节点
private Node[] rightNode;//右子节点
private Node[] parentNode;//父节点
private boolean[]blackColor;//颜色(红或黑)
}
}
责任编辑：小草
