platform/platform-impl/src/com/intellij/util/containers/IntObjectLinkedMap.java

/*
 * Copyright 2000-2013 JetBrains s.r.o.
 *
 * 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.
 */
package com.intellij.util.containers;

import org.jetbrains.annotations.Nullable;

/**
 * @author peter
 */
public class IntObjectLinkedMap<Entry extends IntObjectLinkedMap.MapEntry> {
  /**
   * The header of the double-linked list, its before = most recently added entry; its after = eldest entry
   */
  private final MapEntry myHeader;
  private final MapEntry[] myArray;
  private final int myCapacity;
  private int mySize;

  public IntObjectLinkedMap(int capacity) {
    myCapacity = capacity;
    myArray = new MapEntry[capacity * 8 / 5];
    myHeader = new MapEntry<Object>(0, null);
    myHeader.before = myHeader.after = myHeader;
  }

  @Nullable
  public Entry getEntry(int key) {
    MapEntry candidate = myArray[getArrayIndex(key)];
    while (candidate != null) {
      if (candidate.key == key) {
        //noinspection unchecked
        return (Entry)candidate;
      }
      candidate = candidate.next;
    }
    return null;
  }

  private int getArrayIndex(int key) {
    return (key & 0x7fffffff) % myArray.length;
  }

  public void removeEntry(int key) {
    int index = getArrayIndex(key);
    MapEntry candidate = myArray[index];
    MapEntry prev = null;
    while (candidate != null) {
      if (candidate.key == key) {
        if (prev == null) {
          myArray[index] = candidate.next;
        } else {
          prev.next = candidate.next;
        }

        candidate.before.after = candidate.after;
        candidate.after.before = candidate.before;
        candidate.next = candidate.before = candidate.after = null;

        mySize--;
        return;
      }
      prev = candidate;
      candidate = candidate.next;
    }
  }

  public Entry putEntry(Entry entry) {
    removeEntry(entry.key);

    int index = getArrayIndex(entry.key);
    entry.next = myArray[index];
    myArray[index] = entry;

    entry.before = myHeader.before;
    entry.after = myHeader;
    entry.before.after = entry;
    myHeader.before = entry;

    mySize++;
    if (mySize <= myCapacity) {
      return null;
    }

    //noinspection unchecked
    Entry eldest = (Entry)myHeader.after;
    removeEntry(eldest.key);
    return eldest;
  }

  public static class MapEntry<T> {
    public final int key;
    public final T value;
    MapEntry next; // in the list of entries with the same hash
    MapEntry before, after; // in the doubly-linked list reflecting the map's history

    public MapEntry(int key, T value) {
      this.key = key;
      this.value = value;
    }

    @Override
    public String toString() {
      return key + "->" + value;
    }
  }


}