/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / sources / 2600

< prev

next >

MacOS 8.1

Win98

DOS

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 50 61 74 68 3a 20 73 70 | 61 72 6b 79 21 75 75 6e |Path: sp|arky!uun|
|00000010| 65 74 21 6d 63 73 75 6e | 21 73 75 6e 69 63 21 6c |et!mcsun|!sunic!l|
|00000020| 75 6e 69 63 21 6d 79 21 | 6c 6a 70 0a 46 72 6f 6d |unic!my!|ljp.From|
|00000030| 3a 20 6c 6a 70 40 73 6d | 2e 6c 75 74 68 2e 73 65 |: ljp@sm|.luth.se|
|00000040| 20 28 4a 6f 68 61 6e 20 | 50 65 72 73 73 6f 6e 29 | (Johan |Persson)|
|00000050| 0a 4e 65 77 73 67 72 6f | 75 70 73 3a 20 61 6c 74 |.Newsgro|ups: alt|
|00000060| 2e 73 6f 75 72 63 65 73 | 0a 53 75 62 6a 65 63 74 |.sources|.Subject|
|00000070| 3a 20 73 70 6c 61 79 74 | 72 65 65 2d 70 61 72 74 |: splayt|ree-part|
|00000080| 31 2f 32 0a 4d 65 73 73 | 61 67 65 2d 49 44 3a 20 |1/2.Mess|age-ID: |
|00000090| 3c 31 33 35 36 40 6d 79 | 2e 73 6d 2e 6c 75 74 68 |<1356@my|.sm.luth|
|000000a0| 2e 73 65 3e 0a 44 61 74 | 65 3a 20 32 32 20 4e 6f |.se>.Dat|e: 22 No|
|000000b0| 76 20 39 32 20 31 33 3a | 33 36 3a 33 35 20 47 4d |v 92 13:|36:35 GM|
|000000c0| 54 0a 52 65 70 6c 79 2d | 54 6f 3a 20 4a 6f 68 61 |T.Reply-|To: Joha|
|000000d0| 6e 20 50 65 72 73 73 6f | 6e 20 3c 6c 6a 70 40 6d |n Persso|n <ljp@m|
|000000e0| 79 2e 73 6d 2e 6c 75 74 | 68 2e 73 65 3e 0a 4f 72 |y.sm.lut|h.se>.Or|
|000000f0| 67 61 6e 69 7a 61 74 69 | 6f 6e 3a 20 55 6e 69 76 |ganizati|on: Univ|
|00000100| 65 72 73 69 74 79 20 6f | 66 20 4c 75 6c 65 61 2c |ersity o|f Lulea,|
|00000110| 20 53 77 65 64 65 6e 0a | 4c 69 6e 65 73 3a 20 33 | Sweden.|Lines: 3|
|00000120| 31 36 0a 0a 53 75 62 6d | 69 74 74 65 64 2d 62 79 |16..Subm|itted-by|
|00000130| 3a 20 6c 6a 70 40 73 6d | 2e 6c 75 74 68 2e 73 65 |: ljp@sm|.luth.se|
|00000140| 0a 41 72 63 68 69 76 65 | 2d 6e 61 6d 65 3a 20 73 |.Archive|-name: s|
|00000150| 70 6c 61 79 74 72 65 65 | 2d 70 61 72 74 31 0a 0a |playtree|-part1..|
|00000160| 54 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 61 72 |The foll|owing ar|
|00000170| 63 68 69 76 65 20 69 73 | 20 61 20 6d 6f 64 75 6c |chive is| a modul|
|00000180| 61 2d 32 20 69 6d 70 6c | 65 6d 65 6e 74 61 74 69 |a-2 impl|ementati|
|00000190| 6f 6e 20 6f 66 20 0a 73 | 70 6c 61 79 20 74 72 65 |on of .s|play tre|
|000001a0| 65 73 2e 0a 0a 53 65 65 | 20 74 68 65 20 52 45 41 |es...See| the REA|
|000001b0| 44 4d 45 20 66 69 6c 65 | 20 66 6f 72 20 66 75 72 |DME file| for fur|
|000001c0| 74 68 65 72 20 69 6e 66 | 6f 72 6d 61 74 69 6f 6e |ther inf|ormation|
|000001d0| 2e 0a 0a 49 6e 20 73 68 | 6f 72 74 2c 20 73 70 6c |...In sh|ort, spl|
|000001e0| 61 79 20 74 72 65 65 73 | 20 61 72 65 20 61 20 66 |ay trees| are a f|
|000001f0| 6f 72 6d 20 6f 66 20 62 | 61 6c 61 6e 63 65 64 20 |orm of b|alanced |
|00000200| 62 69 6e 61 72 79 20 74 | 72 65 65 73 20 77 68 69 |binary t|rees whi|
|00000210| 63 68 0a 6d 6f 76 65 73 | 20 65 76 65 72 79 20 61 |ch.moves| every a|
|00000220| 63 63 65 73 73 65 64 20 | 6e 6f 64 65 20 74 6f 20 |ccessed |node to |
|00000230| 74 68 65 20 72 6f 6f 74 | 2e 20 54 68 69 73 20 6d |the root|. This m|
|00000240| 65 61 6e 73 20 74 68 61 | 74 20 74 68 65 20 74 72 |eans tha|t the tr|
|00000250| 65 65 0a 77 69 6c 6c 20 | 62 65 68 61 76 65 20 76 |ee.will |behave v|
|00000260| 65 72 79 20 77 65 6c 6c | 20 77 68 65 6e 20 74 68 |ery well| when th|
|00000270| 65 72 65 20 69 73 20 73 | 6f 6d 65 20 66 6f 72 6d |ere is s|ome form|
|00000280| 20 6f 66 20 6c 6f 63 61 | 6c 69 74 79 20 69 6e 20 | of loca|lity in |
|00000290| 74 68 65 0a 64 61 74 61 | 20 70 72 6f 63 65 73 73 |the.data| process|
|000002a0| 65 64 2e 20 46 75 72 74 | 68 65 72 6d 6f 72 65 20 |ed. Furt|hermore |
|000002b0| 69 74 20 63 61 6e 20 62 | 65 20 73 68 6f 77 6e 20 |it can b|e shown |
|000002c0| 74 68 61 74 20 74 68 65 | 20 61 6d 6f 72 74 69 7a |that the| amortiz|
|000002d0| 65 64 0a 61 63 63 65 73 | 73 20 63 6f 73 74 20 69 |ed.acces|s cost i|
|000002e0| 73 20 4f 28 6c 67 6e 29 | 20 66 6f 72 20 74 68 65 |s O(lgn)| for the|
|000002f0| 20 62 61 73 69 63 20 6f | 70 65 72 61 74 69 6f 6e | basic o|peration|
|00000300| 73 20 28 69 6e 73 65 72 | 74 2c 20 64 65 6c 65 74 |s (inser|t, delet|
|00000310| 65 20 61 6e 64 0a 66 69 | 6e 64 29 2e 0a 0a 54 68 |e and.fi|nd)...Th|
|00000320| 65 20 73 70 6c 61 79 20 | 74 72 65 65 20 61 6c 73 |e splay |tree als|
|00000330| 6f 20 68 61 73 20 74 68 | 65 20 6e 69 63 65 20 70 |o has th|e nice p|
|00000340| 72 6f 70 65 72 74 79 20 | 74 68 61 74 20 61 6e 20 |roperty |that an |
|00000350| 69 74 65 6d 20 61 63 63 | 65 73 73 65 64 0a 74 20 |item acc|essed.t |
|00000360| 6f 70 65 72 61 74 69 6f | 6e 73 20 61 67 6f 20 63 |operatio|ns ago c|
|00000370| 61 6e 20 62 65 20 6c 6f | 63 61 74 65 64 20 69 6e |an be lo|cated in|
|00000380| 20 4f 28 6c 67 74 29 20 | 74 69 6d 65 2e 0a 0a 2d | O(lgt) |time...-|
|00000390| 2d 2d 0a 4a 6f 68 61 6e | 20 50 65 72 73 73 6f 6e |--.Johan| Persson|
|000003a0| 20 28 6c 6a 70 40 73 6d | 2e 6c 75 74 68 2e 73 65 | (ljp@sm|.luth.se|
|000003b0| 29 0a 0a 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |)..-----|--------|
|000003c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 20 63 75 74 20 68 65 |--------|- cut he|
|000003d0| 72 65 20 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |re -----|--------|
|000003e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 0a 0a 23 |--------|-----..#|
|000003f0| 21 2f 62 69 6e 2f 73 68 | 0a 23 20 54 68 69 73 20 |!/bin/sh|.# This |
|00000400| 69 73 20 61 20 73 68 65 | 6c 6c 20 61 72 63 68 69 |is a she|ll archi|
|00000410| 76 65 20 28 73 68 61 72 | 20 33 2e 32 31 29 0a 23 |ve (shar| 3.21).#|
|00000420| 20 6d 61 64 65 20 31 31 | 2f 32 32 2f 31 39 39 32 | made 11|/22/1992|
|00000430| 20 31 33 3a 31 34 20 55 | 54 43 20 62 79 20 6c 6a | 13:14 U|TC by lj|
|00000440| 70 40 6d 79 0a 23 20 53 | 6f 75 72 63 65 20 64 69 |p@my.# S|ource di|
|00000450| 72 65 63 74 6f 72 79 20 | 2f 75 73 72 2f 73 74 61 |rectory |/usr/sta|
|00000460| 66 66 2f 6c 6a 70 2f 74 | 6d 70 2f 73 70 6c 61 79 |ff/ljp/t|mp/splay|
|00000470| 54 72 65 65 0a 23 0a 23 | 20 65 78 69 73 74 69 6e |Tree.#.#| existin|
|00000480| 67 20 66 69 6c 65 73 20 | 77 69 6c 6c 20 4e 4f 54 |g files |will NOT|
|00000490| 20 62 65 20 6f 76 65 72 | 77 72 69 74 74 65 6e 0a | be over|written.|
|000004a0| 23 0a 23 20 54 68 69 73 | 20 73 68 61 72 20 63 6f |#.# This| shar co|
|000004b0| 6e 74 61 69 6e 73 3a 0a | 23 20 6c 65 6e 67 74 68 |ntains:.|# length|
|000004c0| 20 20 6d 6f 64 65 20 20 | 20 20 20 20 20 6e 61 6d |  mode  |     nam|
|000004d0| 65 0a 23 20 2d 2d 2d 2d | 2d 2d 20 2d 2d 2d 2d 2d |e.# ----|-- -----|
|000004e0| 2d 2d 2d 2d 2d 20 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |----- --|--------|
|000004f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000500| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000510| 0a 23 20 20 20 33 35 30 | 34 20 2d 72 77 2d 72 2d |.#   350|4 -rw-r-|
|00000520| 2d 72 2d 2d 20 52 45 41 | 44 4d 45 0a 23 20 20 20 |-r-- REA|DME.#   |
|00000530| 33 37 35 35 20 2d 72 2d | 2d 72 2d 2d 72 2d 2d 20 |3755 -r-|-r--r-- |
|00000540| 73 70 6c 61 79 2e 64 65 | 66 0a 23 20 20 20 20 35 |splay.de|f.#    5|
|00000550| 30 35 20 2d 72 77 2d 72 | 2d 2d 72 2d 2d 20 73 70 |05 -rw-r|--r-- sp|
|00000560| 6c 61 79 49 74 65 6d 2e | 64 65 66 0a 23 20 20 31 |layItem.|def.#  1|
|00000570| 31 35 32 34 20 2d 72 2d | 2d 72 2d 2d 72 2d 2d 20 |1524 -r-|-r--r-- |
|00000580| 73 70 6c 61 79 2e 6d 6f | 64 0a 23 20 20 20 20 34 |splay.mo|d.#    4|
|00000590| 34 37 20 2d 72 77 2d 72 | 2d 2d 72 2d 2d 20 73 70 |47 -rw-r|--r-- sp|
|000005a0| 6c 61 79 49 74 65 6d 2e | 6d 6f 64 0a 23 20 20 20 |layItem.|mod.#   |
|000005b0| 32 32 34 32 20 2d 72 77 | 2d 72 2d 2d 72 2d 2d 20 |2242 -rw|-r--r-- |
|000005c0| 73 70 6c 61 79 54 65 73 | 74 2e 6d 6f 64 0a 23 0a |splayTes|t.mod.#.|
|000005d0| 69 66 20 74 6f 75 63 68 | 20 32 3e 26 31 20 7c 20 |if touch| 2>&1 | |
|000005e0| 66 67 72 65 70 20 27 5b | 2d 61 6d 63 5d 27 20 3e |fgrep '[|-amc]' >|
|000005f0| 20 2f 64 65 76 2f 6e 75 | 6c 6c 0a 20 74 68 65 6e | /dev/nu|ll. then|
|00000600| 20 54 4f 55 43 48 3d 74 | 6f 75 63 68 0a 20 65 6c | TOUCH=t|ouch. el|
|00000610| 73 65 20 54 4f 55 43 48 | 3d 74 72 75 65 0a 66 69 |se TOUCH|=true.fi|
|00000620| 0a 23 20 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |.# =====|========|
|00000630| 20 52 45 41 44 4d 45 20 | 3d 3d 3d 3d 3d 3d 3d 3d | README |========|
|00000640| 3d 3d 3d 3d 3d 3d 0a 69 | 66 20 74 65 73 74 20 58 |======.i|f test X|
|00000650| 22 24 31 22 20 21 3d 20 | 58 22 2d 63 22 20 2d 61 |"$1" != |X"-c" -a|
|00000660| 20 2d 66 20 27 52 45 41 | 44 4d 45 27 3b 20 74 68 | -f 'REA|DME'; th|
|00000670| 65 6e 0a 09 65 63 68 6f | 20 22 46 69 6c 65 20 61 |en..echo| "File a|
|00000680| 6c 72 65 61 64 79 20 65 | 78 69 73 74 73 3a 20 73 |lready e|xists: s|
|00000690| 6b 69 70 70 69 6e 67 20 | 27 52 45 41 44 4d 45 27 |kipping |'README'|
|000006a0| 22 0a 65 6c 73 65 0a 65 | 63 68 6f 20 22 78 20 2d |".else.e|cho "x -|
|000006b0| 20 65 78 74 72 61 63 74 | 69 6e 67 20 52 45 41 44 | extract|ing READ|
|000006c0| 4d 45 20 28 54 65 78 74 | 29 22 0a 73 65 64 20 27 |ME (Text|)".sed '|
|000006d0| 73 2f 5e 58 2f 2f 27 20 | 3c 3c 20 27 53 48 41 52 |s/^X//' |<< 'SHAR|
|000006e0| 5f 45 4f 46 27 20 3e 20 | 52 45 41 44 4d 45 20 26 |_EOF' > |README &|
|000006f0| 26 0a 58 53 50 4c 41 59 | 20 54 52 45 45 20 4c 49 |&.XSPLAY| TREE LI|
|00000700| 42 52 41 52 59 0a 58 3d | 3d 3d 3d 3d 3d 3d 3d 3d |BRARY.X=|========|
|00000710| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 0a 58 0a 58 54 68 69 |========|=.X.XThi|
|00000720| 73 20 6c 69 62 72 61 72 | 79 20 63 6f 6e 74 61 69 |s librar|y contai|
|00000730| 6e 73 20 74 68 65 20 66 | 6f 6c 6c 6f 77 69 6e 67 |ns the f|ollowing|
|00000740| 20 66 69 6c 65 73 3a 0a | 58 0a 58 09 73 70 6c 61 | files:.|X.X.spla|
|00000750| 79 2e 64 65 66 09 44 65 | 66 69 6e 69 74 69 6f 6e |y.def.De|finition|
|00000760| 20 6d 6f 64 75 6c 65 20 | 66 6f 72 20 74 68 65 20 | module |for the |
|00000770| 73 70 6c 61 79 20 74 72 | 65 65 20 6c 69 62 72 61 |splay tr|ee libra|
|00000780| 72 79 0a 58 09 73 70 6c | 61 79 2e 6d 6f 64 20 09 |ry.X.spl|ay.mod .|
|00000790| 49 6d 70 6c 65 6d 65 6e | 74 61 74 69 6f 6e 20 6f |Implemen|tation o|
|000007a0| 66 20 73 70 6c 61 79 20 | 74 72 65 65 0a 58 09 73 |f splay |tree.X.s|
|000007b0| 70 6c 61 79 49 74 65 6d | 2e 64 65 66 20 09 44 65 |playItem|.def .De|
|000007c0| 66 69 6e 69 74 69 6f 6e | 20 6d 6f 64 75 6c 65 20 |finition| module |
|000007d0| 66 6f 72 20 64 61 74 61 | 20 73 74 6f 72 65 64 20 |for data| stored |
|000007e0| 69 6e 20 74 68 65 20 74 | 72 65 65 0a 58 09 73 70 |in the t|ree.X.sp|
|000007f0| 6c 61 79 49 74 65 6d 2e | 6d 6f 64 09 49 6d 70 6c |layItem.|mod.Impl|
|00000800| 65 6d 65 6e 74 61 74 69 | 6f 6e 20 6d 6f 64 75 6c |ementati|on modul|
|00000810| 65 20 66 6f 72 20 64 61 | 74 61 20 73 74 6f 72 65 |e for da|ta store|
|00000820| 64 20 69 6e 0a 58 09 09 | 09 74 68 65 20 74 72 65 |d in.X..|.the tre|
|00000830| 65 0a 58 09 73 70 6c 61 | 79 54 65 73 74 2e 6d 6f |e.X.spla|yTest.mo|
|00000840| 64 09 41 20 73 68 6f 72 | 74 20 74 65 73 74 20 70 |d.A shor|t test p|
|00000850| 72 6f 67 72 61 6d 0a 58 | 0a 58 0a 58 46 6f 72 20 |rogram.X|.X.XFor |
|00000860| 61 20 66 75 6c 6c 20 69 | 6e 74 72 6f 64 75 63 74 |a full i|ntroduct|
|00000870| 69 6f 6e 20 74 6f 20 73 | 70 6c 61 79 20 74 72 65 |ion to s|play tre|
|00000880| 65 73 20 73 65 65 0a 58 | 0a 58 09 20 20 20 20 20 |es see.X|.X.     |
|00000890| 20 20 20 20 20 20 20 20 | 20 20 20 53 6c 65 61 74 |        |   Sleat|
|000008a0| 6f 72 20 44 2e 20 61 6e | 64 20 54 61 72 6a 61 6e |or D. an|d Tarjan|
|000008b0| 20 52 2e 20 22 53 65 6c | 66 20 61 64 6a 75 73 74 | R. "Sel|f adjust|
|000008c0| 69 6e 67 0a 58 09 09 09 | 62 69 6e 61 72 79 20 74 |ing.X...|binary t|
|000008d0| 72 65 65 73 22 2c 20 4a | 41 43 4d 20 56 6f 6c 20 |rees", J|ACM Vol |
|000008e0| 33 32 2e 20 4e 6f 20 33 | 2c 20 31 39 38 35 2c 20 |32. No 3|, 1985, |
|000008f0| 70 70 20 36 35 32 2d 0a | 58 09 09 09 36 38 36 2e |pp 652-.|X...686.|
|00000900| 0a 58 0a 58 0a 58 49 6e | 20 73 68 6f 72 74 2c 20 |.X.X.XIn| short, |
|00000910| 73 70 6c 61 79 20 74 72 | 65 65 73 20 61 72 65 20 |splay tr|ees are |
|00000920| 61 20 66 6f 72 6d 20 6f | 66 20 62 61 6c 61 6e 63 |a form o|f balanc|
|00000930| 65 64 20 62 69 6e 61 72 | 79 20 74 72 65 65 73 20 |ed binar|y trees |
|00000940| 77 68 69 63 68 0a 58 6d | 6f 76 65 73 20 65 76 65 |which.Xm|oves eve|
|00000950| 72 79 20 61 63 63 65 73 | 73 65 64 20 6e 6f 64 65 |ry acces|sed node|
|00000960| 20 74 6f 20 74 68 65 20 | 72 6f 6f 74 2e 20 54 68 | to the |root. Th|
|00000970| 69 73 20 6d 65 61 6e 73 | 20 74 68 61 74 20 74 68 |is means| that th|
|00000980| 65 20 74 72 65 65 0a 58 | 77 69 6c 6c 20 62 65 68 |e tree.X|will beh|
|00000990| 61 76 65 20 76 65 72 79 | 20 77 65 6c 6c 20 77 68 |ave very| well wh|
|000009a0| 65 6e 20 74 68 65 72 65 | 20 69 73 20 73 6f 6d 65 |en there| is some|
|000009b0| 20 66 6f 72 6d 20 6f 66 | 20 6c 6f 63 61 6c 69 74 | form of| localit|
|000009c0| 79 20 69 6e 20 74 68 65 | 0a 58 64 61 74 61 20 70 |y in the|.Xdata p|
|000009d0| 72 6f 63 65 73 73 65 64 | 2e 20 46 75 72 74 68 65 |rocessed|. Furthe|
|000009e0| 72 6d 6f 72 65 20 69 74 | 20 63 61 6e 20 62 65 20 |rmore it| can be |
|000009f0| 73 68 6f 77 6e 20 74 68 | 61 74 20 74 68 65 20 61 |shown th|at the a|
|00000a00| 6d 6f 72 74 69 7a 65 64 | 0a 58 61 63 63 65 73 73 |mortized|.Xaccess|
|00000a10| 20 63 6f 73 74 20 69 73 | 20 4f 28 6c 67 6e 29 20 | cost is| O(lgn) |
|00000a20| 66 6f 72 20 74 68 65 20 | 62 61 73 69 63 20 6f 70 |for the |basic op|
|00000a30| 65 72 61 74 69 6f 6e 73 | 20 28 69 6e 73 65 72 74 |erations| (insert|
|00000a40| 2c 20 64 65 6c 65 74 65 | 20 61 6e 64 0a 58 66 69 |, delete| and.Xfi|
|00000a50| 6e 64 29 2e 0a 58 0a 58 | 54 68 65 20 73 70 6c 61 |nd)..X.X|The spla|
|00000a60| 79 20 74 72 65 65 20 61 | 6c 73 6f 20 68 61 73 20 |y tree a|lso has |
|00000a70| 74 68 65 20 6e 69 63 65 | 20 70 72 6f 70 65 72 74 |the nice| propert|
|00000a80| 79 20 74 68 61 74 20 61 | 6e 20 69 74 65 6d 20 61 |y that a|n item a|
|00000a90| 63 63 65 73 73 65 64 0a | 58 74 20 6f 70 65 72 61 |ccessed.|Xt opera|
|00000aa0| 74 69 6f 6e 73 20 61 67 | 6f 20 63 61 6e 20 62 65 |tions ag|o can be|
|00000ab0| 20 6c 6f 63 61 74 65 64 | 20 69 6e 20 4f 28 6c 67 | located| in O(lg|
|00000ac0| 74 29 20 74 69 6d 65 2e | 0a 58 0a 58 41 6c 6c 20 |t) time.|.X.XAll |
|00000ad0| 69 6e 20 61 6c 6c 20 70 | 72 61 63 74 69 63 61 6c |in all p|ractical|
|00000ae0| 20 74 65 73 74 73 20 68 | 61 76 65 20 73 68 6f 77 | tests h|ave show|
|00000af0| 6e 20 73 70 6c 61 79 20 | 74 72 65 65 73 20 74 6f |n splay |trees to|
|00000b00| 20 62 65 20 61 6e 20 65 | 78 63 65 6c 6c 65 6e 74 | be an e|xcellent|
|00000b10| 0a 58 73 75 62 73 74 69 | 74 75 74 69 6f 6e 20 66 |.Xsubsti|tution f|
|00000b20| 6f 72 20 74 68 65 20 6d | 6f 72 65 20 77 65 6c 6c |or the m|ore well|
|00000b30| 20 6b 6e 6f 77 6e 20 72 | 2d 62 2d 74 72 65 65 73 | known r|-b-trees|
|00000b40| 20 6f 72 20 73 6f 6d 65 | 20 6f 74 68 65 72 20 76 | or some| other v|
|00000b50| 61 72 69 61 74 69 6f 6e | 73 0a 58 6f 6e 20 62 61 |ariation|s.Xon ba|
|00000b60| 6c 61 6e 63 65 64 20 74 | 72 65 65 73 2e 0a 58 0a |lanced t|rees..X.|
|00000b70| 58 53 69 6e 63 65 20 6d | 6f 64 75 6c 61 32 20 6c |XSince m|odula2 l|
|00000b80| 61 63 6b 73 20 70 6f 73 | 73 69 62 69 6c 69 74 69 |acks pos|sibiliti|
|00000b90| 65 73 20 74 6f 20 63 72 | 65 61 74 65 20 67 65 6e |es to cr|eate gen|
|00000ba0| 65 72 69 63 20 6d 6f 64 | 75 6c 65 73 20 6d 79 0a |eric mod|ules my.|
|00000bb0| 58 61 70 70 72 6f 61 63 | 68 20 69 73 20 74 6f 20 |Xapproac|h is to |
|00000bc0| 70 72 6f 76 69 64 65 20 | 61 20 73 65 70 61 72 61 |provide |a separa|
|00000bd0| 74 65 20 6d 6f 64 75 6c | 65 20 77 68 69 63 68 20 |te modul|e which |
|00000be0| 67 69 76 65 73 20 74 68 | 65 20 6f 70 65 72 61 74 |gives th|e operat|
|00000bf0| 69 6f 6e 73 0a 58 61 6e | 64 20 74 79 70 65 20 6f |ions.Xan|d type o|
|00000c00| 66 20 74 68 65 20 65 6c | 65 6d 65 6e 74 20 73 74 |f the el|ement st|
|00000c10| 6f 72 65 64 20 69 6e 20 | 74 68 65 20 74 72 65 65 |ored in |the tree|
|00000c20| 2e 20 54 68 69 73 20 6d | 6f 64 75 6c 65 0a 58 28 |. This m|odule.X(|
|00000c30| 68 65 72 65 20 63 61 6c | 6c 65 64 20 73 70 6c 61 |here cal|led spla|
|00000c40| 79 49 74 65 6d 29 20 6d | 75 73 74 20 73 75 70 70 |yItem) m|ust supp|
|00000c50| 6f 72 74 20 6f 70 65 72 | 61 74 69 6f 6e 73 20 74 |ort oper|ations t|
|00000c60| 6f 20 63 72 65 61 74 65 | 2c 20 64 65 73 74 72 6f |o create|, destro|
|00000c70| 79 0a 58 61 6e 64 20 63 | 6f 6d 70 61 72 65 20 65 |y.Xand c|ompare e|
|00000c80| 6c 65 6d 65 6e 74 73 2e | 20 54 68 69 73 20 73 63 |lements.| This sc|
|00000c90| 68 65 6d 65 20 70 72 6f | 76 69 64 65 73 20 66 6f |heme pro|vides fo|
|00000ca0| 72 20 61 20 66 61 69 72 | 6c 79 20 67 65 6e 65 72 |r a fair|ly gener|
|00000cb0| 69 63 0a 58 69 6d 70 6c | 65 6d 65 6e 74 61 74 69 |ic.Ximpl|ementati|
|00000cc0| 6f 6e 2c 20 28 73 65 65 | 20 74 68 65 20 74 65 73 |on, (see| the tes|
|00000cd0| 74 20 70 72 6f 67 72 61 | 6d 20 61 6e 64 20 73 70 |t progra|m and sp|
|00000ce0| 6c 61 79 49 74 65 6d 2e | 5b 6d 6f 64 2c 64 65 66 |layItem.|[mod,def|
|00000cf0| 5d 29 0a 58 49 6e 20 74 | 68 65 20 74 65 73 74 20 |]).XIn t|he test |
|00000d00| 70 72 6f 67 72 61 6d 20 | 73 75 70 70 6c 69 65 64 |program |supplied|
|00000d10| 20 74 68 65 20 63 72 65 | 61 74 65 20 61 6e 64 20 | the cre|ate and |
|00000d20| 64 65 73 74 72 6f 79 20 | 72 6f 75 74 69 6e 65 73 |destroy |routines|
|00000d30| 0a 58 61 72 65 20 65 6d | 70 74 79 20 73 69 6e 63 |.Xare em|pty sinc|
|00000d40| 65 20 74 68 65 20 6f 62 | 6a 65 63 74 73 20 64 6f |e the ob|jects do|
|00000d50| 65 73 6e 27 74 20 75 73 | 65 20 61 6e 79 20 64 79 |esn't us|e any dy|
|00000d60| 6e 61 6d 69 63 20 6d 65 | 6d 6f 72 79 2e 20 54 68 |namic me|mory. Th|
|00000d70| 65 0a 58 70 72 69 7a 65 | 20 74 6f 20 70 61 79 20 |e.Xprize| to pay |
|00000d80| 66 6f 72 20 74 68 65 20 | 67 65 6e 65 72 69 63 20 |for the |generic |
|00000d90| 73 74 72 75 63 74 75 72 | 65 20 69 73 20 61 20 6c |structur|e is a l|
|00000da0| 69 74 74 6c 65 20 6f 76 | 65 72 68 65 61 64 20 66 |ittle ov|erhead f|
|00000db0| 6f 72 0a 58 65 61 63 68 | 20 63 6f 6d 70 61 72 69 |or.Xeach| compari|
|00000dc0| 73 6f 6e 2e 0a 58 0a 58 | 49 66 20 73 70 65 65 64 |son..X.X|If speed|
|00000dd0| 20 69 73 20 65 73 73 65 | 6e 74 69 61 6c 20 28 61 | is esse|ntial (a|
|00000de0| 73 20 61 6c 77 61 79 73 | 29 20 79 6f 75 20 6d 61 |s always|) you ma|
|00000df0| 79 20 68 61 72 64 20 63 | 6f 64 65 20 74 68 65 20 |y hard c|ode the |
|00000e00| 63 6f 6d 70 61 72 69 73 | 6f 6e 0a 58 62 65 65 74 |comparis|on.Xbeet|
|00000e10| 77 65 65 6e 20 65 6c 65 | 6d 65 6e 74 73 20 69 6e |ween ele|ments in|
|00000e20| 20 74 68 65 20 69 6d 70 | 6c 65 6d 65 6e 74 61 74 | the imp|lementat|
|00000e30| 69 6f 6e 20 69 66 20 79 | 6f 75 20 61 72 65 20 6f |ion if y|ou are o|
|00000e40| 6e 6c 79 20 77 6f 72 6b | 69 6e 67 0a 58 77 69 74 |nly work|ing.Xwit|
|00000e50| 68 20 73 69 6d 70 6c 65 | 20 74 79 70 65 73 20 6c |h simple| types l|
|00000e60| 69 6b 65 20 69 6e 74 65 | 67 65 72 73 20 6f 72 20 |ike inte|gers or |
|00000e70| 73 6f 6d 65 74 68 69 6e | 67 20 6c 69 6b 65 20 74 |somethin|g like t|
|00000e80| 68 61 74 2e 20 4f 72 20 | 79 6f 75 0a 58 6d 69 67 |hat. Or |you.Xmig|
|00000e90| 68 74 20 77 61 6e 74 20 | 74 6f 20 72 65 77 72 69 |ht want |to rewri|
|00000ea0| 74 65 20 74 68 65 20 63 | 6f 64 65 20 74 6f 20 68 |te the c|ode to h|
|00000eb0| 61 6e 64 6c 65 20 74 68 | 65 20 6d 6f 72 65 20 63 |andle th|e more c|
|00000ec0| 6c 61 73 73 69 63 0a 58 | 76 61 72 69 61 74 69 6f |lassic.X|variatio|
|00000ed0| 6e 20 77 69 74 68 20 61 | 20 6b 65 79 20 61 6e 64 |n with a| key and|
|00000ee0| 20 61 20 67 65 6e 65 72 | 69 63 20 70 6f 69 6e 74 | a gener|ic point|
|00000ef0| 65 72 20 73 74 6f 72 65 | 64 20 69 6e 20 65 61 63 |er store|d in eac|
|00000f00| 68 0a 58 6e 6f 64 65 2e | 20 54 68 65 73 65 20 63 |h.Xnode.| These c|
|00000f10| 68 61 6e 67 65 73 20 61 | 72 65 20 74 72 69 76 69 |hanges a|re trivi|
|00000f20| 61 6c 20 61 6e 64 20 73 | 68 6f 75 6c 64 6e 27 74 |al and s|houldn't|
|00000f30| 20 74 61 6b 65 20 6c 6f | 6e 67 0a 58 74 69 6d 65 | take lo|ng.Xtime|
|00000f40| 20 74 6f 20 64 6f 2e 0a | 58 0a 58 54 6f 20 74 68 | to do..|X.XTo th|
|00000f50| 65 20 62 65 73 74 20 6f | 66 20 6d 79 20 6b 6e 6f |e best o|f my kno|
|00000f60| 77 6c 65 64 67 65 20 74 | 68 69 73 20 63 6f 64 65 |wledge t|his code|
|00000f70| 20 69 73 20 62 75 67 20 | 66 72 65 65 2e 20 42 75 | is bug |free. Bu|
|00000f80| 74 20 69 66 20 79 6f 75 | 0a 58 64 6f 20 64 69 73 |t if you|.Xdo dis|
|00000f90| 63 6f 76 65 72 20 73 6f | 6d 20 69 72 72 65 67 75 |cover so|m irregu|
|00000fa0| 6c 61 72 69 74 69 65 73 | 20 70 6c 65 61 73 65 20 |larities| please |
|00000fb0| 64 72 6f 70 20 6d 65 20 | 61 20 6e 6f 74 65 2e 0a |drop me |a note..|
|00000fc0| 58 0a 58 09 4a 6f 68 61 | 6e 20 50 65 72 73 73 6f |X.X.Joha|n Persso|
|00000fd0| 6e 20 28 6c 6a 70 40 73 | 6d 2e 6c 75 74 68 2e 73 |n (ljp@s|m.luth.s|
|00000fe0| 65 29 0a 58 0a 58 0a 58 | 2d 2d 2d 2d 0a 58 0a 58 |e).X.X.X|----.X.X|
|00000ff0| 4e 6f 74 65 30 3a 20 59 | 6f 75 20 6d 61 79 20 65 |Note0: Y|ou may e|
|00001000| 6e 63 6f 75 6e 74 65 72 | 20 73 6f 6d 65 20 64 69 |ncounter| some di|
|00001010| 66 66 69 63 75 6c 74 69 | 65 73 20 77 68 65 6e 20 |fficulti|es when |
|00001020| 74 72 79 69 6e 67 20 74 | 6f 0a 58 63 6f 6d 70 69 |trying t|o.Xcompi|
|00001030| 6c 65 20 74 68 65 20 27 | 73 70 6c 61 79 54 65 73 |le the '|splayTes|
|00001040| 74 2e 6d 6f 64 27 20 64 | 75 65 20 74 6f 20 74 68 |t.mod' d|ue to th|
|00001050| 65 20 6c 61 63 6b 20 6f | 66 20 73 74 61 6e 64 61 |e lack o|f standa|
|00001060| 72 64 20 62 65 74 77 65 | 65 6e 0a 58 64 69 66 66 |rd betwe|en.Xdiff|
|00001070| 65 72 65 6e 74 20 63 6f | 6d 70 69 6c 65 72 73 20 |erent co|mpilers |
|00001080| 69 6e 20 74 68 65 69 72 | 20 49 2f 4f 20 6c 69 62 |in their| I/O lib|
|00001090| 72 61 72 69 65 73 2e 20 | 54 68 6f 75 67 68 20 69 |raries. |Though i|
|000010a0| 74 20 73 68 6f 75 6c 64 | 20 62 65 0a 58 66 61 69 |t should| be.Xfai|
|000010b0| 72 6c 79 20 73 69 6d 70 | 65 6c 20 6a 75 73 74 20 |rly simp|el just |
|000010c0| 74 6f 20 63 68 61 6e 67 | 65 20 74 68 65 20 6e 61 |to chang|e the na|
|000010d0| 6d 65 20 74 6f 20 79 6f | 75 72 20 6f 77 6e 20 72 |me to yo|ur own r|
|000010e0| 6f 75 74 69 6e 65 73 20 | 77 68 69 63 68 0a 58 70 |outines |which.Xp|
|000010f0| 72 69 6e 74 73 20 61 20 | 73 74 72 69 6e 67 2c 20 |rints a |string, |
|00001100| 61 20 63 61 72 64 69 6e | 61 6c 20 61 6e 64 20 73 |a cardin|al and s|
|00001110| 6f 20 6f 6e 2e 0a 58 0a | 58 4e 6f 74 65 31 3a 20 |o on..X.|XNote1: |
|00001120| 54 68 69 73 20 63 6f 64 | 65 20 69 6d 70 6c 65 6d |This cod|e implem|
|00001130| 65 6e 74 73 20 74 68 65 | 20 6d 6f 72 65 20 65 66 |ents the| more ef|
|00001140| 66 69 63 69 65 6e 74 20 | 74 6f 70 2d 64 6f 77 6e |ficient |top-down|
|00001150| 20 73 70 6c 61 79 69 6e | 67 20 61 73 0a 58 64 65 | splayin|g as.Xde|
|00001160| 73 63 72 69 62 65 64 20 | 69 6e 20 73 65 63 74 69 |scribed |in secti|
|00001170| 6f 6e 20 34 20 6f 66 20 | 6f 72 69 67 69 6e 61 6c |on 4 of |original|
|00001180| 20 70 61 70 65 72 20 28 | 73 65 65 20 61 62 6f 76 | paper (|see abov|
|00001190| 65 29 2e 0a 58 0a 58 4e | 6f 74 65 32 3a 20 54 68 |e)..X.XN|ote2: Th|
|000011a0| 69 73 20 69 6d 70 6c 65 | 6d 65 6e 74 61 74 69 6f |is imple|mentatio|
|000011b0| 6e 20 68 61 73 20 62 65 | 65 6e 20 61 75 67 75 6d |n has be|en augum|
|000011c0| 65 6e 74 65 64 20 77 69 | 74 68 20 6f 70 65 72 61 |ented wi|th opera|
|000011d0| 74 69 6f 6e 73 0a 58 74 | 6f 20 72 65 74 72 69 76 |tions.Xt|o retriv|
|000011e0| 65 20 74 68 65 20 72 61 | 6e 6b 20 6f 66 20 74 68 |e the ra|nk of th|
|000011f0| 65 20 65 6c 65 6d 65 6e | 74 20 73 74 6f 72 65 64 |e elemen|t stored|
|00001200| 20 69 6e 20 74 68 65 20 | 74 72 65 65 2c 20 28 69 | in the |tree, (i|
|00001210| 2e 65 20 74 68 65 69 72 | 0a 58 70 6f 73 69 74 69 |.e their|.Xpositi|
|00001220| 6f 6e 20 77 68 65 6e 20 | 6d 61 6b 69 6e 67 20 61 |on when |making a|
|00001230| 6e 20 69 6e 6f 72 64 65 | 72 20 74 72 65 65 20 77 |n inorde|r tree w|
|00001240| 61 6c 6b 29 2e 20 54 68 | 69 73 20 6f 70 65 72 61 |alk). Th|is opera|
|00001250| 74 69 6f 6e 73 20 74 61 | 6b 65 20 74 69 6d 65 0a |tions ta|ke time.|
|00001260| 58 4f 28 6c 67 6e 29 2c | 20 62 75 74 20 74 6f 20 |XO(lgn),| but to |
|00001270| 61 63 68 69 76 65 20 74 | 68 69 73 20 77 65 20 68 |achive t|his we h|
|00001280| 61 76 65 20 74 6f 20 70 | 61 79 20 61 20 70 72 69 |ave to p|ay a pri|
|00001290| 7a 65 20 77 68 65 6e 20 | 6d 61 6b 69 6e 67 0a 58 |ze when |making.X|
|000012a0| 74 68 65 20 62 61 73 69 | 63 20 6f 70 65 72 61 74 |the basi|c operat|
|000012b0| 69 6f 6e 73 20 28 69 6e | 73 65 72 74 2c 64 65 6c |ions (in|sert,del|
|000012c0| 65 74 65 2c 66 69 6e 64 | 29 2c 20 74 68 69 73 20 |ete,find|), this |
|000012d0| 6d 65 61 6e 73 20 74 68 | 61 74 20 74 68 65 73 65 |means th|at these|
|000012e0| 0a 58 6f 70 65 72 61 74 | 69 6f 6e 73 20 6e 6f 77 |.Xoperat|ions now|
|000012f0| 20 74 61 6b 65 20 4f 28 | 6e 29 20 74 69 6d 65 20 | take O(|n) time |
|00001300| 69 6e 73 74 65 61 64 2e | 20 49 66 20 79 6f 75 20 |instead.| If you |
|00001310| 66 69 6e 64 20 74 68 69 | 73 20 75 6e 65 78 63 65 |find thi|s unexce|
|00001320| 70 74 61 62 6c 65 0a 58 | 79 6f 75 20 6d 61 79 20 |ptable.X|you may |
|00001330| 6d 6f 64 69 66 79 20 74 | 68 65 20 73 6f 75 72 63 |modify t|he sourc|
|00001340| 65 20 62 79 20 73 69 6d | 70 6c 79 20 72 65 6d 6f |e by sim|ply remo|
|00001350| 76 69 6e 67 20 74 68 65 | 20 63 61 6c 6c 73 20 74 |ving the| calls t|
|00001360| 6f 20 27 66 69 78 52 61 | 6e 6b 27 20 61 74 0a 58 |o 'fixRa|nk' at.X|
|00001370| 74 68 65 20 65 6e 64 20 | 6f 66 20 28 69 6e 73 65 |the end |of (inse|
|00001380| 72 74 2c 64 65 6c 65 74 | 65 2c 66 69 6e 64 29 2e |rt,delet|e,find).|
|00001390| 20 4e 4f 54 45 3a 20 74 | 68 69 73 20 77 69 6c 6c | NOTE: t|his will|
|000013a0| 20 6d 61 6b 65 20 74 68 | 65 20 72 61 6e 6b 20 6f | make th|e rank o|
|000013b0| 70 65 72 61 74 69 6f 6e | 73 0a 58 75 6e 75 73 61 |peration|s.Xunusa|
|000013c0| 62 6c 65 21 20 54 68 65 | 20 62 61 73 69 63 20 70 |ble! The| basic p|
|000013d0| 72 6f 62 6c 65 6d 20 69 | 73 20 74 68 61 74 20 77 |roblem i|s that w|
|000013e0| 65 20 6d 75 73 74 20 6d | 61 69 6e 74 61 69 6e 20 |e must m|aintain |
|000013f0| 74 68 65 20 77 65 69 67 | 68 74 20 6f 66 0a 58 65 |the weig|ht of.Xe|
|00001400| 61 63 68 20 65 6c 65 6d | 65 6e 74 2c 20 61 6e 64 |ach elem|ent, and|
|00001410| 20 65 61 63 68 20 62 61 | 73 69 63 20 6f 70 65 72 | each ba|sic oper|
|00001420| 61 74 69 6f 6e 73 20 72 | 65 73 74 72 75 63 74 75 |ations r|estructu|
|00001430| 72 65 20 74 68 65 20 74 | 72 65 65 20 73 6f 20 77 |re the t|ree so w|
|00001440| 65 0a 58 6d 75 73 74 20 | 72 65 63 61 6c 63 75 6c |e.Xmust |recalcul|
|00001450| 61 74 65 20 74 68 65 20 | 77 65 69 67 68 74 73 20 |ate the |weights |
|00001460| 66 6f 72 20 65 61 63 68 | 20 6e 6f 64 65 20 62 6f |for each| node bo|
|00001470| 74 74 6f 6d 20 75 70 2e | 0a 58 0a 58 0a 58 2d 2d |ttom up.|.X.X.X--|
|00001480| 2d 0a 58 4a 6f 68 61 6e | 20 50 65 72 73 73 6f 6e |-.XJohan| Persson|
|00001490| 09 09 09 09 45 2d 6d 61 | 69 6c 3a 20 6c 6a 70 40 |....E-ma|il: ljp@|
|000014a0| 73 6d 2e 6c 75 74 68 2e | 73 65 0a 58 44 65 70 74 |sm.luth.|se.XDept|
|000014b0| 2e 20 6f 66 20 43 6f 6d | 70 75 74 65 72 20 53 63 |. of Com|puter Sc|
|000014c0| 69 65 6e 63 65 0a 58 54 | 65 63 68 6e 69 63 61 6c |ience.XT|echnical|
|000014d0| 20 55 6e 69 76 65 72 73 | 69 74 79 20 6f 66 20 4c | Univers|ity of L|
|000014e0| 75 6c 65 61 0a 58 53 2d | 39 35 31 20 38 37 20 4c |ulea.XS-|951 87 L|
|000014f0| 75 6c 65 61 0a 58 09 09 | 09 0a 53 48 41 52 5f 45 |ulea.X..|..SHAR_E|
|00001500| 4f 46 0a 24 54 4f 55 43 | 48 20 2d 61 6d 20 31 31 |OF.$TOUC|H -am 11|
|00001510| 32 32 31 34 30 30 39 32 | 20 52 45 41 44 4d 45 20 |22140092| README |
|00001520| 26 26 0a 63 68 6d 6f 64 | 20 30 36 34 34 20 52 45 |&&.chmod| 0644 RE|
|00001530| 41 44 4d 45 20 7c 7c 0a | 65 63 68 6f 20 22 72 65 |ADME ||.|echo "re|
|00001540| 73 74 6f 72 65 20 6f 66 | 20 52 45 41 44 4d 45 20 |store of| README |
|00001550| 66 61 69 6c 65 64 22 0a | 73 65 74 20 60 77 63 20 |failed".|set `wc |
|00001560| 2d 63 20 52 45 41 44 4d | 45 60 3b 57 63 5f 63 3d |-c READM|E`;Wc_c=|
|00001570| 24 31 0a 69 66 20 74 65 | 73 74 20 22 24 57 63 5f |$1.if te|st "$Wc_|
|00001580| 63 22 20 21 3d 20 22 33 | 35 30 34 22 3b 20 74 68 |c" != "3|504"; th|
|00001590| 65 6e 0a 09 65 63 68 6f | 20 6f 72 69 67 69 6e 61 |en..echo| origina|
|000015a0| 6c 20 73 69 7a 65 20 33 | 35 30 34 2c 20 63 75 72 |l size 3|504, cur|
|000015b0| 72 65 6e 74 20 73 69 7a | 65 20 24 57 63 5f 63 0a |rent siz|e $Wc_c.|
|000015c0| 66 69 0a 66 69 0a 23 20 | 3d 3d 3d 3d 3d 3d 3d 3d |fi.fi.# |========|
|000015d0| 3d 3d 3d 3d 3d 20 73 70 | 6c 61 79 2e 64 65 66 20 |===== sp|lay.def |
|000015e0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 0a 69 |========|======.i|
|000015f0| 66 20 74 65 73 74 20 58 | 22 24 31 22 20 21 3d 20 |f test X|"$1" != |
|00001600| 58 22 2d 63 22 20 2d 61 | 20 2d 66 20 27 73 70 6c |X"-c" -a| -f 'spl|
|00001610| 61 79 2e 64 65 66 27 3b | 20 74 68 65 6e 0a 09 65 |ay.def';| then..e|
|00001620| 63 68 6f 20 22 46 69 6c | 65 20 61 6c 72 65 61 64 |cho "Fil|e alread|
|00001630| 79 20 65 78 69 73 74 73 | 3a 20 73 6b 69 70 70 69 |y exists|: skippi|
|00001640| 6e 67 20 27 73 70 6c 61 | 79 2e 64 65 66 27 22 0a |ng 'spla|y.def'".|
|00001650| 65 6c 73 65 0a 65 63 68 | 6f 20 22 78 20 2d 20 65 |else.ech|o "x - e|
|00001660| 78 74 72 61 63 74 69 6e | 67 20 73 70 6c 61 79 2e |xtractin|g splay.|
|00001670| 64 65 66 20 28 54 65 78 | 74 29 22 0a 73 65 64 20 |def (Tex|t)".sed |
|00001680| 27 73 2f 5e 58 2f 2f 27 | 20 3c 3c 20 27 53 48 41 |'s/^X//'| << 'SHA|
|00001690| 52 5f 45 4f 46 27 20 3e | 20 73 70 6c 61 79 2e 64 |R_EOF' >| splay.d|
|000016a0| 65 66 20 26 26 0a 58 44 | 45 46 49 4e 49 54 49 4f |ef &&.XD|EFINITIO|
|000016b0| 4e 20 4d 4f 44 55 4c 45 | 20 73 70 6c 61 79 3b 0a |N MODULE| splay;.|
|000016c0| 58 28 2a 0a 58 09 54 69 | 74 6c 65 3a 09 09 49 6d |X(*.X.Ti|tle:..Im|
|000016d0| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 20 6f 66 20 |plementa|tion of |
|000016e0| 73 70 6c 61 79 20 74 72 | 65 65 73 0a 58 09 4c 61 |splay tr|ees.X.La|
|000016f0| 73 74 20 45 64 69 74 3a | 09 53 75 6e 20 4e 6f 76 |st Edit:|.Sun Nov|
|00001700| 20 32 32 20 31 33 3a 34 | 33 3a 32 33 20 31 39 39 | 22 13:4|3:23 199|
|00001710| 32 0a 58 09 41 75 74 68 | 6f 72 3a 09 09 4a 6f 68 |2.X.Auth|or:..Joh|
|00001720| 61 6e 20 50 65 72 73 73 | 6f 6e 20 61 74 20 6d 79 |an Perss|on at my|
|00001730| 39 0a 58 0a 58 09 53 43 | 43 53 3a 09 09 40 28 23 |9.X.X.SC|CS:..@(#|
|00001740| 29 73 70 6c 61 79 2e 64 | 65 66 20 20 20 20 20 20 |)splay.d|ef      |
|00001750| 20 32 2e 31 20 20 20 20 | 20 39 32 2f 31 31 2f 32 | 2.1    | 92/11/2|
|00001760| 32 0a 58 0a 58 09 44 65 | 73 63 72 69 70 74 69 6f |2.X.X.De|scriptio|
|00001770| 6e 3a 09 54 68 69 73 20 | 63 6f 64 65 20 69 6d 70 |n:.This |code imp|
|00001780| 6c 65 6d 65 6e 74 73 20 | 73 70 6c 61 79 20 74 72 |lements |splay tr|
|00001790| 65 65 20 61 73 20 64 65 | 73 63 72 69 62 65 64 20 |ee as de|scribed |
|000017a0| 69 6e 20 0a 58 09 20 20 | 20 20 20 20 20 20 20 20 |in .X.  |        |
|000017b0| 20 20 20 20 20 20 53 6c | 65 61 74 6f 72 20 44 2e |      Sl|eator D.|
|000017c0| 20 61 6e 64 20 54 61 72 | 6a 61 6e 20 52 2e 20 22 | and Tar|jan R. "|
|000017d0| 53 65 6c 66 20 61 64 6a | 75 73 74 69 6e 67 0a 58 |Self adj|usting.X|
|000017e0| 09 09 09 62 69 6e 61 72 | 79 20 74 72 65 65 73 22 |...binar|y trees"|
|000017f0| 2c 20 4a 41 43 4d 20 56 | 6f 6c 20 33 32 2e 20 4e |, JACM V|ol 32. N|
|00001800| 6f 20 33 2c 20 31 39 38 | 35 2c 20 70 70 20 36 35 |o 3, 198|5, pp 65|
|00001810| 32 2d 0a 58 09 09 09 36 | 38 36 2e 0a 58 09 09 09 |2-.X...6|86..X...|
|00001820| 0a 58 09 09 09 54 68 65 | 20 69 6d 70 6c 65 6d 65 |.X...The| impleme|
|00001830| 6e 61 74 69 6f 6e 20 69 | 73 20 62 61 73 65 64 20 |nation i|s based |
|00001840| 6f 6e 20 61 20 74 6f 70 | 20 64 6f 77 6e 0a 58 20 |on a top| down.X |
|00001850| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001860| 20 20 20 20 20 20 20 73 | 70 6c 61 79 69 6e 67 20 |       s|playing |
|00001870| 68 65 75 72 69 73 74 69 | 63 73 20 61 73 20 64 65 |heuristi|cs as de|
|00001880| 73 63 72 69 62 65 64 20 | 69 6e 20 73 65 63 74 69 |scribed |in secti|
|00001890| 6f 6e 20 34 20 6f 66 20 | 0a 58 09 09 09 74 68 65 |on 4 of |.X...the|
|000018a0| 20 61 72 74 69 63 6c 65 | 2e 0a 58 0a 58 09 4e 6f | article|..X.X.No|
|000018b0| 74 65 3a 09 09 54 68 69 | 73 20 69 6d 70 6c 65 6d |te:..Thi|s implem|
|000018c0| 65 6e 74 61 74 69 6f 6e | 20 61 6c 73 6f 20 73 75 |entation| also su|
|000018d0| 70 70 6f 72 74 73 20 74 | 68 65 20 6f 70 65 72 61 |pports t|he opera|
|000018e0| 74 69 6f 6e 73 0a 58 09 | 09 09 27 67 65 74 52 61 |tions.X.|..'getRa|
|000018f0| 6e 6b 45 6c 65 6d 65 6e | 74 27 20 77 68 69 63 68 |nkElemen|t' which|
|00001900| 20 66 69 6e 64 73 20 74 | 68 65 20 65 6c 65 6d 65 | finds t|he eleme|
|00001910| 6e 74 20 69 6e 20 74 68 | 65 20 74 72 65 65 0a 58 |nt in th|e tree.X|
|00001920| 09 09 09 77 69 74 68 20 | 61 20 67 69 76 65 6e 20 |...with |a given |
|00001930| 72 61 6e 6b 20 69 6e 20 | 4f 28 6c 67 6e 29 20 74 |rank in |O(lgn) t|
|00001940| 69 6d 65 29 20 61 6e 64 | 20 27 67 65 74 52 61 6e |ime) and| 'getRan|
|00001950| 6b 27 2c 20 0a 58 09 09 | 09 28 77 68 69 63 68 20 |k', .X..|.(which |
|00001960| 72 65 74 75 72 6e 73 20 | 74 68 65 20 72 61 6e 6b |returns |the rank|
|00001970| 20 6f 66 20 61 20 67 69 | 76 65 6e 20 65 6c 65 6d | of a gi|ven elem|
|00001980| 65 6e 74 29 0a 58 09 09 | 09 54 6f 20 61 63 68 69 |ent).X..|.To achi|
|00001990| 76 65 20 74 68 69 73 20 | 6f 6e 65 20 6d 75 73 74 |ve this |one must|
|000019a0| 20 73 74 6f 72 65 20 74 | 68 65 20 77 65 69 67 68 | store t|he weigh|
|000019b0| 74 20 6f 66 20 61 20 6e | 6f 64 65 20 69 6e 0a 58 |t of a n|ode in.X|
|000019c0| 09 09 09 65 61 63 68 20 | 6e 6f 64 65 20 28 69 2e |...each |node (i.|
|000019d0| 65 20 74 68 65 20 6e 75 | 6d 62 65 72 20 6f 66 20 |e the nu|mber of |
|000019e0| 64 65 73 63 61 64 65 6e | 74 73 29 2e 20 54 68 69 |descaden|ts). Thi|
|000019f0| 73 0a 58 09 09 09 69 6e | 66 6f 72 6d 61 74 69 6f |s.X...in|formatio|
|00001a00| 6e 20 6d 75 73 74 20 62 | 65 20 75 70 64 61 74 65 |n must b|e update|
|00001a10| 64 20 61 66 74 65 72 20 | 65 61 63 68 20 6f 70 65 |d after |each ope|
|00001a20| 72 61 74 69 6f 6e 0a 58 | 09 09 09 28 69 6e 73 65 |ration.X|...(inse|
|00001a30| 72 74 2c 20 64 65 6c 65 | 74 65 2c 20 66 69 6e 64 |rt, dele|te, find|
|00001a40| 29 2e 20 49 66 20 74 68 | 69 73 20 69 73 20 74 6f |). If th|is is to|
|00001a50| 20 63 6f 73 74 6c 79 0a | 58 09 09 09 28 69 74 20 | costly.|X...(it |
|00001a60| 74 61 6b 65 73 20 4f 28 | 6e 29 29 20 74 68 65 20 |takes O(|n)) the |
|00001a70| 73 6f 75 72 63 65 20 63 | 61 6e 20 62 65 20 6d 6f |source c|an be mo|
|00001a80| 64 69 66 69 65 64 20 74 | 6f 20 72 65 6d 6f 76 65 |dified t|o remove|
|00001a90| 0a 58 09 09 09 74 68 65 | 20 63 61 6c 6c 20 74 6f |.X...the| call to|
|00001aa0| 20 27 66 69 78 52 61 6e | 6b 27 20 69 6e 20 27 69 | 'fixRan|k' in 'i|
|00001ab0| 6e 73 65 72 74 27 2c 20 | 27 64 65 6c 65 74 65 27 |nsert', |'delete'|
|00001ac0| 20 61 6e 64 0a 58 09 09 | 09 27 66 69 6e 64 27 0a | and.X..|.'find'.|
|00001ad0| 58 0a 58 2a 29 0a 58 0a | 58 20 20 49 4d 50 4f 52 |X.X*).X.|X  IMPOR|
|00001ae0| 54 20 73 70 6c 61 79 49 | 74 65 6d 3b 0a 58 0a 58 |T splayI|tem;.X.X|
|00001af0| 20 20 54 59 50 45 0a 58 | 20 20 20 20 20 61 75 78 |  TYPE.X|     aux|
|00001b00| 46 75 6e 63 20 3d 20 50 | 52 4f 43 45 44 55 52 45 |Func = P|ROCEDURE|
|00001b10| 20 28 73 70 6c 61 79 49 | 74 65 6d 2e 54 29 3b 0a | (splayI|tem.T);.|
|00001b20| 58 20 20 20 20 20 54 3b | 0a 58 0a 58 20 20 50 52 |X     T;|.X.X  PR|
|00001b30| 4f 43 45 44 55 52 45 20 | 63 72 65 61 74 65 28 56 |OCEDURE |create(V|
|00001b40| 41 52 20 74 72 65 65 3a | 54 29 3b 0a 58 20 20 28 |AR tree:|T);.X  (|
|00001b50| 2a 20 50 6f 73 74 3a 20 | 54 68 65 20 73 70 6c 61 |* Post: |The spla|
|00001b60| 79 20 74 72 65 65 20 74 | 72 65 65 20 27 74 72 65 |y tree t|ree 'tre|
|00001b70| 65 27 20 68 61 73 20 62 | 65 65 6e 20 63 72 65 61 |e' has b|een crea|
|00001b80| 74 65 64 2e 0a 58 20 20 | 2a 29 0a 58 09 09 20 20 |ted..X  |*).X..  |
|00001b90| 20 0a 58 20 20 50 52 4f | 43 45 44 55 52 45 20 64 | .X  PRO|CEDURE d|
|00001ba0| 65 73 74 72 6f 79 28 56 | 41 52 20 74 72 65 65 3a |estroy(V|AR tree:|
|00001bb0| 54 29 3b 0a 58 20 20 28 | 2a 20 50 72 65 3a 20 27 |T);.X  (|* Pre: '|
|00001bc0| 74 72 65 65 27 20 68 61 | 73 20 62 65 65 6e 20 63 |tree' ha|s been c|
|00001bd0| 72 65 61 74 65 64 20 77 | 69 74 68 20 27 63 72 65 |reated w|ith 'cre|
|00001be0| 61 74 65 27 0a 58 20 20 | 20 20 20 50 6f 73 74 3a |ate'.X  |   Post:|
|00001bf0| 20 41 6c 6c 20 64 79 6e | 61 6d 69 63 20 6d 65 6d | All dyn|amic mem|
|00001c00| 6f 72 79 20 70 72 65 76 | 69 6f 75 73 6c 79 20 61 |ory prev|iously a|
|00001c10| 73 73 6f 63 69 61 74 65 | 64 20 77 69 74 68 20 27 |ssociate|d with '|
|00001c20| 74 72 65 65 27 0a 58 20 | 20 20 20 20 20 20 20 20 |tree'.X |        |
|00001c30| 20 20 68 61 76 65 20 62 | 65 65 6e 20 72 65 74 75 |  have b|een retu|
|00001c40| 72 6e 65 64 2e 20 54 68 | 65 20 27 64 65 6c 27 20 |rned. Th|e 'del' |
|00001c50| 66 75 6e 63 74 69 6f 6e | 20 73 70 65 63 69 66 69 |function| specifi|
|00001c60| 65 64 20 69 6e 0a 58 09 | 20 20 20 27 63 72 65 61 |ed in.X.|   'crea|
|00001c70| 74 65 27 20 68 61 73 20 | 62 65 65 6e 20 63 61 6c |te' has |been cal|
|00001c80| 6c 65 64 20 6f 6e 65 20 | 74 69 6d 65 20 66 6f 72 |led one |time for|
|00001c90| 20 65 61 63 68 20 64 61 | 74 75 6d 20 69 6e 20 74 | each da|tum in t|
|00001ca0| 68 65 0a 58 09 20 20 20 | 74 72 65 65 2e 20 55 70 |he.X.   |tree. Up|
|00001cb0| 6f 6e 20 63 6f 6d 70 6c | 65 74 69 6f 6e 20 27 74 |on compl|etion 't|
|00001cc0| 72 65 65 27 20 69 73 20 | 6e 6f 20 6c 6f 6e 67 65 |ree' is |no longe|
|00001cd0| 72 20 61 20 76 61 6c 69 | 64 20 74 72 65 65 2e 0a |r a vali|d tree..|
|00001ce0| 58 20 20 2a 29 20 0a 58 | 20 20 0a 58 20 20 50 52 |X  *) .X|  .X  PR|
|00001cf0| 4f 43 45 44 55 52 45 20 | 69 6e 73 65 72 74 28 74 |OCEDURE |insert(t|
|00001d00| 72 65 65 3a 54 3b 20 69 | 74 65 6d 3a 73 70 6c 61 |ree:T; i|tem:spla|
|00001d10| 79 49 74 65 6d 2e 54 29 | 3b 0a 58 20 20 28 2a 20 |yItem.T)|;.X  (* |
|00001d20| 50 72 65 3a 20 27 74 72 | 65 65 27 20 68 61 73 20 |Pre: 'tr|ee' has |
|00001d30| 62 65 65 6e 20 63 72 65 | 61 74 65 64 20 77 69 74 |been cre|ated wit|
|00001d40| 68 20 27 63 72 65 61 74 | 65 27 0a 58 20 20 20 20 |h 'creat|e'.X    |
|00001d50| 20 50 6f 73 74 3a 20 27 | 69 74 65 6d 27 20 68 61 | Post: '|item' ha|
|00001d60| 73 20 62 65 65 6e 20 69 | 6e 73 65 72 74 65 64 20 |s been i|nserted |
|00001d70| 69 6e 20 27 74 72 65 65 | 27 2e 20 49 66 20 74 68 |in 'tree|'. If th|
|00001d80| 65 20 27 69 74 65 6d 27 | 20 61 6c 72 65 61 64 79 |e 'item'| already|
|00001d90| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 65 78 69 |.X      |     exi|
|00001da0| 73 74 73 20 74 68 69 73 | 20 6f 70 65 72 61 74 69 |sts this| operati|
|00001db0| 6f 6e 20 65 71 75 61 6c | 73 20 0a 58 09 20 20 20 |on equal|s .X.   |
|00001dc0| 20 20 20 64 65 6c 65 74 | 65 28 74 72 65 65 2c 69 |   delet|e(tree,i|
|00001dd0| 74 65 6d 29 3b 69 6e 73 | 65 72 74 28 74 72 65 65 |tem);ins|ert(tree|
|00001de0| 2c 69 74 65 6d 29 0a 58 | 20 20 2a 29 0a 58 20 20 |,item).X|  *).X  |
|00001df0| 0a 58 20 20 50 52 4f 43 | 45 44 55 52 45 20 64 65 |.X  PROC|EDURE de|
|00001e00| 6c 65 74 65 28 74 72 65 | 65 3a 54 3b 20 69 74 65 |lete(tre|e:T; ite|
|00001e10| 6d 3a 73 70 6c 61 79 49 | 74 65 6d 2e 54 29 3b 0a |m:splayI|tem.T);.|
|00001e20| 58 20 20 28 2a 20 50 72 | 65 3a 20 27 74 72 65 65 |X  (* Pr|e: 'tree|
|00001e30| 27 20 68 61 73 20 62 65 | 65 6e 20 63 72 65 61 74 |' has be|en creat|
|00001e40| 65 64 20 77 69 74 68 20 | 27 63 72 65 61 74 65 27 |ed with |'create'|
|00001e50| 0a 58 20 20 20 20 20 50 | 6f 73 74 3a 20 49 66 20 |.X     P|ost: If |
|00001e60| 27 69 74 65 6d 27 20 65 | 78 69 73 74 73 20 69 74 |'item' e|xists it|
|00001e70| 20 68 61 73 20 62 65 65 | 6e 20 72 65 6d 6f 76 65 | has bee|n remove|
|00001e80| 64 20 66 72 6f 6d 20 27 | 74 72 65 65 27 0a 58 20 |d from '|tree'.X |
|00001e90| 20 20 20 20 20 20 20 20 | 20 20 6f 74 68 65 72 77 |        |  otherw|
|00001ea0| 69 73 65 20 74 68 65 20 | 74 72 65 65 20 69 73 20 |ise the |tree is |
|00001eb0| 6c 65 66 74 20 75 6e 74 | 6f 75 63 68 65 64 0a 58 |left unt|ouched.X|
|00001ec0| 20 20 2a 29 0a 58 20 20 | 0a 58 20 20 50 52 4f 43 |  *).X  |.X  PROC|
|00001ed0| 45 44 55 52 45 20 66 69 | 6e 64 28 74 72 65 65 3a |EDURE fi|nd(tree:|
|00001ee0| 54 3b 20 69 74 65 6d 3a | 73 70 6c 61 79 49 74 65 |T; item:|splayIte|
|00001ef0| 6d 2e 54 3b 20 56 41 52 | 20 66 6f 75 6e 64 3a 73 |m.T; VAR| found:s|
|00001f00| 70 6c 61 79 49 74 65 6d | 2e 54 29 3a 42 4f 4f 4c |playItem|.T):BOOL|
|00001f10| 45 41 4e 3b 0a 58 20 20 | 28 2a 20 50 72 65 3a 20 |EAN;.X  |(* Pre: |
|00001f20| 27 74 72 65 65 27 20 68 | 61 73 20 62 65 65 6e 20 |'tree' h|as been |
|00001f30| 63 72 65 61 74 65 64 20 | 77 69 74 68 20 27 63 72 |created |with 'cr|
|00001f40| 65 61 74 65 27 0a 58 20 | 20 20 20 20 50 6f 73 74 |eate'.X |    Post|
|00001f50| 3a 20 49 66 20 27 69 74 | 65 6d 27 20 65 78 69 73 |: If 'it|em' exis|
|00001f60| 74 73 20 69 6e 20 27 74 | 72 65 65 27 20 27 66 6f |ts in 't|ree' 'fo|
|00001f70| 75 6e 64 27 20 68 61 73 | 20 62 65 65 6e 20 61 73 |und' has| been as|
|00001f80| 73 69 67 6e 65 64 0a 58 | 20 20 20 20 20 20 20 20 |signed.X|        |
|00001f90| 20 20 20 74 6f 20 74 68 | 65 20 63 6f 72 72 65 73 |   to th|e corres|
|00001fa0| 70 6f 6e 64 69 6e 67 20 | 64 61 74 61 20 69 6e 20 |ponding |data in |
|00001fb0| 27 74 72 65 65 27 2e 0a | 58 09 20 20 20 4e 6f 74 |'tree'..|X.   Not|
|00001fc0| 65 3a 20 54 68 65 20 72 | 65 61 73 6f 6e 20 66 6f |e: The r|eason fo|
|00001fd0| 72 20 72 65 74 75 72 6e | 69 6e 67 20 74 68 65 20 |r return|ing the |
|00001fe0| 73 61 6d 65 20 69 74 65 | 6d 20 73 65 61 72 63 68 |same ite|m search|
|00001ff0| 65 64 0a 58 09 20 20 20 | 20 20 20 20 20 20 66 6f |ed.X.   |      fo|
|00002000| 72 20 69 73 20 74 6f 20 | 6d 61 6b 65 20 69 74 20 |r is to |make it |
|00002010| 70 6f 73 73 69 62 6c 65 | 20 74 6f 20 73 70 65 63 |possible| to spec|
|00002020| 69 66 79 20 61 6e 20 69 | 6e 63 6f 6d 70 6c 65 74 |ify an i|ncomplet|
|00002030| 65 0a 58 09 09 20 73 65 | 61 72 63 68 20 73 74 72 |e.X.. se|arch str|
|00002040| 75 63 74 75 72 65 20 61 | 6e 64 20 74 68 65 6e 20 |ucture a|nd then |
|00002050| 67 65 74 20 74 68 65 20 | 66 75 6c 6c 20 73 74 72 |get the |full str|
|00002060| 75 63 74 75 72 65 0a 58 | 09 09 20 72 65 74 75 72 |ucture.X|.. retur|
|00002070| 6e 65 64 2e 0a 58 20 20 | 20 20 20 52 65 74 75 72 |ned..X  |   Retur|
|00002080| 6e 73 3a 20 54 52 55 45 | 20 69 66 20 27 69 74 65 |ns: TRUE| if 'ite|
|00002090| 6d 27 20 65 78 69 73 74 | 2c 20 46 41 4c 53 45 20 |m' exist|, FALSE |
|000020a0| 6f 74 68 65 72 77 69 73 | 65 0a 58 20 20 2a 29 0a |otherwis|e.X  *).|
|000020b0| 58 20 20 0a 58 20 20 50 | 52 4f 43 45 44 55 52 45 |X  .X  P|ROCEDURE|
|000020c0| 20 6e 62 72 45 6c 65 6d | 28 74 72 65 65 3a 54 29 | nbrElem|(tree:T)|
|000020d0| 3a 20 43 41 52 44 49 4e | 41 4c 3b 0a 58 20 20 28 |: CARDIN|AL;.X  (|
|000020e0| 2a 20 50 72 65 3a 20 27 | 74 72 65 65 27 20 68 61 |* Pre: '|tree' ha|
|000020f0| 73 20 62 65 65 6e 20 63 | 72 65 61 74 65 64 20 77 |s been c|reated w|
|00002100| 69 74 68 20 27 63 72 65 | 61 74 65 27 0a 58 20 20 |ith 'cre|ate'.X  |
|00002110| 20 20 20 52 65 74 75 72 | 6e 73 3a 20 54 68 65 20 |   Retur|ns: The |
|00002120| 6e 75 6d 62 65 72 20 6f | 66 20 65 6c 65 6d 65 6e |number o|f elemen|
|00002130| 74 73 20 69 6e 20 27 74 | 72 65 65 27 0a 58 20 20 |ts in 't|ree'.X  |
|00002140| 2a 29 0a 58 20 20 0a 58 | 20 20 50 52 4f 43 45 44 |*).X  .X|  PROCED|
|00002150| 55 52 45 20 67 65 74 52 | 61 6e 6b 45 6c 65 6d 65 |URE getR|ankEleme|
|00002160| 6e 74 28 74 72 65 65 3a | 54 3b 20 72 3a 43 41 52 |nt(tree:|T; r:CAR|
|00002170| 44 49 4e 41 4c 3b 20 56 | 41 52 20 66 6f 75 6e 64 |DINAL; V|AR found|
|00002180| 3a 73 70 6c 61 79 49 74 | 65 6d 2e 54 29 3a 20 42 |:splayIt|em.T): B|
|00002190| 4f 4f 4c 45 41 4e 3b 0a | 58 20 20 28 2a 20 50 72 |OOLEAN;.|X  (* Pr|
|000021a0| 65 3a 20 27 74 72 65 65 | 27 20 68 61 73 20 62 65 |e: 'tree|' has be|
|000021b0| 65 6e 20 63 72 65 61 74 | 65 64 20 77 69 74 68 20 |en creat|ed with |
|000021c0| 27 63 72 65 61 74 65 27 | 0a 58 20 20 20 20 20 50 |'create'|.X     P|
|000021d0| 6f 73 74 3a 20 54 68 65 | 20 27 69 74 65 6d 27 20 |ost: The| 'item' |
|000021e0| 77 69 74 68 20 72 61 6e | 6b 20 27 72 27 20 68 61 |with ran|k 'r' ha|
|000021f0| 73 20 62 65 65 6e 20 61 | 73 73 69 67 6e 65 64 20 |s been a|ssigned |
|00002200| 74 6f 20 27 66 6f 75 6e | 64 27 0a 58 20 20 20 20 |to 'foun|d'.X    |
|00002210| 20 52 65 74 75 72 6e 73 | 3a 20 54 52 55 45 20 69 | Returns|: TRUE i|
|00002220| 66 20 27 69 74 65 6d 27 | 20 65 78 69 73 74 2c 20 |f 'item'| exist, |
|00002230| 46 41 4c 53 45 20 6f 74 | 68 65 72 77 69 73 65 0a |FALSE ot|herwise.|
|00002240| 58 20 20 2a 29 0a 58 20 | 20 0a 58 20 20 50 52 4f |X  *).X | .X  PRO|
|00002250| 43 45 44 55 52 45 20 67 | 65 74 52 61 6e 6b 28 74 |CEDURE g|etRank(t|
|00002260| 72 65 65 3a 54 3b 20 69 | 74 65 6d 3a 73 70 6c 61 |ree:T; i|tem:spla|
|00002270| 79 49 74 65 6d 2e 54 29 | 3a 43 41 52 44 49 4e 41 |yItem.T)|:CARDINA|
|00002280| 4c 3b 0a 58 20 20 28 2a | 20 50 72 65 3a 20 27 74 |L;.X  (*| Pre: 't|
|00002290| 72 65 65 27 20 68 61 73 | 20 62 65 65 6e 20 63 72 |ree' has| been cr|
|000022a0| 65 61 74 65 64 20 77 69 | 74 68 20 27 63 72 65 61 |eated wi|th 'crea|
|000022b0| 74 65 27 0a 58 20 20 20 | 20 20 52 65 74 75 72 6e |te'.X   |  Return|
|000022c0| 73 3a 20 54 68 65 20 72 | 61 6e 6b 20 6f 66 20 65 |s: The r|ank of e|
|000022d0| 6c 65 6d 65 6e 74 20 27 | 69 74 65 6d 27 2e 20 49 |lement '|item'. I|
|000022e0| 66 20 27 69 74 65 6d 27 | 20 77 61 73 6e 27 74 20 |f 'item'| wasn't |
|000022f0| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X      |        |
|00002300| 66 6f 75 6e 64 20 74 68 | 65 20 72 6f 75 74 69 6e |found th|e routin|
|00002310| 65 20 72 65 74 75 72 6e | 73 20 30 20 0a 58 20 20 |e return|s 0 .X  |
|00002320| 2a 29 0a 58 20 20 0a 58 | 20 20 50 52 4f 43 45 44 |*).X  .X|  PROCED|
|00002330| 55 52 45 20 6d 61 70 49 | 6e 28 74 72 65 65 3a 54 |URE mapI|n(tree:T|
|00002340| 3b 20 66 3a 61 75 78 46 | 75 6e 63 29 3b 0a 58 20 |; f:auxF|unc);.X |
|00002350| 20 28 2a 20 50 72 65 3a | 20 27 74 72 65 65 27 20 | (* Pre:| 'tree' |
|00002360| 68 61 73 20 62 65 65 6e | 20 63 72 65 61 74 65 64 |has been| created|
|00002370| 20 77 69 74 68 20 27 63 | 72 65 61 74 65 27 0a 58 | with 'c|reate'.X|
|00002380| 20 20 20 20 20 50 6f 73 | 74 3a 20 54 68 65 20 27 |     Pos|t: The '|
|00002390| 66 27 20 70 72 6f 63 65 | 64 75 72 65 20 68 61 73 |f' proce|dure has|
|000023a0| 20 62 65 65 6e 20 61 70 | 70 6c 69 65 64 20 74 6f | been ap|plied to|
|000023b0| 20 61 6c 6c 20 65 6c 65 | 6d 65 6e 74 73 20 69 6e | all ele|ments in|
|000023c0| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 27 74 72 |.X      |     'tr|
|000023d0| 65 65 27 20 61 63 63 6f | 72 64 69 6e 67 20 74 6f |ee' acco|rding to|
|000023e0| 20 61 20 74 72 65 65 2d | 69 6e 6f 72 64 65 72 20 | a tree-|inorder |
|000023f0| 77 61 6c 6b 0a 58 20 20 | 2a 29 0a 58 20 20 0a 58 |walk.X  |*).X  .X|
|00002400| 20 20 50 52 4f 43 45 44 | 55 52 45 20 6d 61 70 50 |  PROCED|URE mapP|
|00002410| 72 65 28 74 72 65 65 3a | 54 3b 20 66 3a 61 75 78 |re(tree:|T; f:aux|
|00002420| 46 75 6e 63 29 3b 0a 58 | 20 20 28 2a 20 50 72 65 |Func);.X|  (* Pre|
|00002430| 3a 20 27 74 72 65 65 27 | 20 68 61 73 20 62 65 65 |: 'tree'| has bee|
|00002440| 6e 20 63 72 65 61 74 65 | 64 20 77 69 74 68 20 27 |n create|d with '|
|00002450| 63 72 65 61 74 65 27 0a | 58 20 20 20 20 20 50 6f |create'.|X     Po|
|00002460| 73 74 3a 20 54 68 65 20 | 27 66 27 20 70 72 6f 63 |st: The |'f' proc|
|00002470| 65 64 75 72 65 20 68 61 | 73 20 62 65 65 6e 20 61 |edure ha|s been a|
|00002480| 70 70 6c 69 65 64 20 74 | 6f 20 61 6c 6c 20 65 6c |pplied t|o all el|
|00002490| 65 6d 65 6e 74 73 20 69 | 6e 0a 58 20 20 20 20 20 |ements i|n.X     |
|000024a0| 20 20 20 20 20 20 27 74 | 72 65 65 27 20 61 63 63 |      't|ree' acc|
|000024b0| 6f 72 64 69 6e 67 20 74 | 6f 20 61 20 74 72 65 65 |ording t|o a tree|
|000024c0| 2d 70 72 65 6f 72 64 65 | 72 20 77 61 6c 6b 0a 58 |-preorde|r walk.X|
|000024d0| 20 20 2a 29 0a 58 20 20 | 0a 58 20 20 50 52 4f 43 |  *).X  |.X  PROC|
|000024e0| 45 44 55 52 45 20 6d 61 | 70 50 6f 73 28 74 72 65 |EDURE ma|pPos(tre|
|000024f0| 65 3a 54 3b 20 66 3a 61 | 75 78 46 75 6e 63 29 3b |e:T; f:a|uxFunc);|
|00002500| 20 0a 58 20 20 28 2a 20 | 50 72 65 3a 20 27 74 72 | .X  (* |Pre: 'tr|
|00002510| 65 65 27 20 68 61 73 20 | 62 65 65 6e 20 63 72 65 |ee' has |been cre|
|00002520| 61 74 65 64 20 77 69 74 | 68 20 27 63 72 65 61 74 |ated wit|h 'creat|
|00002530| 65 27 0a 58 20 20 20 20 | 20 50 6f 73 74 3a 20 54 |e'.X    | Post: T|
|00002540| 68 65 20 27 66 27 20 70 | 72 6f 63 65 64 75 72 65 |he 'f' p|rocedure|
|00002550| 20 68 61 73 20 62 65 65 | 6e 20 61 70 70 6c 69 65 | has bee|n applie|
|00002560| 64 20 74 6f 20 61 6c 6c | 20 65 6c 65 6d 65 6e 74 |d to all| element|
|00002570| 73 20 69 6e 0a 58 20 20 | 20 20 20 20 20 20 20 20 |s in.X  |        |
|00002580| 20 27 74 72 65 65 27 20 | 61 63 63 6f 72 64 69 6e | 'tree' |accordin|
|00002590| 67 20 74 6f 20 61 20 74 | 72 65 65 2d 70 72 65 6f |g to a t|ree-preo|
|000025a0| 72 64 65 72 20 77 61 6c | 6b 0a 58 20 20 2a 29 0a |rder wal|k.X  *).|
|000025b0| 58 0a 58 45 4e 44 20 73 | 70 6c 61 79 2e 0a 53 48 |X.XEND s|play..SH|
|000025c0| 41 52 5f 45 4f 46 0a 24 | 54 4f 55 43 48 20 2d 61 |AR_EOF.$|TOUCH -a|
|000025d0| 6d 20 31 31 32 32 31 34 | 30 30 39 32 20 73 70 6c |m 112214|0092 spl|
|000025e0| 61 79 2e 64 65 66 20 26 | 26 0a 63 68 6d 6f 64 20 |ay.def &|&.chmod |
|000025f0| 30 34 34 34 20 73 70 6c | 61 79 2e 64 65 66 20 7c |0444 spl|ay.def ||
|00002600| 7c 0a 65 63 68 6f 20 22 | 72 65 73 74 6f 72 65 20 ||.echo "|restore |
|00002610| 6f 66 20 73 70 6c 61 79 | 2e 64 65 66 20 66 61 69 |of splay|.def fai|
|00002620| 6c 65 64 22 0a 73 65 74 | 20 60 77 63 20 2d 63 20 |led".set| `wc -c |
|00002630| 73 70 6c 61 79 2e 64 65 | 66 60 3b 57 63 5f 63 3d |splay.de|f`;Wc_c=|
|00002640| 24 31 0a 69 66 20 74 65 | 73 74 20 22 24 57 63 5f |$1.if te|st "$Wc_|
|00002650| 63 22 20 21 3d 20 22 33 | 37 35 35 22 3b 20 74 68 |c" != "3|755"; th|
|00002660| 65 6e 0a 09 65 63 68 6f | 20 6f 72 69 67 69 6e 61 |en..echo| origina|
|00002670| 6c 20 73 69 7a 65 20 33 | 37 35 35 2c 20 63 75 72 |l size 3|755, cur|
|00002680| 72 65 6e 74 20 73 69 7a | 65 20 24 57 63 5f 63 0a |rent siz|e $Wc_c.|
|00002690| 66 69 0a 66 69 0a 23 20 | 3d 3d 3d 3d 3d 3d 3d 3d |fi.fi.# |========|
|000026a0| 3d 3d 3d 3d 3d 20 73 70 | 6c 61 79 49 74 65 6d 2e |===== sp|layItem.|
|000026b0| 64 65 66 20 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |def ====|========|
|000026c0| 3d 3d 0a 69 66 20 74 65 | 73 74 20 58 22 24 31 22 |==.if te|st X"$1"|
|000026d0| 20 21 3d 20 58 22 2d 63 | 22 20 2d 61 20 2d 66 20 | != X"-c|" -a -f |
|000026e0| 27 73 70 6c 61 79 49 74 | 65 6d 2e 64 65 66 27 3b |'splayIt|em.def';|
|000026f0| 20 74 68 65 6e 0a 09 65 | 63 68 6f 20 22 46 69 6c | then..e|cho "Fil|
|00002700| 65 20 61 6c 72 65 61 64 | 79 20 65 78 69 73 74 73 |e alread|y exists|
|00002710| 3a 20 73 6b 69 70 70 69 | 6e 67 20 27 73 70 6c 61 |: skippi|ng 'spla|
|00002720| 79 49 74 65 6d 2e 64 65 | 66 27 22 0a 65 6c 73 65 |yItem.de|f'".else|
|00002730| 0a 65 63 68 6f 20 22 78 | 20 2d 20 65 78 74 72 61 |.echo "x| - extra|
|00002740| 63 74 69 6e 67 20 73 70 | 6c 61 79 49 74 65 6d 2e |cting sp|layItem.|
|00002750| 64 65 66 20 28 54 65 78 | 74 29 22 0a 73 65 64 20 |def (Tex|t)".sed |
|00002760| 27 73 2f 5e 58 2f 2f 27 | 20 3c 3c 20 27 53 48 41 |'s/^X//'| << 'SHA|
|00002770| 52 5f 45 4f 46 27 20 3e | 20 73 70 6c 61 79 49 74 |R_EOF' >| splayIt|
|00002780| 65 6d 2e 64 65 66 20 26 | 26 0a 58 44 45 46 49 4e |em.def &|&.XDEFIN|
|00002790| 49 54 49 4f 4e 20 4d 4f | 44 55 4c 45 20 73 70 6c |ITION MO|DULE spl|
|000027a0| 61 79 49 74 65 6d 3b 0a | 58 28 2a 0a 58 20 09 54 |ayItem;.|X(*.X .T|
|000027b0| 69 74 6c 65 3a 09 09 0a | 58 09 4c 61 73 74 20 45 |itle:...|X.Last E|
|000027c0| 64 69 74 3a 09 53 75 6e | 20 4e 6f 76 20 32 32 20 |dit:.Sun| Nov 22 |
|000027d0| 31 32 3a 33 31 3a 30 35 | 20 31 39 39 32 0a 58 09 |12:31:05| 1992.X.|
|000027e0| 41 75 74 68 6f 72 3a 09 | 09 4a 6f 68 61 6e 20 50 |Author:.|.Johan P|
|000027f0| 65 72 73 73 6f 6e 20 61 | 74 20 6d 79 39 0a 58 0a |ersson a|t my9.X.|
|00002800| 58 2a 29 0a 58 20 20 54 | 59 50 45 0a 58 20 20 20 |X*).X  T|YPE.X   |
|00002810| 20 20 54 20 3d 20 49 4e | 54 45 47 45 52 3b 0a 58 |  T = IN|TEGER;.X|
|00002820| 0a 58 20 20 50 52 4f 43 | 45 44 55 52 45 20 63 6d |.X  PROC|EDURE cm|
|00002830| 70 28 61 3a 54 3b 20 62 | 3a 54 29 3a 20 49 4e 54 |p(a:T; b|:T): INT|
|00002840| 45 47 45 52 3b 0a 58 20 | 20 28 2a 20 52 65 74 75 |EGER;.X | (* Retu|
|00002850| 72 6e 73 3a 09 20 20 20 | 63 6d 70 28 61 2c 62 29 |rns:.   |cmp(a,b)|
|00002860| 20 3d 20 30 20 20 3d 3e | 20 61 3d 62 0a 58 09 09 | = 0  =>| a=b.X..|
|00002870| 20 20 20 63 6d 70 28 61 | 2c 62 29 20 3d 20 31 20 |   cmp(a|,b) = 1 |
|00002880| 20 3d 3e 20 61 3e 62 0a | 58 09 09 20 20 20 63 6d | => a>b.|X..   cm|
|00002890| 70 28 61 2c 62 29 20 3d | 20 2d 31 20 3d 3e 20 61 |p(a,b) =| -1 => a|
|000028a0| 3c 62 0a 58 20 20 2a 29 | 0a 58 20 20 0a 58 20 20 |<b.X  *)|.X  .X  |
|000028b0| 50 52 4f 43 45 44 55 52 | 45 20 63 72 65 61 74 65 |PROCEDUR|E create|
|000028c0| 28 56 41 52 20 61 3a 54 | 29 3b 0a 58 20 20 28 2a |(VAR a:T|);.X  (*|
|000028d0| 20 50 6f 73 74 3a 20 41 | 20 6e 65 77 20 6f 62 6a | Post: A| new obj|
|000028e0| 65 63 74 20 68 61 73 20 | 62 65 65 6e 20 63 72 65 |ect has |been cre|
|000028f0| 61 74 65 64 20 0a 58 20 | 20 2a 29 20 0a 58 20 20 |ated .X | *) .X  |
|00002900| 0a 58 20 20 50 52 4f 43 | 45 44 55 52 45 20 64 65 |.X  PROC|EDURE de|
|00002910| 73 74 72 6f 79 28 56 41 | 52 20 61 3a 54 29 3b 0a |stroy(VA|R a:T);.|
|00002920| 58 20 20 28 2a 20 50 72 | 65 3a 20 63 72 65 61 74 |X  (* Pr|e: creat|
|00002930| 65 28 61 29 0a 58 20 20 | 20 20 20 50 6f 73 74 3a |e(a).X  |   Post:|
|00002940| 20 41 6c 6c 20 6d 65 6d | 6f 72 79 20 6f 63 63 75 | All mem|ory occu|
|00002950| 70 69 65 64 20 62 79 20 | 27 61 27 20 68 61 73 20 |pied by |'a' has |
|00002960| 62 65 65 6e 20 72 65 74 | 75 72 6e 65 64 2e 0a 58 |been ret|urned..X|
|00002970| 20 20 20 20 20 20 20 20 | 20 20 20 61 20 3d 20 4e |        |   a = N|
|00002980| 49 4c 20 0a 58 20 20 2a | 29 0a 58 20 20 0a 58 45 |IL .X  *|).X  .XE|
|00002990| 4e 44 20 73 70 6c 61 79 | 49 74 65 6d 2e 0a 53 48 |ND splay|Item..SH|
|000029a0| 41 52 5f 45 4f 46 0a 24 | 54 4f 55 43 48 20 2d 61 |AR_EOF.$|TOUCH -a|
|000029b0| 6d 20 31 31 32 32 31 34 | 30 30 39 32 20 73 70 6c |m 112214|0092 spl|
|000029c0| 61 79 49 74 65 6d 2e 64 | 65 66 20 26 26 0a 63 68 |ayItem.d|ef &&.ch|
|000029d0| 6d 6f 64 20 30 36 34 34 | 20 73 70 6c 61 79 49 74 |mod 0644| splayIt|
|000029e0| 65 6d 2e 64 65 66 20 7c | 7c 0a 65 63 68 6f 20 22 |em.def |||.echo "|
|000029f0| 72 65 73 74 6f 72 65 20 | 6f 66 20 73 70 6c 61 79 |restore |of splay|
|00002a00| 49 74 65 6d 2e 64 65 66 | 20 66 61 69 6c 65 64 22 |Item.def| failed"|
|00002a10| 0a 73 65 74 20 60 77 63 | 20 2d 63 20 73 70 6c 61 |.set `wc| -c spla|
|00002a20| 79 49 74 65 6d 2e 64 65 | 66 60 3b 57 63 5f 63 3d |yItem.de|f`;Wc_c=|
|00002a30| 24 31 0a 69 66 20 74 65 | 73 74 20 22 24 57 63 5f |$1.if te|st "$Wc_|
|00002a40| 63 22 20 21 3d 20 22 35 | 30 35 22 3b 20 74 68 65 |c" != "5|05"; the|
|00002a50| 6e 0a 09 65 63 68 6f 20 | 6f 72 69 67 69 6e 61 6c |n..echo |original|
|00002a60| 20 73 69 7a 65 20 35 30 | 35 2c 20 63 75 72 72 65 | size 50|5, curre|
|00002a70| 6e 74 20 73 69 7a 65 20 | 24 57 63 5f 63 0a 66 69 |nt size |$Wc_c.fi|
|00002a80| 0a 66 69 0a 65 63 68 6f | 20 22 45 6e 64 20 6f 66 |.fi.echo| "End of|
|00002a90| 20 70 61 72 74 20 31 2c | 20 63 6f 6e 74 69 6e 75 | part 1,| continu|
|00002aa0| 65 20 77 69 74 68 20 70 | 61 72 74 20 32 22 0a 65 |e with p|art 2".e|
|00002ab0| 78 69 74 20 30 0a       |                         |xit 0.  |        |
+--------+-------------------------+-------------------------+--------+--------+