123456789_123456789_123456789_123456789_123456789_

Class: SyntaxSuggest::PriorityQueue

Relationships & Source Files
Inherits: Object
Defined in: lib/syntax_suggest/priority_queue.rb

Overview

Holds elements in a priority heap on insert

Instead of constantly calling sort!, put the element where it belongs the first time around

Example:

queue = PriorityQueue.new
queue << 33
queue << 44
queue << 1

puts queue.peek # => 44

Class Method Summary

Instance Attribute Summary

Instance Method Summary

Constructor Details

.new ⇒ PriorityQueue

[ GitHub ] 

  


# File 'lib/syntax_suggest/priority_queue.rb', line 22



def initialize
  @elements = []
end


  







Instance Attribute Details



  

    #elements   (readonly)
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 20



attr_reader :elements


  








  

    #empty?  ⇒ Boolean  (readonly)
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 42



def empty?
  @elements.empty?
end


  







Instance Method Details



  

    #<<(element)  
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 26



def <<(element)
  @elements << element
  bubble_up(last_index, element)
end


  








  

    #bubble_down(index)   (private)
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 81



private def bubble_down(index)
  child_index = (index * 2) + 1

  return if child_index > last_index

  not_the_last_element = child_index < last_index
  left_element = @elements[child_index]
  right_element = @elements[child_index + 1]

  child_index += 1 if not_the_last_element && (right_element <=> left_element) == 1

  return if (@elements[index] <=> @elements[child_index]) >= 0

  exchange(index, child_index)
  bubble_down(child_index)
end


  








  

    #bubble_up(index, element)   (private)
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 69



private def bubble_up(index, element)
  return if index <= 0

  parent_index = (index - 1) / 2
  parent = @elements[parent_index]

  return if (parent <=> element) >= 0

  exchange(index, parent_index)
  bubble_up(parent_index, element)
end


  








  

    #exchange(source, target)  
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 98



def exchange(source, target)
  a = @elements[source]
  b = @elements[target]
  @elements[source] = b
  @elements[target] = a
end


  








  

    #last_index   (private)
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 65



private def last_index
  @elements.size - 1
end


  








  

    #length  
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 38



def length
  @elements.length
end


  








  

    #peek  
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 46



def peek
  @elements.first
end


  








  

    #pop  
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 31



def pop
  exchange(0, last_index)
  max = @elements.pop
  bubble_down(0)
  max
end


  








  

    #sorted  
  



  

    

Used for testing, extremely not performant


  



  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 55



def sorted
  out = []
  elements = @elements.dup
  while (element = pop)
    out << element
  end
  @elements = elements
  out.reverse
end


  








  

    #to_a  
  

  [ GitHub ]


  

  


# File 'lib/syntax_suggest/priority_queue.rb', line 50



def to_a
  @elements
end