/* SkipList container for Java.

  Copyright (C) 1997-2000 Business Management Systems, Inc.

  Everyone has permission to use or modify this code for any purpose, 
  just give credit to Stuart D. Gathman and Business Management Systems.

  The algorithm was copied from an article in Dr. Dobbs Journal.  It has
  been adapted to Java containers, both JDK 1.1 Dictionary and the
  Java General Library, by Stuart D. Gathman.

  http://www.objectspace.com/products/voyager/librariers.asp

  To extricate from JGL, remove add(Object),start(),finish() from
  SkipList and extra methods from SLData. Provide an equivalent of
  BinaryPredicate for comparing keys.

 *
 * $Log: SkipList.java,v $
 * Revision 1.2  2003/03/06 22:13:10  stuart
 * doc update
 *
 * Revision 1.1  2001/06/03 03:29:37  stuart
 * Initial revision
 *
 *
 */
package bmsi.util;
import java.util.Enumeration;
import java.util.Dictionary;
import jgl.BinaryPredicate;
import jgl.Container;
import jgl.ForwardIterator;
import jgl.LessString;
import jgl.Pair;

/** The core SkipList data structure.  Holds the data and N forward pointers.
 */
class SLnode {
  Object data;
  Object key;
  final SLnode[] forward;
  SLnode(int nlevel) { forward = new SLnode[nlevel]; }
  SLnode(int nlevel,Object data,Object key) {
    this.data = data;
    this.key = key;
    forward = new SLnode[nlevel];
  }
}

/** The SkipList iterator.   One of the vaunted features of a SkipLIst is that
  iteration should be Thread safe, even when elements are simultaneosly
  inserted or removed.  I tried to keep this in mind while coding, with the
  assumption that while the container is Threadsafe, each iterator can
  be used by only one Thread.
  <p>
  However, this code has *not* been thoroughly checked for Thread safety.
 */
class SLData implements ForwardIterator {
  protected SLnode cur;
  protected final SkipList parent;

  SLData(SkipList parent,SLnode cur) {
    this.parent = parent;
    this.cur = cur;
  }

  /** SkipList iterators are considered equal if they are in the same position
    on the same container. */
  public boolean equals(Object obj) {
    if (!(obj instanceof SLData)) return false;
    SLData that = (SLData)obj;
    return that.cur == cur && that.parent == parent;
  }

  public boolean hasMoreElements() { return cur != null; }
  public Object nextElement() { Object x = get(); advance(); return x; }
  public Object get() { return cur.data; }
  public Object clone() { return new SLData(parent,cur); }
  
  // following methods can eliminated if not using JGL
  public Container getContainer() { return parent; }
  public boolean atEnd() { return cur == null; }
  public boolean atBegin() { return equals(parent.start()); }
  public final void advance() { cur = cur.forward[0]; }
  public void advance(int n) { 
    while (n-- > 0)
      advance();
  }
  public int distance(ForwardIterator t) {
    SLnode there = ((SLData)t).cur;
    SLnode here = cur;
    int dist = 0;
    while (here != there) {
      here = here.forward[0];
      ++dist;
    }
    return dist;
  }
  public void put(Object val) { cur.data = val; }
}

class SLKeys extends SLData {
  SLKeys(SkipList par,SLnode cur) { super(par,cur); }
  public Object get() { return cur.key; }
  public Object clone() { return new SLKeys(parent,cur); }
}

/** A skip list is a sorted container with efficient updates.
  Updates are 1.5 to 4 times faster than a balanced or AVL trees.  
  Memory use averages
  1.33 pointers / node (binary tree uses 2 pointers / node).  Searches
  are as fast as a balanced tree on average.  However, performance is
  probablistic.  The probability of a search taking twice as long as
  the optimum is about 1/1000 for >256 nodes.  This probability decreases
  rapidly with the number of nodes.  A SkipList performs like a HashTable,
  but for sorted keys.
  @author Stuart D. Gathman
  Copyright (C) 1997-2000 Business Management Systems, Inc.
 */
public class SkipList extends Dictionary implements Container {
  private final BinaryPredicate comparer;
  /** The default maxlevel for a SkipList. 
    A SkipList provides good performance up to 2 ^ (maxlevel * 2) nodes.
   */
  public static final int MAXLEVEL = 10;
  private SLnode head;
  private int level;
  private int count;
  private final boolean allowdups;

  /** The most efficient search will result from a probability of 1/e.
   * However, 1/4 is only slightly slower and uses less memory - 1.33
   * pointers / node on average. */
  private final float prob;

  /** Permanently allocate the update vector to reduce GC overhead */
  private final SLnode[] update;

  /** Create a SkipList. 
    @param lessthan An object used to compare keys.
    @param maxlevel The maximum number of levels for this SkipList.
    A SkipList provides good performance up to 2 ^ (maxlevel * 2) nodes.
    @param allowdups True if duplicate keys should be allowed.
   */

  public SkipList(BinaryPredicate lessthan,int maxlevel,boolean allowdups) {
    this.comparer = lessthan;
    this.allowdups = allowdups;
    update = new SLnode[maxlevel];
    prob = 0.25f;
    clear();
  }

  /** Create a SkipList with MAXLEVEL levels. */
  public SkipList(BinaryPredicate lessthan,boolean allowdups) {
    this.comparer = lessthan;
    this.allowdups = allowdups;
    update = new SLnode[MAXLEVEL];
    prob = 0.25f;
    clear();
  }

  /** Create a SkipList with MAXLEVEL levels and no duplicates allowed */
  public SkipList(BinaryPredicate lessthan) {
    this.comparer = lessthan;
    this.allowdups = false;
    update = new SLnode[MAXLEVEL];
    prob = 0.25f;
    clear();
  }

  /** Return true if duplicate keys are allowed in this SkipList. */
  public final boolean allowsDuplicates() { return allowdups; }

  /** Return the maximum number of elements this SkipList can efficiently hold.
      The SkipList has no hard limit, but it starts to become less efficient
      at this number of elements.
   */
  public int maxSize() { return 1 << (update.length * 2); }

  /** Remove all elements from this SkipList. */
  public synchronized void clear() {
    head = new SLnode(update.length);
    level = 1;
    count = 0;
  }

  public Enumeration elements() { return new SLData(this,head.forward[0]); }

  public Enumeration keys() { return new SLKeys(this,head.forward[0]); }

  public Object get(Object key) {
    SLnode next = find(key);
    if (next != null && !comparer.execute(key,next.key))
      return next.data;
    return null;
  }

  private int rand_level() {
    int level = 1;
    while (Math.random() < prob && level < update.length)
      ++level;
    return level;
  }

  private SLnode find(Object key) {
    SLnode cur = head, next = null;
    for (int i = level - 1; i >= 0; --i) {
      next = cur.forward[i];
      while (next != null && comparer.execute(next.key,key)) {
	cur = next;
	next = cur.forward[i];
      }
      update[i] = cur;
    }
    return next;
  }

  private void insert(Object key,Object data) {
    int pos_level = rand_level();
    SLnode new_pos = new SLnode(pos_level,data,key);
    if (pos_level > level) {
      for (int i = level; i < pos_level; ++i)
	update[i] = head;
      level = pos_level;
    }
    for (int i = 0; i < pos_level; ++i) {
      new_pos.forward[i] = update[i].forward[i];
      update[i].forward[i] = new_pos;
    }
    ++count;
  }

  /** If the key doesn't exist or duplicates are allowed, associate the value 
  with the key and return null, otherwise don't modify the map and return 
  the current value associated with the key.
   */
  public synchronized Object add(Object key,Object data) {
    SLnode next = find(key);
    if (!allowdups && next != null && !comparer.execute(key,next.key))
      return next.data;
    insert(key,data);
    return null;
  }

  /** If the key doesn't exist, associate the value with the key and return 
  null, otherwise replace the first value associated with the key and 
  return the old value.
   */
  public synchronized Object put(Object key,Object data) {
    SLnode next = find(key);
    if (next != null && !comparer.execute(key,next.key)) {
      Object old = next.data;
      next.data = data;
      return old;
    }
    insert(key,data);
    return null;
  }

  /** Remove the key/value pair matching a key.
   @return the value that was removed or null if none.
   */
  public synchronized Object remove(Object key) {
    SLnode next = find(key);
    if (next != null && !comparer.execute(key,next.key)) {
      for (int i = 0; i < level; ++i) {
	if (update[i].forward[i] != next)
	  break;
	update[i].forward[i] = next.forward[i];
      }
      while (level > 0 && head.forward[level] == null)
	--level;
      --count;
      return next.data;
    }
    return null;
  }

  /** Return true if there are no elements in this SkipList. */
  public final boolean isEmpty() { return count == 0; }

  /** Return the number of elements in this SkipList. */
  public final int size() { return count; }

  /** Assume that the specified object is a Pair whose first field is a key 
    and whose second field is a value. If the key doesn't exist or 
    duplicates are allowed, associate the value with the key and return 
    null, otherwise don't modify the map and return the current value 
    associated with the key. 
  */
  public Object add(Object pair) {
    if (!(pair instanceof Pair))
      throw new IllegalArgumentException();
    Pair p = (Pair)pair;
    return add(p.first,p.second);
  }
  public ForwardIterator start() { return new SLData(this,head.forward[0]); }
  public ForwardIterator finish() { return new SLData(this,null); }

  public boolean equals(Object obj) {
    if (!(obj instanceof SkipList)) return false;
    SkipList that = (SkipList)obj;
    SLnode cur1 = this.head.forward[0];
    SLnode cur2 = that.head.forward[0];
    while (cur1 != null) {
      if (cur2 == null) return false;
      if (!cur1.key.equals(cur2.key)) return false;
      if (!cur1.data.equals(cur2.data)) return false;
      cur1 = cur1.forward[0];
      cur2 = cur2.forward[0];
    }
    return cur2 == null;
  }

  public String toString() {
    StringBuffer buf = new StringBuffer("SkipList[");
    SLnode cur = head.forward[0];
    while (cur != null) {
      buf.append('(');
      buf.append(cur.key.toString());
      buf.append(',');
      buf.append(cur.data.toString());
      buf.append(')');
      cur = cur.forward[0];
      if (cur != null)
	buf.append(',');
    }
    buf.append(']');
    return buf.toString();
  }

  /** Copy all elements of another Dictionary to this SkipList.  This
  is a shallow copy.
    @param dict	the Dictionary to copy from
   */
  public void copy(Dictionary dict) {
    clear();
    Enumeration k;
    Enumeration d;
    synchronized (dict) {
      k = dict.keys();
      d = dict.elements();
    }
    while (k.hasMoreElements()) {
      add(k.nextElement(),d.nextElement());
    }
  }

  /** Return a shallow copy of this SkipList. */
  public Object clone() {
    SkipList s = new SkipList(comparer,update.length,allowdups);
    s.copy(this);
    return s;
  }

  /** Test SkipList by sorting an ascii file on stdin. */
  public static void main(String[] args) {
    Dictionary list = new SkipList(new LessString());
    java.io.BufferedReader in = new java.io.BufferedReader(
      new java.io.InputStreamReader(System.in));
    try {
      for (;;) {
	String txt = in.readLine();
	if (txt == null) break;
	list.put(txt,txt);
      }
    }
    catch (java.io.IOException e) {
      System.out.println(e);
    }
    System.err.println(list.size() + " input lines.");
    Enumeration data = list.elements();
    while (data.hasMoreElements())
      System.out.println((String)data.nextElement());
  }
}