From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,2eac5e4279bf777c,start
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2001-07-15 17:37:54 PST
Path: 
 archiver1.google.com!newsfeed.google.com!newsfeed.stanford.edu!nntp.cs.ubc.ca!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!howland.erols.net!news-out.worldnet.att.net.MISMATCH!wn3feed!worldnet.att.net!135.173.83.71!wnfilter1!worldnet-localpost!bgtnsc06-news.ops.worldnet.att.net.POSTED!not-for-mail
Message-ID: <3B5237EC.D54299A7@worldnet.att.net>
From: James Rogers <jimmaureenrogers@worldnet.att.net>
X-Mailer: Mozilla 4.76 [en] (Win98; U)
X-Accept-Language: en
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: C++ STL Components and Ada
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Date: Mon, 16 Jul 2001 00:37:53 GMT
NNTP-Posting-Host: 12.86.34.70
X-Complaints-To: abuse@worldnet.att.net
X-Trace: bgtnsc06-news.ops.worldnet.att.net 995243873 12.86.34.70 (Mon,
 16 Jul 2001 00:37:53 GMT)
NNTP-Posting-Date: Mon, 16 Jul 2001 00:37:53 GMT
Organization: AT&T Worldnet
Xref: archiver1.google.com comp.lang.ada:9977
Date: 2001-07-16T00:37:53+00:00
List-Id: <comp.lang.ada>

Occasionally I read questions from Ada newbies about the presence of
Ada equivalents to the C++ STL. 

After many years of reading about and hearing from C++ programmers that
the STL is the best thing since the invention of fire, I decided to
look into exactly what the STL is. Ok, I took a little longer than 
others :-).

I started by looking at the definition of the C++ Vector class, which
has an analog in Java. I have come to the conclusion that the Vector
class is one of the most used components from the STL. I am aware that
C++ needed some standard kind of "safe" array. The array type
inherited from C certainly does not fit this description. I found the
Vector class to be very flexible, if not overly safe. It does prevent
reading beyond the end of the Vector object. It does not prevent
writing beyond the end of the Vector object because the Vector is
an extensible structure.

In the best case a Vector is about as efficient as an Ada array.
In the worst case it is far less efficient. I cannot imagine using
a Vector in an embedded application with limited memory. I do think
that most C++ code, like most Java code, is not written in the
embedded domain. Therefore, the inefficiencies may not often be
visible.

I have learned a lot about the Vector class by creating an Ada
implementation. The implementation works. It is not particularly
pretty. I suspect it can be improved.

The following code is my generic Vector in Ada.

-- File: Tagged_Vector.ads
--
-- Generic vector for tagged types following C++ rules

generic
	type Element_Type is tagged private;
	with function ">=" (Left, Right : Element_Type) return Boolean;
package Tagged_Vector is
   type Group is array(Positive range <>) of Element_Type;
	type Vector is private;
	function First(Item : in Vector) return Natural;
	function Last(Item : in Vector) return Natural;
	function Size(Item : in Vector) return Natural;
	function Capacity(Item : in Vector) return Natural;
	function Is_Empty(Item : in Vector) return Boolean;
	function Element(Num : in Positive; 
	                 Item : in Vector) return Element_Type;
	procedure Reserve(Num_Items : in Positive;
	                  Item : in out Vector);
	function Front(Item : in Vector) return Element_Type;
	function Back(Item : in Vector) return Element_Type;
	procedure Push_Back(Value : in Element_Type;
	                    Onto  : in out Vector);
	procedure Pop_Back(Value : out Element_Type;
	                   From  : in out Vector);
	procedure Insert(Value  : in Element_Type;
	                 Before : in Positive;
			Onto   : in out Vector);
	procedure Insert(Value      : in Element_Type;
	                 Num_Copies : in Positive;
			Before     : in Positive;
			Onto       : in out Vector);
	procedure Insert(The_Group : in Group;
	                 Before    : in Positive;
			 Onto      : in out Vector);
	procedure Erase(Index : in Positive;
	                From  : in out Vector);
	procedure Erase(First : in Positive;
	                Last  : in Positive;
			From  : in out Vector);
	procedure Resize(Num  : in Positive;
	                 Item : in out Vector);
	function "="(Left, Right : Vector) return Boolean;
	function "<"(Left, Right : Vector) return Boolean;
	
	Vector_Empty_Error : Exception;
private
   type Group_Access is access all Group;
   type Vector is record
	Buffer : Group_Access := new Group(1..20);
	Num_Elements : Natural := 0;
   end record;
end Tagged_Vector; 


-- File : Tagged_Vector.adb
   with Ada.Unchecked_Deallocation;

   package body Tagged_Vector is
      procedure Free is new Ada.Unchecked_Deallocation(
                        Object => Group,
                        Name =>Group_Access);
   
      function First(Item : in Vector) return Natural is
      begin
         if Item.Num_Elements > 0 then
            return 1;
         else
            return 0;
         end if;
      end First;
   
      function Last(Item : in Vector) return Natural is
      begin
         return Item.Num_Elements;
      end Last;
   
      function Size(Item : in Vector) return Natural is
      begin
         return Item.Num_Elements;
      end Size;
   
      function Capacity(Item : in Vector) return Natural is
      begin
         if Item.Buffer /= null then
            return Item.Buffer.all'Last;
         else
            return 0;
         end if;
      end Capacity;
   
      function Is_Empty(Item : in Vector) return Boolean is
      begin
         return Item.Num_Elements = 0;
      end Is_Empty;
   
      function Element(Num : in Positive;
                       Item : in Vector) return Element_Type is
      begin
         if Num <= Item.Num_Elements then
            return Item.Buffer.all(Num);
         else
            return Item.Buffer.all(Item.Num_Elements);
         end if;
      end Element;
   
      procedure Reserve(Num_Items : in Positive;
                        Item : in out Vector) is
         Temp : Group_Access;
      begin
         if Num_Items > Item.Buffer.all'Last then
            Temp := new Group(1..(2 * Num_Items));
         -- Copy Elements to new buffer
            Temp.all(1..Item.Num_Elements) :=
                    Item.Buffer.all(1..Item.Num_Elements);
            Free(Item.Buffer);
         end if;
         Item.Buffer := Temp;
      end Reserve;
   
      function Front(Item : in Vector) return Element_Type is
      begin
         if Item.Num_Elements = 0 then
            raise Vector_Empty_Error;
         end if;
         return Item.Buffer.all(1);
      end Front;
   
      function Back(Item : in Vector) return Element_Type is
      begin
         if Item.Num_Elements = 0 then
            raise Vector_Empty_Error;
         end if;
         return Item.Buffer.all(Item.Num_Elements);
      end Back;
   
      procedure Push_Back(Value : in Element_Type;
                          Onto  : in out Vector) is
         Temp : Group_Access;
      begin
         if Onto.Num_Elements = Onto.Buffer.All'Last then
            Temp := new Group(1..(2 * Onto.Num_Elements));
            Temp.all(1..Onto.Num_Elements) :=
                   Onto.Buffer.all(1..Onto.Num_Elements);
            Free(Onto.Buffer);
            Onto.Buffer := Temp;
         end if;
         Onto.Num_Elements := Onto.Num_Elements + 1;
         Onto.Buffer.all(Onto.Num_Elements) := Value;
      end Push_Back;
   
      procedure Pop_Back(Value : out Element_Type;
                         From  : in out Vector) is
      begin
         if From.Num_Elements = 0 then
            raise Vector_Empty_Error;
         end if;
         Value := From.Buffer.all(From.Num_Elements);
         From.Num_Elements := From.Num_Elements - 1;
      end Pop_Back;
   
      procedure Insert(Value : in Element_Type;
                       Before : in Positive;
                       Onto   : in out Vector) is
         Temp : Group_Access;
         new_Pos : Positive;
      begin
         if Onto.Num_Elements = Onto.Buffer.All'Last then
            Temp := new Group(1..(2 * Onto.Num_Elements));
            Temp.all(1..Onto.Num_Elements) := 
                Onto.Buffer.all(1..Onto.Num_elements);
            Free(Onto.Buffer);
            Onto.Buffer := Temp;
         end if;
         if Before <= Onto.Num_Elements then
            for num in reverse Before..Onto.Num_Elements loop
               Onto.Buffer.all(Num + 1) := Onto.Buffer.All(Num);
            end loop;
            New_Pos := Before;
         else
            New_Pos := Onto.Num_Elements + 1;
         end if;
         Onto.Buffer.All(New_Pos) := Value;
         Onto.Num_Elements := Onto.Num_Elements + 1;
      end Insert;
   
      procedure Insert(Value      : in Element_Type;
                       Num_Copies : in Positive;
                       Before     : in Positive;
                       Onto       : in out Vector) is
      begin
         for copy in 1..Num_Copies loop
            Insert(Value => Value, Before => Before, Onto => Onto);
         end loop;
      end Insert;
   
      procedure Insert(The_Group : in Group;
                       Before    : in Positive;
                       Onto      : in out Vector) is
      begin
         for Index in reverse The_Group'Range loop
            Insert(Value  => The_Group(Index),
                   Before => Before,
                   Onto   => Onto);
         end loop;
      end Insert;
   
      procedure Erase(Index : in Positive;
                      From  : in out Vector) is
      begin
         if Index <= From.Num_Elements then
            for num in Index + 1..From.Num_Elements loop
               From.Buffer.all(Num - 1) := From.Buffer.all(Num);
            end loop;
            From.Num_Elements := From.Num_Elements - 1;
         end if;
      end Erase;
   
      procedure Erase(First : in Positive;
                      Last  : in Positive;
                      From  : in out Vector) is
         Final : Positive;
      begin
         if Last >= First then
            if Last > From.Num_Elements then
               Final := From.Num_Elements;
            else
               Final := Last;
            end if;
            for num in First..Final loop
               Erase(Index => First, From => From);
            end loop;
         end if;
      end Erase;
   
      procedure Resize(Num : in Positive;
                       Item : in out Vector) is
         Temp : Group_Access;
      begin
         if Num >= (2 * Item.Num_Elements) then
            Temp := new Group(1..Num);
            for index in 1..Item.Num_Elements loop
               Temp.all(index) := Item.Buffer.all(Index);
            end loop;
            Free(Item.Buffer);
            Item.Buffer := Temp;
         end if;
      end Resize;
   
      function "="(Left, Right : in Vector) return Boolean is
         Result : Boolean;
      begin
         if Left.Num_Elements = Right.Num_Elements then
            Result := True;
            for index in 1..Left.Num_Elements loop
               if Left.Buffer.all(index) /= Right.Buffer.all(Index) then
                  Result := False;
               end if;
               exit when Result = False;
            end loop;
         else
            Result := False;
         end if;
         return Result;
      end "=";
   
      function "<"(Left, Right : in Vector) return Boolean is
         Result : Boolean;
      begin
         if Left.Num_Elements <= Right.Num_Elements then
            Result := True;
            for index in 1..Left.Num_Elements loop
               if Left.Buffer.all(Index) >= Right.Buffer.all(Index) then
                  Result := False;
               end if;
               exit when Result = False;
            end loop;
         else
            Result := False;
         end if;
         return Result;
      end "<";
   end Tagged_Vector;

Jim Rogers
Coloardo Springs, Colorado USA