PQueue

# File lib/facets/more/pqueue.rb, line 43
  def initialize(compareProc=lambda{|x,y| x>y})
    # By default, retrieves maximal elements first. 
    @qarray=[nil]; @size=0; @gt=compareProc; make_legal
  end

# File lib/facets/more/pqueue.rb, line 78
  def clear
    @qarray.replace([nil]); @size=0;
  end

# File lib/facets/more/pqueue.rb, line 87
  def clone
    q=new; q.qarray=@qarray.clone; q.size=@size; q.gt=@gt; return q;
  end

# File lib/facets/more/pqueue.rb, line 144
  def each_pop
    # iterate pop. destructive. Use as self.each_pop{|x| ... }. 
    while(@size>0); yield self.pop; end;
  end

# File lib/facets/more/pqueue.rb, line 149
  def each_with_index
    # Not ordered. Use as self.each_with_index{|e,i| ... }. 
    for i in 1..@size do; yield @qarray[i],i; end;
  end

# File lib/facets/more/pqueue.rb, line 74
  def empty?
    return (0==@size)
  end

# File lib/facets/more/pqueue.rb, line 70
  def make_legal
    for k in 2..@size do; upheap(k); end;
  end

# File lib/facets/more/pqueue.rb, line 99
  def pop
    # return top element.  nil if queue is empty.
    if @size>0;
      res=@qarray[1]; @qarray[1]=@qarray[@size]; @size=@size-1;
      downheap(1);
      return res;
    else return nil
    end;
  end

# File lib/facets/more/pqueue.rb, line 109
  def pop_array(n=@size)
    # return top n-element as an sorted array. (i.e. The obtaining array is decreasing order.)
    # See also to_a.
    a=[]
    n.times{a.push(pop)}
    return a
  end

# File lib/facets/more/pqueue.rb, line 91
  def push(v)
    @size=@size+1; @qarray[@size]=v; upheap(@size);
  end

# File lib/facets/more/pqueue.rb, line 95
  def push_array(arr=[])
    @qarray[@size+1,arr.size]=arr; arr.size.times{@size+=1; upheap(@size)}
  end

# File lib/facets/more/pqueue.rb, line 82
  def replace_array(arr=[])
    # Use push_array.
    @qarray.replace([nil]+arr); @size=arr.size; make_legal
  end

# File lib/facets/more/pqueue.rb, line 137
  def replace_top(v)
    # replace top element
    if @size>0; res=@qarray[1]; @qarray[1]=v; downheap(1); return res;
    else @qarray[1]=v; return nil;
    end;
  end

# File lib/facets/more/pqueue.rb, line 130
  def replace_top_low(v)
    # replace top element if v<top element.
    if @size>0; @qarray[0]=v; downheap(0); return @qarray[0];
    else @qarray[1]=v; return nil;
    end;
  end

# File lib/facets/more/pqueue.rb, line 117
  def to_a
    # array sorted as increasing order.
    # See also pop_array.
    res=@qarray[1..@size];
    res.sort!{|x,y| if @gt[x,y]; 1;elsif @gt[y,x]; -1; else 0; end;}
    return res
  end

# File lib/facets/more/pqueue.rb, line 125
  def top
    # top element. not destructive.
    if @size>0; return @qarray[1]; else return nil; end;
  end

# File lib/facets/more/pqueue.rb, line 58
  def downheap(k)
    v=@qarray[k]; q2=@size.div(2)
    loop{
      if (k>q2); break; end;
      j=k+k; if ((j<@size)and(@gt[@qarray[j+1],@qarray[j]])); j=j+1; end;
      if @gt[v,@qarray[j]]; break; end;
      @qarray[k]=@qarray[j]; k=j;
    }
    @qarray[k]=v;
  end

# File lib/facets/more/pqueue.rb, line 49
  def upheap(k)
    k2=k.div(2); v=@qarray[k];
    while ((k2>0)and(@gt[v,@qarray[k2]]));
      @qarray[k]=@qarray[k2]; k=k2; k2=k2.div(2)
    end;
    @qarray[k]=v;
  end