1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.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.collections4.OrderedIterator;
25 import org.apache.commons.collections4.OrderedMap;
26 import org.apache.commons.collections4.OrderedMapIterator;
27 import org.apache.commons.collections4.ResettableIterator;
28 import org.apache.commons.collections4.iterators.EmptyOrderedIterator;
29 import org.apache.commons.collections4.iterators.EmptyOrderedMapIterator;
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> {
70
71
72
73
74 protected static class EntrySetIterator<K, V> extends LinkIterator<K, V> implements
75 OrderedIterator<Map.Entry<K, V>>, ResettableIterator<Map.Entry<K, V>> {
76
77 protected EntrySetIterator(final AbstractLinkedMap<K, V> parent) {
78 super(parent);
79 }
80
81 @Override
82 public Map.Entry<K, V> next() {
83 return super.nextEntry();
84 }
85
86 @Override
87 public Map.Entry<K, V> previous() {
88 return super.previousEntry();
89 }
90 }
91
92
93
94
95 protected static class KeySetIterator<K> extends LinkIterator<K, Object> implements
96 OrderedIterator<K>, ResettableIterator<K> {
97
98 @SuppressWarnings("unchecked")
99 protected KeySetIterator(final AbstractLinkedMap<K, ?> parent) {
100 super((AbstractLinkedMap<K, Object>) parent);
101 }
102
103 @Override
104 public K next() {
105 return super.nextEntry().getKey();
106 }
107
108 @Override
109 public K previous() {
110 return super.previousEntry().getKey();
111 }
112 }
113
114
115
116
117
118
119
120
121
122 protected static class LinkEntry<K, V> extends HashEntry<K, V> {
123
124 protected LinkEntry<K, V> before;
125
126 protected LinkEntry<K, V> after;
127
128
129
130
131
132
133
134
135
136 protected LinkEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
137 super(next, hashCode, key, value);
138 }
139 }
140
141
142
143
144 protected abstract static class LinkIterator<K, V> {
145
146
147 protected final AbstractLinkedMap<K, V> parent;
148
149 protected LinkEntry<K, V> last;
150
151 protected LinkEntry<K, V> next;
152
153 protected int expectedModCount;
154
155 protected LinkIterator(final AbstractLinkedMap<K, V> parent) {
156 this.parent = parent;
157 this.next = parent.header.after;
158 this.expectedModCount = parent.modCount;
159 }
160
161 protected LinkEntry<K, V> currentEntry() {
162 return last;
163 }
164
165 public boolean hasNext() {
166 return next != parent.header;
167 }
168
169 public boolean hasPrevious() {
170 return next.before != parent.header;
171 }
172
173 protected LinkEntry<K, V> nextEntry() {
174 if (parent.modCount != expectedModCount) {
175 throw new ConcurrentModificationException();
176 }
177 if (next == parent.header) {
178 throw new NoSuchElementException(NO_NEXT_ENTRY);
179 }
180 last = next;
181 next = next.after;
182 return last;
183 }
184
185 protected LinkEntry<K, V> previousEntry() {
186 if (parent.modCount != expectedModCount) {
187 throw new ConcurrentModificationException();
188 }
189 final LinkEntry<K, V> previous = next.before;
190 if (previous == parent.header) {
191 throw new NoSuchElementException(NO_PREVIOUS_ENTRY);
192 }
193 next = previous;
194 last = previous;
195 return last;
196 }
197
198 public void remove() {
199 if (last == null) {
200 throw new IllegalStateException(REMOVE_INVALID);
201 }
202 if (parent.modCount != expectedModCount) {
203 throw new ConcurrentModificationException();
204 }
205 parent.remove(last.getKey());
206 last = null;
207 expectedModCount = parent.modCount;
208 }
209
210 public void reset() {
211 last = null;
212 next = parent.header.after;
213 }
214
215 @Override
216 public String toString() {
217 if (last != null) {
218 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
219 }
220 return "Iterator[]";
221 }
222 }
223
224
225
226
227 protected static class LinkMapIterator<K, V> extends LinkIterator<K, V> implements
228 OrderedMapIterator<K, V>, ResettableIterator<K> {
229
230 protected LinkMapIterator(final AbstractLinkedMap<K, V> parent) {
231 super(parent);
232 }
233
234 @Override
235 public K getKey() {
236 final LinkEntry<K, V> current = currentEntry();
237 if (current == null) {
238 throw new IllegalStateException(GETKEY_INVALID);
239 }
240 return current.getKey();
241 }
242
243 @Override
244 public V getValue() {
245 final LinkEntry<K, V> current = currentEntry();
246 if (current == null) {
247 throw new IllegalStateException(GETVALUE_INVALID);
248 }
249 return current.getValue();
250 }
251
252 @Override
253 public K next() {
254 return super.nextEntry().getKey();
255 }
256
257 @Override
258 public K previous() {
259 return super.previousEntry().getKey();
260 }
261
262 @Override
263 public V setValue(final V value) {
264 final LinkEntry<K, V> current = currentEntry();
265 if (current == null) {
266 throw new IllegalStateException(SETVALUE_INVALID);
267 }
268 return current.setValue(value);
269 }
270 }
271
272
273
274
275 protected static class ValuesIterator<V> extends LinkIterator<Object, V> implements
276 OrderedIterator<V>, ResettableIterator<V> {
277
278 @SuppressWarnings("unchecked")
279 protected ValuesIterator(final AbstractLinkedMap<?, V> parent) {
280 super((AbstractLinkedMap<Object, V>) parent);
281 }
282
283 @Override
284 public V next() {
285 return super.nextEntry().getValue();
286 }
287
288 @Override
289 public V previous() {
290 return super.previousEntry().getValue();
291 }
292 }
293
294
295 transient LinkEntry<K, V> header;
296
297
298
299
300 protected AbstractLinkedMap() {
301 }
302
303
304
305
306
307
308
309 protected AbstractLinkedMap(final int initialCapacity) {
310 super(initialCapacity);
311 }
312
313
314
315
316
317
318
319
320
321
322 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor) {
323 super(initialCapacity, loadFactor);
324 }
325
326
327
328
329
330
331
332
333 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor, final int threshold) {
334 super(initialCapacity, loadFactor, threshold);
335 }
336
337
338
339
340
341
342
343 protected AbstractLinkedMap(final Map<? extends K, ? extends V> map) {
344 super(map);
345 }
346
347
348
349
350
351
352
353
354
355
356 @Override
357 protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) {
358 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
359 link.after = header;
360 link.before = header.before;
361 header.before.after = link;
362 header.before = link;
363 data[hashIndex] = link;
364 }
365
366
367
368
369
370 @Override
371 public void clear() {
372
373 super.clear();
374 header.before = header.after = header;
375 }
376
377
378
379
380
381
382
383 @Override
384 public boolean containsValue(final Object value) {
385
386 if (value == null) {
387 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
388 if (entry.getValue() == null) {
389 return true;
390 }
391 }
392 } else {
393 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
394 if (isEqualValue(value, entry.getValue())) {
395 return true;
396 }
397 }
398 }
399 return false;
400 }
401
402
403
404
405
406
407
408
409
410
411
412
413 @Override
414 protected LinkEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
415 return new LinkEntry<>(next, hashCode, convertKey(key), value);
416 }
417
418
419
420
421
422
423
424 @Override
425 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
426 if (isEmpty()) {
427 return EmptyOrderedIterator.<Map.Entry<K, V>>emptyOrderedIterator();
428 }
429 return new EntrySetIterator<>(this);
430 }
431
432
433
434
435
436
437
438 @Override
439 protected Iterator<K> createKeySetIterator() {
440 if (isEmpty()) {
441 return EmptyOrderedIterator.<K>emptyOrderedIterator();
442 }
443 return new KeySetIterator<>(this);
444 }
445
446
447
448
449
450
451
452 @Override
453 protected Iterator<V> createValuesIterator() {
454 if (isEmpty()) {
455 return EmptyOrderedIterator.<V>emptyOrderedIterator();
456 }
457 return new ValuesIterator<>(this);
458 }
459
460
461
462
463
464
465
466
467
468
469 protected LinkEntry<K, V> entryAfter(final LinkEntry<K, V> entry) {
470 return entry.after;
471 }
472
473
474
475
476
477
478
479
480
481
482 protected LinkEntry<K, V> entryBefore(final LinkEntry<K, V> entry) {
483 return entry.before;
484 }
485
486
487
488
489
490
491 @Override
492 public K firstKey() {
493 if (size == 0) {
494 throw new NoSuchElementException("Map is empty");
495 }
496 return header.after.getKey();
497 }
498
499
500
501
502
503
504
505
506 protected LinkEntry<K, V> getEntry(final int index) {
507 if (index < 0) {
508 throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
509 }
510 if (index >= size) {
511 throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
512 }
513 LinkEntry<K, V> entry;
514 if (index < size / 2) {
515
516 entry = header.after;
517 for (int currentIndex = 0; currentIndex < index; currentIndex++) {
518 entry = entry.after;
519 }
520 } else {
521
522 entry = header;
523 for (int currentIndex = size; currentIndex > index; currentIndex--) {
524 entry = entry.before;
525 }
526 }
527 return entry;
528 }
529
530 @Override
531 protected LinkEntry<K, V> getEntry(final Object key) {
532 return (LinkEntry<K, V>) super.getEntry(key);
533 }
534
535
536
537
538
539
540
541
542 @Override
543 protected void init() {
544 header = createEntry(null, -1, null, null);
545 header.before = header.after = header;
546 }
547
548
549
550
551
552
553 @Override
554 public K lastKey() {
555 if (size == 0) {
556 throw new NoSuchElementException("Map is empty");
557 }
558 return header.before.getKey();
559 }
560
561
562
563
564 @Override
565 public OrderedMapIterator<K, V> mapIterator() {
566 if (size == 0) {
567 return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
568 }
569 return new LinkMapIterator<>(this);
570 }
571
572
573
574
575
576
577
578 @Override
579 public K nextKey(final Object key) {
580 final LinkEntry<K, V> entry = getEntry(key);
581 return entry == null || entry.after == header ? null : entry.after.getKey();
582 }
583
584
585
586
587
588
589
590 @Override
591 public K previousKey(final Object key) {
592 final LinkEntry<K, V> entry = getEntry(key);
593 return entry == null || entry.before == header ? null : entry.before.getKey();
594 }
595
596
597
598
599
600
601
602
603
604
605
606 @Override
607 protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
608 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
609 link.before.after = link.after;
610 link.after.before = link.before;
611 link.after = null;
612 link.before = null;
613 super.removeEntry(entry, hashIndex, previous);
614 }
615
616 }