1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.map;
18
19 import java.util.ConcurrentModificationException;
20 import java.util.Iterator;
21 import java.util.Map;
22 import java.util.NoSuchElementException;
23
24 import org.apache.commons.collections.MapIterator;
25 import org.apache.commons.collections.OrderedIterator;
26 import org.apache.commons.collections.OrderedMap;
27 import org.apache.commons.collections.OrderedMapIterator;
28 import org.apache.commons.collections.ResettableIterator;
29 import org.apache.commons.collections.iterators.EmptyOrderedIterator;
30 import org.apache.commons.collections.iterators.EmptyOrderedMapIterator;
31
32 /**
33 * An abstract implementation of a hash-based map that links entries to create an
34 * ordered map and which provides numerous points for subclasses to override.
35 * <p>
36 * This class implements all the features necessary for a subclass linked
37 * hash-based map. Key-value entries are stored in instances of the
38 * <code>LinkEntry</code> class which can be overridden and replaced.
39 * The iterators can similarly be replaced, without the need to replace the KeySet,
40 * EntrySet and Values view classes.
41 * <p>
42 * Overridable methods are provided to change the default hashing behaviour, and
43 * to change how entries are added to and removed from the map. Hopefully, all you
44 * need for unusual subclasses is here.
45 * <p>
46 * This implementation maintains order by original insertion, but subclasses
47 * may work differently. The <code>OrderedMap</code> interface is implemented
48 * to provide access to bidirectional iteration and extra convenience methods.
49 * <p>
50 * The <code>orderedMapIterator()</code> method provides direct access to a
51 * bidirectional iterator. The iterators from the other views can also be cast
52 * to <code>OrderedIterator</code> if required.
53 * <p>
54 * All the available iterators can be reset back to the start by casting to
55 * <code>ResettableIterator</code> and calling <code>reset()</code>.
56 * <p>
57 * The implementation is also designed to be subclassed, with lots of useful
58 * methods exposed.
59 *
60 * @since Commons Collections 3.0
61 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
62 *
63 * @author java util LinkedHashMap
64 * @author Stephen Colebourne
65 */
66 public class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap {
67
68 /** Header in the linked list */
69 protected transient LinkEntry header;
70
71 /**
72 * Constructor only used in deserialization, do not use otherwise.
73 */
74 protected AbstractLinkedMap() {
75 super();
76 }
77
78 /**
79 * Constructor which performs no validation on the passed in parameters.
80 *
81 * @param initialCapacity the initial capacity, must be a power of two
82 * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f
83 * @param threshold the threshold, must be sensible
84 */
85 protected AbstractLinkedMap(int initialCapacity, float loadFactor, int threshold) {
86 super(initialCapacity, loadFactor, threshold);
87 }
88
89 /**
90 * Constructs a new, empty map with the specified initial capacity.
91 *
92 * @param initialCapacity the initial capacity
93 * @throws IllegalArgumentException if the initial capacity is less than one
94 */
95 protected AbstractLinkedMap(int initialCapacity) {
96 super(initialCapacity);
97 }
98
99 /**
100 * Constructs a new, empty map with the specified initial capacity and
101 * load factor.
102 *
103 * @param initialCapacity the initial capacity
104 * @param loadFactor the load factor
105 * @throws IllegalArgumentException if the initial capacity is less than one
106 * @throws IllegalArgumentException if the load factor is less than zero
107 */
108 protected AbstractLinkedMap(int initialCapacity, float loadFactor) {
109 super(initialCapacity, loadFactor);
110 }
111
112 /**
113 * Constructor copying elements from another map.
114 *
115 * @param map the map to copy
116 * @throws NullPointerException if the map is null
117 */
118 protected AbstractLinkedMap(Map map) {
119 super(map);
120 }
121
122 /**
123 * Initialise this subclass during construction.
124 * <p>
125 * NOTE: As from v3.2 this method calls
126 * {@link #createEntry(HashEntry, int, Object, Object)} to create
127 * the map entry object.
128 */
129 protected void init() {
130 header = (LinkEntry) createEntry(null, -1, null, null);
131 header.before = header.after = header;
132 }
133
134 //-----------------------------------------------------------------------
135 /**
136 * Checks whether the map contains the specified value.
137 *
138 * @param value the value to search for
139 * @return true if the map contains the value
140 */
141 public boolean containsValue(Object value) {
142 // override uses faster iterator
143 if (value == null) {
144 for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
145 if (entry.getValue() == null) {
146 return true;
147 }
148 }
149 } else {
150 for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
151 if (isEqualValue(value, entry.getValue())) {
152 return true;
153 }
154 }
155 }
156 return false;
157 }
158
159 /**
160 * Clears the map, resetting the size to zero and nullifying references
161 * to avoid garbage collection issues.
162 */
163 public void clear() {
164 // override to reset the linked list
165 super.clear();
166 header.before = header.after = header;
167 }
168
169 //-----------------------------------------------------------------------
170 /**
171 * Gets the first key in the map, which is the most recently inserted.
172 *
173 * @return the most recently inserted key
174 */
175 public Object firstKey() {
176 if (size == 0) {
177 throw new NoSuchElementException("Map is empty");
178 }
179 return header.after.getKey();
180 }
181
182 /**
183 * Gets the last key in the map, which is the first inserted.
184 *
185 * @return the eldest key
186 */
187 public Object lastKey() {
188 if (size == 0) {
189 throw new NoSuchElementException("Map is empty");
190 }
191 return header.before.getKey();
192 }
193
194 /**
195 * Gets the next key in sequence.
196 *
197 * @param key the key to get after
198 * @return the next key
199 */
200 public Object nextKey(Object key) {
201 LinkEntry entry = (LinkEntry) getEntry(key);
202 return (entry == null || entry.after == header ? null : entry.after.getKey());
203 }
204
205 /**
206 * Gets the previous key in sequence.
207 *
208 * @param key the key to get before
209 * @return the previous key
210 */
211 public Object previousKey(Object key) {
212 LinkEntry entry = (LinkEntry) getEntry(key);
213 return (entry == null || entry.before == header ? null : entry.before.getKey());
214 }
215
216 //-----------------------------------------------------------------------
217 /**
218 * Gets the key at the specified index.
219 *
220 * @param index the index to retrieve
221 * @return the key at the specified index
222 * @throws IndexOutOfBoundsException if the index is invalid
223 */
224 protected LinkEntry getEntry(int index) {
225 if (index < 0) {
226 throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
227 }
228 if (index >= size) {
229 throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
230 }
231 LinkEntry entry;
232 if (index < (size / 2)) {
233 // Search forwards
234 entry = header.after;
235 for (int currentIndex = 0; currentIndex < index; currentIndex++) {
236 entry = entry.after;
237 }
238 } else {
239 // Search backwards
240 entry = header;
241 for (int currentIndex = size; currentIndex > index; currentIndex--) {
242 entry = entry.before;
243 }
244 }
245 return entry;
246 }
247
248 /**
249 * Adds an entry into this map, maintaining insertion order.
250 * <p>
251 * This implementation adds the entry to the data storage table and
252 * to the end of the linked list.
253 *
254 * @param entry the entry to add
255 * @param hashIndex the index into the data array to store at
256 */
257 protected void addEntry(HashEntry entry, int hashIndex) {
258 LinkEntry link = (LinkEntry) entry;
259 link.after = header;
260 link.before = header.before;
261 header.before.after = link;
262 header.before = link;
263 data[hashIndex] = entry;
264 }
265
266 /**
267 * Creates an entry to store the data.
268 * <p>
269 * This implementation creates a new LinkEntry instance.
270 *
271 * @param next the next entry in sequence
272 * @param hashCode the hash code to use
273 * @param key the key to store
274 * @param value the value to store
275 * @return the newly created entry
276 */
277 protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
278 return new LinkEntry(next, hashCode, key, value);
279 }
280
281 /**
282 * Removes an entry from the map and the linked list.
283 * <p>
284 * This implementation removes the entry from the linked list chain, then
285 * calls the superclass implementation.
286 *
287 * @param entry the entry to remove
288 * @param hashIndex the index into the data structure
289 * @param previous the previous entry in the chain
290 */
291 protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
292 LinkEntry link = (LinkEntry) entry;
293 link.before.after = link.after;
294 link.after.before = link.before;
295 link.after = null;
296 link.before = null;
297 super.removeEntry(entry, hashIndex, previous);
298 }
299
300 //-----------------------------------------------------------------------
301 /**
302 * Gets the <code>before</code> field from a <code>LinkEntry</code>.
303 * Used in subclasses that have no visibility of the field.
304 *
305 * @param entry the entry to query, must not be null
306 * @return the <code>before</code> field of the entry
307 * @throws NullPointerException if the entry is null
308 * @since Commons Collections 3.1
309 */
310 protected LinkEntry entryBefore(LinkEntry entry) {
311 return entry.before;
312 }
313
314 /**
315 * Gets the <code>after</code> field from a <code>LinkEntry</code>.
316 * Used in subclasses that have no visibility of the field.
317 *
318 * @param entry the entry to query, must not be null
319 * @return the <code>after</code> field of the entry
320 * @throws NullPointerException if the entry is null
321 * @since Commons Collections 3.1
322 */
323 protected LinkEntry entryAfter(LinkEntry entry) {
324 return entry.after;
325 }
326
327 //-----------------------------------------------------------------------
328 /**
329 * Gets an iterator over the map.
330 * Changes made to the iterator affect this map.
331 * <p>
332 * A MapIterator returns the keys in the map. It also provides convenient
333 * methods to get the key and value, and set the value.
334 * It avoids the need to create an entrySet/keySet/values object.
335 *
336 * @return the map iterator
337 */
338 public MapIterator mapIterator() {
339 if (size == 0) {
340 return EmptyOrderedMapIterator.INSTANCE;
341 }
342 return new LinkMapIterator(this);
343 }
344
345 /**
346 * Gets a bidirectional iterator over the map.
347 * Changes made to the iterator affect this map.
348 * <p>
349 * A MapIterator returns the keys in the map. It also provides convenient
350 * methods to get the key and value, and set the value.
351 * It avoids the need to create an entrySet/keySet/values object.
352 *
353 * @return the map iterator
354 */
355 public OrderedMapIterator orderedMapIterator() {
356 if (size == 0) {
357 return EmptyOrderedMapIterator.INSTANCE;
358 }
359 return new LinkMapIterator(this);
360 }
361
362 /**
363 * MapIterator implementation.
364 */
365 protected static class LinkMapIterator extends LinkIterator implements OrderedMapIterator {
366
367 protected LinkMapIterator(AbstractLinkedMap parent) {
368 super(parent);
369 }
370
371 public Object next() {
372 return super.nextEntry().getKey();
373 }
374
375 public Object previous() {
376 return super.previousEntry().getKey();
377 }
378
379 public Object getKey() {
380 HashEntry current = currentEntry();
381 if (current == null) {
382 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
383 }
384 return current.getKey();
385 }
386
387 public Object getValue() {
388 HashEntry current = currentEntry();
389 if (current == null) {
390 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
391 }
392 return current.getValue();
393 }
394
395 public Object setValue(Object value) {
396 HashEntry current = currentEntry();
397 if (current == null) {
398 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
399 }
400 return current.setValue(value);
401 }
402 }
403
404 //-----------------------------------------------------------------------
405 /**
406 * Creates an entry set iterator.
407 * Subclasses can override this to return iterators with different properties.
408 *
409 * @return the entrySet iterator
410 */
411 protected Iterator createEntrySetIterator() {
412 if (size() == 0) {
413 return EmptyOrderedIterator.INSTANCE;
414 }
415 return new EntrySetIterator(this);
416 }
417
418 /**
419 * EntrySet iterator.
420 */
421 protected static class EntrySetIterator extends LinkIterator {
422
423 protected EntrySetIterator(AbstractLinkedMap parent) {
424 super(parent);
425 }
426
427 public Object next() {
428 return super.nextEntry();
429 }
430
431 public Object previous() {
432 return super.previousEntry();
433 }
434 }
435
436 //-----------------------------------------------------------------------
437 /**
438 * Creates a key set iterator.
439 * Subclasses can override this to return iterators with different properties.
440 *
441 * @return the keySet iterator
442 */
443 protected Iterator createKeySetIterator() {
444 if (size() == 0) {
445 return EmptyOrderedIterator.INSTANCE;
446 }
447 return new KeySetIterator(this);
448 }
449
450 /**
451 * KeySet iterator.
452 */
453 protected static class KeySetIterator extends EntrySetIterator {
454
455 protected KeySetIterator(AbstractLinkedMap parent) {
456 super(parent);
457 }
458
459 public Object next() {
460 return super.nextEntry().getKey();
461 }
462
463 public Object previous() {
464 return super.previousEntry().getKey();
465 }
466 }
467
468 //-----------------------------------------------------------------------
469 /**
470 * Creates a values iterator.
471 * Subclasses can override this to return iterators with different properties.
472 *
473 * @return the values iterator
474 */
475 protected Iterator createValuesIterator() {
476 if (size() == 0) {
477 return EmptyOrderedIterator.INSTANCE;
478 }
479 return new ValuesIterator(this);
480 }
481
482 /**
483 * Values iterator.
484 */
485 protected static class ValuesIterator extends LinkIterator {
486
487 protected ValuesIterator(AbstractLinkedMap parent) {
488 super(parent);
489 }
490
491 public Object next() {
492 return super.nextEntry().getValue();
493 }
494
495 public Object previous() {
496 return super.previousEntry().getValue();
497 }
498 }
499
500 //-----------------------------------------------------------------------
501 /**
502 * LinkEntry that stores the data.
503 * <p>
504 * If you subclass <code>AbstractLinkedMap</code> but not <code>LinkEntry</code>
505 * then you will not be able to access the protected fields.
506 * The <code>entryXxx()</code> methods on <code>AbstractLinkedMap</code> exist
507 * to provide the necessary access.
508 */
509 protected static class LinkEntry extends HashEntry {
510 /** The entry before this one in the order */
511 protected LinkEntry before;
512 /** The entry after this one in the order */
513 protected LinkEntry after;
514
515 /**
516 * Constructs a new entry.
517 *
518 * @param next the next entry in the hash bucket sequence
519 * @param hashCode the hash code
520 * @param key the key
521 * @param value the value
522 */
523 protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
524 super(next, hashCode, key, value);
525 }
526 }
527
528 /**
529 * Base Iterator that iterates in link order.
530 */
531 protected static abstract class LinkIterator
532 implements OrderedIterator, ResettableIterator {
533
534 /** The parent map */
535 protected final AbstractLinkedMap parent;
536 /** The current (last returned) entry */
537 protected LinkEntry last;
538 /** The next entry */
539 protected LinkEntry next;
540 /** The modification count expected */
541 protected int expectedModCount;
542
543 protected LinkIterator(AbstractLinkedMap parent) {
544 super();
545 this.parent = parent;
546 this.next = parent.header.after;
547 this.expectedModCount = parent.modCount;
548 }
549
550 public boolean hasNext() {
551 return (next != parent.header);
552 }
553
554 public boolean hasPrevious() {
555 return (next.before != parent.header);
556 }
557
558 protected LinkEntry nextEntry() {
559 if (parent.modCount != expectedModCount) {
560 throw new ConcurrentModificationException();
561 }
562 if (next == parent.header) {
563 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
564 }
565 last = next;
566 next = next.after;
567 return last;
568 }
569
570 protected LinkEntry previousEntry() {
571 if (parent.modCount != expectedModCount) {
572 throw new ConcurrentModificationException();
573 }
574 LinkEntry previous = next.before;
575 if (previous == parent.header) {
576 throw new NoSuchElementException(AbstractHashedMap.NO_PREVIOUS_ENTRY);
577 }
578 next = previous;
579 last = previous;
580 return last;
581 }
582
583 protected LinkEntry currentEntry() {
584 return last;
585 }
586
587 public void remove() {
588 if (last == null) {
589 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
590 }
591 if (parent.modCount != expectedModCount) {
592 throw new ConcurrentModificationException();
593 }
594 parent.remove(last.getKey());
595 last = null;
596 expectedModCount = parent.modCount;
597 }
598
599 public void reset() {
600 last = null;
601 next = parent.header.after;
602 }
603
604 public String toString() {
605 if (last != null) {
606 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
607 } else {
608 return "Iterator[]";
609 }
610 }
611 }
612
613 }