Commons Collections学习笔记(三)
时间:2011-07-20 博客园 Phinecos
这个Map类是基于红黑树构建的,每个树节点有两个域,一个存放节点的Key,一个存放节点的Value,相当于是两棵红黑树,一棵是关于key的 红黑树,一棵是关于Value的红黑树。
关于红黑树的详细介绍,参考《C#与数据结构--树论--红黑树(Red Black Tree)》这篇文章。
public final class DoubleOrderedMap extends AbstractMap
{
private Node[] rootNode = new Node[] { null, null };//根节点
public Set entrySetByValue()
{//按Value获取Entry集合
if (setOfEntries[VALUE] == null) {
setOfEntries[VALUE] = new AbstractSet() {
public Iterator iterator() {
return new DoubleOrderedMapIterator(VALUE) {
protected Object doGetNext() {
return lastReturnedNode;
}
};
}
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 DoubleOrderedMap.this.size();
}
public void clear() {
DoubleOrderedMap.this.clear();
}
};
}
return setOfEntries[VALUE];
}
private Object doRemove(final Comparable o, final int index)
{
Node node = lookup(o, index);//在红黑树中查找节点
Object rval = null;
if (node != null)
{
rval = node.getData(oppositeIndex(index));
doRedBlackDelete(node);//在红黑树中删除指定节点
}
return rval;
}
private Object doGet(final Comparable o, final int index)
{
checkNonNullComparable(o, index);//检查参数非空
Node node = lookup(o, index);//按Key或Value查找指定节点
return ((node == null)? null: node.getData(oppositeIndex(index)));
}
private Node lookup(final Comparable data, final int i
|