Packages

t

de.h2b.scala.lib.coll.adt.searching

OrderedSymbolTable

trait OrderedSymbolTable[Key, Value] extends BasicSymbolTable[Key, Value]

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

Linear Supertypes
BasicSymbolTable[Key, Value], AnyRef, Any
Known Subclasses
BinarySearchTable, BinarySearchTree
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. OrderedSymbolTable
  2. BasicSymbolTable
  3. AnyRef
  4. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Abstract Value Members

  1. abstract def apply(key: Key): Value

    returns

    value paired with key

    Definition Classes
    BasicSymbolTable
    Exceptions thrown

    NoSuchElementException if key is not in table

  2. abstract def ceil(key: Key): Key

    returns

    the smallest key greater than or equal to the specified key

    Exceptions thrown

    NoSuchElementException if key is greater than maximum key

  3. abstract def delete(key: Key): Unit

    Removes key/value pair from table.

    Removes key/value pair from table.

    Definition Classes
    BasicSymbolTable
    Exceptions thrown

    NoSuchElementException if key is not in table

  4. abstract def floor(key: Key): Key

    returns

    the largest key less than or equal to the specified key

    Exceptions thrown

    NoSuchElementException if key is less than minimum key

  5. abstract def keys(lo: Key, hi: Key): Iterable[Key]

    returns

    all keys in the table between lo and hi (inclusive) in sorted order

  6. abstract def max: Key

    returns

    the largest key

    Exceptions thrown

    NoSuchElementException if table is empty

  7. abstract def min: Key

    returns

    the smallest key

    Exceptions thrown

    NoSuchElementException if table is empty

  8. abstract val ord: Ordering[Key]
    Attributes
    protected
  9. abstract def rank(key: Key): Int

    returns

    the number of keys less than the specified key

  10. abstract def select(k: Int): Key

    returns

    the key of rank k

    Exceptions thrown

    NoSuchElementException if k is less than 0 or greater than the maximum rank

  11. abstract def size: Int
    Definition Classes
    OrderedSymbolTable → BasicSymbolTable
  12. abstract def update(key: Key, value: Value): Unit

    Inserts key/value pair into table.

    Inserts key/value pair into table. Replaces value if key is already there.

    Definition Classes
    BasicSymbolTable

Concrete Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  6. def contains(key: Key): Boolean
    Definition Classes
    BasicSymbolTable
  7. def deleteMax(): Unit

    Removes the node with the the largest key.

    Removes the node with the the largest key.

    Exceptions thrown

    NoSuchElementException if table is empty

  8. def deleteMin(): Unit

    Removes the node with the the smallest key.

    Removes the node with the the smallest key.

    Exceptions thrown

    NoSuchElementException if table is empty

  9. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  10. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  11. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  12. def get(key: Key): Option[Value]
    Definition Classes
    BasicSymbolTable
  13. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  14. def getOrElse(key: Key, default: ⇒ Value): Value
    Definition Classes
    BasicSymbolTable
  15. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  16. def isEmpty: Boolean
    Definition Classes
    BasicSymbolTable
  17. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  18. def keys(): Iterable[Key]

    returns

    all keys in the table

    Definition Classes
    OrderedSymbolTable → BasicSymbolTable
  19. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  20. final def notify(): Unit
    Definition Classes
    AnyRef
  21. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  22. def size(lo: Key, hi: Key): Int

    returns

    the number of keys between lo and hi (inclusive)

  23. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  24. def toString(): String
    Definition Classes
    OrderedSymbolTable → BasicSymbolTable → AnyRef → Any
  25. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  26. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  27. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from BasicSymbolTable[Key, Value]

Inherited from AnyRef

Inherited from Any

Ungrouped