Class: PQueue

Inherits:
Object show all
Defined in:
lib/carat-dev/priority-queue/pqueue.rb

Overview

PQueue

Priority queue with array based heap.

Authors

  • Rick Bradley 2003/02/02 (patch for Ruby 1.6.5. Thank you!)

  • K.Kodama 2001/03/10

This is distributed freely in the sence of GPL(GNU General Public License).

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#gt ⇒ Object (readonly)

Returns the value of attribute gt.



23
24
25
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 23

def gt
  @gt
end

#qarray ⇒ Object

Returns the value of attribute qarray.



21
22
23
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 21

def qarray
  @qarray
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



22
23
24
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 22

def size
  @size
end

Instance Method Details

#clear ⇒ Object 



77
78
79
80
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 77

def clear
  @qarray.replace([nil])
  @size=0
end

#clone ⇒ Object 



95
96
97
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 95

def clone
  q=new; q.qarray=@qarray.clone; q.size=@size; q.gt=@gt; return q;
end

#each_pop ⇒ Object

Iterate pop. Destructive. Use as self.each_pop{|x| … }.



151
152
153
154
155
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 151

def each_pop
  while(@size>0)
    yield self.pop
  end
end

#each_with_index ⇒ Object

Not ordered. Use as self.each_with_index{|e,i| … }.



159
160
161
162
163
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 159

def each_with_index
  (1..@size).each do |i|
    yield( @qarray[i], i )
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


72
73
74
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 72

def empty?
  return (0==@size)
end

#make_legal ⇒ Object 



65
66
67
68
69
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 65

def make_legal
  (2..@size).each do |k|
    upheap(k)
  end
end

#pop ⇒ Object

Return top element. Returns nil if queue is empty.



107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 107

def pop
  if @size > 0
    res = @qarray[1]
    @qarray[1] = @qarray[@size]
    @size -= 1
    downheap(1)
    return res
  else 
    return nil
  end
end

#push(v) ⇒ Object 



100
101
102
103
104
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 100

def push(v)
  @size += 1
  @qarray[@size] = v
  upheap(@size)
end

#replace(v) ⇒ Object

Rreplace top element.



137
138
139
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 137

def replace(arr=[])
  @qarray.replace([nil]+arr); @size=arr.size; make_legal
end

#replace_low(v) ⇒ Object

Replace top element if v < top element.



125
126
127
128
129
130
131
132
133
134
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 125

def replace_low(v)
  if @size > 0
    @qarray[0] = v
    downheap(0)
    return @qarray[0]
  else 
    @qarray[1] = v
    return nil
  end
end

#to_a ⇒ Object

Returns array sorted in increasing order.



83
84
85
86
87
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 83

def to_a
  res=@qarray[1..@size];
  res.sort!{|x,y| if @gt[x,y]; 1;elsif @gt[y,x]; -1; else 0; end;}
  return res
end

#top ⇒ Object

Returns top element, non-destructive.



120
121
122
 
# File 'lib/carat-dev/priority-queue/pqueue.rb', line 120

def top
  @size > 0 ? @qarray[1] : nil
end