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)

New graph implemented as Adjency List

graph = Graph.new(edges,:list)

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]