LinkedHashMapImplementation() {
  _map = new HashMap<K, DoubleLinkedQueueEntry<KeyValuePair<K, V>>>();
  _list = new DoubleLinkedQueue<KeyValuePair<K, V>>();
}

factory LinkedHashMapImplementation.from(Map<K, V> other) {
  Map<K, V> result = new LinkedHashMapImplementation<K, V>();
  other.forEach((K key, V value) { result[key] = value; });
  return result;
}

void clear() {
  _map.clear();
  _list.clear();
}

bool containsKey(K key) {
  return _map.containsKey(key);
}

bool containsValue(V value) {
  return _list.some(bool _(KeyValuePair<K, V> entry) {
    return (entry.value == value);
  });
}

void forEach(void f(K key, V value)) {
  _list.forEach(void _(KeyValuePair<K, V> entry) {
    f(entry.key, entry.value);
  });
}

Collection<K> getKeys() {
  List<K> list = new List<K>(length);
  int index = 0;
  _list.forEach(void _(KeyValuePair<K, V> entry) {
    list[index++] = entry.key;
  });
  assert(index == length);
  return list;
}

Collection<V> getValues() {
  List<V> list = new List<V>(length);
  int index = 0;
  _list.forEach(void _(KeyValuePair<K, V> entry) {
    list[index++] = entry.value;
  });
  assert(index == length);
  return list;
}

bool isEmpty() {
  return length == 0;
}

int get length() {
  return _map.length;
}

void operator []=(K key, V value) {
  if (_map.containsKey(key)) {
    _map[key].element.value = value;
  } else {
    _list.addLast(new KeyValuePair<K, V>(key, value));
    _map[key] = _list.lastEntry();
  }
}

V operator [](K key) {
  DoubleLinkedQueueEntry<KeyValuePair<K, V>> entry = _map[key];
  if (entry === null) return null;
  return entry.element.value;
}

V putIfAbsent(K key, V ifAbsent()) {
  V value = this[key];
  if ((this[key] === null) && !(containsKey(key))) {
    value = ifAbsent();
    this[key] = value;
  }
  return value;
}

V remove(K key) {
  DoubleLinkedQueueEntry<KeyValuePair<K, V>> entry = _map.remove(key);
  if (entry === null) return null;
  entry.remove();
  return entry.element.value;
}

String toString() {
  return Maps.mapToString(this);
}