pointerreversal.java

内存受限系统软件开发一书的代码。（虽不及Gang of Four的模式掷地有声

import java.util.*;

class PointerReversal {
    public static void assert (boolean  assertion, String excuse) {
        if  (!assertion) { throw new RuntimeException(excuse);}
    }

    static void main( String[] args ) {
        // Example from the text:
        BinaryTreeObject A = new BinaryTreeObject( null, null, 'A' );
        BinaryTreeObject B = new BinaryTreeObject( A, null, 'B' );
        BinaryTreeObject D = new BinaryTreeObject( null, null, 'D' );
        BinaryTreeObject C = new BinaryTreeObject( B, D, 'C' );
        BinaryTreeObject F = new BinaryTreeObject( null, null, 'F' );
        BinaryTreeObject E = new BinaryTreeObject( C, F, 'E' );
        
        String res = (String) BinaryTreeObject.Iterate( E, "" );
        assert( res.equals( "ABCDEF" ), "Sequence wrong: " + res);
        res = (String) BinaryTreeObject.Iterate( E, "" );
        assert( res.equals( "ABCDEF" ), "Sequence wrong second time: "
                + res );

        // Sorting binary tree:
        String[] forSorting = 
        {"32415", "12345", "HGFEDCAB", "ABCDEFGH", "54321", "12345", 
         "12345", "12345" };
                            
        for (int i=0; i<forSorting.length; i+=2) {
            testSort( forSorting[i], forSorting[i+1] );
        }
    }
    static void testSort( String toSort, String answer ) {
        BinaryTreeObject start = 
            new BinaryTreeObject( toSort.charAt(0) );
        for (int i = 1; i < toSort.length(); i++)
            start.AddSorted( new BinaryTreeObject( toSort.charAt( i ) ) );
        String res = (String) BinaryTreeObject.Iterate( start, "" );
        assert( res.equals( answer ), "Sorting failed from: " + toSort +
                " wanted: " + answer + " got: " + res );
    }
}

class BinaryTreeObject {
    public static void progress (String msg) {System.out.println(msg);}
    char data;
    boolean greaterThan( BinaryTreeObject other ) { 
        return data > other.data; }

    // Embedded pointers to implement the tree structure.
    BinaryTreeObject left;
    BinaryTreeObject right;
 
    // Embedded pointer for pointer reversal
    //      BinaryTreeObject previous;
    static final int Inactive = 0, DoingLeft = 1, DoingRight = 2;
    int action = Inactive;

    BinaryTreeObject( BinaryTreeObject left, BinaryTreeObject right,
                      char data ) {
        this.left = left; 
        this.right = right; 
        this.data = data; 
    }

    BinaryTreeObject( char data ) {
        this.data = data; 
    }

    void AddSorted( BinaryTreeObject newItem ) {
        // Called only on the top element of the tree:

        for (BinaryTreeObject current = this;
             current.left != newItem && current.right != newItem;
             ) {
            if (current.greaterThan( newItem )) {
                if (current.left == null) {
                    current.left = newItem; 
                }
                else { 
                    current = current.left;
                }
            } else if (current.right == null) {
                current.right = newItem;
            } else {
                current = current.right;
            }
        }
    }

    BinaryTreeObject saveParentReturningLeaf( BinaryTreeObject parent ) {
        BinaryTreeObject leaf;
        if (action == DoingLeft) {
            leaf = left;
            left = parent;
        }
        else {
            PointerReversal.assert(action == DoingRight, 
                                   "Must be going left or right" ); 
            leaf = right;
            right = parent;
        }
        return leaf;
    }

    BinaryTreeObject restoreLeafReturningParent
        ( BinaryTreeObject leafJustDone ) {
        BinaryTreeObject parent;
        if (action == DoingLeft) {
            parent = left;
            left = leafJustDone;
        }
        else {
            PointerReversal.assert(action == DoingRight, 
                                   "Not pointer reversal" ); 
            parent = right;
            right = leafJustDone;
        }
        return parent;
    }
    
    static Object Iterate( BinaryTreeObject start, Object param ) {
        BinaryTreeObject current = start;
        BinaryTreeObject leafJustDone = null;
        BinaryTreeObject parentOfCurrent = null;
        
        for (;;) {
            if (current.action == DoingLeft || 
                (current.action == Inactive && current.left == null)) {
                param = current.doIt( param );
            }

            if (current.action != Inactive)
                parentOfCurrent = current.restoreLeafReturningParent
                    ( leafJustDone );

            if (current.action == Inactive && current.left != null) {
                current.action = DoingLeft;
                BinaryTreeObject p = current; 
                current = current.saveParentReturningLeaf( parentOfCurrent );
                parentOfCurrent = p;
            }

            else if ( current.action != DoingRight &&
                      current.right != null) {
                current.action = DoingRight;
                BinaryTreeObject p = current; 
                current = current.saveParentReturningLeaf( parentOfCurrent );
                parentOfCurrent = p;
            }

            else {
                current.action = Inactive;
                if (parentOfCurrent == null) break;
                leafJustDone = current;
                current = parentOfCurrent;
            }
        } 
        return param;
    }

    Object doIt( Object param ) {
        return ( (String) param + data );
    }
}