Skip to content

Containers#

Container Contracts

Many aspects have been excluded from the container specifications because of the verbosity of the contracts. Check the respective AARM pages for the full declarations and subprogram descriptions.

package Ada.Containers is
   with Pure is

   type Hash_Type  is mod <implementation-defined>;
   type Count_Type is range 0 .. <implementation-defined>;

   Capacity_Error: exception;
end Ada.Containers;

Language-defined containers:

Array Sorting#

The language-defined generic procedures Containers.Generic_Array_Sort, Containers.Generic_Constrained_Array_Sort, and Containers.Generic_Sort provide sorting on arbitrary array types.

Ada.Containers.Generic_Array_Sort
generic
   type Index_Type   is (<>);
   type Element_Type is private;
   type Array_Type   is array(Index_Type range <>) of Element_Type;
   with function "<"(Left, Right: Element_Type) return Boolean is <>;
procedure Ada.Containers.Generic_Array_Sort(Container: in out Array_Type)
   with Pure, Nonblocking, Global => null;
Ada.Containers.Generic_Constrained_Array_Sort
generic
   type Index_Type   is (<>);
   type Element_Type is private;
   type Array_Type   is array(Index_Type) of Element_Type;
   with function "<"(Left, Right: Element_Type) return Boolean is <>;
procedure Ada.Containers.Generic_Constrained_Array_Sort(Container: in out Array_Type)
   with Pure, Nonblocking, Global => null;
Ada.Containers.Generic_Sort
generic
   type Index_Type is (<>);
   with function  Before(Left, Right: Index_Type) return Boolean;
   with procedure Swap  (Left, Right: Index_Type);
procedure Ada.Containers.Generic_Sort(First, Last: Index_Type'Base)
   with Pure, Nonblocking, Global => null;

Examples#

Dijkstra’s Shortest Path Algorithm

The following example is an implementation of Dijkstra’s shortest path algorithm in a directed graph with positive distances. The graph is represented by a map from nodes to sets of edges. 

with Ada.Containers.Vectors;
with Ada.Containers.Doubly_Linked_Lists;
use Ada.Containers;

generic
   type Node is range <>;
package Shortest_Paths is
   type Distance is new Float range 0.0 .. Float'Last;
   type Edge is record
      To, From: Node;
      Length  : Distance;
   end record;

   package Node_Maps is new Vectors(Node, Node);
   -- The algorithm builds a map to indicate the node used to reach a given
   -- node in the shortest distance.

   package Adjacency_Lists is new Doubly_Linked_Lists(Edge);
   use Adjacency_Lists;

   package Graphs is new Vectors(Node, Adjacency_Lists.List);
   package Paths  is new Doubly_Linked_Lists(Node);

   function Shortest_Path(G: Graphs.Vector; Source: Node; Target: Node) return Paths.List
      with Pre => G(Source) /= Adjacency_Lists.Empty_List;

end Shortest_Paths;

package body Shortest_Paths is
   function Shortest_Path(G: Graphs.Vector; Source: Node; Target: Node) return Paths.List
   is
      use Adjacency_Lists, Node_Maps, Paths, Graphs;
      Reached: array(Node) of Boolean := (others => False);
      -- The set of nodes whose shortest distance to the source is known.
      Reached_From    : array(Node) of Node;
      So_Far          : array(Node) of Distance := (others => Distance'Last);
      The_Path        : Paths.List := Paths.Empty_List;
      Nearest_Distance: Distance;
      Next            : Node;
   begin
      So_Far(Source) := 0.0;
      while not Reached(Target) loop
         Nearest_Distance := Distance'Last;
         -- Find closest node not reached yet, by iterating over all nodes.
         -- A more efficient algorithm uses a priority queue for this step.
         Next := Source;
         for N in Node'First .. Node'Last loop
            if not Reached(N) and then So_Far(N) < Nearest_Distance then
               Next := N;
               Nearest_Distance := So_Far(N);
            end if;
         end loop;

         if Nearest_Distance = Distance'Last then
            -- No next node found, graph is not connected
            return Paths.Empty_List;
         else
            Reached(Next) := True;
         end if;

         -- Update minimum distance to newly reachable nodes.
         for E of G (Next) loop
            if not Reached(E.To) then
               Nearest_Distance := E.Length + So_Far(Next);
               if Nearest_Distance < So_Far(E.To) then
                  Reached_From(E.To) := Next;
                  So_Far(E.To) := Nearest_Distance;
               end if;
            end if;
         end loop;
      end loop;

      -- Rebuild path from target to source.
      declare
         N: Node := Target;
      begin
         Prepend(The_Path, N);
         while N /= Source loop
            N := Reached_From(N);
            Prepend(The_Path, N);
         end loop;
      end;

      return The_Path;
   end;
end Shortest_Paths;