or run

npx @tessl/cli init

Version

Tile

Overview

Evals

Files

docs

index.md

tile.json

tessl/npm-lru_map

Finite key-value map using the Least Recently Used (LRU) algorithm where the most recently used objects are kept in the map while less recently used items are evicted to make room for new ones.

Workspace: tessl
Visibility: Public
Created: 3 months ago
Last updated: 3 months ago
Describes: pkg:npm/lru_map@0.4.x

To install, run

npx @tessl/cli install tessl/npm-lru_map@0.4.0

LRU Map

A doubly linked list-based Least Recently Used (LRU) cache that maintains a finite key-value map where the most recently used items are kept alive while older, less recently used items are evicted to make room for newer items. Provides O(1) complexity for all operations.

Package Information

Package Name: lru_map
Package Type: npm
Language: JavaScript with TypeScript definitions
Installation: npm install lru_map

Core Imports

import { LRUMap } from "lru_map";

For CommonJS:

const { LRUMap } = require("lru_map");

For AMD:

define(["lru_map"], function(lru) {
  const { LRUMap } = lru;
});

Basic Usage

import { LRUMap } from "lru_map";

// Create LRU cache with capacity of 3
const cache = new LRUMap<string, number>(3);

// Add entries
cache.set('adam', 29);
cache.set('john', 26);
cache.set('angela', 24);

console.log(cache.toString()); // "adam:29 < john:26 < angela:24"

// Access entry (moves to most recently used)
const johnAge = cache.get('john'); // 26
console.log(cache.toString()); // "adam:29 < angela:24 < john:26"

// Adding 4th entry evicts oldest
cache.set('zorro', 141);
console.log(cache.toString()); // "angela:24 < john:26 < zorro:141"
// 'adam' was evicted

// Alternative constructor with entries
const cacheFromEntries = new LRUMap([
  ['key1', 'value1'],
  ['key2', 'value2']
]);

Architecture

LRU Map uses a doubly-linked list design for efficient cache management:

Doubly-linked list: Enables O(1) complexity for insertion, deletion, and reordering
Hash map lookup: Internal Map provides O(1) key-to-entry mapping
Head/tail pointers: oldest (head) and newest (tail) entries for efficient eviction
Generic types: Full TypeScript support with LRUMap<K,V>
Map-compatible API: Similar interface to JavaScript's native Map

Capabilities

Construction

Create new LRU cache instances with optional capacity limits and initial entries.

/**
 * Create LRU cache with specified capacity limit
 */
constructor(limit: number, entries?: Iterable<[K,V]>);

/**
 * Convenience constructor equivalent to new LRUMap(count(entries), entries)
 */
constructor(entries: Iterable<[K,V]>);

Core Cache Operations

Essential cache operations for storing, retrieving, and managing entries.

/**
 * Add or update entry and mark as most recently used
 * @param key - Entry key
 * @param value - Entry value
 * @returns This LRUMap instance for chaining
 */
set(key: K, value: V): LRUMap<K,V>;

/**
 * Get value and mark entry as most recently used
 * @param key - Entry key
 * @returns Value if found, undefined otherwise
 */
get(key: K): V | undefined;

/**
 * Check if key exists without affecting usage order
 * @param key - Entry key
 * @returns True if key exists
 */
has(key: K): boolean;

/**
 * Remove entry from cache
 * @param key - Entry key to remove
 * @returns Removed value if found, undefined otherwise
 */
delete(key: K): V | undefined;

/**
 * Remove all entries from cache
 */
clear(): void;

Advanced Access Operations

Additional methods for cache inspection and management.

/**
 * Access value without marking as recently used (peek)
 * @param key - Entry key
 * @returns Value if found, undefined otherwise
 */
find(key: K): V | undefined;

/**
 * Remove and return least recently used entry
 * @returns Tuple of [key, value] or undefined if empty
 */
shift(): [K,V] | undefined;

/**
 * Replace all entries with provided iterable
 * @param entries - Iterable of [key, value] pairs
 */
assign(entries: Iterable<[K,V]>): void;

Iteration and Traversal

Methods for iterating over cache entries in LRU order (oldest to newest).

/**
 * Iterator over keys from oldest to newest
 */
keys(): Iterator<K>;

/**
 * Iterator over values from oldest to newest
 */
values(): Iterator<V>;

/**
 * Iterator over [key, value] pairs from oldest to newest
 */
entries(): Iterator<[K,V]>;

/**
 * Default iterator (same as entries())
 */
[Symbol.iterator](): Iterator<[K,V]>;

/**
 * Execute function for each entry from oldest to newest
 * @param fun - Function to call for each entry
 * @param thisArg - Optional this context
 */
forEach(fun: (value: V, key: K, m: LRUMap<K,V>) => void, thisArg?: any): void;

Serialization

Convert cache contents to standard data formats.

/**
 * Convert to JSON-serializable array
 * @returns Array of {key, value} objects in LRU order
 */
toJSON(): Array<{key: K, value: V}>;

/**
 * Create human-readable string representation
 * @returns String showing entries in LRU order: "key1:value1 < key2:value2"
 */
toString(): string;

Properties

Cache state and configuration properties.

/**
 * Current number of entries (read-only)
 */
readonly size: number;

/**
 * Maximum number of entries allowed
 */
limit: number;

/**
 * Least recently used entry (internal use, may be invalidated)
 */
readonly oldest: Entry<K,V>;

/**
 * Most recently used entry (internal use, may be invalidated)
 */
readonly newest: Entry<K,V>;

Types

/**
 * Entry holds key and value with internal linking pointers
 * Note: Entry objects should not be stored or modified directly
 */
interface Entry<K,V> {
  key: K;
  value: V;
}

Error Handling

Constructor throws Error('overflow') if initial entries exceed the specified limit during assign()
All other methods handle missing keys gracefully by returning undefined
No other exceptions are thrown during normal operation

Advanced Usage Patterns

Custom Eviction Handling:

// Wrap shift method to handle evicted entries
const cache = new LRUMap<string, Resource>(100);
const originalShift = cache.shift.bind(cache);
cache.shift = function() {
  const entry = originalShift();
  if (entry) {
    // Clean up evicted resource
    cleanupResource(entry[1]);
  }
  return entry;
};

Iteration Examples:

// Iterate in LRU order (oldest first)
for (const [key, value] of cache) {
  console.log(`${key}: ${value}`);
}

// Get all keys as array
const allKeys = Array.from(cache.keys());

// Process with forEach
cache.forEach((value, key) => {
  console.log(`Processing ${key}: ${value}`);
});

JSON Serialization:

// Serialize cache state
const serialized = JSON.stringify(cache.toJSON());

// Restore from serialized state
const restored = new LRUMap<string, number>(100);
const data = JSON.parse(serialized);
restored.assign(data.map(item => [item.key, item.value]));