Implementation of SortedCollection
Warning: the implementation of one method
has been left as an exercise.
The table below indicates where methods are implemented and the time
complexity of these methods. Some methods are
implemented in more than one place. When this
happens, each entry overrides the entries to its left. When an entry says "based on
iterator" or "traverse iterator" or "uses size," then the time
complexity depends on the iterator or size method.
|
|
SortedCollection Implementation
|
Abstract
Container
|
Abstract
Sorted
Collection
|
LinkedBST
Sorted
Collection
|
|
|
constructor ()
|
O(1)
|
O(1)
|
O(1)
|
|
|
constructor (Collection
col, boolean addUnique)
|
|
|
O(n log n) if balanced
|
|
|
|
|
|
|
| boolean
|
add (Object item)
|
|
abstract
|
O(log n) if balanced
|
| boolean
|
addUnique (Object item)
|
|
uses add method
|
|
| void
|
clear ()
|
O(1)
|
|
O(1)
|
| Object
|
clone ()
|
|
|
O(n log n) if balanced
|
| Collection
|
collectionView ()
|
based on iterator
|
|
|
| boolean
|
contains (Object item)
|
|
uses get method
|
|
| boolean
|
equals (Object other)
|
|
traverse iterator
|
|
| int
|
indexOf (Object item)
|
|
exercise
|
|
| Object
|
get (int i)
|
|
abstract
|
O(n)
|
| Object
|
get (Object item)
|
|
abstract
|
O(log n) if balanced
|
| int
|
hashCode ()
|
traverse iterator
|
|
|
| boolean
|
isEmpty ()
|
uses size method
|
|
|
| Iterator
|
iterator ()
|
abstract
|
|
O(n)
|
| Object
|
remove (int i)
|
|
uses get (i) and remove (item)
|
|
| boolean
|
remove (Object item)
|
|
abstract
|
O(log n) if balanced
|
| int
|
size ()
|
O(1)
|
|
|
| Object[]
|
toArray ()
|
traverse iterator
|
|
|
| String
|
toString ()
|
traverse iterator
|
|
|