ParaSail

func Hello_World(var IO) is    IO.Println("Hello, World");end func Hello_World;

interface BMap<Key_Type is Ordered<>; Element_Type is Assignable<>> is    op "[]"() -> BMap;  // Create an empty map    func Insert(var BMap; Key : Key_Type; Value : Element_Type);    func Find(BMap; Key : Key_Type) -> optional Element_Type;    func Delete(var BMap; Key : Key_Type);    func Count(BMap) -> Univ_Integer;end interface BMap;

class BMap is    interface Binary_Node<> is      // A simple "concrete" binary node module        var Left : optional Binary_Node;        var Right : optional Binary_Node;        const Key : Key_Type;        var Value : optional Element_Type;  // null means deleted    end interface Binary_Node;    var Tree : optional Binary_Node;    var Count := 0;  exports    op "[]"() -> BMap is  // Create an empty map        return (Tree => null, Count => 0);    end op "[]";    func Insert(var BMap; Key : Key_Type; Value : Element_Type) is      // Search for Key, overwrite if found, insert new node if not        for M => BMap.Tree loop            if M is null then                // Not already in the map; add it                M := (Key => Key, Value => Value, Left => null, Right => null);                BMap.Count += 1;            else               case Key =? M.Key of                 [#less] =>                   continue loop with M.Left;                 [#greater] =>                   continue loop with M.Right;                 [#equal] =>                   // Key is already in the map;                   // bump count if Value was null;                   if M.Value is null then                       BMap.Count += 1;                   end if;                   // in any case overwrite the Value field                   M.Value := Value;                   return;               end case;            end if;        end loop;    end func Insert;    func Find(BMap; Key : Key_Type) -> optional Element_Type is      // Search for Key, return associated Value if present, or null otherwise        for M => BMap.Tree while M not null loop            case Key =? M.Key of              [#less] =>                continue loop with M.Left;              [#greater] =>                continue loop with M.Right;              [#equal] =>                // Found it; return the value                return M.Value;            end case;        end loop;        // Not found in BMap        return null;    end func Find;    func Delete(var BMap; Key : Key_Type) is      // Search for Key; delete associated node if found        for M => BMap.Tree while M not null loop            case Key =? M.Key of              [#less] =>                continue loop with M.Left;              [#greater] =>                continue loop with M.Right;              [#equal] =>                // Found it; if at most one subtree is non-null, overwrite                // it; otherwise, set its value field to null                // (to avoid a more complex re-balancing).                if M.Left is null then                    // Move right subtree into M                    M <== M.Right;                elsif M.Right is null then                    // Move left subtree into M                    M <== M.Left;                else                    // Cannot immediately reclaim node;                    // set value field to null instead.                    M.Value := null;                end if;                // Decrement count                BMap.Count -= 1;            end case;        end loop;        // Not found in the map    end func Delete;    func Count(BMap) -> Univ_Integer is      // Return count of number of items in map        return BMap.Count;    end func Count;end class BMap;

import PSL::Core::Random;import BMap;func Test_BMap(Num : Univ_Integer; Seed : Univ_Integer) is    // Test the Binary-Tree-based Map    var Ran : Random := Start(Seed);  // Start a random-number sequence    // Declare a map from integers to strings    var M : BMap<Key_Type => Univ_Integer, Element_Type => Univ_String>;    M := [];  // Initialize the map to the empty map    for I in 1..Num*2 forward loop  // Add elements to the map        const Key := Next(Ran) mod Num + 1;        const Val := "Val" | To_String(I);        Println("About to insert " | Key | " => " | Val);        Insert(M, Key, Val);    end loop;    Println("Count = " | Count(M));    for I in 1..Num loop // Search for elements in the map        const Key := Next(Ran) mod Num + 1;        Println("Looking for " | Key | ", found " | Find(M, Key));    end loop;    for I in 1..Num/3 loop  // Delete some elements from the map        const Key := Next(Ran) mod Num + 1;        Println("About to delete " | Key);        Delete(M, Key);    end loop;    Println("Count = " | Count(M));    for I in 1..Num forward loop  // Search again for elements in the map        Println("Looking for " | I | ", found " | Find(M, I));    end loop;end func Test_BMap;