Wednesday, August 1, 2012

A pointer-free balanced "AA_Tree" in ParaSail

Talking about pointer-free data structures without an example is difficult. Here is an example from the "standard library" of ParaSail. It is a balanced "AA" tree. First we have the interface to the AA_Tree module, then the class that implements it, and finally a simple test function "Test_AA_Tree."

Note that this is just part of the ParaSail standard library, which is included in the downloadable prototype compiler and virtual machine. See a separate blog entry for the most recent downloadable version. You can run the test program after installing the ParaSail release by the command "pslc aaa.psi -command Test_AA_Tree 2 9 4". See the appendix in the ParaSail reference manual for more information on running the ParaSail compiler and virtual machine.

// ParaSail Prototype Standard Library

// Copyright (C) 2011-2012, S. Tucker Taft, Lexington MA, USA
// To be used only for Personal, Academic, or Evaluation Purposes;
// Not for Commercial Production Use.
// Report errors at http://groups.google.com/group/parasail-programming-language

interface AA_Tree<Element is Comparable<>> is

    // This module implements a balanced "AA" tree, originally
    // described by Arne Andersson in the "Proceedings of the Workshop
    // on Algorithms and Data Structures," pp 60-71, Springer Verlag, 1993.
    // The following algorithm and descriptions were taken from the
    // WikiPedia article on AA_Tree: 
    //       http://en.wikipedia.org/wiki/AA_tree
    // Note that various additional checks for a null tree have been added.

    // Only two operations are needed for maintaining balance in an AA tree.
    // These operations are called skew and split. Skew is a right rotation
    // when an insertion or deletion creates a left horizontal link. Split
    // is a conditional left rotation when an insertion or deletion creates two
    // horizontal right links, which once again corresponds to two
    // consecutive red links in red-black trees.

    op "[]"() -> optional AA_Tree;
        // Create an empty tree

    func Insert(var T : optional AA_Tree; X : Element);
        // input: X, the value to be inserted, and 
        // T, the root of the tree to insert it into.
        // output: A balanced T' including X.

    func Delete(var T : optional AA_Tree; X : Element);
        // input: X, the value to delete, and T, 
        // the root of the tree from which it should be deleted.
        // output: T', balanced, without the value X.

    op "in"(X : Element; T : optional AA_Tree) -> Boolean;

    func Overlapping(T : optional AA_Tree; X : Element) -> optional Element;
        // input: X, the value to find, and T, 
        // the root of the tree to be searched.
        // output: the element equal to or "unordered" relative to X.

    op "|="(var T : optional AA_Tree; X : Element) is Insert;

    op "<|="(var T : optional AA_Tree; var X : optional Element);
        // Move X into AA_Tree, leaving X null.

    func First(T : optional AA_Tree) -> optional Element;
      // Return first (smallest) element in tree

    func Last(T : optional AA_Tree) -> optional Element;
      // Return last (greatest) element in tree

    func Remove_First(var T : optional AA_Tree) -> optional Element;
      // Remove first (smallest) element in tree

    func Remove_Last(var T : optional AA_Tree) -> optional Element;
      // Remove last (greatest) element in tree

    func Remove_Any(var T : optional AA_Tree) -> optional Element;
      // Remove some element from tree

    func Count(T : optional AA_Tree) -> Univ_Integer;
      // Return a count of the nodes in the tree

    func Is_Empty(T : optional AA_Tree) -> Boolean;
      // Return True if the tree is empty

end interface AA_Tree;

class AA_Tree is
    var Value : Element;
    var Level : Univ_Integer := 0;
    var Left : optional AA_Tree;
    var Right : optional AA_Tree;

    func Node(var Value : optional Element; Level : Univ_Integer; 
      Left, Right : optional AA_Tree) -> AA_Tree is
        // Create a new tree; move Value into it.
        return (Value <== Value, Level => Level, Left => Left, Right => Right);
    end func Node;

    func Is_Leaf(T : optional AA_Tree) -> Boolean is
        return T not null and then
          T.Left is null and then T.Right is null;
    end func Is_Leaf;

    func Leftmost(ref T : optional AA_Tree) -> ref optional AA_Tree is
        for L => T loop
            if L not null and then L.Left not null then
                // Continue with Left until we reach null
                continue loop with L.Left;
            else
                // Found left-most
                return L;
            end if;
        end loop;
    end func Leftmost;

    func Successor(T : optional AA_Tree) -> optional Element is
        // Return element in tree greater than but closest to T.Value
        if T.Right not null then
            const Succ := Leftmost(T.Right);
            {Succ not null};
            return Succ.Value;
        else
            return null;
        end if;
    end func Successor;

    func Rightmost(ref T : optional AA_Tree) -> ref optional AA_Tree is
        for R => T loop
            if R not null and then R.Right not null then
                // Keep following down Right side
                continue loop with R.Right;
            else
                // Found right-most
                return R;
            end if;
        end loop;
    end func Rightmost;

    func Predecessor(T : optional AA_Tree) -> optional Element is
        // Return element in tree less than but closest to T.Value
        if T.Left not null then
            return Rightmost(T.Left).Value;
        else
            return null;
        end if;
    end func Predecessor;

    func Skew(var T : optional AA_Tree) is
      // input: T, a node representing an AA tree that needs to be rebalanced.
      // output: T' Another node representing the rebalanced AA tree.

        if T not null and then
          T.Left not null and then
          T.Left.Level == T.Level then
            // The current T.Left becomes new root

            // Exchange value of T.Left with root
            T.Value <=> T.Left.Value;
           
            // Move old root and T.Left.Right over to right side of tree
            T.Left.Right <=> T.Right;
            T.Left.Left <=> T.Right;
            T.Left <=> T.Right;
        end if;
    end func Skew;

    func Split(var T : optional AA_Tree) is
        // input: T, a node representing an AA tree that needs to be rebalanced.
        // output: T' Another node representing the rebalanced AA tree.

        if T not null and then
          T.Right not null and then
          T.Right.Right not null and then
          T.Level == T.Right.Right.Level then
            // T.Right becomes the new root
            // Exchange value and level between root and T.Right
            T.Value <=> T.Right.Value;
            T.Level <=> T.Right.Level;

            // Move old root and T.Right.Left to left side of tree
            T.Left <=> T.Right.Right;
            T.Right.Left <=> T.Right.Right;
            T.Left <=> T.Right;

            // Increment level
            T.Level += 1;
        end if;
    end func Split;

    func Decrease_Level(var T : optional AA_Tree) is
        // input: T, a tree for which we want to remove links that skip levels.
        // output: T with its level decreased.

        if T is null then
            return;
        end if;
           
        var Should_Be : Univ_Integer := 1;

        if T.Left not null then
            Should_Be := T.Left.Level + 1;
        end if;

        if T.Right not null then
            Should_Be := Min(Should_Be, T.Right.Level + 1);
        end if;
            
        if Should_Be < T.Level then
            T.Level := Should_Be;
            if T.Right not null and then
              Should_Be < T.Right.Level then
                T.Right.Level := Should_Be;
            end if;
        end if;
    end func Decrease_Level;

  exports

    op "[]"() -> optional AA_Tree is
        // Create an empty tree
        return null;
    end op "[]";

    // Insertion begins with the normal binary tree search and insertion
    // procedure. Then, as the call stack unwinds (assuming a recursive
    // implementation of the search), it's easy to check the validity of the
    // tree and perform any rotations as necessary. If a horizontal left link
    // arises, a skew will be performed, and if two horizontal right links
    // arise, a split will be performed, possibly incrementing the level of the
    // new root node of the current subtree. Note, in the code as given above,
    // the increment of T.Level. This makes it necessary to continue checking
    // the validity of the tree as the modifications bubble up from the leaves.
    
    op "<|="(var T : optional AA_Tree; var X : optional Element) is
        // Move X into AA_Tree, leaving X null.
        // input: X, the value to be inserted, and 
        // T, the root of the tree to insert it into.
        // output: A balanced T' including X.

        // Do the normal binary tree insertion procedure. 
        // Set the result of the recursive call to the correct 
        // child in case a new node was created or the
        // root of the subtree changes.

        if T is null then
            // Create a new leaf node with X.
            T := Node(X, 1, null, null);
            return;
        end if;

        case X =? T.Value of
          [#less] =>
            T.Left <|= X;
          [#greater] =>
            T.Right <|= X;
          [#equal | #unordered] =>
            // Note that the case of X == T.Value is unspecified. 
            // As given, an insert will have no effect. 
            // The implementor may desire different behavior.
            X := null;
            return;
        end case;

        // Perform skew and then split. 
        // The conditionals that determine whether or
        // not a rotation will occur or not are inside 
        // of the procedures, as given above.

        Skew(T);
        Split(T);
    end op "<|=";

    func Insert(var T : optional AA_Tree; X : Element) is
        // Just pass the buck to the "<|=" operation
        var X_Copy for T := X;
        T <|= X_Copy;
    end func Insert;

    // As in most balanced binary trees, the deletion of an internal node can
    // be turned into the deletion of a leaf node by swapping the internal node
    // with either its closest predecessor or successor, depending on which are
    // in the tree or on the implementor's whims. Retrieving a predecessor is
    // simply a matter of following one left link and then all of the remaining
    // right links. Similarly, the successor can be found by going right once
    // and left until a null pointer is found. Because of the AA property of
    // all nodes of level greater than one having two children, the successor
    // or predecessor node will be in level 1, making their removal trivial.
    // 
    // To re-balance a tree, there are a few approaches. The one described by
    // Andersson in his original paper is the simplest, and it is described
    // here, although actual implementations may opt for a more optimized
    // approach. After a removal, the first step to maintaining tree validity
    // is to lower the level of any nodes whose children are two levels below
    // them, or who are missing children. Then, the entire level must be skewed
    // and split. This approach was favored, because when laid down
    // conceptually, it has three easily understood separate steps:
    // 
    //     Decrease the level, if appropriate.
    //     Skew the level.
    //     Split the level.
    // 
    // However, we have to skew and split the entire level this time instead of
    // just a node, complicating our code.

    func Delete(var T : optional AA_Tree; X : Element) is
        // input: X, the value to delete, and T, 
        // the root of the tree from which it should be deleted.
        // output: T', balanced, without the value X.

        if T is null then
            // Not in tree -- should we complain?
            return;
        end if;

        case X =? T.Value of
          [#less] =>
            Delete(T.Left, X);
          [#greater] =>
            Delete(T.Right, X);
          [#equal] =>
            // If we're a leaf, easy, otherwise reduce to leaf case. 
            if Is_Leaf(T) then
                T := null;
            elsif T.Left is null then
                // Get successor value and delete it from right tree,
                // and set root to have that value
                const Succ := Successor(T);
                Delete(T.Right, Succ);
                T.Value := Succ;
            else
                // Get predecessor value and delete it from left tree,
                // and set root to have that value
                const Pred := Predecessor(T);
                Delete(T.Left, Pred);
                T.Value := Pred;
            end if;
          [#unordered] =>
            // Not in tree; should we complain?
            return;  
        end case;

        // Rebalance the tree. Decrease the level of all nodes in this level if
        // necessary, and then skew and split all nodes in the new level.

        if T is null then
            return;
        end if;

        Decrease_Level(T);
        Skew(T);
        Skew(T.Right);
        if T.Right not null then
            Skew(T.Right.Right);
        end if;
        Split(T);
        Split(T.Right);
    end func Delete;

    op "in"(X : Element; T : optional AA_Tree) -> Result : Boolean is
        for P => T while P not null loop
            case X =? P.Value of
              [#less] =>
                continue loop with P.Left;
              [#greater] =>
                continue loop with P.Right;
              [#equal] =>
                return #true;
              [#unordered] =>
                return #false;
            end case;
        end loop;
        return #false;  // Not found
    end op "in";

    func First(T : optional AA_Tree) -> optional Element is
      // Return first (smallest) element in tree
        if T is null then
            return null;
        else 
            return Leftmost(T).Value;
        end if;
    end func First;

    func Last(T : optional AA_Tree) -> optional Element is
      // Return last (greatest) element in tree
        if T is null then
            return null;
        else
            return Rightmost(T).Value;
        end if;
    end func Last;


    func Remove_First(var T : optional AA_Tree) -> Result : optional Element is
      // Remove first (smallest) element in tree
        Result := First(T);
        if Result not null then
            Delete(T, Result);
        end if;
    end func Remove_First;

    func Remove_Last(var T : optional AA_Tree) -> Result : optional Element is
      // Remove last (greatest) element in tree
        Result := Last(T);
        if Result not null then
            Delete(T, Result);
        end if;
    end func Remove_Last;

    func Remove_Any(var T : optional AA_Tree) -> Result : optional Element is
      // Remove some element from tree
        if T is null then
            return null;
        end if;
        Result := T.Value;
        if Result not null then
            Delete(T, Result);
        end if;
    end func Remove_Any;

    func Is_Empty(T : optional AA_Tree) -> Boolean is
      // Return True if the tree is empty
        return T is null;
    end func Is_Empty;

    func Count(T : optional AA_Tree) -> Univ_Integer is
      // Return a count of the nodes in the tree
        if T is null then
            return 0;
        else
            return Count(T.Left) + Count(T.Right) + 1;
        end if;
    end func Count;

    func Overlapping(T : optional AA_Tree; X : Element) -> optional Element is
        // input: X, the value to find, and T, 
        // the root of the tree to be searched.
        // output: the element equal to or "unordered" relative to X.
        if T is null or else T.Value is null then
            return null;
        else
            case X =? T.Value of
              [#less] =>
                return Overlapping(T.Left, X);
              [#greater] =>
                return Overlapping(T.Right, X);
              [#equal | #unordered] =>
                // Close enough
                return T.Value;
            end case;
        end if;
    end func Overlapping;

end class AA_Tree;

func Test_AA_Tree(A : Univ_Integer; B : Univ_Integer; C : Univ_Integer) is
    type Univ_Tree is AA_Tree<Univ_Integer>;
    var T : Univ_Tree := [];
    var X : Univ_Integer := A;

    Insert(T, A);
    Println("Count = " | Count(T) | " after insert of " | A);
    Insert(T, B);
    Println("Count = " | Count(T) | " after insert of " | B);
    Insert(T, C);
    Println("Count = " | Count(T) | " after insert of " | C);

    Insert(T, A);
    Println("Count = " | Count(T) | " after another insert of " | A);

    Println(A | " in T = " | (A in T));
    Println(B | " in T = " | (B in T));
    Println(C | " in T = " | (C in T));
    Println("7 in T = " | (7 in T));

    for E := Remove_First(T) then Remove_First(T) while E not null loop
        Println("Remove_First = " | E);
    end loop;

    Println("Count after loop : " | Count(T));

    for I in 1..10 forward loop
        Insert(T, I);
        Println("Count = " | Count(T) | " after insert of " | I);
    end loop;

    for L := Remove_Last(T) then Remove_Last(T) while L not null loop
        Println("Remove_Last = " | L);
    end loop;

    Println("Count after loop : " | Count(T));

    for J in 1..10 reverse loop
        Insert(T, J);
        Println("Count = " | Count(T) | " after insert of " | J);
    end loop;

    Println("Count after loop : " | Count(T));

    Println("Overlapping(T, 5) = " | Overlapping(T, 5));

    for Z := Remove_Any(T) then Remove_Any(T) while Z not null loop
        Println("Remove_Any = " | Z);
    end loop;

    Println("Count after loop : " | Count(T));

    for K in 1..10 loop
        Insert(T, K);
        Println("Count = " | Count(T) | " after insert of " | K);
    end loop;

    for F := Remove_First(T) then Remove_First(T) while F not null loop
        Println("Remove_First = " | F);
    end loop;

    Println("Count after loop : " | Count(T));

end func Test_AA_Tree;

No comments:

Post a Comment