IndexedMap

A high-performance hybrid data structure that combines the benefits of both Map and List in a single container, providing O(1) lookup by ID, O(1) indexed access, and O(1) index-of-ID resolution while maintaining ordered/indexed access to elements.

Features

• O(1) ID-based lookups - Fast retrieval using unique identifiers
• O(1) indexed access - Direct access by position like a List
• O(1) index-of-ID - Find an item's position by its ID instantly
• Ordered iteration - Maintains insertion/move order
• Configurable duplicate policies - Control how duplicate IDs are handled
• In-place sorting - Sort without losing ID associations
• Bulk operations - addAll and removeWhere for efficient batch work
• Memory efficient - Optimized internal storage with wrapper objects
• Type safe - Full generic type support with compile-time safety

Perfect for

• User lists with fast lookup by user ID
• Chat/message histories with chronological order and ID-based editing
• Product catalogs with sorting and quick lookups
• Cache implementations with insertion order preservation
• Any collection where you need both random access and ordered iteration

Quick Start

import 'package:indexed_map/indexed_map.dart';

// Define your indexable class
class User implements MapIndexable<String> {
  final String id;
  final String name;

  User(this.id, this.name);

  @override
  String get indexId => id;

  @override
  String toString() => 'User($id, $name)';
}

void main() {
  // Create an IndexedMap
  final users = IndexedMap<User, String>();

  // Add users
  users.add(User('u1', 'Alice'));
  users.add(User('u2', 'Bob'));
  users.add(User('u3', 'Carol'));

  // O(1) lookup by ID
  final alice = users.getById('u1');
  print(alice); // User(u1, Alice)

  // O(1) indexed access
  final firstUser = users[0];
  print(firstUser); // User(u1, Alice)

  // O(1) find position by ID
  final position = users.indexOfId('u2');
  print(position); // 1

  // Insert at specific position
  users.insertAt(1, User('u4', 'David'));

  // Move items around
  users.moveIdTo('u1', 3); // Move Alice to position 3

  // Sort while maintaining ID associations
  users.sortBy((a, b) => a.name.compareTo(b.name));

  // Iterate in order
  for (final user in users) {
    print(user);
  }
}

Core Concepts

MapIndexable Interface

Your classes must implement the MapIndexable<I> interface to provide a stable ID:

class Product implements MapIndexable<int> {
  final int id;
  final String name;
  final double price;

  Product(this.id, this.name, this.price);

  @override
  int get indexId => id;  // Must return a stable, unique identifier
}

Duplicate Policies

Control how duplicate IDs are handled:

enum DuplicatePolicy {
  ignore,                 // Keep existing item, ignore new one
  replaceKeepPosition,    // Replace item, keep same position (default)
  replaceMoveToEnd,       // Replace item, move to end (useful for "recent activity")
}

// Example: Recent activity tracking
final activeUsers = IndexedMap<User, String>(
  duplicatePolicy: DuplicatePolicy.replaceMoveToEnd,
);

activeUsers.add(User('alice', 'Alice'));
activeUsers.add(User('bob', 'Bob'));
activeUsers.add(User('alice', 'Alice')); // Alice moves to end

Performance Characteristics

Operation	Time Complexity	Description
add(item)	O(1) amortized	Add to end (new ID)
addAll(items)	O(k) amortized	Add k items
getById(id)	O(1)	Lookup by ID
operator[](index)	O(1)	Access by index
indexOfId(id)	O(1)	Find position of ID
containsId(id)	O(1)	Check if ID exists
contains(item)	O(1)	Check if item exists
insertAt(index, item)	O(n)	Insert at position
removeById(id)	O(n)	Remove by ID
removeAt(index)	O(n)	Remove by index
removeWhere(test)	O(n)	Remove matching items
moveIdTo(id, index)	O(n)	Move item to position
sortBy(comparator)	O(n log n)	In-place sort

Benchmark Results

Based on 10,000 items with 1,000 operations:

Operation	IndexedMap	Alternative
ID Lookup	~0.05ms	Map: ~0.05ms
Index Access	~0.03ms	List: ~0.03ms
ID Lookup (vs Linear)	~0.05ms	List.firstWhere: ~50ms
Combined Ops	~0.08ms	Map+List: ~0.12ms

Run benchmarks: dart run benchmark/indexed_map_benchmark.dart

Common Use Cases

1. Chat Message Management

class Message implements MapIndexable<String> {
  final String id;
  final String content;
  final String senderId;

  Message(this.id, this.content, this.senderId);

  @override
  String get indexId => id;
}

final messages = IndexedMap<Message, String>();

// Add messages in chronological order
messages.add(Message('msg1', 'Hello!', 'alice'));
messages.add(Message('msg2', 'Hi there!', 'bob'));

// Quick edit by ID (e.g., user edited message)
final idx = messages.indexOfId('msg1'); // O(1)
messages[idx] = Message('msg1', 'Hello everyone!', 'alice');

// Insert out-of-order message
messages.insertAt(1, Message('msg3', 'Good morning!', 'carol'));

2. User Activity Tracking

final activeUsers = IndexedMap<User, String>(
  duplicatePolicy: DuplicatePolicy.replaceMoveToEnd,
);

// Users become active (automatically move to end)
activeUsers.add(User('alice', 'Alice'));
activeUsers.add(User('bob', 'Bob'));
activeUsers.add(User('alice', 'Alice')); // Alice moves to end

// Most recently active user
final mostActive = activeUsers.last;

// Activity ranking
for (int i = 0; i < activeUsers.length; i++) {
  print('${i + 1}. ${activeUsers[i].name}');
}

3. Product Catalog with Sorting

final catalog = IndexedMap<Product, int>();

// Add products
catalog.add(Product(1, 'Laptop', 999.99));
catalog.add(Product(2, 'Mouse', 29.99));
catalog.add(Product(3, 'Keyboard', 79.99));

// Sort by price (IDs remain valid)
catalog.sortBy((a, b) => a.price.compareTo(b.price));

// Quick lookup still works after sorting
final laptop = catalog.getById(1);
final laptopPosition = catalog.indexOfId(1); // O(1)

4. Cache with LRU-like Behavior

class CacheItem<T> implements MapIndexable<String> {
  final String key;
  final T value;
  final DateTime accessTime;

  CacheItem(this.key, this.value) : accessTime = DateTime.now();

  @override
  String get indexId => key;
}

final cache = IndexedMap<CacheItem<String>, String>(
  duplicatePolicy: DuplicatePolicy.replaceMoveToEnd,
);

// Access moves item to end (most recently used)
String getValue(String key) {
  final item = cache.getById(key);
  if (item != null) {
    // Re-add to move to end
    cache.add(CacheItem(key, item.value));
    return item.value;
  }
  return loadFromSource(key);
}

API Reference

Construction

// Empty constructor
IndexedMap<T, I>({DuplicatePolicy duplicatePolicy})

// From iterable
IndexedMap<T, I>.fromIterable(Iterable<T> items, {DuplicatePolicy duplicatePolicy})

Core Operations

// Adding items
bool add(T item)
int addAll(Iterable<T> items)
void insertAt(int index, T item)

// Retrieving items
T? getById(I id)
T operator[](int index)
bool containsId(I id)
bool contains(Object? element)   // O(1) by ID
int indexOfId(I id)              // O(1)

// Removing items
T? removeById(I id)
T removeAt(int index)
int removeWhere(bool Function(T) test)
void clear()

// Updating items
void operator[]=(int index, T newItem)
bool upsertKeepingPosition({required I oldId, required T newItem})

// Moving items
bool moveIdTo(I id, int toIndex)

// Sorting
void sortBy(Comparator<T> comparator)

Views and Iteration

// Read-only access
Iterable<T> get values
Iterable<I> get keys
List<T> toList({bool growable = false})
Map<I, T> toMap()
List<ItemWrapper<T, I>> get wrappers
Map<I, ItemWrapper<T, I>> get asMapView

// Properties
int get length
bool get isEmpty
bool get isNotEmpty
T get first
T get last

// Iteration
Iterator<T> get iterator  // Supports for-in loops

Error Handling

// Safe operations that return null / -1 / false
final user = map.getById('nonexistent');   // null
final removed = map.removeById('nonexistent'); // null
final idx = map.indexOfId('nonexistent');   // -1
final moved = map.moveIdTo('nonexistent', 0); // false

// Operations that throw on invalid input
final user = map[999];         // RangeError
final removed = map.removeAt(-1); // RangeError

Testing

Run the comprehensive test suite:

dart test

Benchmarking

Run performance benchmarks:

dart run benchmark/indexed_map_benchmark.dart

Contributing

Contributions are welcome! Please:

1. Report bugs with minimal reproduction cases
2. Suggest features with clear use cases
3. Submit PRs with tests and benchmarks
4. Improve docs and examples

License

MIT License - see LICENSE file for details.

Changelog

See CHANGELOG.md for version history and migration guides.