Containers: Maps, Sets, Holders & Trees

Use Hashed_Maps and Ordered_Maps (Insert, Include, Replace, Contains, Element, indexing, cursor iteration with Key/Element), Hashed_Sets and Ordered_Sets with union/intersection/difference, Indefinite variants with Ada.Strings.Hash, Indefinite_Holders, Multiway_Trees and synchronized queues.

Maps associate keys with elements; sets store unique elements. Ada provides hashed versions (fast average lookup, unordered iteration; you supply a Hash function) and ordered versions (balanced trees, iteration in key order; you supply "<"). The same Indefinite and Bounded variants exist as for vectors.

Maps

'package Word_Counts is new Ada.Containers.Indefinite_Hashed_Maps (Key_Type => String, Element_Type => Natural, Hash => Ada.Strings.Hash, Equivalent_Keys => "=");' — Indefinite because String keys vary in length. Insert adds a new key (raising Constraint_Error if it exists); Include inserts or replaces; Replace requires the key to exist; Contains, Find (cursor), Element (Key), Delete, Exclude. M (Key) reads or updates an element through indexing. 'for C in M.Iterate loop ... Key (C) ... Element (C)' visits all pairs; for Ordered_Maps the order is sorted by key, and Floor/Ceiling find nearest keys.

• Hashed_Maps (Key, Element, Hash, Equivalent_Keys); Ordered_Maps (Key, Element ["<"]). • Insert (fails if present) / Include (upsert) / Replace (must exist). • M (Key) indexing; iterate cursors for Key + Element. • Ada.Strings.Hash for String keys.

Sets

Hashed_Sets and Ordered_Sets store unique elements: Insert, Include, Delete, Contains, and set algebra: Union / "or", Intersection / "and", Difference / "-", Symmetric_Difference / "xor", Is_Subset, Overlap. The operators are declared in the instance, so you need 'use type Int_Sets.Set;' (or a use clause) to write A or B — GNAT reports 'there is no applicable operator "Or"' otherwise. Ordered sets iterate in sorted order, which makes them handy for producing stable, sorted output.

• Union/or, Intersection/and, Difference/-, Symmetric_Difference/xor. • use type Pkg.Set to make the operators visible. • Ordered sets iterate sorted.

Holders, Trees and Queues

Indefinite_Holders stores a single indefinite value (e.g. a String or Shape'Class component in a record) without explicit pointers. Multiway_Trees implements general trees with cursors (Append_Child, Parent, Children iteration). Synchronized_Queue_Interfaces with Unbounded_Synchronized_Queues / Bounded_Priority_Queues provide task-safe queues for producer-consumer designs (see the concurrency lessons).

• Indefinite_Holders: one indefinite value, auto-managed. • Multiway_Trees: general trees. • Synchronized queues: task-safe.

Code Examples

Word counting with a hashed map, an ordered map printed in key order (Include replaced 'a'), set algebra with container aggregates, a holder storing strings of different lengths, and Insert of an existing key raising Constraint_Error. Output: Distinct words: 4 to => 2 be => 2 or => 1 not => 1 Contains "question"? FALSE Ordered map: a= 97 b= 80 c= 70 Contains key 'b'? TRUE A: 1 3 5 7 9 B: 3 6 9 A or B (union): 1 3 5 6 7 9 A and B (intersection): 3 9 A - B (difference): 1 5 7 B subset of A? FALSE Holder: any length Holder: a much longer string value Insert of an existing key raised Constraint_Error

M.Insert (Key, V); -- when the key may already exist M.Include (Key, V);

Insert raises Constraint_Error for duplicate keys; Include replaces.

package Counts is new Hashed_Maps (String, Natural, ...);

package Counts is new Indefinite_Hashed_Maps (String, Natural, Ada.Strings.Hash, "=");

String keys are indefinite.

Show (A or B); -- operator not visible use type Int_Sets.Set;... Show (A or B);

Set operators live in the instance; make them visible.

Which map iterates in sorted key order? A. Hashed_Maps B. Ordered_Maps C. Both D. Neither

What does Include do if the key exists? A. Raises Constraint_Error B. Replaces the element C. Ignores D. Adds a duplicate

Which function hashes String keys? A. Ada.Strings.Hash B. String'Hash C. Ada.Containers.Hash_String D. Hash is not needed

What is 'A - B' for sets? A. Union B. Intersection C. Difference (in A, not in B) D. Symmetric difference C. (verified: 1 5 7) Trace the maps/sets example.

Real output: Distinct words: 4 to => 2 be => 2 or => 1 not => 1 Contains "question"? FALSE Ordered map: a= 97 b= 80 c= 70 Contains key 'b'? TRUE A: 1 3 5 7 9 B: 3 6 9 A or B (union): 1 3 5 6 7 9 A and B (intersection): 3 9 A - B (difference): 1 5 7 B subset of A? FALSE Holder: any length Holder: a much longer string value Insert of an existing key raised Constraint_Error

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Hash;
with Ada.Containers.Indefinite_Hashed_Maps;
with Ada.Containers.Ordered_Maps;
with Ada.Containers.Ordered_Sets;
with Ada.Containers.Indefinite_Holders;

procedure L48_Maps_Sets is
   use Ada.Containers;

   --  Hash map from String keys to Natural counts
   package Word_Counts is new Indefinite_Hashed_Maps
     (Key_Type => String, Element_Type => Natural,
      Hash => Ada.Strings.Hash, Equivalent_Keys => "=");

   --  Ordered map: iteration in key order (a balanced tree)
   package Grades is new Ordered_Maps (Key_Type => Character, Element_Type => Natural);

   package Int_Sets is new Ordered_Sets (Integer);
   package String_Holders is new Indefinite_Holders (String);
   use type Int_Sets.Set;                      --  makes "or", "and", "-" on sets visible

   type Word_List is array (Positive range <>) of access constant String;
   W1 : aliased constant String := "to";
   W2 : aliased constant String := "be";
   W3 : aliased constant String := "or";
   W4 : aliased constant String := "not";
   Text : constant Word_List := [W1'Access, W2'Access, W3'Access, W4'Access, W1'Access, W2'Access];

   Counts : Word_Counts.Map;
  
…