%!
% insertion-sort.ps
% 
% an insertion sort.  Original by John Warnock.
% 
% you must call SortInit then call Insert for each thing to
% be sorted.  Then call one of the "walk" routines to traverse.

/$sort 20 dict def

%SortInit returns the root node of an empty binary tree.

/SortInit { 1 array } def

% Insert expects a root node and string on the stack.
% inserts the string into the tree. It expect /compare
% to be defined, and to take two strings and return a boolian
% that tells if the first is greater than the second.

/compare { gt } def

/Insert { %def
    exch dup 0 get type (nulltype) eq { %ifelse
        exch [ exch 1 array 1 array ] 0 exch put
    }{ %else
        aload pop aload pop 4 2 roll 2 copy compare { %ifelse
            pop 3 -1 roll pop Insert
        }{ %else
            pop exch pop Insert
        } ifelse
    } ifelse
} def

%PrefixWalk expects a root node  and a proc body on the operand stack.
%For each element in the array, it executes the proc body.

/PrefixWalk { %def
    $sort begin
	cvx /!bt exch def bpwalk 
    end
} def


%PostfixWalk expects a rootnode and a proc body on the stack
%For each element (in posfix order), it executes the proc body.

/PostfixWalk { %def
    $sort begin
	cvx /!bt exch def bbwalk
    end
} def

/SystemSort&Print { %def
  $sort begin
     /tree SortInit def
     systemdict { %forall
         pop
	 (                            )cvs dup length string copy
	 tree exch Insert
     } forall
     tree { == } PrefixWalk
  end
} def

$sort begin

/bpwalk { %def
    dup 0 get type /nulltype eq { pop }{ %ifelse
	aload pop aload pop exch bpwalk exch !bt bpwalk
    } ifelse
} bind def

/bbwalk { %def
    dup 0 get type /nulltype eq { pop }{ %ifelse
	aload pop aload pop bbwalk exch !bt bbwalk
    } ifelse
} bind def

end %end of $sort