Collections topic

A collection of additional data structures used in and by 2D algorithms.

Sector provides additional common data structures that are used in and by 2D algorithms and not found in the Dart SDK or package:collection. These data structures are not required to use sector but are provided for convenience in building custom algorithms where their performance characteristics are beneficial.

Table of Contents:

Fast Insertion-Order Retained Set and Map

IndexSet and IndexMap provide fast insertion-order retained sets and maps, respectively, with O(1) time complexity for most operations, and are used by many of the data structures and pathfinding algorithms in this package. For example, consider the following:

import 'package:sector/sector.dart';

void main() {
  final set = IndexSet<int>();
  set.add(1);
  set.add(2);
  set.add(3);
  print(set); // {1, 2, 3}

  final map = IndexMap<int, String>();
  map[1] = 'one';
  map[2] = 'two';
  map.entryOf(3).setOrUpdate('three');
  print(map); // {1: 'one', 2: 'two', 3: 'three'}
}

Index collections have most of the same characteristics of LinkedHashSet and LinkedHashMap (outside of removals), but 2-3x faster iteration speed, similar removal speed to HashSet and HashMap, and only somewhat slower insertion speed (~2x of HashSet and HashMap) which is still ~5x faster than LinkedHashSet and LinkedHashMap.

Fast Minimum Priority Queue

FlatQueue is a minimum priority queue that supports O(log n) insertion and removal, and O(1) minimum value retrieval, but exclusively uses 32-bit int keys and 32-bit double priorities associated with each element, making it suitable for BestPathfinder implementations:

import 'package:sector/sector.dart';

void main() {
  final queue = FlatQueue();
  queue.add(3, 1.0);
  queue.add(1, 3.0);
  queue.add(2, 2.0);
  print(queue.removeFirst()); // 3
  print(queue.removeFirst()); // 2
  print(queue.removeFirst()); // 1
}

FlatQueue is used in the A* and Dijkstra pathfinding algorithms.

Fixed Length Iterable

Many of the algorithms in this package return a lazy iterable of fixed length during iteration, which can be useful for performance-sensitive code over the default extends Iterable<E> implementations:

import 'package:sector/sector.dart';

// An iterator over the rows of a grid, with fast random access.
final class GridRows<E> extends FixedLengthIterable<Iterable<E>> {
  const GridRows(this._grid);
  final Grid<E> _grid;

  @override
  int get length => _grid.height;

  @override
  Iterable<E> elementAt(int index) {
    return Iterable.generate(_grid.width, (x) {
      return _grid.getUnchecked(Pos(x, index));
    });
  }
}

Classes

AbsentMapEntry<K, V> Collections
An entry for an absent key-value pair in an IndexMap.
AbsentMapEntry<K, V> Collections
An entry for an absent key-value pair in an IndexMap.
FixedLengthIterable<E> Collections
An Iterable for classes that have an efficient fixed length property.
FixedLengthIterable<E> Collections
An Iterable for classes that have an efficient fixed length property.
FlatQueue Collections
A very fast and tiny binary heap priority queue that stores (int, double).
FlatQueue Collections
A very fast and tiny binary heap priority queue that stores (int, double).
IndexedMapEntry<K, V> Collections
An entry for an present or absent key-value pair in an IndexMap.
IndexedMapEntry<K, V> Collections
An entry for an present or absent key-value pair in an IndexMap.
IndexMap<K, V> Collections
A hash map where element iteration order is independent of their hash codes.
IndexMap<K, V> Collections
A hash map where element iteration order is independent of their hash codes.
IndexSet<E> Collections
A hash set where element iteration order is independent of their hash codes.
IndexSet<E> Collections
A hash set where element iteration order is independent of their hash codes.
PresentMapEntry<K, V> Collections
An entry for a present key-value pair in an IndexMap.
PresentMapEntry<K, V> Collections
An entry for a present key-value pair in an IndexMap.