/*
 * Copyright (c) 2004-2008 The University of Wroclaw.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *    1. Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *    2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *    3. The name of the University may not be used to endorse or promote
 *       products derived from this software without specific prior
 *       written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
 * NO EVENT SHALL THE UNIVERSITY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

using SCG = System.Collections.Generic; 
 
namespace Nemerle.Collections
{
  /**
   * A handy shortcut for the EmptyCollection exception.
   */
  public class EmptyHeap : EmptyCollection
  {
    public this () { base ("Nemerle.Collections.Heap") }
  }
  
  /**
   * General usage heap, can be used as priority queue.
   */
  public class Heap ['a] : SCG.ICollection ['a] where 'a : System.IComparable ['a]
  {
    /* -- PUBLIC CONSTRUCTORS ----------------------------------------------- */
    
    /** 
     * Creates new heap that will initialy contain elements from array a.
     * All the elements are copied into the heap, so later modifications of a
     * do not influence the heap. This operation takes time O(n), where n 
     * is the number of elements in array a.
     */
    public this (a : array ['a])
    {
      m_elements_count = a.Length;
      m_heap = array (a.Length + 1);
      a.CopyTo (m_heap, 1);
      build_heap ();
    }

    /**
     * Creates new heap initially filled with elements from given collection
     */
    public this (coll : SCG.IEnumerable ['a])
    {
      m_elements_count = 0;
      m_heap = array (10);
      
      foreach (x in coll) {
        when (m_elements_count >= m_heap.Length - 1)
          grow ();
        m_elements_count++;
        m_heap [m_elements_count] = x;
      }
      
      build_heap ();
    }
        
    /**
     * Creates a new empty heap with given initial capacity.
     */
    public this (capacity : int)
    {
      def capacity = if (capacity >= 10) capacity else 10;

      m_heap = array (capacity + 1);
      m_elements_count = 0
    }

    
    /* -- PRIVATE CONSTRUCTORS ---------------------------------------------- */
    
    /** 
     * Private constructor, do not use from outside this class.
     */
    private this ()
    {
      /* do nothing */
    }

    
    /* -- PUBLIC PROPERTIES ------------------------------------------------- */
    
    /**
     * Checks if the heap is empty.
     */
    public IsEmpty : bool
    {
      get { m_elements_count == 0 }
    }

    
    /**
     * Returns number of elements in the heap.
     */
    public Count : int
    {
      get { m_elements_count }
    }

    /**
     * Returns the number of elements that this heap can store
     * without the need to grow.
     */
    public CurrentCapacity : int
    {
      get { m_heap.Length - 1 }
    }

    /**
     * Returns false.
     */ 
    public IsReadOnly : bool {
      get { false } 
    }
    
    /**
     * Returns the number of elements that this heap can store
     * without the need to grow.
     */
    public Capacity : int
    {
      get { m_heap.Length - 1 }
    }

    /* -- PUBLIC METHODS ---------------------------------------------------- */
    
    /**
     * Inserts a new element into the heap.
     */
    public Insert (x : 'a) : void
    {
      when (m_elements_count >= m_heap.Length - 1)
        grow ();

      ++m_elements_count;
      
      mutable i = m_elements_count;      
      while (i > 1 && x.CompareTo (m_heap [parent (i)]) > 0)
      {
        m_heap [i] = m_heap [parent (i)];
        i = parent (i)
      }
      
      m_heap [i] = x
    }

    /*
     * Adds element to heap. Alist for Insert method.
     */
    public Add (x : 'a) : void
    {
      Insert (x)
    }
    
    /**
     * Count is set to 0, and references to other objects from elements of the collection are also released.
     *
     * Capacity remains unchanged.
     */
    public Clear () : void
    {
      System.Array.Clear (m_heap, 1, m_elements_count);
      m_elements_count = 0;
    }
    
    /**
     * Returns the first (with maximal priority) element from the heap
     * without removing it. Throws EmptyHeap exception.
     */
    public Top () : 'a
    {
      if (m_elements_count == 0)
        throw EmptyHeap ()
      else 
        m_heap [1]
    }

    
    /**
     * Returns the first (with maximal priority) element from the heap,
     * removing it. Throws EmptyHeap exception.
     */
    public ExtractFirst () : 'a
    {
      if (m_elements_count < 1)
        throw EmptyHeap ()
      else
      {
        // FIXME: get rid of `result' -- use <--> instead
        def result = m_heap [1];
        m_heap [1] = m_heap [m_elements_count];
        --m_elements_count;
        heapify (1);
        result
      } 
    }

    /**
     * Copies elements from heap to given array, starting at specified index in target array
     */
    public CopyTo (to : array ['a], mutable startIdx : int) : void
    {
      startIdx--; // because i is 1-based
      for (mutable i = 1; i <= m_elements_count; i++)
        to [startIdx + i] = m_heap [i];
    }
    
    /**
     * Checks if given value is contained in heap. This is O(n) operation in worst case.
     */ 
    public Contains (x : 'a) : bool
    {
      System.Array.IndexOf (m_heap, x, 1) != -1
    }
    
    /**
     * Creates new heap of elements of type 'b. New heap is totally independent, i.e.
     * any changes in original heap do not influence the second one and vice versa.
     */
    public Map ['b] (f : 'a -> 'b) : Heap ['b] where 'b : System.IComparable ['b] 
    {
      def newHeapArray = array (m_heap.Length + 1);
      
      for (mutable i = 1; i <= m_elements_count; ++i)
        newHeapArray [i] = f (m_heap [i]);

      def newHeap = Heap ();
      newHeap.m_heap = newHeapArray;
      newHeap.m_elements_count = m_elements_count;
      newHeap.build_heap ();
      newHeap
    }

    
    /**
     * Calls the specified function for all elements of this heap.
     */
    public Iter (f : 'a -> void) : void 
    {
      for (mutable i = 1; i <= m_elements_count; ++i)
        f (m_heap [i])
    }

    
    /**
     * Folds this heap's elements using the specified function
     * and an initial value.
     */
    public Fold ['b] (f : ('b * 'a) -> 'b, x : 'b) : 'b
    {
      mutable v = x;
      for (mutable i = 1; i <= m_elements_count; ++i)
        v = f (v, m_heap [i]);
      v  
    }

    public GetEnumerator () : SCG.IEnumerator ['a]
    {
      for (mutable i = 1; i <= m_elements_count; i++)
        yield m_heap [i];
    }
    
    /* HIDDED INTERFACE IMPLEMENTATION */
    
    private Remove (_ : 'a) : bool implements SCG.ICollection.Remove
    {
      throw System.NotSupportedException ("remove operation is not supported by heap class");
    }

    /* -- PRIVATE METHODS --------------------------------------------------- */
    
    /**
     * Grows the table that is used to store heap elements
     * multiplying size by 2.
     */
    private grow () : void
    {
      def newSize = 2 * m_heap.Length;
      def newHeap = array (newSize + 1);

      m_heap.CopyTo (newHeap, 0);

      m_heap = newHeap
    }

    
    /**
     * Checks if the element at index k is greater than the element at index l.
     */
    private is_greater (k : int, l : int) : bool
    {
      m_heap [k].CompareTo (m_heap [l]) > 0
    }


    /**
     * Calculates the index of the parent of element at index i.
     */
    private static parent (i : int) : int
    {
      i >> 1
    }

    
    /**
     * Calculates the index of the left child of element at index i.
     */
    private static left (i : int) : int
    {
      i << 1
    }

    
    /**
     * Calculates the index of the right child of element at index i.
     */
    private static right (i : int) : int
    {
      2 * i + 1
    }

    /**
     * Repairs the heap structure starting from element at index i, moving down.
     * For explanations see Cormen, Leiserson, Rivest "Introduction to algorithms".
     */
    private heapify (i : int) : void
    {
      def l = left (i);
      def r = right (i);
      mutable largest = 0;
      
      if (l <= m_elements_count && is_greater (l, i)) 
        largest = l
      else
        largest = i;
        
      when (r <= m_elements_count && is_greater (r, largest))
        largest = r;
        
      when (largest != i)
      {
        m_heap [i] <-> m_heap [largest];
        heapify (largest)
      }
    }

    
    /**
     * Builds the heap from elements stored in the m_heap array. 
     * This is done in time O (m_heap.Length).
     */
    private build_heap () : void
    {
      for (mutable i = m_elements_count / 2; i >= 1; --i)
        heapify(i)
    }
    
    
    /* -- PRIVATE FIELDS ---------------------------------------------------- */

    /**
     * An array that stores the heap, elements are stored in heap[1]..heap[count]
     */
    private mutable m_heap : array ['a];
     
    /**
     * The number of the elements that are in the heap right now
     */
    private mutable m_elements_count : int;
  }
}