File : agpl-dynamic_vector.ads


------------------------------------------------------------------------------

--                         ADAGIO - ADALID - AENEA.                         --

--                                                                          --

--                            Copyright (C) 2003                            --

--                                 A. Mosteo.                               --

--                                                                          --

--  Authors: A. Mosteo. (adagio@mosteo.com)                                 --

--                                                                          --

--  If you have any questions in regard to this software, please address    --

--  them to the above email.                                                --

--                                                                          --

--  This program 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 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.  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.          --

--                                                                          --

--  You are not allowed to use any part of this code to develop a program   --

--  whose output would be used to harass or prosecute other users of the    --

--  networks Adagio connects with. All data collected with Adagio or a tool --

--  containing Adagio code about other network users must remain            --

--  confidential and cannot be made public by any mean, nor be used to      --

--  harass or legally prosecute these users.                                --

------------------------------------------------------------------------------

--  $Id: agpl-dynamic_vector.ads,v 1.3 2004/02/03 22:52:08 Jano Exp $


-- Package for unbounded vectors, integer-indexed


with Ada.Finalization;  use Ada;
with Ada.Streams;

generic
   type Item_type is private;
   Initial_size : Natural := 16;
   Grow_factor  : Float   := 1.5;
package Agpl.Dynamic_vector is

   pragma Elaborate_body;

   Item_not_found : Exception;

   type Item_array is array (integer range <>) of Item_type;
   type Item_array_access is access all Item_array;
   
   -- That's visible so we can access the internal array an mimic the usual

   -- arrays semantics except for 'Last attribute: Last function must be used.

   -- First can be anything except Integer'First

   -- Controlling guarantees that no leaks occur, and that copies are deep,

   --    and that vector.all is valid from the very first moment.

   type Proto_object (First : Integer) is 
      new Finalization.Controlled with record
      Vector : Item_array_access;
   end record;

   ------------

   -- Object --

   ------------


   -- First is the index for the first element.

   type Object (First : Integer) is new Proto_object with private;

   -- First "attribute"

   -- O (1)

   function First (this : in Object) return integer;
   pragma Inline (First);

   -- Last "attribute"

   -- O (1)

   function Last (this : in Object) return integer;
   pragma Inline (Last);

   -- Length "attribute"

   -- O (1)

   function Length (this : in Object) return integer;
   pragma Inline (Length);

   -- Adds an item to the end. Will grow the vector if necessary.

   -- O (1) or O (n) if growing occurs

   procedure Append (this : in out Object; Item : in Item_type);

   -- Adds an item before a certain position (that could not exist if we

   --    want insertion at Last + 1, i.e., the end. Will grow the vector

   --    if necessary.

   -- O (n)

   procedure Insert (
      this : in out Object; Item : in Item_type; Pos : in Integer);

   -- Grows the vector according to the Grow_factor. Should not be necessary

   --    to be used. It's used internally.

   -- O (n)

   type Sides is (Start, Ending);
   procedure Grow (this : in out Object; Empty_side : in Sides := Ending);

   -- Deletes an item at given pos

   -- O (n)

   procedure Delete (this : in out Object; Pos : in Integer);

   -- Delete all ocurrences of an item

   -- O (n^2)

   procedure Delete_item (this : in out Object; Item : in Item_type);

   -- Clean the vector, starts afresh

   -- O (1)

   procedure Reset (this : in out Object);
   procedure Clear (this : in out Object) renames Reset;

   -- Optimize memory usage, vector of only valid positions

   -- Right after optimize, 'Last is valid.

   -- O (n)

   procedure Optimize (this : in out Object);

   -- Member functions, not very useful if you access the vector directly:

   function Value (this : in Object) return Item_array;
   pragma Inline (Value);

   function Value (this : in Object; Pos : in Integer) return Item_type;
   pragma Inline (Value);

   -- Basic searching:

   -- Returns first found after given position

   -- Raise Item_not_found

   -- O (n)

   function Pos (
      this : in Object; 
      Item : in Item_type;
      Pos  : in Integer := Integer'First) return Integer;

   -- Overriden attributes

   procedure Write (
      Stream : access Ada.Streams.Root_stream_type'Class;
      Item   : in Object);
   for Object'Write use Write;

   procedure Read (
      Stream : access Ada.Streams.Root_stream_type'Class;
      Result : out Object);
   for Object'Read use Read;

private

   procedure Initialize (this : in out Proto_object);
   procedure Adjust     (this : in out Proto_object);
   procedure Finalize   (this : in out Proto_object);

   type Object (First : Integer) is new Proto_object(First) with record
      Last : Integer := First - 1;
   end record;

end Agpl.Dynamic_vector;