Class: RubyVor::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/ruby_vor/priority_queue.rb,
ext/ruby_vor_c.c

Defined Under Namespace

Classes: QueueItem

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



31
32
33
34
35
 
# File 'lib/ruby_vor/priority_queue.rb', line 31

def initialize
  @data = []
  @size = 0
  heapify()
end

Instance Attribute Details

#data ⇒ Object (readonly)

Returns the value of attribute data.



4
5
6
 
# File 'lib/ruby_vor/priority_queue.rb', line 4

def data
  @data
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



4
5
6
 
# File 'lib/ruby_vor/priority_queue.rb', line 4

def size
  @size
end

Class Method Details

.build_queue(max_index = -1,, &block) ⇒ Object 



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/ruby_vor/priority_queue.rb', line 7

def build_queue(max_index=-1,&block)
  data = []

  index = 0
  loop do
    x = QueueItem.new(nil, nil, nil)

    yield(x)
    break if !(max_index < 0 || index < max_index) || x.priority.nil?
    
    x.index = index
    data.push(x)
    index += 1
  end

  q = new
  q.instance_variable_set(:@data, data)
  q.instance_variable_set(:@size, data.length)
  q.heapify()

  return q
end

Instance Method Details

#heapify ⇒ Object

#peek ⇒ Object 



37
38
39
 
# File 'lib/ruby_vor/priority_queue.rb', line 37

def peek
  @data[0]
end

#percolate_down ⇒ Object

#percolate_up ⇒ Object

#pop ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/ruby_vor/priority_queue.rb', line 41

def pop
  return nil if @size < 1
  
  r = @data[0]

  @data[0] = @data[@size-1]
  @data[0].index = 0
  @data.delete_at(@size-1)

  @size -= 1
  
  percolate_down(0) if @size > 0

  return r
end

#push(data, priority = data) ⇒ Object 



57
58
59
60
61
 
# File 'lib/ruby_vor/priority_queue.rb', line 57

def push(data, priority=data)
  @size += 1
  @data[@size - 1] = QueueItem.new(priority, @size - 1, data)
  percolate_up(@size - 1)
end

#reorder_queue ⇒ Object

Implemented in C



64
 
# File 'lib/ruby_vor/priority_queue.rb', line 64

def reorder_queue;end