0
# FastUtil
1
2
FastUtil extends the Java Collections Framework by providing type-specific maps, sets, lists, and queues with a small memory footprint and fast access and insertion. It offers both primitive-optimized collections avoiding boxing/unboxing overhead and big (64-bit) arrays, sets and lists, sorting algorithms, fast I/O classes for binary and text files, and facilities for memory mapping large files.
3
4
## Package Information
5
6
- **Package Name**: it.unimi.dsi:fastutil
7
- **Package Type**: maven
8
- **Language**: Java
9
- **Installation**: Add to Maven dependencies:
10
```xml
11
<dependency>
12
<groupId>it.unimi.dsi</groupId>
13
<artifactId>fastutil</artifactId>
14
<version>8.5.16</version>
15
</dependency>
16
```
17
18
## Core Imports
19
20
```java
21
import it.unimi.dsi.fastutil.*;
22
```
23
24
For specific functionality:
25
26
```java
27
import it.unimi.dsi.fastutil.ints.*;
28
import it.unimi.dsi.fastutil.longs.*;
29
import it.unimi.dsi.fastutil.objects.*;
30
import it.unimi.dsi.fastutil.io.*;
31
```
32
33
## Basic Usage
34
35
```java
36
import it.unimi.dsi.fastutil.ints.*;
37
import it.unimi.dsi.fastutil.objects.*;
38
39
// Type-specific collections for primitives
40
IntList numbers = new IntArrayList();
41
numbers.add(42);
42
numbers.add(24);
43
44
// Big collections for large datasets
45
BigList<String> bigData = new ObjectBigArrayBigList<>();
46
bigData.add("item1");
47
bigData.add("item2");
48
49
// Fast I/O operations
50
FastBufferedInputStream input = new FastBufferedInputStream(
51
new FileInputStream("data.bin"));
52
byte[] buffer = new byte[1024];
53
int bytesRead = input.read(buffer);
54
```
55
56
## Architecture
57
58
FastUtil is organized around several key design principles:
59
60
- **Type-Specific Collections**: Separate collection implementations for each primitive type (int, long, double, etc.) to avoid boxing/unboxing overhead
61
- **Big Data Structures**: Collections supporting 64-bit indices for datasets exceeding 2^31 elements
62
- **Bidirectional Navigation**: Enhanced iterators supporting both forward and backward traversal
63
- **Performance Optimization**: Unsynchronized implementations prioritizing speed over thread safety
64
- **Unified Interface**: All collections implement standard Java collection interfaces while providing additional optimized methods
65
66
## Capabilities
67
68
### Core Utilities and Interfaces
69
70
Foundation interfaces, utility classes, and abstract base classes that provide common functionality across all FastUtil collections.
71
72
```java { .api }
73
public interface Function<K,V> extends java.util.function.Function<K,V> {
74
V get(Object key);
75
V put(K key, V value);
76
boolean containsKey(Object key);
77
int size();
78
}
79
80
public interface BigList<K> extends Collection<K>, Size64 {
81
K get(long index);
82
K set(long index, K element);
83
void add(long index, K element);
84
K remove(long index);
85
long size64();
86
}
87
88
public class Arrays {
89
public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
90
public static void mergeSort(int from, int to, IntComparator c, Swapper swapper);
91
public static void quickSort(int from, int to, IntComparator comp, Swapper swapper);
92
public static void parallelQuickSort(int from, int to, IntComparator comp, Swapper swapper);
93
}
94
```
95
96
[Core Utilities](./core-utilities.md)
97
98
### Type-Specific Collections
99
100
High-performance primitive collections for int, long, double, float, char, short, byte, and boolean types, avoiding boxing/unboxing overhead.
101
102
```java { .api }
103
// Example interfaces for type-specific collections
104
public interface IntList extends List<Integer> {
105
int getInt(int index);
106
int set(int index, int k);
107
void add(int index, int k);
108
int removeInt(int index);
109
}
110
111
public interface IntSet extends Set<Integer> {
112
boolean add(int k);
113
boolean contains(int k);
114
boolean remove(int k);
115
}
116
117
public interface Int2ObjectMap<V> extends Map<Integer, V> {
118
V put(int key, V value);
119
V get(int key);
120
V remove(int key);
121
boolean containsKey(int key);
122
}
123
```
124
125
[Type-Specific Collections](./type-specific-collections.md)
126
127
### Big Data Structures
128
129
Collections with 64-bit indices supporting datasets larger than 2^31 elements, including big arrays, lists, and sets.
130
131
```java { .api }
132
public interface BigArrays {
133
public static final long SEGMENT_SIZE = 1L << 27;
134
public static final int SEGMENT_SHIFT = 27;
135
public static final int SEGMENT_MASK = (1 << 27) - 1;
136
}
137
138
public interface BigSwapper {
139
void swap(long a, long b);
140
}
141
142
public interface Size64 {
143
long size64();
144
default int size() { return (int) Math.min(size64(), Integer.MAX_VALUE); }
145
}
146
```
147
148
[Big Data Structures](./big-data-structures.md)
149
150
### High-Performance I/O
151
152
Fast, repositionable stream implementations with measurement capabilities for efficient binary and text file operations.
153
154
```java { .api }
155
public interface MeasurableStream {
156
long length() throws IOException;
157
long position() throws IOException;
158
}
159
160
public interface RepositionableStream {
161
void position(long newPosition) throws IOException;
162
long position() throws IOException;
163
}
164
165
public class FastBufferedInputStream extends MeasurableInputStream
166
implements RepositionableStream {
167
public FastBufferedInputStream(InputStream is);
168
public FastBufferedInputStream(InputStream is, int bufSize);
169
}
170
```
171
172
[High-Performance I/O](./io-streams.md)
173
174
### Priority Queues and Stacks
175
176
Specialized priority queue implementations including indirect priority queues and stack interfaces.
177
178
```java { .api }
179
public interface PriorityQueue<K> {
180
void enqueue(K x);
181
K dequeue();
182
K first();
183
boolean isEmpty();
184
int size();
185
Comparator<? super K> comparator();
186
}
187
188
public interface IndirectPriorityQueue {
189
void enqueue(int x);
190
int dequeue();
191
int first();
192
boolean contains(int index);
193
}
194
195
public interface Stack<K> {
196
void push(K o);
197
K pop();
198
boolean isEmpty();
199
}
200
```
201
202
[Priority Queues and Stacks](./priority-queues-stacks.md)
203
204
## Types
205
206
```java { .api }
207
public interface Hash {
208
int DEFAULT_INITIAL_SIZE = 16;
209
float DEFAULT_LOAD_FACTOR = 0.75f;
210
float FAST_LOAD_FACTOR = 0.5f;
211
float VERY_FAST_LOAD_FACTOR = 0.25f;
212
213
interface Strategy<K> {
214
int hashCode(K o);
215
boolean equals(K a, K b);
216
}
217
}
218
219
public interface BidirectionalIterator<K> extends Iterator<K> {
220
K previous();
221
boolean hasPrevious();
222
}
223
224
public interface BigListIterator<K> extends BidirectionalIterator<K> {
225
long nextIndex();
226
long previousIndex();
227
void add(K k);
228
void set(K k);
229
}
230
231
public interface Pair<L,R> {
232
L left();
233
R right();
234
Pair<L,R> left(L l);
235
Pair<L,R> right(R r);
236
237
// Alternative accessors
238
default L first() { return left(); }
239
default R second() { return right(); }
240
default L key() { return left(); }
241
default R value() { return right(); }
242
}
243
244
@FunctionalInterface
245
public interface Swapper {
246
void swap(int a, int b);
247
}
248
249
@FunctionalInterface
250
public interface BigSwapper {
251
void swap(long a, long b);
252
}
253
254
public final class SafeMath {
255
public static char safeIntToChar(int value);
256
public static byte safeIntToByte(int value);
257
public static short safeIntToShort(int value);
258
public static int safeLongToInt(long value);
259
public static float safeDoubleToFloat(double value);
260
}
261
```