0
# Type-Specific Collections
1

2
High-performance primitive collections for int, long, double, float, char, short, byte, and boolean types. These collections avoid the boxing/unboxing overhead of standard Java collections by working directly with primitive values while maintaining compatibility with standard collection interfaces.
3

4
## Overview
5

6
Each primitive type has its own dedicated package with complete collection implementations:
7

8
- **`it.unimi.dsi.fastutil.ints`** - Integer collections
9
- **`it.unimi.dsi.fastutil.longs`** - Long collections  
10
- **`it.unimi.dsi.fastutil.doubles`** - Double collections
11
- **`it.unimi.dsi.fastutil.floats`** - Float collections
12
- **`it.unimi.dsi.fastutil.chars`** - Character collections
13
- **`it.unimi.dsi.fastutil.shorts`** - Short collections
14
- **`it.unimi.dsi.fastutil.bytes`** - Byte collections
15
- **`it.unimi.dsi.fastutil.booleans`** - Boolean collections
16

17
Each package follows the same naming convention and provides the same collection types, differing only in the primitive type they handle.
18

19
**Note**: In version 8.5.16 source code examined, these packages contain only `package-info.java` placeholder files. The actual implementation classes are generated during the build process using preprocessor techniques from driver files, or may be available in the compiled JAR distribution.
20

21
## Capabilities
22

23
### Type-Specific Lists
24

25
Lists optimized for primitive types with direct primitive access methods alongside standard List interface compatibility.
26

27
```java { .api }
28
/**
29
 * List specialized for int elements, avoiding boxing overhead
30
 */
31
public interface IntList extends List<Integer>, IntCollection {
32
    /**
33
     * Get int element at specified index without boxing
34
     * @param index the index
35
     * @return the int value at index
36
     */
37
    int getInt(int index);
38
    
39
    /**
40
     * Set int element at specified index without boxing  
41
     * @param index the index
42
     * @param k the int value to set
43
     * @return the previous int value at index
44
     */
45
    int set(int index, int k);
46
    
47
    /**
48
     * Add int element at specified index without boxing
49
     * @param index the index
50
     * @param k the int value to add
51
     */
52
    void add(int index, int k);
53
    
54
    /**
55
     * Remove int element at specified index without boxing
56
     * @param index the index
57
     * @return the removed int value
58
     */
59
    int removeInt(int index);
60
    
61
    /**
62
     * Find first occurrence of int value
63
     * @param k the int value to find
64
     * @return the index, or -1 if not found
65
     */
66
    int indexOf(int k);
67
    
68
    /**
69
     * Find last occurrence of int value
70
     * @param k the int value to find
71
     * @return the index, or -1 if not found
72
     */
73
    int lastIndexOf(int k);
74
    
75
    /**
76
     * Get specialized int iterator
77
     * @return IntListIterator for this list
78
     */
79
    IntListIterator listIterator();
80
    
81
    /**
82
     * Get specialized int iterator starting at index
83
     * @param index starting position
84
     * @return IntListIterator starting at index
85
     */
86
    IntListIterator listIterator(int index);
87
    
88
    /**
89
     * Get sublist view
90
     * @param from start index (inclusive)
91
     * @param to end index (exclusive)
92
     * @return IntList view of the specified range
93
     */
94
    IntList subList(int from, int to);
95
}
96

97
// Similar interfaces exist for all primitive types:
98
// LongList, DoubleList, FloatList, CharList, ShortList, ByteList, BooleanList
99
```
100

101
**Usage Examples:**
102

103
```java
104
import it.unimi.dsi.fastutil.ints.*;
105

106
// Create and populate an int list
107
IntList numbers = new IntArrayList();
108
numbers.add(42);        // Direct int addition
109
numbers.add(1, 24);     // Insert at index 1
110

111
// Direct primitive access (no boxing)
112
int value = numbers.getInt(0);     // Get without boxing
113
int oldValue = numbers.set(1, 99); // Set without boxing
114

115
// Still compatible with standard List<Integer>
116
List<Integer> standardList = numbers; // Works seamlessly
117
standardList.add(Integer.valueOf(15)); // Boxing when needed
118
```
119

120
### Type-Specific Sets
121

122
Sets optimized for primitive types with direct primitive membership testing and modification.
123

124
```java { .api }
125
/**
126
 * Set specialized for int elements, avoiding boxing overhead
127
 */
128
public interface IntSet extends Set<Integer>, IntCollection {
129
    /**
130
     * Add int element to set without boxing
131
     * @param k the int value to add
132
     * @return true if the set was modified
133
     */
134
    boolean add(int k);
135
    
136
    /**
137
     * Test membership of int value without boxing
138
     * @param k the int value to test
139
     * @return true if the set contains the value
140
     */
141
    boolean contains(int k);
142
    
143
    /**
144
     * Remove int value from set without boxing
145
     * @param k the int value to remove
146
     * @return true if the set was modified
147
     */
148
    boolean remove(int k);
149
    
150
    /**
151
     * Get specialized int iterator
152
     * @return IntIterator for this set
153
     */
154
    IntIterator iterator();
155
}
156

157
/**
158
 * Sorted set specialized for int elements
159
 */
160
public interface IntSortedSet extends IntSet, SortedSet<Integer> {
161
    /**
162
     * Get comparator for int values
163
     * @return IntComparator used by this set
164
     */
165
    IntComparator comparator();
166
    
167
    /**
168
     * Get subset from fromElement (inclusive) to toElement (exclusive)
169
     * @param fromElement start value
170
     * @param toElement end value  
171
     * @return IntSortedSet view of the range
172
     */
173
    IntSortedSet subSet(int fromElement, int toElement);
174
    
175
    /**
176
     * Get subset with elements less than toElement
177
     * @param toElement upper bound (exclusive)
178
     * @return IntSortedSet view of elements < toElement
179
     */
180
    IntSortedSet headSet(int toElement);
181
    
182
    /**
183
     * Get subset with elements >= fromElement
184
     * @param fromElement lower bound (inclusive)
185
     * @return IntSortedSet view of elements >= fromElement
186
     */
187
    IntSortedSet tailSet(int fromElement);
188
    
189
    /**
190
     * Get first (smallest) int value
191
     * @return the first int value
192
     */
193
    int firstInt();
194
    
195
    /**
196
     * Get last (largest) int value
197
     * @return the last int value
198
     */
199
    int lastInt();
200
}
201

202
// Similar interfaces exist for all primitive types:
203
// LongSet, DoubleSet, FloatSet, CharSet, ShortSet, ByteSet, BooleanSet
204
// LongSortedSet, DoubleSortedSet, etc.
205
```
206

207
**Usage Examples:**
208

209
```java
210
import it.unimi.dsi.fastutil.ints.*;
211

212
// Create and populate an int set
213
IntSet uniqueNumbers = new IntOpenHashSet();
214
uniqueNumbers.add(42);         // Direct int addition
215
uniqueNumbers.add(42);         // Duplicate, ignored
216

217
boolean hasValue = uniqueNumbers.contains(42); // Direct primitive test
218
boolean removed = uniqueNumbers.remove(42);    // Direct primitive removal
219

220
// Sorted set usage
221
IntSortedSet sortedNumbers = new IntAVLTreeSet();
222
sortedNumbers.add(30);
223
sortedNumbers.add(10);  
224
sortedNumbers.add(20);
225

226
int smallest = sortedNumbers.firstInt(); // 10
227
int largest = sortedNumbers.lastInt();   // 30
228
IntSortedSet range = sortedNumbers.subSet(15, 25); // [20]
229
```
230

231
### Type-Specific Maps
232

233
Maps with primitive keys and/or values, providing direct primitive access without boxing overhead.
234

235
```java { .api }
236
/**
237
 * Map with int keys and Object values
238
 * @param <V> the type of values
239
 */
240
public interface Int2ObjectMap<V> extends Map<Integer, V> {
241
    /**
242
     * Put mapping with int key without boxing
243
     * @param key the int key
244
     * @param value the value
245
     * @return the previous value, or null
246
     */
247
    V put(int key, V value);
248
    
249
    /**
250
     * Get value for int key without boxing
251
     * @param key the int key
252
     * @return the value, or null if not present
253
     */
254
    V get(int key);
255
    
256
    /**
257
     * Remove mapping for int key without boxing
258
     * @param key the int key
259
     * @return the removed value, or null
260
     */
261
    V remove(int key);
262
    
263
    /**
264
     * Test if int key is present without boxing
265
     * @param key the int key
266
     * @return true if key is present
267
     */
268
    boolean containsKey(int key);
269
    
270
    /**
271
     * Get set of int keys
272
     * @return IntSet containing all keys
273
     */
274
    IntSet keySet();
275
    
276
    /**
277
     * Get collection of values
278
     * @return Collection<V> containing all values
279
     */
280
    Collection<V> values();
281
    
282
    /**
283
     * Get set of int key-value entries
284
     * @return ObjectSet<Entry> containing all entries
285
     */
286
    ObjectSet<Int2ObjectMap.Entry<V>> int2ObjectEntrySet();
287
    
288
    /**
289
     * Entry with int key and Object value
290
     * @param <V> the type of value
291
     */
292
    interface Entry<V> extends Map.Entry<Integer, V> {
293
        /**
294
         * Get int key without boxing
295
         * @return the int key
296
         */
297
        int getIntKey();
298
        
299
        /**
300
         * Set int key without boxing
301
         * @param key the new int key
302
         * @return the old int key
303
         */
304
        int setValue(V value);
305
    }
306
}
307

308
/**
309
 * Map with int keys and int values (fully primitive)
310
 */
311
public interface Int2IntMap extends Map<Integer, Integer> {
312
    /**
313
     * Put int-to-int mapping without boxing
314
     * @param key the int key
315
     * @param value the int value
316
     * @return the previous int value, or default return value
317
     */
318
    int put(int key, int value);
319
    
320
    /**
321
     * Get int value for int key without boxing
322
     * @param key the int key
323
     * @return the int value, or default return value if not present
324
     */
325
    int get(int key);
326
    
327
    /**
328
     * Remove int key without boxing
329
     * @param key the int key
330
     * @return the removed int value, or default return value
331
     */
332
    int remove(int key);
333
    
334
    /**
335
     * Test if int key is present without boxing
336
     * @param key the int key
337
     * @return true if key is present
338
     */
339
    boolean containsKey(int key);
340
    
341
    /**
342
     * Test if int value is present without boxing
343
     * @param value the int value
344
     * @return true if value is present
345
     */
346
    boolean containsValue(int value);
347
    
348
    /**
349
     * Get default return value for missing keys
350
     * @return the default return value
351
     */
352
    int defaultReturnValue();
353
    
354
    /**
355
     * Set default return value for missing keys
356
     * @param rv the new default return value
357
     */
358
    void defaultReturnValue(int rv);
359
}
360

361
// All combinations of primitive types are available:
362
// Int2LongMap, Int2DoubleMap, Long2IntMap, Double2ObjectMap, etc.
363
```
364

365
**Usage Examples:**
366

367
```java
368
import it.unimi.dsi.fastutil.ints.*;
369
import it.unimi.dsi.fastutil.objects.*;
370

371
// Int-to-Object map
372
Int2ObjectMap<String> intToString = new Int2ObjectOpenHashMap<>();
373
intToString.put(1, "one");       // Direct int key
374
intToString.put(2, "two");
375
String value = intToString.get(1); // Direct int key lookup
376

377
// Fully primitive int-to-int map
378
Int2IntMap countMap = new Int2IntOpenHashMap();
379
countMap.defaultReturnValue(0);   // Return 0 for missing keys
380
countMap.put(42, 5);              // Both key and value are primitive
381
int count = countMap.get(42);     // Direct primitive access
382
int missing = countMap.get(99);   // Returns 0 (default)
383

384
// Increment counter without boxing
385
countMap.put(42, countMap.get(42) + 1); // All primitive operations
386
```
387

388
### Type-Specific Functions
389

390
Functional interfaces for primitive-to-primitive and primitive-to-object mappings.
391

392
```java { .api }
393
/**
394
 * Function mapping int to int
395
 */
396
@FunctionalInterface
397
public interface Int2IntFunction extends Function<Integer, Integer> {
398
    /**
399
     * Apply function to int value without boxing
400
     * @param key the int input
401
     * @return the int output
402
     */
403
    int get(int key);
404
    
405
    /**
406
     * Get default return value for undefined inputs
407
     * @return the default return value
408
     */
409
    int defaultReturnValue();
410
    
411
    /**
412
     * Set default return value for undefined inputs
413
     * @param rv the new default return value
414
     */
415
    void defaultReturnValue(int rv);
416
}
417

418
/**
419
 * Function mapping int to Object
420
 * @param <V> the type of output values
421
 */
422
@FunctionalInterface
423
public interface Int2ObjectFunction<V> extends Function<Integer, V> {
424
    /**
425
     * Apply function to int value without boxing
426
     * @param key the int input
427
     * @return the output value
428
     */
429
    V get(int key);
430
}
431

432
/**
433
 * Function mapping Object to int
434
 * @param <K> the type of input keys
435
 */
436
@FunctionalInterface  
437
public interface Object2IntFunction<K> extends Function<K, Integer> {
438
    /**
439
     * Apply function to get int result without boxing
440
     * @param key the input
441
     * @return the int output
442
     */
443
    int getInt(K key);
444
    
445
    /**
446
     * Get default return value for undefined inputs
447
     * @return the default return value
448
     */
449
    int defaultReturnValue();
450
    
451
    /**
452
     * Set default return value for undefined inputs
453
     * @param rv the new default return value
454
     */
455
    void defaultReturnValue(int rv);
456
}
457

458
// All primitive type combinations are available:
459
// Long2LongFunction, Double2DoubleFunction, Char2IntFunction, etc.
460
```
461

462
### Type-Specific Iterators and Comparators
463

464
Specialized iterators and comparators for primitive types, avoiding boxing during iteration and comparison.
465

466
```java { .api }
467
/**
468
 * Iterator specialized for int values
469
 */
470
public interface IntIterator extends Iterator<Integer> {
471
    /**
472
     * Get next int value without boxing
473
     * @return the next int value
474
     */
475
    int nextInt();
476
    
477
    /**
478
     * Skip next n elements efficiently
479
     * @param n number of elements to skip
480
     * @return number of elements actually skipped
481
     */
482
    default int skip(int n) {
483
        int i = 0;
484
        while (i < n && hasNext()) {
485
            nextInt();
486
            i++;
487
        }
488
        return i;
489
    }
490
}
491

492
/**
493
 * List iterator specialized for int values
494
 */  
495
public interface IntListIterator extends IntIterator, ListIterator<Integer> {
496
    /**
497
     * Get previous int value without boxing
498
     * @return the previous int value
499
     */
500
    int previousInt();
501
    
502
    /**
503
     * Set current int value without boxing
504
     * @param k the int value to set
505
     */
506
    void set(int k);
507
    
508
    /**
509
     * Add int value at current position without boxing
510
     * @param k the int value to add
511
     */
512
    void add(int k);
513
}
514

515
/**
516
 * Comparator specialized for int values
517
 */
518
@FunctionalInterface
519
public interface IntComparator extends Comparator<Integer> {
520
    /**
521
     * Compare two int values without boxing
522
     * @param k1 first int value
523
     * @param k2 second int value
524
     * @return comparison result
525
     */
526
    int compare(int k1, int k2);
527
    
528
    /**
529
     * Get natural order comparator for int values
530
     * @return IntComparator using natural ordering
531
     */
532
    static IntComparator naturalOrder() {
533
        return Integer::compare;
534
    }
535
    
536
    /**
537
     * Get reverse order comparator for int values
538
     * @return IntComparator using reverse ordering
539
     */
540
    static IntComparator reverseOrder() {
541
        return (a, b) -> Integer.compare(b, a);
542
    }
543
}
544

545
// Similar specialized iterators and comparators exist for all primitive types:
546
// LongIterator, DoubleIterator, FloatIterator, etc.  
547
// LongComparator, DoubleComparator, FloatComparator, etc.
548
```
549

550
**Usage Examples:**
551

552
```java
553
import it.unimi.dsi.fastutil.ints.*;
554

555
// Efficient iteration without boxing
556
IntList numbers = new IntArrayList();
557
numbers.add(10);
558
numbers.add(20);
559
numbers.add(30);
560

561
IntIterator iter = numbers.iterator();
562
while (iter.hasNext()) {
563
    int value = iter.nextInt(); // No boxing overhead
564
    System.out.println(value);
565
}
566

567
// Custom comparator for reverse order
568
IntComparator reverse = (a, b) -> Integer.compare(b, a);
569
numbers.sort(reverse); // Sorts in descending order
570

571
// Efficient skipping
572
IntIterator skipIter = numbers.iterator();
573
int skipped = skipIter.skip(2); // Skip first 2 elements efficiently
574
if (skipIter.hasNext()) {
575
    int value = skipIter.nextInt(); // Get 3rd element
576
}
577
```
578

579
## Implementation Classes
580

581
Each primitive type package provides multiple implementation classes optimized for different use cases:
582

583
### Array-Based Implementations
584
- **`IntArrayList`**, **`LongArrayList`**, etc. - Dynamic arrays with primitive storage
585
- **`IntArraySet`**, **`LongArraySet`**, etc. - Sets backed by sorted arrays
586

587
### Hash-Based Implementations  
588
- **`IntOpenHashSet`**, **`LongOpenHashSet`**, etc. - Open addressing hash sets
589
- **`Int2ObjectOpenHashMap`**, **`Long2IntOpenHashMap`**, etc. - Open addressing hash maps
590

591
### Tree-Based Implementations
592
- **`IntAVLTreeSet`**, **`LongAVLTreeSet`**, etc. - AVL tree sorted sets
593
- **`IntRBTreeSet`**, **`LongRBTreeSet`**, etc. - Red-black tree sorted sets
594

595
### Specialized Implementations
596
- **`IntLinkedOpenHashSet`** - Hash set maintaining insertion order
597
- **`Int2IntLinkedOpenHashMap`** - Hash map maintaining insertion order
598

599
Each implementation is optimized for specific usage patterns while maintaining the same interface, allowing easy switching between implementations based on performance requirements.