%! % A POSTSCRIPT HEAP SORT UTILITY AND DEMO % ======================================= % by Don Lancaster % This is the companion heapsort test code to http://www.tinaja.com/glib/heapsort.pdf % Additional support at http://www.tinaja.com and don@tinaja.com (928) 428-2073. % To use, modify as desired, save as standard ASCII text file and send to Acrobat Distiller. % Use of gonzo utilities are strongly recommended but not essential. % See http://www.tinaja.com/post01.asp % (C:\\windows\\desktop\\gonzo\\gonzo.ps) run % use internal gonzo % (A:\\gonzo.ps) run % use external gonzo /guru { gonzo begin ps.util.1 begin printerror nuisance begin} def % Uncomment next line if gonzo is in use % guru % activate gonzo utilities % Stopwatch utilities extracted from Gonzo... % ============================ % timing utilities. use stopwatchon and stopwatchoff for simple % one shot timing. For multiple time totals, use resettimer % starttimer stoptimer ... starttimer stoptimer reporttimer /stopwatchoff {stoptimer reporttimer} def % for single shots /stopwatchon {resettimer starttimer} def % for single shots /reporttimer {mytime 1000 div (\rElapsed time: ) print 20 string cvs print ( seconds.\r) print flush} def % to host /resettimer {/mytime 0 def} def % reset timer /starttimer {usertime /mytimenow exch def} def % add to time so far /stoptimer {usertime mytimenow sub /mytime exch mytime add def} def % for multiple timing intervals % ========================== % Mergestr utility extracted from Gonzo... % mergestr merges the two top stack strings into one top stack string /mergestr {2 copy length exch length add string dup dup 4 3 roll 4 index length exch putinterval 3 1 roll exch 0 exch putinterval} def % ========================== % standard data /stdat is a collection of 273 strings for testing /stddat [(Tca785 pdf) (Humidity measurement principles tutorial pdf) (Fluxgate) (Its a gas) (Bargain pages) (12C508 WAKEUP) (Pic sinewave) (Guru s timeline) (Postscript transparency) (Cubic spline) (Breath alcohol detector ) (Biomedical Instrumentation tutorial) (Pdf_sec.ps) (Rice and Tesla turbine) (Bidding scams live auction) (412 xerox tech mode) (Earth inclination magnetic north tutorial) (Spline math) (Surplus dilbert books) (NE5520) (Mitutoyo scale bcd format) (Receiver strong 4355 version download) (Hydrogen energy) (Tv extend drill cable coaxial fish) (Bytes Transferred mismatch webtrends) (TTL FM LEBANON) (COS objects) (Plating current efficiencies surface geometries) (Delete plug-in adobe acrobat) (Filter cookbook download) (Acrobat distiller) (Watermark.api Acrobat) (PSD Position Sensitive Detector) (Mc145447) (Save html pdf netscape) (Max126 ) (Cryogenic pumps tutorials) (Genlocking hardware) (Stratasys auction) (Superregenerative detector) (Uniscan scheme download) (Farenheit Rankine Kelvin Centigrade) (SVG Adobe acrobat) (Top-octave generator) (Hydrogen energy) (Polywater pole setting foam) (Pic 16f84 products) (PostScript ADDfont) (On-demand book publishing low volume) (Acrobat Distiller) (Cubic spline) (Cubic bezier surface) (Simplify postscript) (Tesla autobiography ebooks download) (3 phase power equation) (Cubic spline) (Html full screen) (Peltier cells vehicle air conditioning ) (Http://www.tinaja.com/glib/pstrans.pdf) (Handy numbers list country codes) (Images jpg en postscript) (Gs append pdf side) (Acrobat security printing) (Santa bitmaps) (16f84 gateway) (PIC development boards vendors) (TAS455 Repair) (NURBS math) (Pic microcontroller encryption project ) (Example of postscript) (Arizona source code pic) (Adobe acrobat cooltype bgr) (SCR FIRING CIRCUIT TUTORIAL) (Voice dimmer scheme) (Crest factor) (Electronic compass pic16f84) (Kty schematic) (Flutterwumper) (Chain codes) (Loctite luminescent) (Ecg true type font) (Bezier curve) (CTS DSR) (Microprocessor pic) (Acrobat distiller) (Bitmap directory) (Micro cookbook I ) (HYDROGEN) (Genie psrt) (Archaeomagnetism ) (PWM Modulation and Demodulation Circuit Design) (Hv2405e) (Byte range acrobat) (Html tutorial redirecting) (Binary chain code) (Content-range http cgi) (SPLINE CUBIC) (UGN3013) (Metering digital speed rotations of motors ) (Related:www.tinaja.com/glib/hackar1.pdf) (Acrobat distiller) (Tv repairing pdf ) (Lcd font editor ) (HTML referral) (Video output spec db15 canon ) (Problem searching ghostscript acrobat problem) (Techniks and methods of System Analysis) (Binary chain code ) (Three inverters programable pic) (Distiller error printer) (Automatic voltage regulator fuzzy pdf) (Thomson rr 600 cd user manual) (Binary chain encoder) (Bezier cubic java) (Compound gauges) (Striking voltage fluorescent service ) (BMP file format ) (Visual Basic Gauss Jordan ) (Pfa font ) (Transmission line transformers) (Bargain pages) (IBM patents pdf) (Allpass opamp) (Hide save on acrobat) (Conversion degrees compass cad) (Http://www.tinaja.com/glib/resbar02.pdf) (Ds1624 ) (Install pfm adobe) (Hydrogen fuel) (Speed meter digital pic) (Thumbnail pdf file in html) (Max631 application) (Hydrogen electrolysis) (Rewiring phone lines tutorial) (Photoshop 6 tutorial filetype:pdf) (74hc02 code radio) (Justified fonts ) (Postscript bdef) (Acrobat distiller) (74HC02 pinouts) (SI 3241 voltage regulator) (Uhr 16F84) (Acrobat distiller) (Microchip pic software ) (Fuel cell handbook) (Postscript font cache distiller) (Square word ghostscript pdf problem) (Adobe acrobat editor) (PIC robots) (Hot rolling of steel tutorials free) (Info on hydrogen) (Adobe acrobat software development kit) (Java spline control point) (Led lazer pinouts) (Acrobat distiller) (Print acrobat distiller) (Hydrogen fuel) (Ba1404 spec) (Copyright symbol encoding) (Slow start 6100c scanner) (Adobe acrobat 5 download) (Copyright symbol html encoding) (Related:www.solarbotics.net/library/circuits/bot_head_pshead.html) (Pdf xobjects) (IC 4013 Tutorial) (Micro Cookbook updates) (Using adobe acrobat distiller) (3d models Santa Claus) (Bargain Pages) (Bitmap resampling code) (Enter Password in 5 seconds or this machine will self destruct and destroy everything in a 50 foot radius. 5....4....3....2...1.....BOOM!!!!) (Surplus fiberscope) (Aircraft skin scews) (Pdf flate compression code) (Get integers out of string) (Mac interface circuit pic) (Free ebook for download attenuators) (My Ebay) (Acrobat Distiller download) (Dissolvable laundry bags) (Sum stereo mono schematics) (Electret for steady state pressure) (Hydrogen fuel ) (Tektronix 2215A) (Pic tools) (Pic tutorials) (Single sideband, polyphase networks) (Web friendly colors) (Microprocessor pic) (Ghostscript acrobat password) (Microwave ) (Curve slope spline) (Adobe acrobat the plugin initialize.) (Html tutorial redirection page) (Microcontroller tutorial) (Postscript reader .pfa) (Understanding wavelets) (Spline) (AC motor control pic microcontroller) (Backwards phone lookup) (Adobe acrobat http options 5) (Rf variable attenuator pot) (Cubic spline) (Bezier curve length) (.bin archive repair) (Adobe pdfmark Reference Manual) (Basic stamp midi footswitch) (Drmo williamsburg) (Avi files inductive position encoder) (Hack keynet internet cards) (Copyright symbols) (Santa Claus International Resourcing inc.) (Curve fitting power) (Acrobat distiller) (Bitmap font generator) (Sign changer circuit analog) (Best metals for thermocouples) (Triac 603) (Vcr controller) (Samples ic free electronics semiconductors) (Pendulum vacuum valve) (Buckyball capacitor) (\(PIC, microcontroller\) \(video\)) (THIOKOL DYNACHEM MODEL 300) (Quadrants for sines and cosines) (Adobe byte range ) (Suspa gas spring sell) (Acrobat distiller tutorial ) (Robotics projects stepper pic 16f84) (POSTSCRIPT DISTILLER) (What is acrobat distiller) (QMS Magic Color 330 fuser rollers) (Transformer railroad antique schematics) (RFID handbook) (Ignition system pic microcontroller) (Convert old Aldus Freehand files) (Genie garage door circuits) (Old frothingslosh pale stale ale) (Fundamentals of solar energy) (Chirp radar) (Dummy text to use in website samples) (Bezier algorithms ) (Tutorials for postscript) (Email contact of don) (Bmp file format ) (Wein-bridge oscillator with agc) (Converting JPEG to PDF) (Postscript viewer) (Shake light piezo) (Digimatic bcd format) (Turbine cars electric hybrid ) (Magnetic sensors pavel ripka) (Postscript curveto) (Piezoelectric ring bender) (Don lancaster) (Magnetic sensors pavel ripka fluxgate ext pdf) (Iron-on printing t-shirts va fairfax) (Copyright symbols) (Precision humidity gauge probe) (Why do people use primary research) (Bookbinding fabric glue soak ) (On demand publishing ) (Bezier curves) (Shareware for Wavelet analysis) (M65830 schematic) (General Radio universal filter 1952) (Total reflection x-ray fluorescence tutorial) (Mouse bot pic) (Zero Crossing Triac Driver Output Optocoupler) (B) (BBBBBBB) (Multimeter eico model 249 ) (Basic stamp heart rate )] store % An optional short data set. Change name to stddat to use. /stddatx [ (Piezoelectric ring bender) (Don lancaster) (Magnetic sensors pavel ripka fluxgate ext pdf) (Iron-on printing t-shirts va fairfax) (Copyright symbols) (Precision humidity gauge probe) (Why do people use primary research) (Bookbinding fabric glue soak ) (On demand publishing ) (Bezier curves) (Shareware for Wavelet analysis) (M65830 schematic) (General Radio universal filter 1952) (Total reflection x-ray fluorescence tutorial) (Mouse bot pic) (Zero Crossing Triac Driver Output Optocoupler) ] store % An optional numeric short data set. Change name to stddat to use. /stddatx [ (00) (01) (02) (10) (11) (12) (20) (21) (22) (30) (31) (32) (40) (41) (42) (50) (51) (21) (52) ] def % ============= stddat length == % report strings being tested % ============= /heap stddat length 1 add array store heap == % /upchuck checks child versus parent and repeatedly swaps UP /upchuck { /cposn hposn store {/pposn cposn 2 idiv store pposn 0 le {exit} if heap cposn get heap pposn get % checkforswap 2 copy gt {heap exch cposn exch put % reallyswap heap exch pposn exch put} {pop pop exit} ifelse /cposn pposn store % up one triad } loop } bind store % /fillheap orders the strings into a binary tree heap array. Heap fills from top % to bottom, left to right. Highest value is always at the TOP of any data triad. % Top of any array data triad address is either lowleft 2 idiv or (identically) % lowright 2 idiv. % makeheap currently at 4.17 milliseconds for 273 strings. repeat loop timing = 0. /fillheap {/hposn 1 store stddat { % heap exch hposn exch put % place in next avail opening %%%%%%%%%%%%%%%%% inline upchuck routine %%%%%%%%%%%%%%% % we have child as pposn on stack /cposn hposn store % cposn is initially hposn {/pposn cposn 2 idiv store % parent position pposn 0 le { heap exch cposn exch put % got to top? exit } if % store child and exit heap pposn get % checkforswap 2 copy ge { % needed heap exch cposn exch put} % hold old child as parent {pop heap exch cposn exch put % save child flush parent exit exit} ifelse /cposn pposn store % up one triad } loop %%%%%%%%%%%%%%%%%% end upchuck %%%%%%%%%%%%%%%%%%%%%%%%%% /hposn hposn 1 add store} forall % reset opening and repeat % exit hposn is high by one } bind store % /emptyheap removes the highest strings in order by removing the first element. % Last element becomes first then downchucks as far as needed to preserve efficient % filed binary tree with each data triad highest value at top. Array address of % leftchild is parent*2. Array address of rightchild is (parent*2)+1 or leftchild+1. % /downchuck checks triads and places the largest on the top, swapping top with largest. /lefttriadposn 1 store /downchuck { heap exch 1 exch put % temporary save of last item /lefttriadposn 1 store { /lefttriadposn lefttriadposn 2 mul store % pick rank of lefttriad position lefttriadposn h1posn 1 sub ge {exit} if % exit if all the way through lefttriadposn dup h1posn 1 sub ne % are we NOT at the last string? { % is right triad bigger? heap lefttriadposn get heap lefttriadposn 1 add get le {1 add} if } if /swapme exch store % correct to exact position heap swapme get heap lefttriadposn 2 idiv get 2 copy lt % true=done false=swap {pop pop exit} {heap exch swapme exch put heap exch lefttriadposn 2 idiv exch put } ifelse /lefttriadposn swapme store % right-left shift? % uncomment for more detailed analysis % reportstuff } loop } bind store /h1posn 9999 store % temp marker /reportstuff { (\n\n**%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n) print (hposn: ) hposn 20 string cvs mergestr ( h1posn: ) mergestr h1posn 20 string cvs mergestr ( maybe: ) mergestr maybe 20 string cvs mergestr (\n) mergestr print heap == } store % new downchuck enter with top candidate on stack /basecheck {heap maybe get % get left point heap maybe 1 add get % get right point lt {/maybe maybe 1 add store} if % set address of larger point heap maybe get % get correct swapee } store /swapcheckold {2 copy lt % apex and heap on stack { heap exch apex exch put dup % save next apex heap exch maybe exch put} % save apex to maybe {pop pop exit} ifelse % no swap needed, done, exit } store /basecheck { heap maybe get % get left point heap maybe 1 add get % get right point lt {/maybe maybe 1 add store} if % set address of larger point heap maybe get % get correct swapee } bind def { /basechecknew { heap maybe get % get left point heap maybe 1 add get % get right point 2 copy lt {/maybe maybe 1 add store exch} if % set address of larger point pop % get correct swapee } bind def } pop % slightly slower so not used one get is faster than a 2 copy + exch /downchuck { /apex 1 store { /maybe apex 2 mul store % calculate lower left maybe h1posn 2 sub le % full triad available? { basecheck % find larger base %%%%%%%%% swapcheck 2 copy lt { % is a swap needed? heap exch apex exch put % yes, swap and save apex } {pop heap exch apex exch % no, save apex only and exit put exit} ifelse %%%%%%%%% } {maybe h1posn 1 sub eq % left only available? {heap maybe get %%%%%%%%% 2 copy le { % is a swap needed? heap exch apex exch put % yes, swap and save apex } {pop heap exch apex exch % no, save apex only and exit put exit} ifelse %%%%%%%%% } % yes, process {heap exch apex exch put exit} ifelse % no, save apex only and exit } ifelse /apex maybe store % reset apex for next triad down } loop } bind store % new emptyheap /emptyheap { hposn 1 sub -1 2 {/h1posn exch store % loop through all strings heap h1posn get % end item to stack heap 1 get % get highest value from apex heap exch h1posn exch put % place at end downchuck % rework heap triads } for } bind store -1 vmreclaim % apparently no longer needed since arrays are not rebuilt % stddat == % Set desired number of trips to establish stopwatch accuracy. 100 recommended. stopwatchon 100 { fillheap emptyheap } repeat stopwatchoff (\n\n\nzzzzzzzz\n\n\n) print flush heap {==} forall heap length == % EOF