---

Cache.java

package gov.nasa.arc.ase.util;

import java.util.*;

public class Cache {
  public interface Listener {
    public void elementRemoved(Object o);
  }
  
  private class EntryComparator implements Comparator {
    public int compare(Object o1, Object o2) {
      Map.Entry e1 = (Map.Entry)o1;
      Index c1 = (Index)e1.getValue();
      Map.Entry e2 = (Map.Entry)o2;
      Index c2 = (Index)e2.getValue();

      return c1.cnt - c2.cnt;
    }
  }

  private class Index {
    int cnt;

    public Index() {
      cnt = 0;
    }

    public Index(int value) {
      cnt = value;
    }

    public Object clone() {
      return new Index(cnt);
    }

    public boolean equals(Object o) {
      return ((Index)o).cnt == cnt;
    }

    public String toString() {
      return new Integer(cnt).toString();
    }
  }

  private Hashtable ht = new Hashtable();
  private Index     lowest = new Index(0);
  private Index     highest = new Index(0);
  private int       count = 0;
  private int       size;
  private Listener  listener;

  public Cache(int s) {
    size = s;
    listener = null;
  }  
  public Cache(int s, Listener l) {
    size = s;
    listener = l;
  }  
  private Object getKey(Index c) {
    Collection entrySet = ht.entrySet();
    for(Iterator i = entrySet.iterator(); i.hasNext();) {
      Map.Entry v = (Map.Entry)i.next();
      if(v.getValue().equals(c)) return v.getKey();
    }

    return null;
  }  
  private Index getValue(Index c) {
    Collection entrySet = ht.entrySet();
    for(Iterator i = entrySet.iterator(); i.hasNext();) {
      Map.Entry v = (Map.Entry)i.next();
      if(v.getValue().equals(c)) return (Index)v.getValue();
    }

    return null;
  }  
  private int lowestValue() {
    int min = 0;
    boolean found = false;
    Collection values = ht.values();

    for(Iterator i = values.iterator(); i.hasNext();) {
      Index v = (Index)i.next();

      if(!found || v.cnt < min) {
    found = true;
    min = v.cnt;
      }
    }

    return min;
  }  
  private void next() {
    highest.cnt++;
    if(highest.cnt < 0) {
      ArrayList entries = new ArrayList(ht.entrySet());
      int idx = 0;

      ht = new Hashtable();
      Collections.sort(entries, new EntryComparator());
      for(Iterator i = entries.iterator(); i.hasNext(); idx++) {
    Map.Entry e = (Map.Entry)i.next();
    ht.put(e.getKey(), new Index(idx));
      }

      lowest.cnt = 0;
      highest.cnt = entries.size();
    }
  }  
  public boolean put(Object o) {
    if(ht.containsKey(o)) {
      Index c = (Index)ht.get(o);

      if(c.cnt != highest.cnt-1) {
    int old = c.cnt;

    c.cnt = highest.cnt;
    if(old == lowest.cnt)
      lowest.cnt = lowestValue();
    next();
      }

      return false;
    }

    if(count == size)
      removeLowest();
    else
      count++;

    ht.put(o, new Index(highest.cnt));
    next();

    return true;
  }  
  private void removeLowest() {
    Object key = getKey(lowest);
    if(key == null) {
      System.err.println("key == null");
      System.err.println(highest);
      System.err.println(lowest);
      System.err.println(ht);
    }

    ht.remove(key);
    lowest.cnt = lowestValue();
    if(count == 1) highest.cnt = 0;

    if(listener != null) listener.elementRemoved(key);
  }  
  public void setSize(int s) {
    if(s > count) {
      size = s;
    } else {
      while(count > s) {
    removeLowest();
    count--;
      }
      size = s;
    }
  }  
  public String toString() {
    return ht.toString();
  }  
}

---