DS - Data Structures for Ruby¶ ↑
<img src=“https://travis-ci.org/knife/ds.svg?branch=master” alt=“Build Status” />
DS provides some popular data structures not implemented in Ruby natively.
Data structures included in this gem:
-
Pair
-
Stacks
-
Stack
-
-
Queues
-
SimpleQueue
-
PriorityQueue
-
-
Lists
-
List
-
-
Trees
-
Tree
-
BinaryTree
-
BinaryHeap
-
RedBlackTree
-
Trie
-
-
Matrixes
-
Array2D
-
ExpandableArray
-
TriMatrix
-
-
Sets
-
IndexedSet
-
Instalation¶ ↑
gem install ds
Usage¶ ↑
require 'ds' stack = DS::Stack.new
To not have to type “DS::” before each class, use:
include DS stack = Stack.new
Pair¶ ↑
Pair is simple key-value data structure.
Creating new Pair
p = Pair.new(3, 9)
Accessors defined on Pair object:
p.key #=> 3 p.value #=> 9 p.value = 27 p.first #=> 3 p.second #=> 9 p.second = 27
Stack¶ ↑
Stack is very simple data structure which allows access only to the top element. More: Stack
Creating new Stack (implemented as Array).
stack = Stack.new
with initial values:
s = Stack.new(:first, :second)
Creating new Stack (implemented as List).
stack = Stack.create
The following methods are available on a Stack:
-
push
-
pop
-
peek
-
size
-
empty?
Examples:
stack.empty? #=> true stack.push :first stack.push :second stack.size #=> 2 stack.peek #=> :second stack.empty? #=> false stack.pop #=> :second stack.size #=> 1
Queues¶ ↑
Queue is First-In-First-Out (FIFO) data structure. Which means that first element added to the queue will be the first one to be removed. More: Queue
SimpleQueue¶ ↑
Creating new SimpleQueue (implemented as Array).
q = SimpleQueue.new
with initial values:
q = SimpleQueue.new(1, 2, 3)
Creating new SimpleQueue (implemented as List)
q1 = SimpleQueue.create
The following methods are available on a Queue:
-
enqueue or push
-
dequeue or shift
-
peek
-
length or size
-
empty?
Examples:
q.enqueue :first q.push :second q.peek #=> :first q.length #=> 2 q.empty? #=> false q.dequeue #=> :first q.shift #=> :second q.empty? #=> true
Priority Queue¶ ↑
In opposite to simple Queue, in PriorityQueue each element is associated with a “priority”. More: Priority Queue
Creating new Priority Queue (implemented as BinaryHeap)
q = PriorityQueue.new
By default higher value means higher priority but you can define own priority order by passing block to constructor:
PriorityQueue.new { |a, b| a < b }
To add new element to priority queue use #unshift or #push method:
q.push(value, priority)
To remove element from priority queue use #shift or #pop method. The interface is very similar to SimpleQueue.
Examples:
q.push(:important, 3) q.push(:very_important, 5) q.push(:nevermind, 1) q.shift #=> :very_important q.peek #=> :important q.length #=> 2 q.shift #=> :important q.peek #=> :nevermind
Indexed Priority Queue¶ ↑
Indexed Priority Queue is special form of PriorityQueue with constant access to any element. Additionaly you can easily change priority of any element stored on queue.
Creating new Indexed Priority Queue
q = IndexedPriorityQueue.new
or
IndexedPriorityQueue.new { |a, b| a.key < b.key }
IndexedPriorityQueue inherits from PriorityQueue so all methods from PriorityQueue are available.
Examples:
q.push(:important, 3) q.push(:very_important, 5) q.push(:nevermind, 1) q.peek #=> :very_important q.change(:nevermind, 10) q.peek #=> :nevermind
Elements stored on priority queue are wrapped in Pair object, when you call get method this object is returned:
q.get(:very_important) #=> Pair.new(5, :very_important) q.include?(:very_important) #=> true
Lists¶ ↑
List¶ ↑
List is an ordered collection of values. Each element of list has pointer to the next element (last element points to nil). This implementation uses doubly linked list underhood. More: List
Creating new List
l = List.new l.append(2)
or
list = List.new(1, 2, 3, 4)
Examples:
Simple operations on lists
list.length #=> 4 list.append(5).to_a #=> [1, 2, 3, 4, 5] list.unshift(0).to_a #=> [0, 1, 2, 3, 4, 5] list.remove(list.head).to_a #=> [1, 2, 3, 4, 5] list.shift #=> 1
Accessing first and last element
list.head.data #=> 2 list.tail.data #=> 5 list.first #=> 2 list.last #=> 5
Accessing by index
list[2].data #=> 2 list.at(2).data #=> 2 list[-1].data #=> 4 list[1..2].map(&:data) #=> [2, 3] list[1,3].map(&:data) #=> [2, 3, 4]
Modifying elements on given index:
list[2].data = 8 list[2].data #=> 8 list[2] = [9, 10] #=> [1, 2, 9, 10, 4] list[0,1] = 0 #=> [0, 2, 3, 4] list[2..3] = ['x', 'x'] #=> [1, 2, 'x', 'x']
Checking if given element exists on list
list.get(el) #=> el or nil list.get!(el) #=> raises Exception if not found
Reversing
list.reverse!.to_a #=> [5, 4, 3, 1, 0]
Enumerable methods are also available
list.map{ |e| e.data } #=> [1, 2, 3, 4] list.inject(0){ |a, e| a + e.data } #=> 10
Append one list to other list
list1.concat(list2)
Comparable module is included so you can:
Check if lists are equal
list1 == list2
Check if one list is greater than other (same rules as in Array class)
list1 > list2
Other operations
-
clone
-
clear
-
insert_before
-
insert_after
-
zip?
-
looped?
-
cycle_size
-
to_s
Trees¶ ↑
Tree¶ ↑
A tree is a data structure with nodes organised in hierarchy. More: Tree
Building Tree
t = Tree.new(2) c1 = t << 5 c2 = t << 8 t << 9 c1 << 4 c1 << 10 c3 = c2 << 3
Methods:
t.leaf? #=> false c3.leaf? #=> true c1.sibblings.map &:data #=> [8, 9] c1.parent.data #=> 2 t.height #=> 3 t.width #=> 3 t.leaf_count #=> 4 t.levels #=> {1=>1, 2=>3, 3=>3}
Other methods
-
get_leaves
-
isometric?
-
mirror!
Enumerable Module is also included.
t.map { |node| node.data } #=> [2, 5, 8, 9, 4, 10, 3]
Binary Tree¶ ↑
BinaryTree is sublass of Tree. In BinaryTree each node can have at most two children. More: BinaryTree
Building tree
bin_tree = BinaryTree.new [2, 5, 8, 9, 11, 12, 14].each { |x| bin_tree.insert(x) } #builds complete binary Tree
Accessors defined on BinaryTree object:
bin_tree.left.data #=> 5 bin_tree.right.data #=> 8
Red Black Tree¶ ↑
Red-black tree is symbol table data structure. It’s very simmilar to hash, but internally uses tree (perfect balanced binary tree) and not depends on hash function. Red black trees aren’t as fast as hashes but supports ordered operations.
rb = RedBlackTree.new rb.insert(:z, 3) rb.insert(:p, 2) rb.insert(:a, 1) rb.get(:a) #=> 1
You can also create RBT by passing hash to constructor
rb = RedBlackTree.new(a: 1, p: 2, z: 3)
Hash like accessors are defined
rb[:z] = 3 rb[:z] #=> 3
You can convert RedBlackTree to Hash with to_h method:
rb.to_h #=> {a: 1, p: 2, z: 3}
Enumerable is included and traversing is ordered by key
rb.map(&:key) #=> [:a, :p, :z]
Binary Heap¶ ↑
BinaryHeap is tree in which every node satisfies heap property. Binary Heap allows very fast access to maximum or minimum element of the tree (const access). More: Binary Heap
Creating
Maximum Binary Heap
max_heap = BinaryHeap.new(9, 8, 4, 5, 11, 6)
or
max_heap = BinaryHeap.max(9, 8, 4, 5, 11, 6)
Minimum Binary Heap
min_heap = BinaryHeap.min(9, 8, 4, 5, 11, 6)
or
BinaryHeap.new(9, 8, 4, 5, 11, 6){ |parent, child| parent < child }
You can set heap relation by passing block to BinaryHeap constructor.
Examples
max_heap.shift #returns max element (11) max_heap.to_a #=> [9, 8, 6, 5, 4] max_heap.insert 15 max_heap.shift #=> 15 min_heap.shift #returns min element (4)
Trie¶ ↑
Trie is an ordered tree data structure which allows very quick search: O(k), where k is word length. More: Trie
Creating
trie = Trie.new
Setting custom alphabet (memory usage depends on alphabet size)
trie.alphabet = %w(a b c d)
Examples
trie.insert('thing', true); trie.find('thing') # => true trie.delete('thing')
or
trie['one'] = 'thing' trie['one'] # => 'thing'
Enumerable module is included so you can iterate through trie:
trie.map { |k, v| [k, v] } # => [['he', true], ['hello', true], ['help', true]]
Finding all words matching given prefix:
trie.with_prefix('th') # => ['the', 'thing'] trie.with_prefix('yeti') # => []
Alternatively you can pass block to this method:
trie.with_prefix('th'){ |word, val| res[word] = val } # => {'the' => true, 'thing' => true}
Tree Traversals¶ ↑
b = BinaryTree.new [2, 5, 8, 9, 11, 12, 14].each{ |x| b.insert(x) } walker = TreeWalker.new(b)
Iterating in postorder
walker.traverse(:postorder) #=> [9, 11, 5, 12, 14, 8, 2]
Iterating in inorder
walker.traverse(:inorder) #=> [9, 5, 11, 2, 12, 8, 14]
Iterating in preorder
walker.traverse(:preorder) #=> [2, 5, 9, 11, 8, 12, 14]
Iterating in BFS order
walker.each{ |x| x } #=> [2, 5, 8, 9, 11, 12, 14]
You can also pass block to traverse method
walker.traverse(:inorder){ |n| n.data**2 }
If you want to change value of tree nodes, use recalculate! method
walker.recalculate!(b, :preorder, 0) { |e, a| a + e.data }
Arrays¶ ↑
Array2D¶ ↑
Simple two dimensional array(matrix). Array2D extends automatically like simple Array.
Creating
discrete_matrix = Array2D.new(2, 0)
First argument is size of row(or column) and second is default value of matrix.
Examples
discrete_matrix.to_a #=> [[0, 0], [0, 0]] discrete_matrix[3, 3] #=> 0
ExpandableArray¶ ↑
Automaticaly fills empty slots with custom value:
arr = ExpandableArray.new(0, 0) arr[4] = 1 #=> [0, 0, 0, 0, 4]
TriMatrix¶ ↑
Triangular matrix is a special kind of matrix where M = M. More: Triangular Matrix
Creating
tri_matrix = TriMatrix.new tri_matrix[0, 1] = true tri_matrix[0, 2] = true
Examples
tri_matrix[0, 1] == tri_matrix[1, 0] #=> true
Sets¶ ↑
IndexedSet¶ ↑
IndexedSet is a set whose elements are indexed. In opposite to Array, duplicates are not allowed. Internally uses hash for fast access and array for ordering.
Creating new Indexed Set
set = IndexedSet.new
Examples
set.push(:first) #=> 0 set.push(:second) #=> 1 set.index(:first) #=> 0 set.to_a #=> [:first, :second]