1. /*
  2. * Copyright 2003-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.map;
  17. import java.io.IOException;
  18. import java.io.ObjectInputStream;
  19. import java.io.ObjectOutputStream;
  20. import java.io.Serializable;
  21. import java.util.AbstractCollection;
  22. import java.util.AbstractSet;
  23. import java.util.Collection;
  24. import java.util.Iterator;
  25. import java.util.Map;
  26. import java.util.NoSuchElementException;
  27. import java.util.Set;
  28. import org.apache.commons.collections.IterableMap;
  29. import org.apache.commons.collections.MapIterator;
  30. import org.apache.commons.collections.ResettableIterator;
  31. import org.apache.commons.collections.iterators.EmptyIterator;
  32. import org.apache.commons.collections.iterators.EmptyMapIterator;
  33. /**
  34. * A <code>Map</code> implementation that stores data in simple fields until
  35. * the size is greater than 3.
  36. * <p>
  37. * This map is designed for performance and can outstrip HashMap.
  38. * It also has good garbage collection characteristics.
  39. * <ul>
  40. * <li>Optimised for operation at size 3 or less.
  41. * <li>Still works well once size 3 exceeded.
  42. * <li>Gets at size 3 or less are about 0-10% faster than HashMap,
  43. * <li>Puts at size 3 or less are over 4 times faster than HashMap.
  44. * <li>Performance 5% slower than HashMap once size 3 exceeded once.
  45. * </ul>
  46. * The design uses two distinct modes of operation - flat and delegate.
  47. * While the map is size 3 or less, operations map straight onto fields using
  48. * switch statements. Once size 4 is reached, the map switches to delegate mode
  49. * and only switches back when cleared. In delegate mode, all operations are
  50. * forwarded straight to a HashMap resulting in the 5% performance loss.
  51. * <p>
  52. * The performance gains on puts are due to not needing to create a Map Entry
  53. * object. This is a large saving not only in performance but in garbage collection.
  54. * <p>
  55. * Whilst in flat mode this map is also easy for the garbage collector to dispatch.
  56. * This is because it contains no complex objects or arrays which slow the progress.
  57. * <p>
  58. * Do not use <code>Flat3Map</code> if the size is likely to grow beyond 3.
  59. *
  60. * @since Commons Collections 3.0
  61. * @version $Revision: 1.18 $ $Date: 2004/05/26 21:56:05 $
  62. *
  63. * @author Stephen Colebourne
  64. */
  65. public class Flat3Map implements IterableMap, Serializable, Cloneable {
  66. /** Serialization version */
  67. private static final long serialVersionUID = -6701087419741928296L;
  68. /** The size of the map, used while in flat mode */
  69. private transient int size;
  70. /** Hash, used while in flat mode */
  71. private transient int hash1;
  72. /** Hash, used while in flat mode */
  73. private transient int hash2;
  74. /** Hash, used while in flat mode */
  75. private transient int hash3;
  76. /** Key, used while in flat mode */
  77. private transient Object key1;
  78. /** Key, used while in flat mode */
  79. private transient Object key2;
  80. /** Key, used while in flat mode */
  81. private transient Object key3;
  82. /** Value, used while in flat mode */
  83. private transient Object value1;
  84. /** Value, used while in flat mode */
  85. private transient Object value2;
  86. /** Value, used while in flat mode */
  87. private transient Object value3;
  88. /** Map, used while in delegate mode */
  89. private transient AbstractHashedMap delegateMap;
  90. /**
  91. * Constructor.
  92. */
  93. public Flat3Map() {
  94. super();
  95. }
  96. /**
  97. * Constructor copying elements from another map.
  98. *
  99. * @param map the map to copy
  100. * @throws NullPointerException if the map is null
  101. */
  102. public Flat3Map(Map map) {
  103. super();
  104. putAll(map);
  105. }
  106. //-----------------------------------------------------------------------
  107. /**
  108. * Gets the value mapped to the key specified.
  109. *
  110. * @param key the key
  111. * @return the mapped value, null if no match
  112. */
  113. public Object get(Object key) {
  114. if (delegateMap != null) {
  115. return delegateMap.get(key);
  116. }
  117. if (key == null) {
  118. switch (size) {
  119. // drop through
  120. case 3:
  121. if (key3 == null) return value3;
  122. case 2:
  123. if (key2 == null) return value2;
  124. case 1:
  125. if (key1 == null) return value1;
  126. }
  127. } else {
  128. if (size > 0) {
  129. int hashCode = key.hashCode();
  130. switch (size) {
  131. // drop through
  132. case 3:
  133. if (hash3 == hashCode && key.equals(key3)) return value3;
  134. case 2:
  135. if (hash2 == hashCode && key.equals(key2)) return value2;
  136. case 1:
  137. if (hash1 == hashCode && key.equals(key1)) return value1;
  138. }
  139. }
  140. }
  141. return null;
  142. }
  143. /**
  144. * Gets the size of the map.
  145. *
  146. * @return the size
  147. */
  148. public int size() {
  149. if (delegateMap != null) {
  150. return delegateMap.size();
  151. }
  152. return size;
  153. }
  154. /**
  155. * Checks whether the map is currently empty.
  156. *
  157. * @return true if the map is currently size zero
  158. */
  159. public boolean isEmpty() {
  160. return (size() == 0);
  161. }
  162. //-----------------------------------------------------------------------
  163. /**
  164. * Checks whether the map contains the specified key.
  165. *
  166. * @param key the key to search for
  167. * @return true if the map contains the key
  168. */
  169. public boolean containsKey(Object key) {
  170. if (delegateMap != null) {
  171. return delegateMap.containsKey(key);
  172. }
  173. if (key == null) {
  174. switch (size) { // drop through
  175. case 3:
  176. if (key3 == null) return true;
  177. case 2:
  178. if (key2 == null) return true;
  179. case 1:
  180. if (key1 == null) return true;
  181. }
  182. } else {
  183. if (size > 0) {
  184. int hashCode = key.hashCode();
  185. switch (size) { // drop through
  186. case 3:
  187. if (hash3 == hashCode && key.equals(key3)) return true;
  188. case 2:
  189. if (hash2 == hashCode && key.equals(key2)) return true;
  190. case 1:
  191. if (hash1 == hashCode && key.equals(key1)) return true;
  192. }
  193. }
  194. }
  195. return false;
  196. }
  197. /**
  198. * Checks whether the map contains the specified value.
  199. *
  200. * @param value the value to search for
  201. * @return true if the map contains the key
  202. */
  203. public boolean containsValue(Object value) {
  204. if (delegateMap != null) {
  205. return delegateMap.containsValue(value);
  206. }
  207. if (value == null) { // drop through
  208. switch (size) {
  209. case 3:
  210. if (value3 == null) return true;
  211. case 2:
  212. if (value2 == null) return true;
  213. case 1:
  214. if (value1 == null) return true;
  215. }
  216. } else {
  217. switch (size) { // drop through
  218. case 3:
  219. if (value.equals(value3)) return true;
  220. case 2:
  221. if (value.equals(value2)) return true;
  222. case 1:
  223. if (value.equals(value1)) return true;
  224. }
  225. }
  226. return false;
  227. }
  228. //-----------------------------------------------------------------------
  229. /**
  230. * Puts a key-value mapping into this map.
  231. *
  232. * @param key the key to add
  233. * @param value the value to add
  234. * @return the value previously mapped to this key, null if none
  235. */
  236. public Object put(Object key, Object value) {
  237. if (delegateMap != null) {
  238. return delegateMap.put(key, value);
  239. }
  240. // change existing mapping
  241. if (key == null) {
  242. switch (size) { // drop through
  243. case 3:
  244. if (key3 == null) {
  245. Object old = value3;
  246. value3 = value;
  247. return old;
  248. }
  249. case 2:
  250. if (key2 == null) {
  251. Object old = value2;
  252. value2 = value;
  253. return old;
  254. }
  255. case 1:
  256. if (key1 == null) {
  257. Object old = value1;
  258. value1 = value;
  259. return old;
  260. }
  261. }
  262. } else {
  263. if (size > 0) {
  264. int hashCode = key.hashCode();
  265. switch (size) { // drop through
  266. case 3:
  267. if (hash3 == hashCode && key.equals(key3)) {
  268. Object old = value3;
  269. value3 = value;
  270. return old;
  271. }
  272. case 2:
  273. if (hash2 == hashCode && key.equals(key2)) {
  274. Object old = value2;
  275. value2 = value;
  276. return old;
  277. }
  278. case 1:
  279. if (hash1 == hashCode && key.equals(key1)) {
  280. Object old = value1;
  281. value1 = value;
  282. return old;
  283. }
  284. }
  285. }
  286. }
  287. // add new mapping
  288. switch (size) {
  289. default:
  290. convertToMap();
  291. delegateMap.put(key, value);
  292. return null;
  293. case 2:
  294. hash3 = (key == null ? 0 : key.hashCode());
  295. key3 = key;
  296. value3 = value;
  297. break;
  298. case 1:
  299. hash2 = (key == null ? 0 : key.hashCode());
  300. key2 = key;
  301. value2 = value;
  302. break;
  303. case 0:
  304. hash1 = (key == null ? 0 : key.hashCode());
  305. key1 = key;
  306. value1 = value;
  307. break;
  308. }
  309. size++;
  310. return null;
  311. }
  312. /**
  313. * Puts all the values from the specified map into this map.
  314. *
  315. * @param map the map to add
  316. * @throws NullPointerException if the map is null
  317. */
  318. public void putAll(Map map) {
  319. int size = map.size();
  320. if (size == 0) {
  321. return;
  322. }
  323. if (delegateMap != null) {
  324. delegateMap.putAll(map);
  325. return;
  326. }
  327. if (size < 4) {
  328. for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
  329. Map.Entry entry = (Map.Entry) it.next();
  330. put(entry.getKey(), entry.getValue());
  331. }
  332. } else {
  333. convertToMap();
  334. delegateMap.putAll(map);
  335. }
  336. }
  337. /**
  338. * Converts the flat map data to a map.
  339. */
  340. private void convertToMap() {
  341. delegateMap = createDelegateMap();
  342. switch (size) { // drop through
  343. case 3:
  344. delegateMap.put(key3, value3);
  345. case 2:
  346. delegateMap.put(key2, value2);
  347. case 1:
  348. delegateMap.put(key1, value1);
  349. }
  350. size = 0;
  351. hash1 = hash2 = hash3 = 0;
  352. key1 = key2 = key3 = null;
  353. value1 = value2 = value3 = null;
  354. }
  355. /**
  356. * Create an instance of the map used for storage when in delegation mode.
  357. * <p>
  358. * This can be overridden by subclasses to provide a different map implementation.
  359. * Not every AbstractHashedMap is suitable, identity and reference based maps
  360. * would be poor choices.
  361. *
  362. * @return a new AbstractHashedMap or subclass
  363. * @since Commons Collections 3.1
  364. */
  365. protected AbstractHashedMap createDelegateMap() {
  366. return new HashedMap();
  367. }
  368. /**
  369. * Removes the specified mapping from this map.
  370. *
  371. * @param key the mapping to remove
  372. * @return the value mapped to the removed key, null if key not in map
  373. */
  374. public Object remove(Object key) {
  375. if (delegateMap != null) {
  376. return delegateMap.remove(key);
  377. }
  378. if (size == 0) {
  379. return null;
  380. }
  381. if (key == null) {
  382. switch (size) { // drop through
  383. case 3:
  384. if (key3 == null) {
  385. Object old = value3;
  386. hash3 = 0;
  387. key3 = null;
  388. value3 = null;
  389. size = 2;
  390. return old;
  391. }
  392. if (key2 == null) {
  393. Object old = value3;
  394. hash2 = hash3;
  395. key2 = key3;
  396. value2 = value3;
  397. hash3 = 0;
  398. key3 = null;
  399. value3 = null;
  400. size = 2;
  401. return old;
  402. }
  403. if (key1 == null) {
  404. Object old = value3;
  405. hash1 = hash3;
  406. key1 = key3;
  407. value1 = value3;
  408. hash3 = 0;
  409. key3 = null;
  410. value3 = null;
  411. size = 2;
  412. return old;
  413. }
  414. return null;
  415. case 2:
  416. if (key2 == null) {
  417. Object old = value2;
  418. hash2 = 0;
  419. key2 = null;
  420. value2 = null;
  421. size = 1;
  422. return old;
  423. }
  424. if (key1 == null) {
  425. Object old = value2;
  426. hash1 = hash2;
  427. key1 = key2;
  428. value1 = value2;
  429. hash2 = 0;
  430. key2 = null;
  431. value2 = null;
  432. size = 1;
  433. return old;
  434. }
  435. return null;
  436. case 1:
  437. if (key1 == null) {
  438. Object old = value1;
  439. hash1 = 0;
  440. key1 = null;
  441. value1 = null;
  442. size = 0;
  443. return old;
  444. }
  445. }
  446. } else {
  447. if (size > 0) {
  448. int hashCode = key.hashCode();
  449. switch (size) { // drop through
  450. case 3:
  451. if (hash3 == hashCode && key.equals(key3)) {
  452. Object old = value3;
  453. hash3 = 0;
  454. key3 = null;
  455. value3 = null;
  456. size = 2;
  457. return old;
  458. }
  459. if (hash2 == hashCode && key.equals(key2)) {
  460. Object old = value3;
  461. hash2 = hash3;
  462. key2 = key3;
  463. value2 = value3;
  464. hash3 = 0;
  465. key3 = null;
  466. value3 = null;
  467. size = 2;
  468. return old;
  469. }
  470. if (hash1 == hashCode && key.equals(key1)) {
  471. Object old = value3;
  472. hash1 = hash3;
  473. key1 = key3;
  474. value1 = value3;
  475. hash3 = 0;
  476. key3 = null;
  477. value3 = null;
  478. size = 2;
  479. return old;
  480. }
  481. return null;
  482. case 2:
  483. if (hash2 == hashCode && key.equals(key2)) {
  484. Object old = value2;
  485. hash2 = 0;
  486. key2 = null;
  487. value2 = null;
  488. size = 1;
  489. return old;
  490. }
  491. if (hash1 == hashCode && key.equals(key1)) {
  492. Object old = value2;
  493. hash1 = hash2;
  494. key1 = key2;
  495. value1 = value2;
  496. hash2 = 0;
  497. key2 = null;
  498. value2 = null;
  499. size = 1;
  500. return old;
  501. }
  502. return null;
  503. case 1:
  504. if (hash1 == hashCode && key.equals(key1)) {
  505. Object old = value1;
  506. hash1 = 0;
  507. key1 = null;
  508. value1 = null;
  509. size = 0;
  510. return old;
  511. }
  512. }
  513. }
  514. }
  515. return null;
  516. }
  517. /**
  518. * Clears the map, resetting the size to zero and nullifying references
  519. * to avoid garbage collection issues.
  520. */
  521. public void clear() {
  522. if (delegateMap != null) {
  523. delegateMap.clear(); // should aid gc
  524. delegateMap = null; // switch back to flat mode
  525. } else {
  526. size = 0;
  527. hash1 = hash2 = hash3 = 0;
  528. key1 = key2 = key3 = null;
  529. value1 = value2 = value3 = null;
  530. }
  531. }
  532. //-----------------------------------------------------------------------
  533. /**
  534. * Gets an iterator over the map.
  535. * Changes made to the iterator affect this map.
  536. * <p>
  537. * A MapIterator returns the keys in the map. It also provides convenient
  538. * methods to get the key and value, and set the value.
  539. * It avoids the need to create an entrySet/keySet/values object.
  540. * It also avoids creating the Map Entry object.
  541. *
  542. * @return the map iterator
  543. */
  544. public MapIterator mapIterator() {
  545. if (delegateMap != null) {
  546. return delegateMap.mapIterator();
  547. }
  548. if (size == 0) {
  549. return EmptyMapIterator.INSTANCE;
  550. }
  551. return new FlatMapIterator(this);
  552. }
  553. /**
  554. * FlatMapIterator
  555. */
  556. static class FlatMapIterator implements MapIterator, ResettableIterator {
  557. private final Flat3Map parent;
  558. private int nextIndex = 0;
  559. private boolean canRemove = false;
  560. FlatMapIterator(Flat3Map parent) {
  561. super();
  562. this.parent = parent;
  563. }
  564. public boolean hasNext() {
  565. return (nextIndex < parent.size);
  566. }
  567. public Object next() {
  568. if (hasNext() == false) {
  569. throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
  570. }
  571. canRemove = true;
  572. nextIndex++;
  573. return getKey();
  574. }
  575. public void remove() {
  576. if (canRemove == false) {
  577. throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
  578. }
  579. parent.remove(getKey());
  580. nextIndex--;
  581. canRemove = false;
  582. }
  583. public Object getKey() {
  584. if (canRemove == false) {
  585. throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
  586. }
  587. switch (nextIndex) {
  588. case 3:
  589. return parent.key3;
  590. case 2:
  591. return parent.key2;
  592. case 1:
  593. return parent.key1;
  594. }
  595. throw new IllegalStateException("Invalid map index");
  596. }
  597. public Object getValue() {
  598. if (canRemove == false) {
  599. throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
  600. }
  601. switch (nextIndex) {
  602. case 3:
  603. return parent.value3;
  604. case 2:
  605. return parent.value2;
  606. case 1:
  607. return parent.value1;
  608. }
  609. throw new IllegalStateException("Invalid map index");
  610. }
  611. public Object setValue(Object value) {
  612. if (canRemove == false) {
  613. throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
  614. }
  615. Object old = getValue();
  616. switch (nextIndex) {
  617. case 3:
  618. parent.value3 = value;
  619. case 2:
  620. parent.value2 = value;
  621. case 1:
  622. parent.value1 = value;
  623. }
  624. return old;
  625. }
  626. public void reset() {
  627. nextIndex = 0;
  628. canRemove = false;
  629. }
  630. public String toString() {
  631. if (canRemove) {
  632. return "Iterator[" + getKey() + "=" + getValue() + "]";
  633. } else {
  634. return "Iterator[]";
  635. }
  636. }
  637. }
  638. /**
  639. * Gets the entrySet view of the map.
  640. * Changes made to the view affect this map.
  641. * The Map Entry is not an independent object and changes as the
  642. * iterator progresses.
  643. * To simply iterate through the entries, use {@link #mapIterator()}.
  644. *
  645. * @return the entrySet view
  646. */
  647. public Set entrySet() {
  648. if (delegateMap != null) {
  649. return delegateMap.entrySet();
  650. }
  651. return new EntrySet(this);
  652. }
  653. /**
  654. * EntrySet
  655. */
  656. static class EntrySet extends AbstractSet {
  657. private final Flat3Map parent;
  658. EntrySet(Flat3Map parent) {
  659. super();
  660. this.parent = parent;
  661. }
  662. public int size() {
  663. return parent.size();
  664. }
  665. public void clear() {
  666. parent.clear();
  667. }
  668. public boolean remove(Object obj) {
  669. if (obj instanceof Map.Entry == false) {
  670. return false;
  671. }
  672. Map.Entry entry = (Map.Entry) obj;
  673. Object key = entry.getKey();
  674. boolean result = parent.containsKey(key);
  675. parent.remove(key);
  676. return result;
  677. }
  678. public Iterator iterator() {
  679. if (parent.delegateMap != null) {
  680. return parent.delegateMap.entrySet().iterator();
  681. }
  682. if (parent.size() == 0) {
  683. return EmptyIterator.INSTANCE;
  684. }
  685. return new EntrySetIterator(parent);
  686. }
  687. }
  688. /**
  689. * EntrySetIterator and MapEntry
  690. */
  691. static class EntrySetIterator implements Iterator, Map.Entry {
  692. private final Flat3Map parent;
  693. private int nextIndex = 0;
  694. private boolean canRemove = false;
  695. EntrySetIterator(Flat3Map parent) {
  696. super();
  697. this.parent = parent;
  698. }
  699. public boolean hasNext() {
  700. return (nextIndex < parent.size);
  701. }
  702. public Object next() {
  703. if (hasNext() == false) {
  704. throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
  705. }
  706. canRemove = true;
  707. nextIndex++;
  708. return this;
  709. }
  710. public void remove() {
  711. if (canRemove == false) {
  712. throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
  713. }
  714. parent.remove(getKey());
  715. nextIndex--;
  716. canRemove = false;
  717. }
  718. public Object getKey() {
  719. if (canRemove == false) {
  720. throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
  721. }
  722. switch (nextIndex) {
  723. case 3:
  724. return parent.key3;
  725. case 2:
  726. return parent.key2;
  727. case 1:
  728. return parent.key1;
  729. }
  730. throw new IllegalStateException("Invalid map index");
  731. }
  732. public Object getValue() {
  733. if (canRemove == false) {
  734. throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
  735. }
  736. switch (nextIndex) {
  737. case 3:
  738. return parent.value3;
  739. case 2:
  740. return parent.value2;
  741. case 1:
  742. return parent.value1;
  743. }
  744. throw new IllegalStateException("Invalid map index");
  745. }
  746. public Object setValue(Object value) {
  747. if (canRemove == false) {
  748. throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
  749. }
  750. Object old = getValue();
  751. switch (nextIndex) {
  752. case 3:
  753. parent.value3 = value;
  754. case 2:
  755. parent.value2 = value;
  756. case 1:
  757. parent.value1 = value;
  758. }
  759. return old;
  760. }
  761. public boolean equals(Object obj) {
  762. if (canRemove == false) {
  763. return false;
  764. }
  765. if (obj instanceof Map.Entry == false) {
  766. return false;
  767. }
  768. Map.Entry other = (Map.Entry) obj;
  769. Object key = getKey();
  770. Object value = getValue();
  771. return (key == null ? other.getKey() == null : key.equals(other.getKey())) &&
  772. (value == null ? other.getValue() == null : value.equals(other.getValue()));
  773. }
  774. public int hashCode() {
  775. if (canRemove == false) {
  776. return 0;
  777. }
  778. Object key = getKey();
  779. Object value = getValue();
  780. return (key == null ? 0 : key.hashCode()) ^
  781. (value == null ? 0 : value.hashCode());
  782. }
  783. public String toString() {
  784. if (canRemove) {
  785. return getKey() + "=" + getValue();
  786. } else {
  787. return "";
  788. }
  789. }
  790. }
  791. /**
  792. * Gets the keySet view of the map.
  793. * Changes made to the view affect this map.
  794. * To simply iterate through the keys, use {@link #mapIterator()}.
  795. *
  796. * @return the keySet view
  797. */
  798. public Set keySet() {
  799. if (delegateMap != null) {
  800. return delegateMap.keySet();
  801. }
  802. return new KeySet(this);
  803. }
  804. /**
  805. * KeySet
  806. */
  807. static class KeySet extends AbstractSet {
  808. private final Flat3Map parent;
  809. KeySet(Flat3Map parent) {
  810. super();
  811. this.parent = parent;
  812. }
  813. public int size() {
  814. return parent.size();
  815. }
  816. public void clear() {
  817. parent.clear();
  818. }
  819. public boolean contains(Object key) {
  820. return parent.containsKey(key);
  821. }
  822. public boolean remove(Object key) {
  823. boolean result = parent.containsKey(key);
  824. parent.remove(key);
  825. return result;
  826. }
  827. public Iterator iterator() {
  828. if (parent.delegateMap != null) {
  829. return parent.delegateMap.keySet().iterator();
  830. }
  831. if (parent.size() == 0) {
  832. return EmptyIterator.INSTANCE;
  833. }
  834. return new KeySetIterator(parent);
  835. }
  836. }
  837. /**
  838. * KeySetIterator
  839. */
  840. static class KeySetIterator extends EntrySetIterator {
  841. KeySetIterator(Flat3Map parent) {
  842. super(parent);
  843. }
  844. public Object next() {
  845. super.next();
  846. return getKey();
  847. }
  848. }
  849. /**
  850. * Gets the values view of the map.
  851. * Changes made to the view affect this map.
  852. * To simply iterate through the values, use {@link #mapIterator()}.
  853. *
  854. * @return the values view
  855. */
  856. public Collection values() {
  857. if (delegateMap != null) {
  858. return delegateMap.values();
  859. }
  860. return new Values(this);
  861. }
  862. /**
  863. * Values
  864. */
  865. static class Values extends AbstractCollection {
  866. private final Flat3Map parent;
  867. Values(Flat3Map parent) {
  868. super();
  869. this.parent = parent;
  870. }
  871. public int size() {
  872. return parent.size();
  873. }
  874. public void clear() {
  875. parent.clear();
  876. }
  877. public boolean contains(Object value) {
  878. return parent.containsValue(value);
  879. }
  880. public Iterator iterator() {
  881. if (parent.delegateMap != null) {
  882. return parent.delegateMap.values().iterator();
  883. }
  884. if (parent.size() == 0) {
  885. return EmptyIterator.INSTANCE;
  886. }
  887. return new ValuesIterator(parent);
  888. }
  889. }
  890. /**
  891. * ValuesIterator
  892. */
  893. static class ValuesIterator extends EntrySetIterator {
  894. ValuesIterator(Flat3Map parent) {
  895. super(parent);
  896. }
  897. public Object next() {
  898. super.next();
  899. return getValue();
  900. }
  901. }
  902. //-----------------------------------------------------------------------
  903. /**
  904. * Write the map out using a custom routine.
  905. */
  906. private void writeObject(ObjectOutputStream out) throws IOException {
  907. out.defaultWriteObject();
  908. out.writeInt(size());
  909. for (MapIterator it = mapIterator(); it.hasNext();) {
  910. out.writeObject(it.next()); // key
  911. out.writeObject(it.getValue()); // value
  912. }
  913. }
  914. /**
  915. * Read the map in using a custom routine.
  916. */
  917. private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
  918. in.defaultReadObject();
  919. int count = in.readInt();
  920. if (count > 3) {
  921. delegateMap = createDelegateMap();
  922. }
  923. for (int i = count; i > 0; i--) {
  924. put(in.readObject(), in.readObject());
  925. }
  926. }
  927. //-----------------------------------------------------------------------
  928. /**
  929. * Clones the map without cloning the keys or values.
  930. *
  931. * @return a shallow clone
  932. * @since Commons Collections 3.1
  933. */
  934. public Object clone() {
  935. try {
  936. Flat3Map cloned = (Flat3Map) super.clone();
  937. if (cloned.delegateMap != null) {
  938. cloned.delegateMap = (HashedMap) cloned.delegateMap.clone();
  939. }
  940. return cloned;
  941. } catch (CloneNotSupportedException ex) {
  942. throw new InternalError();
  943. }
  944. }
  945. /**
  946. * Compares this map with another.
  947. *
  948. * @param obj the object to compare to
  949. * @return true if equal
  950. */
  951. public boolean equals(Object obj) {
  952. if (obj == this) {
  953. return true;
  954. }
  955. if (delegateMap != null) {
  956. return delegateMap.equals(obj);
  957. }
  958. if (obj instanceof Map == false) {
  959. return false;
  960. }
  961. Map other = (Map) obj;
  962. if (size != other.size()) {
  963. return false;
  964. }
  965. if (size > 0) {
  966. Object otherValue = null;
  967. switch (size) { // drop through
  968. case 3:
  969. if (other.containsKey(key3) == false) {
  970. otherValue = other.get(key3);
  971. if (value3 == null ? otherValue != null : !value3.equals(otherValue)) {
  972. return false;
  973. }
  974. }
  975. case 2:
  976. if (other.containsKey(key2) == false) {
  977. otherValue = other.get(key2);
  978. if (value2 == null ? otherValue != null : !value2.equals(otherValue)) {
  979. return false;
  980. }
  981. }
  982. case 1:
  983. if (other.containsKey(key1) == false) {
  984. otherValue = other.get(key1);
  985. if (value1 == null ? otherValue != null : !value1.equals(otherValue)) {
  986. return false;
  987. }
  988. }
  989. }
  990. }
  991. return true;
  992. }
  993. /**
  994. * Gets the standard Map hashCode.
  995. *
  996. * @return the hash code defined in the Map interface
  997. */
  998. public int hashCode() {
  999. if (delegateMap != null) {
  1000. return delegateMap.hashCode();
  1001. }
  1002. int total = 0;
  1003. switch (size) { // drop through
  1004. case 3:
  1005. total += (hash3 ^ (value3 == null ? 0 : value3.hashCode()));
  1006. case 2:
  1007. total += (hash2 ^ (value2 == null ? 0 : value2.hashCode()));
  1008. case 1:
  1009. total += (hash1 ^ (value1 == null ? 0 : value1.hashCode()));
  1010. }
  1011. return total;
  1012. }
  1013. /**
  1014. * Gets the map as a String.
  1015. *
  1016. * @return a string version of the map
  1017. */
  1018. public String toString() {
  1019. if (delegateMap != null) {
  1020. return delegateMap.toString();
  1021. }
  1022. if (size == 0) {
  1023. return "{}";
  1024. }
  1025. StringBuffer buf = new StringBuffer(128);
  1026. buf.append('{');
  1027. switch (size) { // drop through
  1028. case 3:
  1029. buf.append((key3 == this ? "(this Map)" : key3));
  1030. buf.append('=');
  1031. buf.append((value3 == this ? "(this Map)" : value3));
  1032. buf.append(',');
  1033. case 2:
  1034. buf.append((key2 == this ? "(this Map)" : key2));
  1035. buf.append('=');
  1036. buf.append((value2 == this ? "(this Map)" : value2));
  1037. buf.append(',');
  1038. case 1:
  1039. buf.append((key1 == this ? "(this Map)" : key1));
  1040. buf.append('=');
  1041. buf.append((value1 == this ? "(this Map)" : value1));
  1042. }
  1043. buf.append('}');
  1044. return buf.toString();
  1045. }
  1046. }