Notes on Interfaces, Classes, and Methods
Read these notes before using any classes:
General
 | clone and toString could be omitted: The methods clone and toString could be omitted from lamborne interfaces as they are inherited from Object, but they are included throughout as reminders to users and implementers of the abstract data types (ADTs) . |
| toArray is shallow:The method toArray returns the items in a collection, not copies of these items. This same convention is followed throughout java.util and lamborne. In this regard, toArray follows the convention established by clone, which also is shallow. |
| collectionView is useful: The method collectionView is available in most interfaces and gives access to the many convenient methods in the Collection interface, such as contains and containsAll. The method also provides a mechanism for passing many ADTs as parameters in situations where a collection is required. |
| iterators and fail fast: Generally iterators are backed by their underlying collections. This can cause a potentially ambiguous situation if mutator messages are sent to the backing collection while an iterator is active. In order to expose these ambiguities as quickly as possible, the iterator throws an exception as soon as the next method is called again. This is called "fail fast." |
| time complexity of iterators: Methods that traverse iterators are O(n) plus the complexity of creating the iterator, which is usually O(1), but sometimes can be more. |
Queues
| iterator: The iterator is connected to the underlying structure in LinkedPriorityQueue but not in HeapPriorityQueue. |
Heap
| sort method: The arrays returned by the static sort methods contain the items provided by the input parameter, rather than copies of these items. In this regard the sort methods are similar to the methods clone and toArray. They are "shallow |
| order of items in iterator: Because a heap has the largest item on top, the "natural order" for a heap iterator is descending order on the items. This can be done at an initial cost of O(n log n). The other choice would be for the iterator to serve up items in the physical order in which they are stored in the heap. The cost would then be O(1) per item, but the iterator would be less useful. |
| time complexity of the equals method: An O(n) equals method could be implemented in ArrayHeap. This would be better than the O(n log n) equals method currently implemented in AbstractHeap. The current method is based on an iterator that in turn takes O(n log n) to create in ArrayHeap. Interested users are encouraged to change the implementation to better suit their purposes. |
| iterator: The ArrayHeap iterator is NOT connected to the underlying collection. |
| time complexity of the add method: The method add in class ArrayHeap occasionally triggers a doubling in the size of the underlying array. When this occurs, the operation is O(n), but amortized over all additions, the operation is O(1) per addition. |
| time complexity of the pop method: The method pop in class ArrayHeap occasionally triggers a halving in the size of the underlying array. When this occurs, the operation is O(n), but amortized over all pops, the operation is O(1) per pop. |
SortedCollection
· purpose of the get (item) and remove (item) methods: Use the "Object get (Object item)" method to get an item that "equals" a given item, but is in fact different. Suppose, for instance, that student objects have a unique id and that "equals" is based on that id. One can then use the "get" method to retrieve a student with a given id. This method also makes it possible to use SortedCollection as the basis for SortedMap. The SortedMap keeps a SortedCollection of associations, where "equals" is based on the key portion of the association. Similar remarks apply to the "boolean remove (Object item)" method.
· iterator: The iterator method for BinarySearchTree creates a queue from an inorder traversal of the tree and returns an iterator on this queue. This is more appropriate than returning an iterator on a list because the iterator for a queue doesn't allow removal whereas the iterators on LinkedList and ArrayList do. Removal from a BinarySearchTree should only be done directly, not via an iterator.
· iterator: The iterator on a BinarySearchTree is not connected directly to its backing store but rather to a queue created from the tree.
Tree and TreeIterator
· get methods: The get methods for Tree and TreeIterator never throw an exception, instead they return null. In contrast an iterator's next method does throw an exception if one tries to iterate too far.
· how
to interpret index[]
· Tree nodes are located using a hierarchical indexing scheme, and this index is represented as an array of integers.
· The root corresponds to the empty array {}
·
The index {2,3,1} refers to the item at position root / 2nd
child / 3rd child / 1st child or in other words:
root
child
1
child 2
child 1
child 2
child 3
child 1
<<<<<< this one is at index {2,3,1}
· Non standard representations are also handled, for instance,
· {0,0,0} and {0} both refer to the root
· {2,0,3,4} and {2} both refer to root / 2nd child
· {2,1,0,4,0,0,5} and {2,1} both refer to root / 2nd child / 1st child
· Basically, processing stops at the first 0 encountered.
| role of TreeIterator: Most of a tree's methods are implemented in AbstractTree. This is possible because the methods are implemented by means of TreeIterator and AbstractTree uses TreeIterator all over the place. |
| implementation of Iterator: Iterator, in contrast to TreeIterator, does not remain in direct touch with the underlying tree, because it first builds a queue and then returns an iterator on that queue. |
| implementation of Iterator: Iterator is based on a queue rather than on a list because list iterator supporst remove, which in this situation would be misleading since the iterator is no longer in touch with the underlying tree. |
| size method: The size method in a LinkedTree is usually O(1); however, after a node has just been deleted, the size information is invalidated and requires O(n) to recalculate |
| time complexity of methods: The time complexity of many abstract tree methods depends on the complexity of moveTo(index), which in the average case, for a fairly balanced LinkedTree, would be O(log n) |