Index: src/natools-constant_indefinite_ordered_maps.adb ================================================================== --- src/natools-constant_indefinite_ordered_maps.adb +++ src/natools-constant_indefinite_ordered_maps.adb @@ -1,7 +1,7 @@ ------------------------------------------------------------------------------ --- Copyright (c) 2014, Natacha Porté -- +-- Copyright (c) 2014-2015, Natacha Porté -- -- -- -- Permission to use, copy, modify, and distribute this software for any -- -- purpose with or without fee is hereby granted, provided that the above -- -- copyright notice and this permission notice appear in all copies. -- -- -- @@ -652,10 +652,348 @@ Position.Index := I; Process.all (Position); end loop; end Reverse_Iterate; + + + ---------------------------------------- + -- Constant Map "Update" Constructors -- + ---------------------------------------- + + function Insert + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type; + Position : out Cursor; + Inserted : out Boolean) + return Constant_Map + is + Floor, Ceiling : Count_Type; + begin + if Source.Is_Empty then + declare + Backend : constant Backend_Refs.Data_Access := new Backend_Array' + (Ada.Finalization.Limited_Controlled with + Size => 1, + Nodes => (1 => (Key => new Key_Type'(Key), + Element => new Element_Type'(New_Item))), + Finalized => False); + Result : constant Constant_Map + := (Backend => Backend_Refs.Create (Backend)); + begin + Position := (Is_Empty => False, + Backend => Result.Backend, + Index => 1); + Inserted := True; + return Result; + end; + end if; + + Search (Source.Backend.Query.Data.Nodes, Key, Floor, Ceiling); + + if Floor = Ceiling then + Position := (Is_Empty => False, + Backend => Source.Backend, + Index => Floor); + Inserted := False; + return Source; + end if; + + declare + function Key_Factory (Index : Index_Type) return Key_Type; + function Element_Factory (Index : Index_Type) return Element_Type; + + Accessor : constant Backend_Refs.Accessor := Source.Backend.Query; + + function Key_Factory (Index : Index_Type) return Key_Type is + begin + if Index <= Floor then + return Accessor.Nodes (Index).Key.all; + elsif Index = Floor + 1 then + return Key; + else + return Accessor.Nodes (Index - 1).Key.all; + end if; + end Key_Factory; + + function Element_Factory (Index : Index_Type) return Element_Type is + begin + if Index <= Floor then + return Accessor.Nodes (Index).Element.all; + elsif Index = Floor + 1 then + return New_Item; + else + return Accessor.Nodes (Index - 1).Element.all; + end if; + end Element_Factory; + + Result : constant Constant_Map := (Backend => Make_Backend + (Accessor.Size + 1, Key_Factory'Access, Element_Factory'Access)); + begin + Position := (Is_Empty => False, + Backend => Result.Backend, + Index => Floor + 1); + Inserted := True; + return Result; + end; + end Insert; + + + function Insert + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type) + return Constant_Map + is + Position : Cursor; + Inserted : Boolean; + Result : constant Constant_Map + := Insert (Source, Key, New_Item, Position, Inserted); + begin + if not Inserted then + raise Constraint_Error with "Inserted key already in Constant_Map"; + end if; + + return Result; + end Insert; + + + function Include + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type) + return Constant_Map + is + Position : Cursor; + Inserted : Boolean; + Result : constant Constant_Map + := Insert (Source, Key, New_Item, Position, Inserted); + begin + if Inserted then + return Result; + end if; + + declare + function Key_Factory (Index : Index_Type) return Key_Type; + function Element_Factory (Index : Index_Type) return Element_Type; + + Accessor : constant Backend_Refs.Accessor := Source.Backend.Query; + + function Key_Factory (Index : Index_Type) return Key_Type is + begin + if Index = Position.Index then + return Key; + else + return Accessor.Nodes (Index).Key.all; + end if; + end Key_Factory; + + function Element_Factory (Index : Index_Type) return Element_Type is + begin + if Index = Position.Index then + return New_Item; + else + return Accessor.Nodes (Index).Element.all; + end if; + end Element_Factory; + + Result : constant Constant_Map := (Backend => Make_Backend + (Accessor.Size, Key_Factory'Access, Element_Factory'Access)); + begin + return Result; + end; + end Include; + + + function Replace + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type) + return Constant_Map + is + Floor, Ceiling : Count_Type; + begin + if Source.Is_Empty then + raise Constraint_Error with "Replace called on empty Constant_Map"; + end if; + + Search (Source.Backend.Query.Data.Nodes, Key, Floor, Ceiling); + + if Floor /= Ceiling then + raise Constraint_Error + with "Replace called with key not in Constant_Map"; + end if; + + return Replace_Element + (Source => Source, + Position => + (Is_Empty => False, + Backend => Source.Backend, + Index => Floor), + New_Item => New_Item); + end Replace; + + + function Replace_Element + (Source : in Constant_Map; + Position : in Cursor; + New_Item : in Element_Type) + return Constant_Map + is + use type Backend_Refs.Immutable_Reference; + begin + if Position.Is_Empty then + raise Constraint_Error + with "Constant_Map.Replace_Element called with empty cursor"; + end if; + + if Source.Backend /= Position.Backend then + raise Program_Error with "Constant_Map.Replace_Element " + & "with unrelated container and cursor"; + end if; + + declare + function Key_Factory (Index : Index_Type) return Key_Type; + function Element_Factory (Index : Index_Type) return Element_Type; + + Accessor : constant Backend_Refs.Accessor := Source.Backend.Query; + + function Key_Factory (Index : Index_Type) return Key_Type is + begin + return Accessor.Nodes (Index).Key.all; + end Key_Factory; + + function Element_Factory (Index : Index_Type) return Element_Type is + begin + if Index = Position.Index then + return New_Item; + else + return Accessor.Nodes (Index).Element.all; + end if; + end Element_Factory; + + Result : constant Constant_Map := (Backend => Make_Backend + (Accessor.Size, Key_Factory'Access, Element_Factory'Access)); + begin + return Result; + end; + end Replace_Element; + + + function Replace_Element + (Source : in Constant_Map; + Position : in Cursor; + New_Item : in Element_Type; + New_Position : out Cursor) + return Constant_Map + is + Result : constant Constant_Map + := Replace_Element (Source, Position, New_Item); + begin + New_Position := + (Is_Empty => False, + Backend => Result.Backend, + Index => Position.Index); + return Result; + end Replace_Element; + + + function Exclude + (Source : in Constant_Map; + Key : in Key_Type) + return Constant_Map + is + Floor, Ceiling : Count_Type; + begin + if Source.Is_Empty then + return Source; + end if; + + Search (Source.Backend.Query.Data.Nodes, Key, Floor, Ceiling); + + if Floor = Ceiling then + return Delete + (Source, + Cursor'(Is_Empty => False, + Backend => Source.Backend, + Index => Floor)); + else + return Source; + end if; + end Exclude; + + + function Delete + (Source : in Constant_Map; + Key : in Key_Type) + return Constant_Map + is + Floor, Ceiling : Count_Type; + begin + if Source.Is_Empty then + raise Constraint_Error with "Delete called on empty Constant_Map"; + end if; + + Search (Source.Backend.Query.Data.Nodes, Key, Floor, Ceiling); + + if Floor /= Ceiling then + raise Constraint_Error with "Deleted key not in Constant_Map"; + end if; + + return Delete (Source, + (Is_Empty => False, Backend => Source.Backend, Index => Floor)); + end Delete; + + + function Delete + (Source : in Constant_Map; + Position : in Cursor) + return Constant_Map + is + use type Backend_Refs.Immutable_Reference; + begin + if Position.Is_Empty then + raise Constraint_Error with "Constant_Map.Delete with empty cursor"; + end if; + + if Source.Backend /= Position.Backend then + raise Program_Error + with "Constant_Map.Delete with unrelated container and cursor"; + end if; + + declare + function Key_Factory (Index : Index_Type) return Key_Type; + function Element_Factory (Index : Index_Type) return Element_Type; + + Accessor : constant Backend_Refs.Accessor := Source.Backend.Query; + + function Key_Factory (Index : Index_Type) return Key_Type is + begin + if Index < Position.Index then + return Accessor.Nodes (Index).Key.all; + else + return Accessor.Nodes (Index + 1).Key.all; + end if; + end Key_Factory; + + function Element_Factory (Index : Index_Type) return Element_Type is + begin + if Index < Position.Index then + return Accessor.Nodes (Index).Element.all; + else + return Accessor.Nodes (Index + 1).Element.all; + end if; + end Element_Factory; + + Result : constant Constant_Map := (Backend => Make_Backend + (Accessor.Size - 1, Key_Factory'Access, Element_Factory'Access)); + begin + return Result; + end; + end Delete; + ------------------------------ -- Updatable Map Operations -- ------------------------------ Index: src/natools-constant_indefinite_ordered_maps.ads ================================================================== --- src/natools-constant_indefinite_ordered_maps.ads +++ src/natools-constant_indefinite_ordered_maps.ads @@ -25,24 +25,25 @@ -- Cursors also hold a reference, which is used to identify the parent map, -- -- so after an assignment or a call to Clear or Move, the link between the -- -- map object and the cursor is broken, but the cursor is still usable and -- -- behaves as the original version of the maps. -- -- -- --- There are four types defined here, depending on their restrictions and -- +-- There are two types defined here, depending on their restrictions and -- -- safety against concurrent accesses: -- -- * Constant_Map cannot be changed in any way, but is completely -- -- task-safe (unless some referential magic is performed, like -- -- tampering checks in standard containers) -- -- * Updatable_Map allows read-write operations on stored elements, but -- -- it is up to the client to ensure there operations are task-safe, -- -- e.g. by using an atomic or protected Element_Type. -- --- * Mutable_Map allows all standard operations, but creating a new -- --- mapping copied from the original. This is likely to be very -- --- inefficient, and it is up to the client to ensure task-safety of the -- --- underlying copy with regard to update operations. -- --- NOTE: Mutable_Map is not provided yet, since its usefullness is -- --- really not obvious. -- +-- -- +-- Insertion and deletion primitives are provided as function rather than -- +-- procedures, to emphasize that they actually create a new map with the -- +-- requested change. Since most of the map is blindly duplicated, they are -- +-- all in O(n) time, which makes them a quite inefficient way to build -- +-- maps. For a significant number of changes, it's probably better to go -- +-- through an unsafe map. -- -- -- -- All the subprograms here have the semantics of standard indefinite -- -- ordered maps (see ARM A.18.6), except for tampering, which becomes -- -- irrelevant. -- ------------------------------------------------------------------------------ @@ -189,10 +190,65 @@ function Constant_Reference (Container : aliased in Constant_Map; Key : in Key_Type) return Constant_Reference_Type; + + function Insert + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type; + Position : out Cursor; + Inserted : out Boolean) + return Constant_Map; + + function Insert + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type) + return Constant_Map; + + function Include + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type) + return Constant_Map; + + function Replace + (Source : in Constant_Map; + Key : in Key_Type; + New_Item : in Element_Type) + return Constant_Map; + + function Replace_Element + (Source : in Constant_Map; + Position : in Cursor; + New_Item : in Element_Type) + return Constant_Map; + + function Replace_Element + (Source : in Constant_Map; + Position : in Cursor; + New_Item : in Element_Type; + New_Position : out Cursor) + return Constant_Map; + + function Exclude + (Source : in Constant_Map; + Key : in Key_Type) + return Constant_Map; + + function Delete + (Source : in Constant_Map; + Key : in Key_Type) + return Constant_Map; + + function Delete + (Source : in Constant_Map; + Position : in Cursor) + return Constant_Map; + type Updatable_Map is new Constant_Map with private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate,