DS - Data Structures for Ruby

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

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)

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)

max_heap = BinaryHeap.max(9, 8, 4, 5, 11, 6)

Minimum Binary Heap

min_heap = BinaryHeap.min(9, 8, 4, 5, 11, 6)

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

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]