0
# Core Utilities
1

2
Foundation interfaces, utility classes, and abstract base classes that provide common functionality across all FastUtil collections. These components form the infrastructure that supports all type-specific implementations.
3

4
## Capabilities
5

6
### Function Interface
7

8
High-performance mapping interface extending Java's standard Function with additional optimized methods.
9

10
```java { .api }
11
/**
12
 * Maps keys to values, optimized for high-performance implementations
13
 * @param <K> the type of keys
14
 * @param <V> the type of values
15
 */
16
public interface Function<K,V> extends java.util.function.Function<K,V> {
17
    /** Returns the value associated with the given key */
18
    V get(Object key);
19
    
20
    /** Returns the value for key, or defaultValue if not present */
21
    V getOrDefault(Object key, V defaultValue);
22
    
23
    /** Associates the value with the key (optional operation) */  
24
    V put(K key, V value);
25
    
26
    /** Removes the mapping for the key (optional operation) */
27
    V remove(Object key);
28
    
29
    /** Returns true if this function contains a mapping for the key */
30
    boolean containsKey(Object key);
31
    
32
    /** Returns the number of key-value mappings, or -1 if unlimited */
33
    int size();
34
    
35
    /** Removes all mappings (optional operation) */
36
    void clear();
37
}
38
```
39

40
**Usage Examples:**
41

42
```java
43
import it.unimi.dsi.fastutil.Function;
44
import java.util.Map;
45
import java.util.HashMap;
46

47
// Custom function implementation
48
Function<String, Integer> wordLength = new Function<String, Integer>() {
49
    private Map<String, Integer> cache = new HashMap<>();
50
    
51
    public Integer get(Object key) {
52
        return cache.computeIfAbsent((String) key, String::length);
53
    }
54
    
55
    public boolean containsKey(Object key) {
56
        return key instanceof String;
57
    }
58
};
59

60
int length = wordLength.get("hello"); // Returns 5
61
```
62

63
### Arrays Utility Class
64

65
Static methods for array operations and generic sorting algorithms that work with any swappable data structure.
66

67
```java { .api }
68
/**
69
 * Utility class providing array operations and generic sorting algorithms
70
 */
71
public class Arrays {
72
    /** Maximum safe array size */
73
    public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
74
    
75
    /**
76
     * Ensures that the range [from, to) is valid for an array of given length
77
     * @param arrayLength the length of the array
78
     * @param from the start index (inclusive)
79
     * @param to the end index (exclusive)
80
     * @throws IllegalArgumentException if the range is invalid
81
     */
82
    public static void ensureFromTo(int arrayLength, int from, int to);
83
    
84
    /**
85
     * Ensures that offset and length are valid for an array of given length
86
     * @param arrayLength the length of the array
87
     * @param offset the starting offset
88
     * @param length the number of elements
89
     * @throws IllegalArgumentException if parameters are invalid
90
     */
91
    public static void ensureOffsetLength(int arrayLength, int offset, int length);
92
    
93
    /**
94
     * Stable in-place merge sort using a comparator and swapper
95
     * @param from the start index (inclusive)
96
     * @param to the end index (exclusive)
97
     * @param c the comparator
98
     * @param swapper the swapper for element exchanges
99
     */
100
    public static void mergeSort(int from, int to, IntComparator c, Swapper swapper);
101
    
102
    /**
103
     * Generic quicksort using a comparator and swapper
104
     * @param from the start index (inclusive)
105
     * @param to the end index (exclusive)
106
     * @param comp the comparator
107
     * @param swapper the swapper for element exchanges
108
     */
109
    public static void quickSort(int from, int to, IntComparator comp, Swapper swapper);
110
    
111
    /**
112
     * Parallel quicksort using a comparator and swapper
113
     * @param from the start index (inclusive)
114
     * @param to the end index (exclusive) 
115
     * @param comp the comparator
116
     * @param swapper the swapper for element exchanges
117
     */
118
    public static void parallelQuickSort(int from, int to, IntComparator comp, Swapper swapper);
119
}
120
```
121

122
**Usage Examples:**
123

124
```java
125
import it.unimi.dsi.fastutil.Arrays;
126
import it.unimi.dsi.fastutil.Swapper;
127

128
// Custom data structure sorting
129
String[] names = {"Charlie", "Alice", "Bob"};
130
Arrays.quickSort(0, names.length, 
131
    (i, j) -> names[i].compareTo(names[j]),
132
    (i, j) -> { String temp = names[i]; names[i] = names[j]; names[j] = temp; });
133
// Result: names = ["Alice", "Bob", "Charlie"]
134
```
135

136
### Hash Interface and Utilities
137

138
Constants and strategy interfaces for hash-based data structures, providing customizable hashing behavior.
139

140
```java { .api }
141
/**
142
 * Interface providing constants and strategy for hash-based data structures
143
 */
144
public interface Hash {
145
    /** Default initial capacity for hash structures */
146
    int DEFAULT_INITIAL_SIZE = 16;
147
    
148
    /** Default load factor balancing space and time */
149
    float DEFAULT_LOAD_FACTOR = 0.75f;
150
    
151
    /** Fast load factor for speed-optimized structures */
152
    float FAST_LOAD_FACTOR = 0.5f;
153
    
154
    /** Very fast load factor for maximum speed */
155
    float VERY_FAST_LOAD_FACTOR = 0.25f;
156
    
157
    /**
158
     * Custom hash strategy for objects
159
     * @param <K> the type of keys
160
     */
161
    interface Strategy<K> {
162
        /** Compute hash code for the object */
163
        int hashCode(K o);
164
        
165
        /** Test equality between two objects */
166
        boolean equals(K a, K b);
167
    }
168
}
169

170
/**
171
 * Utility class providing common hash methods
172
 */
173
public class HashCommon {
174
    /**
175
     * MurmurHash3 finalization step for avalanching bits
176
     * @param x the value to hash
177
     * @return the finalized hash value
178
     */
179
    public static int murmurHash3(int x);
180
    
181
    // Additional hash methods for other primitive types
182
    public static int murmurHash3(long x);
183
    public static int murmurHash3(float x);
184
    public static int murmurHash3(double x);
185
}
186
```
187

188
### Safe Math Conversions
189

190
Safe conversions between primitive types with overflow checking to prevent silent data loss.
191

192
```java { .api }
193
/**
194
 * Utility class for safe conversions between primitive types
195
 */
196
public final class SafeMath {
197
    /**
198
     * Safely convert int to char, throwing exception on overflow
199
     * @param value the int value to convert
200
     * @return the char value
201
     * @throws IllegalArgumentException if value is outside char range
202
     */
203
    public static char safeIntToChar(int value);
204
    
205
    /**
206
     * Safely convert int to byte, throwing exception on overflow
207
     * @param value the int value to convert
208
     * @return the byte value
209
     * @throws IllegalArgumentException if value is outside byte range
210
     */
211
    public static byte safeIntToByte(int value);
212
    
213
    /**
214
     * Safely convert int to short, throwing exception on overflow
215
     * @param value the int value to convert
216
     * @return the short value
217
     * @throws IllegalArgumentException if value is outside short range
218
     */
219
    public static short safeIntToShort(int value);
220
    
221
    /**
222
     * Safely convert long to int, throwing exception on overflow
223
     * @param value the long value to convert
224
     * @return the int value
225
     * @throws IllegalArgumentException if value is outside int range
226
     */
227
    public static int safeLongToInt(long value);
228
    
229
    /**
230
     * Safely convert long to char, throwing exception on overflow
231
     * @param value the long value to convert
232
     * @return the char value
233
     * @throws IllegalArgumentException if value is outside char range
234
     */
235
    public static char safeLongToChar(long value);
236
    
237
    /**
238
     * Safely convert long to byte, throwing exception on overflow
239
     * @param value the long value to convert
240
     * @return the byte value
241
     * @throws IllegalArgumentException if value is outside byte range
242
     */
243
    public static byte safeLongToByte(long value);
244
    
245
    /**
246
     * Safely convert long to short, throwing exception on overflow
247
     * @param value the long value to convert
248
     * @return the short value
249
     * @throws IllegalArgumentException if value is outside short range
250
     */
251
    public static short safeLongToShort(long value);
252
    
253
    /**
254
     * Safely convert double to float, throwing exception on overflow
255
     * @param value the double value to convert
256
     * @return the float value
257
     * @throws IllegalArgumentException if value is outside float range
258
     */
259
    public static float safeDoubleToFloat(double value);
260
}
261
```
262

263
### Swapper Interfaces
264

265
Functional interfaces for swapping elements at specified positions, enabling generic sorting algorithms.
266

267
```java { .api }
268
/**
269
 * Functional interface for swapping elements at integer positions
270
 */
271
@FunctionalInterface
272
public interface Swapper {
273
    /**
274
     * Swap elements at positions a and b
275
     * @param a first position
276
     * @param b second position
277
     */
278
    void swap(int a, int b);
279
}
280

281
/**
282
 * Functional interface for swapping elements at 64-bit positions
283
 */  
284
@FunctionalInterface
285
public interface BigSwapper {
286
    /**
287
     * Swap elements at 64-bit positions a and b
288
     * @param a first position
289
     * @param b second position
290
     */
291
    void swap(long a, long b);
292
}
293
```
294

295
### Iterator Interfaces
296

297
Enhanced iterator interfaces supporting bidirectional traversal and big data navigation.
298

299
```java { .api }
300
/**
301
 * Iterator supporting both forward and backward traversal
302
 * @param <K> the type of elements
303
 */
304
public interface BidirectionalIterator<K> extends Iterator<K> {
305
    /**
306
     * Get the previous element in the iteration
307
     * @return the previous element
308
     * @throws NoSuchElementException if no previous element
309
     */
310
    K previous();
311
    
312
    /**
313
     * Check if there is a previous element
314
     * @return true if there is a previous element
315
     */
316
    boolean hasPrevious();
317
}
318

319
/**
320
 * Bidirectional iterator for BigList with 64-bit indices
321
 * @param <K> the type of elements  
322
 */
323
public interface BigListIterator<K> extends BidirectionalIterator<K> {
324
    /**
325
     * Get the next index as a long value
326
     * @return the next index
327
     */
328
    long nextIndex();
329
    
330
    /**
331
     * Get the previous index as a long value
332
     * @return the previous index
333
     */
334
    long previousIndex();
335
    
336
    /**
337
     * Add an element at the current position
338
     * @param k the element to add
339
     */
340
    void add(K k);
341
    
342
    /**
343
     * Set the element at the current position
344
     * @param k the element to set
345
     */
346
    void set(K k);
347
}
348
```
349

350
### Pair Interface
351

352
Generic pair interface providing multiple access patterns for paired elements.
353

354
```java { .api }
355
/**
356
 * Generic pair of elements with multiple access patterns
357
 * @param <L> type of left element
358
 * @param <R> type of right element
359
 */
360
public interface Pair<L,R> {
361
    /** Get the left element */
362
    L left();
363
    
364
    /** Get the right element */
365
    R right();
366
    
367
    /** Set the left element (optional operation) */
368
    Pair<L,R> left(L l);
369
    
370
    /** Set the right element (optional operation) */
371
    Pair<L,R> right(R r);
372
    
373
    // Alternative accessors
374
    /** Alias for left() */
375
    default L first() { return left(); }
376
    
377
    /** Alias for right() */
378
    default R second() { return right(); }
379
    
380
    /** Alias for left() when used as key-value pair */
381
    default L key() { return left(); }
382
    
383
    /** Alias for right() when used as key-value pair */
384
    default R value() { return right(); }
385
}
386

387
/**
388
 * Pair where left element is always ≤ right element
389
 * @param <K> type of elements (must be Comparable)
390
 */
391
public interface SortedPair<K> extends Pair<K,K>, Comparable<SortedPair<? extends K>> {
392
    /**
393
     * Create a sorted pair ensuring left ≤ right
394
     * @param l first element
395
     * @param r second element  
396
     * @return sorted pair with smaller element as left
397
     */
398
    static <K extends Comparable<K>> SortedPair<K> of(K l, K r);
399
}
400
```
401

402
**Usage Examples:**
403

404
```java
405
import it.unimi.dsi.fastutil.Pair;
406
import it.unimi.dsi.fastutil.SortedPair;
407

408
// Using pairs for coordinate representation
409
Pair<Integer, Integer> coordinate = Pair.of(10, 20);
410
int x = coordinate.first(); // or coordinate.left()
411
int y = coordinate.second(); // or coordinate.right()
412

413
// Using sorted pairs
414
SortedPair<Integer> range = SortedPair.of(100, 50);
415
int min = range.left(); // 50 (smaller value)
416
int max = range.right(); // 100 (larger value)
417
```