itu.algs4.searching package

Submodules

itu.algs4.searching.binary_search_st module

class itu.algs4.searching.binary_search_st.BinarySearchST(capacity=2)

Bases: object

The BST class 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 ordered methods for finding the minimum, maximum, floor, select, and ceiling. 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. Unlike java.util.Map, this class uses the convention that values cannot be None—setting the value associated with a key to None is equivalent to deleting the key from the symbol table.

This implementation uses a sorted array. It requires that the key type implements the Comparable interface and calls the compareTo() and method to compare two keys. It does not call either equals() or hashCode(). The put and remove operations each take linear time in the worst case the contains, ceiling, floor, and rank operations take logarithmic time the size, is-empty, minimum, maximum, and select operations take constant time. Construction takes constant time.

ceiling(key)

Returns the smallest key in this symbol table greater than or equal to key.

Parameters:

key – the key
Returns:

the smallest key in this symbol table greater than or equal to key
Raises:
  • ValueError – if there is no such key
  • ValueError – if key is None
contains(key)

Does this symbol table contain the given key?

Parameters:key – the key
Returns:True if this symbol table contains key and False otherwise
Raises:ValueError – if key is None
delete(key)

Removes the specified key and associated value from this symbol table (if the key is in the symbol table).

Parameters:key – the key
Raises:ValueError – if key is None
deleteMax()

Removes the largest key and associated value from this symbol table.

Raises:ValueError – if the symbol table is empty
deleteMin()

Removes the smallest key and associated value from this symbol table.

Raises:ValueError – if the symbol table is empty
floor(key)

Returns the largest key in this symbol table less than or equal to key.

Parameters:

key – the key
Returns:

the largest key in this symbol table less than or equal to key
Raises:
  • ValueError – if there is no such key
  • ValueError – if key is None
get(key)

Returns the value associated with the given key in this symbol table.

Parameters:key – the key
Returns:the value associated with the given key if the key is in the symbol table and None if the key is not in the symbol table
Raises:ValueError – if key is None
is_empty()

Returns True if this symbol table is empty.

Returns:True if this symbol table is empty False otherwise
keys()

Returns all keys in this symbol table as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).

Returns:all keys in this symbol table
keys_between(lo, hi)

Returns all keys in this symbol table in the given range, as an Iterable.

Parameters:
  • lo – minimum endpoint
  • hi – maximum endpoint
Returns:

all keys in this symbol table between lo (inclusive) and hi (inclusive)
Raises:

ValueError – if either lo or hi are None
max()

Returns the largest key in this symbol table.

Returns:the largest key in this symbol table
Raises:ValueError – if this symbol table is empty
min()

Returns the smallest key in this symbol table.

Returns:the smallest key in this symbol table
Raises:ValueError – if this symbol table is empty
put(key, val)

Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is None.

Parameters:
  • key – the key
  • val – the value
Raises:

ValueError – if key is None
rank(key)

Returns the number of keys in this symbol table strictly less than key.

Parameters:key – the key
Returns:the number of keys in the symbol table strictly less than key
Raises:ValueError – if key is None
select(k)

Return the kth smallest key in this symbol table.

Parameters:k – the order statistic
Returns:the kth smallest key in this symbol table
Raises:ValueError – unless k is between 0 and n-1
size()

Returns the number of key-value pairs in this symbol table.

Returns:the number of key-value pairs in this symbol table
size_between(lo, hi)

Returns the number of keys in this symbol table in the specified range.

Parameters:
  • lo – minimum endpoint
  • hi – maximum endpoint
Returns:

the number of keys in this symbol table between lo (inclusive) and hi (inclusive)
Raises:

ValueError – if either lo or hi is None

itu.algs4.searching.bst module

class itu.algs4.searching.bst.BST

Bases: typing.Generic

ceiling(key: Key) → Key

Returns the smallest key in the symbol table greater than or equal to key Raises NoSuchElementException if no such key exists.

contains(key: Key) → bool

Does this symbol table contain the given key?

Parameters:key – the key to search for
Return boolean:true if symbol table contains key, false otherwise
delete(key: Key) → None

Removes the specified key and its associated value from this symbol table (if the key is in this symbol table)

delete_max() → None

Removes the largest key and associated value from the symbol table.

delete_min() → None

Removes the smallest key and associated value from the symbol table TODO exception?

floor(key: Key) → Key

Returns the largest key in the symbol table less than or equal to key Raises NoSuchElementException if no such key exists.

get(key: Key) → Optional[Val]

Returns the value associated with the given key.

Parameters:key – The key whose value is returned
Returns:the value associated with the given key if the key

is in the symbol table, None otherwise

height() → int

Returns the height of the BST (for debugging)

is_empty() → bool

Returns true if this symbol table is empty.

keys() → itu.algs4.fundamentals.queue.Queue[~Key][Key]

Returns all keys in the symbol table as a list.

level_order() → itu.algs4.fundamentals.queue.Queue[~Key][Key]

Returns the keys in the BST in level order (for debugging)

max() → Key

Returns the larget key in the symbol table.

min() → Key

Returns the smallest key in the BST.

put(key: Key, value: Optional[Val]) → None

Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is None.

Parameters:value (key,) – the key-value pair to be inserted
range_keys(lo: Key, hi: Key) → itu.algs4.fundamentals.queue.Queue[~Key][Key]

returns all keys in the symbol table in the given range as a list.

Parameters:
  • lo – minimum endpoint
  • hi – maximum endpoint
Returns:

all keys in symbol table between lo (inclusive) and hi (inclusive)
rank(key: Key) → int

Returns the number of keys in the symbol table strictly less than key.

Parameters:key – the key
Returns:the number of keys in the symbol table strictly less than key
Return type:int
Raises:IllegalArgumentException – if key is None
select(k: int) → Key

Return the kth smallest key in the symbol table.

Parameters:k – the order statistic
Returns:the kth smallest key in the symbol table
Raises:IllegalArgumentException – unless k is between 0 and n-1
size() → int

Returns the number of key-value pairs in this symbol table.

size_range(lo: Key, hi: Key) → int

Returns the number of keys in the symbol table in the given range.

Parameters:
  • lo – minimum endpoint
  • hi – maximum endpoint
Returns:

the number of keys in the symbol table between lo

(inclusive) and hi (inclusive) :rtype: int :raises IllegalArgumentException: if either lo or hi is None

class itu.algs4.searching.bst.Comparable(*args, **kwargs)

Bases: typing_extensions.Protocol

class itu.algs4.searching.bst.Node(key: Key, value: Optional[Val], size: int)

Bases: typing.Generic

itu.algs4.searching.file_index module

itu.algs4.searching.frequency_counter module

itu.algs4.searching.linear_probing_hst module

class itu.algs4.searching.linear_probing_hst.LinearProbingHashST(capacity=4)

Bases: object

The LinearProbingHashST class represents a symbol table of dynamic key- value pairs. It supports the usual put, get, contains, delete, size, and is- empty methods. It also provides a key_list 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. Unlike the Map- class in Java, this class uses the convention that values cannot be null/None. Setting the value associated with a key to None is equivalent to deleting the key from the symbol table.

This implementation uses a linear probing hash table. It requires that the key type overrides the __eq__ and __hash__ methods. The expected time per put, contains, or remove operation is constant, subject to the uniform hashing assumption. The size, and is-empty operations take constant time. Construction takes constant time.

contains(key)

Returns True if this symbol table contains the specified key.

Parameters:key – the key
Returns:True if this symbol table contains the key; False otherwize
Raises:ValueError – if key is None
delete(key)

Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).

Parameters:key – the key
Raises:ValueError – if key is None
get(key)

Returns the value associated with the specified key.

Parameters:key – the key
Returns:the value associated with the key in the symbol table; None if no such value
Raises:ValueError – if key is None
is_empty()

Returns True if this symbol table is empty.

Returns:True if this symbol table is empty; False otherwise
key_list()

Returns the keys in the symbol table as an iterable :returns: A list containing all keys

put(key, value)

Inserts the specified key-value paur into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is None.

Parameters:
  • key – the key
  • value – the value
Raises:

ValueError – if key is None.
size()

Returns the number of key-value pairs in this symbol table.

Returns:the number of key-value pairs in this symbol table.
itu.algs4.searching.linear_probing_hst.main()

Unit tests the LinearProbingHashST data type.

itu.algs4.searching.lookup_csv module

itu.algs4.searching.lookup_index module

itu.algs4.searching.red_black_bst module

class itu.algs4.searching.red_black_bst.Comparable(*args, **kwargs)

Bases: typing_extensions.Protocol

class itu.algs4.searching.red_black_bst.Node(key: Key, val: Val, color: bool, size: int)

Bases: typing.Generic

RedBlackBST helper node data type.

class itu.algs4.searching.red_black_bst.RedBlackBST

Bases: typing.Generic

The RedBlackBST class 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 ordered methods for finding the minimum, maximum, floor, and ceiling. It also provides a keys method for iterating over all 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. This class uses the convention that values cannot be None-setting the value associated with a key to None is equivalent to deleting the key from the symbol table. This implementation uses a left-leaning red-black BST. It requires that the keys are all of the same type and that they can be compared. The put, contains, remove, minimum, maximum, ceiling, and floor operations each take logarithmic time in the worst case, if the tree becomes unbalanced. The size, and is-empty operations take constant time. Construction takes constant time.

BLACK = False
RED = True
ceiling(key: Key) → Key

Returns the smallest key in the symbol table greater than or equal to key.

Parameters:

key – the key
Returns:

the smallest key in the symbol table greater than or equal to key
Raises:
contains(key: Key) → bool

Does this symbol table contain the given key?

Parameters:key – the key
Returns:True if this symbol table contains key and False otherwise
delete(key: Key) → None

Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).

Parameters:key – the key
Raises:IllegalArgumentException – if key is None
delete_max() → None

Removes the largest key and associated value from the symbol table.

Raises:NoSuchElementException – if the symbol table is empty
delete_min() → None

Removes the smallest key and associated value from the symbol table.

Raises:NoSuchElementException – if the symbol table is empty
floor(key: Key) → Key

Returns the largest key in the symbol table less than or equal to key.

Parameters:

key – the key
Returns:

the largest key in the symbol table less than er equal to key
Raises:
get(key: Key) → Optional[Val]

Returns the value associated with the given key.

Parameters:key – the key
Returns:the value associated with the given key if the key is in the symbol table

and None if the key is not in the symbol table :raises IllegalArgumentException: if key is None

height() → int

Returns the height of the RedBlackBST

Returns:the height of the RedBlackBST (a 1-node tree has height 0)
is_empty() → bool

Is this symbol table empty?

Returns:True if this symbol table is empty and False otherwise
keys() → itu.algs4.fundamentals.queue.Queue[~Key][Key]

Returns all keys in the symbol table.

Returns:all keys in the symbol table
keys_range(lo: Key, hi: Key) → itu.algs4.fundamentals.queue.Queue[~Key][Key]

Returns all keys in the symbol table in the given range.

Parameters:
  • lo – minimum endpoint
  • hi – maximum endpoint
Returns:

all keys in the symbol table between lo (inclusive) and hi (inclusive)
Raises:

IllegalArgumentException – if either lo or hi is None
max() → Key

Returns the largest key in the symbol table.

Returns:the largest key in the symbol table
Raises:NoSuchElementException – if the symbol table is empty
min() → Key

Returns the smallest key in the symbol table.

Returns:the smallest key in the symbol table
Raises:NoSuchElementException – if the symbol table is empty
put(key: Key, val: Val) → None

Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is None.

Parameters:
  • key – the key
  • val – the value
Raises:

IllegalArgumentException – if key is None
rank(key: Key) → int

Returns the number of keys in the symbol table strictly less than key.

Parameters:key – the key
Returns:the number of keys in the symbol table strictly less than key
Raises:IllegalArgumentException – if key is None
select(k: int) → Key

Return the kth smallest key in the symbol table.

Parameters:k – the order statistic
Returns:the kth smallest key in the symbol table
Raises:IllegalArgumentException – unless k is between 0 and n-1
size() → int

Return the number of key-value pairs in this symbol table.

Returns:the number of key-value pairs in this symbol table
size_range(lo: Key, hi: Key) → int

Returns the number of keys in the symbol table in the given range.

Parameters:
  • lo – minimum endpoint
  • hi – maximum endpoint
Returns:

the number of keys in the symbol table between lo

(inclusive) and hi (inclusive) :raises IllegalArgumentException: if either lo or hi is None

itu.algs4.searching.seperate_chaining_hst module

class itu.algs4.searching.seperate_chaining_hst.SeparateChainingHashST(M=997)

Bases: object

The SeparateChainingHashST class represents a symbol table of dynamic 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. Unlike the Map- class in Java, this class uses the convention that values cannot be null/None. Setting the value associated with a key to None is equivalent to deleting the key from the symbol table.

This implementation uses a separate chaining hash table. It requires that the key type overrides the __eq__ and __hash__ methods. The expected time per put, contains, or remove operation is constant, subject to the uniform hashing assumption. The size, and is-empty operations take constant time. Construction takes constant time.

contains(key)

Returns true if this symbol table contains the specified key.

Parameters:key – the key
Returns:True if this symbol table contains the key; False otherwise.
Raises:ValueError – if key is None.
delete(key)

Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).

Parameters:key – the key
Raises:ValueError – if key is None
get(key)

Returns the value associated with the specified key.

Parameters:key – the key
Returns:the value associated with the key in the symbol table; None if no such value
Raises:ValueError – if key is None
is_empty()

Returns true if the symbol table is empty.

Returns:True if this symbol table is empty; False otherwise.
keys()

Returns the keys in the symbol table as an iterable :returns: A list containing all keys

put(key, value)

Inserts the specified key-value paur into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is None.

Parameters:
  • key – the key
  • value – the value
Raises:

ValueError – if key is None.
size()

Returns the number of key-value pairs in this symbol table.

Returns:the number of key-value pairs in this symbol table.
itu.algs4.searching.seperate_chaining_hst.main()

Unit tests the SeparateChainingHashST data type.

itu.algs4.searching.sequential_search_st module

class itu.algs4.searching.sequential_search_st.SequentialSearchST

Bases: object

The SequentialSearchST class represents an (unordered) 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. The class also uses the convention that values cannot be None. Setting the value associated with a key to None is equivalent to deleting the key from the symbol table.

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 compareTo() 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.

class Node(key, val, next)

Bases: object

contains(key)

” Returns true if this symbol table contains the specified key.

:param key the key :returns: true if this symbol table contains key

false otherwise
Raises:ValueError – if key is None
delete(key)

Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).

:param key the key :raises ValueError: if key is None

get(key)

Returns the value associated with the given key in this symbol table.

Parameters:key – the key
Returns:the value associated with the given key if the key is in the symbol table and None if the key is not in the symbol table
Raises:ValueError – if key is None
is_empty()

Returns true if this symbol table is empty.

Returns:true if this symbol table is empty false otherwise
keys()

Returns all keys in the symbol table as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for Key key in st.keys().

Returns:all keys in the symbol table
put(key, val)

Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is None.

Parameters:
  • key – the key
  • val – the value
Raises:

ValueError – if key is None
size()

Returns the number of key-value pairs in this symbol table.

Returns:the number of key-value pairs in this symbol table

itu.algs4.searching.set module

class itu.algs4.searching.set.SET(x=None)

Bases: object

add(key)
ceiling(key)
contains(key)
delete(key)
floor(key)
hashCode()
intersects(that)
is_empty()
max()
min()
size()
union(that)
itu.algs4.searching.set.main()

itu.algs4.searching.sparse_vector module

class itu.algs4.searching.sparse_vector.SparseVector(d)

Bases: object

The SparseVector class represents a d-dimensional mathematical vector. Vectors are mutable: their values can be changed after they are created. It includes methods for addition, subtraction, dot product, scalar product, unit vector and Euclidean norm.

The implementation is a symbol table of indices and values for which the vector coordinates are nonzero. This makes it efficient when most of the vector coordinates are zero.

dimension()

Returns the dimension of this vector.

Returns:the dimension of this vector.
dot(that)

Returns the inner product of this vector with the specified vector.

Parameters:that – the other vector
Returns:the dot product between this vector and that vector
Raises:ValueError – if the lengths of the two vectors are not equal
get(i)

Returns the ith coordinate of this vector.

Parameters:i – the index
Returns:the value of the ith coordinate of this vector
Raises:ValueError – unless i is between 0 and d-1
magnitude()

Returns the magnitude of this vector. This is also known as the L2 norm or the Euclidean norm.

Returns:the magnitude of this vector
nnz()

Returns the number of nonzero entries in this vector.

Returns:the number of nonzero entries in this vector.
plus(that)

Returns the sum of this vector and the specified vector.

Parameters:that – the vector to add to this vector
Returns:the sum of this vector and that vector
Raises:ValueError – if the dimension of the two vectors are not equal
put(i, value)

Sets the ith coordinate of this vector to the specified value.

Parameters:
  • i – the index
  • value – the new value
Raises:

ValueError – unless i is between 0 and d-1
scale(alpha)

Returns the scalar-vector product of this vector with the specified scalar.

Parameters:alpha – the scalar
Returns:the scalar-vector product of this vector with the specified scalar
itu.algs4.searching.sparse_vector.main()

Unit tests the SparseVector data type.

itu.algs4.searching.st module

class itu.algs4.searching.st.ST

Bases: object

ceiling(key)
contains(key)
delete(key)
floor(key)
get(key)
is_empty()
keys()
max()
min()
put(key, val)
size()

Module contents