--- 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

Questions? Ask the ACAA Technical Agent