Package dsa

Interface OrderedST<K extends Comparable<K>,V>

Type Parameters:
K - the type of keys in the symbol table.
V - the type of values in the symbol table.
All Known Implementing Classes:
BinarySearchST, BinarySearchTreeST, RedBlackBinarySearchTreeST
public interface OrderedST<K extends Comparable<K>,V>
This interface specifies the API for the ordered symbol table data structure.

  • Method Summary

    Modifier and Type
    Method
    Description
    K
    ceiling(K key)
    Returns the smallest key in this symbol table that is larger than or equal to key.
    boolean
    contains(K key)
    Returns true if this symbol table contains key, and false otherwise.
    void
    delete(K key)
    Deletes key and the associated value from this symbol table.
    void
    deleteMax()
    Deletes the largest key and the associated value from this symbol table.
    void
    deleteMin()
    Deletes the smallest key and the associated value from this symbol table.
    K
    floor(K key)
    Returns the largest key in this symbol table that is smaller than or equal to key.
    V
    get(K key)
    Returns the value associated with key in this symbol table, or null .
    boolean
    isEmpty()
    Returns true if this symbol table is empty, and false otherwise.
    Iterable<K>
    keys()
    Returns all the keys in this symbol table in sorted order.
    Iterable<K>
    keys(K lo, K hi)
    Returns the keys in this symbol table that are in the interval [lo, hi] in sorted order.
    K
    max()
    Returns the largest key in this symbol table.
    K
    min()
    Returns the smallest key in this symbol table.
    void
    put(K key, V value)
    Inserts the key and value pair into this symbol table.
    int
    rank(K key)
    Returns the number of keys in this symbol table that are strictly smaller than key.
    K
    select(int k)
    Returns the key in this symbol table with the rank k.
    int
    size()
    Returns the number of key-value pairs in this symbol table.
    int
    size(K lo, K hi)
    Returns the number of keys in this symbol table that are in the interval [lo, hi].
    String
    toString()
    Returns a string representation of this symbol table.

  • Method Details

    • isEmpty

      boolean isEmpty()
      Returns true if this symbol table is empty, and false otherwise.
      Returns:
      true if this symbol table is empty, and false otherwise.

    • size

      int size()
      Returns the number of key-value pairs in this symbol table.
      Returns:
      the number of key-value pairs in this symbol table.

    • put

      void put(K key, V value)
      Inserts the key and value pair into this symbol table.
      Parameters:
      key - the key.
      value - the value.

    • get

      V get(K key)
      Returns the value associated with key in this symbol table, or null .
      Parameters:
      key - the key.
      Returns:
      the value associated with key in this symbol table, or null .

    • contains

      boolean contains(K key)
      Returns true if this symbol table contains key, and false otherwise.
      Parameters:
      key - the key.
      Returns:
      true if this symbol table contains key, and false otherwise.

    • delete

      void delete(K key)
      Deletes key and the associated value from this symbol table.
      Parameters:
      key - the key.

    • keys

      Iterable<K> keys()
      Returns all the keys in this symbol table in sorted order.
      Returns:
      all the keys in this symbol table in sorted order.

    • min

      K min()
      Returns the smallest key in this symbol table.
      Returns:
      the smallest key in this symbol table.

    • max

      K max()
      Returns the largest key in this symbol table.
      Returns:
      the largest key in this symbol table.

    • deleteMin

      void deleteMin()
      Deletes the smallest key and the associated value from this symbol table.

    • deleteMax

      void deleteMax()
      Deletes the largest key and the associated value from this symbol table.

    • floor

      K floor(K key)
      Returns the largest key in this symbol table that is smaller than or equal to key.
      Parameters:
      key - the key.
      Returns:
      the largest key in this symbol table that is smaller than or equal to key.

    • ceiling

      K ceiling(K key)
      Returns the smallest key in this symbol table that is larger than or equal to key.
      Parameters:
      key - the key.
      Returns:
      the smallest key in this symbol table that is larger than or equal to key.

    • rank

      int rank(K key)
      Returns the number of keys in this symbol table that are strictly smaller than key.
      Parameters:
      key - the key.
      Returns:
      the number of keys in this symbol table that are strictly smaller than key.

    • select

      K select(int k)
      Returns the key in this symbol table with the rank k.
      Parameters:
      k - the rank.
      Returns:
      the key in this symbol table with the rank k.

    • size

      int size(K lo, K hi)
      Returns the number of keys in this symbol table that are in the interval [lo, hi].
      Parameters:
      lo - lower key.
      hi - higher key
      Returns:
      the number of keys in this symbol table that are in the interval [lo, hi].

    • keys

      Iterable<K> keys(K lo, K hi)
      Returns the keys in this symbol table that are in the interval [lo, hi] in sorted order.
      Parameters:
      lo - lower key.
      hi - higher key.
      Returns:
      the keys in this symbol table that are in the interval [lo, hi] in sorted order.

    • toString

      String toString()
      Returns a string representation of this symbol table.
      Overrides:
      toString in class Object
      Returns:
      a string representation of this symbol table.