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.AbstractList;
  22. import java.util.Collection;
  23. import java.util.Iterator;
  24. import java.util.List;
  25. import java.util.ListIterator;
  26. import java.util.Map;
  27. import org.apache.commons.collections.iterators.UnmodifiableIterator;
  28. import org.apache.commons.collections.iterators.UnmodifiableListIterator;
  29. import org.apache.commons.collections.list.UnmodifiableList;
  30. /**
  31. * A <code>Map</code> implementation that maintains the order of the entries.
  32. * In this implementation order is maintained by original insertion.
  33. * <p>
  34. * This implementation improves on the JDK1.4 LinkedHashMap by adding the
  35. * {@link org.apache.commons.collections.MapIterator MapIterator}
  36. * functionality, additional convenience methods and allowing
  37. * bidirectional iteration. It also implements <code>OrderedMap</code>.
  38. * In addition, non-interface methods are provided to access the map by index.
  39. * <p>
  40. * The <code>orderedMapIterator()</code> method provides direct access to a
  41. * bidirectional iterator. The iterators from the other views can also be cast
  42. * to <code>OrderedIterator</code> if required.
  43. * <p>
  44. * All the available iterators can be reset back to the start by casting to
  45. * <code>ResettableIterator</code> and calling <code>reset()</code>.
  46. * <p>
  47. * The implementation is also designed to be subclassed, with lots of useful
  48. * methods exposed.
  49. *
  50. * @since Commons Collections 3.0
  51. * @version $Revision: 1.9 $ $Date: 2004/02/18 01:13:19 $
  52. *
  53. * @author Stephen Colebourne
  54. */
  55. public class LinkedMap
  56. extends AbstractLinkedMap implements Serializable, Cloneable {
  57. /** Serialisation version */
  58. private static final long serialVersionUID = 9077234323521161066L;
  59. /**
  60. * Constructs a new empty map with default size and load factor.
  61. */
  62. public LinkedMap() {
  63. super(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD);
  64. }
  65. /**
  66. * Constructs a new, empty map with the specified initial capacity.
  67. *
  68. * @param initialCapacity the initial capacity
  69. * @throws IllegalArgumentException if the initial capacity is less than one
  70. */
  71. public LinkedMap(int initialCapacity) {
  72. super(initialCapacity);
  73. }
  74. /**
  75. * Constructs a new, empty map with the specified initial capacity and
  76. * load factor.
  77. *
  78. * @param initialCapacity the initial capacity
  79. * @param loadFactor the load factor
  80. * @throws IllegalArgumentException if the initial capacity is less than one
  81. * @throws IllegalArgumentException if the load factor is less than zero
  82. */
  83. public LinkedMap(int initialCapacity, float loadFactor) {
  84. super(initialCapacity, loadFactor);
  85. }
  86. /**
  87. * Constructor copying elements from another map.
  88. *
  89. * @param map the map to copy
  90. * @throws NullPointerException if the map is null
  91. */
  92. public LinkedMap(Map map) {
  93. super(map);
  94. }
  95. //-----------------------------------------------------------------------
  96. /**
  97. * Clones the map without cloning the keys or values.
  98. *
  99. * @return a shallow clone
  100. */
  101. public Object clone() {
  102. return super.clone();
  103. }
  104. /**
  105. * Write the map out using a custom routine.
  106. */
  107. private void writeObject(ObjectOutputStream out) throws IOException {
  108. out.defaultWriteObject();
  109. doWriteObject(out);
  110. }
  111. /**
  112. * Read the map in using a custom routine.
  113. */
  114. private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
  115. in.defaultReadObject();
  116. doReadObject(in);
  117. }
  118. //-----------------------------------------------------------------------
  119. /**
  120. * Gets the key at the specified index.
  121. *
  122. * @param index the index to retrieve
  123. * @return the key at the specified index
  124. * @throws IndexOutOfBoundsException if the index is invalid
  125. */
  126. public Object get(int index) {
  127. return getEntry(index).getKey();
  128. }
  129. /**
  130. * Gets the value at the specified index.
  131. *
  132. * @param index the index to retrieve
  133. * @return the key at the specified index
  134. * @throws IndexOutOfBoundsException if the index is invalid
  135. */
  136. public Object getValue(int index) {
  137. return getEntry(index).getValue();
  138. }
  139. /**
  140. * Gets the index of the specified key.
  141. *
  142. * @param key the key to find the index of
  143. * @return the index, or -1 if not found
  144. */
  145. public int indexOf(Object key) {
  146. key = convertKey(key);
  147. int i = 0;
  148. for (LinkEntry entry = header.after; entry != header; entry = entry.after, i++) {
  149. if (isEqualKey(key, entry.key)) {
  150. return i;
  151. }
  152. }
  153. return -1;
  154. }
  155. /**
  156. * Removes the element at the specified index.
  157. *
  158. * @param index the index of the object to remove
  159. * @return the previous value corresponding the <code>key</code>,
  160. * or <code>null</code> if none existed
  161. * @throws IndexOutOfBoundsException if the index is invalid
  162. */
  163. public Object remove(int index) {
  164. return remove(get(index));
  165. }
  166. /**
  167. * Gets an unmodifiable List view of the keys.
  168. * <p>
  169. * The returned list is unmodifiable because changes to the values of
  170. * the list (using {@link java.util.ListIterator#set(Object)}) will
  171. * effectively remove the value from the list and reinsert that value at
  172. * the end of the list, which is an unexpected side effect of changing the
  173. * value of a list. This occurs because changing the key, changes when the
  174. * mapping is added to the map and thus where it appears in the list.
  175. * <p>
  176. * An alternative to this method is to use {@link #keySet()}.
  177. *
  178. * @see #keySet()
  179. * @return The ordered list of keys.
  180. */
  181. public List asList() {
  182. return new LinkedMapList(this);
  183. }
  184. /**
  185. * List view of map.
  186. */
  187. static class LinkedMapList extends AbstractList {
  188. final LinkedMap parent;
  189. LinkedMapList(LinkedMap parent) {
  190. this.parent = parent;
  191. }
  192. public int size() {
  193. return parent.size();
  194. }
  195. public Object get(int index) {
  196. return parent.get(index);
  197. }
  198. public boolean contains(Object obj) {
  199. return parent.containsKey(obj);
  200. }
  201. public int indexOf(Object obj) {
  202. return parent.indexOf(obj);
  203. }
  204. public int lastIndexOf(Object obj) {
  205. return parent.indexOf(obj);
  206. }
  207. public boolean containsAll(Collection coll) {
  208. return parent.keySet().containsAll(coll);
  209. }
  210. public Object remove(int index) {
  211. throw new UnsupportedOperationException();
  212. }
  213. public boolean remove(Object obj) {
  214. throw new UnsupportedOperationException();
  215. }
  216. public boolean removeAll(Collection coll) {
  217. throw new UnsupportedOperationException();
  218. }
  219. public boolean retainAll(Collection coll) {
  220. throw new UnsupportedOperationException();
  221. }
  222. public void clear() {
  223. throw new UnsupportedOperationException();
  224. }
  225. public Object[] toArray() {
  226. return parent.keySet().toArray();
  227. }
  228. public Object[] toArray(Object[] array) {
  229. return parent.keySet().toArray(array);
  230. }
  231. public Iterator iterator() {
  232. return UnmodifiableIterator.decorate(parent.keySet().iterator());
  233. }
  234. public ListIterator listIterator() {
  235. return UnmodifiableListIterator.decorate(super.listIterator());
  236. }
  237. public ListIterator listIterator(int fromIndex) {
  238. return UnmodifiableListIterator.decorate(super.listIterator(fromIndex));
  239. }
  240. public List subList(int fromIndexInclusive, int toIndexExclusive) {
  241. return UnmodifiableList.decorate(super.subList(fromIndexInclusive, toIndexExclusive));
  242. }
  243. }
  244. }