# Priority queue with array based heap.
#
# This is distributed freely in the sence of 
# GPL(GNU General Public License).
#
# Brent@mbari.org 2003/6/4 for Ruby 1.6.8 -- was called PQueue
# Rick Bradley 2003/02/02 patch for Ruby 1.6.5. Thank you!
# K.Kodama 2001/03/10

require 'mbari'

class PriorityQ < Array

  protected :[], :[]=, :at, :indexes, :indices, :each_index, :index, :rindex
  protected :slice, :slice!
  private   :map!, :map, :collect!, :fill, :flatten, :flatten!
  private   :rassoc, :reverse, :reverse!
    
  rename_method :aryConcat, :concat
  private :aryConcat
 
  def initialize(heap=[nil], &compareProc)
    # By default, retrieves maximal elements first.
    # don't supply the heap argument from calls outside this class!
    # default compareProc keeps greatest key at heap top for a descending sort
    aryConcat heap
    compareProc = proc{|x,y| x<=>y} unless compareProc
    @compare=compareProc
  end

  attr_reader :compare
  
  def size
    super-1
  end
  
  def eachPriority (v, &block)
  #execute supplied block each item in heap with v's priority
    forPriority (v, 1, proc {|i| block[at(i)]})
  end
  
  def include? v
    catch (:found) {
      eachPriority(v) {|item| throw :found, true if item==v}
      false
    }
  end
  
  def empty?
    size < 1
  end

  def clear
    slice!(1,size)
    self
  end;

  def to_a
    []+slice(1,size)
  end

  def replace(arr=[])
    super([nil]+arr); make_legal
    self
  end
  
  def clone
    type.new([]+self, &@compare)
  end

  def << (v)
    super; upheap(size)
    self
  end
  alias_method :unshift, :<<

  def concat (other)
    for v in other.to_a do self << v; end
    self
  end

  def + (other)
    clone.concat other
  end
      
  def push (*a)
    concat a
  end

  def first
    # top element. not destructive.
    at(1)
  end
  alias_method :top, :first
    

  def pop
    # return top element.  nil if queue is empty.
    res=first
    if size < 2
      clear
    else
      self[1]=super
      downheap(1)
    end
    res
  end
  alias_method :shift, :pop
  

  def each
    # Not ordered.
    for i in 1..size do yield at(i); end
  end

  def reverse_each
    # reverse order of each (but no particular order)
    i = size
    while i > 0
      yield at(i)
      i-=1
    end
  end

  def each!
    # in priority order!
    # otherwise, same as each, but empties the heap in the process
    yield pop until empty?
  end

  def sort!
  #sort the heap.  Result is a sorted array.
  #the heap is cleared
    a = [];
    each! {|n| a << n}
    a
  end
  

  def delete_at (i)
  # remove element at i from heap
    return pop if i < 2
    return super(size) if i>=size
    self[i]=super(size)
    downheap(i)
  end
  private :delete_at
  

  def deletePriority (v)
  # remove all items in heap with the same priority as v's
  # if a block is suppled, each "v prioity item" is passed to it.
  # When block returns:
  #    true => the item is deleted 
  #   false or nil => the item is not deleted
  # if block throws (:last) the search is terminated and
  #  the last item passed to block is deleted if throw parameter is true
  # returns the number of items deleted
    indices=[]
    begin
      if block_given?
        i=nil
        if catch (:last) do
                           eachIndex(v) {|i|indices<<i if yield at i}
                           nil
                         end
          indices<<i
        end
      else
        eachIndex(v) {|i| indices<<i}
      end
    ensure
      indices.reverse_each {|i| delete_at(i)}
    end
    indices.size
  end


  def delete (v)
  #analogous to Array#delete
    return v if deletePriority (v) {|item| item==v} > 0
    block_given? ? yield : nil
  end
  
    
  def reject!
  # remove all items for which the supplied block is true
  # returns nil if no changes made
    res=nil
    size.downto(1) {
      if yield at(i)
        delete_at(i)
        res=self
      end
    }
    res
  end
  

  def delete_if
  # remove all items for which the supplied block is true
    reject!
    self
  end
  

  def replaceTop(v)
    # replace the item at the top of the heap
    # same as x=pop; push v; return x 
    if empty?
      self[1]=v
      nil
    else
      top=first; self[1]=v
      downheap(1)
      top
    end
  end


  def op (operator, other)
    type.new (@compare, [nil]+(to_a.method(operator)[other]))
  end
  private :op
  
  def & (other)
    op (:&, other.to_a)
  end
  
  def | (other)
    op (:|, other.to_a)
  end
  
  def - (other)
    op (:-, other.to_a)
  end
  
  def * (other)
    op (:*, other)
  end
  
  def uniq!
    replace (to_a.uniq)
  end
  
  def uniq
    type.new (@compare, [nil]+to_a.uniq)
  end

  def sort
  #sort the heap. Result is a sorted array.
  #the original heap is preserved
    clone.sort!
  end
  
  def join (aSepString=$,)
    to_a.join (aSepString)
  end

  def to_s
    to_a.to_s
  end
  
  def inspect
    to_a.inspect
  end
    
    
  protected
  
  def gt (x,y)
    @compare[x,y] > 0
  end  

  def upheap(child)
    parent=child>>1; v=at(child)
    while parent>0 and gt(v, at(parent))
      self[child]=at(parent)
      child=parent; parent>>=1
    end
    self[child]=v
  end

  def make_legal
    for k in 2..size do; upheap(k); end
  end


  def downheap(parent)
    v=at(parent); lastLeaf=size>>1
    loop{
      break if parent>lastLeaf
      child=parent+parent
      child+=1 if child<size and gt(at(child+1),at(child))
      break if gt(v, at(child))
      self[parent]=at(child); parent=child
    }
    self[parent]=v
  end


  def forPriority (v, parent, block)
  #execute supplied block on index of each item in heap with v's priority
  #begin search at parent
    if size>=parent and (c=(@compare[at(parent),v]))>=0
      block[parent] if c==0        
      child=parent+parent
      if child <= size
        forPriority (v, child, block)
        forPriority (v, child+1, block) if child < size
      end
    end
  end
  
  def eachIndex (v, &block)
  #execute supplied block on index of each item in heap with v's priority
    forPriority (v, 1, block)
  end
  
end # class PriorityQ

if $0 == __FILE__
  pq=PriorityQ.new
  pq.push(2,3,4)
  pq.push(3,2,4)
  pq.push(-6,14,1)
  print pq.size.to_s+"\n"
  print pq.join(",")+"\n"
  print pq.sort.join(",")+"\n"
  pq.each{|x| p x}
  p "---"
  print "Deleting ",pq.delete (1),"\n"
  print "Deleting ",pq.deletePriority(3) {throw :last, true}, " threes \n"
  puts pq.include? 3
  pq.each!{|x| p x}
end