BinaryTreepublic final class BinaryTree extends AbstractMap | Red-Black tree-based implementation of Map. This class guarantees
that the map will be in both ascending key order and ascending
value order, sorted according to the natural order for the key's
and value's classes.
This Map is intended for applications that need to be able to look
up a key-value pairing by either key or value, and need to do so
with equal efficiency.
While that goal could be accomplished by taking a pair of TreeMaps
and redirecting requests to the appropriate TreeMap (e.g.,
containsKey would be directed to the TreeMap that maps values to
keys, containsValue would be directed to the TreeMap that maps keys
to values), there are problems with that implementation,
particularly when trying to keep the two TreeMaps synchronized with
each other. And if the data contained in the TreeMaps is large, the
cost of redundant storage becomes significant.
This solution keeps the data properly synchronized and minimizes
the data storage. The red-black algorithm is based on TreeMap's,
but has been modified to simultaneously map a tree node by key and
by value. This doubles the cost of put operations (but so does
using two TreeMaps), and nearly doubles the cost of remove
operations (there is a savings in that the lookup of the node to be
removed only has to be performed once). And since only one node
contains the key and value, storage is significantly less than that
required by two TreeMaps.
There are some limitations placed on data kept in this Map. The
biggest one is this:
When performing a put operation, neither the key nor the value may
already exist in the Map. In the java.util Map implementations
(HashMap, TreeMap), you can perform a put with an already mapped
key, and neither cares about duplicate values at all ... but this
implementation's put method with throw an IllegalArgumentException
if either the key or the value is already in the Map.
Obviously, that same restriction (and consequence of failing to
heed that restriction) applies to the putAll method.
The Map.Entry instances returned by the appropriate methods will
not allow setValue() and will throw an
UnsupportedOperationException on attempts to call that method.
New methods are added to take advantage of the fact that values are
kept sorted independently of their keys:
Object getKeyForValue(Object value) is the opposite of get; it
takes a value and returns its key, if any.
Object removeValue(Object value) finds and removes the specified
value and returns the now un-used key.
Set entrySetByValue() returns the Map.Entry's in a Set whose
iterator will iterate over the Map.Entry's in ascending order by
their corresponding values.
Set keySetByValue() returns the keys in a Set whose iterator will
iterate over the keys in ascending order by their corresponding
values.
Collection valuesByValue() returns the values in a Collection whose
iterator will iterate over the values in ascending order. |
| Fields Summary |
|---|
| private Node[] | _root | | private int | _size | | private int | _modifications | | private Set[] | _key_set | | private Set[] | _entry_set | | private Collection[] | _value_collection | | private static final int | _KEY | | private static final int | _VALUE | | private static final int | _INDEX_SUM | | private static final int | _MINIMUM_INDEX | | private static final int | _INDEX_COUNT | | private static final String[] | _data_name |
| Constructors Summary |
|---|
public BinaryTree()Construct a new BinaryTree
| public BinaryTree(Map map)Constructs a new BinaryTree from an existing Map, with keys and
values sorted
putAll(map);
|
| Methods Summary |
|---|
| private static void | checkKey(java.lang.Object key)check a key for validity (non-null and implements Comparable)
checkNonNullComparable(key, _KEY);
| | private static void | checkKeyAndValue(java.lang.Object key, java.lang.Object value)check a key and a value for validity (non-null and implements
Comparable)
checkKey(key);
checkValue(value);
| | private static void | checkNonNullComparable(java.lang.Object o, int index)check if an object is fit to be proper input ... has to be
Comparable and non-null
if (o == null)
{
throw new NullPointerException(_data_name[ index ]
+ " cannot be null");
}
if (!(o instanceof Comparable))
{
throw new ClassCastException(_data_name[ index ]
+ " must be Comparable");
}
| | private static void | checkValue(java.lang.Object value)check a value for validity (non-null and implements Comparable)
checkNonNullComparable(value, _VALUE);
| | public void | clear()Removes all mappings from this map
modify();
_size = 0;
_root[ _KEY ] = null;
_root[ _VALUE ] = null;
| | private static int | compare(java.lang.Comparable o1, java.lang.Comparable o2)Compare two objects
return (( Comparable ) o1).compareTo(o2);
| | public boolean | containsKey(java.lang.Object key)Returns true if this map contains a mapping for the specified
key.
checkKey(key);
return lookup(( Comparable ) key, _KEY) != null;
| | public boolean | containsValue(java.lang.Object value)Returns true if this map maps one or more keys to the
specified value.
checkValue(value);
return lookup(( Comparable ) value, _VALUE) != null;
| | private static void | copyColor(org.apache.poi.util.BinaryTree$Node from, org.apache.poi.util.BinaryTree$Node to, int index)copy the color from one node to another, dealing with the fact
that one or both nodes may, in fact, be null
if (to != null)
{
if (from == null)
{
// by default, make it black
to.setBlack(index);
}
else
{
to.copyColor(from, index);
}
}
| | private java.lang.Object | doGet(java.lang.Comparable o, int index)common get logic, used to get by key or get by value
checkNonNullComparable(o, index);
Node node = lookup(o, index);
return ((node == null) ? null
: node.getData(oppositeIndex(index)));
| | private void | doRedBlackDelete(org.apache.poi.util.BinaryTree$Node deleted_node)complicated red-black delete stuff. Based on Sun's TreeMap
implementation, though it's barely recognizeable any more
for (int index = _MINIMUM_INDEX; index < _INDEX_COUNT; index++)
{
// if deleted node has both left and children, swap with
// the next greater node
if ((deleted_node.getLeft(index) != null)
&& (deleted_node.getRight(index) != null))
{
swapPosition(nextGreater(deleted_node, index), deleted_node,
index);
}
Node replacement = ((deleted_node.getLeft(index) != null)
? deleted_node.getLeft(index)
: deleted_node.getRight(index));
if (replacement != null)
{
replacement.setParent(deleted_node.getParent(index), index);
if (deleted_node.getParent(index) == null)
{
_root[ index ] = replacement;
}
else if (deleted_node
== deleted_node.getParent(index).getLeft(index))
{
deleted_node.getParent(index).setLeft(replacement, index);
}
else
{
deleted_node.getParent(index).setRight(replacement,
index);
}
deleted_node.setLeft(null, index);
deleted_node.setRight(null, index);
deleted_node.setParent(null, index);
if (isBlack(deleted_node, index))
{
doRedBlackDeleteFixup(replacement, index);
}
}
else
{
// replacement is null
if (deleted_node.getParent(index) == null)
{
// empty tree
_root[ index ] = null;
}
else
{
// deleted node had no children
if (isBlack(deleted_node, index))
{
doRedBlackDeleteFixup(deleted_node, index);
}
if (deleted_node.getParent(index) != null)
{
if (deleted_node
== deleted_node.getParent(index)
.getLeft(index))
{
deleted_node.getParent(index).setLeft(null,
index);
}
else
{
deleted_node.getParent(index).setRight(null,
index);
}
deleted_node.setParent(null, index);
}
}
}
}
shrink();
| | private void | doRedBlackDeleteFixup(org.apache.poi.util.BinaryTree$Node replacement_node, int index)complicated red-black delete stuff. Based on Sun's TreeMap
implementation, though it's barely recognizeable any more. This
rebalances the tree (somewhat, as red-black trees are not
perfectly balanced -- perfect balancing takes longer)
Node current_node = replacement_node;
while ((current_node != _root[ index ])
&& (isBlack(current_node, index)))
{
if (isLeftChild(current_node, index))
{
Node sibling_node =
getRightChild(getParent(current_node, index), index);
if (isRed(sibling_node, index))
{
makeBlack(sibling_node, index);
makeRed(getParent(current_node, index), index);
rotateLeft(getParent(current_node, index), index);
sibling_node =
getRightChild(getParent(current_node, index), index);
}
if (isBlack(getLeftChild(sibling_node, index), index)
&& isBlack(getRightChild(sibling_node, index), index))
{
makeRed(sibling_node, index);
current_node = getParent(current_node, index);
}
else
{
if (isBlack(getRightChild(sibling_node, index), index))
{
makeBlack(getLeftChild(sibling_node, index), index);
makeRed(sibling_node, index);
rotateRight(sibling_node, index);
sibling_node =
getRightChild(getParent(current_node, index),
index);
}
copyColor(getParent(current_node, index), sibling_node,
index);
makeBlack(getParent(current_node, index), index);
makeBlack(getRightChild(sibling_node, index), index);
rotateLeft(getParent(current_node, index), index);
current_node = _root[ index ];
}
}
else
{
Node sibling_node =
getLeftChild(getParent(current_node, index), index);
if (isRed(sibling_node, index))
{
makeBlack(sibling_node, index);
makeRed(getParent(current_node, index), index);
rotateRight(getParent(current_node, index), index);
sibling_node =
getLeftChild(getParent(current_node, index), index);
}
if (isBlack(getRightChild(sibling_node, index), index)
&& isBlack(getLeftChild(sibling_node, index), index))
{
makeRed(sibling_node, index);
current_node = getParent(current_node, index);
}
else
{
if (isBlack(getLeftChild(sibling_node, index), index))
{
makeBlack(getRightChild(sibling_node, index), index);
makeRed(sibling_node, index);
rotateLeft(sibling_node, index);
sibling_node =
getLeftChild(getParent(current_node, index),
index);
}
copyColor(getParent(current_node, index), sibling_node,
index);
makeBlack(getParent(current_node, index), index);
makeBlack(getLeftChild(sibling_node, index), index);
rotateRight(getParent(current_node, index), index);
current_node = _root[ index ];
}
}
}
makeBlack(current_node, index);
| | private void | doRedBlackInsert(org.apache.poi.util.BinaryTree$Node inserted_node, int index)complicated red-black insert stuff. Based on Sun's TreeMap
implementation, though it's barely recognizeable any more
Node current_node = inserted_node;
makeRed(current_node, index);
while ((current_node != null) && (current_node != _root[ index ])
&& (isRed(current_node.getParent(index), index)))
{
if (isLeftChild(getParent(current_node, index), index))
{
Node y = getRightChild(getGrandParent(current_node, index),
index);
if (isRed(y, index))
{
makeBlack(getParent(current_node, index), index);
makeBlack(y, index);
makeRed(getGrandParent(current_node, index), index);
current_node = getGrandParent(current_node, index);
}
else
{
if (isRightChild(current_node, index))
{
current_node = getParent(current_node, index);
rotateLeft(current_node, index);
}
makeBlack(getParent(current_node, index), index);
makeRed(getGrandParent(current_node, index), index);
if (getGrandParent(current_node, index) != null)
{
rotateRight(getGrandParent(current_node, index),
index);
}
}
}
else
{
// just like clause above, except swap left for right
Node y = getLeftChild(getGrandParent(current_node, index),
index);
if (isRed(y, index))
{
makeBlack(getParent(current_node, index), index);
makeBlack(y, index);
makeRed(getGrandParent(current_node, index), index);
current_node = getGrandParent(current_node, index);
}
else
{
if (isLeftChild(current_node, index))
{
current_node = getParent(current_node, index);
rotateRight(current_node, index);
}
makeBlack(getParent(current_node, index), index);
makeRed(getGrandParent(current_node, index), index);
if (getGrandParent(current_node, index) != null)
{
rotateLeft(getGrandParent(current_node, index),
index);
}
}
}
}
makeBlack(_root[ index ], index);
| | private java.lang.Object | doRemove(java.lang.Comparable o, int index)common remove logic (remove by key or remove by value)
Node node = lookup(o, index);
Object rval = null;
if (node != null)
{
rval = node.getData(oppositeIndex(index));
doRedBlackDelete(node);
}
return rval;
| | public java.util.Set | entrySet()Returns a set view of the mappings contained in this map. Each
element in the returned set is a Map.Entry. The set is backed
by the map, so changes to the map are reflected in the set, and
vice-versa. If the map is modified while an iteration over the
set is in progress, the results of the iteration are
undefined. The set supports element removal, which removes the
corresponding mapping from the map, via the Iterator.remove,
Set.remove, removeAll, retainAll and clear operations. It does
not support the add or addAll operations.
if (_entry_set[ _KEY ] == null)
{
_entry_set[ _KEY ] = new AbstractSet()
{
public Iterator iterator()
{
return new BinaryTreeIterator(_KEY)
{
protected Object doGetNext()
{
return _last_returned_node;
}
};
}
public boolean contains(Object o)
{
if (!(o instanceof Map.Entry))
{
return false;
}
Map.Entry entry = ( Map.Entry ) o;
Object value = entry.getValue();
Node node = lookup(( Comparable ) entry.getKey(),
_KEY);
return (node != null)
&& node.getData(_VALUE).equals(value);
}
public boolean remove(Object o)
{
if (!(o instanceof Map.Entry))
{
return false;
}
Map.Entry entry = ( Map.Entry ) o;
Object value = entry.getValue();
Node node = lookup(( Comparable ) entry.getKey(),
_KEY);
if ((node != null) && node.getData(_VALUE).equals(value))
{
doRedBlackDelete(node);
return true;
}
return false;
}
public int size()
{
return BinaryTree.this.size();
}
public void clear()
{
BinaryTree.this.clear();
}
};
}
return _entry_set[ _KEY ];
| | public java.util.Set | entrySetByValue()Returns a set view of the mappings contained in this map. Each
element in the returned set is a Map.Entry. The set is backed
by the map, so changes to the map are reflected in the set, and
vice-versa. If the map is modified while an iteration over the
set is in progress, the results of the iteration are
undefined. The set supports element removal, which removes the
corresponding mapping from the map, via the Iterator.remove,
Set.remove, removeAll, retainAll and clear operations. It does
not support the add or addAll operations.
The difference between this method and entrySet is that
entrySet's iterator() method returns an iterator that iterates
over the mappings in ascending order by key. This method's
iterator method iterates over the mappings in ascending order
by value.
if (_entry_set[ _VALUE ] == null)
{
_entry_set[ _VALUE ] = new AbstractSet()
{
public Iterator iterator()
{
return new BinaryTreeIterator(_VALUE)
{
protected Object doGetNext()
{
return _last_returned_node;
}
};
}
public boolean contains(Object o)
{
if (!(o instanceof Map.Entry))
{
return false;
}
Map.Entry entry = ( Map.Entry ) o;
Object key = entry.getKey();
Node node = lookup(( Comparable ) entry.getValue(),
_VALUE);
return (node != null) && node.getData(_KEY).equals(key);
}
public boolean remove(Object o)
{
if (!(o instanceof Map.Entry))
{
return false;
}
Map.Entry entry = ( Map.Entry ) o;
Object key = entry.getKey();
Node node = lookup(( Comparable ) entry.getValue(),
_VALUE);
if ((node != null) && node.getData(_KEY).equals(key))
{
doRedBlackDelete(node);
return true;
}
return false;
}
public int size()
{
return BinaryTree.this.size();
}
public void clear()
{
BinaryTree.this.clear();
}
};
}
return _entry_set[ _VALUE ];
| | public java.lang.Object | get(java.lang.Object key)Returns the value to which this map maps the specified
key. Returns null if the map contains no mapping for this key.
return doGet(( Comparable ) key, _KEY);
| | private static org.apache.poi.util.BinaryTree$Node | getGrandParent(org.apache.poi.util.BinaryTree$Node node, int index)get a node's grandparent. mind you, the node, its parent, or
its grandparent may not exist. no problem
return getParent(getParent(node, index), index);
| | public java.lang.Object | getKeyForValue(java.lang.Object value)Returns the key to which this map maps the specified value.
Returns null if the map contains no mapping for this value.
return doGet(( Comparable ) value, _VALUE);
| | private static org.apache.poi.util.BinaryTree$Node | getLeftChild(org.apache.poi.util.BinaryTree$Node node, int index)get a node's left child. mind you, the node may not exist. no
problem
return (node == null) ? null
: node.getLeft(index);
| | private static org.apache.poi.util.BinaryTree$Node | getParent(org.apache.poi.util.BinaryTree$Node node, int index)get a node's parent. mind you, the node, or its parent, may not
exist. no problem
return ((node == null) ? null
: node.getParent(index));
| | private static org.apache.poi.util.BinaryTree$Node | getRightChild(org.apache.poi.util.BinaryTree$Node node, int index)get a node's right child. mind you, the node may not exist. no
problem
return (node == null) ? null
: node.getRight(index);
| | private void | grow()bump up the size and note that the map has changed
modify();
_size++;
| | private void | insertValue(org.apache.poi.util.BinaryTree$Node newNode)insert a node by its value
Node node = _root[ _VALUE ];
while (true)
{
int cmp = compare(newNode.getData(_VALUE), node.getData(_VALUE));
if (cmp == 0)
{
throw new IllegalArgumentException(
"Cannot store a duplicate value (\""
+ newNode.getData(_VALUE) + "\") in this Map");
}
else if (cmp < 0)
{
if (node.getLeft(_VALUE) != null)
{
node = node.getLeft(_VALUE);
}
else
{
node.setLeft(newNode, _VALUE);
newNode.setParent(node, _VALUE);
doRedBlackInsert(newNode, _VALUE);
break;
}
}
else
{ // cmp > 0
if (node.getRight(_VALUE) != null)
{
node = node.getRight(_VALUE);
}
else
{
node.setRight(newNode, _VALUE);
newNode.setParent(node, _VALUE);
doRedBlackInsert(newNode, _VALUE);
break;
}
}
}
| | private static boolean | isBlack(org.apache.poi.util.BinaryTree$Node node, int index)is the specified black red? if the node does not exist, sure,
it's black, thank you
return ((node == null) ? true
: node.isBlack(index));
| | private static boolean | isLeftChild(org.apache.poi.util.BinaryTree$Node node, int index)is this node its parent's left child? mind you, the node, or
its parent, may not exist. no problem. if the node doesn't
exist ... it's its non-existent parent's left child. If the
node does exist but has no parent ... no, we're not the
non-existent parent's left child. Otherwise (both the specified
node AND its parent exist), check.
return (node == null) ? true
: ((node.getParent(index) == null) ? false
: (node
== node.getParent(
index).getLeft(
index)));
| | private static boolean | isRed(org.apache.poi.util.BinaryTree$Node node, int index)is the specified node red? if the node does not exist, no, it's
black, thank you
return ((node == null) ? false
: node.isRed(index));
| | private static boolean | isRightChild(org.apache.poi.util.BinaryTree$Node node, int index)is this node its parent's right child? mind you, the node, or
its parent, may not exist. no problem. if the node doesn't
exist ... it's its non-existent parent's right child. If the
node does exist but has no parent ... no, we're not the
non-existent parent's right child. Otherwise (both the
specified node AND its parent exist), check.
return (node == null) ? true
: ((node.getParent(index) == null) ? false
: (node
== node.getParent(
index).getRight(
index)));
| | public java.util.Set | keySet()Returns a set view of the keys contained in this map. The set
is backed by the map, so changes to the map are reflected in
the set, and vice-versa. If the map is modified while an
iteration over the set is in progress, the results of the
iteration are undefined. The set supports element removal,
which removes the corresponding mapping from the map, via the
Iterator.remove, Set.remove, removeAll, retainAll, and clear
operations. It does not support the add or addAll operations.
if (_key_set[ _KEY ] == null)
{
_key_set[ _KEY ] = new AbstractSet()
{
public Iterator iterator()
{
return new BinaryTreeIterator(_KEY)
{
protected Object doGetNext()
{
return _last_returned_node.getData(_KEY);
}
};
}
public int size()
{
return BinaryTree.this.size();
}
public boolean contains(Object o)
{
return containsKey(o);
}
public boolean remove(Object o)
{
int old_size = _size;
BinaryTree.this.remove(o);
return _size != old_size;
}
public void clear()
{
BinaryTree.this.clear();
}
};
}
return _key_set[ _KEY ];
| | public java.util.Set | keySetByValue()Returns a set view of the keys contained in this map. The set
is backed by the map, so changes to the map are reflected in
the set, and vice-versa. If the map is modified while an
iteration over the set is in progress, the results of the
iteration are undefined. The set supports element removal,
which removes the corresponding mapping from the map, via the
Iterator.remove, Set.remove, removeAll, retainAll, and clear
operations. It does not support the add or addAll
operations.
The difference between this method and keySet is that keySet's
iterator() method returns an iterator that iterates over the
keys in ascending order by key. This method's iterator method
iterates over the keys in ascending order by value.
if (_key_set[ _VALUE ] == null)
{
_key_set[ _VALUE ] = new AbstractSet()
{
public Iterator iterator()
{
return new BinaryTreeIterator(_VALUE)
{
protected Object doGetNext()
{
return _last_returned_node.getData(_KEY);
}
};
}
public int size()
{
return BinaryTree.this.size();
}
public boolean contains(Object o)
{
return containsKey(o);
}
public boolean remove(Object o)
{
int old_size = _size;
BinaryTree.this.remove(o);
return _size != old_size;
}
public void clear()
{
BinaryTree.this.clear();
}
};
}
return _key_set[ _VALUE ];
| | private static org.apache.poi.util.BinaryTree$Node | leastNode(org.apache.poi.util.BinaryTree$Node node, int index)find the least node from a given node. very useful for starting
a sorting iterator ...
Node rval = node;
if (rval != null)
{
while (rval.getLeft(index) != null)
{
rval = rval.getLeft(index);
}
}
return rval;
| | private org.apache.poi.util.BinaryTree$Node | lookup(java.lang.Comparable data, int index)do the actual lookup of a piece of data
Node rval = null;
Node node = _root[ index ];
while (node != null)
{
int cmp = compare(data, node.getData(index));
if (cmp == 0)
{
rval = node;
break;
}
else
{
node = (cmp < 0) ? node.getLeft(index)
: node.getRight(index);
}
}
return rval;
| | private static void | makeBlack(org.apache.poi.util.BinaryTree$Node node, int index)force a node (if it exists) black
if (node != null)
{
node.setBlack(index);
}
| | private static void | makeRed(org.apache.poi.util.BinaryTree$Node node, int index)force a node (if it exists) red
if (node != null)
{
node.setRed(index);
}
| | private void | modify()increment the modification count -- used to check for
concurrent modification of the map through the map and through
an Iterator from one of its Set or Collection views
_modifications++;
| | private org.apache.poi.util.BinaryTree$Node | nextGreater(org.apache.poi.util.BinaryTree$Node node, int index)get the next larger node from the specified node
Node rval = null;
if (node == null)
{
rval = null;
}
else if (node.getRight(index) != null)
{
// everything to the node's right is larger. The least of
// the right node's descendents is the next larger node
rval = leastNode(node.getRight(index), index);
}
else
{
// traverse up our ancestry until we find an ancestor that
// is null or one whose left child is our ancestor. If we
// find a null, then this node IS the largest node in the
// tree, and there is no greater node. Otherwise, we are
// the largest node in the subtree on that ancestor's left
// ... and that ancestor is the next greatest node
Node parent = node.getParent(index);
Node child = node;
while ((parent != null) && (child == parent.getRight(index)))
{
child = parent;
parent = parent.getParent(index);
}
rval = parent;
}
return rval;
| | private int | oppositeIndex(int index)Get the opposite index of the specified index
// old trick ... to find the opposite of a value, m or n,
// subtract the value from the sum of the two possible
// values. (m + n) - m = n; (m + n) - n = m
return _INDEX_SUM - index;
| | public java.lang.Object | put(java.lang.Object key, java.lang.Object value)Associates the specified value with the specified key in this
map.
checkKeyAndValue(key, value);
Node node = _root[ _KEY ];
if (node == null)
{
Node root = new Node(( Comparable ) key, ( Comparable ) value);
_root[ _KEY ] = root;
_root[ _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;
| | public java.lang.Object | remove(java.lang.Object key)Removes the mapping for this key from this map if present
return doRemove(( Comparable ) key, _KEY);
| | public java.lang.Object | removeValue(java.lang.Object value)Removes the mapping for this value from this map if present
return doRemove(( Comparable ) value, _VALUE);
| | private void | rotateLeft(org.apache.poi.util.BinaryTree$Node node, int index)do a rotate left. standard fare in the world of balanced trees
Node right_child = node.getRight(index);
node.setRight(right_child.getLeft(index), index);
if (right_child.getLeft(index) != null)
{
right_child.getLeft(index).setParent(node, index);
}
right_child.setParent(node.getParent(index), index);
if (node.getParent(index) == null)
{
// node was the root ... now its right child is the root
_root[ index ] = right_child;
}
else if (node.getParent(index).getLeft(index) == node)
{
node.getParent(index).setLeft(right_child, index);
}
else
{
node.getParent(index).setRight(right_child, index);
}
right_child.setLeft(node, index);
node.setParent(right_child, index);
| | private void | rotateRight(org.apache.poi.util.BinaryTree$Node node, int index)do a rotate right. standard fare in the world of balanced trees
Node left_child = node.getLeft(index);
node.setLeft(left_child.getRight(index), index);
if (left_child.getRight(index) != null)
{
left_child.getRight(index).setParent(node, index);
}
left_child.setParent(node.getParent(index), index);
if (node.getParent(index) == null)
{
// node was the root ... now its left child is the root
_root[ index ] = left_child;
}
else if (node.getParent(index).getRight(index) == node)
{
node.getParent(index).setRight(left_child, index);
}
else
{
node.getParent(index).setLeft(left_child, index);
}
left_child.setRight(node, index);
node.setParent(left_child, index);
| | private void | shrink()decrement the size and note that the map has changed
modify();
_size--;
| | public int | size()Returns the number of key-value mappings in this map. If the
map contains more than Integer.MAX_VALUE elements, returns
Integer.MAX_VALUE.
return _size;
| | private void | swapPosition(org.apache.poi.util.BinaryTree$Node x, org.apache.poi.util.BinaryTree$Node y, int index)swap two nodes (except for their content), taking care of
special cases where one is the other's parent ... hey, it
happens.
// Save initial values.
Node x_old_parent = x.getParent(index);
Node x_old_left_child = x.getLeft(index);
Node x_old_right_child = x.getRight(index);
Node y_old_parent = y.getParent(index);
Node y_old_left_child = y.getLeft(index);
Node y_old_right_child = y.getRight(index);
boolean x_was_left_child =
(x.getParent(index) != null)
&& (x == x.getParent(index).getLeft(index));
boolean y_was_left_child =
(y.getParent(index) != null)
&& (y == y.getParent(index).getLeft(index));
// Swap, handling special cases of one being the other's parent.
if (x == y_old_parent)
{ // x was y's parent
x.setParent(y, index);
if (y_was_left_child)
{
y.setLeft(x, index);
y.setRight(x_old_right_child, index);
}
else
{
y.setRight(x, index);
y.setLeft(x_old_left_child, index);
}
}
else
{
x.setParent(y_old_parent, index);
if (y_old_parent != null)
{
if (y_was_left_child)
{
y_old_parent.setLeft(x, index);
}
else
{
y_old_parent.setRight(x, index);
}
}
y.setLeft(x_old_left_child, index);
y.setRight(x_old_right_child, index);
}
if (y == x_old_parent)
{ // y was x's parent
y.setParent(x, index);
if (x_was_left_child)
{
x.setLeft(y, index);
x.setRight(y_old_right_child, index);
}
else
{
x.setRight(y, index);
x.setLeft(y_old_left_child, index);
}
}
else
{
y.setParent(x_old_parent, index);
if (x_old_parent != null)
{
if (x_was_left_child)
{
x_old_parent.setLeft(y, index);
}
else
{
x_old_parent.setRight(y, index);
}
}
x.setLeft(y_old_left_child, index);
x.setRight(y_old_right_child, 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 (_root[ index ] == x)
{
_root[ index ] = y;
}
else if (_root[ index ] == y)
{
_root[ index ] = x;
}
| | public java.util.Collection | values()Returns a collection view of the values contained in this
map. The collection is backed by the map, so changes to the map
are reflected in the collection, and vice-versa. If the map is
modified while an iteration over the collection is in progress,
the results of the iteration are undefined. The collection
supports element removal, which removes the corresponding
mapping from the map, via the Iterator.remove,
Collection.remove, removeAll, retainAll and clear operations.
It does not support the add or addAll operations.
if (_value_collection[ _KEY ] == null)
{
_value_collection[ _KEY ] = new AbstractCollection()
{
public Iterator iterator()
{
return new BinaryTreeIterator(_KEY)
{
protected Object doGetNext()
{
return _last_returned_node.getData(_VALUE);
}
};
}
public int size()
{
return BinaryTree.this.size();
}
public boolean contains(Object o)
{
return containsValue(o);
}
public boolean remove(Object o)
{
int old_size = _size;
removeValue(o);
return _size != old_size;
}
public boolean removeAll(Collection c)
{
boolean modified = false;
Iterator iter = c.iterator();
while (iter.hasNext())
{
if (removeValue(iter.next()) != null)
{
modified = true;
}
}
return modified;
}
public void clear()
{
BinaryTree.this.clear();
}
};
}
return _value_collection[ _KEY ];
| | public java.util.Collection | valuesByValue()Returns a collection view of the values contained in this
map. The collection is backed by the map, so changes to the map
are reflected in the collection, and vice-versa. If the map is
modified while an iteration over the collection is in progress,
the results of the iteration are undefined. The collection
supports element removal, which removes the corresponding
mapping from the map, via the Iterator.remove,
Collection.remove, removeAll, retainAll and clear operations.
It does not support the add or addAll operations.
The difference between this method and values is that values's
iterator() method returns an iterator that iterates over the
values in ascending order by key. This method's iterator method
iterates over the values in ascending order by key.
if (_value_collection[ _VALUE ] == null)
{
_value_collection[ _VALUE ] = new AbstractCollection()
{
public Iterator iterator()
{
return new BinaryTreeIterator(_VALUE)
{
protected Object doGetNext()
{
return _last_returned_node.getData(_VALUE);
}
};
}
public int size()
{
return BinaryTree.this.size();
}
public boolean contains(Object o)
{
return containsValue(o);
}
public boolean remove(Object o)
{
int old_size = _size;
removeValue(o);
return _size != old_size;
}
public boolean removeAll(Collection c)
{
boolean modified = false;
Iterator iter = c.iterator();
while (iter.hasNext())
{
if (removeValue(iter.next()) != null)
{
modified = true;
}
}
return modified;
}
public void clear()
{
BinaryTree.this.clear();
}
};
}
return _value_collection[ _VALUE ];
|
|
