Node cache, binary search.

pkg/analysis_server/lib/src/index/lru_cache.dart

+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+library index.lru_cache;
+
+import 'dart:collection';
+
+
+/**
+ * This listener is notified when an item is evicted from the cache.
+ */
+typedef EvictionListener<K, V>(K key, V value);
+
+/**
+ * A hash-table based cache implementation.
+ *
+ * When it reaches the specified number of items, the item that has not been
+ * accessed recently is evicted.
+ */
+class LRUCache<K, V> {

[Brian Wilkerson, 2014/06/10 17:08:29]

There is also an LruCache in angular. Perhaps we should look into generalizing
them...

+  final LinkedHashSet<K> _lastKeys = new LinkedHashSet<K>();
+  final HashMap<K, V> _map = new HashMap<K, V>();
+  final int _maxSize;
+  final EvictionListener _listener;
+
+  LRUCache(this._maxSize, [this._listener]);
+
+  /**
+   * Returns the value for the given [key] or null if [key] is not
+   * in the cache.
+   */
+  V get(K key) {
+    V value = _map[key];
+    if (value != null) {
+      _lastKeys.remove(key);
+      _lastKeys.add(key);
+    }
+    return value;
+  }
+
+  /**
+   * Removes the association for the given [key].
+   */
+  void remove(K key) {
+    _lastKeys.remove(key);
+    _map.remove(key);
+  }
+
+  /**
+   * Associates the [key] with the given [value].
+   *
+   * If the cache is full, an item that has not been accessed recently is
+   * evicted.
+   */
+  void put(K key, V value) {
+    _lastKeys.add(key);
+    if (_lastKeys.length > _maxSize) {
+      K evictedKey = _lastKeys.first;
+      V evictedValue = _map.remove(evictedKey);
+      _lastKeys.remove(evictedKey);
+      if (_listener != null) {
+        _listener(evictedKey, evictedValue);
+      }
+    }
+    _map[key] = value;
+  }
+}