--  Abstract:
--
--  An unbounded minimum binary heap of definite non-limited elements.
--
--  References:
--
--  [1] Introduction to Algorithms, Third Edition. Thomas H. Cormen,
--  Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Chapter 6.
--
--  Copyright (C) 2017 Stephen Leake.  All Rights Reserved.
--
--  This library is free software;  you can redistribute it and/or modify it
--  under terms of the  GNU General Public License  as published by the Free
--  Software  Foundation;  either version 3,  or (at your  option) any later
--  version. This library is distributed in the hope that it will be useful,
--  but WITHOUT ANY WARRANTY;  without even the implied warranty of MERCHAN-
--  TABILITY or FITNESS FOR A PARTICULAR PURPOSE.
--
--  As a special exception under Section 7 of GPL version 3, you are granted
--  additional permissions described in the GCC Runtime Library Exception,
--  version 3.1, as published by the Free Software Foundation.

pragma License (Modified_GPL);

with Ada.Finalization;
with Ada.Unchecked_Deallocation;
generic
   type Element_Type is private;
   type Key_Type is private;
   with function Key (Item : in Element_Type) return Key_Type;
   with procedure Set_Key (Item : in out Element_Type; Key : in Key_Type);
   pragma Unreferenced (Set_Key); -- needed for Decrease_Key
   with function "<" (Left, Right : in Key_Type) return Boolean is <>;

   Initial_Size : in SAL.Base_Peek_Type := 128; --  Initial internal data array size.
package SAL.Gen_Unbounded_Definite_Min_Heaps_Binary is

   type Heap_Type is new Ada.Finalization.Controlled with private;

   Empty_Heap : constant Heap_Type;

   overriding
   procedure Initialize (Object : in out Heap_Type);

   overriding
   procedure Finalize (Object : in out Heap_Type);

   overriding
   procedure Adjust (Object : in out Heap_Type);

   procedure Clear (Heap : in out Heap_Type);
   --  Empty Heap (may not free memory; use Finalize for that).

   function Count (Heap : in Heap_Type) return Base_Peek_Type;
   --  Return count of elements in Heap.

   function Remove (Heap : in out Heap_Type) return Element_Type;
   --  Remove minimum element in Heap, return it.

   function Min_Key (Heap : in out Heap_Type) return Key_Type;
   --  Return a copy of the minimum key value.

   function Get (Heap : in out Heap_Type) return Element_Type renames Remove;

   procedure Drop (Heap : in out Heap_Type);
   --  Remove minimum element in Heap, discard it.

   procedure Add (Heap : in out Heap_Type; Item : in Element_Type);
   --  Add Item to Heap.

   procedure Insert (Heap : in out Heap_Type; Item : in Element_Type) renames Add;

   --  procedure Increase_Key (Heap : in out Heap_Type; index : in index_type; Item : in Element_Type);
   --  IMPROVEME: implement. need Index (heap, Key), or Add return index.
private

   type Element_Array is array (SAL.Peek_Type range <>) of Element_Type;
   type Element_Array_Access is access Element_Array;

   procedure Free is new Ada.Unchecked_Deallocation (Element_Array, Element_Array_Access);

   type Heap_Type is new Ada.Finalization.Controlled with record
      Data : Element_Array_Access;
      --  Root is at Data (1).

      Count : Base_Peek_Type;
      --  [1] 6.1 heap-size = Count, length = Data'Length.
   end record;

   Empty_Heap : constant Heap_Type := (Ada.Finalization.Controlled with Data => null, Count => 0);

end SAL.Gen_Unbounded_Definite_Min_Heaps_Binary;