CVS difference for ai05s/ai05-0212-1.txt

--- ai05s/ai05-0212-1.txt	2011/02/16 06:15:23	1.4
+++ ai05s/ai05-0212-1.txt	2011/03/08 23:59:38	1.5
@@ -1,4 +1,4 @@
-!standard A.18.2(9/2)                                  11-02-09  AI05-0212-1/04
+!standard A.18.2(9/2)                                  11-02-16  AI05-0212-1/05
 !class Amendment 10-04-26
 !status work item 10-04-26
 !status received 10-02-27
@@ -312,31 +312,153 @@
 
 Add a new clause at the end of the containers section: (Currently A.18.33)
 
-A.18.33 Example of container use.
+A.18.33 Example of container use
 
-[** TBD - bigger, better examples are supposed to be coming from Ed and Steve.
-   Examples of iterator use need to be included. **]
+The following example using the containers to calculate the shortest paths
+between each pair of nodes in a set.
 
-For the following declarations:
-
-    type Point is record
-        X, Y : Natural;
-    end record;
-    subtype Short is Natural range 1 .. 100;
-    package Point_Vectors is new Ada.Containers.Vectors (Short, Point);
-    use Point_Vectors;
-    Obj : Point_Vectors.Vector;
-    Cur : Point_Vectors.Cursor;
-
-the effect of the Variable_Indexing and Implicit_Dereference aspects is that
-
-    Obj(Cur).X := 10;
-
-has the effect of calling the Reference function and dereferencing the result, as in the
-following expression:
-
-    Point_Vectors.Reference (Obj, Cur).Element.all.X := 10;
-
+with Ada.Containers.Hashed_Sets; 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_Sets is new Vectors (Node, Boolean);
+   package Node_Maps is new Vectors (Node, Node); 
+
+   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);
+
+   package Distances is new Vectors (Node, Distance);
+
+   function Shortest_Path
+     (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List;
+end Shortest_Paths;
+
+package body Shortest_Paths is
+   function Shortest_Path
+     (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List
+   is
+      use Node_Sets, Node_Maps, Paths, Distances, Graphs;
+      Reached  : Node_Sets.Vector;
+      Reached_From : Node_Maps.Vector;
+      So_Far   : Distances.Vector;
+      The_Path : Paths.List := Paths.Empty_List;
+      Nearest  : Node;
+      Nearest_Distance : Distance;
+      Next     : Node;
+   begin
+      Reserve_Capacity (So_Far, Length (G));
+      Reserve_Capacity (Reached, Length (G));
+
+      --  Initially all nodes are unreachable.
+      for N in G.Iterate loop
+        So_Far (N) :=  Distance'Last;
+        Reached (N) := False;
+      end loop;
+
+      Reached (Source) := True;
+
+      while not Reached (Target) loop
+         Nearest_Distance := Distance'Last;
+
+         --  Find closest node not reached yet.
+
+         for N in G.Iterate loop
+            if not Reached (N)
+              and then So_Far (N) < Nearest_Distance then
+                 Next := N;
+                 Nearest_Distance := So_Far (N);
+            end if;
+         end loop;
+
+         Reached (Next) := True;
+
+         --  Update minimum distance to newly reachable nodes.
+
+         for E of G (Next) loop
+            if not Reached (E.To) then
+               Nearest_Distance :=
+                 Distance'Min (So_Far (E.To) + So_Far (Nearest), So_Far (E.To));
+
+               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
+         while N /= Source loop
+            N := Reached_From (N);
+            Prepend (The_Path, N);
+         end loop;
+      end;
+      return The_Path;
+   end;
+end Shortest_Paths;
+
+Note that the effect of the Variable_Indexing aspect (on type Vector) and the
+Implicit_Dereference aspect (on type Reference_Type) is that
+
+   So_Far (N) := Distance'Last;
+
+is a convinient short hand for
+
+   So_Far.Reference (N).Element.all := Distance'Last;
+
+Similarly, the effect of the loop:
+
+         for E of G (Next) loop
+            if not Reached (E.To) then
+               ...
+            end if;
+         end loop;
+
+is the same as:
+
+         for C in G (Next).Iterate loop
+            declare
+               E : Edge renames G (Next)(C).all;
+            begin
+               if not Reached (E.To) then
+                  ...
+               end if;
+            end;
+         end loop;
+
+which is the same as:
+
+         declare
+            L : Adjecency_Lists.List renames G (Next);
+            C : Adjacency_Lists.Cursor := L.First;
+         begin
+            while C /= No_Element loop
+               declare
+                  E : Edge renames L(C).all;
+               begin
+                  if not Reached (E.To) then
+                     ...
+                   end if;
+               end;
+               C := L.Next (C);
+            end loop;
+         end;
 
 !discussion