Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Implementation of common data structures in Ruby

branch: master

Merge pull request #1 from kristianmandrup/master

Some improvements, including a useful FIFO stack and "factory" macros
latest commit 2b0c85343d
B V Satyaram authored November 25, 2012
Octocat-spinner-32 lib stack #last more logical November 05, 2012
Octocat-spinner-32 test stack #last more logical November 05, 2012
Octocat-spinner-32 .gitignore Changing to Bundler as the gem manager March 05, 2011
Octocat-spinner-32 Gemfile Changing to Bundler as the gem manager March 05, 2011
Octocat-spinner-32 LICENSE MultiDimensionalArray February 21, 2011
Octocat-spinner-32 README.md some more useful stack methods November 05, 2012
Octocat-spinner-32 RELEASE_NOTES bumo version November 05, 2012
Octocat-spinner-32 Rakefile bumo version November 05, 2012
Octocat-spinner-32 RubyDataStructures.gemspec Changing to Bundler as the gem manager March 05, 2011
README.md

RubyDatStructures

RubyDataStructures gem is a ruby implementation of common data structures that are not by default supported by the Ruby programming language. The RubyDatStructures supports the following data structures:

  • Multi Dimensional Array
  • Stack (Implemented as an array)
  • Queue (Implemented as an array)
  • Singly Linked List
  • Doubly Linked List
  • Max Heap

Installation

gem install RubyDataStructures

Usage

The RubyDatStructures library can be easily imported by running:

require 'rubygems'
require 'RubyDataStructures'

The usage of each of the data structures is described below.

You can enable macros to more conveniently create these data structures by:

require 'RubyDataStructures/macros'

@stack = stack(3)
@fifo = fifo_stack(5)
@arr = multi_array(1,2,3)
...

Tests

Run tests/specs from console:

rake test

Multi Dimensional Array

A multi dimensional array can be initialized by running:

RubyDataStructures::MultiDimensionalArray.new(n)

where n is the number of dimensions of the multi dimensional array.

The key at a particular index can be easily accessed by calling the array with the dimensions of the index. The key at the index with dimensions (2,4,3) of a multi dimensional array mul_dim_array can be access by calling:

mul_dim_array[2,4,3]

The key for an index can also be easily set by calling the setter with the dimensions of the index. The key at the index with dimensions (2,4,3) of a multi dimensional array mul_dim_array can be set to 36 by calling:

mul_dim_array[2,4,3] = 36

Stack

A Stack can be initialized by running:

RubyDataStructures::StackAsArray.new(n)

where n is the max-size of stack.

The following methods available on a stack are self explanatory:

  • empty?
  • full?
  • singleton?
  • push(element)
  • pop
  • reset

Examples:

my_stack = RubyDataStructures::StackAsArray.new(5)
my_stack.empty?     # Returns `true`
my_stack.full?      # Returns `false`
my_stack.singleton? # Returns `false`
my_stack.push(1)
my_stack.push(2)
my_stach.push(3)
my_stack.pop        # Return `3`

Notes: Why not use the internal #push and #pop methods of Array that already makes an Array simulate a stack? Why create the initial array with the full max length? Perhaps make this a config option?

Queue

A Queue can be initialized by calling:

RubyDataStructures::QueueAsArray.new(n)

where n is the max-size of the queue.

The following methods available on a queue are self explanatory:

  • empty?
  • full?
  • enqueue(element)
  • dequeue
  • reset

Examples:

my_queue = RubyDataStructures::QueueAsArray.new(5)
my_queue.empty?     # Returns `true`
my_queue.full?      # Returns `false`
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)
my_queue.dequeue    # Returns `1`

Singly Linked List

A singly linked list can be initialized by running:

RubyDataStructures::SinglyLinkedList.new

The following methods available on a singly linked list are self explanatory:

  • head
  • empty?
  • insert(item)
  • search(key)
  • delete(key)
  • reset

Examples:

my_list = RubyDataStructures::SinglyLinkedList.new
my_list.head # Returns `nil`
my_list.empty? # Returns `true`
my_list.insert(7)
my_list.search(7) # Returns a `RubyDataStructures::SinglyLinkedList::Element` element, whose key is `7`
my_list.delete(7)

Doubly Linked List

A doubly linked list can be intialized by running:

RubyDataStructures::DoublyLinkedList.new

The following methods available on a doubly linked list are self explanatory:

  • head
  • tail
  • empty?
  • insert(item)
  • search(key)
  • delete(key)
  • reset

Examples:

my_list = RubyDataStructures::DoublyLinkedList.new
my_list.head       # Returns a `RubyDataStructures::DoublyLinkedList::Element` element, whose key is nil
my_list.tail       # Returns a `RubyDataStructures::DoublyLinkedList::Element` element, whose key is nil
my_list.empty?     # Returns `true`
my_list.insert(7)
my_list.search(7)  # Returns a `RubyDataStructures::DoublyLinkedList::Element` element, whose key is `7`
my_list.delete(7)

Max Heap

MaxHeap inherits most of its functionality from Array. A max heap can be initialized by running:

RubyDataStructures::MaxHeap.build(array)

where array is an array, out of which we would like to build a max heap.

For example, a heap can be built out of an array [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] by running:

heap = RubyDataStructures::MaxHeap.build([4, 1, 3, 2, 16, 9, 10, 14, 8, 7])
# Returns the MaxHeap: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

The maximum of the heap can be accessed by running:

heap.maximum # Returns `16`

The maximum of the heap can be extracted by running:

heap.extract_maximum!

The key of a particular element can be increased by running:

heap.increase_key!(index, key)

Example:

heap.increase_key!(8, 15)

A key can be inserted into a heap by running:

heap.insert!(key)

Example:

heap.insert!(11)

Author

B V Satyaram <bvsatyaram.com>

Something went wrong with that request. Please try again.