#--
# Heap
#
# Copyright (c) 2002,2004 Renald Buter (Ruby Version)
# [See Cormen1990 for original]
#
# Ruby License
#
# This module is free software. You may use, modify, and/or redistribute this
# software under the same terms as Ruby.
#
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE.
#
#
# ==========================================================================
# Revision History
# --------------------------------------------------------------------------
# 2005.04.28 trans
#   Ported to Calibre and Documentatation.
# ==========================================================================
#
# NOTE:
#   Ruby Quiz has a simple Heap class and had a contest for writting 
#   ascii-ast visual trees of the heap. If someone would like
#   a small poject it would be cool to improve on this class, in general,
#   and also see about integrating the best of those Ruby Quiz solutions.
#
# THANKS:
#   Special thanks to Nenad Ocelic for many suggestions.
#
#++

#:title: Heap
#
# A simple Heap structure and sort.
#
# == Extending Heap
#
# To extend the heap, implement a cmp(i,j) method which compares array
# elements i and j and returns true iff i is larger than j, where larger or
# is the required heap sorting. See Heap::Min and Heap::Max for examples.
#
# == Notes
#
# The +parent+, +left+ and +right+ methods do not check the supplied parameter,
# but their result is _only_ valid if the supplied with an integer >=0 
# for +left+ and +right+ and >0 for +parent+.
#
# == Reference
#
#   <quote>
#   Cormen1990: Chapter 7 (Heapsort) of 'An introduction to algorithms', by
#   Cormen, T.H; Leiserson, C.E.; Rivest, R.L; MIT Press, Cambridge, 1990
#   ISBN 0-262-53091-0
#   </quote>
#
# == Author(s)
#
# * Renald Buter (buter at cwts nl)
#

class Heap

  class EmptyHeapException < Exception; end

  # We are an abstract class
  private_class_method :new
  def self.inherited(sub) sub.class_eval("public_class_method :new") end

  # Keeps an heap sorted with the largest element on top
  class Max < Heap

    def initialize(array=[]) super(array) end

    def cmp(a,b) a > b end

  end

  # Keeps an heap sorted with the smallest element on top
  class Min < Heap

    def initialize(array=[]) super(array) end

    def cmp(a,b) a < b end

  end

  # Initialise the heap. If supplied an array, build the heap with the values
  # of the array. The array can be unsorted. Note: this method can only be
  # called by superclasses
  def initialize(array)
    @array, @heap_size = array, array.length
    ((@heap_size * 0.5) - 1).downto(0) { |i| heapify(i) }
  end

  # Get the heap size
  def size
    @heap_size
  end

  # Pretty print
  def to_s
    "<#{self.class}: size=#@heap_size, top=#{self.top}>"
  end

  # Heap-sort a clone of the internal array. This will not touch the
  # internal array. Returns the array sorted *reversely* on the heap
  # condition!
  def sort
    old_ary = @array.dup
    old_heap = @heap_size
    new_ary = sort_internal
    @array = old_ary
    @heap_size = old_heap
    new_ary
  end

  # Heap-sort the internal array. This reduces heap size to 1, since
  # sorting the internal array destroys the heap property. Use this only if
  # the heap is not used after this call and you want save speed and
  # memory; otherwise use Heap#sort. See +Heap#sort+.
  def sort_internal
    (@array.length-1).downto(1) do |i|
      swap(0,i)
      @heap_size -= 1
      heapify(0)
    end
    @array
  end

  # Get the first (maximum) element on the heap
  def top
    raise EmptyHeapException if @heap_size < 1
    @array[0]
  end

  # Extract the first element from the heap. Will raise EmptyHeapException
  # if there are no (more) elements on the heap.
  def pop
    raise EmptyHeapException if @heap_size < 1
    @heap_size -= 1
    top, @array[0] = @array[0], @array[@heap_size]
    heapify(0)
    top
  end

  # Push an element on the heap.
  def push(elm)
    i = @heap_size
    @heap_size += 1
    while i > 0 and cmp(elm, @array[(j = parent(i))])
      @array[i] = @array[(i = j)]
    end
    @array[i] = elm
  end

  # Push a list of  elements on the heap.
  def push_all(elms)
    elms.each {|e| push(e)}
  end

protected

  # Compare elements at the supplied indices
  def cmp_idx(i,j) 
    cmp(@array[i], @array[j]) 
  end

  # Get the parent of the node i > 0.
  def parent(i)
    ( i - 1 ) >> 1  # (i-1)/2, only valid iff i > 0 !!
  end

  # Get the node left of node i >= 0
  def left(i)
    ( i << 1 ) + 1  # 2i+1
  end

  # Get the node right of node i >= 0
  def right(i)
    ( i << 1 ) + 2  # 2i+2
  end

  # Keeps an heap sorted with the smallest (largest) element on top
  def heapify(i)
    l = left i
    top = if l < @heap_size && cmp_idx(l,i) then l else i end
    r = right i
    top = if r < @heap_size && cmp_idx(r,top) then r else top end
    if top != i
      swap(i, top)
      heapify(top)
    end
  end

  # Get the size of the internal array. This may be different from the heap
  # size, e.g. after +sort+ has been called.
  def internal_size
    @array.size
  end

  # Swap elements in the array
  def swap(i,j)
    @array[i], @array[j] = @array[j], @array[i]
  end

end



#  _____         _
# |_   _|__  ___| |_
#   | |/ _ \/ __| __|
#   | |  __/\__ \ |_
#   |_|\___||___/\__|
#

# TODO

=begin #test

  require 'test/unit'

=end