kanwei/algorithms

To avoid prefixing every class with Containers::, you can include the Containers module in your scope.

include Containers
max_heap = MaxHeap.new

To use the algorithms library, require rubygems and algorithms. The library provides various data structures under the Containers namespace and algorithms under the Algorithms namespace. For better performance, it is highly recommended to install the C extensions.

require 'rubygems'
require 'algorithms'

# Usage example
max_heap = Containers::MaxHeap.new

A Containers::Trie is a Ternary Search Tree implementation that stores key-value pairs. It provides $O(m)$ lookup speed (where $m$ is the length of the key) and avoids collisions. It is suitable for longest prefix matching and wildcard searches.

t = Containers::Trie.new
t["hello"] = "world"
puts t["hello"] #=> "world"

A SplayTreeMap is a map that stores items in ascending order of their keys (using the <=> operator). It is self-optimizing: recently accessed nodes are moved near the root for faster subsequent access.

Key characteristics:

• Ordering: Keys are stored in order, allowing for ordered iteration.
• Complexity: Most methods have amortized $O(\log n)$ performance, though worst-case is $O(n)$ if keys are added in sorted order.
• Duplicates: Duplicate keys are not allowed; inserting a new value for an existing key overwrites the old value.

A Containers::RBTreeMap is a map that stores items in sorted order based on their keys (using the <=> operator). Unlike a standard Hash, keys can be iterated over in order. Duplicate keys are not allowed; inserting a duplicate key will overwrite the existing value.

Containers::RBTreeMap automatically selects the faster C implementation (Containers::CRBTreeMap) if available, otherwise it falls back to the Ruby implementation (Containers::RubyRBTreeMap).

By default, all container classes are namespaced under the Containers module. To avoid prefixing every initialization with Containers::, you can include Containers in your scope.

require 'algorithms'
include Containers

tree = RBTreeMap.new

Use has_substring?(substring) to determine if a specific substring exists within the original string. This method uses binary search for efficiency.

Complexity: O(m + log n) where m is the length of the substring and n is the total number of suffixes.

Returns: true if the substring is found, false otherwise.

s_array = Containers::SuffixArray.new("abracadabra")
s_array.has_substring?("abra") #=> true
s_array.has_substring?("nope") #=> false

Use push_front(obj) to add an object to the beginning of the Deque, or push_back(obj) to add an object to the end. Both methods return the object being added.

d = Containers::Deque.new([1, 2, 3])
d.push_front(0)
d.push_back(4)

Use Algorithms::Search.kmp_search(string, substring) to efficiently find the starting position of a substring within a string.

• Returns: The integer index of the starting position where the substring is found. Returns nil if no match is found.
• Complexity: O(n + k), where n is the length of the string and k is the length of the substring.
• Instance Method: You can include Algorithms::Search in a class (like String) to call kmp_search as an instance method.

# As a module method
Algorithms::Search.kmp_search("ABC ABCDAB ABCDABCDABDE", "ABCDABD") #=> 15
Algorithms::Search.kmp_search("ABC ABCDAB ABCDABCDABDE", "ABCDEF") #=> nil

# As an instance method via inclusion
class String; include Algorithms::Search; end
"ABC ABCDAB ABCDABCDABDE".kmp_search("ABCDABD") #=> 15

Use delete(key) to remove the item associated with the key. It returns the value of the deleted item, or nil if the key was not found. This operation has amortized $O(\log n)$ complexity.

map = Containers::SplayTreeMap.new
map["MA"] = "Massachusetts"
map.delete("MA") #=> "Massachusetts"
map.delete("MA") #=> nil