LRU cache: Circular linked map

lru_linked_map.dart

/// if true, will pop the last
typedef LRUPolicyTest<K, V> = bool Function(LRULinkedMap lru, _Node<K, V> item);

class _Node<K, V> {
  late K key;
  late V value;
  _Node<K, V>? prev;
  _Node<K, V>? next;
}

class LRULinkedMap<K, V> {
  static LRUPolicyTest<K, V> withCapacity<K, V>(int capacity) => (lru, item) => lru.length >= capacity;
  static LRUPolicyTest<K, V> withInfinite<K, V>() => (lru, item) => false;
  final LRUPolicyTest<K, V> test;
  LRULinkedMap(this.test);

  _Node<K, V>? head;

  bubbleNode(_Node<K, V> node) {
    if (head == node) return;
    if (head != null) {
      node.prev?.next = node.next;
      node.next?.prev = node.prev;
      node.prev = head?.prev;
      node.next = head;
      head?.prev?.next = node;
      head?.prev = node;
    } else {
      node.prev = node;
      node.next = node;
    }
    head = node;
  }

  void removeNode(_Node<K, V> node) {
    if (length == 1) head = null;
    node.prev?.next = node.next;
    node.next?.prev = node.prev;
    if (node == head) head = node.next;
  }

  _Node<K, V>? getNodeByKey(K key) {
    var cur = head;
    do {
      if (cur?.key == key) return cur;
      cur = cur?.next;
    } while (cur != null && cur != head);
    return null;
  }

  _Node<K, V>? get last {
    return head?.prev;
  }

  /// get
  V? get(K key) {
    final found = getNodeByKey(key);
    if (found != null) bubbleNode(found);
    return found?.value;
  }

  /// set
  void set(K key, V value) {
    var item = getNodeByKey(key);
    if (item != null) {
      item.value = value;
    } else {
      item = _Node<K, V>()
        ..key = key
        ..value = value;
      if (test(this, item)) {
        final last = this.last;
        if (last != null) removeNode(last);
      }
    }
    bubbleNode(item);
  }

  /// clear
  void clear(K key) {
    final found = getNodeByKey(key);
    if (found != null) {
      removeNode(found);
    }
  }

  void clearAll() {
    head = null;
  }

  int get length {
    int i = 0;
    var cur = head;
    do {
      if (cur != null) i++;
      cur = cur?.next;
    } while (cur != null && cur != head);
    return i;
  }

  List<_Node<K, V>> getAll() {
    final list = <_Node<K, V>>[];
    var cur = head;
    do {
      if (cur != null) list.add(cur);
      cur = cur?.next;
    } while (cur != null && cur != head);
    return list;
  }

  Map<K, V> toMap() {
    return Map.fromEntries(getAll().map((node) => MapEntry(node.key, node.value)));
  }
}

lru_linked_map_test.dart

import 'package:app_domain/util/lru_linked_map.dart';
import 'package:flutter_test/flutter_test.dart';

void main() {
  test("empty map", () {
    final m = LRULinkedMap<int, dynamic>(LRULinkedMap.withCapacity(5));
    expect(m.head, null);
    expect(m.head, null);
    expect(m.last, null);
    expect(m.length, 0);
    expect(m.get(0), null);
    expect(m.get(1), null);
    expect(m.get(2), null);
    expect(m.get(3), null);
    expect(m.get(4), null);
    expect(m.get(5), null);
    expect(m.get(6), null);
    expect(m.getAll().length, 0);
    expect(m.toMap().length, 0);
  });

  test("length 1", () {
    final m = LRULinkedMap<int, dynamic>(LRULinkedMap.withInfinite());
    m.set(0, 1);
    expect(m.get(0), 1);
    expect(m.head?.value, 1);
    expect(m.last?.value, 1);
    expect(m.length, 1);
    expect(m.getAll().length, 1);
    expect(m.toMap().length, 1);
  });

  test("remove node", () {
    final m = LRULinkedMap<int, dynamic>(LRULinkedMap.withInfinite());
    m.set(0, 1);
    m.removeNode(m.head!);
    expect(m.length, 0);

    m.set(1, 2);
    m.set(2, 3);
    m.removeNode(m.last!);
    expect(m.length, 1);
  });

  test("chain", () {
    final m = LRULinkedMap<int, dynamic>(LRULinkedMap.withInfinite());
    m.set(1, null); // 1
    expect(m.head?.key, 1);
    expect(m.head?.prev?.key, 1);
    expect(m.head?.next?.key, 1);
    expect(m.last?.key, 1);

    m.set(2, null); // 2-1
    expect(m.last?.key, 1);
    expect(m.head?.key, 2);
    expect(m.head?.next?.key, 1);
    expect(m.head?.next?.next, m.head);
    expect(m.head?.prev?.key, 1);
    expect(m.head?.prev?.prev, m.head);
    expect(m.head?.prev?.prev?.prev?.key, 1);

    m.set(3, null); // 3-2-1
    expect(m.head?.key, 3);
    expect(m.head?.next?.key, 2);
    expect(m.head?.next?.next?.key, 1);
    expect(m.head?.next?.next?.next?.key, 3);
    expect(m.head?.next?.next?.next?.next?.key, 2);
    expect(m.head?.next?.next?.next?.next?.next?.key, 1);
    expect(m.head?.prev?.key, 1);
    expect(m.head?.prev?.prev?.key, 2);
    expect(m.head?.prev?.prev?.prev, m.head);
    expect(m.last?.key, 1);

    m.clear(3);
    expect(m.length, 2);
  });

  test("basic get set clear", () {
    final m = LRULinkedMap<String, dynamic>(LRULinkedMap.withInfinite());
    m.set("cache1", "cache1value");
    m.set("cache2", "cache2value");
    expect(m.get("cache1"), "cache1value");
    expect(m.get("cache2"), "cache2value");
    expect(m.get("cache3"), null);

    m.set("cache3", "cache3");
    m.clear("cache3");
    expect(m.get("cache3"), null);

    m.clearAll();
    expect(m.head, null);
    expect(m.head, m.last);
    expect(m.length, 0);
  });

  test("basic get set bubble", () {
    final m = LRULinkedMap<String, dynamic>(LRULinkedMap.withInfinite());
    m.set("cache1", "cache1value");
    m.set("cache2", "cache2value");
    expect(m.length, 2);
    expect(m.get("cache1"), "cache1value");
    expect(m.get("cache2"), "cache2value");
    expect(m.get("cache3"), null);

    m.set("cache3", "cache3");
    expect(m.length, 3);
    expect(m.get("cache1"), "cache1value");
    expect(m.get("cache2"), "cache2value");
    expect(m.get("cache3"), "cache3");
    m.set("cache3", "cache3value");
    expect(m.length, 3);
    expect(m.get("cache3"), "cache3value");
    m.clear("cache3");
    expect(m.length, 2);
    expect(m.get("cache3"), null);

    m.clearAll();
    expect(m.head, null);
    expect(m.head, m.last);
    expect(m.length, 0);
  });

  test("lru policy", () {
    final m = LRULinkedMap<int, dynamic>(LRULinkedMap.withCapacity(2));
    m.set(1, 1);
    m.set(2, 2);
    m.set(3, 3);
    // 3-2-{1:deleted}
    expect(m.get(1), null);
    expect(m.get(2), 2);
    expect(m.get(3), 3);
  });
}