Roll Observatory packages and add a roll script

quiver/lib/src/collection/lru_map.dart

-// Copyright 2014 Google Inc. All Rights Reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//     http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-part of quiver.collection;
-
-/**
- * An implementation of a [Map] which has a maximum size and uses a (Least
- * Recently Used)[http://en.wikipedia.org/wiki/Cache_algorithms#LRU] algorithm
- * to remove items from the [Map] when the [maximumSize] is reached and new
- * items are added.
- *
- * It is safe to access the [keys] and [values] collections without affecting
- * the "used" ordering - as well as using [forEach]. Other types of access,
- * including bracket, and [putIfAbsent], promotes the key-value pair to the MRU
- * position.
- */
-abstract class LruMap<K, V> implements Map<K, V> {
-  /**
-   * Creates a [LruMap] instance with the default implementation.
-   */
-  factory LruMap({int maximumSize}) = LinkedLruHashMap;
-
-  /**
-   * Maximum size of the [Map]. If [length] exceeds this value at any time,
-   * n entries accessed the earliest are removed, where n is [length] -
-   * [maximumSize].
-   */
-  int maximumSize;
-}
-
-/**
- * Simple implementation of a linked-list entry that contains a [key] and
- * [value].
- */
-class _LinkedEntry<K, V> {
-  K key;
-  V value;
-
-  _LinkedEntry<K, V> next;
-  _LinkedEntry<K, V> previous;
-
-  _LinkedEntry([this.key, this.value]);
-}
-
-/**
- * A linked hash-table based implementation of [LruMap].
- */
-class LinkedLruHashMap<K, V> implements LruMap<K, V> {
-  static const _DEFAULT_MAXIMUM_SIZE = 100;
-
-  final Map<K, _LinkedEntry<K, V>> _entries;
-
-  int _maximumSize;
-
-  _LinkedEntry<K, V> _head;
-  _LinkedEntry<K, V> _tail;
-
-  /**
-   * Create a new LinkedLruHashMap with a [maximumSize].
-   */
-  factory LinkedLruHashMap({int maximumSize}) =>
-      new LinkedLruHashMap._fromMap(new HashMap<K, _LinkedEntry<K, V>>(),
-          maximumSize: maximumSize);
-
-  LinkedLruHashMap._fromMap(
-      this._entries, {
-      int maximumSize})
-          // This pattern is used instead of a default value because we want to
-          // be able to respect null values coming in from MapCache.lru.
-          : _maximumSize = firstNonNull(maximumSize, _DEFAULT_MAXIMUM_SIZE);
-
-  /**
-   * Adds all key-value pairs of [other] to this map.
-   *
-   * The operation is equivalent to doing this[key] = value for each key and
-   * associated value in other. It iterates over other, which must therefore not
-   * change during the iteration.
-   *
-   * If a key of [other] is already in this map, its value is overwritten. If
-   * the number of unique keys is greater than [maximumSize] then the least
-   * recently use keys are evicted. For keys written to by [other], the least
-   * recently user order is determined by [other]'s iteration order.
-   */
-  @override
-  void addAll(Map<K, V> other) => other.forEach((k, v) => this[k] = v);
-
-  @override
-  void clear() {
-    _entries.clear();
-    _head = _tail = null;
-  }
-
-  @override
-  bool containsKey(K key) => _entries.containsKey(key);
-
-  @override
-  bool containsValue(V value) => values.contains(value);
-
-  /**
-   * Applies [action] to each key-value pair of the map in order of MRU to LRU.
-   *
-   * Calling `action` must not add or remove keys from the map.
-   */
-  @override
-  void forEach(void action(K key, V value)) {
-    var head = _head;
-    while (head != null) {
-      action(head.key, head.value);
-      head = head.next;
-    }
-  }
-
-  @override
-  int get length => _entries.length;
-
-  @override
-  bool get isEmpty => _entries.isEmpty;
-
-  @override
-  bool get isNotEmpty => _entries.isNotEmpty;
-
-  /**
-   * Creates an [Iterable] around the entries of the map.
-   */
-  Iterable<_LinkedEntry<K, V>> _iterable() {
-    return new GeneratingIterable<_LinkedEntry<K, V>>(
-        () => _head, (n) => n.next);
-  }
-
-  /**
-   * The keys of [this] - in order of MRU to LRU.
-   *
-   * The returned iterable does *not* have efficient `length` or `contains`.
-   */
-  @override
-  Iterable<K> get keys => _iterable().map((e) => e.key);
-
-  /**
-   * The values of [this] - in order of MRU to LRU.
-   *
-   * The returned iterable does *not* have efficient `length` or `contains`.
-   */
-  @override
-  Iterable<V> get values => _iterable().map((e) => e.value);
-
-  @override
-  int get maximumSize => _maximumSize;
-
-  @override
-  void set maximumSize(int maximumSize) {
-    if (maximumSize == null) throw new ArgumentError.notNull('maximumSize');
-    while (length > maximumSize) {
-      _removeLru();
-    }
-    _maximumSize = maximumSize;
-  }
-
-  /**
-   * Look up the value associated with [key], or add a new value if it isn't
-   * there. The pair is promoted to the MRU position.
-   *
-   * Otherwise calls [ifAbsent] to get a new value, associates [key] to that
-   * [value], and then returns the new [value], with the key-value pair in the
-   * MRU position. If this causes [length] to exceed [maximumSize], then the
-   * LRU position is removed.
-   */
-  @override
-  V putIfAbsent(K key, V ifAbsent()) {
-    final entry =  _entries.putIfAbsent(
-        key, () => _createEntry(key, ifAbsent()));
-    if (length > maximumSize) {
-      _removeLru();
-    }
-    _promoteEntry(entry);
-    return entry.value;
-  }
-
-  /**
-   * Get the value for a [key] in the [Map]. The [key] will be promoted to the
-   * 'Most Recently Used' position. *NOTE*: Calling [] inside an iteration over
-   * keys/values is currently unsupported; use [keys] or [values] if you
-   * need information about entries without modifying their position.
-   */
-  @override
-  V operator[](K key) {
-    final entry = _entries[key];
-    if (entry != null) {
-      _promoteEntry(entry);
-      return entry.value;
-    } else {
-      return null;
-    }
-  }
-
-  /**
-   * If [key] already exists, promotes it to the MRU position & assigns [value].
-   *
-   * Otherwise, adds [key] and [value] to the MRU position.
-   * If [length] exceeds [maximumSize] while adding, removes the LRU position.
-   */
-  @override
-  void operator []=(K key, V value) {
-    // Add this item to the MRU position.
-    _insertMru(_createEntry(key, value));
-
-    // Remove the LRU item if the size would be exceeded by adding this item.
-    if (length > maximumSize) {
-      assert(length == maximumSize + 1);
-      _removeLru();
-    }
-  }
-
-  @override
-  V remove(K key) {
-    final entry = _entries.remove(key);
-    if (entry != null) {
-      if (entry == _head) {
-        _head = _head.next;
-      } else if (entry == _tail) {
-        _tail.previous.next = null;
-        _tail = _tail.previous;
-      } else {
-        entry.previous.next = entry.next;
-      }
-      return entry.value;
-    }
-    return null;
-  }
-
-  @override
-  String toString() => Maps.mapToString(this);
-
-  /**
-   * Moves [entry] to the MRU position, shifting the linked list if necessary.
-   */
-  void _promoteEntry(_LinkedEntry<K, V> entry) {
-    if (entry.previous != null) {
-      // If already existed in the map, link previous to next.
-      entry.previous.next = entry.next;
-
-      // If this was the tail element, assign a new tail.
-      if (_tail == entry) {
-        _tail = entry.previous;
-      }
-    }
-
-    // Replace head with this element.
-    if (_head != null) {
-      _head.previous = entry;
-    }
-    entry.previous = null;
-    entry.next = _head;
-    _head = entry;
-
-    // Add a tail if this is the first element.
-    if (_tail == null) {
-      assert(length == 1);
-      _tail = _head;
-    }
-  }
-
-  /**
-   * Creates and returns an entry from [key] and [value].
-   */
-  _LinkedEntry<K, V> _createEntry(K key, V value) {
-    return new _LinkedEntry<K, V>(key, value);
-  }
-
-  /**
-   * If [entry] does not exist, inserts it into the backing map.
-   * If it does, replaces the existing [_LinkedEntry.value] with [entry.value].
-   * Then, in either case, promotes [entry] to the MRU position.
-   */
-  void _insertMru(_LinkedEntry<K, V> entry) {
-    // Insert a new entry if necessary (only 1 hash lookup in entire function).
-    // Otherwise, just updates the existing value.
-    final value = entry.value;
-    _promoteEntry(_entries.putIfAbsent(entry.key, () => entry)..value = value);
-  }
-
-  /**
-   * Removes the LRU position, shifting the linked list if necessary.
-   */
-  void _removeLru() {
-    // Remove the tail from the internal map.
-    _entries.remove(_tail.key);
-
-    // Remove the tail element itself.
-    _tail = _tail.previous;
-    _tail.next = null;
-  }
-}