/* Copyright 1997, John Webster Small, All rights reserved */
package extensions.util;
import java.util.*;

/**
 * A general purpose container for objects of any class
 * or polymorphic cluster of classes.  The container
 * emulates the various collection classes, e.g.
 * stack, queue, list, bag, etc.
 *
 * @version 1.0.2
 * @author John Webster Small, email: jsmall@laser.net
 * @see extensions.util.Comparable
 */
public
class ContainerLite implements Cloneable {
    /** Maximum nodes ever allowed in one container.
     *  Notes: Value must be <= Integer.MAX_VALUE / 2
     *  to prevent overflow on (first+n)%_limit
     *  expressions!
     */
    public static final int MAXNODES = Integer.MAX_VALUE/2;

    /** Indicates that the requested node was not found. */
    public static final int NOTFOUND = MAXNODES;

    /** Default size of initial physical array. */
    public static final int LIMIT = 32;

    /** Default expansion/contraction increment. */
    public static final int DELTA = 16;

    /** Restricts containment to instances of
     * baseElementClass and its descendants.
     */
    public static final boolean DESCENDANTS = true;

    /** Restricts containment to instances of
     * baseElementClass.
     */
    public static final boolean ONLY_CLASS = false;

    private Class _rootElementClass;
    private boolean _descendants;

    /**
     * The following relationships are maintained
     * during operation of a Container:
     * 1 <= _delta <= lowLimit <= _limit <= _maxNodes
     *   <= MAXNODES and
     * lowThreshold = lowLimit - _delta;
     */
    private int lowLimit, lowThreshold, first;
    private Object linkS[];
    private int _limit, _delta, _nodes, _maxNodes;

    /** Is container still sorted? */
    private boolean _sorted;

    /** Node comparator */
    private Comparable cmP;

    /** Override to notify incoming element that it
     * is about to be attached to the container. The
     * element has the opportunity to reject binding
     * by having this function return false.
     */
    protected boolean attachD(Object D)
      { return true; }

    /** Override to notify element that it has been
     * detached from the container.
     */
    protected void detachD(Object D) { return; }

    /**
     * Constructs an empty container, restricting
     * containment to the rootElementClass and perhaps
     * its descendants.
     * @param rootElementClass restrict object membership
     * @param descendants allow binding of descendants
     */
    public ContainerLite
      (Class rootElementClass, boolean descendants)
    {
      if (rootElementClass == null)
          try {
            _rootElementClass = Class.forName("java.lang.Object");
          } catch (ClassNotFoundException e) {}
      else
          _rootElementClass = rootElementClass;
      _descendants = descendants;
      _sorted = true;
      lowLimit = _limit;
      lowThreshold = lowLimit - _delta;
      first = 0;
      linkS = null;
      _limit = LIMIT;
      _delta = DELTA;
      _nodes = 0;
      _maxNodes = MAXNODES;
    }

    /** Constructs an empty container for instances
     * of any derivative of java.lang.Object. */
    public ContainerLite()
      { this(null,DESCENDANTS); }

    /** Explodes an enumeration into a container
      * of its elements.
      * @param e elements to be added initially
      */
    public ContainerLite(Enumeration e)
    {
      this(null,DESCENDANTS);
      while (e.hasMoreElements())
        insQ(e.nextElement());
    }

    /** Explodes an array into a container
      * of its elements.
      * @param array array of elements to be added initially
      */
    public ContainerLite(Object[] array)
    {
      this(null,DESCENDANTS);
      for (int i = 0; i < array.length; i++)
        insQ(array[i]);
    }

    /** Explodes a vector into a container
      * of its elements.
      * @param v vector of elements to be added initially
      */
    public ContainerLite(Vector v)
    {
      this(null,DESCENDANTS);
      for (int i = 0; i < v.size(); i++)
        insQ(v.elementAt(i));
    }

    /** Clone this container via a shallow copy! */
    public synchronized Object clone()
    {
      ContainerLite gc = new ContainerLite(_rootElementClass,_descendants);
      gc.setLimit(_limit);
      int i = first;
      int j = _nodes;
      while (j > 0 && i < _limit)  {
        gc.atIns(0,linkS[i++]);
        j--;
      }
      i = 0;
      while (j > 0)  {
        gc.atIns(0,linkS[i++]);
        j--;
      }
      return gc;
    }

    /** Convert container to string for debug, etc. */
    public synchronized String toString()
    {
      StringBuffer buf = new StringBuffer();
      Enumeration e = elements();
      buf.append(getClass().getName());
      buf.append("[");
      while (e.hasMoreElements())  {
        buf.append(e.nextElement().toString());
        if (e.hasMoreElements())
            buf.append(", ");
      }
      buf.append("]");
      return buf.toString();
    }

    /** Compare two containers for equality. */
    public synchronized boolean equals(Object anObject)
    {
      if (anObject instanceof ContainerLite)  {
        ContainerLite b = (ContainerLite) anObject;
        if (_nodes != b.nodes())
            return false;
        for (int i = 0; i < nodes(); i++)
          if (!atGet(i).equals(b.atGet(i)))
            return false;
        return true;
      }
      return false;
    }

    /** Maximum number of nodes that can be
     * accomodated without expansion.
     */
    public final int limit() { return _limit; }

    /**
     * Expands the current limit
     * @param newLimit the newly requested limit
     */
    public final synchronized void setLimit(int newLimit)
    {
      if (newLimit < _nodes)
          newLimit = _nodes;
      else if (newLimit > _maxNodes)
        newLimit = _maxNodes;
      if (newLimit < _delta)
          newLimit = _delta;
      if (newLimit <= 0 || newLimit == _limit)
          return;
      if (linkS == null) {
          _limit = newLimit;
          return;
      }
      Object[] newLinkS = new Object[newLimit];
      int headNodes = _limit - first;
      if (headNodes > _nodes)
          headNodes = _nodes;
      if (headNodes > 0)  // move leading nodes
          System.arraycopy
            (linkS,first,newLinkS,0,headNodes);
      // copy wrap around trailing nodes
      if (headNodes < _nodes)
          System.arraycopy
              (linkS,0,newLinkS,headNodes,_nodes-headNodes);
      if (newLimit > _limit)
          if (newLimit - _delta > _limit)
              lowLimit = newLimit - _delta;
          else
              lowLimit = _limit;
      else
          if (newLimit - _delta > _delta)
              lowLimit = newLimit - _delta;
          else
              lowLimit = _delta;
      lowThreshold = lowLimit - _delta;
      linkS = newLinkS;
      _limit = newLimit;
      first = 0;
    }

    /** Trim container's internal physical array size
     * to its logical size.
     */
    public final void pack()  { setLimit(_nodes); }

    /**
     * Increment of expansion
     * @return increment
     */
    public final int delta() { return _delta; }

    /**
     * Sets increment of expansion.
     * @param newDelta the newly requested increment
     */
    public final synchronized void setDelta(int newDelta)
    {
      if (newDelta > 0 && newDelta <= lowLimit)
          _delta = newDelta;
    }

    /** Returns count of elements in container. */
    public final int nodes() { return _nodes; }

    /** Returns true if there are no elements in container. */
    public final boolean empty() { return _nodes == 0; }

    /** Returns maximum number of elements allowed in container. */
    public final int maxNodes() { return _maxNodes; }

    /**
     * Sets the maximum number of nodes allowed in container.
     * @param newMaxNodes the new upper bound on container size
     */
    public final synchronized void setMaxNodes(int newMaxNodes)
    {
      if (newMaxNodes < _limit)
          if (newMaxNodes > _nodes)
              setLimit(newMaxNodes);
      if (newMaxNodes >= _limit)
          if (newMaxNodes > MAXNODES)
              _maxNodes = MAXNODES;
          else
              _maxNodes = newMaxNodes;
    }

    /** The maximum number of additional nodes allowed. */
    public final boolean vacancy()
      { return _nodes < _maxNodes; }

    /** The maximum number of additional nodes that can
     * be accomodated without expansion of internal,
     * physical array.
     */
    public final boolean vacancyNonElastic()
      { return _nodes < _limit; }

    private boolean implementsInterface(Class[] i)
    {
      for (int j = 0; j < i.length; j++)
        if (i[j] == _rootElementClass)
          return true;
        else if (_descendants)
          if (implementsInterface(i[j].getInterfaces()))
            return true;
      return false;
    }

    /** Is this type of instance allowed in this container? */
    public final boolean typeAllowed(Object D)
    {
      if (D == null)
          return false;
      if (_rootElementClass.isInterface())  {
          return implementsInterface(D.getClass().getInterfaces());
      }
      else if (_descendants)  {
          try {
            if (_rootElementClass == Class.forName("java.lang.Object"))
              return true;
          } catch (ClassNotFoundException e) {}
          for (Class T = D.getClass();
              T != null; T = T.getSuperclass())
              if (T == _rootElementClass)
                 return true;
          return false;
      }
      else
          return D.getClass() == _rootElementClass;
    }

    private final void validateType(Object D)
    {
      if (!typeAllowed(D))
         throw new ArrayStoreException
          ("wrong type for ContainerLite");
    }
    private final void validateIndex(int n)
    {
      if (linkS == null || n >= _nodes || n < 0)
          throw new ArrayIndexOutOfBoundsException();
    }

    /** The basic type allowed in this container. */
    public final Class rootType()
      {  return _rootElementClass; }

    /** Are descendants allowed? */
    public final boolean polyCluster()
      { return _descendants; }

    /**
     * Insert a new cell into the "elastic array"
     * assigning the incoming element to this cell.
     * @return indicate success of insertion
     * @param n index of insertion
     * @param D element to insert
     */
    public final synchronized boolean atIns(int n, Object D)
    {
      Object[] newLinkS;
      int newLimit, i;
      if (D == null)
          return false;
      validateType(D);
      if (n < 0)
          throw new ArrayIndexOutOfBoundsException();
      if (_nodes == _limit)  {
          // no vacancy - expand
          if (_limit == _maxNodes)
              return false;
          if (_maxNodes - _delta > _limit)
              newLimit = _limit + _delta;
          else
              newLimit = _maxNodes;
          newLinkS = new Object[newLimit];
          if (!attachD(D)) // data refuses binding
              return false;
          if (n > _nodes)
              n = _nodes;
          newLinkS[n] = D;
          // calc headNodes
          i = _limit - first;
          if (n <= i)  {
              // insert in head section
              if (n > 0)  {
                  // postfix or split head
                  System.arraycopy
                    (linkS,first,newLinkS,0,n);
                  if (n < i)  // it's a split
                      System.arraycopy
                        (linkS,first+n,newLinkS,n+1,i-n);
              }
              else  // prefix head
                  System.arraycopy
                    (linkS,first,newLinkS,1,i);
              if (i < _nodes)  // copy tail
                  System.arraycopy
                    (linkS,0,newLinkS,1+i,_nodes-i);
          }
          else  {  // insert in tail section
              // copy head first
              System.arraycopy
                (linkS,first,newLinkS,0,i);
              if (i < _nodes)  {  // copy tail
                  System.arraycopy
                    (linkS,0,newLinkS,i,n-i);
                  if (n < _nodes)
                      // it's a tail split
                      System.arraycopy
                        (linkS,n-i,newLinkS,
                         n+1,_nodes-n);
              }
          }
          /* Compute next smaller linkS size
             and threshold for shrinking. */
          lowLimit = _limit;
          lowThreshold = lowLimit - _delta;
          // swap new for old
          linkS = newLinkS;
          _limit = newLimit;
          first = 0;
      }
      else  {  // vacancy
        if (linkS == null)
            linkS = new Object[_limit];
        if (!attachD(D))  {
            // data refuses binding
            if (_nodes == 0)
                linkS = null;
            return false;
        }
        if (n == 0)  {  // push
            if (first > 0)
                first--;
            else
                first = _limit - 1;
            linkS[first] = D;
        }
        else if (n >= _nodes)   { // insQ
            n = _nodes;
            linkS[(first+n) % _limit] = D;
        }
        else  {  // insert interior
            i = (first + n) % _limit;
            if (i < first || first == 0)
                // move rear rightward
                System.arraycopy(linkS,i,linkS,
                  i+1,_nodes-n);
            else  { // move front leftward
                System.arraycopy(linkS,first,
                  linkS,first-1,n);
                first--;
                i--;
            }
            linkS[i] = D;
        }
      }
      _nodes++;
      _sorted = false;
      return true;
    }

    /**
     * Insert remaining elements of the enumeration
     * sequentially into the "elastic array".
     * @return number of elements inserted
     * @param n index of insertion
     * @param D element to insert
     */
    public final synchronized int atIns(int n, Enumeration e)
    {
      int i = n;
      for (/* no init */; e.hasMoreElements(); i++)
        if (!atIns(i,e.nextElement()))
          break;
      return i - n;
    }

    /**
     * Insert element into the queue.
     * @return indicate success of insertion
     * @param D element to be queued
     */
    public final boolean insQ(Object D)
      { return atIns(_nodes,D); }

    /**
     * Exchange the element with the one stored
     * in a container at the specified index.
     * @return element orignally at index n
     * @param n index of cell to be exchanged
     * @param D new element to store at index n
     */
    public final synchronized Object atXchg(int n, Object D)
    {
      if (D == null)
          return null;
      validateType(D);
      validateIndex(n);
      int i = (first + n) % _limit;
      if (D != linkS[i]) if (attachD(D))  {
          Object oldD = linkS[i];
          detachD(oldD);
          linkS[i] = D;
          _sorted = false;
          return oldD;
      }
      return null;
    }

    /**
     * Fetch element at index n
     * @return element at index n
     * @param n index
     */
    public final synchronized Object atGet(int n)
    {
      validateIndex(n);
      return linkS[(first + n) % _limit];
    }

    /**
     * Remove cell from the elastic array returning
     * its element.
     * @return element at index n
     * @param n index of extraction
     */
    public final synchronized Object atRmv(int n)
    {
      Object[] newLinkS;
      int newLimit, i;
      Object D;
      validateIndex(n);
      i = (first + n) % _limit;
      D = linkS[i];
      newLinkS = null;
      newLimit = lowLimit;
      if (_nodes <= lowThreshold)  {
          // get ready to contract
          try  {
            newLinkS = new Object[newLimit];
          } catch(Throwable t) { newLinkS = null; }
          /* Compute next smaller linkS
             size and threshold for
             shrinking. */
          if (newLinkS != null)  {
            if (_nodes < _delta)
                lowThreshold = 0;
            else
                lowThreshold -= _delta;
            lowLimit = lowThreshold + _delta;
          }
      }
      if (newLinkS != null)  {
          // remove and contract
          // calc head nodes
          i = _limit - first;
          if (i > _nodes)
             i = _nodes;
          if (n < i)  {
              // rmv from head section
              if (n > 0)  { // rmv from head
                  System.arraycopy(linkS,first,
                    newLinkS,0,n);
                  if (n < i - 1)
                      System.arraycopy(linkS,first+n+1,
                        newLinkS,n,i-n-1);
              }
              else if (i > 1) // pop head
                  System.arraycopy(linkS,first+1,
                    newLinkS,0,i-1);
              if (i < _nodes)  // copy tail
                  System.arraycopy(linkS,0,
                    newLinkS,i-1,_nodes-i);
          }
          else  { // i <= n < nodes
              // rmv from tail section copy head first
              System.arraycopy(linkS,first,
                newLinkS,0,i);
              if (i == n)  { // pop tail
                  if (n < _nodes - 1)
                      // copy trailing tail
                      System.arraycopy(linkS,1,
                        newLinkS,i,_nodes-n-1);
              }
              else  { // copy up to n in tail
                  System.arraycopy(linkS,0,
                    newLinkS,i,n-i);
                  // skip n'th node
                  if (n < _nodes - 1)
                      // copy anything
                      // trailing n'th node
                      System.arraycopy(linkS,n-i+1,
                        newLinkS,n,_nodes-n-1);
              }
          }
          // swap new for old
          linkS = newLinkS;
          _limit = newLimit;
          first = 0;
      }
      else  { // simply remove
          if (n == 0)  { // pop
              linkS[first++] = null;
              if (first >= _limit)
                  first = 0;
          }
          else if (n != _nodes-1) // del interior
              if (i < first)  { // move tail leftward
                  System.arraycopy(linkS,i+1,
                    linkS,i,_nodes-n-1);
                  linkS[(first+_nodes-1)% _limit] = null;
              }
              else  { // move head rightward
                  System.arraycopy(linkS,first,
                    linkS,first+1,n);
                  linkS[first++] = null;
              }
          else // unQ
              linkS[(first+_nodes-1)% _limit] = null;
      }
      if (--_nodes == 0)  {
          linkS = null;
          _sorted = true;
      }
      detachD(D);
      return D;
    }

    /**
     * Remove all occurrences of the indicated element and
     * their cells from the elastic array.
     * @return number of occurrences removed
     * @param D object to be removed
     */
    public final synchronized int rmv(Object D)
    {
      int i = 0;
      int found = 0;

      while ((i = indexOf(D,i)) != NOTFOUND)  {
        found++;
        atRmv(i);
      }
      return found;
    }

    /** Remove all elements from container. */
    public final synchronized void allRmv()
    {
      int i, j;
      if (linkS != null)  {
          i = first;
          j = _nodes;
          while (j > 0 && i < _limit)  {
              detachD(linkS[i++]);
              j--;
          }
          i = 0;
          while (j > 0)  {
              detachD(linkS[i++]);
              j--;
          }
          _sorted = true;
          first = 0;
          _nodes = 0;
          linkS = null;
          _limit = _delta;
          lowLimit = _limit;
          lowThreshold = lowLimit - _delta;
      }
    }

    /** Remove all instances of all remaining
      * elements of the enumeration from the container.
      */
    public final synchronized void allRmv(Enumeration e)
    {
      while (e.hasMoreElements())
        rmv(e.nextElement());
    }

    /**
     * Look for element in container using a linear search.
     * @return index of element if found, otherwise NOTFOUND
     * @param D element sought
     * @param startIdx index to start search from
     */
    public final synchronized int indexOf(Object D, int startIdx)
    {
      if (linkS != null) {
          int i = (first + startIdx) % _limit;
          int j = _nodes - startIdx;
          while (j > 0 && i < _limit)  {
            if (linkS[i] == D)
                return i;
            i++;
            j--;
          }
          i = 0;
          while (j > 0)  {
            if (linkS[i] == D)
                return i;
            i++;
            j--;
          }
      }
      return NOTFOUND;
    }

    /**
     * Look for element in container using a linear search.
     * @return index of element if found, otherwise NOTFOUND
     * @param D element sought
     */
    public final int indexOf(Object D)
      { return indexOf(D,0); }

    /** Release all elements in the container. */
    public void finalize() { allRmv(); }

    /** Return enumeration of elements in the container. */
    public final synchronized Enumeration elements()
      { return new ContainerLiteEnumerator(this); }

    /** Return array of elements in the container.  */
    public final synchronized Object[]
      toArray(int offset, int count)
    {
      if (_nodes <= 0 || offset < 0
          || offset >= _nodes || count <= 0)
          return null;
      if (offset + count > _nodes)
          count = _nodes - offset;
      Object[] array = new Object[_nodes]; 
      int i = first, j = count, k = 0;
      while (j > 0 && i < _limit)  {
          array[k++] = linkS[i++];
          j--;
      }
      i = 0;
      while (j-- > 0)
          array[k++] = linkS[i++];
      return array;
    }

    /** Return array of elements in the container.  */
    public final synchronized Object[] toArray()
      { return toArray(0,_nodes); }

    /** Is the container still sorted? */
    public final boolean sorted() { return _sorted; }

    /** Force container to think it is unsorted. */
    public final synchronized void unsort() { _sorted = false; }

    /**
     * Set the comparator object
     * @see Comparable
     */
    public final synchronized void setCmP(Comparable cmP)
    {
      if ((this.cmP != cmP) && (_nodes > 0))
          _sorted = false;
      this.cmP = cmP;
    }

    /**
     * Insert element into priority queue.
     * The comparator object must have been previously set.
     * @see #setCmP
     * @return indicate success of insertion
     * @param D element to be inserted
     */
    public final synchronized boolean insSort(Object D)
    {
      int low, mid, high;
      if (cmP == null || D == null)
          return false;
      validateType(D);
      if (!_sorted)  {
          sort();
          if (!_sorted)
              return false;
      }
      low = 0;
      high = _nodes;  // linkS == 0 -> nodes == 0!
      while (low < high)  {
          mid = (int)((((long)high)
              + ((long)low)) >> 1);
          if (cmP.compare(D,linkS[(first+mid)
              % _limit]) <= 0)
              high = mid;
          else
              low = mid + 1;
      }
      boolean ok = atIns(high,D);
      _sorted = true;
      return ok;
    }

    /**
     * Insert elements into priority queue.
     * The comparator object must have been previously set.
     * @see #setCmP
     * @return number of elements inserted
     * @param e elements to be inserted
     */
    public final synchronized int insSort(Enumeration e)
    {
      int count = 0;
      while (e.hasMoreElements())  {
        if (!insSort(e.nextElement()))
          break;
        count++;
      }
      return count;
    }

    /**
     * Sort the container.
     * The comparator object must have been previously set.
     * @see #setCmP
     */
    public final synchronized void sort()
    {
      int low, mid, high, d, nidx;
      Object D_;
      if (cmP == null)
          return;
      _sorted = true;
      if (_nodes == 0)
          return;
      if (first > 0)  {
          // form contiguous block at front
          d = (first + _nodes) % _limit;
          if (d > first)  { // no wrap
              System.arraycopy
                (linkS,first,linkS,0,_nodes);
              nidx = first + _nodes;
              while (--nidx >= _nodes)
                linkS[nidx] = null;
          }
          else if (d < first)  {
              // join head to rear of tail
              System.arraycopy(linkS,first,
                linkS,d,_limit-first);
              nidx = d + _limit - first;
              while (nidx < _limit)
                linkS[nidx++] = null;
          }
          // else array is full/contiguous
          first = 0;
      }
      high = 1; d = 1;
      while (d < _nodes)  {
          low = 0;
          D_ = linkS[d];
          while (low < high)  {
              mid = (int) ((((long)high)
                  + ((long)low)) >> 1);
              if (cmP.compare(D_,linkS[mid])
                  <= 0)
                  high = mid;
              else
                  low = mid + 1;
          }
          if (high < d)  {
              System.arraycopy(linkS,high,
                linkS,high+1,d-high);
              linkS[high] = D_;
          }
          high = ++d;
      }
    }

    /**
     * Look for first matching element using binary
     * search if the container is sorted and honorSorted
     * flag is set, otherwise a linear search is used.
     * @return index of first matching element or NOTFOUND
     * @param key element key
     * @param cmpKey comparator object
     * @param honorSorted if true then use a binary search
     * if the container is sorted, in all other cases use
     * a linear search.
     * @param offset search at offset
     * @param count range of search is from offset to
     * offset + count - 1.
     */
    public final synchronized int find(Object key,
      Comparable cmpKey, boolean honorSorted,
      int offset, int count)
    {
      int low, high, idx;
      if (key == null || cmpKey == null
          || offset < 0 || offset >= _nodes
          || count <= 0)
          return NOTFOUND;
      if (offset + count > _nodes)
        count = _nodes - offset;
      if (honorSorted && _sorted)  {
          low = offset; high = offset + count - 1;
          // binary search for first match
          while (low < high)  {
              idx = (int)((((long)high)
                  + ((long)low)) >> 1);
              if (cmpKey.compare(key,linkS[(first+idx)
                  % _limit]) <= 0)
                  high = idx;
              else
                  low = idx + 1;
          }
          idx = high;
          if (cmpKey.compare(key,linkS[(first+high)
              % _limit]) != 0)
              idx = _nodes;
      }
      else  { // linear search!
          idx = offset;
          do {
              if (cmpKey.compare(key,linkS[(first+idx)
                  % _limit]) == 0)
                  break;
              idx++;
          } while (count-- > 0);
      }
      return ((idx < _nodes)? idx: NOTFOUND);
    }

    /**
     * Look for first matching element using binary
     * search if the container is sorted and honorSorted
     * flag is set, otherwise a linear search is used.
     * @return index of first matching element or NOTFOUND
     * @param key element key
     * @param cmpKey comparator object
     * @param honorSorted if true then use a binary search
     * if the container is sorted, in all other cases use
     * a linear search.
     */
    public final int findFirst
      (Object key, Comparable cmpKey, boolean honorSorted)
      { return find(key,cmpKey,honorSorted,0,_nodes); }

    /**
     * Look for all matching elements using binary
     * search if the container is sorted and honorSorted
     * flag is set, otherwise a linear search is used.
     * @return enumeration of matching elements
     * @param key element key
     * @param cmpKey comparator object
     * @param honorSorted if true then use a binary search
     * if the container is sorted, in all other cases use
     * a linear search.
     */
    public final synchronized Enumeration findAll
      (Object key, Comparable cmpKey, boolean honorSorted)
    {
      ContainerLite gc = new ContainerLite();
      for (int i = find(key,cmpKey,honorSorted,0,_nodes);
        i != NOTFOUND;
        i = find(key,cmpKey,honorSorted,i+1,_nodes-i))
        gc.insQ(atGet(i));
      return gc.elements();
    }

    /**
     * Look for first matching element using binary search if the
     * container is sorted, otherwise a linear search is used.
     * The comparator object must have been previously set.
     * @see #setCmP
     * @return index of first matching element or NOTFOUND
     * @param D element key
     */
    public final int firstMatching(Object D)
      { return find(D,cmP,true,0,_nodes); }

    /**
     * Look for all matching elements using binary
     * search if the container is sorted and honorSorted
     * flag is set, otherwise a linear search is used.
     * @return enumeration of matching elements
     * @param D element key
     */
    public final synchronized Enumeration allMatching(Object D)
    {
      ContainerLite gc = new ContainerLite();
      for (int i = find(D,cmP,true,0,_nodes);
        i != NOTFOUND;
        i = find(D,cmP,true,i+1,_nodes-i))
        gc.insQ(atGet(i));
      return gc.elements();
    }

}

final
class ContainerLiteEnumerator implements Enumeration {
    private ContainerLite gc;
    private int idx;

    public ContainerLiteEnumerator(ContainerLite gc) {
      this.gc = gc;
      idx = 0;
    }

    public boolean hasMoreElements() {
      return idx < gc.nodes();
    }

    public Object nextElement() {
      try {
        return gc.atGet(idx++);
      } catch (Exception e)  {
        throw new NoSuchElementException
          ("ContainerLiteEnumerator");
      }
    }
}