or run

npx @tessl/cli init
Log in

Version

Tile

Overview

Evals

Files

docs

big-data-structures.mdcore-utilities.mdindex.mdio-streams.mdpriority-queues-stacks.mdtype-specific-collections.md
tile.json

tessl/maven-it-unimi-dsi--fastutil

High-performance type-specific collections extending the Java Collections Framework with memory-efficient primitive containers and big data structures.

Workspace
tessl
Visibility
Public
Created
Last updated
Describes
mavenpkg:maven/it.unimi.dsi/fastutil@8.5.x

To install, run

npx @tessl/cli install tessl/maven-it-unimi-dsi--fastutil@8.5.0

index.mddocs/

FastUtil

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.

Package Information

  • Package Name: it.unimi.dsi:fastutil
  • Package Type: maven
  • Language: Java
  • Installation: Add to Maven dependencies: 
    <dependency>
  <groupId>it.unimi.dsi</groupId>
  <artifactId>fastutil</artifactId>
  <version>8.5.16</version>
</dependency>

Core Imports

import it.unimi.dsi.fastutil.*;

For specific functionality:

import it.unimi.dsi.fastutil.ints.*;
import it.unimi.dsi.fastutil.longs.*;
import it.unimi.dsi.fastutil.objects.*;
import it.unimi.dsi.fastutil.io.*;

Basic Usage

import it.unimi.dsi.fastutil.ints.*;
import it.unimi.dsi.fastutil.objects.*;

// Type-specific collections for primitives
IntList numbers = new IntArrayList();
numbers.add(42);
numbers.add(24);

// Big collections for large datasets
BigList<String> bigData = new ObjectBigArrayBigList<>();
bigData.add("item1");
bigData.add("item2");

// Fast I/O operations
FastBufferedInputStream input = new FastBufferedInputStream(
    new FileInputStream("data.bin"));
byte[] buffer = new byte[1024];
int bytesRead = input.read(buffer);

Architecture

FastUtil is organized around several key design principles:

  • Type-Specific Collections: Separate collection implementations for each primitive type (int, long, double, etc.) to avoid boxing/unboxing overhead
  • Big Data Structures: Collections supporting 64-bit indices for datasets exceeding 2^31 elements
  • Bidirectional Navigation: Enhanced iterators supporting both forward and backward traversal
  • Performance Optimization: Unsynchronized implementations prioritizing speed over thread safety
  • Unified Interface: All collections implement standard Java collection interfaces while providing additional optimized methods

Capabilities

Core Utilities and Interfaces

Foundation interfaces, utility classes, and abstract base classes that provide common functionality across all FastUtil collections.

public interface Function<K,V> extends java.util.function.Function<K,V> {
    V get(Object key);
    V put(K key, V value);
    boolean containsKey(Object key);
    int size();
}

public interface BigList<K> extends Collection<K>, Size64 {
    K get(long index);
    K set(long index, K element);
    void add(long index, K element);
    K remove(long index);
    long size64();
}

public class Arrays {
    public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    public static void mergeSort(int from, int to, IntComparator c, Swapper swapper);
    public static void quickSort(int from, int to, IntComparator comp, Swapper swapper);
    public static void parallelQuickSort(int from, int to, IntComparator comp, Swapper swapper);
}

Core Utilities

Type-Specific Collections

High-performance primitive collections for int, long, double, float, char, short, byte, and boolean types, avoiding boxing/unboxing overhead.

// Example interfaces for type-specific collections
public interface IntList extends List<Integer> {
    int getInt(int index);
    int set(int index, int k);
    void add(int index, int k);
    int removeInt(int index);
}

public interface IntSet extends Set<Integer> {
    boolean add(int k);
    boolean contains(int k);
    boolean remove(int k);
}

public interface Int2ObjectMap<V> extends Map<Integer, V> {
    V put(int key, V value);
    V get(int key);
    V remove(int key);
    boolean containsKey(int key);
}

Type-Specific Collections

Big Data Structures

Collections with 64-bit indices supporting datasets larger than 2^31 elements, including big arrays, lists, and sets.

public interface BigArrays {
    public static final long SEGMENT_SIZE = 1L << 27;
    public static final int SEGMENT_SHIFT = 27;
    public static final int SEGMENT_MASK = (1 << 27) - 1;
}

public interface BigSwapper {
    void swap(long a, long b);
}

public interface Size64 {
    long size64();
    default int size() { return (int) Math.min(size64(), Integer.MAX_VALUE); }
}

Big Data Structures

High-Performance I/O

Fast, repositionable stream implementations with measurement capabilities for efficient binary and text file operations.

public interface MeasurableStream {
    long length() throws IOException;
    long position() throws IOException;
}

public interface RepositionableStream {
    void position(long newPosition) throws IOException;
    long position() throws IOException;
}

public class FastBufferedInputStream extends MeasurableInputStream 
    implements RepositionableStream {
    public FastBufferedInputStream(InputStream is);
    public FastBufferedInputStream(InputStream is, int bufSize);
}

High-Performance I/O

Priority Queues and Stacks

Specialized priority queue implementations including indirect priority queues and stack interfaces.

public interface PriorityQueue<K> {
    void enqueue(K x);
    K dequeue();
    K first();
    boolean isEmpty();
    int size();
    Comparator<? super K> comparator();
}

public interface IndirectPriorityQueue {
    void enqueue(int x);
    int dequeue();
    int first();
    boolean contains(int index);
}

public interface Stack<K> {
    void push(K o);
    K pop();
    boolean isEmpty();
}

Priority Queues and Stacks

Types

public interface Hash {
    int DEFAULT_INITIAL_SIZE = 16;
    float DEFAULT_LOAD_FACTOR = 0.75f;
    float FAST_LOAD_FACTOR = 0.5f;
    float VERY_FAST_LOAD_FACTOR = 0.25f;
    
    interface Strategy<K> {
        int hashCode(K o);
        boolean equals(K a, K b);
    }
}

public interface BidirectionalIterator<K> extends Iterator<K> {
    K previous();
    boolean hasPrevious();
}

public interface BigListIterator<K> extends BidirectionalIterator<K> {
    long nextIndex();
    long previousIndex();
    void add(K k);
    void set(K k);
}

public interface Pair<L,R> {
    L left();
    R right();
    Pair<L,R> left(L l);
    Pair<L,R> right(R r);
    
    // Alternative accessors
    default L first() { return left(); }
    default R second() { return right(); }
    default L key() { return left(); }
    default R value() { return right(); }
}

@FunctionalInterface
public interface Swapper {
    void swap(int a, int b);
}

@FunctionalInterface  
public interface BigSwapper {
    void swap(long a, long b);
}

public final class SafeMath {
    public static char safeIntToChar(int value);
    public static byte safeIntToByte(int value);
    public static short safeIntToShort(int value);
    public static int safeLongToInt(long value);
    public static float safeDoubleToFloat(double value);
}