Collections: SortedMap

Bifurcan's SortedMap is an immutable, sorted map implementation based on a Red-Black Tree. It keeps entries sorted by key, allowing for efficient range queries and ordered iteration.

Features

  • Key Ordering: Entries are always sorted according to the key's natural order or a custom Comparator provided at construction.
  • Efficient Lookups: Provides logarithmic time complexity for lookups, insertions, and deletions.
  • Range Queries: Supports efficient slicing and retrieval of entries within a specific key range.
  • Ordered Iteration: Iterating over the map yields entries in sorted key order.

SortedMap is an excellent choice when you need to maintain key order or perform queries based on key ranges.

Basic Usage

import io.lacuna.bifurcan.SortedMap;
import io.lacuna.bifurcan.ISortedMap;

// Create a sorted map with natural ordering of keys
ISortedMap<Integer, String> map = new SortedMap<Integer, String>()
    .put(10, "ten")
    .put(5, "five")
    .put(15, "fifteen");

// Iteration is in sorted order
map.forEach(entry -> System.out.println(entry.key()));
// Output:
// 5
// 10
// 15

// Get a slice of the map
ISortedMap<Integer, String> slice = map.slice(6, 16);
System.out.println(slice);
// Output: {10=ten, 15=fifteen}

// Find floor and ceiling entries
System.out.println(map.floor(12).key());   // 10
System.out.println(map.ceil(12).key());    // 15

Custom Comparator

You can provide a custom Comparator to define a different sort order.

import io.lacuna.bifurcan.SortedMap;
import java.util.Comparator;

// A map sorted in reverse order
SortedMap<Integer, String> reversedMap = new SortedMap<>(Comparator.reverseOrder());
reversedMap = reversedMap.put(10, "ten").put(5, "five");

System.out.println(reversedMap.first().key()); // 10