1. /*
  2. * Copyright 2002-2004 The Apache Software Foundation
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. package org.apache.commons.collections;
  17. import java.util.AbstractCollection;
  18. import java.util.AbstractMap;
  19. import java.util.AbstractSet;
  20. import java.util.Collection;
  21. import java.util.ConcurrentModificationException;
  22. import java.util.Iterator;
  23. import java.util.Map;
  24. import java.util.NoSuchElementException;
  25. import java.util.Set;
  26. /**
  27. * Red-Black tree-based implementation of Map. This class guarantees
  28. * that the map will be in both ascending key order and ascending
  29. * value order, sorted according to the natural order for the key's
  30. * and value's classes.
  31. * <p>
  32. * This Map is intended for applications that need to be able to look
  33. * up a key-value pairing by either key or value, and need to do so
  34. * with equal efficiency.
  35. * <p>
  36. * While that goal could be accomplished by taking a pair of TreeMaps
  37. * and redirecting requests to the appropriate TreeMap (e.g.,
  38. * containsKey would be directed to the TreeMap that maps values to
  39. * keys, containsValue would be directed to the TreeMap that maps keys
  40. * to values), there are problems with that implementation,
  41. * particularly when trying to keep the two TreeMaps synchronized with
  42. * each other. And if the data contained in the TreeMaps is large, the
  43. * cost of redundant storage becomes significant. (See also the new
  44. * {@link org.apache.commons.collections.bidimap.DualTreeBidiMap DualTreeBidiMap} and
  45. * {@link org.apache.commons.collections.bidimap.DualHashBidiMap DualHashBidiMap}
  46. * implementations.)
  47. * <p>
  48. * This solution keeps the data properly synchronized and minimizes
  49. * the data storage. The red-black algorithm is based on TreeMap's,
  50. * but has been modified to simultaneously map a tree node by key and
  51. * by value. This doubles the cost of put operations (but so does
  52. * using two TreeMaps), and nearly doubles the cost of remove
  53. * operations (there is a savings in that the lookup of the node to be
  54. * removed only has to be performed once). And since only one node
  55. * contains the key and value, storage is significantly less than that
  56. * required by two TreeMaps.
  57. * <p>
  58. * There are some limitations placed on data kept in this Map. The
  59. * biggest one is this:
  60. * <p>
  61. * When performing a put operation, neither the key nor the value may
  62. * already exist in the Map. In the java.util Map implementations
  63. * (HashMap, TreeMap), you can perform a put with an already mapped
  64. * key, and neither cares about duplicate values at all ... but this
  65. * implementation's put method with throw an IllegalArgumentException
  66. * if either the key or the value is already in the Map.
  67. * <p>
  68. * Obviously, that same restriction (and consequence of failing to
  69. * heed that restriction) applies to the putAll method.
  70. * <p>
  71. * The Map.Entry instances returned by the appropriate methods will
  72. * not allow setValue() and will throw an
  73. * UnsupportedOperationException on attempts to call that method.
  74. * <p>
  75. * New methods are added to take advantage of the fact that values are
  76. * kept sorted independently of their keys:
  77. * <p>
  78. * Object getKeyForValue(Object value) is the opposite of get; it
  79. * takes a value and returns its key, if any.
  80. * <p>
  81. * Object removeValue(Object value) finds and removes the specified
  82. * value and returns the now un-used key.
  83. * <p>
  84. * Set entrySetByValue() returns the Map.Entry's in a Set whose
  85. * iterator will iterate over the Map.Entry's in ascending order by
  86. * their corresponding values.
  87. * <p>
  88. * Set keySetByValue() returns the keys in a Set whose iterator will
  89. * iterate over the keys in ascending order by their corresponding
  90. * values.
  91. * <p>
  92. * Collection valuesByValue() returns the values in a Collection whose
  93. * iterator will iterate over the values in ascending order.
  94. *
  95. * @deprecated Replaced by TreeBidiMap in bidimap subpackage. Due to be removed in v4.0.
  96. * @see BidiMap
  97. * @see org.apache.commons.collections.bidimap.DualTreeBidiMap
  98. * @see org.apache.commons.collections.bidimap.DualHashBidiMap
  99. * @since Commons Collections 2.0
  100. * @version $Revision: 1.14 $ $Date: 2004/02/18 01:15:42 $
  101. *
  102. * @author Marc Johnson
  103. */
  104. public final class DoubleOrderedMap extends AbstractMap {
  105. // final for performance
  106. private static final int KEY = 0;
  107. private static final int VALUE = 1;
  108. private static final int SUM_OF_INDICES = KEY + VALUE;
  109. private static final int FIRST_INDEX = 0;
  110. private static final int NUMBER_OF_INDICES = 2;
  111. private static final String[] dataName = new String[] { "key", "value" };
  112. private Node[] rootNode = new Node[] { null, null };
  113. private int nodeCount = 0;
  114. private int modifications = 0;
  115. private Set[] setOfKeys = new Set[] { null, null };
  116. private Set[] setOfEntries = new Set[] { null, null };
  117. private Collection[] collectionOfValues = new Collection[] { null, null };
  118. /**
  119. * Construct a new DoubleOrderedMap
  120. */
  121. public DoubleOrderedMap() {
  122. }
  123. /**
  124. * Constructs a new DoubleOrderedMap from an existing Map, with keys and
  125. * values sorted
  126. *
  127. * @param map the map whose mappings are to be placed in this map.
  128. *
  129. * @throws ClassCastException if the keys in the map are not
  130. * Comparable, or are not mutually
  131. * comparable; also if the values in
  132. * the map are not Comparable, or
  133. * are not mutually Comparable
  134. * @throws NullPointerException if any key or value in the map
  135. * is null
  136. * @throws IllegalArgumentException if there are duplicate keys
  137. * or duplicate values in the
  138. * map
  139. */
  140. public DoubleOrderedMap(final Map map)
  141. throws ClassCastException, NullPointerException,
  142. IllegalArgumentException {
  143. putAll(map);
  144. }
  145. /**
  146. * Returns the key to which this map maps the specified value.
  147. * Returns null if the map contains no mapping for this value.
  148. *
  149. * @param value value whose associated key is to be returned.
  150. *
  151. * @return the key to which this map maps the specified value, or
  152. * null if the map contains no mapping for this value.
  153. *
  154. * @throws ClassCastException if the value is of an
  155. * inappropriate type for this map.
  156. * @throws NullPointerException if the value is null
  157. */
  158. public Object getKeyForValue(final Object value)
  159. throws ClassCastException, NullPointerException {
  160. return doGet((Comparable) value, VALUE);
  161. }
  162. /**
  163. * Removes the mapping for this value from this map if present
  164. *
  165. * @param value value whose mapping is to be removed from the map.
  166. *
  167. * @return previous key associated with specified value, or null
  168. * if there was no mapping for value.
  169. */
  170. public Object removeValue(final Object value) {
  171. return doRemove((Comparable) value, VALUE);
  172. }
  173. /**
  174. * Returns a set view of the mappings contained in this map. Each
  175. * element in the returned set is a Map.Entry. The set is backed
  176. * by the map, so changes to the map are reflected in the set, and
  177. * vice-versa. If the map is modified while an iteration over the
  178. * set is in progress, the results of the iteration are
  179. * undefined. The set supports element removal, which removes the
  180. * corresponding mapping from the map, via the Iterator.remove,
  181. * Set.remove, removeAll, retainAll and clear operations. It does
  182. * not support the add or addAll operations.<p>
  183. *
  184. * The difference between this method and entrySet is that
  185. * entrySet's iterator() method returns an iterator that iterates
  186. * over the mappings in ascending order by key. This method's
  187. * iterator method iterates over the mappings in ascending order
  188. * by value.
  189. *
  190. * @return a set view of the mappings contained in this map.
  191. */
  192. public Set entrySetByValue() {
  193. if (setOfEntries[VALUE] == null) {
  194. setOfEntries[VALUE] = new AbstractSet() {
  195. public Iterator iterator() {
  196. return new DoubleOrderedMapIterator(VALUE) {
  197. protected Object doGetNext() {
  198. return lastReturnedNode;
  199. }
  200. };
  201. }
  202. public boolean contains(Object o) {
  203. if (!(o instanceof Map.Entry)) {
  204. return false;
  205. }
  206. Map.Entry entry = (Map.Entry) o;
  207. Object key = entry.getKey();
  208. Node node = lookup((Comparable) entry.getValue(),
  209. VALUE);
  210. return (node != null) && node.getData(KEY).equals(key);
  211. }
  212. public boolean remove(Object o) {
  213. if (!(o instanceof Map.Entry)) {
  214. return false;
  215. }
  216. Map.Entry entry = (Map.Entry) o;
  217. Object key = entry.getKey();
  218. Node node = lookup((Comparable) entry.getValue(),
  219. VALUE);
  220. if ((node != null) && node.getData(KEY).equals(key)) {
  221. doRedBlackDelete(node);
  222. return true;
  223. }
  224. return false;
  225. }
  226. public int size() {
  227. return DoubleOrderedMap.this.size();
  228. }
  229. public void clear() {
  230. DoubleOrderedMap.this.clear();
  231. }
  232. };
  233. }
  234. return setOfEntries[VALUE];
  235. }
  236. /**
  237. * Returns a set view of the keys contained in this map. The set
  238. * is backed by the map, so changes to the map are reflected in
  239. * the set, and vice-versa. If the map is modified while an
  240. * iteration over the set is in progress, the results of the
  241. * iteration are undefined. The set supports element removal,
  242. * which removes the corresponding mapping from the map, via the
  243. * Iterator.remove, Set.remove, removeAll, retainAll, and clear
  244. * operations. It does not support the add or addAll
  245. * operations.<p>
  246. *
  247. * The difference between this method and keySet is that keySet's
  248. * iterator() method returns an iterator that iterates over the
  249. * keys in ascending order by key. This method's iterator method
  250. * iterates over the keys in ascending order by value.
  251. *
  252. * @return a set view of the keys contained in this map.
  253. */
  254. public Set keySetByValue() {
  255. if (setOfKeys[VALUE] == null) {
  256. setOfKeys[VALUE] = new AbstractSet() {
  257. public Iterator iterator() {
  258. return new DoubleOrderedMapIterator(VALUE) {
  259. protected Object doGetNext() {
  260. return lastReturnedNode.getData(KEY);
  261. }
  262. };
  263. }
  264. public int size() {
  265. return DoubleOrderedMap.this.size();
  266. }
  267. public boolean contains(Object o) {
  268. return containsKey(o);
  269. }
  270. public boolean remove(Object o) {
  271. int oldnodeCount = nodeCount;
  272. DoubleOrderedMap.this.remove(o);
  273. return nodeCount != oldnodeCount;
  274. }
  275. public void clear() {
  276. DoubleOrderedMap.this.clear();
  277. }
  278. };
  279. }
  280. return setOfKeys[VALUE];
  281. }
  282. /**
  283. * Returns a collection view of the values contained in this
  284. * map. The collection is backed by the map, so changes to the map
  285. * are reflected in the collection, and vice-versa. If the map is
  286. * modified while an iteration over the collection is in progress,
  287. * the results of the iteration are undefined. The collection
  288. * supports element removal, which removes the corresponding
  289. * mapping from the map, via the Iterator.remove,
  290. * Collection.remove, removeAll, retainAll and clear operations.
  291. * It does not support the add or addAll operations.<p>
  292. *
  293. * The difference between this method and values is that values's
  294. * iterator() method returns an iterator that iterates over the
  295. * values in ascending order by key. This method's iterator method
  296. * iterates over the values in ascending order by key.
  297. *
  298. * @return a collection view of the values contained in this map.
  299. */
  300. public Collection valuesByValue() {
  301. if (collectionOfValues[VALUE] == null) {
  302. collectionOfValues[VALUE] = new AbstractCollection() {
  303. public Iterator iterator() {
  304. return new DoubleOrderedMapIterator(VALUE) {
  305. protected Object doGetNext() {
  306. return lastReturnedNode.getData(VALUE);
  307. }
  308. };
  309. }
  310. public int size() {
  311. return DoubleOrderedMap.this.size();
  312. }
  313. public boolean contains(Object o) {
  314. return containsValue(o);
  315. }
  316. public boolean remove(Object o) {
  317. int oldnodeCount = nodeCount;
  318. removeValue(o);
  319. return nodeCount != oldnodeCount;
  320. }
  321. public boolean removeAll(Collection c) {
  322. boolean modified = false;
  323. Iterator iter = c.iterator();
  324. while (iter.hasNext()) {
  325. if (removeValue(iter.next()) != null) {
  326. modified = true;
  327. }
  328. }
  329. return modified;
  330. }
  331. public void clear() {
  332. DoubleOrderedMap.this.clear();
  333. }
  334. };
  335. }
  336. return collectionOfValues[VALUE];
  337. }
  338. /**
  339. * common remove logic (remove by key or remove by value)
  340. *
  341. * @param o the key, or value, that we're looking for
  342. * @param index KEY or VALUE
  343. *
  344. * @return the key, if remove by value, or the value, if remove by
  345. * key. null if the specified key or value could not be
  346. * found
  347. */
  348. private Object doRemove(final Comparable o, final int index) {
  349. Node node = lookup(o, index);
  350. Object rval = null;
  351. if (node != null) {
  352. rval = node.getData(oppositeIndex(index));
  353. doRedBlackDelete(node);
  354. }
  355. return rval;
  356. }
  357. /**
  358. * common get logic, used to get by key or get by value
  359. *
  360. * @param o the key or value that we're looking for
  361. * @param index KEY or VALUE
  362. *
  363. * @return the key (if the value was mapped) or the value (if the
  364. * key was mapped); null if we couldn't find the specified
  365. * object
  366. */
  367. private Object doGet(final Comparable o, final int index) {
  368. checkNonNullComparable(o, index);
  369. Node node = lookup(o, index);
  370. return ((node == null)
  371. ? null
  372. : node.getData(oppositeIndex(index)));
  373. }
  374. /**
  375. * Get the opposite index of the specified index
  376. *
  377. * @param index KEY or VALUE
  378. *
  379. * @return VALUE (if KEY was specified), else KEY
  380. */
  381. private int oppositeIndex(final int index) {
  382. // old trick ... to find the opposite of a value, m or n,
  383. // subtract the value from the sum of the two possible
  384. // values. (m + n) - m = n; (m + n) - n = m
  385. return SUM_OF_INDICES - index;
  386. }
  387. /**
  388. * do the actual lookup of a piece of data
  389. *
  390. * @param data the key or value to be looked up
  391. * @param index KEY or VALUE
  392. *
  393. * @return the desired Node, or null if there is no mapping of the
  394. * specified data
  395. */
  396. private Node lookup(final Comparable data, final int index) {
  397. Node rval = null;
  398. Node node = rootNode[index];
  399. while (node != null) {
  400. int cmp = compare(data, node.getData(index));
  401. if (cmp == 0) {
  402. rval = node;
  403. break;
  404. } else {
  405. node = (cmp < 0)
  406. ? node.getLeft(index)
  407. : node.getRight(index);
  408. }
  409. }
  410. return rval;
  411. }
  412. /**
  413. * Compare two objects
  414. *
  415. * @param o1 the first object
  416. * @param o2 the second object
  417. *
  418. * @return negative value if o1 < o2; 0 if o1 == o2; positive
  419. * value if o1 > o2
  420. */
  421. private static int compare(final Comparable o1, final Comparable o2) {
  422. return o1.compareTo(o2);
  423. }
  424. /**
  425. * find the least node from a given node. very useful for starting
  426. * a sorting iterator ...
  427. *
  428. * @param node the node from which we will start searching
  429. * @param index KEY or VALUE
  430. *
  431. * @return the smallest node, from the specified node, in the
  432. * specified mapping
  433. */
  434. private static Node leastNode(final Node node, final int index) {
  435. Node rval = node;
  436. if (rval != null) {
  437. while (rval.getLeft(index) != null) {
  438. rval = rval.getLeft(index);
  439. }
  440. }
  441. return rval;
  442. }
  443. /**
  444. * get the next larger node from the specified node
  445. *
  446. * @param node the node to be searched from
  447. * @param index KEY or VALUE
  448. *
  449. * @return the specified node
  450. */
  451. private Node nextGreater(final Node node, final int index) {
  452. Node rval = null;
  453. if (node == null) {
  454. rval = null;
  455. } else if (node.getRight(index) != null) {
  456. // everything to the node's right is larger. The least of
  457. // the right node's descendants is the next larger node
  458. rval = leastNode(node.getRight(index), index);
  459. } else {
  460. // traverse up our ancestry until we find an ancestor that
  461. // is null or one whose left child is our ancestor. If we
  462. // find a null, then this node IS the largest node in the
  463. // tree, and there is no greater node. Otherwise, we are
  464. // the largest node in the subtree on that ancestor's left
  465. // ... and that ancestor is the next greatest node
  466. Node parent = node.getParent(index);
  467. Node child = node;
  468. while ((parent != null) && (child == parent.getRight(index))) {
  469. child = parent;
  470. parent = parent.getParent(index);
  471. }
  472. rval = parent;
  473. }
  474. return rval;
  475. }
  476. /**
  477. * copy the color from one node to another, dealing with the fact
  478. * that one or both nodes may, in fact, be null
  479. *
  480. * @param from the node whose color we're copying; may be null
  481. * @param to the node whose color we're changing; may be null
  482. * @param index KEY or VALUE
  483. */
  484. private static void copyColor(final Node from, final Node to,
  485. final int index) {
  486. if (to != null) {
  487. if (from == null) {
  488. // by default, make it black
  489. to.setBlack(index);
  490. } else {
  491. to.copyColor(from, index);
  492. }
  493. }
  494. }
  495. /**
  496. * is the specified node red? if the node does not exist, no, it's
  497. * black, thank you
  498. *
  499. * @param node the node (may be null) in question
  500. * @param index KEY or VALUE
  501. */
  502. private static boolean isRed(final Node node, final int index) {
  503. return ((node == null)
  504. ? false
  505. : node.isRed(index));
  506. }
  507. /**
  508. * is the specified black red? if the node does not exist, sure,
  509. * it's black, thank you
  510. *
  511. * @param node the node (may be null) in question
  512. * @param index KEY or VALUE
  513. */
  514. private static boolean isBlack(final Node node, final int index) {
  515. return ((node == null)
  516. ? true
  517. : node.isBlack(index));
  518. }
  519. /**
  520. * force a node (if it exists) red
  521. *
  522. * @param node the node (may be null) in question
  523. * @param index KEY or VALUE
  524. */
  525. private static void makeRed(final Node node, final int index) {
  526. if (node != null) {
  527. node.setRed(index);
  528. }
  529. }
  530. /**
  531. * force a node (if it exists) black
  532. *
  533. * @param node the node (may be null) in question
  534. * @param index KEY or VALUE
  535. */
  536. private static void makeBlack(final Node node, final int index) {
  537. if (node != null) {
  538. node.setBlack(index);
  539. }
  540. }
  541. /**
  542. * get a node's grandparent. mind you, the node, its parent, or
  543. * its grandparent may not exist. no problem
  544. *
  545. * @param node the node (may be null) in question
  546. * @param index KEY or VALUE
  547. */
  548. private static Node getGrandParent(final Node node, final int index) {
  549. return getParent(getParent(node, index), index);
  550. }
  551. /**
  552. * get a node's parent. mind you, the node, or its parent, may not
  553. * exist. no problem
  554. *
  555. * @param node the node (may be null) in question
  556. * @param index KEY or VALUE
  557. */
  558. private static Node getParent(final Node node, final int index) {
  559. return ((node == null)
  560. ? null
  561. : node.getParent(index));
  562. }
  563. /**
  564. * get a node's right child. mind you, the node may not exist. no
  565. * problem
  566. *
  567. * @param node the node (may be null) in question
  568. * @param index KEY or VALUE
  569. */
  570. private static Node getRightChild(final Node node, final int index) {
  571. return (node == null)
  572. ? null
  573. : node.getRight(index);
  574. }
  575. /**
  576. * get a node's left child. mind you, the node may not exist. no
  577. * problem
  578. *
  579. * @param node the node (may be null) in question
  580. * @param index KEY or VALUE
  581. */
  582. private static Node getLeftChild(final Node node, final int index) {
  583. return (node == null)
  584. ? null
  585. : node.getLeft(index);
  586. }
  587. /**
  588. * is this node its parent's left child? mind you, the node, or
  589. * its parent, may not exist. no problem. if the node doesn't
  590. * exist ... it's its non-existent parent's left child. If the
  591. * node does exist but has no parent ... no, we're not the
  592. * non-existent parent's left child. Otherwise (both the specified
  593. * node AND its parent exist), check.
  594. *
  595. * @param node the node (may be null) in question
  596. * @param index KEY or VALUE
  597. */
  598. private static boolean isLeftChild(final Node node, final int index) {
  599. return (node == null)
  600. ? true
  601. : ((node.getParent(index) == null)
  602. ? false
  603. : (node == node.getParent(index).getLeft(index)));
  604. }
  605. /**
  606. * is this node its parent's right child? mind you, the node, or
  607. * its parent, may not exist. no problem. if the node doesn't
  608. * exist ... it's its non-existent parent's right child. If the
  609. * node does exist but has no parent ... no, we're not the
  610. * non-existent parent's right child. Otherwise (both the
  611. * specified node AND its parent exist), check.
  612. *
  613. * @param node the node (may be null) in question
  614. * @param index KEY or VALUE
  615. */
  616. private static boolean isRightChild(final Node node, final int index) {
  617. return (node == null)
  618. ? true
  619. : ((node.getParent(index) == null)
  620. ? false
  621. : (node == node.getParent(index).getRight(index)));
  622. }
  623. /**
  624. * do a rotate left. standard fare in the world of balanced trees
  625. *
  626. * @param node the node to be rotated
  627. * @param index KEY or VALUE
  628. */
  629. private void rotateLeft(final Node node, final int index) {
  630. Node rightChild = node.getRight(index);
  631. node.setRight(rightChild.getLeft(index), index);
  632. if (rightChild.getLeft(index) != null) {
  633. rightChild.getLeft(index).setParent(node, index);
  634. }
  635. rightChild.setParent(node.getParent(index), index);
  636. if (node.getParent(index) == null) {
  637. // node was the root ... now its right child is the root
  638. rootNode[index] = rightChild;
  639. } else if (node.getParent(index).getLeft(index) == node) {
  640. node.getParent(index).setLeft(rightChild, index);
  641. } else {
  642. node.getParent(index).setRight(rightChild, index);
  643. }
  644. rightChild.setLeft(node, index);
  645. node.setParent(rightChild, index);
  646. }
  647. /**
  648. * do a rotate right. standard fare in the world of balanced trees
  649. *
  650. * @param node the node to be rotated
  651. * @param index KEY or VALUE
  652. */
  653. private void rotateRight(final Node node, final int index) {
  654. Node leftChild = node.getLeft(index);
  655. node.setLeft(leftChild.getRight(index), index);
  656. if (leftChild.getRight(index) != null) {
  657. leftChild.getRight(index).setParent(node, index);
  658. }
  659. leftChild.setParent(node.getParent(index), index);
  660. if (node.getParent(index) == null) {
  661. // node was the root ... now its left child is the root
  662. rootNode[index] = leftChild;
  663. } else if (node.getParent(index).getRight(index) == node) {
  664. node.getParent(index).setRight(leftChild, index);
  665. } else {
  666. node.getParent(index).setLeft(leftChild, index);
  667. }
  668. leftChild.setRight(node, index);
  669. node.setParent(leftChild, index);
  670. }
  671. /**
  672. * complicated red-black insert stuff. Based on Sun's TreeMap
  673. * implementation, though it's barely recognizable any more
  674. *
  675. * @param insertedNode the node to be inserted
  676. * @param index KEY or VALUE
  677. */
  678. private void doRedBlackInsert(final Node insertedNode, final int index) {
  679. Node currentNode = insertedNode;
  680. makeRed(currentNode, index);
  681. while ((currentNode != null) && (currentNode != rootNode[index])
  682. && (isRed(currentNode.getParent(index), index))) {
  683. if (isLeftChild(getParent(currentNode, index), index)) {
  684. Node y = getRightChild(getGrandParent(currentNode, index),
  685. index);
  686. if (isRed(y, index)) {
  687. makeBlack(getParent(currentNode, index), index);
  688. makeBlack(y, index);
  689. makeRed(getGrandParent(currentNode, index), index);
  690. currentNode = getGrandParent(currentNode, index);
  691. } else {
  692. if (isRightChild(currentNode, index)) {
  693. currentNode = getParent(currentNode, index);
  694. rotateLeft(currentNode, index);
  695. }
  696. makeBlack(getParent(currentNode, index), index);
  697. makeRed(getGrandParent(currentNode, index), index);
  698. if (getGrandParent(currentNode, index) != null) {
  699. rotateRight(getGrandParent(currentNode, index),
  700. index);
  701. }
  702. }
  703. } else {
  704. // just like clause above, except swap left for right
  705. Node y = getLeftChild(getGrandParent(currentNode, index),
  706. index);
  707. if (isRed(y, index)) {
  708. makeBlack(getParent(currentNode, index), index);
  709. makeBlack(y, index);
  710. makeRed(getGrandParent(currentNode, index), index);
  711. currentNode = getGrandParent(currentNode, index);
  712. } else {
  713. if (isLeftChild(currentNode, index)) {
  714. currentNode = getParent(currentNode, index);
  715. rotateRight(currentNode, index);
  716. }
  717. makeBlack(getParent(currentNode, index), index);
  718. makeRed(getGrandParent(currentNode, index), index);
  719. if (getGrandParent(currentNode, index) != null) {
  720. rotateLeft(getGrandParent(currentNode, index), index);
  721. }
  722. }
  723. }
  724. }
  725. makeBlack(rootNode[index], index);
  726. }
  727. /**
  728. * complicated red-black delete stuff. Based on Sun's TreeMap
  729. * implementation, though it's barely recognizable any more
  730. *
  731. * @param deletedNode the node to be deleted
  732. */
  733. private void doRedBlackDelete(final Node deletedNode) {
  734. for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
  735. // if deleted node has both left and children, swap with
  736. // the next greater node
  737. if ((deletedNode.getLeft(index) != null)
  738. && (deletedNode.getRight(index) != null)) {
  739. swapPosition(nextGreater(deletedNode, index), deletedNode,
  740. index);
  741. }
  742. Node replacement = ((deletedNode.getLeft(index) != null)
  743. ? deletedNode.getLeft(index)
  744. : deletedNode.getRight(index));
  745. if (replacement != null) {
  746. replacement.setParent(deletedNode.getParent(index), index);
  747. if (deletedNode.getParent(index) == null) {
  748. rootNode[index] = replacement;
  749. } else if (deletedNode
  750. == deletedNode.getParent(index).getLeft(index)) {
  751. deletedNode.getParent(index).setLeft(replacement, index);
  752. } else {
  753. deletedNode.getParent(index).setRight(replacement, index);
  754. }
  755. deletedNode.setLeft(null, index);
  756. deletedNode.setRight(null, index);
  757. deletedNode.setParent(null, index);
  758. if (isBlack(deletedNode, index)) {
  759. doRedBlackDeleteFixup(replacement, index);
  760. }
  761. } else {
  762. // replacement is null
  763. if (deletedNode.getParent(index) == null) {
  764. // empty tree
  765. rootNode[index] = null;
  766. } else {
  767. // deleted node had no children
  768. if (isBlack(deletedNode, index)) {
  769. doRedBlackDeleteFixup(deletedNode, index);
  770. }
  771. if (deletedNode.getParent(index) != null) {
  772. if (deletedNode
  773. == deletedNode.getParent(index)
  774. .getLeft(index)) {
  775. deletedNode.getParent(index).setLeft(null, index);
  776. } else {
  777. deletedNode.getParent(index).setRight(null,
  778. index);
  779. }
  780. deletedNode.setParent(null, index);
  781. }
  782. }
  783. }
  784. }
  785. shrink();
  786. }
  787. /**
  788. * complicated red-black delete stuff. Based on Sun's TreeMap
  789. * implementation, though it's barely recognizable any more. This
  790. * rebalances the tree (somewhat, as red-black trees are not
  791. * perfectly balanced -- perfect balancing takes longer)
  792. *
  793. * @param replacementNode the node being replaced
  794. * @param index KEY or VALUE
  795. */
  796. private void doRedBlackDeleteFixup(final Node replacementNode,
  797. final int index) {
  798. Node currentNode = replacementNode;
  799. while ((currentNode != rootNode[index])
  800. && (isBlack(currentNode, index))) {
  801. if (isLeftChild(currentNode, index)) {
  802. Node siblingNode =
  803. getRightChild(getParent(currentNode, index), index);
  804. if (isRed(siblingNode, index)) {
  805. makeBlack(siblingNode, index);
  806. makeRed(getParent(currentNode, index), index);
  807. rotateLeft(getParent(currentNode, index), index);
  808. siblingNode = getRightChild(getParent(currentNode, index), index);
  809. }
  810. if (isBlack(getLeftChild(siblingNode, index), index)
  811. && isBlack(getRightChild(siblingNode, index),
  812. index)) {
  813. makeRed(siblingNode, index);
  814. currentNode = getParent(currentNode, index);
  815. } else {
  816. if (isBlack(getRightChild(siblingNode, index), index)) {
  817. makeBlack(getLeftChild(siblingNode, index), index);
  818. makeRed(siblingNode, index);
  819. rotateRight(siblingNode, index);
  820. siblingNode =
  821. getRightChild(getParent(currentNode, index), index);
  822. }
  823. copyColor(getParent(currentNode, index), siblingNode,
  824. index);
  825. makeBlack(getParent(currentNode, index), index);
  826. makeBlack(getRightChild(siblingNode, index), index);
  827. rotateLeft(getParent(currentNode, index), index);
  828. currentNode = rootNode[index];
  829. }
  830. } else {
  831. Node siblingNode = getLeftChild(getParent(currentNode, index), index);
  832. if (isRed(siblingNode, index)) {
  833. makeBlack(siblingNode, index);
  834. makeRed(getParent(currentNode, index), index);
  835. rotateRight(getParent(currentNode, index), index);
  836. siblingNode = getLeftChild(getParent(currentNode, index), index);
  837. }
  838. if (isBlack(getRightChild(siblingNode, index), index)
  839. && isBlack(getLeftChild(siblingNode, index), index)) {
  840. makeRed(siblingNode, index);
  841. currentNode = getParent(currentNode, index);
  842. } else {
  843. if (isBlack(getLeftChild(siblingNode, index), index)) {
  844. makeBlack(getRightChild(siblingNode, index), index);
  845. makeRed(siblingNode, index);
  846. rotateLeft(siblingNode, index);
  847. siblingNode =
  848. getLeftChild(getParent(currentNode, index), index);
  849. }
  850. copyColor(getParent(currentNode, index), siblingNode,
  851. index);
  852. makeBlack(getParent(currentNode, index), index);
  853. makeBlack(getLeftChild(siblingNode, index), index);
  854. rotateRight(getParent(currentNode, index), index);
  855. currentNode = rootNode[index];
  856. }
  857. }
  858. }
  859. makeBlack(currentNode, index);
  860. }
  861. /**
  862. * swap two nodes (except for their content), taking care of
  863. * special cases where one is the other's parent ... hey, it
  864. * happens.
  865. *
  866. * @param x one node
  867. * @param y another node
  868. * @param index KEY or VALUE
  869. */
  870. private void swapPosition(final Node x, final Node y, final int index) {
  871. // Save initial values.
  872. Node xFormerParent = x.getParent(index);
  873. Node xFormerLeftChild = x.getLeft(index);
  874. Node xFormerRightChild = x.getRight(index);
  875. Node yFormerParent = y.getParent(index);
  876. Node yFormerLeftChild = y.getLeft(index);
  877. Node yFormerRightChild = y.getRight(index);
  878. boolean xWasLeftChild =
  879. (x.getParent(index) != null)
  880. && (x == x.getParent(index).getLeft(index));
  881. boolean yWasLeftChild =
  882. (y.getParent(index) != null)
  883. && (y == y.getParent(index).getLeft(index));
  884. // Swap, handling special cases of one being the other's parent.
  885. if (x == yFormerParent) { // x was y's parent
  886. x.setParent(y, index);
  887. if (yWasLeftChild) {
  888. y.setLeft(x, index);
  889. y.setRight(xFormerRightChild, index);
  890. } else {
  891. y.setRight(x, index);
  892. y.setLeft(xFormerLeftChild, index);
  893. }
  894. } else {
  895. x.setParent(yFormerParent, index);
  896. if (yFormerParent != null) {
  897. if (yWasLeftChild) {
  898. yFormerParent.setLeft(x, index);
  899. } else {
  900. yFormerParent.setRight(x, index);
  901. }
  902. }
  903. y.setLeft(xFormerLeftChild, index);
  904. y.setRight(xFormerRightChild, index);
  905. }
  906. if (y == xFormerParent) { // y was x's parent
  907. y.setParent(x, index);
  908. if (xWasLeftChild) {
  909. x.setLeft(y, index);
  910. x.setRight(yFormerRightChild, index);
  911. } else {
  912. x.setRight(y, index);
  913. x.setLeft(yFormerLeftChild, index);
  914. }
  915. } else {
  916. y.setParent(xFormerParent, index);
  917. if (xFormerParent != null) {
  918. if (xWasLeftChild) {
  919. xFormerParent.setLeft(y, index);
  920. } else {
  921. xFormerParent.setRight(y, index);
  922. }
  923. }
  924. x.setLeft(yFormerLeftChild, index);
  925. x.setRight(yFormerRightChild, index);
  926. }
  927. // Fix children's parent pointers
  928. if (x.getLeft(index) != null) {
  929. x.getLeft(index).setParent(x, index);
  930. }
  931. if (x.getRight(index) != null) {
  932. x.getRight(index).setParent(x, index);
  933. }
  934. if (y.getLeft(index) != null) {
  935. y.getLeft(index).setParent(y, index);
  936. }
  937. if (y.getRight(index) != null) {
  938. y.getRight(index).setParent(y, index);
  939. }
  940. x.swapColors(y, index);
  941. // Check if root changed
  942. if (rootNode[index] == x) {
  943. rootNode[index] = y;
  944. } else if (rootNode[index] == y) {
  945. rootNode[index] = x;
  946. }
  947. }
  948. /**
  949. * check if an object is fit to be proper input ... has to be
  950. * Comparable and non-null
  951. *
  952. * @param o the object being checked
  953. * @param index KEY or VALUE (used to put the right word in the
  954. * exception message)
  955. *
  956. * @throws NullPointerException if o is null
  957. * @throws ClassCastException if o is not Comparable
  958. */
  959. private static void checkNonNullComparable(final Object o,
  960. final int index) {
  961. if (o == null) {
  962. throw new NullPointerException(dataName[index]
  963. + " cannot be null");
  964. }
  965. if (!(o instanceof Comparable)) {
  966. throw new ClassCastException(dataName[index]
  967. + " must be Comparable");
  968. }
  969. }
  970. /**
  971. * check a key for validity (non-null and implements Comparable)
  972. *
  973. * @param key the key to be checked
  974. *
  975. * @throws NullPointerException if key is null
  976. * @throws ClassCastException if key is not Comparable
  977. */
  978. private static void checkKey(final Object key) {
  979. checkNonNullComparable(key, KEY);
  980. }
  981. /**
  982. * check a value for validity (non-null and implements Comparable)
  983. *
  984. * @param value the value to be checked
  985. *
  986. * @throws NullPointerException if value is null
  987. * @throws ClassCastException if value is not Comparable
  988. */
  989. private static void checkValue(final Object value) {
  990. checkNonNullComparable(value, VALUE);
  991. }
  992. /**
  993. * check a key and a value for validity (non-null and implements
  994. * Comparable)
  995. *
  996. * @param key the key to be checked
  997. * @param value the value to be checked
  998. *
  999. * @throws NullPointerException if key or value is null
  1000. * @throws ClassCastException if key or value is not Comparable
  1001. */
  1002. private static void checkKeyAndValue(final Object key,
  1003. final Object value) {
  1004. checkKey(key);
  1005. checkValue(value);
  1006. }
  1007. /**
  1008. * increment the modification count -- used to check for
  1009. * concurrent modification of the map through the map and through
  1010. * an Iterator from one of its Set or Collection views
  1011. */
  1012. private void modify() {
  1013. modifications++;
  1014. }
  1015. /**
  1016. * bump up the size and note that the map has changed
  1017. */
  1018. private void grow() {
  1019. modify();
  1020. nodeCount++;
  1021. }
  1022. /**
  1023. * decrement the size and note that the map has changed
  1024. */
  1025. private void shrink() {
  1026. modify();
  1027. nodeCount--;
  1028. }
  1029. /**
  1030. * insert a node by its value
  1031. *
  1032. * @param newNode the node to be inserted
  1033. *
  1034. * @throws IllegalArgumentException if the node already exists
  1035. * in the value mapping
  1036. */
  1037. private void insertValue(final Node newNode)
  1038. throws IllegalArgumentException {
  1039. Node node = rootNode[VALUE];
  1040. while (true) {
  1041. int cmp = compare(newNode.getData(VALUE), node.getData(VALUE));
  1042. if (cmp == 0) {
  1043. throw new IllegalArgumentException(
  1044. "Cannot store a duplicate value (\""
  1045. + newNode.getData(VALUE) + "\") in this Map");
  1046. } else if (cmp < 0) {
  1047. if (node.getLeft(VALUE) != null) {
  1048. node = node.getLeft(VALUE);
  1049. } else {
  1050. node.setLeft(newNode, VALUE);
  1051. newNode.setParent(node, VALUE);
  1052. doRedBlackInsert(newNode, VALUE);
  1053. break;
  1054. }
  1055. } else { // cmp > 0
  1056. if (node.getRight(VALUE) != null) {
  1057. node = node.getRight(VALUE);
  1058. } else {
  1059. node.setRight(newNode, VALUE);
  1060. newNode.setParent(node, VALUE);
  1061. doRedBlackInsert(newNode, VALUE);
  1062. break;
  1063. }
  1064. }
  1065. }
  1066. }
  1067. /* ********** START implementation of Map ********** */
  1068. /**
  1069. * Returns the number of key-value mappings in this map. If the
  1070. * map contains more than Integer.MAXVALUE elements, returns
  1071. * Integer.MAXVALUE.
  1072. *
  1073. * @return the number of key-value mappings in this map.
  1074. */
  1075. public int size() {
  1076. return nodeCount;
  1077. }
  1078. /**
  1079. * Returns true if this map contains a mapping for the specified
  1080. * key.
  1081. *
  1082. * @param key key whose presence in this map is to be tested.
  1083. *
  1084. * @return true if this map contains a mapping for the specified
  1085. * key.
  1086. *
  1087. * @throws ClassCastException if the key is of an inappropriate
  1088. * type for this map.
  1089. * @throws NullPointerException if the key is null
  1090. */
  1091. public boolean containsKey(final Object key)
  1092. throws ClassCastException, NullPointerException {
  1093. checkKey(key);
  1094. return lookup((Comparable) key, KEY) != null;
  1095. }
  1096. /**
  1097. * Returns true if this map maps one or more keys to the
  1098. * specified value.
  1099. *
  1100. * @param value value whose presence in this map is to be tested.
  1101. *
  1102. * @return true if this map maps one or more keys to the specified
  1103. * value.
  1104. */
  1105. public boolean containsValue(final Object value) {
  1106. checkValue(value);
  1107. return lookup((Comparable) value, VALUE) != null;
  1108. }
  1109. /**
  1110. * Returns the value to which this map maps the specified
  1111. * key. Returns null if the map contains no mapping for this key.
  1112. *
  1113. * @param key key whose associated value is to be returned.
  1114. *
  1115. * @return the value to which this map maps the specified key, or
  1116. * null if the map contains no mapping for this key.
  1117. *
  1118. * @throws ClassCastException if the key is of an inappropriate
  1119. * type for this map.
  1120. * @throws NullPointerException if the key is null
  1121. */
  1122. public Object get(final Object key)
  1123. throws ClassCastException, NullPointerException {
  1124. return doGet((Comparable) key, KEY);
  1125. }
  1126. /**
  1127. * Associates the specified value with the specified key in this
  1128. * map.
  1129. *
  1130. * @param key key with which the specified value is to be
  1131. * associated.
  1132. * @param value value to be associated with the specified key.
  1133. *
  1134. * @return null
  1135. *
  1136. * @throws ClassCastException if the class of the specified key
  1137. * or value prevents it from being
  1138. * stored in this map.
  1139. * @throws NullPointerException if the specified key or value
  1140. * is null
  1141. * @throws IllegalArgumentException if the key duplicates an
  1142. * existing key, or if the
  1143. * value duplicates an
  1144. * existing value
  1145. */
  1146. public Object put(final Object key, final Object value)
  1147. throws ClassCastException, NullPointerException,
  1148. IllegalArgumentException {
  1149. checkKeyAndValue(key, value);
  1150. Node node = rootNode[KEY];
  1151. if (node == null) {
  1152. Node root = new Node((Comparable) key, (Comparable) value);
  1153. rootNode[KEY] = root;
  1154. rootNode[VALUE] = root;
  1155. grow();
  1156. } else {
  1157. while (true) {
  1158. int cmp = compare((Comparable) key, node.getData(KEY));
  1159. if (cmp == 0) {
  1160. throw new IllegalArgumentException(
  1161. "Cannot store a duplicate key (\"" + key
  1162. + "\") in this Map");
  1163. } else if (cmp < 0) {
  1164. if (node.getLeft(KEY) != null) {
  1165. node = node.getLeft(KEY);
  1166. } else {
  1167. Node newNode = new Node((Comparable) key,
  1168. (Comparable) value);
  1169. insertValue(newNode);
  1170. node.setLeft(newNode, KEY);
  1171. newNode.setParent(node, KEY);
  1172. doRedBlackInsert(newNode, KEY);
  1173. grow();
  1174. break;
  1175. }
  1176. } else { // cmp > 0
  1177. if (node.getRight(KEY) != null) {
  1178. node = node.getRight(KEY);
  1179. } else {
  1180. Node newNode = new Node((Comparable) key,
  1181. (Comparable) value);
  1182. insertValue(newNode);
  1183. node.setRight(newNode, KEY);
  1184. newNode.setParent(node, KEY);
  1185. doRedBlackInsert(newNode, KEY);
  1186. grow();
  1187. break;
  1188. }
  1189. }
  1190. }
  1191. }
  1192. return null;
  1193. }
  1194. /**
  1195. * Removes the mapping for this key from this map if present
  1196. *
  1197. * @param key key whose mapping is to be removed from the map.
  1198. *
  1199. * @return previous value associated with specified key, or null
  1200. * if there was no mapping for key.
  1201. */
  1202. public Object remove(final Object key) {
  1203. return doRemove((Comparable) key, KEY);
  1204. }
  1205. /**
  1206. * Removes all mappings from this map
  1207. */
  1208. public void clear() {
  1209. modify();
  1210. nodeCount = 0;
  1211. rootNode[KEY] = null;
  1212. rootNode[VALUE] = null;
  1213. }
  1214. /**
  1215. * Returns a set view of the keys contained in this map. The set
  1216. * is backed by the map, so changes to the map are reflected in
  1217. * the set, and vice-versa. If the map is modified while an
  1218. * iteration over the set is in progress, the results of the
  1219. * iteration are undefined. The set supports element removal,
  1220. * which removes the corresponding mapping from the map, via the
  1221. * Iterator.remove, Set.remove, removeAll, retainAll, and clear
  1222. * operations. It does not support the add or addAll operations.
  1223. *
  1224. * @return a set view of the keys contained in this map.
  1225. */
  1226. public Set keySet() {
  1227. if (setOfKeys[KEY] == null) {
  1228. setOfKeys[KEY] = new AbstractSet() {
  1229. public Iterator iterator() {
  1230. return new DoubleOrderedMapIterator(KEY) {
  1231. protected Object doGetNext() {
  1232. return lastReturnedNode.getData(KEY);
  1233. }
  1234. };
  1235. }
  1236. public int size() {
  1237. return DoubleOrderedMap.this.size();
  1238. }
  1239. public boolean contains(Object o) {
  1240. return containsKey(o);
  1241. }
  1242. public boolean remove(Object o) {
  1243. int oldNodeCount = nodeCount;
  1244. DoubleOrderedMap.this.remove(o);
  1245. return nodeCount != oldNodeCount;
  1246. }
  1247. public void clear() {
  1248. DoubleOrderedMap.this.clear();
  1249. }
  1250. };
  1251. }
  1252. return setOfKeys[KEY];
  1253. }
  1254. /**
  1255. * Returns a collection view of the values contained in this
  1256. * map. The collection is backed by the map, so changes to the map
  1257. * are reflected in the collection, and vice-versa. If the map is
  1258. * modified while an iteration over the collection is in progress,
  1259. * the results of the iteration are undefined. The collection
  1260. * supports element removal, which removes the corresponding
  1261. * mapping from the map, via the Iterator.remove,
  1262. * Collection.remove, removeAll, retainAll and clear operations.
  1263. * It does not support the add or addAll operations.
  1264. *
  1265. * @return a collection view of the values contained in this map.
  1266. */
  1267. public Collection values() {
  1268. if (collectionOfValues[KEY] == null) {
  1269. collectionOfValues[KEY] = new AbstractCollection() {
  1270. public Iterator iterator() {
  1271. return new DoubleOrderedMapIterator(KEY) {
  1272. protected Object doGetNext() {
  1273. return lastReturnedNode.getData(VALUE);
  1274. }
  1275. };
  1276. }
  1277. public int size() {
  1278. return DoubleOrderedMap.this.size();
  1279. }
  1280. public boolean contains(Object o) {
  1281. return containsValue(o);
  1282. }
  1283. public boolean remove(Object o) {
  1284. int oldNodeCount = nodeCount;
  1285. removeValue(o);
  1286. return nodeCount != oldNodeCount;
  1287. }
  1288. public boolean removeAll(Collection c) {
  1289. boolean modified = false;
  1290. Iterator iter = c.iterator();
  1291. while (iter.hasNext()) {
  1292. if (removeValue(iter.next()) != null) {
  1293. modified = true;
  1294. }
  1295. }
  1296. return modified;
  1297. }
  1298. public void clear() {
  1299. DoubleOrderedMap.this.clear();
  1300. }
  1301. };
  1302. }
  1303. return collectionOfValues[KEY];
  1304. }
  1305. /**
  1306. * Returns a set view of the mappings contained in this map. Each
  1307. * element in the returned set is a Map.Entry. The set is backed
  1308. * by the map, so changes to the map are reflected in the set, and
  1309. * vice-versa. If the map is modified while an iteration over the
  1310. * set is in progress, the results of the iteration are
  1311. * undefined.
  1312. * <p>
  1313. * The set supports element removal, which removes the corresponding
  1314. * mapping from the map, via the Iterator.remove, Set.remove, removeAll,
  1315. * retainAll and clear operations.
  1316. * It does not support the add or addAll operations.
  1317. * The setValue method is not supported on the Map Entry.
  1318. *
  1319. * @return a set view of the mappings contained in this map.
  1320. */
  1321. public Set entrySet() {
  1322. if (setOfEntries[KEY] == null) {
  1323. setOfEntries[KEY] = new AbstractSet() {
  1324. public Iterator iterator() {
  1325. return new DoubleOrderedMapIterator(KEY) {
  1326. protected Object doGetNext() {
  1327. return lastReturnedNode;
  1328. }
  1329. };
  1330. }
  1331. public boolean contains(Object o) {
  1332. if (!(o instanceof Map.Entry)) {
  1333. return false;
  1334. }
  1335. Map.Entry entry = (Map.Entry) o;
  1336. Object value = entry.getValue();
  1337. Node node = lookup((Comparable) entry.getKey(),
  1338. KEY);
  1339. return (node != null)
  1340. && node.getData(VALUE).equals(value);
  1341. }
  1342. public boolean remove(Object o) {
  1343. if (!(o instanceof Map.Entry)) {
  1344. return false;
  1345. }
  1346. Map.Entry entry = (Map.Entry) o;
  1347. Object value = entry.getValue();
  1348. Node node = lookup((Comparable) entry.getKey(),
  1349. KEY);
  1350. if ((node != null) && node.getData(VALUE).equals(value)) {
  1351. doRedBlackDelete(node);
  1352. return true;
  1353. }
  1354. return false;
  1355. }
  1356. public int size() {
  1357. return DoubleOrderedMap.this.size();
  1358. }
  1359. public void clear() {
  1360. DoubleOrderedMap.this.clear();
  1361. }
  1362. };
  1363. }
  1364. return setOfEntries[KEY];
  1365. }
  1366. /* ********** END implementation of Map ********** */
  1367. private abstract class DoubleOrderedMapIterator implements Iterator {
  1368. private int expectedModifications;
  1369. protected Node lastReturnedNode;
  1370. private Node nextNode;
  1371. private int iteratorType;
  1372. /**
  1373. * Constructor
  1374. *
  1375. * @param type
  1376. */
  1377. DoubleOrderedMapIterator(final int type) {
  1378. iteratorType = type;
  1379. expectedModifications = DoubleOrderedMap.this.modifications;
  1380. lastReturnedNode = null;
  1381. nextNode = leastNode(rootNode[iteratorType],
  1382. iteratorType);
  1383. }
  1384. /**
  1385. * @return 'next', whatever that means for a given kind of
  1386. * DoubleOrderedMapIterator
  1387. */
  1388. protected abstract Object doGetNext();
  1389. /* ********** START implementation of Iterator ********** */
  1390. /**
  1391. * @return true if the iterator has more elements.
  1392. */
  1393. public final boolean hasNext() {
  1394. return nextNode != null;
  1395. }
  1396. /**
  1397. * @return the next element in the iteration.
  1398. *
  1399. * @throws NoSuchElementException if iteration has no more
  1400. * elements.
  1401. * @throws ConcurrentModificationException if the
  1402. * DoubleOrderedMap is
  1403. * modified behind
  1404. * the iterator's
  1405. * back
  1406. */
  1407. public final Object next()
  1408. throws NoSuchElementException,
  1409. ConcurrentModificationException {
  1410. if (nextNode == null) {
  1411. throw new NoSuchElementException();
  1412. }
  1413. if (modifications != expectedModifications) {
  1414. throw new ConcurrentModificationException();
  1415. }
  1416. lastReturnedNode = nextNode;
  1417. nextNode = nextGreater(nextNode, iteratorType);
  1418. return doGetNext();
  1419. }
  1420. /**
  1421. * Removes from the underlying collection the last element
  1422. * returned by the iterator. This method can be called only
  1423. * once per call to next. The behavior of an iterator is
  1424. * unspecified if the underlying collection is modified while
  1425. * the iteration is in progress in any way other than by
  1426. * calling this method.
  1427. *
  1428. * @throws IllegalStateException if the next method has not
  1429. * yet been called, or the
  1430. * remove method has already
  1431. * been called after the last
  1432. * call to the next method.
  1433. * @throws ConcurrentModificationException if the
  1434. * DoubleOrderedMap is
  1435. * modified behind
  1436. * the iterator's
  1437. * back
  1438. */
  1439. public final void remove()
  1440. throws IllegalStateException,
  1441. ConcurrentModificationException {
  1442. if (lastReturnedNode == null) {
  1443. throw new IllegalStateException();
  1444. }
  1445. if (modifications != expectedModifications) {
  1446. throw new ConcurrentModificationException();
  1447. }
  1448. doRedBlackDelete(lastReturnedNode);
  1449. expectedModifications++;
  1450. lastReturnedNode = null;
  1451. }
  1452. /* ********** END implementation of Iterator ********** */
  1453. } // end private abstract class DoubleOrderedMapIterator
  1454. // final for performance
  1455. private static final class Node implements Map.Entry, KeyValue {
  1456. private Comparable[] data;
  1457. private Node[] leftNode;
  1458. private Node[] rightNode;
  1459. private Node[] parentNode;
  1460. private boolean[] blackColor;
  1461. private int hashcodeValue;
  1462. private boolean calculatedHashCode;
  1463. /**
  1464. * Make a new cell with given key and value, and with null
  1465. * links, and black (true) colors.
  1466. *
  1467. * @param key
  1468. * @param value
  1469. */
  1470. Node(final Comparable key, final Comparable value) {
  1471. data = new Comparable[]{ key, value };
  1472. leftNode = new Node[]{ null, null };
  1473. rightNode = new Node[]{ null, null };
  1474. parentNode = new Node[]{ null, null };
  1475. blackColor = new boolean[]{ true, true };
  1476. calculatedHashCode = false;
  1477. }
  1478. /**
  1479. * get the specified data
  1480. *
  1481. * @param index KEY or VALUE
  1482. *
  1483. * @return the key or value
  1484. */
  1485. private Comparable getData(final int index) {
  1486. return data[index];
  1487. }
  1488. /**
  1489. * Set this node's left node
  1490. *
  1491. * @param node the new left node
  1492. * @param index KEY or VALUE
  1493. */
  1494. private void setLeft(final Node node, final int index) {
  1495. leftNode[index] = node;
  1496. }
  1497. /**
  1498. * get the left node
  1499. *
  1500. * @param index KEY or VALUE
  1501. *
  1502. * @return the left node -- may be null
  1503. */
  1504. private Node getLeft(final int index) {
  1505. return leftNode[index];
  1506. }
  1507. /**
  1508. * Set this node's right node
  1509. *
  1510. * @param node the new right node
  1511. * @param index KEY or VALUE
  1512. */
  1513. private void setRight(final Node node, final int index) {
  1514. rightNode[index] = node;
  1515. }
  1516. /**
  1517. * get the right node
  1518. *
  1519. * @param index KEY or VALUE
  1520. *
  1521. * @return the right node -- may be null
  1522. */
  1523. private Node getRight(final int index) {
  1524. return rightNode[index];
  1525. }
  1526. /**
  1527. * Set this node's parent node
  1528. *
  1529. * @param node the new parent node
  1530. * @param index KEY or VALUE
  1531. */
  1532. private void setParent(final Node node, final int index) {
  1533. parentNode[index] = node;
  1534. }
  1535. /**
  1536. * get the parent node
  1537. *
  1538. * @param index KEY or VALUE
  1539. *
  1540. * @return the parent node -- may be null
  1541. */
  1542. private Node getParent(final int index) {
  1543. return parentNode[index];
  1544. }
  1545. /**
  1546. * exchange colors with another node
  1547. *
  1548. * @param node the node to swap with
  1549. * @param index KEY or VALUE
  1550. */
  1551. private void swapColors(final Node node, final int index) {
  1552. // Swap colors -- old hacker's trick
  1553. blackColor[index] ^= node.blackColor[index];
  1554. node.blackColor[index] ^= blackColor[index];
  1555. blackColor[index] ^= node.blackColor[index];
  1556. }
  1557. /**
  1558. * is this node black?
  1559. *
  1560. * @param index KEY or VALUE
  1561. *
  1562. * @return true if black (which is represented as a true boolean)
  1563. */
  1564. private boolean isBlack(final int index) {
  1565. return blackColor[index];
  1566. }
  1567. /**
  1568. * is this node red?
  1569. *
  1570. * @param index KEY or VALUE
  1571. *
  1572. * @return true if non-black
  1573. */
  1574. private boolean isRed(final int index) {
  1575. return !blackColor[index];
  1576. }
  1577. /**
  1578. * make this node black
  1579. *
  1580. * @param index KEY or VALUE
  1581. */
  1582. private void setBlack(final int index) {
  1583. blackColor[index] = true;
  1584. }
  1585. /**
  1586. * make this node red
  1587. *
  1588. * @param index KEY or VALUE
  1589. */
  1590. private void setRed(final int index) {
  1591. blackColor[index] = false;
  1592. }
  1593. /**
  1594. * make this node the same color as another
  1595. *
  1596. * @param node the node whose color we're adopting
  1597. * @param index KEY or VALUE
  1598. */
  1599. private void copyColor(final Node node, final int index) {
  1600. blackColor[index] = node.blackColor[index];
  1601. }
  1602. /* ********** START implementation of Map.Entry ********** */
  1603. /**
  1604. * @return the key corresponding to this entry.
  1605. */
  1606. public Object getKey() {
  1607. return data[KEY];
  1608. }
  1609. /**
  1610. * @return the value corresponding to this entry.
  1611. */
  1612. public Object getValue() {
  1613. return data[VALUE];
  1614. }
  1615. /**
  1616. * Optional operation that is not permitted in this
  1617. * implementation
  1618. *
  1619. * @param ignored
  1620. *
  1621. * @return does not return
  1622. *
  1623. * @throws UnsupportedOperationException
  1624. */
  1625. public Object setValue(Object ignored)
  1626. throws UnsupportedOperationException {
  1627. throw new UnsupportedOperationException(
  1628. "Map.Entry.setValue is not supported");
  1629. }
  1630. /**
  1631. * Compares the specified object with this entry for equality.
  1632. * Returns true if the given object is also a map entry and
  1633. * the two entries represent the same mapping.
  1634. *
  1635. * @param o object to be compared for equality with this map
  1636. * entry.
  1637. * @return true if the specified object is equal to this map
  1638. * entry.
  1639. */
  1640. public boolean equals(Object o) {
  1641. if (this == o) {
  1642. return true;
  1643. }
  1644. if (!(o instanceof Map.Entry)) {
  1645. return false;
  1646. }
  1647. Map.Entry e = (Map.Entry) o;
  1648. return data[KEY].equals(e.getKey())
  1649. && data[VALUE].equals(e.getValue());
  1650. }
  1651. /**
  1652. * @return the hash code value for this map entry.
  1653. */
  1654. public int hashCode() {
  1655. if (!calculatedHashCode) {
  1656. hashcodeValue = data[KEY].hashCode()
  1657. ^ data[VALUE].hashCode();
  1658. calculatedHashCode = true;
  1659. }
  1660. return hashcodeValue;
  1661. }
  1662. /* ********** END implementation of Map.Entry ********** */
  1663. }
  1664. } // end public class DoubleOrderedMap