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