/* OrderedCollection is an indexed collection in which
  the elements are usually chronologically ordered,
  i.e. elements at the end were added to the
  collection after the ones at the beginning.

  The most obvious use of an OrderedCollection is a
  stack.  You can think of an OrderedCollection as a
  stack, if you prefer, and we have even provided pop
  and push methods.

  An OrderedCollection is considered empty if its two
  instance variables, firstElement and lastElement,
  are equal. */!!

/* inherit(Array, #OrderedCollection, #(firstElement lastElement), 2, 1) */!!

now(class(OrderedCollection))!!

/* Create a new OrderedCollection with the contents of
  the elements Array as its elements. */
Def build(self, elements | coll)
{ coll := new(self, size(elements));
  do(elements,
  {using(elem) add(coll, elem);
  });
  ^static(coll);
}!!

now(OrderedCollection)!!

/* Makes sure that the index is within
  the valid range of the collection.  (Private method) */
Def checkRange(self, idx)
{ ?hasElements(self);
  if idx < firstElement or idx >= lastElement
  then alert(System, self, #rangeError);
  endif;
}!!

/* Return a new collection that is the result of
  evaluating a block over the elements of the receiver. */
Def collect(self, blk)
{ ^collect(self:Collection, blk);
}!!

/* Returns the contents of self from self[begIdx] to
  self[endIdx-1], inclusive in the form of another object
  of the same class of self.  If begIdx > endIdx,
  then a bad range error is generated. */
Def copyFrom(self, strtIdx, endIdx | oc sz)
{ sz := min(endIdx, size(self));
  oc := copyFrom(self:ancestor, strtIdx, sz);
  setFirst(oc, 0);
  setLast(oc, sz-strtIdx);
  ^oc;
}!!

/* Evaluates the one-argument block over the elements of the
  receiver. */
Def do(self, aBlock)
{ ^do(new(Interval, firstElement, lastElement, 1),
  {using(idx) eval(aBlock, at(self:Object, idx));
  });
}!!

/* Return a new collection that has the elements of the
  receiver in reverse order. */
Prim reverse(self):collection!!

/* Return a new collection that is the result of
  evaluating a block over the elements of the receiver for
  which the block returns true. */
Def extract(self, blk)
{ ^extract(self:Collection, blk);
}!!

/* Returns (but doesn't remove) the first
  element in the collection, if any.
  If there isn't a first element, i.e. if
  the receiver is empty, an "Empty
  collection" error is generated. */
Def first(self)
{ ?hasElements(self);
  ^at(self:Object, firstElement);
}!!

/* Grows the OrderedCollection so that it
  can hold more elements.  Works by copying
  elements into larger collection and then
  swapping object pointers with the new
  collection. */
Def grow(self | newColl)
{ newColl := new(class(self), limit(self) + 8);
  do(self,
  {using(elem) add(newColl, elem)
  });
  swapProperties(self, newColl);
  swap(self, newColl);
}!!

/* Initializes an OrderedCollection by setting
  firstElement and lastElement equal to zero.  You can empty
  an existing OrderedCollection simply by sending it an init
  message. */
Def init(self)
{ fill(self, nil);
  firstElement := lastElement := 0;
}!!

/* Inserts a new element at the specified index in the
  collection.  Reports an error if the index is not
  in the current valid range.  Grows the collection if necessary. */
Def insert(self, elem, idx | index)
{ if idx < firstElement or idx > lastElement
  then alert(System, self, #rangeError);
  endif;
  if (index := lastElement) == limit(self)
  then grow(self);
  endif;
  loop
  while index > idx
  begin put(self:Object, at(self:Object,
    index - 1), index);
    index := index - 1;
  endLoop;
  put(self:Object, elem, idx);
  lastElement := lastElement + 1;
}!!

/* Inserts any indexed collection into the receiver,
  starting at the specified idx. */
Def insertAll(self, coll, idx | srcIdx)
{ srcIdx := size(coll);
  loop
  while srcIdx > 0
  begin insert(self, coll [srcIdx-1], idx);
    srcIdx := srcIdx - 1;
  endLoop;
}!!

/* Evaluates a one-argument block over the keys of
  the receiver.  In an OrderedCollection, the keys are
  the integer indices of the collection, and thus are
  probably of little interest. However, keysDo is
  provided so that any collection can respond to
  keysDo. */
Def keysDo(self, aBlock)
{ ^do(over(firstElement, lastElement),
  {using(idx) eval(aBlock, idx);
  });
}!!

/* Returns (but doesn't remove) the last element in the collection, if any.
  If there isn't a last element, i.e. if the receiver is empty,
  an "Empty collection" error is generated. */
Def last(self)
{ ?hasElements(self);
  ^at(self:Object, lastElement - 1);
}!!

/* Removes and returns the last element in the collection.  If the
  collection is empty, an "Empty collection" error is generated. */
Def pop(self)
{ ^removeLast(self:OrderedCollection);
}!!

/* Adds a new last element, anObj, to the collection. */
Def push(self, anObj)
{ add(self:OrderedCollection, anObj)
}!!

/* Removes the element at the specified idx.  If idx is not
  valid, i.e. if it is less than firstElement or greater than
  or equal to lastElement, then a "Range Error" is generated.
  The removed element doesn't leave a "hole;" elements above
  the removed element (i.e. with indices greater than idx) are
  moved down. */
Def remove(self, idx | elem, index, lim, val)
{ ?hasElements(self);
  if idx < firstElement or idx > (lim := lastElement - 1)
  then alert(System, self, #rangeError);
  endif;
  val := self:Object[index := idx];
  loop
  while index < lim:Int
  begin put(self:Object, at(self:Object, index + 1), index);
    index := index + 1;
  endLoop;
  lastElement := lastElement - 1;
  put(self:Object, nil, lastElement);
  ^val;
}!!

/* Removes the first element in the collection, if there is one.
  If there isn't one, then a "Range error" is generated. */
Def removeFirst(self | val)
{ ^remove(self:OrderedCollection, firstElement);
}!!

/* Removes and returns the last element in the
  collection, if any. If the collection is empty, an
  "Empty collection" error is generated. (The pop
  method of this class uses this method; removeLast
  is another name for pop.) */
Def removeLast(self | val)
{ if lastElement > firstElement
  then val := self:Object[lastElement :=
    lastElement - 1];
    put(self:Object, nil, lastElement);
    ^val;
  endif;
  alert(System, self, #emptyError);
}!!

/* Private method used only by OrderedCollection:copyFrom.
  Set the firstElement variable. */
Def setFirst(self, frst)
{ ^firstElement := frst;
}!!

/* Private method used only by OrderedCollection:copyFrom.
  Set the lastElement variable. */
Def setLast(self, last)
{ ^lastElement := last;
}!!

/* Returns the current number of elements in the collection. */
Def size(self)
{ ^lastElement - firstElement;
}!!

/* The writable size of an OrderedCollection is 16K-1,
  the largest possible Int. */
Def writeSize(self)
{ ^0x3fff;
}!!

/* Generates an "Empty collection" error
  if the collection is empty.  If not, then
  it just returns the receiver.  This
  method is used as an error checking
  mechanism by some of the other methods
  of this class. */
Prim ?hasElements(self):OrderedCollection!!

/* Adds the specified object to the receiver at its end.
  The add method is synonomous with push. */
Prim add(self, anObject):OrderedCollection!!
