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

gem install ds

require 'ds'
stack = DS::Stack.new

# To not have to type "DS::" before each class, use:
include DS
stack = Stack.new

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 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 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

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

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

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 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

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]

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

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]

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

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 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

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}

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

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 }

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]

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

arr = ExpandableArray.new(0,0)
arr[4]  = 1 #=> [0,0,0,0,4]

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

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]