0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one or more
0003: * contributor license agreements. See the NOTICE file distributed with
0004: * this work for additional information regarding copyright ownership.
0005: * The ASF licenses this file to You under the Apache License, Version 2.0
0006: * (the "License"); you may not use this file except in compliance with
0007: * the License. You may obtain a copy of the License at
0008: *
0009: * http://www.apache.org/licenses/LICENSE-2.0
0010: *
0011: * Unless required by applicable law or agreed to in writing, software
0012: * distributed under the License is distributed on an "AS IS" BASIS,
0013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014: * See the License for the specific language governing permissions and
0015: * limitations under the License.
0016: */
0017:
0018: package java.util;
0019:
0020: import java.io.IOException;
0021: import java.io.ObjectInputStream;
0022: import java.io.ObjectOutputStream;
0023: import java.io.Serializable;
0024:
0025: /**
0026: * TreeMap is an implementation of SortedMap. All optional operations are
0027: * supported, adding and removing. The values can be any objects. The keys can
0028: * be any objects which are comparable to each other either using their natural
0029: * order or a specified Comparator.
0030: *
0031: * @since 1.2
0032: */
0033: public class TreeMap<K, V> extends AbstractMap<K, V> implements
0034: SortedMap<K, V>, Cloneable, Serializable {
0035: private static final long serialVersionUID = 919286545866124006L;
0036:
0037: transient int size;
0038:
0039: private Comparator<? super K> comparator;
0040:
0041: transient int modCount;
0042:
0043: transient Set<Map.Entry<K, V>> entrySet;
0044:
0045: transient Node<K, V> root;
0046:
0047: class MapEntry implements Map.Entry<K, V>, Cloneable {
0048:
0049: final int offset;
0050: final Node<K, V> node;
0051: final K key;
0052:
0053: MapEntry(Node<K, V> node, int offset) {
0054: this .node = node;
0055: this .offset = offset;
0056: key = node.keys[offset];
0057: }
0058:
0059: @Override
0060: public Object clone() {
0061: try {
0062: return super .clone();
0063: } catch (CloneNotSupportedException e) {
0064: return null;
0065: }
0066: }
0067:
0068: @Override
0069: public boolean equals(Object object) {
0070: if (this == object) {
0071: return true;
0072: }
0073: if (object instanceof Map.Entry) {
0074: Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
0075: V value = getValue();
0076: return (key == null ? entry.getKey() == null : key
0077: .equals(entry.getKey()))
0078: && (value == null ? entry.getValue() == null
0079: : value.equals(entry.getValue()));
0080: }
0081: return false;
0082: }
0083:
0084: public K getKey() {
0085: return key;
0086: }
0087:
0088: public V getValue() {
0089: if (node.keys[offset] == key) {
0090: return node.values[offset];
0091: }
0092: if (containsKey(key)) {
0093: return get(key);
0094: }
0095: throw new IllegalStateException();
0096: }
0097:
0098: @Override
0099: public int hashCode() {
0100: V value = getValue();
0101: return (key == null ? 0 : key.hashCode())
0102: ^ (value == null ? 0 : value.hashCode());
0103: }
0104:
0105: public V setValue(V object) {
0106: if (node.keys[offset] == key) {
0107: V res = node.values[offset];
0108: node.values[offset] = object;
0109: return res;
0110: }
0111: if (containsKey(key)) {
0112: return put(key, object);
0113: }
0114: throw new IllegalStateException();
0115: }
0116:
0117: @Override
0118: public String toString() {
0119: return key + "=" + getValue();
0120: }
0121: }
0122:
0123: static class Node<K, V> implements Cloneable {
0124: static final int NODE_SIZE = 64;
0125: Node<K, V> prev, next;
0126: Node<K, V> parent, left, right;
0127: V[] values;
0128: K[] keys;
0129: int left_idx = 0;
0130: int right_idx = -1;
0131: int size = 0;
0132: boolean color;
0133:
0134: public Node() {
0135: keys = (K[]) new Object[NODE_SIZE];
0136: values = (V[]) new Object[NODE_SIZE];
0137: }
0138:
0139: @SuppressWarnings("unchecked")
0140: Node<K, V> clone(Node<K, V> parent)
0141: throws CloneNotSupportedException {
0142: Node<K, V> clone = (Node<K, V>) super .clone();
0143: clone.keys = (K[]) new Object[NODE_SIZE];
0144: clone.values = (V[]) new Object[NODE_SIZE];
0145: System.arraycopy(keys, 0, clone.keys, 0, keys.length);
0146: System.arraycopy(values, 0, clone.values, 0, values.length);
0147: clone.left_idx = left_idx;
0148: clone.right_idx = right_idx;
0149: clone.parent = parent;
0150: if (left != null) {
0151: clone.left = left.clone(clone);
0152: }
0153: if (right != null) {
0154: clone.right = right.clone(clone);
0155: }
0156: clone.prev = null;
0157: clone.next = null;
0158: return clone;
0159: }
0160: }
0161:
0162: @SuppressWarnings("unchecked")
0163: private static <T> Comparable<T> toComparable(T obj) {
0164: return (Comparable) obj;
0165: }
0166:
0167: static class AbstractMapIterator<K, V> {
0168: TreeMap<K, V> backingMap;
0169: int expectedModCount;
0170: Node<K, V> node;
0171: Node<K, V> lastNode;
0172: int offset;
0173: int lastOffset;
0174:
0175: AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode,
0176: int startOffset) {
0177: backingMap = map;
0178: expectedModCount = map.modCount;
0179: node = startNode;
0180: offset = startOffset;
0181: }
0182:
0183: AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode) {
0184: this (map, startNode,
0185: startNode != null ? startNode.right_idx
0186: - startNode.left_idx : 0);
0187: }
0188:
0189: AbstractMapIterator(TreeMap<K, V> map) {
0190: this (map, minimum(map.root));
0191: }
0192:
0193: public boolean hasNext() {
0194: return node != null;
0195: }
0196:
0197: final void makeNext() {
0198: if (expectedModCount != backingMap.modCount) {
0199: throw new ConcurrentModificationException();
0200: } else if (node == null) {
0201: throw new NoSuchElementException();
0202: }
0203: lastNode = node;
0204: lastOffset = offset;
0205: if (offset != 0) {
0206: offset--;
0207: } else {
0208: node = node.next;
0209: if (node != null) {
0210: offset = node.right_idx - node.left_idx;
0211: }
0212: }
0213: }
0214:
0215: final public void remove() {
0216: if (expectedModCount == backingMap.modCount) {
0217: if (lastNode != null) {
0218: int idx = lastNode.right_idx - lastOffset;
0219: backingMap.removeFromIterator(lastNode, idx);
0220: lastNode = null;
0221: expectedModCount++;
0222: } else {
0223: throw new IllegalStateException();
0224: }
0225: } else {
0226: throw new ConcurrentModificationException();
0227: }
0228: }
0229: }
0230:
0231: static class UnboundedEntryIterator<K, V> extends
0232: AbstractMapIterator<K, V> implements
0233: Iterator<Map.Entry<K, V>> {
0234:
0235: UnboundedEntryIterator(TreeMap<K, V> map, Node<K, V> startNode,
0236: int startOffset) {
0237: super (map, startNode, startOffset);
0238: }
0239:
0240: UnboundedEntryIterator(TreeMap<K, V> map) {
0241: super (map);
0242: }
0243:
0244: public Map.Entry<K, V> next() {
0245: makeNext();
0246: int idx = lastNode.right_idx - lastOffset;
0247: return backingMap.new MapEntry(lastNode, idx);
0248: }
0249: }
0250:
0251: static class UnboundedKeyIterator<K, V> extends
0252: AbstractMapIterator<K, V> implements Iterator<K> {
0253:
0254: UnboundedKeyIterator(TreeMap<K, V> map, Node<K, V> startNode,
0255: int startOffset) {
0256: super (map, startNode, startOffset);
0257: }
0258:
0259: UnboundedKeyIterator(TreeMap<K, V> map) {
0260: super (map);
0261: }
0262:
0263: public K next() {
0264: makeNext();
0265: return lastNode.keys[lastNode.right_idx - lastOffset];
0266: }
0267: }
0268:
0269: static class UnboundedValueIterator<K, V> extends
0270: AbstractMapIterator<K, V> implements Iterator<V> {
0271:
0272: UnboundedValueIterator(TreeMap<K, V> map, Node<K, V> startNode,
0273: int startOffset) {
0274: super (map, startNode, startOffset);
0275: }
0276:
0277: UnboundedValueIterator(TreeMap<K, V> map) {
0278: super (map);
0279: }
0280:
0281: public V next() {
0282: makeNext();
0283: return lastNode.values[lastNode.right_idx - lastOffset];
0284: }
0285: }
0286:
0287: static class BoundedMapIterator<K, V> extends
0288: AbstractMapIterator<K, V> {
0289:
0290: Node<K, V> finalNode;
0291: int finalOffset;
0292:
0293: BoundedMapIterator(Node<K, V> startNode, int startOffset,
0294: TreeMap<K, V> map, Node<K, V> finalNode, int finalOffset) {
0295: super (map, finalNode == null ? null : startNode,
0296: startOffset);
0297: this .finalNode = finalNode;
0298: this .finalOffset = finalOffset;
0299: }
0300:
0301: BoundedMapIterator(Node<K, V> startNode, TreeMap<K, V> map,
0302: Node<K, V> finalNode, int finalOffset) {
0303: this (startNode, startNode != null ? startNode.right_idx
0304: - startNode.left_idx : 0, map, finalNode,
0305: finalOffset);
0306: }
0307:
0308: BoundedMapIterator(Node<K, V> startNode, int startOffset,
0309: TreeMap<K, V> map, Node<K, V> finalNode) {
0310: this (startNode, startOffset, map, finalNode,
0311: finalNode.right_idx - finalNode.left_idx);
0312: }
0313:
0314: void makeBoundedNext() {
0315: makeNext();
0316: if (lastNode == finalNode && lastOffset == finalOffset) {
0317: node = null;
0318: }
0319: }
0320: }
0321:
0322: static class BoundedEntryIterator<K, V> extends
0323: BoundedMapIterator<K, V> implements
0324: Iterator<Map.Entry<K, V>> {
0325:
0326: public BoundedEntryIterator(Node<K, V> startNode,
0327: int startOffset, TreeMap<K, V> map,
0328: Node<K, V> finalNode, int finalOffset) {
0329: super (startNode, startOffset, map, finalNode, finalOffset);
0330: }
0331:
0332: public Map.Entry<K, V> next() {
0333: makeBoundedNext();
0334: int idx = lastNode.right_idx - lastOffset;
0335: return backingMap.new MapEntry(lastNode, idx);
0336: }
0337: }
0338:
0339: static class BoundedKeyIterator<K, V> extends
0340: BoundedMapIterator<K, V> implements Iterator<K> {
0341:
0342: public BoundedKeyIterator(Node<K, V> startNode,
0343: int startOffset, TreeMap<K, V> map,
0344: Node<K, V> finalNode, int finalOffset) {
0345: super (startNode, startOffset, map, finalNode, finalOffset);
0346: }
0347:
0348: public K next() {
0349: makeBoundedNext();
0350: return lastNode.keys[lastNode.right_idx - lastOffset];
0351: }
0352: }
0353:
0354: static class BoundedValueIterator<K, V> extends
0355: BoundedMapIterator<K, V> implements Iterator<V> {
0356:
0357: public BoundedValueIterator(Node<K, V> startNode,
0358: int startOffset, TreeMap<K, V> map,
0359: Node<K, V> finalNode, int finalOffset) {
0360: super (startNode, startOffset, map, finalNode, finalOffset);
0361: }
0362:
0363: public V next() {
0364: makeBoundedNext();
0365: return lastNode.values[lastNode.right_idx - lastOffset];
0366: }
0367: }
0368:
0369: static final class SubMap<K, V> extends AbstractMap<K, V> implements
0370: SortedMap<K, V>, Serializable {
0371: private static final long serialVersionUID = -6520786458950516097L;
0372:
0373: private TreeMap<K, V> backingMap;
0374:
0375: boolean hasStart, hasEnd;
0376: K startKey, endKey;
0377: transient Set<Map.Entry<K, V>> entrySet = null;
0378: transient int firstKeyModCount = -1;
0379: transient int lastKeyModCount = -1;
0380: transient Node<K, V> firstKeyNode;
0381: transient int firstKeyIndex;
0382: transient Node<K, V> lastKeyNode;
0383: transient int lastKeyIndex;
0384:
0385: SubMap(K start, TreeMap<K, V> map) {
0386: backingMap = map;
0387: hasStart = true;
0388: startKey = start;
0389: }
0390:
0391: SubMap(K start, TreeMap<K, V> map, K end) {
0392: backingMap = map;
0393: hasStart = hasEnd = true;
0394: startKey = start;
0395: endKey = end;
0396: }
0397:
0398: SubMap(TreeMap<K, V> map, K end) {
0399: backingMap = map;
0400: hasEnd = true;
0401: endKey = end;
0402: }
0403:
0404: private void checkRange(K key) {
0405: Comparator<? super K> cmp = backingMap.comparator;
0406: if (cmp == null) {
0407: Comparable<K> object = toComparable(key);
0408: if (hasStart && object.compareTo(startKey) < 0) {
0409: throw new IllegalArgumentException();
0410: }
0411: if (hasEnd && object.compareTo(endKey) > 0) {
0412: throw new IllegalArgumentException();
0413: }
0414: } else {
0415: if (hasStart
0416: && backingMap.comparator().compare(key,
0417: startKey) < 0) {
0418: throw new IllegalArgumentException();
0419: }
0420: if (hasEnd
0421: && backingMap.comparator().compare(key, endKey) > 0) {
0422: throw new IllegalArgumentException();
0423: }
0424: }
0425: }
0426:
0427: private boolean isInRange(K key) {
0428: Comparator<? super K> cmp = backingMap.comparator;
0429: if (cmp == null) {
0430: Comparable<K> object = toComparable(key);
0431: if (hasStart && object.compareTo(startKey) < 0) {
0432: return false;
0433: }
0434: if (hasEnd && object.compareTo(endKey) >= 0) {
0435: return false;
0436: }
0437: } else {
0438: if (hasStart && cmp.compare(key, startKey) < 0) {
0439: return false;
0440: }
0441: if (hasEnd && cmp.compare(key, endKey) >= 0) {
0442: return false;
0443: }
0444: }
0445: return true;
0446: }
0447:
0448: private boolean checkUpperBound(K key) {
0449: if (hasEnd) {
0450: Comparator<? super K> cmp = backingMap.comparator;
0451: if (cmp == null) {
0452: return (toComparable(key).compareTo(endKey) < 0);
0453: }
0454: return (cmp.compare(key, endKey) < 0);
0455: }
0456: return true;
0457: }
0458:
0459: private boolean checkLowerBound(K key) {
0460: if (hasStart) {
0461: Comparator<? super K> cmp = backingMap.comparator;
0462: if (cmp == null) {
0463: return (toComparable(key).compareTo(startKey) >= 0);
0464: }
0465: return (cmp.compare(key, startKey) >= 0);
0466: }
0467: return true;
0468: }
0469:
0470: public Comparator<? super K> comparator() {
0471: return backingMap.comparator();
0472: }
0473:
0474: @SuppressWarnings("unchecked")
0475: @Override
0476: public boolean containsKey(Object key) {
0477: if (isInRange((K) key)) {
0478: return backingMap.containsKey(key);
0479: }
0480: return false;
0481: }
0482:
0483: @Override
0484: public void clear() {
0485: keySet().clear();
0486: }
0487:
0488: @Override
0489: public boolean containsValue(Object value) {
0490: Iterator<V> it = values().iterator();
0491: if (value != null) {
0492: while (it.hasNext()) {
0493: if (value.equals(it.next())) {
0494: return true;
0495: }
0496: }
0497: } else {
0498: while (it.hasNext()) {
0499: if (it.next() == null) {
0500: return true;
0501: }
0502: }
0503: }
0504: return false;
0505: }
0506:
0507: @Override
0508: public Set<Map.Entry<K, V>> entrySet() {
0509: if (entrySet == null) {
0510: entrySet = new SubMapEntrySet<K, V>(this );
0511: }
0512: return entrySet;
0513: }
0514:
0515: private void setFirstKey() {
0516: if (firstKeyModCount == backingMap.modCount) {
0517: return;
0518: }
0519: Comparable<K> object = backingMap.comparator == null ? toComparable((K) startKey)
0520: : null;
0521: K key = (K) startKey;
0522: Node<K, V> node = backingMap.root;
0523: Node<K, V> foundNode = null;
0524: int foundIndex = -1;
0525: TOP_LOOP: while (node != null) {
0526: K[] keys = node.keys;
0527: int left_idx = node.left_idx;
0528: int result = backingMap
0529: .cmp(object, key, keys[left_idx]);
0530: if (result < 0) {
0531: foundNode = node;
0532: foundIndex = left_idx;
0533: node = node.left;
0534: } else if (result == 0) {
0535: foundNode = node;
0536: foundIndex = left_idx;
0537: break;
0538: } else {
0539: int right_idx = node.right_idx;
0540: if (left_idx != right_idx) {
0541: result = backingMap.cmp(object, key,
0542: keys[right_idx]);
0543: }
0544: if (result > 0) {
0545: node = node.right;
0546: } else if (result == 0) {
0547: foundNode = node;
0548: foundIndex = right_idx;
0549: break;
0550: } else { /*search in node*/
0551: foundNode = node;
0552: foundIndex = right_idx;
0553: int low = left_idx + 1, mid = 0, high = right_idx - 1;
0554: while (low <= high) {
0555: mid = (low + high) >> 1;
0556: result = backingMap.cmp(object, key,
0557: keys[mid]);
0558: if (result > 0) {
0559: low = mid + 1;
0560: } else if (result == 0) {
0561: foundNode = node;
0562: foundIndex = mid;
0563: break TOP_LOOP;
0564: } else {
0565: foundNode = node;
0566: foundIndex = mid;
0567: high = mid - 1;
0568: }
0569: }
0570: break TOP_LOOP;
0571: }
0572: }
0573: }
0574: if (foundNode != null
0575: && !checkUpperBound(foundNode.keys[foundIndex])) {
0576: foundNode = null;
0577: }
0578: firstKeyNode = foundNode;
0579: firstKeyIndex = foundIndex;
0580: firstKeyModCount = backingMap.modCount;
0581: }
0582:
0583: public K firstKey() {
0584: if (backingMap.size > 0) {
0585: if (!hasStart) {
0586: Node<K, V> node = minimum(backingMap.root);
0587: if (node != null
0588: && checkUpperBound(node.keys[node.left_idx])) {
0589: return node.keys[node.left_idx];
0590: }
0591: } else {
0592: setFirstKey();
0593: if (firstKeyNode != null) {
0594: return firstKeyNode.keys[firstKeyIndex];
0595: }
0596: }
0597: }
0598: throw new NoSuchElementException();
0599: }
0600:
0601: @SuppressWarnings("unchecked")
0602: @Override
0603: public V get(Object key) {
0604: if (isInRange((K) key)) {
0605: return backingMap.get(key);
0606: }
0607: return null;
0608: }
0609:
0610: public SortedMap<K, V> headMap(K endKey) {
0611: checkRange(endKey);
0612: if (hasStart) {
0613: return new SubMap<K, V>(startKey, backingMap, endKey);
0614: }
0615: return new SubMap<K, V>(backingMap, endKey);
0616: }
0617:
0618: @Override
0619: public boolean isEmpty() {
0620: if (hasStart) {
0621: setFirstKey();
0622: return firstKeyNode == null;
0623: } else {
0624: setLastKey();
0625: return lastKeyNode == null;
0626: }
0627: }
0628:
0629: @Override
0630: public Set<K> keySet() {
0631: if (keySet == null) {
0632: keySet = new SubMapKeySet<K, V>(this );
0633: }
0634: return keySet;
0635: }
0636:
0637: private void setLastKey() {
0638: if (lastKeyModCount == backingMap.modCount) {
0639: return;
0640: }
0641: Comparable<K> object = backingMap.comparator == null ? toComparable((K) endKey)
0642: : null;
0643: K key = (K) endKey;
0644: Node<K, V> node = backingMap.root;
0645: Node<K, V> foundNode = null;
0646: int foundIndex = -1;
0647: TOP_LOOP: while (node != null) {
0648: K[] keys = node.keys;
0649: int left_idx = node.left_idx;
0650: int result = backingMap
0651: .cmp(object, key, keys[left_idx]);
0652: if (result <= 0) {
0653: node = node.left;
0654: } else {
0655: int right_idx = node.right_idx;
0656: if (left_idx != right_idx) {
0657: result = backingMap.cmp(object, key,
0658: keys[right_idx]);
0659: }
0660: if (result > 0) {
0661: foundNode = node;
0662: foundIndex = right_idx;
0663: node = node.right;
0664: } else if (result == 0) {
0665: if (node.left_idx == node.right_idx) {
0666: foundNode = node.prev;
0667: if (foundNode != null) {
0668: foundIndex = foundNode.right_idx - 1;
0669: }
0670: } else {
0671: foundNode = node;
0672: foundIndex = right_idx - 1;
0673: }
0674: break;
0675: } else { /*search in node*/
0676: foundNode = node;
0677: foundIndex = left_idx;
0678: int low = left_idx + 1, mid = 0, high = right_idx - 1;
0679: while (low <= high) {
0680: mid = (low + high) >> 1;
0681: result = backingMap.cmp(object, key,
0682: keys[mid]);
0683: if (result > 0) {
0684: foundNode = node;
0685: foundIndex = mid;
0686: low = mid + 1;
0687: } else if (result == 0) {
0688: foundNode = node;
0689: foundIndex = mid - 1;
0690: break TOP_LOOP;
0691: } else {
0692: high = mid - 1;
0693: }
0694: }
0695: break TOP_LOOP;
0696: }
0697: }
0698: }
0699: if (foundNode != null
0700: && !checkLowerBound(foundNode.keys[foundIndex])) {
0701: foundNode = null;
0702: }
0703: lastKeyNode = foundNode;
0704: lastKeyIndex = foundIndex;
0705: lastKeyModCount = backingMap.modCount;
0706: }
0707:
0708: public K lastKey() {
0709: if (backingMap.size > 0) {
0710: if (!hasEnd) {
0711: Node<K, V> node = maximum(backingMap.root);
0712: if (node != null
0713: && checkLowerBound(node.keys[node.right_idx])) {
0714: return node.keys[node.right_idx];
0715: }
0716: } else {
0717: setLastKey();
0718: if (lastKeyNode != null) {
0719: return lastKeyNode.keys[lastKeyIndex];
0720: }
0721: }
0722: }
0723: throw new NoSuchElementException();
0724: }
0725:
0726: @Override
0727: public V put(K key, V value) {
0728: if (isInRange(key)) {
0729: return backingMap.put(key, value);
0730: }
0731: throw new IllegalArgumentException();
0732: }
0733:
0734: @SuppressWarnings("unchecked")
0735: @Override
0736: public V remove(Object key) {
0737: if (isInRange((K) key)) {
0738: return backingMap.remove(key);
0739: }
0740: return null;
0741: }
0742:
0743: public SortedMap<K, V> subMap(K startKey, K endKey) {
0744: checkRange(startKey);
0745: checkRange(endKey);
0746: Comparator<? super K> c = backingMap.comparator();
0747: if (c == null) {
0748: if (toComparable(startKey).compareTo(endKey) <= 0) {
0749: return new SubMap<K, V>(startKey, backingMap,
0750: endKey);
0751: }
0752: } else {
0753: if (c.compare(startKey, endKey) <= 0) {
0754: return new SubMap<K, V>(startKey, backingMap,
0755: endKey);
0756: }
0757: }
0758: throw new IllegalArgumentException();
0759: }
0760:
0761: public SortedMap<K, V> tailMap(K startKey) {
0762: checkRange(startKey);
0763: if (hasEnd) {
0764: return new SubMap<K, V>(startKey, backingMap, endKey);
0765: }
0766: return new SubMap<K, V>(startKey, backingMap);
0767: }
0768:
0769: @Override
0770: public Collection<V> values() {
0771: if (valuesCollection == null) {
0772: valuesCollection = new SubMapValuesCollection<K, V>(
0773: this );
0774: }
0775: return valuesCollection;
0776: }
0777:
0778: public int size() {
0779: Node<K, V> from, to;
0780: int fromIndex, toIndex;
0781: if (hasStart) {
0782: setFirstKey();
0783: from = firstKeyNode;
0784: fromIndex = firstKeyIndex;
0785: } else {
0786: from = minimum(backingMap.root);
0787: fromIndex = from == null ? 0 : from.left_idx;
0788: }
0789: if (from == null) {
0790: return 0;
0791: }
0792: if (hasEnd) {
0793: setLastKey();
0794: to = lastKeyNode;
0795: toIndex = lastKeyIndex;
0796: } else {
0797: to = maximum(backingMap.root);
0798: toIndex = to == null ? 0 : to.right_idx;
0799: }
0800: if (to == null) {
0801: return 0;
0802: }
0803: if (from == to) {
0804: return toIndex - fromIndex + 1;
0805: }
0806: int sum = 0;
0807: while (from != to) {
0808: sum += (from.right_idx - fromIndex + 1);
0809: from = from.next;
0810: fromIndex = from.left_idx;
0811: }
0812: return sum + toIndex - fromIndex + 1;
0813: }
0814:
0815: private void readObject(ObjectInputStream stream)
0816: throws IOException, ClassNotFoundException {
0817: stream.defaultReadObject();
0818: firstKeyModCount = -1;
0819: lastKeyModCount = -1;
0820: }
0821: }
0822:
0823: static class SubMapEntrySet<K, V> extends
0824: AbstractSet<Map.Entry<K, V>> implements
0825: Set<Map.Entry<K, V>> {
0826: SubMap<K, V> subMap;
0827:
0828: SubMapEntrySet(SubMap<K, V> map) {
0829: subMap = map;
0830: }
0831:
0832: @Override
0833: public boolean isEmpty() {
0834: return subMap.isEmpty();
0835: }
0836:
0837: public Iterator<Map.Entry<K, V>> iterator() {
0838: Node<K, V> from;
0839: int fromIndex;
0840: if (subMap.hasStart) {
0841: subMap.setFirstKey();
0842: from = subMap.firstKeyNode;
0843: fromIndex = subMap.firstKeyIndex;
0844: } else {
0845: from = minimum(subMap.backingMap.root);
0846: fromIndex = from != null ? from.left_idx : 0;
0847: }
0848: if (!subMap.hasEnd) {
0849: return new UnboundedEntryIterator<K, V>(
0850: subMap.backingMap, from, from == null ? 0
0851: : from.right_idx - fromIndex);
0852: }
0853: subMap.setLastKey();
0854: Node<K, V> to = subMap.lastKeyNode;
0855: int toIndex = subMap.lastKeyIndex;
0856: return new BoundedEntryIterator<K, V>(from,
0857: from == null ? 0 : from.right_idx - fromIndex,
0858: subMap.backingMap, to, to == null ? 0
0859: : to.right_idx - toIndex);
0860: }
0861:
0862: @Override
0863: public int size() {
0864: return subMap.size();
0865: }
0866:
0867: @SuppressWarnings("unchecked")
0868: @Override
0869: public boolean contains(Object object) {
0870: if (object instanceof Map.Entry) {
0871: Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
0872: K key = entry.getKey();
0873: if (subMap.isInRange(key)) {
0874: V v1 = subMap.get(key), v2 = entry.getValue();
0875: return v1 == null ? v2 == null : v1.equals(v2);
0876: }
0877: }
0878: return false;
0879: }
0880:
0881: @Override
0882: public boolean remove(Object object) {
0883: if (contains(object)) {
0884: Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
0885: K key = entry.getKey();
0886: subMap.remove(key);
0887: return true;
0888: }
0889: return false;
0890: }
0891: }
0892:
0893: static class SubMapKeySet<K, V> extends AbstractSet<K> implements
0894: Set<K> {
0895: SubMap<K, V> subMap;
0896:
0897: SubMapKeySet(SubMap<K, V> map) {
0898: subMap = map;
0899: }
0900:
0901: @Override
0902: public boolean contains(Object object) {
0903: return subMap.containsKey(object);
0904: }
0905:
0906: @Override
0907: public boolean isEmpty() {
0908: return subMap.isEmpty();
0909: }
0910:
0911: @Override
0912: public int size() {
0913: return subMap.size();
0914: }
0915:
0916: @Override
0917: public boolean remove(Object object) {
0918: if (subMap.containsKey(object)) {
0919: subMap.remove(object);
0920: return true;
0921: }
0922: return false;
0923: }
0924:
0925: public Iterator<K> iterator() {
0926: Node<K, V> from;
0927: int fromIndex;
0928: if (subMap.hasStart) {
0929: subMap.setFirstKey();
0930: from = subMap.firstKeyNode;
0931: fromIndex = subMap.firstKeyIndex;
0932: } else {
0933: from = minimum(subMap.backingMap.root);
0934: fromIndex = from != null ? from.left_idx : 0;
0935: }
0936: if (!subMap.hasEnd) {
0937: return new UnboundedKeyIterator<K, V>(
0938: subMap.backingMap, from, from == null ? 0
0939: : from.right_idx - fromIndex);
0940: }
0941: subMap.setLastKey();
0942: Node<K, V> to = subMap.lastKeyNode;
0943: int toIndex = subMap.lastKeyIndex;
0944: return new BoundedKeyIterator<K, V>(from, from == null ? 0
0945: : from.right_idx - fromIndex, subMap.backingMap,
0946: to, to == null ? 0 : to.right_idx - toIndex);
0947: }
0948: }
0949:
0950: static class SubMapValuesCollection<K, V> extends
0951: AbstractCollection<V> {
0952: SubMap<K, V> subMap;
0953:
0954: public SubMapValuesCollection(SubMap<K, V> subMap) {
0955: this .subMap = subMap;
0956: }
0957:
0958: @Override
0959: public boolean isEmpty() {
0960: return subMap.isEmpty();
0961: }
0962:
0963: @Override
0964: public Iterator<V> iterator() {
0965: Node<K, V> from;
0966: int fromIndex;
0967: if (subMap.hasStart) {
0968: subMap.setFirstKey();
0969: from = subMap.firstKeyNode;
0970: fromIndex = subMap.firstKeyIndex;
0971: } else {
0972: from = minimum(subMap.backingMap.root);
0973: fromIndex = from != null ? from.left_idx : 0;
0974: }
0975: if (!subMap.hasEnd) {
0976: return new UnboundedValueIterator<K, V>(
0977: subMap.backingMap, from, from == null ? 0
0978: : from.right_idx - fromIndex);
0979: }
0980: subMap.setLastKey();
0981: Node<K, V> to = subMap.lastKeyNode;
0982: int toIndex = subMap.lastKeyIndex;
0983: return new BoundedValueIterator<K, V>(from,
0984: from == null ? 0 : from.right_idx - fromIndex,
0985: subMap.backingMap, to, to == null ? 0
0986: : to.right_idx - toIndex);
0987: }
0988:
0989: @Override
0990: public int size() {
0991: return subMap.size();
0992: }
0993: }
0994:
0995: /**
0996: * Constructs a new empty instance of spec.TreeMap.
0997: */
0998: public TreeMap() {
0999: }
1000:
1001: /**
1002: * Constructs a new empty instance of spec.TreeMap which uses the specified
1003: * Comparator.
1004: *
1005: * @param comparator the Comparator
1006: */
1007: public TreeMap(Comparator<? super K> comparator) {
1008: this .comparator = comparator;
1009: }
1010:
1011: /**
1012: * Constructs a new instance of spec.TreeMap containing the mappings from the
1013: * specified Map and using the natural ordering.
1014: *
1015: * @param map the mappings to add
1016: * @throws ClassCastException when a key in the Map does not implement the Comparable
1017: * interface, or they keys in the Map cannot be compared
1018: */
1019: public TreeMap(Map<? extends K, ? extends V> map) {
1020: putAll(map);
1021: }
1022:
1023: /**
1024: * Constructs a new instance of spec.TreeMap containing the mappings from the
1025: * specified SortedMap and using the same Comparator.
1026: *
1027: * @param map the mappings to add
1028: */
1029: public TreeMap(SortedMap<K, ? extends V> map) {
1030: this (map.comparator());
1031: Node<K, V> lastNode = null;
1032: Iterator<? extends Map.Entry<K, ? extends V>> it = map
1033: .entrySet().iterator();
1034: while (it.hasNext()) {
1035: Map.Entry<K, ? extends V> entry = it.next();
1036: lastNode = addToLast(lastNode, entry.getKey(), entry
1037: .getValue());
1038: }
1039: }
1040:
1041: Node<K, V> addToLast(Node<K, V> last, K key, V value) {
1042: if (last == null) {
1043: root = last = createNode(key, value);
1044: size = 1;
1045: } else if (last.size == Node.NODE_SIZE) {
1046: Node<K, V> newNode = createNode(key, value);
1047: attachToRight(last, newNode);
1048: balance(newNode);
1049: size++;
1050: last = newNode;
1051: } else {
1052: appendFromRight(last, key, value);
1053: size++;
1054: }
1055: return last;
1056: }
1057:
1058: /**
1059: * Removes all mappings from this spec.TreeMap, leaving it empty.
1060: *
1061: * @see Map#isEmpty
1062: * @see #size
1063: */
1064: @Override
1065: public void clear() {
1066: root = null;
1067: size = 0;
1068: modCount++;
1069: }
1070:
1071: /**
1072: * Answers a new spec.TreeMap with the same mappings, size and comparator as this
1073: * spec.TreeMap.
1074: *
1075: * @return a shallow copy of this spec.TreeMap
1076: * @see java.lang.Cloneable
1077: */
1078: @SuppressWarnings("unchecked")
1079: @Override
1080: public Object clone() {
1081: try {
1082: TreeMap<K, V> clone = (TreeMap<K, V>) super .clone();
1083: clone.entrySet = null;
1084: if (root != null) {
1085: clone.root = root.clone(null);
1086: // restore prev/next chain
1087: Node<K, V> node = minimum(clone.root);
1088: while (true) {
1089: Node<K, V> nxt = successor(node);
1090: if (nxt == null) {
1091: break;
1092: }
1093: nxt.prev = node;
1094: node.next = nxt;
1095: node = nxt;
1096: }
1097: }
1098: return clone;
1099: } catch (CloneNotSupportedException e) {
1100: return null;
1101: }
1102: }
1103:
1104: static private <K, V> Node<K, V> successor(Node<K, V> x) {
1105: if (x.right != null) {
1106: return minimum(x.right);
1107: }
1108: Node<K, V> y = x.parent;
1109: while (y != null && x == y.right) {
1110: x = y;
1111: y = y.parent;
1112: }
1113: return y;
1114: }
1115:
1116: /**
1117: * Answers the Comparator used to compare elements in this spec.TreeMap.
1118: *
1119: * @return a Comparator or null if the natural ordering is used
1120: */
1121: public Comparator<? super K> comparator() {
1122: return comparator;
1123: }
1124:
1125: /**
1126: * Searches this spec.TreeMap for the specified key.
1127: *
1128: * @param key the object to search for
1129: * @return true if <code>key</code> is a key of this spec.TreeMap, false
1130: * otherwise
1131: * @throws ClassCastException when the key cannot be compared with the keys in this
1132: * spec.TreeMap
1133: * @throws NullPointerException when the key is null and the comparator cannot handle null
1134: */
1135: @Override
1136: public boolean containsKey(Object key) {
1137: Comparable<K> object = comparator == null ? toComparable((K) key)
1138: : null;
1139: K keyK = (K) key;
1140: Node<K, V> node = root;
1141: while (node != null) {
1142: K[] keys = node.keys;
1143: int left_idx = node.left_idx;
1144: int result = cmp(object, keyK, keys[left_idx]);
1145: if (result < 0) {
1146: node = node.left;
1147: } else if (result == 0) {
1148: return true;
1149: } else {
1150: int right_idx = node.right_idx;
1151: if (left_idx != right_idx) {
1152: result = cmp(object, keyK, keys[right_idx]);
1153: }
1154: if (result > 0) {
1155: node = node.right;
1156: } else if (result == 0) {
1157: return true;
1158: } else { /*search in node*/
1159: int low = left_idx + 1, mid = 0, high = right_idx - 1;
1160: while (low <= high) {
1161: mid = (low + high) >> 1;
1162: result = cmp(object, keyK, keys[mid]);
1163: if (result > 0) {
1164: low = mid + 1;
1165: } else if (result == 0) {
1166: return true;
1167: } else {
1168: high = mid - 1;
1169: }
1170: }
1171: return false;
1172: }
1173: }
1174: }
1175: return false;
1176: }
1177:
1178: /**
1179: * Searches this spec.TreeMap for the specified value.
1180: *
1181: * @param value the object to search for
1182: * @return true if <code>value</code> is a value of this spec.TreeMap, false
1183: * otherwise
1184: */
1185: @Override
1186: public boolean containsValue(Object value) {
1187: if (root == null) {
1188: return false;
1189: }
1190: Node<K, V> node = minimum(root);
1191: if (value != null) {
1192: while (node != null) {
1193: int to = node.right_idx;
1194: V[] values = node.values;
1195: for (int i = node.left_idx; i <= to; i++) {
1196: if (value.equals(values[i])) {
1197: return true;
1198: }
1199: }
1200: node = node.next;
1201: }
1202: } else {
1203: while (node != null) {
1204: int to = node.right_idx;
1205: V[] values = node.values;
1206: for (int i = node.left_idx; i <= to; i++) {
1207: if (values[i] == null) {
1208: return true;
1209: }
1210: }
1211: node = node.next;
1212: }
1213: }
1214: return false;
1215: }
1216:
1217: /**
1218: * Answers a Set of the mappings contained in this spec.TreeMap. Each element in
1219: * the set is a Map.Entry. The set is backed by this spec.TreeMap so changes to
1220: * one are reflected by the other. The set does not support adding.
1221: *
1222: * @return a Set of the mappings
1223: */
1224: @Override
1225: public Set<Map.Entry<K, V>> entrySet() {
1226: if (entrySet == null) {
1227: entrySet = new AbstractSet<Map.Entry<K, V>>() {
1228: @Override
1229: public int size() {
1230: return size;
1231: }
1232:
1233: @Override
1234: public void clear() {
1235: TreeMap.this .clear();
1236: }
1237:
1238: @SuppressWarnings("unchecked")
1239: @Override
1240: public boolean contains(Object object) {
1241: if (object instanceof Map.Entry) {
1242: Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
1243: Object v1 = TreeMap.this .get(entry.getKey()), v2 = entry
1244: .getValue();
1245: return v1 == null ? v2 == null : v1.equals(v2);
1246: }
1247: return false;
1248: }
1249:
1250: @Override
1251: public boolean remove(Object object) {
1252: if (contains(object)) {
1253: Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
1254: K key = entry.getKey();
1255: TreeMap.this .remove(key);
1256: return true;
1257: }
1258: return false;
1259: }
1260:
1261: @Override
1262: public Iterator<Map.Entry<K, V>> iterator() {
1263: return new UnboundedEntryIterator<K, V>(
1264: TreeMap.this );
1265: }
1266: };
1267: }
1268: return entrySet;
1269: }
1270:
1271: /**
1272: * Answers the first sorted key in this spec.TreeMap.
1273: *
1274: * @return the first sorted key
1275: * @throws NoSuchElementException when this spec.TreeMap is empty
1276: */
1277: public K firstKey() {
1278: if (root != null) {
1279: Node<K, V> node = minimum(root);
1280: return node.keys[node.left_idx];
1281: }
1282: throw new NoSuchElementException();
1283: }
1284:
1285: /**
1286: * Answers the value of the mapping with the specified key.
1287: *
1288: * @param key the key
1289: * @return the value of the mapping with the specified key
1290: * @throws ClassCastException when the key cannot be compared with the keys in this
1291: * spec.TreeMap
1292: * @throws NullPointerException when the key is null and the comparator cannot handle null
1293: */
1294: @Override
1295: public V get(Object key) {
1296: Comparable<K> object = comparator == null ? toComparable((K) key)
1297: : null;
1298: K keyK = (K) key;
1299: Node<K, V> node = root;
1300: while (node != null) {
1301: K[] keys = node.keys;
1302: int left_idx = node.left_idx;
1303: int result = cmp(object, keyK, keys[left_idx]);
1304: if (result < 0) {
1305: node = node.left;
1306: } else if (result == 0) {
1307: return node.values[left_idx];
1308: } else {
1309: int right_idx = node.right_idx;
1310: if (left_idx != right_idx) {
1311: result = cmp(object, keyK, keys[right_idx]);
1312: }
1313: if (result > 0) {
1314: node = node.right;
1315: } else if (result == 0) {
1316: return node.values[right_idx];
1317: } else { /*search in node*/
1318: int low = left_idx + 1, mid = 0, high = right_idx - 1;
1319: while (low <= high) {
1320: mid = (low + high) >> 1;
1321: result = cmp(object, keyK, keys[mid]);
1322: if (result > 0) {
1323: low = mid + 1;
1324: } else if (result == 0) {
1325: return node.values[mid];
1326: } else {
1327: high = mid - 1;
1328: }
1329: }
1330: return null;
1331: }
1332: }
1333: }
1334: return null;
1335: }
1336:
1337: private int cmp(Comparable<K> object, K key1, K key2) {
1338: return object != null ? object.compareTo(key2) : comparator
1339: .compare(key1, key2);
1340: }
1341:
1342: /**
1343: * Answers a SortedMap of the specified portion of this spec.TreeMap which
1344: * contains keys less than the end key. The returned SortedMap is backed by
1345: * this spec.TreeMap so changes to one are reflected by the other.
1346: *
1347: * @param endKey the end key
1348: * @return a sub-map where the keys are less than <code>endKey</code>
1349: * @throws ClassCastException when the end key cannot be compared with the keys in this
1350: * spec.TreeMap
1351: * @throws NullPointerException when the end key is null and the comparator cannot handle
1352: * null
1353: */
1354: public SortedMap<K, V> headMap(K endKey) {
1355: // Check for errors
1356: if (comparator == null) {
1357: toComparable(endKey).compareTo(endKey);
1358: } else {
1359: comparator.compare(endKey, endKey);
1360: }
1361: return new SubMap<K, V>(this , endKey);
1362: }
1363:
1364: /**
1365: * Answers a Set of the keys contained in this spec.TreeMap. The set is backed by
1366: * this spec.TreeMap so changes to one are reflected by the other. The set does
1367: * not support adding.
1368: *
1369: * @return a Set of the keys
1370: */
1371: @Override
1372: public Set<K> keySet() {
1373: if (keySet == null) {
1374: keySet = new AbstractSet<K>() {
1375: @Override
1376: public boolean contains(Object object) {
1377: return TreeMap.this .containsKey(object);
1378: }
1379:
1380: @Override
1381: public int size() {
1382: return TreeMap.this .size;
1383: }
1384:
1385: @Override
1386: public void clear() {
1387: TreeMap.this .clear();
1388: }
1389:
1390: @Override
1391: public boolean remove(Object object) {
1392: if (contains(object)) {
1393: TreeMap.this .remove(object);
1394: return true;
1395: }
1396: return false;
1397: }
1398:
1399: @Override
1400: public Iterator<K> iterator() {
1401: return new UnboundedKeyIterator<K, V>(TreeMap.this );
1402: }
1403: };
1404: }
1405: return keySet;
1406: }
1407:
1408: /**
1409: * Answer the last sorted key in this spec.TreeMap.
1410: *
1411: * @return the last sorted key
1412: * @throws NoSuchElementException when this spec.TreeMap is empty
1413: */
1414: public K lastKey() {
1415: if (root != null) {
1416: Node<K, V> node = maximum(root);
1417: return node.keys[node.right_idx];
1418: }
1419: throw new NoSuchElementException();
1420: }
1421:
1422: static <K, V> Node<K, V> minimum(Node<K, V> x) {
1423: if (x == null) {
1424: return null;
1425: }
1426: while (x.left != null) {
1427: x = x.left;
1428: }
1429: return x;
1430: }
1431:
1432: static <K, V> Node<K, V> maximum(Node<K, V> x) {
1433: if (x == null) {
1434: return null;
1435: }
1436: while (x.right != null) {
1437: x = x.right;
1438: }
1439: return x;
1440: }
1441:
1442: /**
1443: * Maps the specified key to the specified value.
1444: *
1445: * @param key the key
1446: * @param value the value
1447: * @return the value of any previous mapping with the specified key or null
1448: * if there was no mapping
1449: * @throws ClassCastException when the key cannot be compared with the keys in this
1450: * spec.TreeMap
1451: * @throws NullPointerException when the key is null and the comparator cannot handle null
1452: */
1453: @Override
1454: public V put(K key, V value) {
1455: if (root == null) {
1456: root = createNode(key, value);
1457: size = 1;
1458: modCount++;
1459: return null;
1460: }
1461: Comparable<K> object = comparator == null ? toComparable((K) key)
1462: : null;
1463: K keyK = (K) key;
1464: Node<K, V> node = root;
1465: Node<K, V> prevNode = null;
1466: int result = 0;
1467: while (node != null) {
1468: prevNode = node;
1469: K[] keys = node.keys;
1470: int left_idx = node.left_idx;
1471: result = cmp(object, keyK, keys[left_idx]);
1472: if (result < 0) {
1473: node = node.left;
1474: } else if (result == 0) {
1475: V res = node.values[left_idx];
1476: node.values[left_idx] = value;
1477: return res;
1478: } else {
1479: int right_idx = node.right_idx;
1480: if (left_idx != right_idx) {
1481: result = cmp(object, keyK, keys[right_idx]);
1482: }
1483: if (result > 0) {
1484: node = node.right;
1485: } else if (result == 0) {
1486: V res = node.values[right_idx];
1487: node.values[right_idx] = value;
1488: return res;
1489: } else { /*search in node*/
1490: int low = left_idx + 1, mid = 0, high = right_idx - 1;
1491: while (low <= high) {
1492: mid = (low + high) >> 1;
1493: result = cmp(object, keyK, keys[mid]);
1494: if (result > 0) {
1495: low = mid + 1;
1496: } else if (result == 0) {
1497: V res = node.values[mid];
1498: node.values[mid] = value;
1499: return res;
1500: } else {
1501: high = mid - 1;
1502: }
1503: }
1504: result = low;
1505: break;
1506: }
1507: }
1508: } /* while */
1509: /*
1510: if(node == null) {
1511: if(prevNode==null) {
1512: - case of empty Tree
1513: } else {
1514: result < 0 - prevNode.left==null - attach here
1515: result > 0 - prevNode.right==null - attach here
1516: }
1517: } else {
1518: insert into node.
1519: result - index where it should be inserted.
1520: }
1521: */
1522: size++;
1523: modCount++;
1524: if (node == null) {
1525: if (prevNode == null) {
1526: // case of empty Tree
1527: root = createNode(key, value);
1528: } else if (prevNode.size < Node.NODE_SIZE) {
1529: // there is a place for insert
1530: if (result < 0) {
1531: appendFromLeft(prevNode, key, value);
1532: } else {
1533: appendFromRight(prevNode, key, value);
1534: }
1535: } else {
1536: // create and link
1537: Node<K, V> newNode = createNode(key, value);
1538: if (result < 0) {
1539: attachToLeft(prevNode, newNode);
1540: } else {
1541: attachToRight(prevNode, newNode);
1542: }
1543: balance(newNode);
1544: }
1545: } else {
1546: // insert into node.
1547: // result - index where it should be inserted.
1548: if (node.size < Node.NODE_SIZE) { // insert and ok
1549: int left_idx = node.left_idx;
1550: int right_idx = node.right_idx;
1551: if (left_idx == 0
1552: || ((right_idx != Node.NODE_SIZE - 1) && (right_idx
1553: - result <= result - left_idx))) {
1554: int right_idxPlus1 = right_idx + 1;
1555: System.arraycopy(node.keys, result, node.keys,
1556: result + 1, right_idxPlus1 - result);
1557: System.arraycopy(node.values, result, node.values,
1558: result + 1, right_idxPlus1 - result);
1559: node.right_idx = right_idxPlus1;
1560: node.keys[result] = key;
1561: node.values[result] = value;
1562: } else {
1563: int left_idxMinus1 = left_idx - 1;
1564: System.arraycopy(node.keys, left_idx, node.keys,
1565: left_idxMinus1, result - left_idx);
1566: System.arraycopy(node.values, left_idx,
1567: node.values, left_idxMinus1, result
1568: - left_idx);
1569: node.left_idx = left_idxMinus1;
1570: node.keys[result - 1] = key;
1571: node.values[result - 1] = value;
1572: }
1573: node.size++;
1574: } else {
1575: // there are no place here
1576: // insert and push old pair
1577: Node<K, V> previous = node.prev;
1578: Node<K, V> nextNode = node.next;
1579: boolean removeFromStart;
1580: boolean attachFromLeft = false;
1581: Node<K, V> attachHere = null;
1582: if (previous == null) {
1583: if (nextNode != null
1584: && nextNode.size < Node.NODE_SIZE) {
1585: // move last pair to next
1586: removeFromStart = false;
1587: } else {
1588: // next node doesn't exist or full
1589: // left==null
1590: // drop first pair to new node from left
1591: removeFromStart = true;
1592: attachFromLeft = true;
1593: attachHere = node;
1594: }
1595: } else if (nextNode == null) {
1596: if (previous.size < Node.NODE_SIZE) {
1597: // move first pair to prev
1598: removeFromStart = true;
1599: } else {
1600: // right == null;
1601: // drop last pair to new node from right
1602: removeFromStart = false;
1603: attachFromLeft = false;
1604: attachHere = node;
1605: }
1606: } else {
1607: if (previous.size < Node.NODE_SIZE) {
1608: if (nextNode.size < Node.NODE_SIZE) {
1609: // choose prev or next for moving
1610: removeFromStart = previous.size < nextNode.size;
1611: } else {
1612: // move first pair to prev
1613: removeFromStart = true;
1614: }
1615: } else {
1616: if (nextNode.size < Node.NODE_SIZE) {
1617: // move last pair to next
1618: removeFromStart = false;
1619: } else {
1620: // prev & next are full
1621: // if node.right!=null then node.next.left==null
1622: // if node.left!=null then node.prev.right==null
1623: if (node.right == null) {
1624: attachHere = node;
1625: attachFromLeft = false;
1626: removeFromStart = false;
1627: } else {
1628: attachHere = nextNode;
1629: attachFromLeft = true;
1630: removeFromStart = false;
1631: }
1632: }
1633: }
1634: }
1635: K movedKey;
1636: V movedValue;
1637: if (removeFromStart) {
1638: // node.left_idx == 0
1639: movedKey = node.keys[0];
1640: movedValue = node.values[0];
1641: int resMunus1 = result - 1;
1642: System.arraycopy(node.keys, 1, node.keys, 0,
1643: resMunus1);
1644: System.arraycopy(node.values, 1, node.values, 0,
1645: resMunus1);
1646: node.keys[resMunus1] = key;
1647: node.values[resMunus1] = value;
1648: } else {
1649: // node.right_idx == Node.NODE_SIZE - 1
1650: movedKey = node.keys[Node.NODE_SIZE - 1];
1651: movedValue = node.values[Node.NODE_SIZE - 1];
1652: System.arraycopy(node.keys, result, node.keys,
1653: result + 1, Node.NODE_SIZE - 1 - result);
1654: System.arraycopy(node.values, result, node.values,
1655: result + 1, Node.NODE_SIZE - 1 - result);
1656: node.keys[result] = key;
1657: node.values[result] = value;
1658: }
1659: if (attachHere == null) {
1660: if (removeFromStart) {
1661: appendFromRight(previous, movedKey, movedValue);
1662: } else {
1663: appendFromLeft(nextNode, movedKey, movedValue);
1664: }
1665: } else {
1666: Node<K, V> newNode = createNode(movedKey,
1667: movedValue);
1668: if (attachFromLeft) {
1669: attachToLeft(attachHere, newNode);
1670: } else {
1671: attachToRight(attachHere, newNode);
1672: }
1673: balance(newNode);
1674: }
1675: }
1676: }
1677: return null;
1678: }
1679:
1680: private void appendFromLeft(Node<K, V> node, K keyObj, V value) {
1681: if (node.left_idx == 0) {
1682: int new_right = node.right_idx + 1;
1683: System.arraycopy(node.keys, 0, node.keys, 1, new_right);
1684: System.arraycopy(node.values, 0, node.values, 1, new_right);
1685: node.right_idx = new_right;
1686: } else {
1687: node.left_idx--;
1688: }
1689: node.size++;
1690: node.keys[node.left_idx] = keyObj;
1691: node.values[node.left_idx] = value;
1692: }
1693:
1694: private void attachToLeft(Node<K, V> node, Node<K, V> newNode) {
1695: newNode.parent = node;
1696: // node.left==null - attach here
1697: node.left = newNode;
1698: Node<K, V> predecessor = node.prev;
1699: newNode.prev = predecessor;
1700: newNode.next = node;
1701: if (predecessor != null) {
1702: predecessor.next = newNode;
1703: }
1704: node.prev = newNode;
1705: }
1706:
1707: /* add pair into node; existence free room in the node should be checked
1708: * before call
1709: */
1710: private void appendFromRight(Node<K, V> node, K keyObj, V value) {
1711: if (node.right_idx == Node.NODE_SIZE - 1) {
1712: int left_idx = node.left_idx;
1713: int left_idxMinus1 = left_idx - 1;
1714: System.arraycopy(node.keys, left_idx, node.keys,
1715: left_idxMinus1, Node.NODE_SIZE - left_idx);
1716: System.arraycopy(node.values, left_idx, node.values,
1717: left_idxMinus1, Node.NODE_SIZE - left_idx);
1718: node.left_idx = left_idxMinus1;
1719: } else {
1720: node.right_idx++;
1721: }
1722: node.size++;
1723: node.keys[node.right_idx] = keyObj;
1724: node.values[node.right_idx] = value;
1725: }
1726:
1727: private void attachToRight(Node<K, V> node, Node<K, V> newNode) {
1728: newNode.parent = node;
1729: // - node.right==null - attach here
1730: node.right = newNode;
1731: newNode.prev = node;
1732: Node<K, V> successor = node.next;
1733: newNode.next = successor;
1734: if (successor != null) {
1735: successor.prev = newNode;
1736: }
1737: node.next = newNode;
1738: }
1739:
1740: private Node<K, V> createNode(K keyObj, V value) {
1741: Node<K, V> node = new Node<K, V>();
1742: node.keys[0] = keyObj;
1743: node.values[0] = value;
1744: node.left_idx = 0;
1745: node.right_idx = 0;
1746: node.size = 1;
1747: return node;
1748: }
1749:
1750: void balance(Node<K, V> x) {
1751: Node<K, V> y;
1752: x.color = true;
1753: while (x != root && x.parent.color) {
1754: if (x.parent == x.parent.parent.left) {
1755: y = x.parent.parent.right;
1756: if (y != null && y.color) {
1757: x.parent.color = false;
1758: y.color = false;
1759: x.parent.parent.color = true;
1760: x = x.parent.parent;
1761: } else {
1762: if (x == x.parent.right) {
1763: x = x.parent;
1764: leftRotate(x);
1765: }
1766: x.parent.color = false;
1767: x.parent.parent.color = true;
1768: rightRotate(x.parent.parent);
1769: }
1770: } else {
1771: y = x.parent.parent.left;
1772: if (y != null && y.color) {
1773: x.parent.color = false;
1774: y.color = false;
1775: x.parent.parent.color = true;
1776: x = x.parent.parent;
1777: } else {
1778: if (x == x.parent.left) {
1779: x = x.parent;
1780: rightRotate(x);
1781: }
1782: x.parent.color = false;
1783: x.parent.parent.color = true;
1784: leftRotate(x.parent.parent);
1785: }
1786: }
1787: }
1788: root.color = false;
1789: }
1790:
1791: private void rightRotate(Node<K, V> x) {
1792: Node<K, V> y = x.left;
1793: x.left = y.right;
1794: if (y.right != null) {
1795: y.right.parent = x;
1796: }
1797: y.parent = x.parent;
1798: if (x.parent == null) {
1799: root = y;
1800: } else {
1801: if (x == x.parent.right) {
1802: x.parent.right = y;
1803: } else {
1804: x.parent.left = y;
1805: }
1806: }
1807: y.right = x;
1808: x.parent = y;
1809: }
1810:
1811: private void leftRotate(Node<K, V> x) {
1812: Node<K, V> y = x.right;
1813: x.right = y.left;
1814: if (y.left != null) {
1815: y.left.parent = x;
1816: }
1817: y.parent = x.parent;
1818: if (x.parent == null) {
1819: root = y;
1820: } else {
1821: if (x == x.parent.left) {
1822: x.parent.left = y;
1823: } else {
1824: x.parent.right = y;
1825: }
1826: }
1827: y.left = x;
1828: x.parent = y;
1829: }
1830:
1831: /**
1832: * Copies every mapping in the specified Map to this spec.TreeMap.
1833: *
1834: * @param map the Map to copy mappings from
1835: * @throws ClassCastException when a key in the Map cannot be compared with the keys in
1836: * this spec.TreeMap
1837: * @throws NullPointerException when a key in the Map is null and the comparator cannot
1838: * handle null
1839: */
1840: @Override
1841: public void putAll(Map<? extends K, ? extends V> map) {
1842: super .putAll(map);
1843: }
1844:
1845: /**
1846: * Removes a mapping with the specified key from this spec.TreeMap.
1847: *
1848: * @param key the key of the mapping to remove
1849: * @return the value of the removed mapping or null if key is not a key in
1850: * this spec.TreeMap
1851: * @throws ClassCastException when the key cannot be compared with the keys in this
1852: * spec.TreeMap
1853: * @throws NullPointerException when the key is null and the comparator cannot handle null
1854: */
1855: @Override
1856: public V remove(Object key) {
1857: if (size == 0) {
1858: return null;
1859: }
1860: Comparable<K> object = comparator == null ? toComparable((K) key)
1861: : null;
1862: K keyK = (K) key;
1863: Node<K, V> node = root;
1864: while (node != null) {
1865: K[] keys = node.keys;
1866: int left_idx = node.left_idx;
1867: int result = cmp(object, keyK, keys[left_idx]);
1868: if (result < 0) {
1869: node = node.left;
1870: } else if (result == 0) {
1871: V value = node.values[left_idx];
1872: removeLeftmost(node);
1873: return value;
1874: } else {
1875: int right_idx = node.right_idx;
1876: if (left_idx != right_idx) {
1877: result = cmp(object, keyK, keys[right_idx]);
1878: }
1879: if (result > 0) {
1880: node = node.right;
1881: } else if (result == 0) {
1882: V value = node.values[right_idx];
1883: removeRightmost(node);
1884: return value;
1885: } else { /*search in node*/
1886: int low = left_idx + 1, mid = 0, high = right_idx - 1;
1887: while (low <= high) {
1888: mid = (low + high) >> 1;
1889: result = cmp(object, keyK, keys[mid]);
1890: if (result > 0) {
1891: low = mid + 1;
1892: } else if (result == 0) {
1893: V value = node.values[mid];
1894: removeMiddleElement(node, mid);
1895: return value;
1896: } else {
1897: high = mid - 1;
1898: }
1899: }
1900: return null;
1901: }
1902: }
1903: }
1904: return null;
1905: }
1906:
1907: void removeLeftmost(Node<K, V> node) {
1908: int index = node.left_idx;
1909: if (node.size == 1) {
1910: deleteNode(node);
1911: } else if (node.prev != null
1912: && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
1913: // move all to prev node and kill it
1914: Node<K, V> prev = node.prev;
1915: int size = node.right_idx - index;
1916: System.arraycopy(node.keys, index + 1, prev.keys,
1917: prev.right_idx + 1, size);
1918: System.arraycopy(node.values, index + 1, prev.values,
1919: prev.right_idx + 1, size);
1920: prev.right_idx += size;
1921: prev.size += size;
1922: deleteNode(node);
1923: } else if (node.next != null
1924: && (node.next.left_idx) > node.size) {
1925: // move all to next node and kill it
1926: Node<K, V> next = node.next;
1927: int size = node.right_idx - index;
1928: int next_new_left = next.left_idx - size;
1929: next.left_idx = next_new_left;
1930: System.arraycopy(node.keys, index + 1, next.keys,
1931: next_new_left, size);
1932: System.arraycopy(node.values, index + 1, next.values,
1933: next_new_left, size);
1934: next.size += size;
1935: deleteNode(node);
1936: } else {
1937: node.keys[index] = null;
1938: node.values[index] = null;
1939: node.left_idx++;
1940: node.size--;
1941: Node<K, V> prev = node.prev;
1942: if (prev != null && prev.size == 1) {
1943: node.size++;
1944: node.left_idx--;
1945: node.keys[node.left_idx] = prev.keys[prev.left_idx];
1946: node.values[node.left_idx] = prev.values[prev.left_idx];
1947: deleteNode(prev);
1948: }
1949: }
1950: modCount++;
1951: size--;
1952: }
1953:
1954: void removeRightmost(Node<K, V> node) {
1955: int index = node.right_idx;
1956: if (node.size == 1) {
1957: deleteNode(node);
1958: } else if (node.prev != null
1959: && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
1960: // move all to prev node and kill it
1961: Node<K, V> prev = node.prev;
1962: int left_idx = node.left_idx;
1963: int size = index - left_idx;
1964: System.arraycopy(node.keys, left_idx, prev.keys,
1965: prev.right_idx + 1, size);
1966: System.arraycopy(node.values, left_idx, prev.values,
1967: prev.right_idx + 1, size);
1968: prev.right_idx += size;
1969: prev.size += size;
1970: deleteNode(node);
1971: } else if (node.next != null
1972: && (node.next.left_idx) > node.size) {
1973: // move all to next node and kill it
1974: Node<K, V> next = node.next;
1975: int left_idx = node.left_idx;
1976: int size = index - left_idx;
1977: int next_new_left = next.left_idx - size;
1978: next.left_idx = next_new_left;
1979: System.arraycopy(node.keys, left_idx, next.keys,
1980: next_new_left, size);
1981: System.arraycopy(node.values, left_idx, next.values,
1982: next_new_left, size);
1983: next.size += size;
1984: deleteNode(node);
1985: } else {
1986: node.keys[index] = null;
1987: node.values[index] = null;
1988: node.right_idx--;
1989: node.size--;
1990: Node<K, V> next = node.next;
1991: if (next != null && next.size == 1) {
1992: node.size++;
1993: node.right_idx++;
1994: node.keys[node.right_idx] = next.keys[next.left_idx];
1995: node.values[node.right_idx] = next.values[next.left_idx];
1996: deleteNode(next);
1997: }
1998: }
1999: modCount++;
2000: size--;
2001: }
2002:
2003: void removeMiddleElement(Node<K, V> node, int index) {
2004: // this function is called iff index if some middle element;
2005: // so node.left_idx < index < node.right_idx
2006: // condition above assume that node.size > 1
2007: if (node.prev != null
2008: && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
2009: // move all to prev node and kill it
2010: Node<K, V> prev = node.prev;
2011: int left_idx = node.left_idx;
2012: int size = index - left_idx;
2013: System.arraycopy(node.keys, left_idx, prev.keys,
2014: prev.right_idx + 1, size);
2015: System.arraycopy(node.values, left_idx, prev.values,
2016: prev.right_idx + 1, size);
2017: prev.right_idx += size;
2018: size = node.right_idx - index;
2019: System.arraycopy(node.keys, index + 1, prev.keys,
2020: prev.right_idx + 1, size);
2021: System.arraycopy(node.values, index + 1, prev.values,
2022: prev.right_idx + 1, size);
2023: prev.right_idx += size;
2024: prev.size += (node.size - 1);
2025: deleteNode(node);
2026: } else if (node.next != null
2027: && (node.next.left_idx) > node.size) {
2028: // move all to next node and kill it
2029: Node<K, V> next = node.next;
2030: int left_idx = node.left_idx;
2031: int next_new_left = next.left_idx - node.size + 1;
2032: next.left_idx = next_new_left;
2033: int size = index - left_idx;
2034: System.arraycopy(node.keys, left_idx, next.keys,
2035: next_new_left, size);
2036: System.arraycopy(node.values, left_idx, next.values,
2037: next_new_left, size);
2038: next_new_left += size;
2039: size = node.right_idx - index;
2040: System.arraycopy(node.keys, index + 1, next.keys,
2041: next_new_left, size);
2042: System.arraycopy(node.values, index + 1, next.values,
2043: next_new_left, size);
2044: next.size += (node.size - 1);
2045: deleteNode(node);
2046: } else {
2047: int moveFromRight = node.right_idx - index;
2048: int left_idx = node.left_idx;
2049: int moveFromLeft = index - left_idx;
2050: if (moveFromRight <= moveFromLeft) {
2051: System.arraycopy(node.keys, index + 1, node.keys,
2052: index, moveFromRight);
2053: System.arraycopy(node.values, index + 1, node.values,
2054: index, moveFromRight);
2055: Node<K, V> next = node.next;
2056: if (next != null && next.size == 1) {
2057: node.keys[node.right_idx] = next.keys[next.left_idx];
2058: node.values[node.right_idx] = next.values[next.left_idx];
2059: deleteNode(next);
2060: } else {
2061: node.keys[node.right_idx] = null;
2062: node.values[node.right_idx] = null;
2063: node.right_idx--;
2064: node.size--;
2065: }
2066: } else {
2067: System.arraycopy(node.keys, left_idx, node.keys,
2068: left_idx + 1, moveFromLeft);
2069: System.arraycopy(node.values, left_idx, node.values,
2070: left_idx + 1, moveFromLeft);
2071: Node<K, V> prev = node.prev;
2072: if (prev != null && prev.size == 1) {
2073: node.keys[left_idx] = prev.keys[prev.left_idx];
2074: node.values[left_idx] = prev.values[prev.left_idx];
2075: deleteNode(prev);
2076: } else {
2077: node.keys[left_idx] = null;
2078: node.values[left_idx] = null;
2079: node.left_idx++;
2080: node.size--;
2081: }
2082: }
2083: }
2084: modCount++;
2085: size--;
2086: }
2087:
2088: void removeFromIterator(Node<K, V> node, int index) {
2089: if (node.size == 1) {
2090: // it is safe to delete the whole node here.
2091: // iterator already moved to the next node;
2092: deleteNode(node);
2093: } else {
2094: int left_idx = node.left_idx;
2095: if (index == left_idx) {
2096: Node<K, V> prev = node.prev;
2097: if (prev != null && prev.size == 1) {
2098: node.keys[left_idx] = prev.keys[prev.left_idx];
2099: node.values[left_idx] = prev.values[prev.left_idx];
2100: deleteNode(prev);
2101: } else {
2102: node.keys[left_idx] = null;
2103: node.values[left_idx] = null;
2104: node.left_idx++;
2105: node.size--;
2106: }
2107: } else if (index == node.right_idx) {
2108: node.keys[index] = null;
2109: node.values[index] = null;
2110: node.right_idx--;
2111: node.size--;
2112: } else {
2113: int moveFromRight = node.right_idx - index;
2114: int moveFromLeft = index - left_idx;
2115: if (moveFromRight <= moveFromLeft) {
2116: System.arraycopy(node.keys, index + 1, node.keys,
2117: index, moveFromRight);
2118: System.arraycopy(node.values, index + 1,
2119: node.values, index, moveFromRight);
2120: node.keys[node.right_idx] = null;
2121: node.values[node.right_idx] = null;
2122: node.right_idx--;
2123: node.size--;
2124: } else {
2125: System.arraycopy(node.keys, left_idx, node.keys,
2126: left_idx + 1, moveFromLeft);
2127: System.arraycopy(node.values, left_idx,
2128: node.values, left_idx + 1, moveFromLeft);
2129: node.keys[left_idx] = null;
2130: node.values[left_idx] = null;
2131: node.left_idx++;
2132: node.size--;
2133: }
2134: }
2135: }
2136: modCount++;
2137: size--;
2138: }
2139:
2140: private void deleteNode(Node<K, V> node) {
2141: if (node.right == null) {
2142: if (node.left != null) {
2143: attachToParent(node, node.left);
2144: } else {
2145: attachNullToParent(node);
2146: }
2147: fixNextChain(node);
2148: } else if (node.left == null) { // node.right != null
2149: attachToParent(node, node.right);
2150: fixNextChain(node);
2151: } else {
2152: // Here node.left!=nul && node.right!=null
2153: // node.next should replace node in tree
2154: // node.next!=null by tree logic.
2155: // node.next.left==null by tree logic.
2156: // node.next.right may be null or non-null
2157: Node<K, V> toMoveUp = node.next;
2158: fixNextChain(node);
2159: if (toMoveUp.right == null) {
2160: attachNullToParent(toMoveUp);
2161: } else {
2162: attachToParent(toMoveUp, toMoveUp.right);
2163: }
2164: // Here toMoveUp is ready to replace node
2165: toMoveUp.left = node.left;
2166: if (node.left != null) {
2167: node.left.parent = toMoveUp;
2168: }
2169: toMoveUp.right = node.right;
2170: if (node.right != null) {
2171: node.right.parent = toMoveUp;
2172: }
2173: attachToParentNoFixup(node, toMoveUp);
2174: toMoveUp.color = node.color;
2175: }
2176: }
2177:
2178: private void attachToParentNoFixup(Node<K, V> toDelete,
2179: Node<K, V> toConnect) {
2180: // assert toConnect!=null
2181: Node<K, V> parent = toDelete.parent;
2182: toConnect.parent = parent;
2183: if (parent == null) {
2184: root = toConnect;
2185: } else if (toDelete == parent.left) {
2186: parent.left = toConnect;
2187: } else {
2188: parent.right = toConnect;
2189: }
2190: }
2191:
2192: private void attachToParent(Node<K, V> toDelete,
2193: Node<K, V> toConnect) {
2194: // assert toConnect!=null
2195: attachToParentNoFixup(toDelete, toConnect);
2196: if (!toDelete.color) {
2197: fixup(toConnect);
2198: }
2199: }
2200:
2201: private void attachNullToParent(Node<K, V> toDelete) {
2202: Node<K, V> parent = toDelete.parent;
2203: if (parent == null) {
2204: root = null;
2205: } else {
2206: if (toDelete == parent.left) {
2207: parent.left = null;
2208: } else {
2209: parent.right = null;
2210: }
2211: if (!toDelete.color) {
2212: fixup(parent);
2213: }
2214: }
2215: }
2216:
2217: private void fixNextChain(Node<K, V> node) {
2218: if (node.prev != null) {
2219: node.prev.next = node.next;
2220: }
2221: if (node.next != null) {
2222: node.next.prev = node.prev;
2223: }
2224: }
2225:
2226: private void fixup(Node<K, V> x) {
2227: Node<K, V> w;
2228: while (x != root && !x.color) {
2229: if (x == x.parent.left) {
2230: w = x.parent.right;
2231: if (w == null) {
2232: x = x.parent;
2233: continue;
2234: }
2235: if (w.color) {
2236: w.color = false;
2237: x.parent.color = true;
2238: leftRotate(x.parent);
2239: w = x.parent.right;
2240: if (w == null) {
2241: x = x.parent;
2242: continue;
2243: }
2244: }
2245: if ((w.left == null || !w.left.color)
2246: && (w.right == null || !w.right.color)) {
2247: w.color = true;
2248: x = x.parent;
2249: } else {
2250: if (w.right == null || !w.right.color) {
2251: w.left.color = false;
2252: w.color = true;
2253: rightRotate(w);
2254: w = x.parent.right;
2255: }
2256: w.color = x.parent.color;
2257: x.parent.color = false;
2258: w.right.color = false;
2259: leftRotate(x.parent);
2260: x = root;
2261: }
2262: } else {
2263: w = x.parent.left;
2264: if (w == null) {
2265: x = x.parent;
2266: continue;
2267: }
2268: if (w.color) {
2269: w.color = false;
2270: x.parent.color = true;
2271: rightRotate(x.parent);
2272: w = x.parent.left;
2273: if (w == null) {
2274: x = x.parent;
2275: continue;
2276: }
2277: }
2278: if ((w.left == null || !w.left.color)
2279: && (w.right == null || !w.right.color)) {
2280: w.color = true;
2281: x = x.parent;
2282: } else {
2283: if (w.left == null || !w.left.color) {
2284: w.right.color = false;
2285: w.color = true;
2286: leftRotate(w);
2287: w = x.parent.left;
2288: }
2289: w.color = x.parent.color;
2290: x.parent.color = false;
2291: w.left.color = false;
2292: rightRotate(x.parent);
2293: x = root;
2294: }
2295: }
2296: }
2297: x.color = false;
2298: }
2299:
2300: /**
2301: * Answers the number of mappings in this spec.TreeMap.
2302: *
2303: * @return the number of mappings in this spec.TreeMap
2304: */
2305: @Override
2306: public int size() {
2307: return size;
2308: }
2309:
2310: /**
2311: * Answers a SortedMap of the specified portion of this spec.TreeMap which
2312: * contains keys greater or equal to the start key but less than the end
2313: * key. The returned SortedMap is backed by this spec.TreeMap so changes to one
2314: * are reflected by the other.
2315: *
2316: * @param startKey the start key
2317: * @param endKey the end key
2318: * @return a sub-map where the keys are greater or equal to
2319: * <code>startKey</code> and less than <code>endKey</code>
2320: * @throws ClassCastException when the start or end key cannot be compared with the keys
2321: * in this spec.TreeMap
2322: * @throws NullPointerException when the start or end key is null and the comparator
2323: * cannot handle null
2324: */
2325: public SortedMap<K, V> subMap(K startKey, K endKey) {
2326: if (comparator == null) {
2327: if (toComparable(startKey).compareTo(endKey) <= 0) {
2328: return new SubMap<K, V>(startKey, this , endKey);
2329: }
2330: } else {
2331: if (comparator.compare(startKey, endKey) <= 0) {
2332: return new SubMap<K, V>(startKey, this , endKey);
2333: }
2334: }
2335: throw new IllegalArgumentException();
2336: }
2337:
2338: /**
2339: * Answers a SortedMap of the specified portion of this spec.TreeMap which
2340: * contains keys greater or equal to the start key. The returned SortedMap
2341: * is backed by this spec.TreeMap so changes to one are reflected by the other.
2342: *
2343: * @param startKey the start key
2344: * @return a sub-map where the keys are greater or equal to
2345: * <code>startKey</code>
2346: * @throws ClassCastException when the start key cannot be compared with the keys in
2347: * this spec.TreeMap
2348: * @throws NullPointerException when the start key is null and the comparator cannot
2349: * handle null
2350: */
2351: public SortedMap<K, V> tailMap(K startKey) {
2352: // Check for errors
2353: if (comparator == null) {
2354: toComparable(startKey).compareTo(startKey);
2355: } else {
2356: comparator.compare(startKey, startKey);
2357: }
2358: return new SubMap<K, V>(startKey, this );
2359: }
2360:
2361: /**
2362: * Answers a Collection of the values contained in this spec.TreeMap. The
2363: * collection is backed by this spec.TreeMap so changes to one are reflected by
2364: * the other. The collection does not support adding.
2365: *
2366: * @return a Collection of the values
2367: */
2368: @Override
2369: public Collection<V> values() {
2370: if (valuesCollection == null) {
2371: valuesCollection = new AbstractCollection<V>() {
2372: @Override
2373: public boolean contains(Object object) {
2374: return containsValue(object);
2375: }
2376:
2377: @Override
2378: public int size() {
2379: return size;
2380: }
2381:
2382: @Override
2383: public void clear() {
2384: TreeMap.this .clear();
2385: }
2386:
2387: @Override
2388: public Iterator<V> iterator() {
2389: return new UnboundedValueIterator<K, V>(
2390: TreeMap.this );
2391: }
2392: };
2393: }
2394: return valuesCollection;
2395: }
2396:
2397: private void writeObject(ObjectOutputStream stream)
2398: throws IOException {
2399: stream.defaultWriteObject();
2400: stream.writeInt(size);
2401: if (size > 0) {
2402: Node<K, V> node = minimum(root);
2403: while (node != null) {
2404: int to = node.right_idx;
2405: for (int i = node.left_idx; i <= to; i++) {
2406: stream.writeObject(node.keys[i]);
2407: stream.writeObject(node.values[i]);
2408: }
2409: node = node.next;
2410: }
2411: }
2412: }
2413:
2414: @SuppressWarnings("unchecked")
2415: private void readObject(ObjectInputStream stream)
2416: throws IOException, ClassNotFoundException {
2417: stream.defaultReadObject();
2418: int size = stream.readInt();
2419: Node<K, V> lastNode = null;
2420: for (int i = 0; i < size; i++) {
2421: lastNode = addToLast(lastNode, (K) stream.readObject(),
2422: (V) stream.readObject());
2423: }
2424: }
2425: }
|