0
# Advanced Collections
1

2
Apache Commons Collections provides several specialized collection types for specific use cases including tries (prefix trees), bloom filters, advanced queues, and sophisticated iterators.
3

4
## Trie Collections (Prefix Trees)
5

6
Tries are tree-based data structures optimized for prefix-based operations on strings or sequences.
7

8
### Trie<K, V> Interface
9

10
```java { .api }
11
import org.apache.commons.collections4.Trie;
12
import org.apache.commons.collections4.trie.PatriciaTrie;
13
import java.util.SortedMap;
14

15
Trie<String, Integer> trie = new PatriciaTrie<>();
16

17
// Add key-value pairs
18
trie.put("cat", 1);
19
trie.put("car", 2);
20
trie.put("card", 3);
21
trie.put("care", 4);
22
trie.put("careful", 5);
23
trie.put("dog", 6);
24

25
// Standard map operations
26
Integer value = trie.get("car");                    // Returns 2
27
boolean hasKey = trie.containsKey("card");          // true
28
int size = trie.size();                             // 6
29

30
// Prefix-based operations
31
SortedMap<String, Integer> carPrefixed = trie.prefixMap("car");
32
// Returns: {car=2, card=3, care=4, careful=5}
33

34
SortedMap<String, Integer> cPrefixed = trie.prefixMap("c");
35
// Returns: {car=2, card=3, care=4, careful=5, cat=1}
36

37
// Empty prefix returns all entries
38
SortedMap<String, Integer> all = trie.prefixMap("");
39
```
40

41
### PatriciaTrie<V> Implementation
42

43
PATRICIA (Practical Algorithm to Retrieve Information Coded in Alphanumeric) trie implementation.
44

45
```java { .api }
46
import org.apache.commons.collections4.trie.PatriciaTrie;
47
import java.util.Map;
48

49
// Create for String keys
50
PatriciaTrie<String> dictionary = new PatriciaTrie<>();
51

52
// Add dictionary entries
53
dictionary.put("apple", "A red or green fruit");
54
dictionary.put("application", "A software program");
55
dictionary.put("apply", "To put to use");
56
dictionary.put("appreciate", "To value or understand");
57

58
// Autocomplete functionality
59
SortedMap<String, String> suggestions = dictionary.prefixMap("app");
60
System.out.println("Words starting with 'app':");
61
suggestions.forEach((word, definition) -> 
62
    System.out.println(word + ": " + definition));
63

64
// Create from existing map
65
Map<String, Integer> wordCounts = Map.of(
66
    "hello", 5,
67
    "world", 3,
68
    "help", 2,
69
    "helper", 1
70
);
71
PatriciaTrie<Integer> countTrie = new PatriciaTrie<>(wordCounts);
72

73
// Find all words with "hel" prefix
74
SortedMap<String, Integer> helWords = countTrie.prefixMap("hel");
75
// Returns: {hello=5, help=2, helper=1}
76
```
77

78
### Trie Use Cases
79

80
#### Autocomplete System
81

82
```java { .api }
83
public class AutocompleteSystem {
84
    private final Trie<String, Integer> trie = new PatriciaTrie<>();
85
    
86
    public void addWord(String word, int frequency) {
87
        trie.put(word.toLowerCase(), frequency);
88
    }
89
    
90
    public List<String> getSuggestions(String prefix, int maxResults) {
91
        SortedMap<String, Integer> matches = trie.prefixMap(prefix.toLowerCase());
92
        
93
        return matches.entrySet().stream()
94
            .sorted(Map.Entry.<String, Integer>comparingByValue().reversed()) // Sort by frequency
95
            .limit(maxResults)
96
            .map(Map.Entry::getKey)
97
            .collect(Collectors.toList());
98
    }
99
    
100
    public boolean hasWord(String word) {
101
        return trie.containsKey(word.toLowerCase());
102
    }
103
    
104
    public void incrementFrequency(String word) {
105
        String key = word.toLowerCase();
106
        int currentFreq = trie.getOrDefault(key, 0);
107
        trie.put(key, currentFreq + 1);
108
    }
109
}
110
```
111

112
#### Phone Directory
113

114
```java { .api }
115
public class PhoneDirectory {
116
    private final Trie<String, Contact> byName = new PatriciaTrie<>();
117
    private final Trie<String, Contact> byPhone = new PatriciaTrie<>();
118
    
119
    public void addContact(Contact contact) {
120
        byName.put(contact.getName().toLowerCase(), contact);
121
        byPhone.put(contact.getPhone(), contact);
122
    }
123
    
124
    public List<Contact> searchByName(String namePrefix) {
125
        return new ArrayList<>(byName.prefixMap(namePrefix.toLowerCase()).values());
126
    }
127
    
128
    public List<Contact> searchByPhone(String phonePrefix) {
129
        return new ArrayList<>(byPhone.prefixMap(phonePrefix).values());
130
    }
131
    
132
    public Contact getExactMatch(String name) {
133
        return byName.get(name.toLowerCase());
134
    }
135
}
136
```
137

138
## Bloom Filters
139

140
Probabilistic data structures for membership testing with no false negatives but possible false positives.
141

142
### BloomFilter Interface
143

144
```java { .api }
145
import org.apache.commons.collections4.bloomfilter.BloomFilter;
146
import org.apache.commons.collections4.bloomfilter.SimpleBloomFilter;
147
import org.apache.commons.collections4.bloomfilter.Shape;
148
import org.apache.commons.collections4.bloomfilter.Hasher;
149
import org.apache.commons.collections4.bloomfilter.EnhancedDoubleHasher;
150

151
// Create bloom filter shape (size and hash functions)
152
Shape shape = Shape.fromEstimates(1000, 0.01); // Expected elements: 1000, false positive rate: 1%
153

154
BloomFilter filter = new SimpleBloomFilter(shape);
155

156
// Add elements (using hashers)
157
Hasher hasher1 = new EnhancedDoubleHasher("element1".hashCode(), "element1".hashCode());
158
Hasher hasher2 = new EnhancedDoubleHasher("element2".hashCode(), "element2".hashCode());
159

160
filter.merge(hasher1);
161
filter.merge(hasher2);
162

163
// Test membership
164
boolean mayContain1 = filter.contains(hasher1);  // true (definitely in set)
165
Hasher hasher3 = new EnhancedDoubleHasher("element3".hashCode(), "element3".hashCode());
166
boolean mayContain3 = filter.contains(hasher3);  // false or true (maybe in set)
167

168
// Get filter statistics
169
int cardinality = filter.cardinality();          // Number of set bits
170
Shape filterShape = filter.getShape();           // Configuration details
171
```
172

173
### CountingBloomFilter Interface
174

175
Allows removal of elements by maintaining counts.
176

177
```java { .api }
178
import org.apache.commons.collections4.bloomfilter.CountingBloomFilter;
179

180
CountingBloomFilter countingFilter = new ArrayCountingBloomFilter(shape);
181

182
// Add elements
183
countingFilter.merge(hasher1);
184
countingFilter.merge(hasher1); // Add same element twice
185

186
// Remove elements  
187
boolean removed = countingFilter.remove(hasher1); // Decrements count
188
boolean removedAgain = countingFilter.remove(hasher1); // Decrements to zero
189

190
// Element no longer in filter
191
boolean stillThere = countingFilter.contains(hasher1); // false
192
```
193

194
### Bloom Filter Use Cases
195

196
#### Caching Layer
197

198
```java { .api }
199
public class CacheWithBloomFilter<K, V> {
200
    private final Map<K, V> cache = new HashMap<>();
201
    private final BloomFilter filter;
202
    private final Function<K, Hasher> hasherFunction;
203
    
204
    public CacheWithBloomFilter(Shape shape, Function<K, Hasher> hasherFunction) {
205
        this.filter = new SimpleBloomFilter(shape);
206
        this.hasherFunction = hasherFunction;
207
    }
208
    
209
    public void put(K key, V value) {
210
        cache.put(key, value);
211
        filter.merge(hasherFunction.apply(key));
212
    }
213
    
214
    public V get(K key) {
215
        // Fast negative check - if not in bloom filter, definitely not in cache
216
        if (!filter.contains(hasherFunction.apply(key))) {
217
            return null; // Definitely not in cache
218
        }
219
        
220
        // May or may not be in cache - check actual cache
221
        return cache.get(key);
222
    }
223
    
224
    public boolean mightContain(K key) {
225
        return filter.contains(hasherFunction.apply(key));
226
    }
227
}
228
```
229

230
### Additional Bloom Filter Implementations
231

232
Apache Commons Collections provides several specialized bloom filter implementations for different use cases.
233

234
```java { .api }
235
import org.apache.commons.collections4.bloomfilter.ArrayCountingBloomFilter;
236
import org.apache.commons.collections4.bloomfilter.BitMapBloomFilter;
237
import org.apache.commons.collections4.bloomfilter.LayeredBloomFilter;
238

239
// Array-based counting bloom filter (supports removal)
240
ArrayCountingBloomFilter countingFilter = new ArrayCountingBloomFilter(shape);
241
countingFilter.merge(hasher1);
242
countingFilter.merge(hasher1); // Add twice
243
boolean removed = countingFilter.remove(hasher1); // Remove once
244

245
// Bitmap-based bloom filter for memory efficiency
246
BitMapBloomFilter bitMapFilter = new BitMapBloomFilter(shape);
247
bitMapFilter.merge(hasher1);
248
boolean contains = bitMapFilter.contains(hasher1); // Fast membership test
249

250
// Layered bloom filter for time-based data
251
LayeredBloomFilter layeredFilter = new LayeredBloomFilter(shape, 3); // 3 layers
252
layeredFilter.merge(hasher1);
253
layeredFilter.next(); // Advance to next layer
254
layeredFilter.merge(hasher2);
255
```
256

257
### Bloom Filter Shape Configuration
258

259
The Shape class configures bloom filter parameters for optimal performance.
260

261
```java { .api }
262
import org.apache.commons.collections4.bloomfilter.Shape;
263

264
// Create shape from estimates
265
Shape fromEstimates = Shape.fromEstimates(1000, 0.01); // 1000 items, 1% false positive rate
266

267
// Create shape from parameters
268
Shape fromParams = Shape.fromNP(1000, 10); // 1000 items, 10 hash functions
269

270
// Get shape properties
271
int numberOfBits = fromEstimates.getNumberOfBits();       // Total bits in filter
272
int numberOfHashFunctions = fromEstimates.getNumberOfHashFunctions(); // Hash functions used
273
double probability = fromEstimates.getProbability(500);   // False positive rate at 500 items
274

275
// Calculate optimal parameters for different scenarios
276
int optimalBits = Shape.calculateNumberOfBits(1000, 0.01);      // Bits needed
277
int optimalHashes = Shape.calculateNumberOfHashFunctions(1000, 9600); // Hash functions needed
278
```
279

280
## Advanced Queue Implementations
281

282
### CircularFifoQueue<E>
283

284
A fixed-size queue that overwrites the oldest element when full.
285

286
```java { .api }
287
import org.apache.commons.collections4.queue.CircularFifoQueue;
288

289
// Create with default size (32)
290
CircularFifoQueue<String> defaultQueue = new CircularFifoQueue<>();
291

292
// Create with specific size
293
CircularFifoQueue<Integer> numbers = new CircularFifoQueue<>(5);
294

295
// Add elements
296
numbers.offer(1);
297
numbers.offer(2);
298
numbers.offer(3);
299
numbers.offer(4);
300
numbers.offer(5);
301

302
System.out.println(numbers); // [1, 2, 3, 4, 5]
303

304
// Adding when full overwrites oldest
305
numbers.offer(6); // Overwrites 1
306
numbers.offer(7); // Overwrites 2
307

308
System.out.println(numbers); // [3, 4, 5, 6, 7]
309

310
// Queue properties
311
boolean isFull = numbers.isFull();           // true
312
int maxSize = numbers.maxSize();             // 5
313
int currentSize = numbers.size();            // 5
314

315
// Create from existing collection (takes only last N elements if oversized)
316
List<String> manyItems = Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h");
317
CircularFifoQueue<String> fromList = new CircularFifoQueue<>(manyItems); // Takes last 32
318
CircularFifoQueue<String> fromListSized = new CircularFifoQueue<>(3, manyItems); // Takes "f", "g", "h"
319
```
320

321
### Queue Decorators
322

323
```java { .api }
324
import org.apache.commons.collections4.QueueUtils;
325
import org.apache.commons.collections4.Predicate;
326
import org.apache.commons.collections4.Transformer;
327
import java.util.LinkedList;
328
import java.util.Queue;
329

330
Queue<String> baseQueue = new LinkedList<>();
331

332
// Synchronized queue
333
Queue<String> syncQueue = QueueUtils.synchronizedQueue(baseQueue);
334

335
// Unmodifiable queue
336
baseQueue.offer("item1");
337
baseQueue.offer("item2");
338
Queue<String> readOnlyQueue = QueueUtils.unmodifiableQueue(baseQueue);
339

340
// Predicated queue (validates additions)
341
Predicate<String> nonEmpty = s -> s != null && !s.trim().isEmpty();
342
Queue<String> validatedQueue = QueueUtils.predicatedQueue(new LinkedList<>(), nonEmpty);
343

344
validatedQueue.offer("valid");     // Success
345
try {
346
    validatedQueue.offer("");      // Throws IllegalArgumentException
347
} catch (IllegalArgumentException e) {
348
    System.out.println("Empty string rejected");
349
}
350

351
// Transforming queue
352
Transformer<String, String> upperCase = String::toUpperCase;
353
Queue<String> transformingQueue = QueueUtils.transformingQueue(new LinkedList<>(), upperCase);
354
transformingQueue.offer("hello"); // Stored as "HELLO"
355
```
356

357
### Specialized Queue Use Cases
358

359
#### Recent Items Cache
360

361
```java { .api }
362
public class RecentItemsCache<T> {
363
    private final CircularFifoQueue<T> recentItems;
364
    private final Set<T> itemSet = new LinkedHashSet<>();
365
    
366
    public RecentItemsCache(int maxSize) {
367
        this.recentItems = new CircularFifoQueue<>(maxSize);
368
    }
369
    
370
    public void addItem(T item) {
371
        // Remove if already exists to avoid duplicates
372
        if (itemSet.contains(item)) {
373
            recentItems.remove(item);
374
            itemSet.remove(item);
375
        }
376
        
377
        // Add new item
378
        if (recentItems.isFull()) {
379
            T removed = recentItems.poll();
380
            itemSet.remove(removed);
381
        }
382
        
383
        recentItems.offer(item);
384
        itemSet.add(item);
385
    }
386
    
387
    public List<T> getRecentItems() {
388
        return new ArrayList<>(recentItems);
389
    }
390
    
391
    public boolean isRecent(T item) {
392
        return itemSet.contains(item);
393
    }
394
}
395
```
396

397
## Advanced Iterators
398

399
### Specialized Iterator Types
400

401
#### OrderedIterator<E>
402

403
Iterator that supports bidirectional navigation.
404

405
```java { .api }
406
import org.apache.commons.collections4.OrderedIterator;
407
import org.apache.commons.collections4.iterators.ListIteratorWrapper;
408
import java.util.List;
409
import java.util.Arrays;
410

411
List<String> list = Arrays.asList("first", "second", "third", "fourth");
412
OrderedIterator<String> iterator = new ListIteratorWrapper<>(list.listIterator());
413

414
// Forward iteration
415
while (iterator.hasNext()) {
416
    String item = iterator.next();
417
    System.out.println("Forward: " + item);
418
}
419

420
// Backward iteration
421
while (iterator.hasPrevious()) {
422
    String item = iterator.previous();
423
    System.out.println("Backward: " + item);
424
}
425
```
426

427
#### ResettableIterator<E>
428

429
Iterator that can be reset to its initial position.
430

431
```java { .api }
432
import org.apache.commons.collections4.ResettableIterator;
433
import org.apache.commons.collections4.iterators.ArrayIterator;
434

435
String[] array = {"a", "b", "c", "d"};
436
ResettableIterator<String> resetIterator = new ArrayIterator<>(array);
437

438
// First iteration
439
while (resetIterator.hasNext()) {
440
    System.out.println("First pass: " + resetIterator.next());
441
}
442

443
// Reset and iterate again
444
resetIterator.reset();
445
while (resetIterator.hasNext()) {
446
    System.out.println("Second pass: " + resetIterator.next());
447
}
448
```
449

450
#### MapIterator<K, V>
451

452
Iterator optimized for map traversal.
453

454
```java { .api }
455
import org.apache.commons.collections4.MapIterator;
456
import org.apache.commons.collections4.map.LinkedMap;
457

458
LinkedMap<String, Integer> map = new LinkedMap<>();
459
map.put("apple", 5);
460
map.put("banana", 3);
461
map.put("cherry", 8);
462

463
MapIterator<String, Integer> mapIterator = map.mapIterator();
464
while (mapIterator.hasNext()) {
465
    String key = mapIterator.next();
466
    Integer value = mapIterator.getValue();
467
    
468
    // Modify value in-place
469
    mapIterator.setValue(value * 2);
470
    
471
    System.out.println(key + " -> " + mapIterator.getValue());
472
}
473
```
474

475
### Iterator Utilities
476

477
#### Chaining Iterators
478

479
```java { .api }
480
import org.apache.commons.collections4.IteratorUtils;
481
import java.util.Iterator;
482
import java.util.Arrays;
483

484
List<String> list1 = Arrays.asList("a", "b", "c");
485
List<String> list2 = Arrays.asList("d", "e", "f");
486
List<String> list3 = Arrays.asList("g", "h", "i");
487

488
// Chain multiple iterators
489
Iterator<String> chained = IteratorUtils.chainedIterator(
490
    list1.iterator(),
491
    list2.iterator(), 
492
    list3.iterator()
493
);
494

495
// Iterate through all elements in sequence
496
while (chained.hasNext()) {
497
    System.out.println(chained.next()); // a, b, c, d, e, f, g, h, i
498
}
499
```
500

501
#### Filtering Iterators
502

503
```java { .api }
504
import org.apache.commons.collections4.Predicate;
505

506
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
507

508
// Filter even numbers
509
Predicate<Integer> evenPredicate = n -> n % 2 == 0;
510
Iterator<Integer> evenNumbers = IteratorUtils.filteredIterator(numbers.iterator(), evenPredicate);
511

512
System.out.println("Even numbers:");
513
while (evenNumbers.hasNext()) {
514
    System.out.println(evenNumbers.next()); // 2, 4, 6, 8, 10
515
}
516
```
517

518
#### Transforming Iterators
519

520
```java { .api }
521
import org.apache.commons.collections4.Transformer;
522

523
List<String> words = Arrays.asList("hello", "world", "java", "collections");
524

525
// Transform to uppercase
526
Transformer<String, String> upperCase = String::toUpperCase;
527
Iterator<String> upperCaseIterator = IteratorUtils.transformedIterator(words.iterator(), upperCase);
528

529
System.out.println("Uppercase words:");
530
while (upperCaseIterator.hasNext()) {
531
    System.out.println(upperCaseIterator.next()); // HELLO, WORLD, JAVA, COLLECTIONS
532
}
533

534
// Transform to word lengths
535
Transformer<String, Integer> lengthTransformer = String::length;
536
Iterator<Integer> lengthIterator = IteratorUtils.transformedIterator(words.iterator(), lengthTransformer);
537
```
538

539
#### Collating Iterator
540

541
Merges multiple sorted iterators into a single sorted iterator.
542

543
```java { .api }
544
import java.util.Comparator;
545

546
List<Integer> list1 = Arrays.asList(1, 4, 7, 10);  // Sorted
547
List<Integer> list2 = Arrays.asList(2, 5, 8, 11);  // Sorted
548
List<Integer> list3 = Arrays.asList(3, 6, 9, 12);  // Sorted
549

550
// Merge into single sorted sequence
551
Iterator<Integer> collated = IteratorUtils.collatingIterator(
552
    Comparator.naturalOrder(),
553
    list1.iterator(),
554
    list2.iterator(),
555
    list3.iterator()
556
);
557

558
System.out.println("Merged sorted sequence:");
559
while (collated.hasNext()) {
560
    System.out.println(collated.next()); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
561
}
562
```
563

564
## Performance Considerations
565

566
### Trie Performance
567

568
```java { .api }
569
// Trie operations are O(k) where k is key length, not collection size
570
Trie<String, Object> largeTrie = new PatriciaTrie<>();
571

572
// Adding 1M entries - each operation is O(key_length)
573
for (int i = 0; i < 1_000_000; i++) {
574
    largeTrie.put("key" + i, i);
575
}
576

577
// Prefix search is still O(prefix_length + result_size)
578
SortedMap<String, Object> results = largeTrie.prefixMap("key123"); // Fast even with 1M entries
579
```
580

581
### Circular Queue Performance  
582

583
```java { .api }
584
// CircularFifoQueue offers O(1) operations
585
CircularFifoQueue<String> efficient = new CircularFifoQueue<>(1000);
586

587
// All operations are constant time
588
efficient.offer("item"); // O(1)
589
String item = efficient.poll(); // O(1)
590
boolean full = efficient.isFull(); // O(1)
591

592
// Much more efficient than removing from front of ArrayList
593
List<String> inefficient = new ArrayList<>();
594
// Adding to end: O(1), removing from front: O(n)
595
```
596

597
### Iterator Memory Usage
598

599
```java { .api }
600
// Memory-efficient iteration over large collections
601
List<String> hugeList = generateHugeList(); // Millions of items
602

603
// Memory efficient - only holds current position
604
Iterator<String> memoryEfficient = hugeList.iterator();
605

606
// Less memory efficient - may hold references to filtered items
607
List<String> filtered = hugeList.stream()
608
    .filter(s -> s.startsWith("prefix"))
609
    .collect(Collectors.toList());
610

611
// Use iterator utilities for memory-efficient processing
612
Iterator<String> filteredIterator = IteratorUtils.filteredIterator(
613
    hugeList.iterator(),
614
    s -> s.startsWith("prefix")
615
);
616
```
617

618
## Best Practices
619

620
### Choosing Collection Types
621

622
```java { .api }
623
// Use Trie for prefix-based operations
624
Trie<String, Object> autocomplete = new PatriciaTrie<>(); // Autocomplete, dictionaries
625

626
// Use Bloom Filter for membership pre-filtering  
627
BloomFilter membershipFilter = new SimpleBloomFilter(shape); // Cache layers, deduplication
628

629
// Use CircularFifoQueue for fixed-size buffers
630
CircularFifoQueue<LogEntry> logBuffer = new CircularFifoQueue<>(1000); // Recent items, logs
631

632
// Use specialized iterators for complex traversal
633
Iterator<String> complexTraversal = IteratorUtils.chainedIterator(
634
    IteratorUtils.filteredIterator(source1.iterator(), predicate1),
635
    IteratorUtils.transformedIterator(source2.iterator(), transformer)
636
);
637
```
638

639
### Error Handling
640

641
```java { .api }
642
// Safe trie operations
643
public List<String> safeGetSuggestions(Trie<String, Integer> trie, String prefix) {
644
    if (prefix == null || trie == null) {
645
        return Collections.emptyList();
646
    }
647
    
648
    try {
649
        SortedMap<String, Integer> matches = trie.prefixMap(prefix);
650
        return new ArrayList<>(matches.keySet());
651
    } catch (Exception e) {
652
        // Log error and return empty results
653
        return Collections.emptyList();
654
    }
655
}
656

657
// Safe queue operations
658
public boolean safeOffer(CircularFifoQueue<String> queue, String item) {
659
    if (queue == null || item == null) {
660
        return false;
661
    }
662
    
663
    return queue.offer(item); // Always succeeds for CircularFifoQueue
664
}
665
```
666

667
Advanced collections in Apache Commons Collections provide specialized data structures for specific performance and functionality requirements. Choose the appropriate type based on your access patterns, memory constraints, and performance needs.