Core Concepts: Virtual Collections

Bifurcan allows you to create collection implementations that are not backed by data stored in memory, but by pure functions. These virtual collections are extremely memory-efficient and behave just like regular collections, supporting the full IList, ISet, and IMap APIs.

Virtual Lists

A list, at its most fundamental level, is just two things: a size and a function that maps an index to an element. Bifurcan's Lists.from() constructor allows you to create a list from exactly that.

Here's how to create a virtual list containing one million numbers without allocating memory for any of them:

import io.lacuna.bifurcan.IList;
import io.lacuna.bifurcan.Lists;

// Creates a list of numbers from 0 to 999,999
IList<Long> list = Lists.from(1_000_000, i -> i);

System.out.println(list.size());      // Prints 1,000,000
System.out.println(list.nth(500));    // Prints 500
System.out.println(list.nth(999_999)); // Prints 999,999

The list object consumes almost no memory, as the elements are generated on-the-fly whenever nth() is called. All other list operations (adding/removing elements, concatenation, etc.) have efficient default implementations that build on this functional foundation.

Virtual Sets and Maps

Sets and maps can also be defined virtually.

Unsorted Set

An unsorted set is defined by:

  1. A list of its elements (which can itself be virtual).
  2. A function that, given a value, returns an OptionalLong with the index of that element if it exists.
import io.lacuna.bifurcan.*;
import java.util.OptionalLong;
import java.util.function.Function;

IList<Long> list = Lists.from(1_000_000, i -> i);

Function<Long, OptionalLong> indexOf = n -> {
    if (0 <= n && n < list.size()) {
        return OptionalLong.of(n);
    }
    return OptionalLong.empty();
};

ISet<Long> set = Sets.from(list, indexOf);

System.out.println(set.contains(1234L)); // true
System.out.println(set.contains(2_000_000L)); // false

Sorted Set

A sorted set requires:

  1. A list of elements in sorted order.
  2. A Comparator.
  3. A function that, given a value, returns the index of the greatest element less than or equal to it (the "floor index").

Virtual Map

A map is simply a set of keys plus a function that maps a key to a value. You can create a virtual map using Maps.from, or by calling .zip() on an existing set.

import io.lacuna.bifurcan.*;

// Using the virtual set from the previous example
ISet<Long> set = ...;

// Create a map of numbers to their square roots
IMap<Long, Double> squareRoots = set.zip(n -> Math.sqrt(n));

System.out.println(squareRoots.get(144L).get()); // 12.0

Virtual collections are a powerful feature for representing large, well-defined data sets in a memory-efficient way while retaining the rich, functional API of Bifurcan.