Ruby Structures
Ruby implementations of common data structures.
Installation & Usage
Install Ruby Structures:
gem install ruby_structures
Or add it to your Gemfile:
gem 'ruby_structures'
Require Ruby Structures in your file:
require 'ruby_structures'
Available Data Structures
- Stack
- Queue
- Linked List
- Binary Tree
- LRU Cache
- Heap
- Priority Queue
- Graph
- Weighted Graph
More to come...
Stack
A Stack is a LIFO (last in, first out) container.
Stack API
#to_a#==#empty?#push(el)#<<(el)#pop#peek#length#include?(el)
Queue
A Queue is a FIFO (first in, first out) container.
Queue API
#to_a#==#empty?#enqueue(el)#<<(el)#dequeue#peek#length#include?(el)
Linked List
A Linked List is an ordered collection of items, or nodes, where the ordering is determined by links between the nodes. The Ruby Structures implementation of a Linked List is doubly linked, meaning that each node has a link to the node after it as well as the node preceding it.
Linked List API
#to_a#empty?#length#first#last#append(key, val)#prepend(key, val)#add_after_key(ref_key, key, val)#add_before_key(ref_key, key, val)#find_by_key(key)#find_by_val(val)#include_key?(key)#include_val?(val)#remove(key)#update(key, new_val)#each(&prc)
Binary Tree
A Binary Tree is a tree in which each Node may have a maximum of two children.
Binary Tree API
::from_array(array)#depth_first_search#breadth_first_search
LRU Cache
An LRU Cache is an ordered container that combines a Hash and a Linked List to provide insertion, deletion and inclusion methods in constant time.
LRU Cache API
#to_a#empty?#length#first#last#append(key, val)#prepend(key, val)#add_after_key(ref_key, key, val)#add_before_key(ref_key, key, val)#remove(key)#find(key)#include?(key)
Heap
A Heap is a tree-based data structure that adheres to the Heap principle. Ruby Structures implements a Min Heap, which means that each parent element in the heap is of lesser value than each of its child elements. A Min Heap always has access to its minimum element.
Heap API
::from_array(array)#to_a#empty?#length#peek#insert(el)#insert_multiple(array)#extract#find(el)#include?(el)#merge(other_heap)
Priority Queue
A Priority Queue is a specialized queue where each element has a 'priority' attribute. A Priority Queue always has access to its highest priority element.
Priority Queue API
::from_array(array)::from_hash(hash)#to_a#empty?#length#peek#insert(data, priority)#extract#find(data)#include?(data)#merge(other_queue)
Graph
A Graph is a set of vertices and a set vertex pairs, or edges, that connect vertices to one another. Ruby Structures implements both an Undirected Graph (unordered edge pairs) and a Directed Graph (ordered edge pairs).
Graph & Directed Graph API
#add_vertex(id)#delete_vertex(id)#create_edge(id1, id2)#delete_edge(id1, id2)#adjacent?(id1, id2)#adjacent_vertices(id)#depth_first_search(target_id, start_id, &prc)#breadth_first_search(target_id, start_id, &prc)
Weighted Graph
A Weighted Graph is a Graph in which each edge is assigned a weight. Ruby Structures implements both the undirected and directed varieties of a Weighted Graph.
Weighted Graph & Weighted Directed Graph API
#add_vertex(id)#delete_vertex(id)#create_edge(id1, id2, weight)#delete_edge(id1, id2, weight)#adjacent?(id1, id2)#adjacent_vertices(id)#highest_weight_adjacent(id)#lowest_weight_adjacent(id)