1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package org.htmlunit.util;
16
17 import static org.junit.Assert.assertEquals;
18 import static org.junit.Assert.assertFalse;
19 import static org.junit.Assert.assertNotNull;
20 import static org.junit.Assert.assertNull;
21 import static org.junit.Assert.assertSame;
22 import static org.junit.Assert.assertThrows;
23 import static org.junit.Assert.assertTrue;
24
25 import java.io.ByteArrayInputStream;
26 import java.io.ByteArrayOutputStream;
27 import java.io.IOException;
28 import java.io.ObjectInputStream;
29 import java.io.ObjectOutputStream;
30 import java.util.ArrayList;
31 import java.util.Collections;
32 import java.util.HashMap;
33 import java.util.HashSet;
34 import java.util.Iterator;
35 import java.util.LinkedHashMap;
36 import java.util.List;
37 import java.util.Map;
38 import java.util.Map.Entry;
39 import java.util.NoSuchElementException;
40 import java.util.Random;
41 import java.util.Set;
42 import java.util.function.BiConsumer;
43 import java.util.stream.Collectors;
44 import java.util.stream.IntStream;
45
46 import org.junit.Test;
47
48
49
50
51
52
53 public class OrderedFastHashMapTest {
54
55
56
57
58 @Test
59 public void ctr() {
60 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
61 assertEquals(0, m.size());
62 assertEquals(0, m.entrySet().size());
63 assertEquals(0, m.keys().size());
64 assertEquals(0, m.values().size());
65
66 assertNull(m.get("test"));
67 }
68
69
70
71
72 @Test
73 public void simplePut() {
74 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
75 m.put("K", "V");
76
77 assertEquals("V", m.get("K"));
78 assertEquals("K", m.getKey(0));
79 assertEquals("V", m.getValue(0));
80 assertEquals("V", m.getFirst());
81 assertEquals("V", m.getLast());
82
83 assertEquals("K", m.getEntry(0).getKey());
84 assertEquals("V", m.getEntry(0).getValue());
85 }
86
87
88
89
90 @Test
91 public void allowAnEmptyStart() {
92 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(0);
93 assertNull(m.get("K"));
94 assertNull(m.remove("K"));
95
96 m.put("K", "V");
97
98 assertEquals("V", m.get("K"));
99 assertEquals("K", m.getKey(0));
100 assertEquals("V", m.getValue(0));
101 assertEquals("V", m.getFirst());
102 assertEquals("V", m.getLast());
103
104 assertEquals("K", m.getEntry(0).getKey());
105 assertEquals("V", m.getEntry(0).getValue());
106 }
107
108
109
110
111 @Test
112 public void simpleMultiPut() {
113 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
114 m.put("K", "VK");
115 m.put("B", "VB");
116 m.put("A", "VA");
117 m.put("Z", "VZ");
118
119 final BiConsumer<String, Integer> t = (k, index) -> {
120 assertEquals("V" + k, m.get(k));
121 assertEquals(k, m.getKey(index));
122 assertEquals("V" + k, m.getValue(index));
123 };
124 t.accept("K", 0);
125 t.accept("B", 1);
126 t.accept("A", 2);
127 t.accept("Z", 3);
128
129
130 m.put("0", "V0");
131 m.put("z", "Vz");
132
133 t.accept("K", 0);
134 t.accept("B", 1);
135 t.accept("A", 2);
136 t.accept("Z", 3);
137 t.accept("0", 4);
138 t.accept("z", 5);
139 }
140
141
142
143
144 @Test
145 public void putAgainDoesNotChangeOrder() {
146 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
147 m.put("K", "VK");
148 m.put("B", "VB");
149 m.put("A", "VA");
150 m.put("Z", "VZ");
151
152 m.put("B", "VB");
153 m.put("K", "VK");
154 m.put("Z", "VZ");
155 m.put("A", "VA");
156
157 final BiConsumer<String, Integer> t = (k, index) -> {
158 assertEquals("V" + k, m.get(k));
159 assertEquals(k, m.getKey(index));
160 assertEquals("V" + k, m.getValue(index));
161 };
162 t.accept("K", 0);
163 t.accept("B", 1);
164 t.accept("A", 2);
165 t.accept("Z", 3);
166 }
167
168
169
170
171 @Test
172 public void getDoesNotChangeOrder() {
173 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
174 m.put("K", "VK");
175 m.put("B", "VB");
176 m.put("A", "VA");
177 m.put("Z", "VZ");
178
179 assertEquals("VZ", m.get("Z"));
180 assertEquals("VA", m.get("A"));
181 assertEquals("VB", m.get("B"));
182 assertEquals("VZ", m.get("Z"));
183
184 final BiConsumer<String, Integer> t = (k, index) -> {
185 assertEquals("V" + k, m.get(k));
186 assertEquals(k, m.getKey(index));
187 assertEquals("V" + k, m.getValue(index));
188 };
189 t.accept("K", 0);
190 t.accept("B", 1);
191 t.accept("A", 2);
192 t.accept("Z", 3);
193 }
194
195
196
197
198 @Test
199 public void growSmall() {
200 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(3);
201 for (int i = 0; i < 10; i++) {
202 m.add(String.valueOf(i), "V" + String.valueOf(i));
203 }
204
205 final BiConsumer<String, Integer> t = (k, index) -> {
206 assertEquals("V" + k, m.get(k));
207 assertEquals(k, m.getKey(index));
208 assertEquals("V" + k, m.getValue(index));
209 };
210 for (int i = 0; i < 10; i++) {
211 t.accept(String.valueOf(i), i);
212 }
213 }
214
215
216
217
218 @Test
219 public void growBig() {
220 final List<String> keys = new ArrayList<>();
221 final Random r = new Random();
222
223 for (int i = 0; i < 200; i++) {
224 final String key = RandomUtils.randomString(r, 3, 10);
225 keys.add(key);
226 }
227
228
229 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(10);
230 for (final String key : keys) {
231 m.put(key, "V" + key);
232 }
233
234 final BiConsumer<String, Integer> t = (k, index) -> {
235 assertEquals("V" + k, m.get(k));
236 assertEquals(k, m.getKey(index));
237 assertEquals("V" + k, m.getValue(index));
238 };
239
240
241 for (int i = 0; i < 200; i++) {
242 t.accept(keys.get(i), i);
243 }
244 }
245
246
247
248
249 @Test
250 public void keys() {
251 final OrderedFastHashMap<String, Integer> f = new OrderedFastHashMap<>(3);
252 f.put("aa", 1);
253 f.put("bb", 2);
254 f.put("cc", 3);
255 f.put("dd", 4);
256 f.put("ee", 5);
257
258 final List<String> k = f.keys();
259 assertEquals(5, k.size());
260 assertTrue(k.contains("aa"));
261 assertTrue(k.contains("bb"));
262 assertTrue(k.contains("cc"));
263 assertTrue(k.contains("dd"));
264 assertTrue(k.contains("ee"));
265
266
267 assertEquals(Integer.valueOf(3), f.remove("cc"));
268 f.remove("c");
269 final List<String> k2 = f.keys();
270 assertEquals(4, k2.size());
271 assertTrue(k2.contains("aa"));
272 assertTrue(k2.contains("bb"));
273 assertTrue(k2.contains("dd"));
274 assertTrue(k2.contains("ee"));
275
276
277 f.put("zz", 10);
278 f.remove("c");
279 final List<String> k3 = f.keys();
280 assertEquals(5, k3.size());
281 assertTrue(k3.contains("aa"));
282 assertTrue(k3.contains("bb"));
283 assertTrue(k3.contains("dd"));
284 assertTrue(k3.contains("ee"));
285 assertTrue(k3.contains("zz"));
286
287
288 assertNull(f.get("unknown"));
289 }
290
291
292
293
294 @Test
295 public void values() {
296 final OrderedFastHashMap<String, Integer> f = new OrderedFastHashMap<>(3);
297 f.put("aa", 1);
298 f.put("bb", 2);
299 f.put("cc", 3);
300 f.put("dd", 4);
301 f.put("ee", 5);
302
303
304 final List<Integer> values = f.values();
305 assertEquals(5, values.size());
306 assertTrue(values.contains(1));
307 assertTrue(values.contains(2));
308 assertTrue(values.contains(3));
309 assertTrue(values.contains(4));
310 assertTrue(values.contains(5));
311
312
313 assertEquals(Integer.valueOf(3), f.remove("cc"));
314
315 f.remove("c");
316 final List<Integer> v2 = f.values();
317 assertEquals(4, v2.size());
318 assertTrue(v2.contains(1));
319 assertTrue(v2.contains(2));
320 assertTrue(v2.contains(4));
321 assertTrue(v2.contains(5));
322 }
323
324
325
326
327 @Test
328 public void remove_simple_only_one() {
329 final OrderedFastHashMap<String, String> m1 = new OrderedFastHashMap<>();
330
331 m1.put("b", "value");
332 assertEquals("value", m1.remove("b"));
333 assertEquals(0, m1.size());
334 }
335
336
337
338
339 @Test
340 public void remove_simple_first() {
341
342 final OrderedFastHashMap<String, String> m1 = new OrderedFastHashMap<>();
343 m1.put("b", "bvalue");
344 m1.put("c", "cvalue");
345 assertEquals("bvalue", m1.remove("b"));
346 assertEquals("cvalue", m1.get("c"));
347 assertEquals(1, m1.size());
348 }
349
350
351
352
353 @Test
354 public void remove_simple_from_the_middle() {
355
356 final OrderedFastHashMap<String, String> m1 = new OrderedFastHashMap<>();
357 m1.put("a", "avalue");
358 m1.put("b", "bvalue");
359 m1.put("c", "cvalue");
360 assertEquals("bvalue", m1.remove("b"));
361 assertEquals("avalue", m1.get("a"));
362 assertEquals("cvalue", m1.get("c"));
363 assertEquals(2, m1.size());
364 assertEquals("a", m1.getKey(0));
365 assertEquals("c", m1.getKey(1));
366 }
367
368
369
370
371 @Test
372 public void remove_simple_unknown() {
373
374 final OrderedFastHashMap<String, String> m1 = new OrderedFastHashMap<>();
375 assertNull(m1.remove("a"));
376 m1.put("b", "value");
377 assertNull(m1.remove("a"));
378 }
379
380
381
382
383 @Test
384 public void remove_complex() {
385 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(3);
386 m.put("b", "Vb1");
387 m.put("a", "Va");
388 m.put("d", "Vd1");
389 m.put("c", "Vc");
390 m.put("e", "Ve");
391
392 m.remove("b");
393 m.remove("d");
394
395 final BiConsumer<String, Integer> t = (k, index) -> {
396 assertEquals("V" + k, m.get(k));
397 assertEquals(k, m.getKey(index));
398 assertEquals("V" + k, m.getValue(index));
399 };
400
401 assertEquals(3, m.size());
402 t.accept("a", 0);
403 t.accept("c", 1);
404 t.accept("e", 2);
405 assertNull(m.get("d"));
406 assertNull(m.get("b"));
407
408
409 assertNull(m.remove("b"));
410 assertNull(m.remove("d"));
411
412 m.put("d", "Vd");
413 m.put("b", "Vb");
414
415 t.accept("a", 0);
416 t.accept("c", 1);
417 t.accept("e", 2);
418 t.accept("d", 3);
419 t.accept("b", 4);
420 }
421
422
423
424
425 @Test
426 public void removeRandomlyToEmpty() {
427 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(15);
428 final Set<String> keys = new HashSet<>();
429 final Random r = new Random();
430
431 for (int i = 0; i < 1000; i++) {
432 final String key = RandomUtils.randomString(r, 1, 10);
433 keys.add(key);
434 m.put(key, "V" + key);
435 }
436 assertEquals(keys.size(), m.size());
437
438 keys.forEach(key -> {
439 assertEquals("V" + key, m.get(key));
440 m.remove(key);
441 assertNull(m.get(key));
442 });
443 assertEquals(0, m.size());
444 }
445
446
447
448
449 @Test
450 public void removeTryingToCoverEdges_Last() {
451 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
452 for (int i = 0; i < 200; i++) {
453
454 m.put(String.valueOf(i), "V" + String.valueOf(i));
455 m.put(String.valueOf(i + 1), "any");
456 assertEquals("any", m.remove(String.valueOf(i + 1)));
457 }
458
459 final BiConsumer<String, Integer> t = (k, index) -> {
460 assertEquals("V" + k, m.get(k));
461 assertEquals(k, m.getKey(index));
462 assertEquals("V" + k, m.getValue(index));
463 };
464
465 assertEquals(200, m.size());
466 for (int i = 0; i < 200; i++) {
467 t.accept(String.valueOf(i), i);
468 }
469 }
470
471
472
473
474 @Test
475 public void removeTryingToCoverEdges_First() {
476 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
477 for (int i = 0; i < 4000; i = i + 2) {
478 m.put(String.valueOf(i), "any");
479 m.put(String.valueOf(i + 1), "V" + String.valueOf(i + 1));
480 assertEquals("any", m.remove(String.valueOf(i)));
481 }
482
483 final BiConsumer<String, Integer> t = (k, index) -> {
484 assertEquals("V" + k, m.get(k));
485 assertEquals(k, m.getKey(index));
486 assertEquals("V" + k, m.getValue(index));
487 };
488
489 assertEquals(2000, m.size());
490 for (int i = 0; i < 4000; i = i + 2) {
491 t.accept(String.valueOf(i + 1), i / 2);
492 }
493 }
494
495
496
497
498 @Test
499 public void removeTryingToCoverEdges_Middle() {
500 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
501 for (int i = 0; i < 3 * 1972; i = i + 3) {
502 m.put(String.valueOf(i), "V" + String.valueOf(i));
503 m.put(String.valueOf(i + 1), "any");
504 m.put(String.valueOf(i + 2), "V" + String.valueOf(i + 2));
505 assertEquals("any", m.remove(String.valueOf(i + 1)));
506 }
507
508 final BiConsumer<String, Integer> t = (k, index) -> {
509 assertEquals("V" + k, m.get(k));
510 assertEquals(k, m.getKey(index));
511 assertEquals("V" + k, m.getValue(index));
512 };
513
514 assertEquals(2 * 1972, m.size());
515 for (int i = 0, pos = 0; i < 3 * 1972; i = i + 3, pos = pos + 2) {
516 t.accept(String.valueOf(i), pos);
517 t.accept(String.valueOf(i + 2), pos + 1);
518 }
519 }
520
521
522
523
524 @Test
525 public void removeByIndex_first() {
526 final OrderedFastHashMap<String, Integer> m = new OrderedFastHashMap<>();
527 m.put("a", 1);
528 m.put("b", 2);
529 m.put("c", 3);
530 m.remove(0);
531
532 assertEquals("b", m.getKey(0));
533 assertEquals("c", m.getKey(1));
534 assertEquals(2, m.size());
535 }
536
537
538
539
540 @Test
541 public void removeByIndex_second() {
542 final OrderedFastHashMap<String, Integer> m = new OrderedFastHashMap<>();
543 m.put("a", 1);
544 m.put("b", 2);
545 m.put("c", 3);
546 m.remove(1);
547
548 assertEquals("a", m.getKey(0));
549 assertEquals("c", m.getKey(1));
550 assertEquals(2, m.size());
551 }
552
553
554
555
556 @Test
557 public void removeByIndex_last() {
558 final OrderedFastHashMap<String, Integer> m = new OrderedFastHashMap<>();
559 m.put("a", 1);
560 m.put("b", 2);
561 m.put("c", 3);
562 m.remove(2);
563
564 assertEquals("a", m.getKey(0));
565 assertEquals("b", m.getKey(1));
566 assertEquals(2, m.size());
567 }
568
569
570
571
572 @Test
573 public void removeByIndex_middle_to_empty() {
574 final OrderedFastHashMap<String, Integer> m = new OrderedFastHashMap<>();
575 m.put("a", 1);
576 m.put("b", 2);
577 m.put("c", 3);
578 m.remove(1);
579 m.remove(1);
580 m.remove(0);
581
582 assertEquals(0, m.size());
583 }
584
585
586
587
588 @Test
589 public void clear() {
590 final OrderedFastHashMap<String, Integer> m = new OrderedFastHashMap<>();
591 m.put("a", 1);
592 assertEquals(1, m.size());
593
594 m.clear();
595 assertEquals(0, m.size());
596 assertEquals(0, m.keys().size());
597 assertEquals(0, m.values().size());
598 assertNull(m.get("a"));
599
600 m.put("b", 2);
601 assertEquals(1, m.size());
602 m.put("a", 3);
603 assertEquals(2, m.size());
604
605 m.clear();
606 assertEquals(0, m.size());
607 assertEquals(0, m.keys().size());
608 assertEquals(0, m.values().size());
609
610 m.put("a", 1);
611 m.put("b", 2);
612 m.put("c", 3);
613 m.put("c", 3);
614 assertEquals(3, m.size());
615 assertEquals(3, m.keys().size());
616 assertEquals(3, m.values().size());
617
618 assertEquals(Integer.valueOf(1), m.get("a"));
619 assertEquals(Integer.valueOf(2), m.get("b"));
620 assertEquals(Integer.valueOf(3), m.get("c"));
621 }
622
623
624
625
626 @Test
627 public void removeLast() {
628 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
629 final Random r1 = new Random(144L);
630
631
632 assertNull(m.removeLast());
633
634 for (int i = 0; i < 3 * 1972; i++) {
635 final String key = RandomUtils.randomString(r1, 20);
636 final String value = "V" + key;
637
638 m.put(key, value);
639 assertEquals(value, m.removeLast());
640 m.put(key, value);
641 }
642 assertEquals(3 * 1972, m.size());
643
644 final BiConsumer<String, Integer> t = (k, index) -> {
645 assertEquals("V" + k, m.get(k));
646 assertEquals(k, m.getKey(index));
647 assertEquals("V" + k, m.getValue(index));
648 };
649
650 final Random r2 = new Random(144L);
651 for (int i = 0; i < 3 * 1972; i++) {
652 final String key = RandomUtils.randomString(r2, 20);
653 t.accept(key, i);
654 }
655
656 final Random r3 = new Random(144L);
657 for (int i = 0; i < 3 * 1972; i++) {
658 final String key = RandomUtils.randomString(r3, 2, 10);
659 m.removeLast();
660 }
661 assertEquals(0, m.size());
662 }
663
664
665
666
667 @Test
668 public void removeFirst_Empty() {
669 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
670 assertNull(m.removeFirst());
671 assertEquals(0, m.size());
672 }
673
674
675
676
677 @Test
678 public void removeFirst_One() {
679 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
680 m.put("u", "Vu");
681 assertEquals("Vu", m.removeFirst());
682 assertEquals(0, m.size());
683 }
684
685
686
687
688 @Test
689 public void removeFirst_Two() {
690 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
691 m.put("u", "Vu");
692 m.put("a", "Va");
693 assertEquals("Vu", m.removeFirst());
694 assertEquals(1, m.size());
695 assertEquals("a", m.getKey(0));
696 assertEquals("Va", m.getValue(0));
697 }
698
699
700
701
702 @Test
703 public void removeFirst_WithGrowth() {
704 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(3);
705 final Random r = new Random(98765244L);
706 final List<String> keys = new ArrayList<>();
707
708 final BiConsumer<String, Integer> t = (k, index) -> {
709 assertEquals("V" + k, m.get(k));
710 assertEquals(k, m.getKey(index));
711 assertEquals("V" + k, m.getValue(index));
712 };
713
714 for (int i = 1; i < 1992; i++) {
715 keys.clear();
716 m.clear();
717
718
719 for (int e = 0; e < i; e++) {
720 final String k = RandomUtils.randomString(r, 20);
721 keys.add(k);
722 }
723
724
725 for (final String k : keys) {
726 m.put(k, "V" + k);
727 }
728
729 final String rk = keys.remove(0);
730 assertEquals("V" + rk, m.removeFirst());
731
732
733 m.put(rk, "V" + rk);
734 keys.add(rk);
735
736
737 assertEquals(keys.size(), m.size());
738
739
740 for (int e = 0; e < keys.size(); e++) {
741 t.accept(keys.get(e), e);
742 }
743 }
744 }
745
746
747
748
749 @Test
750 public void addFirst_to_empty() {
751 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
752 m.addFirst("a", "1");
753 assertEquals(1, m.size());
754 assertEquals("a", m.getKey(0));
755 assertEquals("1", m.getValue(0));
756 }
757
758
759
760
761
762 @Test
763 public void addFirst_twice() {
764 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
765 m.addFirst("a", "1");
766 m.addFirst("b", "2");
767 assertEquals(2, m.size());
768 assertEquals("a", m.getKey(1));
769 assertEquals("1", m.getValue(1));
770 assertEquals("b", m.getKey(0));
771 assertEquals("2", m.getValue(0));
772 }
773
774
775
776
777 @Test
778 public void addFirst__second_to_normal_added() {
779 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
780 m.add("a", "1");
781 m.addFirst("b", "2");
782 assertEquals(2, m.size());
783 assertEquals("a", m.getKey(1));
784 assertEquals("1", m.getValue(1));
785 assertEquals("b", m.getKey(0));
786 assertEquals("2", m.getValue(0));
787 }
788
789
790
791
792 @Test
793 public void addLast_to_empty() {
794 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
795 m.addLast("a", "1");
796 assertEquals(1, m.size());
797 assertEquals("a", m.getKey(0));
798 assertEquals("1", m.getValue(0));
799 }
800
801
802
803
804 @Test
805 public void addLast_twice() {
806 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
807 m.addLast("a", "1");
808 m.addLast("b", "2");
809 assertEquals(2, m.size());
810 assertEquals("a", m.getKey(0));
811 assertEquals("1", m.getValue(0));
812 assertEquals("b", m.getKey(1));
813 assertEquals("2", m.getValue(1));
814 }
815
816
817
818
819 @Test
820 public void addLast_to_normally_added() {
821 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
822 m.add("a", "1");
823 m.addLast("b", "2");
824 assertEquals(2, m.size());
825 assertEquals("a", m.getKey(0));
826 assertEquals("1", m.getValue(0));
827 assertEquals("b", m.getKey(1));
828 assertEquals("2", m.getValue(1));
829 }
830
831
832
833
834 @Test
835 public void containsKey_Empty() {
836 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
837 assertFalse(m.containsKey("akey"));
838 }
839
840
841
842
843 @Test
844 public void containsKey_True_single() {
845 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
846 m.put("akey", "any");
847 assertTrue(m.containsKey("akey"));
848 }
849
850
851
852
853 @Test
854 public void containsKey_True_many() {
855 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
856 m.put("akey1", "any");
857 m.put("akey2", "any");
858 m.put("akey3", "any");
859 m.put("akey4", "any");
860 assertTrue(m.containsKey("akey2"));
861 assertTrue(m.containsKey(new String("akey2")));
862 }
863
864
865
866
867 @Test
868 public void containsKey_True_content_based() {
869
870 final OrderedFastHashMap<MockKey<String>, String> m = new OrderedFastHashMap<>();
871 final MockKey<String> mockKey1 = new MockKey<>(10, "akey1");
872 m.put(mockKey1, "any1");
873 m.put(new MockKey<>(10, "akey2"), "any2");
874 m.put(new MockKey<>(10, "akey3"), "any3");
875 m.put(new MockKey<>(10, "akey4"), "any4");
876 assertTrue(m.containsKey(mockKey1));
877 assertTrue(m.containsKey(new MockKey<>(10, "akey1")));
878 }
879
880
881
882
883 @Test
884 public void containsKey_False_single() {
885 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
886 m.put("akey", "any");
887 assertFalse(m.containsKey("akey1"));
888 }
889
890
891
892
893 @Test
894 public void containsKey_False_many() {
895 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
896 m.put("akey1", "any");
897 m.put("akey2", "any");
898 m.put("akey3", "any");
899 assertFalse(m.containsKey("akey"));
900 }
901
902
903
904
905 @Test
906 public void containsKey_False_content_based() {
907
908 final OrderedFastHashMap<MockKey<String>, String> m = new OrderedFastHashMap<>();
909 m.put(new MockKey<>(10, "akey2"), "any2");
910 m.put(new MockKey<>(10, "akey3"), "any3");
911 m.put(new MockKey<>(10, "akey4"), "any4");
912 assertFalse(m.containsKey(new MockKey<>(10, "akey")));
913
914
915 assertFalse(m.containsKey(new MockKey<>(114, "akey2")));
916 assertFalse(m.containsKey(new MockKey<>(113, "akey3")));
917 assertFalse(m.containsKey(new MockKey<>(112, "akey4")));
918 }
919
920
921
922
923 @Test
924 public void containsValue_Empty() {
925 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
926 assertFalse(m.containsValue("avalue"));
927 }
928
929
930
931
932 @Test
933 public void containsValue_True_single() {
934 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
935 m.put("akey3", "any");
936 assertTrue(m.containsValue("any"));
937 }
938
939
940
941
942 @Test
943 public void containsValue_True_content_based() {
944 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
945 m.put("akey1", "any1");
946 m.put("akey2", "any2");
947 m.put("akey3", "any3");
948 assertTrue(m.containsValue("any1"));
949 assertTrue(m.containsValue("any2"));
950 assertTrue(m.containsValue("any3"));
951 assertTrue(m.containsValue(new String("any1")));
952 assertTrue(m.containsValue(new String("any2")));
953 assertTrue(m.containsValue(new String("any3")));
954 }
955
956
957
958
959 @Test
960 public void containsValue_False_single() {
961 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
962 m.put("akey3", "any");
963 assertFalse(m.containsValue("asdf"));
964 }
965
966
967
968
969 @Test
970 public void containsValue_False_many() {
971 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
972 m.put("akey1", "any1");
973 m.put("akey2", "any2");
974 m.put("akey3", "any3");
975
976 assertFalse(m.containsValue("akey1"));
977 assertFalse(m.containsValue("akey2"));
978 assertFalse(m.containsValue("akey3"));
979
980
981 assertFalse(m.containsValue("any5"));
982 assertFalse(m.containsValue("any6"));
983 assertFalse(m.containsValue("any7"));
984 }
985
986
987
988
989 @Test
990 public void isEmpty_empty() {
991 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
992 assertTrue(m.isEmpty());
993 }
994
995
996
997
998 @Test
999 public void isEmpty_size_zero() {
1000 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(0);
1001 assertTrue(m.isEmpty());
1002 }
1003
1004
1005
1006
1007 @Test
1008 public void isEmpty_false() {
1009 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1010 m.put("aaa", "a");
1011 assertFalse(m.isEmpty());
1012 }
1013
1014
1015
1016
1017 @Test
1018 public void isEmpty_after_clear() {
1019 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1020 m.put("aaa", "a");
1021 m.clear();
1022 assertTrue(m.isEmpty());
1023 }
1024
1025
1026
1027
1028 @Test
1029 public void entry() {
1030 final Map<String, String> m = new OrderedFastHashMap<>();
1031 m.put("K1", "V1");
1032 m.put("K2", "V1");
1033 final Entry<String, String> e = m.entrySet().iterator().next();
1034
1035 Iterator<Entry<String, String>> i = m.entrySet().iterator();
1036 final Entry<String, String> e1 = i.next();
1037 final Entry<String, String> e2 = i.next();
1038
1039 m.put("K1", "V2");
1040 i = m.entrySet().iterator();
1041 final Entry<String, String> e3 = i.next();
1042
1043
1044 assertEquals("K1", e.getKey());
1045 assertEquals("V1", e.getValue());
1046 assertEquals(e.getKey().hashCode() ^ e.getValue().hashCode(), e.hashCode());
1047 assertEquals("K1=V1", e.toString());
1048
1049 assertTrue(e.equals(e));
1050
1051 assertTrue(e1.equals(e));
1052 assertTrue(e.equals(e1));
1053
1054 assertFalse(e.equals(e2));
1055 assertFalse(e2.equals(e));
1056
1057 assertFalse(e.equals(e2));
1058 assertFalse(e3.equals(e));
1059
1060 assertFalse(e.equals("k"));
1061
1062 assertThrows(UnsupportedOperationException.class, () -> e.setValue("foo"));
1063 }
1064
1065
1066
1067
1068 @Test
1069 public void entrySet_empty() {
1070 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1071 final Set<Entry<String, String>> set = m.entrySet();
1072 assertEquals(0, set.size());
1073 assertTrue(set.isEmpty());
1074 }
1075
1076
1077
1078
1079 @Test
1080 public void entrySet_zero_size() {
1081 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(0);
1082 final Set<Entry<String, String>> set = m.entrySet();
1083 assertEquals(0, set.size());
1084 assertTrue(set.isEmpty());
1085 }
1086
1087
1088
1089
1090 @Test
1091 public void entrySet() {
1092 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1093 m.put("K1", "V1");
1094 final Set<Entry<String, String>> set = m.entrySet();
1095 assertEquals(1, set.size());
1096 assertFalse(set.isEmpty());
1097
1098 final Entry<String, String> e1 = set.iterator().next();
1099 assertEquals("K1", e1.getKey());
1100 assertEquals("V1", e1.getValue());
1101
1102 final Map<String, String> map = new OrderedFastHashMap<>();
1103 map.put("K1", "V1");
1104 map.put("K2", "V1");
1105 final Iterator<Map.Entry<String, String>> i = map.entrySet().iterator();
1106 final Entry<String, String> e2 = i.next();
1107 final Entry<String, String> e3 = i.next();
1108
1109 assertTrue(set.contains(e1));
1110 assertTrue(set.contains(e2));
1111
1112 assertFalse(set.contains("a"));
1113 assertFalse(set.contains(e3));
1114 }
1115
1116
1117
1118
1119 @Test
1120 public void entrySet_large() {
1121 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1122 IntStream.rangeClosed(0, 11).forEach(i -> m.put("K" + i, "V" + i));
1123 final Set<Entry<String, String>> set = m.entrySet();
1124 assertEquals(12, set.size());
1125 assertFalse(set.isEmpty());
1126
1127 final Iterator<Entry<String, String>> iter = set.iterator();
1128 IntStream.rangeClosed(0, 11).forEach(i -> {
1129 assertTrue(iter.hasNext());
1130 final Entry<String, String> e = iter.next();
1131 assertEquals("K" + i, e.getKey());
1132 assertEquals("V" + i, e.getValue());
1133 });
1134 assertFalse(iter.hasNext());
1135
1136
1137 assertThrows(NoSuchElementException.class, () -> iter.next());
1138 }
1139
1140
1141
1142
1143 @Test
1144 public void entrySet_toArray_empty() {
1145 final Map<String, String> m = new OrderedFastHashMap<>();
1146 final Set<Entry<String, String>> set = m.entrySet();
1147 assertEquals(0, set.toArray().length);
1148 assertEquals(0, set.toArray(new Map.Entry[0]).length);
1149 assertEquals(10, set.toArray(new String[10]).length);
1150
1151
1152 final String[] a = set.toArray(new String[10]);
1153 for (int i = 0; i < 10; i++) {
1154 assertNull(a[i]);
1155 }
1156 }
1157
1158
1159
1160
1161 @Test
1162 public void entrySet_toArray_zero_sized() {
1163 final Map<String, String> m = new OrderedFastHashMap<>(0);
1164 final Set<Entry<String, String>> set = m.entrySet();
1165 assertEquals(0, set.toArray().length);
1166 assertEquals(0, set.toArray(new Map.Entry[0]).length);
1167 assertEquals(10, set.toArray(new String[10]).length);
1168
1169
1170 final String[] a = set.toArray(new String[10]);
1171 for (int i = 0; i < 10; i++) {
1172 assertNull(a[i]);
1173 }
1174 }
1175
1176
1177
1178
1179 @Test
1180 public void entrySet_toArray_normal() {
1181 final Map<String, String> m = new OrderedFastHashMap<>();
1182 m.put("K1", "V1");
1183 final Set<Entry<String, String>> set = m.entrySet();
1184 assertEquals(1, set.toArray().length);
1185 assertEquals(1, set.toArray(new Map.Entry[0]).length);
1186 assertEquals(1, set.toArray(new Map.Entry[1]).length);
1187
1188 assertNotNull(set.toArray()[0]);
1189 assertEquals("K1", ((Map.Entry<String, String>) set.toArray()[0]).getKey());
1190 assertEquals("V1", ((Map.Entry<String, String>) set.toArray()[0]).getValue());
1191
1192 assertEquals("K1", set.toArray(new Map.Entry[0])[0].getKey());
1193 assertEquals("V1", set.toArray(new Map.Entry[0])[0].getValue());
1194
1195 assertEquals("K1", set.toArray(new Map.Entry[1])[0].getKey());
1196 assertEquals("V1", set.toArray(new Map.Entry[1])[0].getValue());
1197 }
1198
1199
1200
1201
1202 @Test
1203 public void entrySet_toArray_get_same_back() {
1204
1205 final Map<String, String> m = new OrderedFastHashMap<>();
1206 m.put("K1", "V1");
1207 final Set<Entry<String, String>> set = m.entrySet();
1208
1209
1210 final Map.Entry[] array1 = new Map.Entry[1];
1211 assertSame(array1, set.toArray(array1));
1212
1213
1214 final Map.Entry[] array2 = new Map.Entry[10];
1215 assertSame(array2, set.toArray(array2));
1216 }
1217
1218
1219
1220
1221 @Test
1222 public void entrySet_toArray_large() {
1223 final Map<String, String> m = new OrderedFastHashMap<>();
1224 IntStream.rangeClosed(0, 44).forEach(i -> m.put("K" + i, "V" + i));
1225 final Object[] a1 = m.entrySet().toArray();
1226 final Map.Entry[] a2 = m.entrySet().toArray(new Map.Entry[45]);
1227 assertEquals(45, a1.length);
1228 assertEquals(45, a2.length);
1229
1230 for (int i = 0; i <= 44; i++) {
1231 assertEquals("K" + i, ((Map.Entry<String, String>) a1[i]).getKey());
1232 assertEquals("V" + i, ((Map.Entry<String, String>) a1[i]).getValue());
1233
1234 assertEquals("K" + i, a2[i].getKey());
1235 assertEquals("V" + i, a2[i].getValue());
1236 }
1237 }
1238
1239
1240
1241
1242 @Test
1243 public void keySet_empty() {
1244 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1245 final Set<String> set = m.keySet();
1246 assertEquals(0, set.size());
1247 assertTrue(set.isEmpty());
1248 }
1249
1250
1251
1252
1253 @Test
1254 public void keySet_size_zero() {
1255 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(0);
1256 final Set<String> set = m.keySet();
1257 assertEquals(0, set.size());
1258 assertTrue(set.isEmpty());
1259 }
1260
1261
1262
1263
1264 @Test
1265 public void keySet_one() {
1266 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1267 m.put("K1", "V1");
1268 final Set<String> set = m.keySet();
1269 assertEquals(1, set.size());
1270 assertFalse(set.isEmpty());
1271
1272 final String e1 = set.iterator().next();
1273 assertEquals("K1", e1);
1274 }
1275
1276
1277
1278
1279 @Test
1280 public void keySet_large() {
1281 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1282 IntStream.rangeClosed(0, 44).forEach(i -> m.put("K" + i, "V" + i));
1283 final Set<String> set = m.keySet();
1284 assertEquals(45, set.size());
1285 assertFalse(set.isEmpty());
1286
1287 final Iterator<String> iter = set.iterator();
1288 IntStream.rangeClosed(0, 44).forEach(i -> {
1289 assertTrue(iter.hasNext());
1290 final String e = iter.next();
1291 assertEquals("K" + i, e);
1292 assertTrue(set.contains("K" + i));
1293 });
1294 assertFalse(iter.hasNext());
1295
1296
1297 assertThrows(NoSuchElementException.class, () -> iter.next());
1298 }
1299
1300
1301
1302
1303 @Test
1304 public void keySet_toArray_empty() {
1305 final Map<String, String> m = new OrderedFastHashMap<>();
1306 final Set<String> set = m.keySet();
1307 assertEquals(0, set.toArray().length);
1308 assertEquals(0, set.toArray(new String[0]).length);
1309 assertEquals(10, set.toArray(new String[10]).length);
1310
1311
1312 final String[] a = set.toArray(new String[10]);
1313 for (int i = 0; i < 10; i++) {
1314 assertNull(a[i]);
1315 }
1316 }
1317
1318
1319
1320
1321 @Test
1322 public void keySet_toArray_one() {
1323 final Map<String, String> m = new OrderedFastHashMap<>();
1324 m.put("K1", "V1");
1325 final Set<String> set = m.keySet();
1326 assertEquals(1, set.toArray().length);
1327 assertEquals(1, set.toArray(new String[0]).length);
1328 assertEquals(1, set.toArray(new String[1]).length);
1329
1330 assertEquals("K1", set.toArray()[0]);
1331 assertEquals("K1", set.toArray(new String[0])[0]);
1332 assertEquals("K1", set.toArray(new String[1])[0]);
1333 }
1334
1335
1336
1337
1338 @Test
1339 public void keySet_toArray_same_array() {
1340
1341 final Map<String, String> m = new OrderedFastHashMap<>();
1342 m.put("K1", "V1");
1343 final Set<String> set = m.keySet();
1344
1345
1346 final String[] array1 = new String[1];
1347 assertSame(array1, set.toArray(array1));
1348
1349
1350 final String[] array2 = new String[10];
1351 assertSame(array2, set.toArray(array2));
1352 }
1353
1354
1355
1356
1357 @Test
1358 public void keySet_toArray_many() {
1359 final Map<String, String> m = new OrderedFastHashMap<>();
1360 IntStream.rangeClosed(0, 44).forEach(i -> m.put("K" + i, "V" + i));
1361 final Object[] a1 = m.keySet().toArray();
1362 final String[] a2 = m.keySet().toArray(new String[45]);
1363 assertEquals(45, a1.length);
1364 assertEquals(45, a2.length);
1365
1366 for (int i = 0; i <= 44; i++) {
1367 assertEquals("K" + i, a1[i]);
1368 assertEquals("K" + i, a2[i]);
1369 }
1370 }
1371
1372
1373
1374
1375 @Test
1376 public void putAll_cannot_add_self() {
1377
1378 final IllegalArgumentException thrown = assertThrows(IllegalArgumentException.class, () -> {
1379 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1380 m.putAll(m);
1381 });
1382 assertEquals("Cannot add myself", thrown.getMessage());
1383 }
1384
1385
1386
1387
1388 @Test
1389 public void putAll_empty() {
1390
1391 final Map<String, String> src = new HashMap<>();
1392 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1393 m.putAll(src);
1394 assertEquals(0, m.size());
1395 }
1396
1397
1398
1399
1400 @Test
1401 public void putAll_target_empty() {
1402
1403 final Map<String, String> src = new LinkedHashMap<>();
1404 IntStream.rangeClosed(0, 10).forEach(i -> src.put("K" + i, "V" + i));
1405
1406 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1407 m.putAll(src);
1408 assertEquals(11, m.size());
1409
1410 final Iterator<Entry<String, String>> iter = m.entrySet().iterator();
1411 IntStream.rangeClosed(0, 10).forEach(i -> {
1412 assertTrue(iter.hasNext());
1413 final Entry<String, String> e = iter.next();
1414 assertEquals("K" + i, e.getKey());
1415 assertEquals("V" + i, e.getValue());
1416 });
1417 assertFalse(iter.hasNext());
1418 }
1419
1420
1421
1422
1423 @Test
1424 public void putAll_source_empty() {
1425
1426 final Map<String, String> src = new LinkedHashMap<>();
1427 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1428 m.put("K1", "V1");
1429
1430 m.putAll(src);
1431 assertEquals(1, m.size());
1432
1433 final Iterator<Entry<String, String>> iter = m.entrySet().iterator();
1434 assertTrue(iter.hasNext());
1435 final Entry<String, String> e = iter.next();
1436 assertEquals("K1", e.getKey());
1437 assertEquals("V1", e.getValue());
1438 assertFalse(iter.hasNext());
1439 }
1440
1441
1442
1443
1444 @Test
1445 public void putAll_target_not_empty() {
1446
1447 final Map<String, String> src = new LinkedHashMap<>();
1448 IntStream.rangeClosed(0, 17).forEach(i -> src.put("SRCK" + i, "SRCV" + i));
1449
1450 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1451 IntStream.rangeClosed(100, 111).forEach(i -> m.put("K" + i, "V" + i));
1452
1453 m.putAll(src);
1454 assertEquals(12 + 18, m.size());
1455
1456 final Iterator<Entry<String, String>> iter = m.entrySet().iterator();
1457 IntStream.rangeClosed(100, 111).forEach(i -> {
1458 assertTrue(iter.hasNext());
1459 final Entry<String, String> e = iter.next();
1460 assertEquals("K" + i, e.getKey());
1461 assertEquals("V" + i, e.getValue());
1462 });
1463 assertTrue(iter.hasNext());
1464 IntStream.rangeClosed(0, 17).forEach(i -> {
1465 assertTrue(iter.hasNext());
1466 final Entry<String, String> e = iter.next();
1467 assertEquals("SRCK" + i, e.getKey());
1468 assertEquals("SRCV" + i, e.getValue());
1469 });
1470 assertFalse(iter.hasNext());
1471 }
1472
1473
1474
1475
1476 @Test
1477 public void putAll_same_type_not_same_object() {
1478
1479 final OrderedFastHashMap<String, String> src = new OrderedFastHashMap<>();
1480 IntStream.rangeClosed(19, 99).forEach(i -> src.put("K" + i, "V" + i));
1481
1482 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1483 IntStream.rangeClosed(0, 18).forEach(i -> m.put("K" + i, "V" + i));
1484
1485 m.putAll(src);
1486 assertEquals(100, m.size());
1487
1488 final Set<Entry<String, String>> set = m.entrySet();
1489 final Iterator<Entry<String, String>> iter = set.iterator();
1490 IntStream.rangeClosed(0, 99).forEach(i -> {
1491 assertTrue(iter.hasNext());
1492 final Entry<String, String> e = iter.next();
1493 assertEquals("K" + i, e.getKey());
1494 assertEquals("K" + i, e.getKey());
1495 assertEquals("V" + i, e.getValue());
1496 });
1497 assertFalse(iter.hasNext());
1498 }
1499
1500
1501
1502
1503 @Test
1504 public void putAll_to_another_map() {
1505
1506 final Map<String, String> src = new OrderedFastHashMap<>();
1507 final Map<String, String> m = new HashMap<>();
1508 m.putAll(src);
1509 assertEquals(0, m.size());
1510 }
1511
1512
1513
1514
1515 @Test
1516 public void collision() {
1517 final OrderedFastHashMap<MockKey<String>, String> f = new OrderedFastHashMap<>(13);
1518 IntStream.range(0, 15).forEach(i -> {
1519 f.put(new MockKey<>(12, "k" + i), "v" + i);
1520 });
1521
1522 assertEquals(15, f.size());
1523
1524 IntStream.range(0, 15).forEach(i -> {
1525 assertEquals("v" + i, f.get(new MockKey<>(12, "k" + i)));
1526 });
1527
1528
1529 IntStream.range(0, 20).forEach(i -> {
1530 f.put(new MockKey<>(12, "k" + i), "v" + i);
1531 });
1532
1533 assertEquals(20, f.size());
1534
1535 IntStream.range(0, 20).forEach(i -> {
1536 assertEquals("v" + i, f.get(new MockKey<>(12, "k" + i)));
1537 });
1538
1539
1540 IntStream.range(0, 10).forEach(i -> {
1541 assertEquals("v" + i, f.remove(new MockKey<>(12, "k" + i)));
1542 });
1543 IntStream.range(10, 20).forEach(i -> {
1544 assertEquals("v" + i, f.get(new MockKey<>(12, "k" + i)));
1545 });
1546 }
1547
1548
1549
1550
1551 @Test
1552 public void overflow() {
1553 final OrderedFastHashMap<MockKey<String>, Integer> m = new OrderedFastHashMap<>(5);
1554 final Map<MockKey<String>, Integer> data = IntStream.range(0, 152).mapToObj(Integer::valueOf)
1555 .collect(Collectors.toMap(i -> new MockKey<>(1, "k" + i), i -> i));
1556
1557
1558 data.forEach((k, v) -> m.put(k, v));
1559
1560
1561 data.forEach((k, v) -> assertEquals(v, m.get(k)));
1562 assertEquals(152, m.size());
1563 assertEquals(152, m.keys().size());
1564 assertEquals(152, m.values().size());
1565 }
1566
1567
1568
1569
1570
1571 @Test
1572 public void growFromSmall_InfiniteLoopIsssue() {
1573 for (int initSize = 0; initSize < 100; initSize++) {
1574 final OrderedFastHashMap<Integer, Integer> m = new OrderedFastHashMap<>(initSize);
1575
1576 for (int i = 0; i < 300; i++) {
1577
1578 m.put(i, i);
1579
1580
1581 for (int j = 0; j <= i; j++) {
1582 assertEquals(Integer.valueOf(j), m.get(j));
1583 }
1584
1585
1586 for (int j = -1; j >= -100; j--) {
1587 assertNull(m.get(j));
1588 }
1589 }
1590 }
1591 }
1592
1593
1594
1595
1596 @Test
1597 public void hitEachSlot() {
1598 final OrderedFastHashMap<MockKey<String>, Integer> m = new OrderedFastHashMap<>(15);
1599
1600 final Map<MockKey<String>, Integer> data = IntStream.range(0, 150).mapToObj(Integer::valueOf)
1601 .collect(Collectors.toMap(i -> new MockKey<>(i, "k1" + i), i -> i));
1602
1603
1604 data.putAll(IntStream.range(0, 150).mapToObj(Integer::valueOf)
1605 .collect(Collectors.toMap(i -> new MockKey<>(i, "k2" + i), i -> i)));
1606
1607 data.forEach((k, v) -> m.put(k, v));
1608
1609 data.forEach((k, v) -> assertEquals(v, m.get(k)));
1610 assertEquals(300, m.size());
1611 assertEquals(300, m.keys().size());
1612 assertEquals(300, m.values().size());
1613
1614
1615 data.forEach((k, v) -> m.remove(k));
1616
1617 assertEquals(0, m.size());
1618 assertEquals(0, m.keys().size());
1619 assertEquals(0, m.values().size());
1620
1621
1622 final List<MockKey<String>> keys = data.keySet().stream().collect(Collectors.toList());
1623 keys.stream().sorted().forEach(k -> m.put(k, data.get(k)));
1624
1625 Collections.shuffle(keys);
1626 keys.forEach(k -> m.put(k, data.get(k) + 42));
1627
1628
1629 data.forEach((k, v) -> assertEquals(Integer.valueOf(v + 42), m.get(k)));
1630 assertEquals(300, m.size());
1631 assertEquals(300, m.keys().size());
1632 assertEquals(300, m.values().size());
1633
1634
1635 Collections.shuffle(keys);
1636 keys.forEach(k -> m.remove(k));
1637
1638
1639 data.forEach((k, v) -> assertNull(m.get(k)));
1640 assertEquals(0, m.size());
1641 assertEquals(0, m.keys().size());
1642 assertEquals(0, m.values().size());
1643 }
1644
1645
1646
1647
1648 @Test
1649 public void reverse_empty() {
1650
1651 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1652 m.reverse();
1653 }
1654
1655
1656
1657
1658 @Test
1659 public void reverse_zero_sized() {
1660
1661 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>(0);
1662 m.reverse();
1663 }
1664
1665
1666
1667
1668 @Test
1669 public void reverse_one() {
1670
1671 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1672 m.put("k0", "v0");
1673 m.reverse();
1674 assertEquals("k0", m.getEntry(0).getKey());
1675 assertEquals("v0", m.getEntry(0).getValue());
1676 }
1677
1678
1679
1680
1681 @Test
1682 public void reverse_two() {
1683
1684 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1685 m.put("k0", "v0");
1686 m.put("k1", "v1");
1687 m.reverse();
1688 assertEquals("k1", m.getEntry(0).getKey());
1689 assertEquals("v1", m.getEntry(0).getValue());
1690 assertEquals("k0", m.getEntry(1).getKey());
1691 assertEquals("v0", m.getEntry(1).getValue());
1692 }
1693
1694
1695
1696
1697 @Test
1698 public void reverse_three() {
1699
1700 final OrderedFastHashMap<String, String> m = new OrderedFastHashMap<>();
1701 m.put("k0", "v0");
1702 m.put("k1", "v1");
1703 m.put("k2", "v2");
1704 m.reverse();
1705 assertEquals("k2", m.getEntry(0).getKey());
1706 assertEquals("v2", m.getEntry(0).getValue());
1707 assertEquals("k1", m.getEntry(1).getKey());
1708 assertEquals("v1", m.getEntry(1).getValue());
1709 assertEquals("k0", m.getEntry(2).getKey());
1710 assertEquals("v0", m.getEntry(2).getValue());
1711 }
1712
1713
1714
1715
1716 @Test
1717 public void reverse_many_odd() {
1718
1719 final OrderedFastHashMap<Integer, Integer> m = new OrderedFastHashMap<>(15);
1720 IntStream.range(0, 117).mapToObj(Integer::valueOf).forEach(i -> m.put(i, i));
1721 m.reverse();
1722
1723 IntStream.range(0, 117).mapToObj(Integer::valueOf).forEach(i -> {
1724 final OrderedFastHashMap.Entry<Integer, Integer> e = m.getEntry(m.size() - i - 1);
1725 assertEquals(i, e.getKey());
1726 assertEquals(i, e.getValue());
1727 });
1728 }
1729
1730
1731
1732
1733 @Test
1734 public void reverse_many_even() {
1735
1736 final OrderedFastHashMap<Integer, Integer> m = new OrderedFastHashMap<>(15);
1737 IntStream.range(0, 80).mapToObj(Integer::valueOf).forEach(i -> m.put(i, i));
1738 m.reverse();
1739
1740 IntStream.range(0, 80).mapToObj(Integer::valueOf).forEach(i -> {
1741 final OrderedFastHashMap.Entry<Integer, Integer> e = m.getEntry(m.size() - i - 1);
1742 assertEquals(i, e.getKey());
1743 assertEquals(i, e.getValue());
1744 });
1745 }
1746
1747
1748
1749
1750
1751
1752
1753
1754 @Test
1755 public void serializable() throws IOException, ClassNotFoundException {
1756 final OrderedFastHashMap<String, Integer> src = new OrderedFastHashMap<>();
1757
1758 final ByteArrayOutputStream buffer = new ByteArrayOutputStream();
1759 final ObjectOutputStream objectOutputStream = new ObjectOutputStream(buffer);
1760 objectOutputStream.writeObject(src);
1761 objectOutputStream.close();
1762
1763 final ObjectInputStream objectInputStream =
1764 new ObjectInputStream(new ByteArrayInputStream(buffer.toByteArray()));
1765 final OrderedFastHashMap<String, Integer> copy =
1766 (OrderedFastHashMap<String, Integer>) objectInputStream.readObject();
1767 objectInputStream.close();
1768
1769 assertEquals(src.size(), copy.size());
1770
1771
1772 copy.put("test", 1);
1773 assertEquals(Integer.valueOf(1), copy.get("test"));
1774 }
1775
1776
1777
1778
1779
1780
1781
1782
1783 @Test
1784 public void serializable_notEmpty() throws IOException, ClassNotFoundException {
1785 final OrderedFastHashMap<String, Integer> src = new OrderedFastHashMap<>();
1786 src.put("zuha", 1);
1787 src.put("bs", 2);
1788 src.put("ozuasdc", 3);
1789 src.put("asdf", 4);
1790 src.remove("bs");
1791
1792 final ByteArrayOutputStream buffer = new ByteArrayOutputStream();
1793 final ObjectOutputStream objectOutputStream = new ObjectOutputStream(buffer);
1794 objectOutputStream.writeObject(src);
1795 objectOutputStream.close();
1796
1797 final ObjectInputStream objectInputStream =
1798 new ObjectInputStream(new ByteArrayInputStream(buffer.toByteArray()));
1799 final OrderedFastHashMap<String, Integer> copy =
1800 (OrderedFastHashMap<String, Integer>) objectInputStream.readObject();
1801 objectInputStream.close();
1802
1803 assertEquals(src.size(), copy.size());
1804 assertEquals(Integer.valueOf(4), copy.get("asdf"));
1805 assertEquals(Integer.valueOf(3), copy.get("ozuasdc"));
1806 assertEquals(Integer.valueOf(1), copy.get("zuha"));
1807
1808
1809 assertEquals("zuha", copy.getKey(0));
1810 assertEquals("ozuasdc", copy.getKey(1));
1811 assertEquals("asdf", copy.getKey(2));
1812 }
1813
1814 static class MockKey<T extends Comparable<T>> implements Comparable<MockKey<T>> {
1815 public final T key_;
1816 public final int hash_;
1817
1818 MockKey(final int hash, final T key) {
1819 this.hash_ = hash;
1820 this.key_ = key;
1821 }
1822
1823 @Override
1824 public int hashCode() {
1825 return hash_;
1826 }
1827
1828 @Override
1829 public boolean equals(final Object o) {
1830 final MockKey<T> t = (MockKey<T>) o;
1831 return hash_ == o.hashCode() && key_.equals(t.key_);
1832 }
1833
1834 @Override
1835 public String toString() {
1836 return "MockKey [key=" + key_ + ", hash=" + hash_ + "]";
1837 }
1838
1839 @Override
1840 public int compareTo(final MockKey<T> o) {
1841 return o.key_.compareTo(this.key_);
1842 }
1843 }
1844 }