1. /*
  2. * Copyright 2001-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.Collection;
  18. import java.util.Comparator;
  19. import java.util.ConcurrentModificationException;
  20. import java.util.Iterator;
  21. import java.util.Map;
  22. import java.util.Set;
  23. import java.util.SortedMap;
  24. import java.util.TreeMap;
  25. /**
  26. * <p>A customized implementation of <code>java.util.TreeMap</code> designed
  27. * to operate in a multithreaded environment where the large majority of
  28. * method calls are read-only, instead of structural changes. When operating
  29. * in "fast" mode, read calls are non-synchronized and write calls perform the
  30. * following steps:</p>
  31. * <ul>
  32. * <li>Clone the existing collection
  33. * <li>Perform the modification on the clone
  34. * <li>Replace the existing collection with the (modified) clone
  35. * </ul>
  36. * <p>When first created, objects of this class default to "slow" mode, where
  37. * all accesses of any type are synchronized but no cloning takes place. This
  38. * is appropriate for initially populating the collection, followed by a switch
  39. * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
  40. * is complete.</p>
  41. *
  42. * <p><strong>NOTE</strong>: If you are creating and accessing a
  43. * <code>TreeMap</code> only within a single thread, you should use
  44. * <code>java.util.TreeMap</code> directly (with no synchronization), for
  45. * maximum performance.</p>
  46. *
  47. * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
  48. * Using it may cause unexpected failures on some architectures.</i>
  49. * It suffers from the same problems as the double-checked locking idiom.
  50. * In particular, the instruction that clones the internal collection and the
  51. * instruction that sets the internal reference to the clone can be executed
  52. * or perceived out-of-order. This means that any read operation might fail
  53. * unexpectedly, as it may be reading the state of the internal collection
  54. * before the internal collection is fully formed.
  55. * For more information on the double-checked locking idiom, see the
  56. * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
  57. * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
  58. *
  59. * @since Commons Collections 1.0
  60. * @version $Revision: 1.16 $ $Date: 2004/02/18 01:15:42 $
  61. *
  62. * @author Craig R. McClanahan
  63. * @author Stephen Colebourne
  64. */
  65. public class FastTreeMap extends TreeMap {
  66. /**
  67. * The underlying map we are managing.
  68. */
  69. protected TreeMap map = null;
  70. /**
  71. * Are we operating in "fast" mode?
  72. */
  73. protected boolean fast = false;
  74. // Constructors
  75. // ----------------------------------------------------------------------
  76. /**
  77. * Construct a an empty map.
  78. */
  79. public FastTreeMap() {
  80. super();
  81. this.map = new TreeMap();
  82. }
  83. /**
  84. * Construct an empty map with the specified comparator.
  85. *
  86. * @param comparator the comparator to use for ordering tree elements
  87. */
  88. public FastTreeMap(Comparator comparator) {
  89. super();
  90. this.map = new TreeMap(comparator);
  91. }
  92. /**
  93. * Construct a new map with the same mappings as the specified map,
  94. * sorted according to the keys's natural order
  95. *
  96. * @param map the map whose mappings are to be copied
  97. */
  98. public FastTreeMap(Map map) {
  99. super();
  100. this.map = new TreeMap(map);
  101. }
  102. /**
  103. * Construct a new map with the same mappings as the specified map,
  104. * sorted according to the same ordering
  105. *
  106. * @param map the map whose mappings are to be copied
  107. */
  108. public FastTreeMap(SortedMap map) {
  109. super();
  110. this.map = new TreeMap(map);
  111. }
  112. // Property access
  113. // ----------------------------------------------------------------------
  114. /**
  115. * Returns true if this map is operating in fast mode.
  116. *
  117. * @return true if this map is operating in fast mode
  118. */
  119. public boolean getFast() {
  120. return (this.fast);
  121. }
  122. /**
  123. * Sets whether this map is operating in fast mode.
  124. *
  125. * @param fast true if this map should operate in fast mode
  126. */
  127. public void setFast(boolean fast) {
  128. this.fast = fast;
  129. }
  130. // Map access
  131. // ----------------------------------------------------------------------
  132. // These methods can forward straight to the wrapped Map in 'fast' mode.
  133. // (because they are query methods)
  134. /**
  135. * Return the value to which this map maps the specified key. Returns
  136. * <code>null</code> if the map contains no mapping for this key, or if
  137. * there is a mapping with a value of <code>null</code>. Use the
  138. * <code>containsKey()</code> method to disambiguate these cases.
  139. *
  140. * @param key the key whose value is to be returned
  141. * @return the value mapped to that key, or null
  142. */
  143. public Object get(Object key) {
  144. if (fast) {
  145. return (map.get(key));
  146. } else {
  147. synchronized (map) {
  148. return (map.get(key));
  149. }
  150. }
  151. }
  152. /**
  153. * Return the number of key-value mappings in this map.
  154. *
  155. * @return the current size of the map
  156. */
  157. public int size() {
  158. if (fast) {
  159. return (map.size());
  160. } else {
  161. synchronized (map) {
  162. return (map.size());
  163. }
  164. }
  165. }
  166. /**
  167. * Return <code>true</code> if this map contains no mappings.
  168. *
  169. * @return is the map currently empty
  170. */
  171. public boolean isEmpty() {
  172. if (fast) {
  173. return (map.isEmpty());
  174. } else {
  175. synchronized (map) {
  176. return (map.isEmpty());
  177. }
  178. }
  179. }
  180. /**
  181. * Return <code>true</code> if this map contains a mapping for the
  182. * specified key.
  183. *
  184. * @param key the key to be searched for
  185. * @return true if the map contains the key
  186. */
  187. public boolean containsKey(Object key) {
  188. if (fast) {
  189. return (map.containsKey(key));
  190. } else {
  191. synchronized (map) {
  192. return (map.containsKey(key));
  193. }
  194. }
  195. }
  196. /**
  197. * Return <code>true</code> if this map contains one or more keys mapping
  198. * to the specified value.
  199. *
  200. * @param value the value to be searched for
  201. * @return true if the map contains the value
  202. */
  203. public boolean containsValue(Object value) {
  204. if (fast) {
  205. return (map.containsValue(value));
  206. } else {
  207. synchronized (map) {
  208. return (map.containsValue(value));
  209. }
  210. }
  211. }
  212. /**
  213. * Return the comparator used to order this map, or <code>null</code>
  214. * if this map uses its keys' natural order.
  215. *
  216. * @return the comparator used to order the map, or null if natural order
  217. */
  218. public Comparator comparator() {
  219. if (fast) {
  220. return (map.comparator());
  221. } else {
  222. synchronized (map) {
  223. return (map.comparator());
  224. }
  225. }
  226. }
  227. /**
  228. * Return the first (lowest) key currently in this sorted map.
  229. *
  230. * @return the first key in the map
  231. */
  232. public Object firstKey() {
  233. if (fast) {
  234. return (map.firstKey());
  235. } else {
  236. synchronized (map) {
  237. return (map.firstKey());
  238. }
  239. }
  240. }
  241. /**
  242. * Return the last (highest) key currently in this sorted map.
  243. *
  244. * @return the last key in the map
  245. */
  246. public Object lastKey() {
  247. if (fast) {
  248. return (map.lastKey());
  249. } else {
  250. synchronized (map) {
  251. return (map.lastKey());
  252. }
  253. }
  254. }
  255. // Map modification
  256. // ----------------------------------------------------------------------
  257. // These methods perform special behaviour in 'fast' mode.
  258. // The map is cloned, updated and then assigned back.
  259. // See the comments at the top as to why this won't always work.
  260. /**
  261. * Associate the specified value with the specified key in this map.
  262. * If the map previously contained a mapping for this key, the old
  263. * value is replaced and returned.
  264. *
  265. * @param key the key with which the value is to be associated
  266. * @param value the value to be associated with this key
  267. * @return the value previously mapped to the key, or null
  268. */
  269. public Object put(Object key, Object value) {
  270. if (fast) {
  271. synchronized (this) {
  272. TreeMap temp = (TreeMap) map.clone();
  273. Object result = temp.put(key, value);
  274. map = temp;
  275. return (result);
  276. }
  277. } else {
  278. synchronized (map) {
  279. return (map.put(key, value));
  280. }
  281. }
  282. }
  283. /**
  284. * Copy all of the mappings from the specified map to this one, replacing
  285. * any mappings with the same keys.
  286. *
  287. * @param in the map whose mappings are to be copied
  288. */
  289. public void putAll(Map in) {
  290. if (fast) {
  291. synchronized (this) {
  292. TreeMap temp = (TreeMap) map.clone();
  293. temp.putAll(in);
  294. map = temp;
  295. }
  296. } else {
  297. synchronized (map) {
  298. map.putAll(in);
  299. }
  300. }
  301. }
  302. /**
  303. * Remove any mapping for this key, and return any previously
  304. * mapped value.
  305. *
  306. * @param key the key whose mapping is to be removed
  307. * @return the value removed, or null
  308. */
  309. public Object remove(Object key) {
  310. if (fast) {
  311. synchronized (this) {
  312. TreeMap temp = (TreeMap) map.clone();
  313. Object result = temp.remove(key);
  314. map = temp;
  315. return (result);
  316. }
  317. } else {
  318. synchronized (map) {
  319. return (map.remove(key));
  320. }
  321. }
  322. }
  323. /**
  324. * Remove all mappings from this map.
  325. */
  326. public void clear() {
  327. if (fast) {
  328. synchronized (this) {
  329. map = new TreeMap();
  330. }
  331. } else {
  332. synchronized (map) {
  333. map.clear();
  334. }
  335. }
  336. }
  337. // Basic object methods
  338. // ----------------------------------------------------------------------
  339. /**
  340. * Compare the specified object with this list for equality. This
  341. * implementation uses exactly the code that is used to define the
  342. * list equals function in the documentation for the
  343. * <code>Map.equals</code> method.
  344. *
  345. * @param o the object to be compared to this list
  346. * @return true if the two maps are equal
  347. */
  348. public boolean equals(Object o) {
  349. // Simple tests that require no synchronization
  350. if (o == this) {
  351. return (true);
  352. } else if (!(o instanceof Map)) {
  353. return (false);
  354. }
  355. Map mo = (Map) o;
  356. // Compare the two maps for equality
  357. if (fast) {
  358. if (mo.size() != map.size()) {
  359. return (false);
  360. }
  361. Iterator i = map.entrySet().iterator();
  362. while (i.hasNext()) {
  363. Map.Entry e = (Map.Entry) i.next();
  364. Object key = e.getKey();
  365. Object value = e.getValue();
  366. if (value == null) {
  367. if (!(mo.get(key) == null && mo.containsKey(key))) {
  368. return (false);
  369. }
  370. } else {
  371. if (!value.equals(mo.get(key))) {
  372. return (false);
  373. }
  374. }
  375. }
  376. return (true);
  377. } else {
  378. synchronized (map) {
  379. if (mo.size() != map.size()) {
  380. return (false);
  381. }
  382. Iterator i = map.entrySet().iterator();
  383. while (i.hasNext()) {
  384. Map.Entry e = (Map.Entry) i.next();
  385. Object key = e.getKey();
  386. Object value = e.getValue();
  387. if (value == null) {
  388. if (!(mo.get(key) == null && mo.containsKey(key))) {
  389. return (false);
  390. }
  391. } else {
  392. if (!value.equals(mo.get(key))) {
  393. return (false);
  394. }
  395. }
  396. }
  397. return (true);
  398. }
  399. }
  400. }
  401. /**
  402. * Return the hash code value for this map. This implementation uses
  403. * exactly the code that is used to define the list hash function in the
  404. * documentation for the <code>Map.hashCode</code> method.
  405. *
  406. * @return a suitable integer hash code
  407. */
  408. public int hashCode() {
  409. if (fast) {
  410. int h = 0;
  411. Iterator i = map.entrySet().iterator();
  412. while (i.hasNext()) {
  413. h += i.next().hashCode();
  414. }
  415. return (h);
  416. } else {
  417. synchronized (map) {
  418. int h = 0;
  419. Iterator i = map.entrySet().iterator();
  420. while (i.hasNext()) {
  421. h += i.next().hashCode();
  422. }
  423. return (h);
  424. }
  425. }
  426. }
  427. /**
  428. * Return a shallow copy of this <code>FastTreeMap</code> instance.
  429. * The keys and values themselves are not copied.
  430. *
  431. * @return a clone of this map
  432. */
  433. public Object clone() {
  434. FastTreeMap results = null;
  435. if (fast) {
  436. results = new FastTreeMap(map);
  437. } else {
  438. synchronized (map) {
  439. results = new FastTreeMap(map);
  440. }
  441. }
  442. results.setFast(getFast());
  443. return (results);
  444. }
  445. // Sub map views
  446. // ----------------------------------------------------------------------
  447. /**
  448. * Return a view of the portion of this map whose keys are strictly
  449. * less than the specified key.
  450. *
  451. * @param key Key higher than any in the returned map
  452. * @return a head map
  453. */
  454. public SortedMap headMap(Object key) {
  455. if (fast) {
  456. return (map.headMap(key));
  457. } else {
  458. synchronized (map) {
  459. return (map.headMap(key));
  460. }
  461. }
  462. }
  463. /**
  464. * Return a view of the portion of this map whose keys are in the
  465. * range fromKey (inclusive) to toKey (exclusive).
  466. *
  467. * @param fromKey Lower limit of keys for the returned map
  468. * @param toKey Upper limit of keys for the returned map
  469. * @return a sub map
  470. */
  471. public SortedMap subMap(Object fromKey, Object toKey) {
  472. if (fast) {
  473. return (map.subMap(fromKey, toKey));
  474. } else {
  475. synchronized (map) {
  476. return (map.subMap(fromKey, toKey));
  477. }
  478. }
  479. }
  480. /**
  481. * Return a view of the portion of this map whose keys are greater than
  482. * or equal to the specified key.
  483. *
  484. * @param key Key less than or equal to any in the returned map
  485. * @return a tail map
  486. */
  487. public SortedMap tailMap(Object key) {
  488. if (fast) {
  489. return (map.tailMap(key));
  490. } else {
  491. synchronized (map) {
  492. return (map.tailMap(key));
  493. }
  494. }
  495. }
  496. // Map views
  497. // ----------------------------------------------------------------------
  498. /**
  499. * Return a collection view of the mappings contained in this map. Each
  500. * element in the returned collection is a <code>Map.Entry</code>.
  501. */
  502. public Set entrySet() {
  503. return new EntrySet();
  504. }
  505. /**
  506. * Return a set view of the keys contained in this map.
  507. */
  508. public Set keySet() {
  509. return new KeySet();
  510. }
  511. /**
  512. * Return a collection view of the values contained in this map.
  513. */
  514. public Collection values() {
  515. return new Values();
  516. }
  517. // Map view inner classes
  518. // ----------------------------------------------------------------------
  519. /**
  520. * Abstract collection implementation shared by keySet(), values() and entrySet().
  521. */
  522. private abstract class CollectionView implements Collection {
  523. public CollectionView() {
  524. }
  525. protected abstract Collection get(Map map);
  526. protected abstract Object iteratorNext(Map.Entry entry);
  527. public void clear() {
  528. if (fast) {
  529. synchronized (FastTreeMap.this) {
  530. map = new TreeMap();
  531. }
  532. } else {
  533. synchronized (map) {
  534. get(map).clear();
  535. }
  536. }
  537. }
  538. public boolean remove(Object o) {
  539. if (fast) {
  540. synchronized (FastTreeMap.this) {
  541. TreeMap temp = (TreeMap) map.clone();
  542. boolean r = get(temp).remove(o);
  543. map = temp;
  544. return r;
  545. }
  546. } else {
  547. synchronized (map) {
  548. return get(map).remove(o);
  549. }
  550. }
  551. }
  552. public boolean removeAll(Collection o) {
  553. if (fast) {
  554. synchronized (FastTreeMap.this) {
  555. TreeMap temp = (TreeMap) map.clone();
  556. boolean r = get(temp).removeAll(o);
  557. map = temp;
  558. return r;
  559. }
  560. } else {
  561. synchronized (map) {
  562. return get(map).removeAll(o);
  563. }
  564. }
  565. }
  566. public boolean retainAll(Collection o) {
  567. if (fast) {
  568. synchronized (FastTreeMap.this) {
  569. TreeMap temp = (TreeMap) map.clone();
  570. boolean r = get(temp).retainAll(o);
  571. map = temp;
  572. return r;
  573. }
  574. } else {
  575. synchronized (map) {
  576. return get(map).retainAll(o);
  577. }
  578. }
  579. }
  580. public int size() {
  581. if (fast) {
  582. return get(map).size();
  583. } else {
  584. synchronized (map) {
  585. return get(map).size();
  586. }
  587. }
  588. }
  589. public boolean isEmpty() {
  590. if (fast) {
  591. return get(map).isEmpty();
  592. } else {
  593. synchronized (map) {
  594. return get(map).isEmpty();
  595. }
  596. }
  597. }
  598. public boolean contains(Object o) {
  599. if (fast) {
  600. return get(map).contains(o);
  601. } else {
  602. synchronized (map) {
  603. return get(map).contains(o);
  604. }
  605. }
  606. }
  607. public boolean containsAll(Collection o) {
  608. if (fast) {
  609. return get(map).containsAll(o);
  610. } else {
  611. synchronized (map) {
  612. return get(map).containsAll(o);
  613. }
  614. }
  615. }
  616. public Object[] toArray(Object[] o) {
  617. if (fast) {
  618. return get(map).toArray(o);
  619. } else {
  620. synchronized (map) {
  621. return get(map).toArray(o);
  622. }
  623. }
  624. }
  625. public Object[] toArray() {
  626. if (fast) {
  627. return get(map).toArray();
  628. } else {
  629. synchronized (map) {
  630. return get(map).toArray();
  631. }
  632. }
  633. }
  634. public boolean equals(Object o) {
  635. if (o == this) return true;
  636. if (fast) {
  637. return get(map).equals(o);
  638. } else {
  639. synchronized (map) {
  640. return get(map).equals(o);
  641. }
  642. }
  643. }
  644. public int hashCode() {
  645. if (fast) {
  646. return get(map).hashCode();
  647. } else {
  648. synchronized (map) {
  649. return get(map).hashCode();
  650. }
  651. }
  652. }
  653. public boolean add(Object o) {
  654. throw new UnsupportedOperationException();
  655. }
  656. public boolean addAll(Collection c) {
  657. throw new UnsupportedOperationException();
  658. }
  659. public Iterator iterator() {
  660. return new CollectionViewIterator();
  661. }
  662. private class CollectionViewIterator implements Iterator {
  663. private Map expected;
  664. private Map.Entry lastReturned = null;
  665. private Iterator iterator;
  666. public CollectionViewIterator() {
  667. this.expected = map;
  668. this.iterator = expected.entrySet().iterator();
  669. }
  670. public boolean hasNext() {
  671. if (expected != map) {
  672. throw new ConcurrentModificationException();
  673. }
  674. return iterator.hasNext();
  675. }
  676. public Object next() {
  677. if (expected != map) {
  678. throw new ConcurrentModificationException();
  679. }
  680. lastReturned = (Map.Entry)iterator.next();
  681. return iteratorNext(lastReturned);
  682. }
  683. public void remove() {
  684. if (lastReturned == null) {
  685. throw new IllegalStateException();
  686. }
  687. if (fast) {
  688. synchronized (FastTreeMap.this) {
  689. if (expected != map) {
  690. throw new ConcurrentModificationException();
  691. }
  692. FastTreeMap.this.remove(lastReturned.getKey());
  693. lastReturned = null;
  694. expected = map;
  695. }
  696. } else {
  697. iterator.remove();
  698. lastReturned = null;
  699. }
  700. }
  701. }
  702. }
  703. /**
  704. * Set implementation over the keys of the FastTreeMap
  705. */
  706. private class KeySet extends CollectionView implements Set {
  707. protected Collection get(Map map) {
  708. return map.keySet();
  709. }
  710. protected Object iteratorNext(Map.Entry entry) {
  711. return entry.getKey();
  712. }
  713. }
  714. /**
  715. * Collection implementation over the values of the FastTreeMap
  716. */
  717. private class Values extends CollectionView {
  718. protected Collection get(Map map) {
  719. return map.values();
  720. }
  721. protected Object iteratorNext(Map.Entry entry) {
  722. return entry.getValue();
  723. }
  724. }
  725. /**
  726. * Set implementation over the entries of the FastTreeMap
  727. */
  728. private class EntrySet extends CollectionView implements Set {
  729. protected Collection get(Map map) {
  730. return map.entrySet();
  731. }
  732. protected Object iteratorNext(Map.Entry entry) {
  733. return entry;
  734. }
  735. }
  736. }