DS - Data Structures
DS provides some common data structures not implement in Ruby natively.
The DS gem supports the folowing data structures:
-
Pair
-
Stacks
-
Stack
-
-
Queues
-
Queue
-
PriorityQueue
-
-
Lists
-
List
-
CyclicList
-
Ring
-
-
Trees
-
Tree
-
BinaryTree
-
CompleteBinaryTree
-
BinaryHeap
-
BinarySearchTree
-
Trie
-
-
Graphs
-
Graph
-
Digraph
-
-
Matrixes
-
Array2D
-
ExpandableArray
-
TriMatrix
-
-
Sets
-
OrderedSet
-
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.first #=> 3
p.value #=> 9
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
The following methods are available on a Stack:
-
push
-
pop
-
size
-
empty?
-
size
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
Queues 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
Queue
Creating new Queue (implemented as Array).
q = Queue.new
Creating new Queue (implemented as List)
q1 = Queue.create
q1 = Queue.new(:list)
The following methods are available on a Queue:
-
enqueue(push)
-
dequeue(shift)
-
peek
-
length
-
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
PriorityQueue is special form of Queue (PriorityQueue inherits from 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
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
Lists
List
List is an ordered collection of values. Each element of list has pointer to the next element (last element points to nil). More: List
Creating new List
l = List.new(1)
l.append(2)
or
arr = [1,2,3,4]
list = List.from_array(arr)
Examples:
Simple operation on lists
list.length #=> 4
list.append(5).to_a #=> [1,2,3,4,5]
list.prepend(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
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){ |mem, var| mem = mem + var.data } #=> 10
Other operations
-
insert_before
-
insert_after
-
zip?
-
merge
Ring
Ring is a Cyclic List where the last element(head) points to the first element(tail). More: Ring
Creating new Ring
ring = Ring.from_array([1,2,3,4,5,6,7])
Examples:
ring.looped? #=> true
ring.cycle_size #=> 7
ring.eliminate_by(2) #=> 1
Trees
Tree
A tree is a data structure consisting of nodes organised as a hierarchy. More: Tree
Building Tree
t = Tree.new(2)
c1 = t << 5
c2 = t << 8
t << 9
c1 << 4
c1 << 10
c3 = c2 << 3
Examples:
t.leaf? #=> false
c3.leaf? #=> true
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 included.
t.map{ |node| node.data } #=> [2,5,8,9,4,10,3]
Binary Tree
BinaryTree is sublass of Tree class. 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)} #build complete binary Tree
Accessors defined on BinaryTree object:
bin_tree.left #=> 5
bin_tree.right #=> 8
BinarySearchTree
BST is Binary Tree which has the following properties:
-
The left subtree of a node contains only nodes with keys less than the node’s key.
-
The right subtree of a node contains only nodes with keys greater than the node’s key.
-
Both the left and right subtrees must also be binary search trees.
Creating
bst = BinarySearchTree.from_array([8,1,5,2,7,6,3])
Examples
walker = TreeWalker.new(b)
walker.traverse(:inorder).must_equal [1,2,3,5,6,7,8]
CompleteBinaryTree
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. CompleteBinaryTree is binary tree but does not inherit from Tree and BinaryTree class! Nodes are stored internally in array. More: Complete Binary Tree
Creating
cbt = CompleteBinaryTree.new(1,2,3,4,5,6,7)
Examples
cbt.root #=> 1
cbt.left(0) #=> 2
cbt.right(0) #=> 3
cbt.parent(1) #=> 0
cbt.left_index(0) #=> 1
cbt.right_index(1) #=> 4
cpt.parent_index(1) #=> 0
Binary Heap
BinaryHeap is Complete Binary Tree in which every node satisfies heap property. Binary Heap allows very fast access to maximum or minimum element of the tree. 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
Examples
trie.insert("thing",true);
trie.find("thing") # => true
Traversing Tree
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| p n.data**2}
If you want to change value of tree nodes, use recalculate! method
walker.recalculate!(b,:preorder,0){|x,memo| memo = memo+x.data}
Graphs
A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. More: Graph
Graph
Creating new Graph
edges = []
edges << Edge.new('Lukas','Marc')
edges << Edge.new('Lukas','Tom')
edges << Edge.new('Marc','Jack')
edges << Edge.new('Tom','Marc')
New graph implemented as Triangular Matrix
graph = Graph.create(edges)
New graph implemented as Matrix
graph = Graph.new(edges,:matrix)
Examples:
graph.vertex_size #=> 4
graph.degree("Marc") #=> 3
graph.edge?("Marc","Tom") #=> true
graph.edge?("Tom","Jack") #=> false
graph.add_edges([Edge.new("Marc","Kate")])
graph.remove("Marc","Jack")
graph.neighbors('Tom') #=> ["Marc","Lucas"]
Iterating
graph.each_edge{|e| p e}
graph.each_vertex{ |v| p v }
Digraph
Creating Directed Weighted Graph is simple like that:
edges = []
edges << Edge.new(:A,:C,5)
edges << Edge.new(:A,:D,3)
edges << Edge.new(:A,:G,14)
edges << Edge.new(:C,:E,3)
edges << Edge.new(:C,:F,2)
edges << Edge.new(:D,:C,11)
edges << Edge.new(:D,:E,7)
edges << Edge.new(:D,:G,6)
edges << Edge.new(:G,:E,7)
edges << Edge.new(:E,:B,5)
edges << Edge.new(:G,:B,6)
edges << Edge.new(:F,:B,7)
wdigraph = Digraph.create(edges)
Examples
wdigraph.get_edge(:D,:C).weight #=> 11
wdigraph.degree(:E) #=> 4
wdigraph.in_degree(:E) #=> 3
wdigraph.out_degree(:E) #=> 1
wdigraph.bfs(:A) #=> [:A, :C, :D, :G, :E, :F, :B]
Matrixes
Array2D
Simple two dimensional array(matrix).
Array2D extends automatically like simple Array.
Creating
discrete_matrix = Array2D.new(2,0)
Examples
discrete_matrix.to_a #=> [[0,0],[0,0]]
discrete_matrix[3,3] #=> 0
ExpandableArray
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 Matrixe
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
OrderedSet
OrderedSet is a set whose elements are ordered. In opposite to Array duplicates are not allowed.
Creating new Ordered Set
set = OrderedSet.new
Examples
set.push(:first) #=> 0
set.push(:second) #=> 1
set.index(:first) #=> 0
set.to_a #=> [:first, :second]