Type Members

1.  trait BasicSymbolTable [Key, Value] extends AnyRef

   This trait represents a symbol table of generic key/value pairs.

   This trait represents a symbol table of generic key/value pairs.

   It supports the usual put, get, contains, delete, size, and is-empty methods. It also provides a keys method for iterating over all of the keys.

   A symbol table implements the associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value.

   Adapted from the book Algorithms 4 by R. Sedgewick and K. Wayne.

   See also

   Section 3.1 of Algorithms, 4th Edition

   Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. http://algs4.cs.princeton.edu

2.  class BinarySearchTable [Key, Value] extends OrderedSymbolTable[Key, Value]

   This class implements an ordered symbol table of generic key/value pairs.

   This class implements an ordered symbol table of generic key/value pairs.

   This implementation uses a resizing array and binary search.

   The get' and contains as well as the tow-argument size, the floor and the ceiling operations take logarithmic time. The minimum, maximum and select as well as is-empty and the one-argument size operations are constant in time. The put operation is linear in time in the worst case.

   Adapted from the book Algorithms 4 by R. Sedgewick and K. Wayne.

   See also

   Section 3.1 of Algorithms, 4th Edition

   Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. http://algs4.cs.princeton.edu

3.  class BinarySearchTree [Key, Value] extends OrderedSymbolTable[Key, Value]

   This class implements an ordered symbol table of generic key/value pairs.

   This class implements an ordered symbol table of generic key/value pairs.

   This implementation uses a binary search tree.

   The put, get and contains operations take linear time in the worst case, but logarithmic time on the average. All order-based operations take time proportional to the height of the tree in the worst case; this applies to minimum, maximum and select as well as floor, ceiling and the tow-argument size. The one-argument size and is-empty are constant in time.

   Adapted from the book Algorithms 4 by R. Sedgewick and K. Wayne.

   See also

   Section 3.2 of Algorithms, 4th Edition

   Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. http://algs4.cs.princeton.edu

4.  trait OrderedSymbolTable [Key, Value] extends BasicSymbolTable[Key, Value]

   This trait represents an ordered symbol table of generic key/value pairs.

   This trait represents an ordered symbol table of generic key/value pairs.

   It supports the usual put, get, contains, delete, size, and is-empty methods. It also provides a keys method for iterating over all of the keys.

   It also provides ordered methods for finding the minimum, maximum, floor, and ceiling.

   A symbol table implements the associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value.

   Adapted from the book Algorithms 4 by R. Sedgewick and K. Wayne.

   See also

   Section 3.1 of Algorithms, 4th Edition

   Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. http://algs4.cs.princeton.edu

5.  class SequentialSearchTable [Key, Value] extends BasicSymbolTable[Key, Value]

   This class implements an unordered symbol table of generic key/value pairs.

   This class implements an unordered symbol table of generic key/value pairs.

   This implementation uses a singly-linked list and sequential search. It relies on the equals method to test whether two keys are equal. It does not call either the compare or hashCode method.

   The put and delete operations take linear time; the get and contains operations takes linear time in the worst case. The size, and is-empty operations take constant time. Construction takes constant time.

   Adapted from the book Algorithms 4 by R. Sedgewick and K. Wayne.

   See also

   Section 3.1 of Algorithms, 4th Edition

   Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. http://algs4.cs.princeton.edu