Most of these methods should be familiar. Note that increment changes the object which receives the message, while add does not. Add simply returns the sum. Negated returns a new large integer equal to the negative of the receiver, while negate changes the sign of the receiver.

The implementation of this class is as base 10000 integers stored in an array. NewLargeInteger has parameters for the sign of the value as well as the ten "digits" of this representation. As a result each of these latter parameters should be in the range of 0 through 9999. Note that default values are provided for all parameters. If INTEGER is larger than 32 bits on your computer, it would be advantageous to reimplement this class to take advantage of the fact, though this class will still work correctly there.

4.3 Collections and their Iterators.

We have seen the collection and iterator classes above when we looked at finite stacks. Collections are one of the richest of abstractions. In fact most of them require us to develop groups of abstractions, since collections are linked to iterators. Collections differ in the amount of structure internal to the collection as well as in the type of object which may be collected. Some classes for example, only permit us to collect magnitudes. SortedList is an example of this, as is BinarySearchTree. Sometimes we use an implementation which imposes restrictions. A Set, for example, may hold any sort of reference, and imposes no structure on the values in it. A similar class externally is BSTSet, which also implements a set, but its implementation, while more efficient, requires that the objects in it be in some subclass of Magnitude.

Some collection classes have a well defined notion of a "position" in the collection. This is the case with Lists.T, and with all tree classes. These classes are called indexed collections, and we shall have a pseudo class IndexedCollection to account for this. We shall also have another associated abstraction Position, for each such class. In some classes the notion of position is an ordinal position: first, second, etc. These are the arrayed collections. Still others impose an order on the contents which is derived from the values of the contents themselves. These are the ordered collections, such as BinarySearchTree.T. They require that their contents be in Magnitude.T. If the physical order within the collection is the same as the natural order of the contents then the collection is a sortedCollection, as is SortedList.T. It is instructive to see the entire hierarchy at once, so we present it below. Indentation shows inheritance here, so that a DEQueue is a Queue which is a List which is a Collection. (Note that there are a few inaccuracies in the list below. Our implementations will actually be a little different, with some of the classes using an implementation dependent on some of the others.

Collection
Set  {finite set of objects}
	Dictionary {set of associations-- key-value pairs}
		HashDictionary  {hash table implementation}
Bag  {a multi-set.  multiple inclusion possible}
IndexedCollection  {collection with position-- Pseudo Class}
	Lists
		Queue
	    		DEQueue {double ended queue}
	Stack
	Tree  {a general tree}
		BinaryTree  
	ArrayedCollection  {position is an integer-- Pseudo Class}
			DynamicArray  {very large arrays-- dynamic arrays}
		FixedSizeCollection {not expandable-- Pseudo Class}
			Interval
				Array
	OrderedCollection   {-- Pseudo Class}
                        {collection of magnitudes, kept partially ordered}
			Heap
		BinarySearchTree
		AVL Tree
	 	234 Tree 
		BTree
		BSTSet  {a binary search tree implementation of a set}
		SortedCollection {imposes total order on contents
				-- Pseudo Class}
	     		SortedList

All of these classes are associated with corresponding iterator classes. Iterators provide generalized repetition operators for any collection class. Most iteration classes have the same protocol. A few provide several different forms of repetition. Thus there is a parallel hierarchy to the one shown above, which matches an iteration class to every collection class.

The following three classes are defined in Collection.i3, which also defines the Position class.

INTERFACE Collection;
IMPORT Object;

TYPE   (* Three Abstract Classes: Collection.T, Iterator, and Position *)

	ActionProc = PROCEDURE(o: REFANY);
	TransformProc = PROCEDURE(o: REFANY):REFANY;
	PredicateProc = PROCEDURE(o: REFANY):BOOLEAN;
	
	T = Object.T OBJECT (* Collection of REFANY objects *)
		METHODS
			insert(o:REFANY) ;	(* := NIL  *)
				(*  Insert o into self. *)
			remove(o:REFANY) ;	(* := NIL  *)
				(*  Remove o from self if present. *)
			newIterator():Iterator ;(* := NIL  *)
			eachDo(DoIt:ActionProc) ;(* := NIL  *)
				(*  apply DoIt to each element of self. *)

			firstThat(checkIt:PredicateProc):REFANY	:= FirstThat;
				(*  Return the first value for which checkIt returns TRUE. *)
			select(c:T; checkIt:PredicateProc)		:= Select;
				(*  Insert any element e into c if checkit(e) returns TRUE. *)
			reject(c:T; checkIt:PredicateProc)		:= Reject;
				(*  Insert any element e into c if checkit(e) returns FALSE. *)
			collect(c:T; transformIt:TransformProc)	:= Collect;
				(*  Insert transformIt(e) into c for each element e in self. *)
			empty():BOOLEAN					:= Empty;
				(*  Return TRUE if self is empty. *)
			element(o:REFANY):BOOLEAN			:= Element;
				(*  Return TRUE if o is in self. *)
			cardinality():INTEGER				:= Cardinality;
				(*  Returns the size of the collection. *)
		OVERRIDES
			writeIt						:= WriteIt;
		END;

	PROCEDURE FirstThat(self:T; checkIt:PredicateProc):REFANY ;
	PROCEDURE Select(self:T; c:T; checkIt:PredicateProc) ;
	PROCEDURE Reject(self:T; c:T; checkIt:PredicateProc) ;
	PROCEDURE Collect(self:T; c:T; transformIt:TransformProc) ;
	PROCEDURE Empty(self:T):BOOLEAN ;
	PROCEDURE Element(self:T; o:REFANY):BOOLEAN ;
	PROCEDURE Cardinality(self:T):INTEGER ;
	PROCEDURE WriteIt(self:T; f: Wr.T) ; 

TYPE 
	Iterator <: PublicIterator;
	PublicIterator = Object.T OBJECT
		METHODS
			initIterator(c: T): Iterator;
			nextItem(VAR o: REFANY):BOOLEAN ; (* := NIL  *)
				(*  If all items have been yielded then return FALSE.  Otherwise return TRUE
					and set o to the next unyielded item of self. *)
			reset() ; (* := NIL  *)
				(*  Reset to the beginning as if no elements had yet been yielded. *)
			short();
				(*  Short-circuit the iterator so that nextItem will next return FALSE. *)
			done():BOOLEAN;
				(*  TRUE if all items have been yielded (or none were initially present). *)
		END;

	Position <: PublicPosition;
	PublicPosition = Object.T OBJECT
		METHODS
			initPosition(c: T):Position;
			reset() ; (* := NIL  *)
				(*  Reset self the the "first" position of its collection. *)
		END;

END Collection.

INTERFACE Set;
IMPORT Collection;

TYPE	
	T <: Public;
	Public = Collection.T OBJECT
		METHODS
			union(s: T): T;
				(*  Return the set union of self and s. *)
			intersection(s: T): T;
				(*  Return the intersection of self and s. *)
			allBut(o: REFANY): T;
				(*  Return a set like self, but without o present. *)
			subset(s: T): BOOLEAN;
				(*  TRUE if self is a subset of s. *)
		END;

	PROCEDURE New(): T;

END Set.

INTERFACE Bag;
IMPORT Set;

TYPE	
	T <: Set.T; 

	PROCEDURE New(): T;

END Bag.

INTERFACE Dictionary;
IMPORT  Set, Magnitude;

TYPE	
	T <: Public;
	Public = Set.T OBJECT
		METHODS
			atPut(k: Magnitude.T; v: REFANY);
				(*  If self has no element with key k, then create a new association (k,v) and
					insert it.  Otherwise set the value of the association with key k to v. *)
			at(k: Magnitude.T): REFANY;
				(*  If self has an element with key k then return the associated value.  
					Otherwise return NIL. *)
			keyAtValue(v: REFANY): Magnitude.T; 
				(*  If self has an element with value v then return the associated key.  
					Otherwise return NIL. *)
			removeKey(k: Magnitude.T);
				(*  Remove the element with key k if present. *)
		END;

	PROCEDURE New(): T;

END Dictionary.

INTERFACE Lists;
IMPORT Collection;

TYPE
	T <: Public; (* List of REFANY *)
	Position <: PublicPosition;
	Iterator <: Collection.Iterator;

	WhereFound = {IsHere,IsNext,NotFound};

	Public = Collection.T OBJECT (* List of Objects *)
		METHODS
			initList():T;
			first(): REFANY;
				(* Returns a reference to the first element in the list. *)
			last(): REFANY;
				(*  Returns a reference to the last element in the list. *)
			removeFirst();
				(*  Removes the first element in self, if any. *)
			insertFirst(o: REFANY);
				(*  Insert o as the first element in self. *)
			insertLast(o: REFANY);
				(*  Insert o as the last element of self. *)
			removeLast();
				(*  Removes the last element of self. *)
			newPosition():Position;
				(*  Returns a new position into self, initialized to the first element. *)
		END;

	PublicPosition = Collection.Position OBJECT
		METHODS
			next();
				(*  Move to the next position. *)
			prev();
				(*  Move to the previous position unless at first position. *)
			toLast();
				(*  Move to the last position. *)
			insertFirst(o: REFANY);
				(*  Insert o as the first element of self and move there. *)
			insertAfter(o: REFANY);
				(*  Insert o after the current position and before the current next. *)
			at(): REFANY;
				(*  Return the value at this position. *)
			atPut(o: REFANY);
				(*  Put a new value o into this position. *)
			last():BOOLEAN;
				(*  TRUE if at the last position. *)
			afterLast():BOOLEAN;
				(*  TRUE if current position is AFTER the last position, as in an empty 
					list. *)
			deleteFirst();
				(*  Remove the first element in the list. *)
			deleteNext();
				(*  Remove the next value after the current position (if any). *)
			atNext(): REFANY;
				(*  Return the value in the next position or NIL if none. *)
			search(o: REFANY):WhereFound;
				(*  Search for o from the current position.  Returns:
					isHere if the current position contains o
					notFound if o cannot be found at or after the current position
					isNext if we can move forware (or not at all) to the predecessor of a
					position containing o, in which case we so move. *)
			moveTo(p:Position);
				(*  Move to the same position as p. *)
			exchangeValues(p:Position);
				(*  Swap the values at positions self and p. *)
		END;

	PROCEDURE New(): T;

END Lists.

INTERFACE Stack;
IMPORT  Collection;

TYPE	
	T <: Public;
	Public = Collection.T OBJECT
		METHODS
			push(o: REFANY);
				(* Insert o onto the "top" of the stack. *)
			pop(): REFANY;
				(* Remove and return the item at the top of the stack. *)
			top(): REFANY;
				(* Return a reference to the item at the top of the stack. *)
		END;

	PROCEDURE New(): T;

END Stack.


INTERFACE Queue;
IMPORT Collection;

TYPE	
	T <: Public;
	Public = Collection.T OBJECT
		METHODS
			enqueue(o: REFANY);
				(* Insert o at the rear of the queue. *)
			dequeue(): REFANY;
				(* Remove and return the item at the front of the queue. *)
			atFront(): REFANY;
				(* Return a reference to the item at the front of the queue. *)
		END;

	PROCEDURE New(): T;

END Queue.


INTERFACE DEQueue;
IMPORT Object, Collection, Queue;

TYPE	
	T <: Public;
	Public = Queue.T OBJECT
		METHODS
			insertFront(o:REFANY);
				(* Insert o at the front of the dequeue. *)
			removeRear():REFANY;
				(* Remove and return the item at the rear of the dequeue. *)
			atRear():REFANY;
				(* Return a reference to the item at the rear of the dequeue. *)
		END;

	PROCEDURE New(): T;

END DEQueue.

GENERIC INTERFACE SortableList(E);
IMPORT Lists;

(* REQUIRE:  E.T <: ROOT and support method
	less(e: E.T): BOOLEAN;
  ALSO:  Methods that do inserts only accept arguments of type E.T.  
	These include T.insert, T.insertFirst, T.insertLast, Position.insertFirst, 
	Position.insertAfter, Position.atPut;
*)

TYPE
	T <: Public;

	Public = Lists.T OBJECT (* Sortable List of E.T References *)
		METHODS
			selectionSort();
				(* Sort self using the selection sort algorithm. *)
			merge(list: T):T;
				(* Merge self and list and return the result.  Do not modify self or list. *)
	END;

	PROCEDURE New():T;

END SortableList.

INTERFACE IntegerList = SortableList(Integers) END IntegerList.

INTERFACE BinaryTree;
IMPORT Object, Collection;

TYPE	
	T <: Public;
	Iterator <: PublicIterator;
	Position <: PublicPosition;

	Public = Collection.T OBJECT
		METHODS
			(* Note: Insert inserts a leftmost leaf. *)
			newInOrderIterator():Iterator;
			(* Note: newIterator returns a pre-order iterator. *)
			newPosition():Position;
		END;

	PROCEDURE New(): T;

TYPE
	PublicIterator = Collection.Iterator OBJECT
		METHODS
			nextItemInOrder(VAR o: REFANY): BOOLEAN ;
			(* Note: nextItem returns the next item using pre-order. *)
			iterateFrom(p: Position);
				(* Iterate only from the node at position p. *)
			resetInOrder();
				(* Reset the iterator so it will properly iterate using in-order. *)
		END;

	FromDirection = {fromLeft, fromRight, noMove};

	PublicPosition = Collection.Position OBJECT
		METHODS
			setToRoot();
				(* Move to the root of the tree. *)
			at():REFANY;
				(* Return the item at the current position. *)
			atPut(o: REFANY);
				(* Insert value o into the current position. *)
			atLeftChild():REFANY;
				(* Return the value at the left child of the current position 
					(or NIL if none). *)
			atRightChild():REFANY;
				(* Return the value at the right child of the current position 
					(or NIL if none). *)
			exchangePositions(p: Position);
				(* Self and p will exchange positions. *)
			exchangeValues(p: Position);
				(* Self and p will swap values. *)
			find(o: REFANY);
				(* Search for o from the current position and move there.  
					No-op if not found. *)
			leaf():BOOLEAN;
				(* TRUE if current position has no children. *)
			noLeft():BOOLEAN;
				(* TRUE if current position has no left child. *)
			noRight():BOOLEAN;
				(* TRUE if current position has no right child. *)
			oneChild():BOOLEAN;
				(* TRUE if current position has only one child. *)
			isFull():BOOLEAN;
				(* TRUE if current position has two children. *)
			missingNode():BOOLEAN;
				(* TRUE if the position is not that of any data item: i.e. below a leaf. *)
			moveTo(p: Position);
				(* Make the position of self the same as that of p. *)
			moveLeft();
				(* Move to the left child if any.  May move below a leaf. *)
			moveRight();
				(* Move to the right child if any.  May move below a leaf. *)
			moveToParent():FromDirection;
				(* Move to the parent of the current position.  No-op if at root. *)
			isAtRoot():BOOLEAN;
				(* TRUE if current position is at the root. *)
			insertLeft(o: REFANY);
				(* Insert o to the left.  If the tree is empty this inserts the root. Otherwise
					it assumes that the left child is missing--no-op otherwise. *)
			insertRight(o: REFANY);
				(* Insert o to the right.  If the tree is empty this inserts the root. Otherwise
					it assumes that the right child is missing--no-op otherwise. *)
		END;

END BinaryTree.

INTERFACE Tree;
IMPORT Object, Collection;

TYPE	
	T <: Public;
	Public = Collection.T OBJECT
		METHODS
			newPosition(): Position;
		END;

	PROCEDURE New(): T;

TYPE
	Position <: PublicPosition;
	PublicPosition = Collection.Position OBJECT
		METHODS
			setToRoot();
			at():REFANY;
			atPut(o: REFANY);
			exchangePositions(p: Position);
			exchangeValues(p: Position);
			find(o: REFANY);
			leaf():BOOLEAN;
			noLeft():BOOLEAN;
			noRight():BOOLEAN;
			isFull():BOOLEAN;
			missingNode():BOOLEAN;
			moveTo(p: Position);
			moveToParent();  (* different protocol than in BinaryTree.T *)
			isAtRoot():BOOLEAN;
			moveToChild(n: INTEGER);
				(* Move to the n'th child of this parent.  Can move "past" the last child. *)
			insertChild(o: REFANY);
				(* Insert a new "first" child of this position. *)
			atChild(n: INTEGER):REFANY;
				(* Return the value at the n'th child of this position, or NIL of none. *)
		END;

	END Tree.

GENERIC INTERFACE BinarySearchTree (E);
IMPORT Object, Collection, BinaryTree;

(* REQUIRE: E.T <: ROOT and it must support methods
	equal(o: E.T):Boolean;
	less(o: E.T):Boolean;
	lessEqual(o: E.T):Boolean;
	greaterEqual(o: E.T):Boolean;
  ALSO: Insertion methods here require arguments of type E.T. 
*)
TYPE	
	T <: BinaryTree.T; 
		

	PROCEDURE New(): T;

TYPE

	Position <: PublicPosition;
	PublicPosition = BinaryTree.Position OBJECT
		METHODS
			seek(o: E.T):BOOLEAN; 
				(* Move to position of o or to a leaf where o can be inserted *)
			find(o: E.T); 
				(* Move to position of o only if it exists below current *)
		END;

END BinarySearchTree.

INTERFACE DynamicArray;
IMPORT Object, Collection;

TYPE	
	T <: Public;
	Public = Collection.T OBJECT
		METHODS
			atPut(where: CARDINAL; what: REFANY);
				(* Put what at location where. *)
			at(where: CARDINAL):REFANY;
				(* Return the value at location where. *)
			extend(by: CARDINAL);
				(* Extend the length of the array by appending "by" new cells. *)
			physicalSize():CARDINAL;
				(* Return the current physical size of the array. *)
			swap(a,b:CARDINAL);
				(* Swap the values at locations a and b. *)
			sequentialSearch(what: REFANY; VAR where: CARDINAL):BOOLEAN;
				(* Search for what.  Return TRUE if found and set where to the cell number.
					If not found, return false and do not change where. *)
		END;

	PROCEDURE New(size: CARDINAL): T;
		(*  Set the initial length to size. *)

TYPE
	Iterator <: Collection.Iterator;

END DynamicArray.

INTERFACE Intervals;
IMPORT Object, Collection;

TYPE	
	T <: Public;
	Public = Collection.T OBJECT
		METHODS
			at(loc: INTEGER):INTEGER;
				(* Return the integer at position loc. *)
			size(): CARDINAL;
				(* Return the number of integers in the interval. *)
		END;

	PROCEDURE New(fromVal, toVal, byVal: INTEGER): T;

TYPE
	Iterator <: Collection.Iterator; (* returns elements in Integers.T *)

END Intervals.

		atPut(i: INTEGER; o: Object.T);
		at(i: INTEGER):Object.T;