File : asgc-heap-expandable_managed.adb


-- The Ada Structured Library - A set of container classes and general
--   tools for use with Ada95.
-- Copyright (C) 1998-1999  Corey Minyard (minyard@acm.org)
--
-- This library is free software; you can redistribute it and/or modify it
-- under the terms of the GNU General Public License as published by the
-- Free Software Foundation; either version 2 of the License, 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
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-- General Public License for more details.
--
-- You should have received a copy of the GNU General Public License along
-- with this library; if not, write to the Free Software Foundation, Inc.,
-- 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
--
-- As a special exception, if other files instantiate generics from this
-- unit, or you link this unit with other files to produce an executable,
-- this unit does not by itself cause the resulting executable to be
-- covered by the GNU General Public License.  This exception does not
-- however invalidate any other reasons why the executable file might be
-- covered by the GNU Public License.
--

with Ada.Unchecked_Deallocation;

package body Asgc.Heap.Expandable_Managed is

   procedure Free_Heap_Array is new Ada.Unchecked_Deallocation(Heap_Array,
                                                               Heap_Array_Ptr);

   procedure Free_Iterator is new Ada.Unchecked_Deallocation(Iterator,
                                                             Iterator_Ptr);


   ------------------------------------------------------------------------
   -- Check that an object is valid, that is has not been freed.  This is
   -- not a perfect check, but will hopefully help find some bugs.
   procedure Check_Object (O : in Object'Class) is
   begin
      if (O.Is_Free) then
         raise Object_Free;
      end if;
   end Check_Object;


   ------------------------------------------------------------------------
   -- Check that an iterator is valid.  It must not have been freed, it
   -- must be initialized, its object must be valid, and it must not have
   -- been modified since the last time the iterator was positioned.
   procedure Check_Iterator (Iter : in Iterator'Class) is
   begin
      if (Iter.Is_Free) then
         raise Iterator_Free;
      end if;

      if (Iter.Robj = null) then
         raise Invalid_Iterator;
      end if;

      Check_Object(Iter.Robj.all);

      if (Iter.Update /= Iter.Robj.Update) then
         raise Object_Updated;
      end if;

      if (Iter.Pos = Null_Node) then
         raise Invalid_Iterator;
      end if;
   end Check_Iterator;


   ------------------------------------------------------------------------
   -- Check an iterator, but don't bother checking its positions.  This is
   -- primarily for methods that set some the position of the iterator.
   procedure Check_Iterator_No_Pos (Iter : in Iterator'Class) is
   begin
      if (Iter.Is_Free) then
         raise Iterator_Free;
      end if;

      if (Iter.Robj = null) then
         raise Invalid_Iterator;
      end if;

      Check_Object(Iter.Robj.all);
   end Check_Iterator_No_Pos;


   -- A heap is organized in a tree-like structure, except that instead of
   -- the standard left < node < right structure, we use node > left and
   -- node > right.  So we might have:
   --
   --                            99
   --                  87                 77
   --             76       33         66       39
   --           23  12   10  9      44  22
   --
   -- This is the "virtual" structure, the actual structure varies with
   -- implementation.  In this structure, 99 is at the "top" of the heap.
   -- It is also the "first" item.  22 is the "last" item in the heap.  The
   -- item directly above another item is its "parent", down and to the
   -- left is the left child, and down and to the right is the right child.
   -- The next item to the direct left is called the "left neighbor".  If
   -- the item is on the left side of the tree, then the left neighbor is
   -- the rightmost entry on the row above the value.  The "right neighbor"
   -- is similar except it goes to the right and will go to the row below
   -- the value if the value is on the right of the tree.
   --
   -- So in the example above, we have:
   --
   --       parent  left child  right child   left neighbor  right neighbor
   --       ------  ----------  -----------   -------------  --------------
   --  76     87        23          12             77             33
   --  66     77        44          22             33             39
   --  39     77        --          --             66             23
   --  99     --        87          77             --             87
   --  22     66        --          --             44             --
   --



   ------------------------------------------------------------------------
   -- Expandable heaps are implemented as an array.  This make finding the
   -- left and right neighbors easy, but it makes finding the children and
   -- parents a little more complex.


   ------------------------------------------------------------------------
   -- Return the parent of the current node in the heap.  Since the heap is
   -- binary, we can just divide by two.
   function Parent (O   : in Object'Class;
                    Pos : in Node_Ref)
                    return Node_Ref is
   begin
      if (Pos = 1) then
         return Null_Node;
      else
         return Pos / 2;
      end if;
   end Parent;


   ------------------------------------------------------------------------
   -- Return the node that is the left child of the given node.  Since the
   -- heap is binary, we can multiply by two.
   function Left_Child (O   : in Object'Class;
                        Pos : in Node_Ref)
                        return Node_Ref is
      Retval : Node_Ref;
   begin
      Retval := Pos * 2;
      if (Retval > O.Count) then
         return Null_Node;
      else
         return Retval;
      end if;
   end Left_Child;


   ------------------------------------------------------------------------
   -- Return the node that is the right child of the given node.  Since the
   -- heap is binary, we can multiply by two and add one.
   function Right_Child (O   : in Object'Class;
                         Pos : in Node_Ref)
                         return Node_Ref is
      Retval : Node_Ref;
   begin
      Retval := Pos * 2 + 1;
      if (Retval > O.Count) then
         return Null_Node;
      else
         return Retval;
      end if;
   end Right_Child;


   ------------------------------------------------------------------------
   -- Return the node that is to the "left" of the given node.
   function Left_Neighbor (O   : in Object'Class;
                           Pos : in Node_Ref)
                           return Node_Ref is
   begin
      if (Pos = 1) then
         return Null_Node;
      else
         return Pos - 1;
      end if;
   end Left_Neighbor;


   ------------------------------------------------------------------------
   -- Return the node that is to the "right" of the given node.
   function Right_Neighbor (O   : in Object'Class;
                            Pos : in Node_Ref)
                            return Node_Ref is
   begin
      if (Pos = O.Count) then
         return Null_Node;
      else
         return Pos + 1;
      end if;
   end Right_Neighbor;


   ------------------------------------------------------------------------
   -- Add a new value into the last position in the heap.
   procedure Add_New_Last (O   : in out Object'Class;
                           Val : in Contained_Type) is
   begin
      if (O.Count = O.Data'Last) then
         -- The container is full, so extend it if we can.

         if (O.Increment = 0) then
            raise Container_Full;
         end if;

         declare
            New_Val : Heap_Array_Ptr;
         begin
            New_Val := new Heap_Array(1 .. O.Count + O.Increment);
            New_Val.all(1 .. O.Count) := O.Data.all;
            Free_Heap_Array(O.Data);
            O.Data := New_Val;
         end;
      end if;

      O.Count := O.Count + 1;
      O.Tail := O.Count;
      if (O.Head = Null_Node) then
         O.Head := O.Count;
      end if;
      O.Data(O.Tail).Val := Val;
   end Add_New_Last;


   ------------------------------------------------------------------------
   -- Remove the tail value from the heap.  This routine should not be
   -- called if the tail is at the top of the tree.
   procedure Remove_Last (O : in out Object'Class) is
   begin
      O.Count := O.Count - 1;
   end Remove_Last;


   ------------------------------------------------------------------------
   -- Swap two values in the heap.  This will just swap the values in the
   -- container.  Nodes must be writable and will point to the new
   -- locations of the nodes in the heap.
   procedure Swap (O     : in out Object'Class;
                   Node1 : in out Node_Ref;
                   Node2 : in out Node_Ref) is
      Tmp_Val  : Contained_Type;
      Tmp_Node : Node_Ref;
   begin
      Tmp_Val := O.Data(Node1).Val;
      O.Data(Node1).Val := O.Data(Node2).Val;
      O.Data(Node2).Val := Tmp_Val;
      Tmp_Node := Node1;
      Node1 := Node2;
      Node2 := Tmp_Node;
   end Swap;


   ------------------------------------------------------------------------
   -- Find the specified value in the heap.  This just does a linear search
   -- from the first value.
   function Find_Val (O   : in Object'Class;
                      Val : in Contained_Type)
                      return Node_Ref is
      Retval : Node_Ref;
   begin
      Retval := O.Head;
      while (Retval /= Null_Node) loop
         exit when (O.Data(Retval).Val = Val);

         Retval := Right_Neighbor(O, Retval);
      end loop;

      return Retval;
   end Find_Val;


   ------------------------------------------------------------------------
   -- Find the next position in the heap with the same value.  This just
   -- does a linear search from the current value.
   function Find_Val_Again (O    : in Object'Class;
                            Curr : in Node_Ref)
                            return Node_Ref is
      Retval : Node_Ref;
   begin
      Retval := Right_Neighbor(O, Curr);
      while (Retval /= Null_Node) loop
         exit when (O.Data(Retval).Val = O.Data(Curr).Val);

         Retval := Right_Neighbor(O, Retval);
      end loop;

      return Retval;
   end Find_Val_Again;


   ------------------------------------------------------------------------
   -- Delete a node in the graph.
   procedure Delete_Node (O      : in out Object'Class;
                          Del_Me : in Node_Ref) is
      New_Tail : Node_Ref;
      Curr     : Node_Ref;
      Went_Up  : Boolean;
      Left     : Node_Ref;
      Right    : Node_Ref;
      Up       : Node_Ref;
      Node     : Node_Ref := Del_Me;
   begin
      New_Tail := Left_Neighbor(O, O.Tail);
      if (New_Tail = Null_Node) then
         -- We are the only member of the heap, so just clear it.
         if (O.Tail /= Node) then
            raise Internal_Heap_Error;
         end if;
         O.Head := Null_Node;
         O.Tail := Null_Node;
         O.Count := 0;
      elsif (Node = O.Tail) then
         -- Deleting the tail value is easy.
         Remove_Last(O);
         O.Tail := New_Tail;
      else
         -- We are removing an intermediate node someplace.  Swap it with
         -- the tail and then find the tail node's place.

         Curr := O.Tail;

         -- Swap the tail with the value to delete.
         Swap(O, Curr, Node);

         Remove_Last(O);
         O.Tail := New_Tail;

         -- Now do the swapping to put the old tail value (now in the heap
         -- someplace else) in the proper place in the tree.

         -- Move up while we can move up, swapping values as we go.
         Went_Up := False;
         Up := Parent(O, Curr);
         while ((Up /= Null_Node)
                and then (O.Data(Up).Val < O.Data(Curr).Val))
         loop
            Went_Up := True;
            Swap(O, Curr, Up);
            Up := Parent(O, Curr);
         end loop;

         -- Now go down while we can go down, swapping values as we go, if
         -- we didn't go up at all.
         if (not Went_Up) then
            loop
               Left := Left_Child(O, Curr);
               Right := Right_Child(O, Curr);
               if ((Left /= Null_Node) and (Right /= Null_Node)) then
                  -- A left and right child, so we need to figure out where
                  -- to go down.
                  if (O.Data(Left).Val > O.Data(Right).Val) then
                     -- We always prefer moving up the larger value.
                     if (O.Data(Left).Val > O.Data(Curr).Val) then
                        Swap(O, Curr, Left);
                     else
                        -- Both values are greater than us, we are done.
                        exit;
                     end if;
                  else
                     -- We always prefer moving up the larger value.
                     if (O.Data(Right).Val > O.Data(Curr).Val) then
                        Swap(O, Curr, Right);
                     else
                        -- Both values are greater than us, we are done.
                        exit;
                     end if;
                  end if;
               elsif ((Left /= Null_Node)
                      and then (O.Data(Left).Val > O.Data(Curr).Val))
               then
                  -- No right reference, and the left reference is greater
                  -- than is, so swap to the left.
                  Swap(O, Curr, Left);
               elsif ((Right /= Null_Node)
                      and then (O.Data(Right).Val > O.Data(Curr).Val))
               then
                  -- No left reference, and the left reference is greater
                  -- than is, so swap to the left.
                  Swap(O, Curr, Right);
               else
                  -- Either the node has no left or right reference or it
                  -- has one child but the child is less than us.  We are
                  -- done.
                  exit;
               end if;
            end loop;
         end if;
      end if;

      O.Update := O.Update + 1;

      if (O.Cb /= null) then
         Deleted(O.Cb, O, O.Data(Node).Val);
      end if;
   end Delete_Node;


   ------------------------------------------------------------------------
   function Member_Count (O   : in Object'Class;
                          Val : in Contained_Type)
                          return Natural is
      Retval : Natural := 0;
      Curr   : Node_Ref;
   begin
      Curr := Find_Val(O, Val);
      while (Curr /= Null_Node) loop
         Retval := Retval + 1;
         Curr := Find_Val_Again(O, Curr);
      end loop;

      return Retval;
   end Member_Count;


   ------------------------------------------------------------------------
   procedure Local_Add (O          : in out Object'Class;
                        Val        : in Contained_Type;
                        Added_Node : out Node_Ref) is
      Up   : Node_Ref;
      Node : Node_Ref;
   begin
      -- Add it at the end of the heap.
      Add_New_Last(O, Val);

      -- Now move it up in the heap while it is greater than the ones above
      -- it.
      Node := O.Tail;
      Up := Parent(O, Node);
      while ((Up /= Null_Node)
             and then (O.Data(Node).Val > O.Data(Up).Val))
      loop
         Swap(O, Node, Up);
         Up := Parent(O, Node);
      end loop;

      O.Update := O.Update + 1;

      if (O.Cb /= null) then
         Added(O.Cb, O, O.Data(Node).Val);
      end if;

      Added_Node := Node;
   end Local_Add;


   ------------------------------------------------------------------------
   -- This is a controlled type, so we have those methods to handle.


   ------------------------------------------------------------------------
   procedure Initialize (O : in out Object) is
   begin
      null;
   end Initialize;


   ------------------------------------------------------------------------
   procedure Adjust (O : in out Object) is
   begin
      -- Copy the data and call the Copied function for the new values, if
      -- the callback is set.
      O.Data := new Heap_Array'(O.Data.all);
      if (O.Cb /= null) then
         for I in 1 .. O.Count loop
            Copied(O.Cb, O, O.Data(I).Val);
         end loop;
      end if;
   end Adjust;


   ------------------------------------------------------------------------
   procedure Finalize (O : in out Object) is
   begin
      -- Call the deleted function for all elements of the heap, then free
      -- the allocated data.
      if (O.Cb /= null) then
         for I in 1 .. O.Count loop
            Deleted(O.Cb, O, O.Data(I).Val);
         end loop;
      end if;
      Free_Heap_Array(O.Data);

      O.Is_Free := True;
   end Finalize;


   ------------------------------------------------------------------------
   procedure Finalize (Iter : in out Iterator) is
   begin
      Iter.Is_Free := True;
   end Finalize;


   ------------------------------------------------------------------------
   -- The functions that follow are defined as abstract in previous
   -- packages.  See those packages for descriptions of what these
   -- methods do.


   ------------------------------------------------------------------------
   procedure Add (O   : in out Object;
                  Val : in Contained_Type) is
      Node : Node_Ref;
   begin
      Check_Object(O);

      Local_Add(O, Val, Node);
   end Add;


   ------------------------------------------------------------------------
   procedure Delete (O   : in out Object;
                     Val : in Contained_Type) is
      To_Delete : Node_Ref;
   begin
      Check_Object(O);

      To_Delete := Find_Val(O, Val);
      if (To_Delete = Null_Node) then
         raise Item_Not_Found;
      else
         Delete_Node(O, To_Delete);
      end if;
   end Delete;


   ------------------------------------------------------------------------
   function Value_Exists (O   : in Object;
                          Val : in Contained_Type)
                          return Boolean is
   begin
      Check_Object(O);

      return (Find_Val(O, Val) /= Null_Node);
   end Value_Exists;


   ------------------------------------------------------------------------
   function Member_Count (O : in Object)
                          return Natural is
   begin
      Check_Object(O);

      return O.Count;
   end Member_Count;


   ------------------------------------------------------------------------
   function "=" (O1, O2 : in Object) return Boolean is
      Curr1  : Node_Ref;
   begin
      Check_Object(O1);
      Check_Object(O2);

      if (O1.Count /= O2.Count) then
         return False;
      else
         -- This function will return True if when we remove each item
         -- from the top of the heap we will get the same sequence of
         -- items.  The actual tree structure may not be exactly the
         -- same, but that shouldn't matter.

         -- This works by verifying that for each member of O1, O2 has the
         -- same number of members of that value.  This is quite slow, but
         -- accurate.

         Curr1 := O1.Head;
         while (Curr1 /= Null_Node) loop
            if (Member_Count(O1, O1.Data(Curr1).Val)
                /= Member_Count(O2, O1.Data(Curr1).Val))
            then
               return False;
            end if;

            Curr1 := Right_Neighbor(O1, Curr1);
         end loop;

         return True;
      end if;
   end "=";


   ------------------------------------------------------------------------
   procedure Verify_Integrity (O : in Object) is
      Curr  : Node_Ref;
      Up    : Node_Ref;
      Left  : Node_Ref;
      Right : Node_Ref;
      Count : Natural := 0;
      Depth : Natural := 1;

      Max_Depth : Natural := 0;
      Tail      : Node_Ref;
   begin
      Check_Object(O);

      -- Do an in-order traversal of the tree, checking each node as we
      -- come to it.
      Curr := O.Head;

      if (Curr = Null_Node) then
         if (O.Tail /= Null_Node) then
            raise Internal_Heap_Error;
         end if;
      else
         loop
            -- Count the members.
            Count := Count + 1;

            -- Make sure that the children point back up to their parents.
            Left := Left_Child(O, Curr);
            Right := Right_Child(O, Curr);
            if (Left /= Null_Node) then
               if (Parent(O, Left) /= Curr) then
                  raise Internal_Heap_Error;
               end if;
               if (O.Data(Left).Val > O.Data(Curr).Val) then
                  raise Internal_Heap_Error;
               end if;
            end if;

            if (Right /= Null_Node) then
               if (Parent(O, Right) /= Curr) then
                  raise Internal_Heap_Error;
               end if;
               if (O.Data(Right).Val > O.Data(Curr).Val) then
                  raise Internal_Heap_Error;
               end if;
            end if;

            if (Left /= Null_Node) then
               Curr := Left;
               Depth := Depth + 1;
            elsif (Right /= Null_Node) then
               Curr := Right;
               Depth := Depth + 1;
            else
               -- We are at a leaf.  First check the depth, then move to
               -- the next item in the tree.

               -- The current depth may either be the max depth (the last
               -- one at that depth should be the tail) or one less than
               -- the max depth.
               if (Max_Depth = 0) then
                  Tail := Curr;
                  Max_Depth := Depth;
               elsif (Depth = Max_Depth) then
                  Tail := Curr;
               elsif (Max_Depth /= (Depth + 1)) then
                     raise Internal_Heap_Error;
               end if;

               Up := Parent(O, Curr);
               while (Up /= Null_Node) loop
                  Right := Right_Child(O, Up);
                  Left := Left_Child(O, Up);
                  if (Right = Curr) then
                     Curr := Up;
                     Up := Parent(O, Curr);
                     Depth := Depth - 1;
                  elsif (Left = Curr) then
                     if (Right = Null_Node) then
                        Curr := Up;
                        Up := Parent(O, Curr);
                        Depth := Depth - 1;
                     else
                        Curr := Right;
                        exit;
                     end if;
                  else
                     raise Internal_Heap_Error;
                  end if;
               end loop;

               exit when (Up = Null_Node);
            end if;
         end loop;

         if (Tail /= O.Tail) then
            raise Internal_Heap_Error;
         end if;
      end if;

      if (Count /= O.Count) then
         raise Internal_Heap_Error;
      end if;
   end Verify_Integrity;


   ------------------------------------------------------------------------
   function Copy (O : in Object) return Asgc.Object_Class is
      Retval : Object_Ptr;
   begin
      Retval := new Object(Initial_Size => O.Initial_Size,
                           Increment    => O.Increment);
      -- Let Adjust() take care of the data copy.
      Retval.all := O;

      return Asgc.Object_Class(Retval);
   end Copy;


   ------------------------------------------------------------------------
   function Get_Head (O : in Object)
                      return Contained_Type is
   begin
      Check_Object(O);

      if (O.Head = Null_Node) then
         raise Item_Not_Found;
      else
         return O.Data(O.Head).Val;
      end if;
   end Get_Head;


   ------------------------------------------------------------------------
   procedure Remove_Head (O   : in out Object;
                          Val : out Contained_Type) is
   begin
      Check_Object(O);

      if (O.Head = Null_Node) then
         raise Item_Not_Found;
      else
         Val := O.Data(O.Head).Val;
         Delete_Node(O, O.Head);
      end if;
   end Remove_Head;


   ------------------------------------------------------------------------
   function New_Iterator (O : access Object) return Asgc.Iterator_Class is
      Retval : Iterator_Ptr;
   begin
      Check_Object(O.all);

      Retval := new Iterator;
      Retval.Robj := Object_Class(O);

      return Asgc.Iterator_Class(Retval);
   end New_Iterator;


   ------------------------------------------------------------------------
   function New_Iterator (O : in Object_class) return Iterator is
      Retval : Iterator;
   begin
      Retval.Robj := O;

      return Retval;
   end New_Iterator;


   ------------------------------------------------------------------------
   procedure Free (Iter : access Iterator) is
      To_Free : Iterator_Ptr := Iterator_Ptr(Iter);
   begin
      if (Iter.Is_Free) then
         raise Iterator_Free;
      end if;

      Free_Iterator(To_Free);
   end Free;


   ------------------------------------------------------------------------
   procedure Set_Container (Iter : in out Iterator;
                            O    : in Asgc.Object_Class) is
   begin
      Check_Object(Object'Class(O.all));

      Iter.Robj := Object_Class(O);
      Iter.Update := Invalid_Update;
   end Set_Container;


   ------------------------------------------------------------------------
   procedure Add (Iter : in out Iterator;
                  Val  : in Contained_Type) is
   begin
      Check_Iterator_No_Pos(Iter);

      Local_Add(Iter.Robj.all, Val, Iter.Pos);
      Iter.Update := Iter.Robj.Update;
   end Add;

   ------------------------------------------------------------------------
   procedure First (Iter : in out Iterator; Is_End : out End_Marker) is
   begin
      Check_Iterator_No_Pos(Iter);

      Iter.Pos := Iter.Robj.Head;
      Iter.Update := Iter.Robj.Update;
      if (Iter.Pos = Null_Node) then
         Is_End := Past_End;
      else
         Is_End := Not_Past_End;
      end if;
   end First;


   ------------------------------------------------------------------------
   procedure Next (Iter : in out Iterator; Is_End : out End_Marker) is
      New_Pos : Node_Ref;
   begin
      Check_Iterator(Iter);

      New_Pos := Right_Neighbor(Iter.Robj.all, Iter.Pos);
      if (New_Pos = Null_Node) then
         Is_End := Past_End;
      else
         Iter.Pos := New_Pos;
         Is_End := Not_Past_End;
      end if;
   end Next;


   ------------------------------------------------------------------------
   procedure Delete (Iter : in out Iterator; Is_End : out End_Marker) is
   begin
      Check_Iterator(Iter);

      -- We don't move the actual nodes around in the heap, only the
      -- values, so the position should still be valid after a delete.
      if (Iter.Pos = Iter.Robj.Tail) then
         Delete_Node(Iter.Robj.all, Iter.Pos);
         Is_End := Past_End;
      else
         Delete_Node(Iter.Robj.all, Iter.Pos);
         Is_End := Not_Past_End;
         Iter.Update := Iter.Robj.Update;
      end if;
   end Delete;


   ------------------------------------------------------------------------
   function Is_Same (Iter1, Iter2 : in Iterator) return Boolean is
   begin
      Check_Iterator(Iter1);
      Check_Iterator(Iter2);

      if (Iter1.Robj /= Iter2.Robj) then
         raise Iterator_Mismatch;
      end if;

      return (Iter1.Pos = Iter2.Pos);
   end Is_Same;


   ------------------------------------------------------------------------
   function Get (Iter : in Iterator) return Contained_Type is
   begin
      Check_Iterator(Iter);

      return Iter.Robj.all.Data(Iter.Pos).Val;
   end Get;


   ------------------------------------------------------------------------
   procedure Get_Incr (Iter   : in out Iterator;
                       Val    : out Contained_Type;
                       Is_End : out End_Marker) is
   begin
      Check_Iterator(Iter);

      Val := Iter.Robj.all.Data(Iter.Pos).Val;
      Next(Iter, Is_End);
   end Get_Incr;


   ------------------------------------------------------------------------
   function "=" (Iter1, Iter2 : in Iterator) return Boolean is
   begin
      Check_Iterator(Iter1);
      Check_Iterator(Iter2);

      return (Iter1.Robj.all.Data(Iter1.Pos).Val
              = Iter2.Robj.all.Data(Iter2.Pos).Val);
   end "=";


   ------------------------------------------------------------------------
   function "=" (Iter : in Iterator; Val : in Contained_Type) return Boolean is
   begin
      Check_Iterator(Iter);

      return (Iter.Robj.all.Data(Iter.Pos).Val = Val);
   end "=";


   ------------------------------------------------------------------------
   function "=" (Val : in Contained_Type; Iter : in Iterator) return Boolean is
   begin
      Check_Iterator(Iter);

      return (Val = Iter.Robj.all.Data(Iter.Pos).Val);
   end "=";


   ------------------------------------------------------------------------
   procedure Search (Iter  : in out Iterator;
                     Val   : in Contained_Type;
                     Found : out Boolean) is
      New_Pos : Node_Ref;
   begin
      Check_Iterator_No_Pos(Iter);

      New_Pos := Find_Val(Iter.Robj.all, Val);
      if (New_Pos = Null_Node) then
         Found := False;
      else
         Found := True;
         Iter.Pos := New_Pos;
         Iter.Update := Iter.Robj.Update;
      end if;
   end Search;

end Asgc.Heap.Expandable_Managed;