Giter Club home page Giter Club logo

data-struct's Introduction

data-struct

A simple gem that provides several useful data structures in Ruby.

Gem Version Build Status Dependency Status

##Usage

Install the gem:

  gem install data-struct

Or require in Gemfile:

  gem 'data-struct'

then run

  bundle install

To use the gem, initialize a new object through the DataStruct module (optional).

  require "data-struct"

  linked_list = DataStruct::SinglyLinkedList.new
  # default LinkedList class is doubly linked; use SinglyLinkedList for singly linked list
  dynamic_array = DynamicArray.new(10)
  # same thing, DataStruct module not necessary

Class names correspond with list below:

Abstract Data Type

  • Map
  • Set
  • MaxStack
  • MinMaxStack
  • Priority Queue

Data Structures

  • DynamicArray
  • HashMap
  • SinglyLinkedList
  • LinkedList
  • LRUCache
  • BinarySearchTree
  • BinHeap

Contents

1. Abstract Data Types

1.1 Max Stack

#initialize

Initialize your max stack.

  max_stack = DataStruct::MaxStack.new
  => #<MaxStack:0x007f86c8a04c80 @store=[]>

#push(val)

Pushes the value onto the end of the stack

  max_stack.store
  => []
  max_stack.push(5)
  => [[5, 5]]
  max_stack.store
  => [[5, 5]]

#pop

Pops the last element in the stack

  max_stack.store
  => [[5, 5]]
  max_stack.pop
  => 5
  max_stack.store
  => []

#max

Returns in the max value in O(1) time.

  max_stack.store
  => [[5, 5], [2, 5], [6, 6], [7, 7]]
  max_stack.max
  => 7

1.2 Min Max Stack

#initialize

Initialize your min max stack.

mms = DataStruct::MinMaxStack.new
=> #<DataStruct::MinMaxStack:0x007fd2a2f6d3b8 @store=[]>

#push(val)

Pushes values into the stack.

mms.push(2)
=> [[2, 2, 2]]
mms.push(5)
=> [[2, 2, 2], [5, 2, 5]]
mms.push(-1)
=> [[2, 2, 2], [5, 2, 5], [-1, -1, 5]]

#length

Returns the current length of the stack.

mms.length
=> 3

#max

Returns the max value of the stack in O(1) time.

mms.max
=> 5

#min

Similarly to max, returns min value of stack in O(1) time.

mms.min
=> -1

#pop

Pops from the stack and returns the value.

mms.pop
=> -1
mms.pop
=> 5
mms.pop
=> 2
mms.length
=> 0

2. Data Structures

2.1 Dynamic Array

#initialize

Initialize with the size of your dynamic array

  d_array = DataStruct::DynamicArray.new(4)
  => #<DynamicArray:0x007ffe5c089460 @num_items=0, @size=4, @start=0, @store=[nil, nil, nil, nil]>

#pop

Pops the last element in the array

  d_array.store
  => [1, 2, 3, 4, nil, nil, nil, nil, nil, nil]
  d_array.pop
  => 4
  d_array.store
  [1, 2, 3, nil, nil, nil, nil, nil, nil, nil]

#push(val)

Pushes the value onto the end of the array

  d_array.store
  => [1, 2, 3, 4, nil, nil, nil, nil, nil, nil]
  d_array.push(10)
  => [1, 2, 3, 4, 10, nil, nil, nil, nil, nil]

Resizes when pushed onto full array

  d_array.store
  => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  d_array.push(11)
  => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, nil, nil, nil, nil, nil, nil, nil, nil, nil]

#shift

Shifts and returns the value at the front of the array; doesn't copy the array

  d_array.store
  => [1, 2, 3, 4, 10, nil, nil, nil, nil, nil]
  d_array.shift
  => 1
  d_array.store
  => [nil, 2, 3, 4, 10, nil, nil, nil, nil, nil]

#unshift(val)

Unshifts the value into the front of the array

  d_array.store
  => [nil, 2, 3, 4, 5, 6, 7, 8, nil, nil]
  d_array.unshift(100)
  => [100, 2, 3, 4, 5, 6, 7, 8, nil, nil]

Uses ring buffer to wrap around

  d_array.store
  => [100, 2, 3, 4, 5, 6, 7, 8, nil, nil]
  d_array.unshift(101)
  => [100, 2, 3, 4, 5, 6, 7, 8, nil, 101]

#insert(val, idx)

Inserts the value at idx and pushes everything over

  d_array.store
  => [1, 2, 3, 4, nil, nil, nil, nil, nil, nil]
  d_array.insert(10, 0)
  => [10, 1, 2, 3, 4, nil, nil, nil, nil, nil]
  d_array.insert(100, 2)
  => [10, 1 100, 2, 3, 4, nil, nil, nil, nil]

Ring buffer still in effect

  d_array.store
  => [100, 2, 3, 4, 5, 6, 7, 8, nil, 101]
  d_array.insert(200, 0)
  => [101, 100, 2, 3, 4, 5, 6, 7, 8, 200]

2.2 Singly Linked List

#initialize

Initialize an empty Linked List object with a sentinel Link

  linked_list = DataStruct::SinglyLinkedList.new
  => #<SinglyLinkedList:0x007fabbb1af5b8 @sentinel=#<SinglyLink:0x007fabbb1af590 @next=nil, @val=nil>>

#pop

Pops from the end and returns the value

  linked_list.push(1)
  linked_list.push(2)
  linked_list.push(3)
  linked_list.pop
  => 3
  linked_list.pop
  => 2

#push

Pushes onto the end of the list (inner most nested pointer)

  linked_list.push(1)
  linked_list.push(2)
  linked_list.push(3)
  => #<SinglyLinkedList:0x007fd349bc2220
      @sentinel=
      #<SinglyLink:0x007fd349bc21f8 @next=
        #<SinglyLink:0x007fd349087b30 @next=
          #<SinglyLink:0x007fd3490b2ce0 @next=
            #<SinglyLink:0x007fd3490cbdf8 @next=nil,
            @val=3>,
          @val=2>,
        @val=1>,
      @val=nil>>

#shift

Shifts from the front and returns the value

  linked_list.push(1)
  linked_list.push(2)
  linked_list.push(3)
  linked_list.shift
  => 1
  linked_list.shift
  => 2

#unshift

unshifts to the front of the list and is attached to the sentinel (outer most pointer)

  linked_list.unshift(10)
  linked_list.unshift(20)
  linked_list.unshift(30)
  => #<SinglyLinkedList:0x007fd34a551b38
      @sentinel=
      #<SinglyLink:0x007fd34a551b10 @next=
        #<SinglyLink:0x007fd349bdab18 @next=
          #<SinglyLink:0x007fd34910da28 @next=
            #<SinglyLink:0x007fd348a0e880 @next=nil,
            @val=10>,
          @val=20>,
        @val=30>,
      @val=nil>>

2.3 Binary Search Tree (self balancing)

#initialize

initialize with your root node

  tree = BinarySearchTree.new(10)
  =>  { 10 : {} | {} }

#children

// deprecated //

::from_array

class method to initialize tree from an array

  tree = BinarySearchTree.from_array([1, 5, 2, 6, 8, 10, 3])
  =>  { 6 :  
        { 2 :  
          { 1 : {} | {} }  |  { 5 :  
                        { 3 : {} | {} }  | {}
                                }  
        }  |  
        { 8 : {} |  
          { 10 : {} | {} }  
        }  
      }

#insert(val)

inserts the value in the correct position, then rebalances

  tree = BinarySearchTree.new(10)
  tree.insert(15)
  =>  { 10 : {} |  { 15 : {} | {} }  }
  tree.insert(13)
  =>  { 13 :  { 10 : {} | {} }  |  { 15 : {} | {} }  }

#include?(val)

checks tree for presence of value

  tree = BinarySearchTree.new(10)
  tree.insert(15)
  tree.include?(15)
  => true
  tree.include?(14)
  => false

#to_a

returns the tree in sorted array form

  tree = BinarySearchTree.from_array([10, 5, 7, 15, 12, 0])
  =>  { 7 :  { 5 :  { 0 : {} | {} }  | {} }  |  { 12 :  { 10 : {} | {} }  |  { 15 : {} | {} }  }  }
  tree.to_a
  => [0, 5, 7, 10, 12, 15]

benchmark testing

  test_array = []
  5000.times { test_array << (rand 5000) }

  tree = BinarySearchTree.new(test_array.first)
  test_array.each { |v| tree.insert(v) }
  test_hash = Hash[test_array.map { |x| [x, true] }]

  Benchmark.bm do |benchmark|
    benchmark.report("test_array include" ) { (1..5000).each { |n| test_array.include? n } }
    benchmark.report("binary tree serach")  { (1..5000).each { |n| tree.include? n } }
    benchmark.report("test_hash lookup ")   { (1..5000).each { |n| test_hash.has_key? n }}
  end

                        user     system      total        real
  test_array include  0.880000   0.010000   0.890000 (  0.895702)
  binary tree search  0.010000   0.000000   0.010000 (  0.012694)
  test_hash lookup    0.000000   0.000000   0.000000 (  0.001391)

  80x faster than Ruby array, 10x slower than Ruby hash

2.4 Binary Heap

#initialize(&prc)

Initialize the binary heap:

  heap = DataStruct::BinHeap.new
  => #<BinHeap:0x007f8e38bc3928 @prc=#<Proc:0x007f8e38bc38b0@lib/bin_heap.rb:6>, @store=[]>

Default comparison Proc (MinHeap):

  @prc = Proc.new { |el1, el2| el1 <=> el2 }

#insert(element)

Insert a element into the heap, which will be placed in the correct position via ::heapify_up

  bin_heap.insert(4)
  bin_heap.insert(3)
  bin_heap.insert(6)
  bin_heap.insert(0)
  bin_heap.insert(5)
  bin_heap.insert(2)

  bin_heap.store
  => [0, 3, 2, 4, 5, 6]

#extract

Removes the element with the highest priority and re-organizes the binary heap accordingly via ::heapify_down

  bin_heap.extract
  => 0

  bin_heap.store
  => [2, 3, 6, 4, 5]

::heapify_up(store, child_idx, &prc)

  1. Starts with the last element, store[child_idx], and compares it to its parent to see if priority holds.
  2. If it does, the binary heap is ordered properly.
  3. If it does not, swap the child and parent elements, and call ::heapify_up recursively until the binary heap is ordered.

::heapify_down(store, parent_idx, &prc)

  1. Starts with the first element and compares it to its children to see if priority holds
  2. If it does, the binary heap is ordered properly
  3. If it does not, swap with the child of higher priority if applicable and call ::heapify_down recursively until the heap is ordered.

::find_children(last_idx, parent_idx)

Due to the nature of a binary heap being a full tree, we can find children indices using a parent_idx by using some arithmetic:

  left_child_idx = (parent_idx * 2) + 1
  right_child_idx = (parent_idx * 2) + 2

::find_parent(child_idx)

Similary to ::find_children, we can find a child's parent by solving for parent_idx.

  parent_idx = (child_idx - 1) / 2

##Contact

##Contributing

  • Fork it ( https://github.com/kswang2400/data-structures.git )
  • Create your feature branch (git checkout -b my-new-feature)
  • Commit your changes (git commit -am 'Add some feature')
  • Push to the branch (git push origin my-new-feature)
  • Create new Pull Request

##License

This code is free to use under the terms of the MIT license. © 2015

data-struct's People

Contributors

conanza avatar danielng09 avatar gnoha avatar karenling avatar kswang2400 avatar

Stargazers

avatar avatar avatar avatar

Watchers

avatar avatar avatar avatar

Forkers

conanza

data-struct's Issues

MinMaxQueue, MinMaxStack

I think it'd be cool if we wrote MMQ with MMS objects.

class MinMaxQueue
  def initialize
    @in, @out = [], []
  end

  ...

So instead of @in and @out being arrays, instantiate new MMStacks. Therefore, you won't have to rewrite the min/max/push/pop logic.

I think as is, MMQ#pop has an issue here as well.

  def shift
    flip! if @out.empty?

    @out.pop
  end

I need to write a MMS#length

singly linked list poor design?

can someone run singly linked list and tell me if i'm doing it right

[3] pry(main)> a = SingleLinkedList.new
=> #<SingleLinkedList:0x007fabbb1af5b8 
@sentinel=#<SingleLink:0x007fabbb1af590 @next=nil, @val=nil>>
[4] pry(main)> a
=> #<SingleLinkedList:0x007fabbb1af5b8 
@sentinel=#<SingleLink:0x007fabbb1af590 @next=nil, @val=nil>>
[6] pry(main)> a.push(1)
=> #<SingleLinkedList:0x007fabbb1af5b8
 @sentinel=#<SingleLink:0x007fabbb1af590 
@next=#<SingleLink:0x007fabbb179e68 @next=nil, @val=1>, @val=nil>>
[7] pry(main)> a.push(2)
=> #<SingleLinkedList:0x007fabbb1af5b8
 @sentinel=
  #<SingleLink:0x007fabbb1af590
   @next=#<SingleLink:0x007fabbb179e68 
@next=#<SingleLink:0x007fabba558e18 @next=nil, @val=2>, @val=1>,
   @val=nil>>
[8] pry(main)> a.push(3)
=> #<SingleLinkedList:0x007fabbb1af5b8
 @sentinel=
  #<SingleLink:0x007fabbb1af590
   @next=
    #<SingleLink:0x007fabbb179e68
     @next=#<SingleLink:0x007fabba558e18 @next=#<SingleLink:0x007fabba571c60 @next=nil, @val=3>, @val=2>,
     @val=1>,
   @val=nil>>
[10] pry(main)> a.pop
=> 3
[11] pry(main)> a.pop
=> 2
[13] pry(main)> a.pop
=> 1
[14] pry(main)> a.pop
RuntimeError: empty list

when i push, because the next link "lives" in the previous link, it's sort of cascading. ruby may or may not be pass by reference, which means if im pushing in 100 items instead of the linked list item pointing at the first and ignoring the rest, its carrying all 100 links. someone look into this pleaseeee

DLL POP 

  def pop
    last_link = @last_sentinel.last
    val = last_link.val
    @last_sentinel.prev = last_link.prev

    val
  end

There's no Link#last is there? Should it be @last_sentinel.prev?

Max Stack Pop

Correct me if I'm wrong, but isn't the pop on a max stack supposed to just return the value?

  max_stack.store
  => [[5, 5]]
  max_stack.pop
  => [5, 5]    # shouldn't this be 5?
  max_stack.store
  => []

Comment out return values or not? 

d_array = DataStruct::DynamicArray.new(4)
  => #<DynamicArray:0x007ffe5c089460 @num_items=0, @size=10, @start=0, @store=[nil, nil, nil, nil]>

Should we be using comments for the returns? Not sure how consistent we want to be on this or what the rules are for our readme.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.