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 */ 017 package org.apache.commons.collections.map; 018 019 import java.io.IOException; 020 import java.io.ObjectInputStream; 021 import java.io.ObjectOutputStream; 022 import java.io.Serializable; 023 import java.util.AbstractList; 024 import java.util.Collection; 025 import java.util.Iterator; 026 import java.util.List; 027 import java.util.ListIterator; 028 import java.util.Map; 029 030 import org.apache.commons.collections.iterators.UnmodifiableIterator; 031 import org.apache.commons.collections.iterators.UnmodifiableListIterator; 032 import org.apache.commons.collections.list.UnmodifiableList; 033 034 /** 035 * A <code>Map</code> implementation that maintains the order of the entries. 036 * In this implementation order is maintained by original insertion. 037 * <p> 038 * This implementation improves on the JDK1.4 LinkedHashMap by adding the 039 * {@link org.apache.commons.collections.MapIterator MapIterator} 040 * functionality, additional convenience methods and allowing 041 * bidirectional iteration. It also implements <code>OrderedMap</code>. 042 * In addition, non-interface methods are provided to access the map by index. 043 * <p> 044 * The <code>orderedMapIterator()</code> method provides direct access to a 045 * bidirectional iterator. The iterators from the other views can also be cast 046 * to <code>OrderedIterator</code> if required. 047 * <p> 048 * All the available iterators can be reset back to the start by casting to 049 * <code>ResettableIterator</code> and calling <code>reset()</code>. 050 * <p> 051 * The implementation is also designed to be subclassed, with lots of useful 052 * methods exposed. 053 * <p> 054 * <strong>Note that LinkedMap is not synchronized and is not thread-safe.</strong> 055 * If you wish to use this map from multiple threads concurrently, you must use 056 * appropriate synchronization. The simplest approach is to wrap this map 057 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 058 * exceptions when accessed by concurrent threads without synchronization. 059 * 060 * @since Commons Collections 3.0 061 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 062 * 063 * @author Stephen Colebourne 064 */ 065 public class LinkedMap 066 extends AbstractLinkedMap implements Serializable, Cloneable { 067 068 /** Serialisation version */ 069 private static final long serialVersionUID = 9077234323521161066L; 070 071 /** 072 * Constructs a new empty map with default size and load factor. 073 */ 074 public LinkedMap() { 075 super(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD); 076 } 077 078 /** 079 * Constructs a new, empty map with the specified initial capacity. 080 * 081 * @param initialCapacity the initial capacity 082 * @throws IllegalArgumentException if the initial capacity is less than one 083 */ 084 public LinkedMap(int initialCapacity) { 085 super(initialCapacity); 086 } 087 088 /** 089 * Constructs a new, empty map with the specified initial capacity and 090 * load factor. 091 * 092 * @param initialCapacity the initial capacity 093 * @param loadFactor the load factor 094 * @throws IllegalArgumentException if the initial capacity is less than one 095 * @throws IllegalArgumentException if the load factor is less than zero 096 */ 097 public LinkedMap(int initialCapacity, float loadFactor) { 098 super(initialCapacity, loadFactor); 099 } 100 101 /** 102 * Constructor copying elements from another map. 103 * 104 * @param map the map to copy 105 * @throws NullPointerException if the map is null 106 */ 107 public LinkedMap(Map map) { 108 super(map); 109 } 110 111 //----------------------------------------------------------------------- 112 /** 113 * Clones the map without cloning the keys or values. 114 * 115 * @return a shallow clone 116 */ 117 public Object clone() { 118 return super.clone(); 119 } 120 121 /** 122 * Write the map out using a custom routine. 123 */ 124 private void writeObject(ObjectOutputStream out) throws IOException { 125 out.defaultWriteObject(); 126 doWriteObject(out); 127 } 128 129 /** 130 * Read the map in using a custom routine. 131 */ 132 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 133 in.defaultReadObject(); 134 doReadObject(in); 135 } 136 137 //----------------------------------------------------------------------- 138 /** 139 * Gets the key at the specified index. 140 * 141 * @param index the index to retrieve 142 * @return the key at the specified index 143 * @throws IndexOutOfBoundsException if the index is invalid 144 */ 145 public Object get(int index) { 146 return getEntry(index).getKey(); 147 } 148 149 /** 150 * Gets the value at the specified index. 151 * 152 * @param index the index to retrieve 153 * @return the key at the specified index 154 * @throws IndexOutOfBoundsException if the index is invalid 155 */ 156 public Object getValue(int index) { 157 return getEntry(index).getValue(); 158 } 159 160 /** 161 * Gets the index of the specified key. 162 * 163 * @param key the key to find the index of 164 * @return the index, or -1 if not found 165 */ 166 public int indexOf(Object key) { 167 key = convertKey(key); 168 int i = 0; 169 for (LinkEntry entry = header.after; entry != header; entry = entry.after, i++) { 170 if (isEqualKey(key, entry.key)) { 171 return i; 172 } 173 } 174 return -1; 175 } 176 177 /** 178 * Removes the element at the specified index. 179 * 180 * @param index the index of the object to remove 181 * @return the previous value corresponding the <code>key</code>, 182 * or <code>null</code> if none existed 183 * @throws IndexOutOfBoundsException if the index is invalid 184 */ 185 public Object remove(int index) { 186 return remove(get(index)); 187 } 188 189 /** 190 * Gets an unmodifiable List view of the keys. 191 * <p> 192 * The returned list is unmodifiable because changes to the values of 193 * the list (using {@link java.util.ListIterator#set(Object)}) will 194 * effectively remove the value from the list and reinsert that value at 195 * the end of the list, which is an unexpected side effect of changing the 196 * value of a list. This occurs because changing the key, changes when the 197 * mapping is added to the map and thus where it appears in the list. 198 * <p> 199 * An alternative to this method is to use {@link #keySet()}. 200 * 201 * @see #keySet() 202 * @return The ordered list of keys. 203 */ 204 public List asList() { 205 return new LinkedMapList(this); 206 } 207 208 /** 209 * List view of map. 210 */ 211 static class LinkedMapList extends AbstractList { 212 213 final LinkedMap parent; 214 215 LinkedMapList(LinkedMap parent) { 216 this.parent = parent; 217 } 218 219 public int size() { 220 return parent.size(); 221 } 222 223 public Object get(int index) { 224 return parent.get(index); 225 } 226 227 public boolean contains(Object obj) { 228 return parent.containsKey(obj); 229 } 230 231 public int indexOf(Object obj) { 232 return parent.indexOf(obj); 233 } 234 235 public int lastIndexOf(Object obj) { 236 return parent.indexOf(obj); 237 } 238 239 public boolean containsAll(Collection coll) { 240 return parent.keySet().containsAll(coll); 241 } 242 243 public Object remove(int index) { 244 throw new UnsupportedOperationException(); 245 } 246 247 public boolean remove(Object obj) { 248 throw new UnsupportedOperationException(); 249 } 250 251 public boolean removeAll(Collection coll) { 252 throw new UnsupportedOperationException(); 253 } 254 255 public boolean retainAll(Collection coll) { 256 throw new UnsupportedOperationException(); 257 } 258 259 public void clear() { 260 throw new UnsupportedOperationException(); 261 } 262 263 public Object[] toArray() { 264 return parent.keySet().toArray(); 265 } 266 267 public Object[] toArray(Object[] array) { 268 return parent.keySet().toArray(array); 269 } 270 271 public Iterator iterator() { 272 return UnmodifiableIterator.decorate(parent.keySet().iterator()); 273 } 274 275 public ListIterator listIterator() { 276 return UnmodifiableListIterator.decorate(super.listIterator()); 277 } 278 279 public ListIterator listIterator(int fromIndex) { 280 return UnmodifiableListIterator.decorate(super.listIterator(fromIndex)); 281 } 282 283 public List subList(int fromIndexInclusive, int toIndexExclusive) { 284 return UnmodifiableList.decorate(super.subList(fromIndexInclusive, toIndexExclusive)); 285 } 286 } 287 288 }