001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.map; 018 019import java.io.IOException; 020import java.io.ObjectInputStream; 021import java.io.ObjectOutputStream; 022import java.io.Serializable; 023import java.util.AbstractList; 024import java.util.Collection; 025import java.util.Iterator; 026import java.util.List; 027import java.util.ListIterator; 028import java.util.Map; 029import java.util.function.Predicate; 030 031import org.apache.commons.collections4.CollectionUtils; 032import org.apache.commons.collections4.iterators.UnmodifiableIterator; 033import org.apache.commons.collections4.iterators.UnmodifiableListIterator; 034import org.apache.commons.collections4.list.UnmodifiableList; 035 036/** 037 * A {@code Map} implementation that maintains the order of the entries. 038 * In this implementation order is maintained by original insertion. 039 * <p> 040 * This implementation improves on the JDK1.4 LinkedHashMap by adding the 041 * {@link org.apache.commons.collections4.MapIterator MapIterator} 042 * functionality, additional convenience methods and allowing 043 * bidirectional iteration. It also implements {@code OrderedMap}. 044 * In addition, non-interface methods are provided to access the map by index. 045 * </p> 046 * <p> 047 * The {@code orderedMapIterator()} method provides direct access to a 048 * bidirectional iterator. The iterators from the other views can also be cast 049 * to {@code OrderedIterator} if required. 050 * </p> 051 * <p> 052 * All the available iterators can be reset back to the start by casting to 053 * {@code ResettableIterator} and calling {@code reset()}. 054 * </p> 055 * <p> 056 * The implementation is also designed to be subclassed, with lots of useful 057 * methods exposed. 058 * </p> 059 * <p> 060 * <strong>Note that LinkedMap is not synchronized and is not thread-safe.</strong> 061 * If you wish to use this map from multiple threads concurrently, you must use 062 * appropriate synchronization. The simplest approach is to wrap this map 063 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 064 * exceptions when accessed by concurrent threads without synchronization. 065 * </p> 066 * 067 * @param <K> the type of the keys in this map 068 * @param <V> the type of the values in this map 069 * @since 3.0 070 */ 071public class LinkedMap<K, V> extends AbstractLinkedMap<K, V> implements Serializable, Cloneable { 072 073 /** 074 * List view of map. 075 */ 076 static class LinkedMapList<K> extends AbstractList<K> { 077 078 private final LinkedMap<K, ?> parent; 079 080 LinkedMapList(final LinkedMap<K, ?> parent) { 081 this.parent = parent; 082 } 083 084 @Override 085 public void clear() { 086 throw new UnsupportedOperationException(); 087 } 088 089 @Override 090 public boolean contains(final Object obj) { 091 return parent.containsKey(obj); 092 } 093 094 @Override 095 public boolean containsAll(final Collection<?> coll) { 096 return parent.keySet().containsAll(coll); 097 } 098 099 @Override 100 public K get(final int index) { 101 return parent.get(index); 102 } 103 104 @Override 105 public int indexOf(final Object obj) { 106 return parent.indexOf(obj); 107 } 108 109 @Override 110 public Iterator<K> iterator() { 111 return UnmodifiableIterator.unmodifiableIterator(parent.keySet().iterator()); 112 } 113 114 @Override 115 public int lastIndexOf(final Object obj) { 116 return parent.indexOf(obj); 117 } 118 119 @Override 120 public ListIterator<K> listIterator() { 121 return UnmodifiableListIterator.unmodifiableListIterator(super.listIterator()); 122 } 123 124 @Override 125 public ListIterator<K> listIterator(final int fromIndex) { 126 return UnmodifiableListIterator.unmodifiableListIterator(super.listIterator(fromIndex)); 127 } 128 129 @Override 130 public K remove(final int index) { 131 throw new UnsupportedOperationException(); 132 } 133 134 @Override 135 public boolean remove(final Object obj) { 136 throw new UnsupportedOperationException(); 137 } 138 139 @Override 140 public boolean removeAll(final Collection<?> coll) { 141 throw new UnsupportedOperationException(); 142 } 143 144 /** 145 * @since 4.4 146 */ 147 @Override 148 public boolean removeIf(final Predicate<? super K> filter) { 149 throw new UnsupportedOperationException(); 150 } 151 152 @Override 153 public boolean retainAll(final Collection<?> coll) { 154 throw new UnsupportedOperationException(); 155 } 156 157 @Override 158 public int size() { 159 return parent.size(); 160 } 161 162 @Override 163 public List<K> subList(final int fromIndexInclusive, final int toIndexExclusive) { 164 return UnmodifiableList.unmodifiableList(super.subList(fromIndexInclusive, toIndexExclusive)); 165 } 166 167 @Override 168 public Object[] toArray() { 169 return parent.keySet().toArray(); 170 } 171 172 @Override 173 public <T> T[] toArray(final T[] array) { 174 return parent.keySet().toArray(array); 175 } 176 } 177 178 /** Serialisation version */ 179 private static final long serialVersionUID = 9077234323521161066L; 180 181 /** 182 * Constructs a new empty map with default size and load factor. 183 */ 184 public LinkedMap() { 185 super(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD); 186 } 187 188 /** 189 * Constructs a new, empty map with the specified initial capacity. 190 * 191 * @param initialCapacity the initial capacity 192 * @throws IllegalArgumentException if the initial capacity is negative 193 */ 194 public LinkedMap(final int initialCapacity) { 195 super(initialCapacity); 196 } 197 198 /** 199 * Constructs a new, empty map with the specified initial capacity and 200 * load factor. 201 * 202 * @param initialCapacity the initial capacity 203 * @param loadFactor the load factor 204 * @throws IllegalArgumentException if the initial capacity is negative 205 * @throws IllegalArgumentException if the load factor is less than zero 206 */ 207 public LinkedMap(final int initialCapacity, final float loadFactor) { 208 super(initialCapacity, loadFactor); 209 } 210 211 /** 212 * Constructor copying elements from another map. 213 * 214 * @param map the map to copy 215 * @throws NullPointerException if the map is null 216 */ 217 public LinkedMap(final Map<? extends K, ? extends V> map) { 218 super(map); 219 } 220 221 /** 222 * Gets an unmodifiable List view of the keys. 223 * <p> 224 * The returned list is unmodifiable because changes to the values of 225 * the list (using {@link java.util.ListIterator#set(Object)}) will 226 * effectively remove the value from the list and reinsert that value at 227 * the end of the list, which is an unexpected side effect of changing the 228 * value of a list. This occurs because changing the key, changes when the 229 * mapping is added to the map and thus where it appears in the list. 230 * <p> 231 * An alternative to this method is to use {@link #keySet()}. 232 * 233 * @see #keySet() 234 * @return The ordered list of keys. 235 */ 236 public List<K> asList() { 237 return new LinkedMapList<>(this); 238 } 239 240 /** 241 * Clones the map without cloning the keys or values. 242 * 243 * @return a shallow clone 244 */ 245 @Override 246 public LinkedMap<K, V> clone() { 247 return (LinkedMap<K, V>) super.clone(); 248 } 249 250 /** 251 * Gets the key at the specified index. 252 * 253 * @param index the index to retrieve 254 * @return the key at the specified index 255 * @throws IndexOutOfBoundsException if the index is invalid 256 */ 257 public K get(final int index) { 258 return getEntry(index).getKey(); 259 } 260 261 /** 262 * Gets the value at the specified index. 263 * 264 * @param index the index to retrieve 265 * @return the value at the specified index 266 * @throws IndexOutOfBoundsException if the index is invalid 267 */ 268 public V getValue(final int index) { 269 return getEntry(index).getValue(); 270 } 271 272 /** 273 * Gets the index of the specified key. 274 * 275 * @param key the key to find the index of 276 * @return the index, or -1 if not found 277 */ 278 public int indexOf(Object key) { 279 key = convertKey(key); 280 int i = 0; 281 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after, i++) { 282 if (isEqualKey(key, entry.key)) { 283 return i; 284 } 285 } 286 return CollectionUtils.INDEX_NOT_FOUND; 287 } 288 289 /** 290 * Read the map in using a custom routine. 291 * 292 * @param in the input stream 293 * @throws IOException if an error occurs while reading from the stream 294 * @throws ClassNotFoundException if an object read from the stream can not be loaded 295 */ 296 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 297 in.defaultReadObject(); 298 doReadObject(in); 299 } 300 301 /** 302 * Removes the element at the specified index. 303 * 304 * @param index the index of the object to remove 305 * @return the previous value corresponding the {@code key}, 306 * or {@code null} if none existed 307 * @throws IndexOutOfBoundsException if the index is invalid 308 */ 309 public V remove(final int index) { 310 return remove(get(index)); 311 } 312 313 /** 314 * Write the map out using a custom routine. 315 * 316 * @param out the output stream 317 * @throws IOException if an error occurs while writing to the stream 318 */ 319 private void writeObject(final ObjectOutputStream out) throws IOException { 320 out.defaultWriteObject(); 321 doWriteObject(out); 322 } 323 324}