-- PragmAda Reusable Component (PragmARC)
-- Copyright (C) 2021 by PragmAda Software Engineering. All rights reserved.
-- Released under the terms of the BSD 3-Clause license; see https://opensource.org/licenses
-- **************************************************************************
--
-- Generic unbounded-bag ADT for sequential use only.
--
-- History:
-- 2021 May 01 J. Carter V2.3--Adhere to coding standard
-- 2021 Jan 01 J. Carter V2.2--Removed limited and Assign
-- 2020 Dec 01 J. Carter V2.1--Changed elaboration pragmas to aspects
-- 2020 Nov 01 J. Carter V2.0--Initial Ada-12 version
----------------------------------------------------------------------------
-- 2020 Feb 15 J. Carter V1.2--Make more Object.Operation friendly
-- 2018 Aug 01 J. Carter V1.1--Make Size O(1)
-- 2013 Mar 01 J. Carter V1.0--Initial Ada-07 version
---------------------------------------------------------------------------------------------------
-- 2002 Oct 01 J. Carter V1.3--Added Context to Iterate; use mode out to allow scalars
-- 2002 May 01 J. Carter V1.2--Added Assign
-- 2001 May 01 J. Carter V1.1--Improved time complexity of Empty
-- 2000 May 01 J. Carter V1.0--Initial release
--
pragma Assertion_Policy (Check);
pragma Unsuppress (All_Checks);
private with Ada.Containers.Doubly_Linked_Lists;
generic -- PragmARC.Data_Structures.Bags.Unbounded.Unprotected
type Element is private;
with function "=" (Left : in Element; Right : in Element) return Boolean is <>;
-- Returns True if Left and Right are equal; returns False otherwise.
-- "=" is often implemented to compare only part of the elements (the Key).
package PragmARC.Data_Structures.Bags.Unbounded.Unprotected with Preelaborate is
type Handle is tagged private; -- Intial value: Empty
procedure Clear (Bag : in out Handle) with
Post => Bag.Empty;
-- Makes Bag empty. All bags are initially empty.
--
-- Time: O(N)
procedure Add (Into : in out Handle; Item : in Element) with
Post => not Into.Empty;
-- Adds Item to Into.
-- Raises Storage_Exhausted if we cannot obtain memory to store Item in Into.
-- Into is unchanged if Storage_Exhausted is raised
-- Time: O(1)
procedure Delete (From : in out Handle; Item : in Element);
-- with Post => From'Old.Size >= From.Size; -- 'Old cannot be used with a limited type
-- If From contains an Element X such that X = Item, deletes X from From;
-- otherwise, has no effect.
-- If From contains more than one such Element, deletes one of these Elements.
--
-- Time: O(N)
procedure Update (Bag : in out Handle; Item : in Element);
-- If Bag contains an Element X such that X = Item, performs X := Item;
-- otherwise, has no effect.
-- If Bag contains more than one such Element, updates one of these Elements.
--
-- Time: O(N)
type Find_Result (Found : Boolean := False) is record
case Found is
when False =>
null;
when True =>
Item : Element;
end case;
end record;
function Find (Bag : in Handle; Key : in Element) return Find_Result;
-- If Bag contains an Element X such that X = Key, returns (Found => True, Item => X);
-- otherwise, returns (Found => False).
-- If Bag contains more than one such Element, returns one of these Elements
-- as the Item component of the result.
--
-- Time: O(N)
function Empty (Bag : in Handle) return Boolean;
-- Returns True if Bag contains no elements; returns False otherwise
--
-- Time: O(1)
function Size (Bag : in Handle) return Natural;
-- Returns the number of elements stored in Bag
--
-- Time: O(1)
generic -- Iterate
with procedure Action (Item : in out Element);
procedure Iterate (Over : in out Handle);
-- Applies Action to each Element in Over in some unspecified order, until every Element in Over has been processed
private -- PragmARC.Bag_Unbounded_Unprotected
package Implementation is new Ada.Containers.Doubly_Linked_Lists (Element_Type => Element);
type Handle is tagged record
List : Implementation.List;
end record;
end PragmARC.Data_Structures.Bags.Unbounded.Unprotected;