home *** CD-ROM | disk | FTP | other *** search
| Unknown | 1995-07-02 | 581.0 KB |
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was not able to be converted.
This format is not currently supported by dexvert.
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| file
| data
| default
| |
| 100%
| gt2
| Kopftext: 'HELP('
| default (weak)
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 48 45 4c 50 28 00 00 00 | c9 00 00 00 fc d7 01 00 |HELP(...|........|
|00000010| 44 a0 02 00 00 fd ff ff | 00 00 00 00 60 05 00 00 |D.......|....`...|
|00000020| 00 01 00 00 00 00 00 00 | 24 00 00 00 46 52 45 45 |........|$...FREE|
|00000030| 54 00 00 00 ff ff ff ff | 80 00 00 00 46 ff ff ff |T.......|....F...|
|00000040| 56 96 fb 2a b8 0a 00 00 | 13 00 00 00 00 00 00 00 |V..*....|........|
|00000050| 21 52 6f 6f 74 00 00 00 | 38 0b 00 00 46 ff ff ff |!Root...|8...F...|
|00000060| c0 af fb 2a 28 07 00 00 | 13 00 00 00 00 00 00 00 |...*(...|........|
|00000070| 41 6c 6c 6f 63 52 69 6e | 67 00 00 00 02 ec 8e e3 |AllocRin|g.......|
|00000080| 44 41 54 41 b8 0a 00 00 | 54 6f 70 0a 4e 65 78 74 |DATA....|Top.Next|
|00000090| 3a 20 3c 43 6f 70 79 69 | 6e 67 3d 3e 43 6f 70 79 |: <Copyi|ng=>Copy|
|000000a0| 69 6e 67 3e 20 2a 20 55 | 70 3a 20 3c 28 44 49 52 |ing> * U|p: <(DIR|
|000000b0| 29 3d 3e 44 49 52 3e 0a | 0a 23 57 72 61 70 20 6f |)=>DIR>.|.#Wrap o|
|000000c0| 6e 0a 0a 49 6e 74 72 6f | 64 75 63 74 69 6f 6e 0a |n..Intro|duction.|
|000000d0| 5c 2a 5c 2a 5c 2a 5c 2a | 5c 2a 5c 2a 5c 2a 5c 2a |\*\*\*\*|\*\*\*\*|
|000000e0| 5c 2a 5c 2a 5c 2a 5c 2a | 0a 0a 54 68 69 73 20 6d |\*\*\*\*|..This m|
|000000f0| 61 6e 75 61 6c 20 64 6f | 63 75 6d 65 6e 74 73 20 |anual do|cuments |
|00000100| 68 6f 77 20 74 6f 20 69 | 6e 73 74 61 6c 6c 20 61 |how to i|nstall a|
|00000110| 6e 64 20 75 73 65 20 74 | 68 65 20 47 4e 55 20 43 |nd use t|he GNU C|
|00000120| 2b 2b 20 6c 69 62 72 61 | 72 79 2e 0a 0a 23 57 72 |++ libra|ry...#Wr|
|00000130| 61 70 20 6f 66 66 0a 3c | 43 6f 70 79 69 6e 67 3d |ap off.<|Copying=|
|00000140| 3e 43 6f 70 79 69 6e 67 | 3e 3a 09 20 20 20 20 47 |>Copying|>:. G|
|00000150| 4e 55 20 4c 69 62 72 61 | 72 79 20 50 75 62 6c 69 |NU Libra|ry Publi|
|00000160| 63 20 4c 69 63 65 6e 73 | 65 20 73 61 79 73 20 68 |c Licens|e says h|
|00000170| 6f 77 20 79 6f 75 20 63 | 61 6e 20 63 6f 70 79 0a |ow you c|an copy.|
|00000180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000190| 20 20 20 20 61 6e 64 20 | 73 68 61 72 65 20 74 68 | and |share th|
|000001a0| 65 20 47 4e 55 20 43 2b | 2b 20 6c 69 62 72 61 72 |e GNU C+|+ librar|
|000001b0| 79 2e 0a 3c 43 6f 6e 74 | 72 69 62 75 74 6f 72 73 |y..<Cont|ributors|
|000001c0| 3d 3e 43 6f 6e 74 72 69 | 62 75 74 6f 3e 3a 20 20 |=>Contri|buto>: |
|000001d0| 20 20 50 65 6f 70 6c 65 | 20 77 68 6f 20 68 61 76 | People| who hav|
|000001e0| 65 20 63 6f 6e 74 72 69 | 62 75 74 65 64 20 74 6f |e contri|buted to|
|000001f0| 20 47 4e 55 20 43 2b 2b | 20 6c 69 62 72 61 72 79 | GNU C++| library|
|00000200| 2e 0a 3c 49 6e 73 74 61 | 6c 6c 61 74 69 6f 6e 3d |..<Insta|llation=|
|00000210| 3e 49 6e 73 74 61 6c 6c | 61 74 69 3e 3a 20 20 20 |>Install|ati>: |
|00000220| 20 48 6f 77 20 74 6f 20 | 63 6f 6e 66 69 67 75 72 | How to |configur|
|00000230| 65 2c 20 63 6f 6d 70 69 | 6c 65 20 61 6e 64 20 69 |e, compi|le and i|
|00000240| 6e 73 74 61 6c 6c 20 47 | 4e 55 20 43 2b 2b 20 6c |nstall G|NU C++ l|
|00000250| 69 62 72 61 72 79 0a 3c | 54 72 6f 75 62 6c 65 3d |ibrary.<|Trouble=|
|00000260| 3e 54 72 6f 75 62 6c 65 | 3e 3a 20 20 20 20 20 20 |>Trouble|>: |
|00000270| 20 20 20 49 66 20 79 6f | 75 20 68 61 76 65 20 74 | If yo|u have t|
|00000280| 72 6f 75 62 6c 65 20 69 | 6e 73 74 61 6c 6c 69 6e |rouble i|nstallin|
|00000290| 67 20 47 4e 55 20 43 2b | 2b 20 6c 69 62 72 61 72 |g GNU C+|+ librar|
|000002a0| 79 2e 0a 3c 47 65 6e 65 | 72 61 6c 3d 3e 47 65 6e |y..<Gene|ral=>Gen|
|000002b0| 65 72 61 6c 3e 3a 20 20 | 20 20 20 20 20 20 20 41 |eral>: | A|
|000002c0| 69 6d 73 2c 20 6f 62 6a | 65 63 74 69 76 65 73 2c |ims, obj|ectives,|
|000002d0| 20 61 6e 64 20 6c 69 6d | 69 74 61 74 69 6f 6e 73 | and lim|itations|
|000002e0| 20 6f 66 20 74 68 65 20 | 47 4e 55 20 43 2b 2b 20 | of the |GNU C++ |
|000002f0| 6c 69 62 72 61 72 79 0a | 3c 43 6f 6e 76 65 6e 74 |library.|<Convent|
|00000300| 69 6f 6e 73 3d 3e 43 6f | 6e 76 65 6e 74 69 6f 6e |ions=>Co|nvention|
|00000310| 3e 3a 20 20 20 20 20 53 | 74 79 6c 69 73 74 69 63 |>: S|tylistic|
|00000320| 20 63 6f 6e 76 65 6e 74 | 69 6f 6e 73 0a 3c 4f 4b | convent|ions.<OK|
|00000330| 3d 3e 4f 4b 3e 3a 20 20 | 20 20 20 20 20 20 20 20 |=>OK>: | |
|00000340| 20 20 20 20 53 75 70 70 | 6f 72 74 20 66 6f 72 20 | Supp|ort for |
|00000350| 72 65 70 72 65 73 65 6e | 74 61 74 69 6f 6e 20 69 |represen|tation i|
|00000360| 6e 76 61 72 69 61 6e 74 | 73 0a 3c 50 72 6f 74 6f |nvariant|s.<Proto|
|00000370| 3d 3e 50 72 6f 74 6f 3e | 3a 20 20 20 20 20 20 20 |=>Proto>|: |
|00000380| 20 20 20 20 49 6e 74 72 | 6f 64 75 63 74 69 6f 6e | Intr|oduction|
|00000390| 20 74 6f 20 63 6f 6e 74 | 61 69 6e 65 72 20 63 6c | to cont|ainer cl|
|000003a0| 61 73 73 20 70 72 6f 74 | 6f 74 79 70 65 73 0a 3c |ass prot|otypes.<|
|000003b0| 50 69 78 3d 3e 50 69 78 | 3e 3a 20 20 20 20 20 20 |Pix=>Pix|>: |
|000003c0| 20 20 20 20 20 20 20 50 | 73 65 75 64 6f 2d 69 6e | P|seudo-in|
|000003d0| 64 65 78 65 73 0a 3c 52 | 65 70 72 65 73 65 6e 74 |dexes.<R|epresent|
|000003e0| 61 74 69 6f 6e 73 3d 3e | 52 65 70 72 65 73 65 6e |ations=>|Represen|
|000003f0| 74 61 3e 3a 20 48 6f 77 | 20 76 61 72 69 61 62 6c |ta>: How| variabl|
|00000400| 65 2d 73 69 7a 65 64 20 | 6f 62 6a 65 63 74 73 20 |e-sized |objects |
|00000410| 61 72 65 20 72 65 70 72 | 65 73 65 6e 74 65 64 0a |are repr|esented.|
|00000420| 3c 45 78 70 72 65 73 73 | 69 6f 6e 73 3d 3e 45 78 |<Express|ions=>Ex|
|00000430| 70 72 65 73 73 69 6f 6e | 3e 3a 20 20 20 20 20 53 |pression|>: S|
|00000440| 6f 6d 65 20 67 75 69 64 | 61 6e 63 65 20 6f 6e 20 |ome guid|ance on |
|00000450| 70 72 6f 67 72 61 6d 6d | 69 6e 67 20 65 78 70 72 |programm|ing expr|
|00000460| 65 73 73 69 6f 6e 2d 6f | 72 69 65 6e 74 65 64 20 |ession-o|riented |
|00000470| 63 6c 61 73 73 65 73 0a | 3c 48 65 61 64 65 72 73 |classes.|<Headers|
|00000480| 3d 3e 48 65 61 64 65 72 | 73 3e 3a 20 20 20 20 20 |=>Header|s>: |
|00000490| 20 20 20 20 48 65 61 64 | 65 72 20 66 69 6c 65 73 | Head|er files|
|000004a0| 20 61 6e 64 20 6f 74 68 | 65 72 20 73 75 70 70 6f | and oth|er suppo|
|000004b0| 72 74 20 66 6f 72 20 69 | 6e 74 65 72 66 61 63 69 |rt for i|nterfaci|
|000004c0| 6e 67 20 43 2b 2b 20 74 | 6f 20 43 0a 3c 42 75 69 |ng C++ t|o C.<Bui|
|000004d0| 6c 74 69 6e 3d 3e 42 75 | 69 6c 74 69 6e 3e 3a 20 |ltin=>Bu|iltin>: |
|000004e0| 20 20 20 20 20 20 20 20 | 55 74 69 6c 69 74 79 20 | |Utility |
|000004f0| 66 75 6e 63 74 69 6f 6e | 73 20 66 6f 72 20 62 75 |function|s for bu|
|00000500| 69 6c 74 69 6e 20 74 79 | 70 65 73 0a 3c 4e 65 77 |iltin ty|pes.<New|
|00000510| 3d 3e 4e 65 77 3e 3a 20 | 20 20 20 20 20 20 20 20 |=>New>: | |
|00000520| 20 20 20 20 4c 69 62 72 | 61 72 79 20 64 79 6e 61 | Libr|ary dyna|
|00000530| 6d 69 63 20 61 6c 6c 6f | 63 61 74 69 6f 6e 20 70 |mic allo|cation p|
|00000540| 72 69 6d 69 74 69 76 65 | 73 0a 3c 49 4f 53 74 72 |rimitive|s.<IOStr|
|00000550| 65 61 6d 3d 3e 69 6f 73 | 74 72 65 61 6d 54 6f 3e |eam=>ios|treamTo>|
|00000560| 3a 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |:. | |
|00000570| 20 20 20 20 20 20 54 68 | 65 20 69 6e 70 75 74 5c | Th|e input\|
|00000580| 2f 6f 75 74 70 75 74 20 | 6c 69 62 72 61 72 79 20 |/output |library |
|00000590| 28 69 73 74 72 65 61 6d | 73 20 61 6e 64 20 6f 73 |(istream|s and os|
|000005a0| 74 72 65 61 6d 73 29 2e | 0a 3c 53 74 72 65 61 6d |treams).|.<Stream|
|000005b0| 3d 3e 53 74 72 65 61 6d | 3e 3a 20 20 20 20 20 20 |=>Stream|>: |
|000005c0| 20 20 20 20 6f 62 73 6f | 6c 65 74 65 20 49 5c 2f | obso|lete I\/|
|000005d0| 4f 20 6c 69 62 72 61 72 | 79 0a 3c 4f 62 73 74 61 |O librar|y.<Obsta|
|000005e0| 63 6b 3d 3e 4f 62 73 74 | 61 63 6b 3e 3a 20 20 20 |ck=>Obst|ack>: |
|000005f0| 20 20 20 20 20 20 4f 62 | 73 74 61 63 6b 73 20 61 | Ob|stacks a|
|00000600| 6e 64 20 74 68 65 69 72 | 20 75 73 65 73 2e 0a 3c |nd their| uses..<|
|00000610| 41 6c 6c 6f 63 52 69 6e | 67 3d 3e 41 6c 6c 6f 63 |AllocRin|g=>Alloc|
|00000620| 52 69 6e 67 3e 3a 20 20 | 20 20 20 20 20 41 20 70 |Ring>: | A p|
|00000630| 6c 61 63 65 20 74 6f 20 | 73 74 6f 72 65 20 6f 62 |lace to |store ob|
|00000640| 6a 65 63 74 73 20 66 6f | 72 20 61 20 77 68 69 6c |jects fo|r a whil|
|00000650| 65 0a 3c 53 74 72 69 6e | 67 3d 3e 53 74 72 69 6e |e.<Strin|g=>Strin|
|00000660| 67 3e 3a 20 20 20 20 20 | 20 20 20 20 20 53 74 72 |g>: | Str|
|00000670| 69 6e 67 2c 20 53 75 62 | 53 74 72 69 6e 67 2c 20 |ing, Sub|String, |
|00000680| 61 6e 64 20 52 65 67 65 | 78 20 63 6c 61 73 73 65 |and Rege|x classe|
|00000690| 73 2e 0a 3c 49 6e 74 65 | 67 65 72 3d 3e 49 6e 74 |s..<Inte|ger=>Int|
|000006a0| 65 67 65 72 3e 3a 20 20 | 20 20 20 20 20 20 20 4d |eger>: | M|
|000006b0| 75 6c 74 69 70 6c 65 20 | 70 72 65 63 69 73 69 6f |ultiple |precisio|
|000006c0| 6e 20 49 6e 74 65 67 65 | 72 20 63 6c 61 73 73 2e |n Intege|r class.|
|000006d0| 0a 3c 52 61 74 69 6f 6e | 61 6c 3d 3e 52 61 74 69 |.<Ration|al=>Rati|
|000006e0| 6f 6e 61 6c 3e 3a 20 20 | 20 20 20 20 20 20 4d 75 |onal>: | Mu|
|000006f0| 6c 74 69 70 6c 65 20 70 | 72 65 63 69 73 69 6f 6e |ltiple p|recision|
|00000700| 20 52 61 74 69 6f 6e 61 | 6c 20 63 6c 61 73 73 0a | Rationa|l class.|
|00000710| 3c 43 6f 6d 70 6c 65 78 | 3d 3e 43 6f 6d 70 6c 65 |<Complex|=>Comple|
|00000720| 78 3e 3a 20 20 20 20 20 | 20 20 20 20 43 6f 6d 70 |x>: | Comp|
|00000730| 6c 65 78 20 6e 75 6d 62 | 65 72 20 63 6c 61 73 73 |lex numb|er class|
|00000740| 0a 3c 46 69 78 3d 3e 46 | 69 78 3e 3a 20 20 20 20 |.<Fix=>F|ix>: |
|00000750| 20 20 20 20 20 20 20 20 | 20 46 69 78 65 64 20 70 | | Fixed p|
|00000760| 6f 69 6e 74 20 70 72 6f | 70 6f 72 74 69 6f 6e 20 |oint pro|portion |
|00000770| 63 6c 61 73 73 65 73 0a | 3c 42 69 74 3d 3e 42 69 |classes.|<Bit=>Bi|
|00000780| 74 3e 3a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |t>: | |
|00000790| 42 69 74 53 65 74 20 61 | 6e 64 20 42 69 74 53 74 |BitSet a|nd BitSt|
|000007a0| 72 69 6e 67 20 63 6c 61 | 73 73 65 73 0a 3c 52 61 |ring cla|sses.<Ra|
|000007b0| 6e 64 6f 6d 3d 3e 52 61 | 6e 64 6f 6d 3e 3a 20 20 |ndom=>Ra|ndom>: |
|000007c0| 20 20 20 20 20 20 20 20 | 52 61 6e 64 6f 6d 20 6e | |Random n|
|000007d0| 75 6d 62 65 72 20 67 65 | 6e 65 72 61 74 6f 72 73 |umber ge|nerators|
|000007e0| 0a 3c 44 61 74 61 3d 3e | 44 61 74 61 3e 3a 20 20 |.<Data=>|Data>: |
|000007f0| 20 20 20 20 20 20 20 20 | 20 20 53 61 6d 70 6c 65 | | Sample|
|00000800| 53 74 61 74 69 73 74 69 | 63 20 61 6e 64 20 72 65 |Statisti|c and re|
|00000810| 6c 61 74 65 64 20 63 6c | 61 73 73 65 73 20 66 6f |lated cl|asses fo|
|00000820| 72 20 64 61 74 61 20 63 | 6f 6c 6c 65 63 74 69 6f |r data c|ollectio|
|00000830| 6e 0a 3c 43 75 72 73 65 | 73 3d 3e 43 75 72 73 65 |n.<Curse|s=>Curse|
|00000840| 73 3e 3a 20 20 20 20 20 | 20 20 20 20 20 43 75 72 |s>: | Cur|
|00000850| 73 65 73 57 69 6e 64 6f | 77 20 63 6c 61 73 73 0a |sesWindo|w class.|
|00000860| 3c 4c 69 73 74 3d 3e 4c | 69 73 74 3e 3a 20 20 20 |<List=>L|ist>: |
|00000870| 20 20 20 20 20 20 20 20 | 20 4c 69 73 70 2d 6c 69 | | Lisp-li|
|00000880| 6b 65 20 4c 69 73 74 20 | 70 72 6f 74 6f 74 79 70 |ke List |prototyp|
|00000890| 65 0a 3c 4c 69 6e 6b 4c | 69 73 74 3d 3e 4c 69 6e |e.<LinkL|ist=>Lin|
|000008a0| 6b 4c 69 73 74 3e 3a 20 | 20 20 20 20 20 20 20 53 |kList>: | S|
|000008b0| 69 6e 67 6c 79 20 61 6e | 64 20 64 6f 75 62 6c 79 |ingly an|d doubly|
|000008c0| 20 6c 69 6e 6b 65 64 20 | 6c 69 73 74 20 63 6c 61 | linked |list cla|
|000008d0| 73 73 20 70 72 6f 74 6f | 74 79 70 65 73 0a 3c 56 |ss proto|types.<V|
|000008e0| 65 63 74 6f 72 3d 3e 56 | 65 63 74 6f 72 3e 3a 20 |ector=>V|ector>: |
|000008f0| 20 20 20 20 20 20 20 20 | 20 56 65 63 74 6f 72 20 | | Vector |
|00000900| 70 72 6f 74 6f 74 79 70 | 65 73 0a 3c 50 6c 65 78 |prototyp|es.<Plex|
|00000910| 3d 3e 50 6c 65 78 3e 3a | 20 20 20 20 20 20 20 20 |=>Plex>:| |
|00000920| 20 20 20 20 50 6c 65 78 | 20 28 61 64 6a 75 73 74 | Plex| (adjust|
|00000930| 61 62 6c 65 20 61 72 72 | 61 79 29 20 70 72 6f 74 |able arr|ay) prot|
|00000940| 6f 74 79 70 65 73 0a 3c | 53 74 61 63 6b 3d 3e 53 |otypes.<|Stack=>S|
|00000950| 74 61 63 6b 3e 3a 20 20 | 20 20 20 20 20 20 20 20 |tack>: | |
|00000960| 20 53 74 61 63 6b 20 70 | 72 6f 74 6f 74 79 70 65 | Stack p|rototype|
|00000970| 73 0a 3c 51 75 65 75 65 | 3d 3e 51 75 65 75 65 3e |s.<Queue|=>Queue>|
|00000980| 3a 20 20 20 20 20 20 20 | 20 20 20 20 51 75 65 75 |: | Queu|
|00000990| 65 20 70 72 6f 74 6f 74 | 79 70 65 73 0a 3c 44 65 |e protot|ypes.<De|
|000009a0| 71 75 65 3d 3e 44 65 71 | 75 65 3e 3a 20 20 20 20 |que=>Deq|ue>: |
|000009b0| 20 20 20 20 20 20 20 44 | 6f 75 62 6c 65 20 65 6e | D|ouble en|
|000009c0| 64 65 64 20 71 75 65 75 | 65 20 70 72 6f 74 6f 74 |ded queu|e protot|
|000009d0| 79 70 65 73 0a 3c 50 51 | 3d 3e 50 51 3e 3a 20 20 |ypes.<PQ|=>PQ>: |
|000009e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 48 65 61 70 | | Heap|
|000009f0| 20 28 70 72 69 6f 72 69 | 74 79 20 71 75 65 75 65 | (priori|ty queue|
|00000a00| 29 20 63 6c 61 73 73 20 | 70 72 6f 74 6f 74 79 70 |) class |prototyp|
|00000a10| 65 73 0a 3c 53 65 74 3d | 3e 53 65 74 3e 3a 20 20 |es.<Set=|>Set>: |
|00000a20| 20 20 20 20 20 20 20 20 | 20 20 20 53 65 74 20 63 | | Set c|
|00000a30| 6c 61 73 73 20 70 72 6f | 74 6f 74 79 70 65 73 0a |lass pro|totypes.|
|00000a40| 3c 42 61 67 3d 3e 42 61 | 67 3e 3a 20 20 20 20 20 |<Bag=>Ba|g>: |
|00000a50| 20 20 20 20 20 20 20 20 | 42 61 67 20 63 6c 61 73 | |Bag clas|
|00000a60| 73 20 70 72 6f 74 6f 74 | 79 70 65 73 0a 3c 4d 61 |s protot|ypes.<Ma|
|00000a70| 70 3d 3e 4d 61 70 3e 3a | 20 20 20 20 20 20 20 20 |p=>Map>:| |
|00000a80| 20 20 20 20 20 4d 61 70 | 20 28 41 73 73 6f 63 69 | Map| (Associ|
|00000a90| 61 74 69 76 65 20 61 72 | 72 61 79 29 20 70 72 6f |ative ar|ray) pro|
|00000aa0| 74 6f 74 79 70 65 73 0a | 3c 47 65 74 4f 70 74 3d |totypes.|<GetOpt=|
|00000ab0| 3e 47 65 74 4f 70 74 3e | 3a 20 20 20 20 20 20 20 |>GetOpt>|: |
|00000ac0| 20 20 20 43 2b 2b 20 63 | 6c 61 73 73 2d 62 61 73 | C++ c|lass-bas|
|00000ad0| 65 64 20 76 65 72 73 69 | 6f 6e 20 6f 66 20 74 68 |ed versi|on of th|
|00000ae0| 65 20 47 4e 55 5c 2f 55 | 4e 49 58 20 67 65 74 6f |e GNU\/U|NIX geto|
|00000af0| 70 74 20 66 75 6e 63 74 | 69 6f 6e 0a 3c 50 72 6f |pt funct|ion.<Pro|
|00000b00| 6a 65 63 74 73 3d 3e 50 | 72 6f 6a 65 63 74 73 3e |jects=>P|rojects>|
|00000b10| 3a 09 20 20 20 20 54 68 | 69 6e 67 73 20 53 74 69 |:. Th|ings Sti|
|00000b20| 6c 6c 20 4c 65 66 74 20 | 74 6f 20 64 6f 0a 23 57 |ll Left |to do.#W|
|00000b30| 72 61 70 20 6f 6e 0a 0a | 44 41 54 41 28 07 00 00 |rap on..|DATA(...|
|00000b40| 41 6c 6c 6f 63 52 69 6e | 67 0a 50 72 65 76 69 6f |AllocRin|g.Previo|
|00000b50| 75 73 3a 20 3c 4f 62 73 | 74 61 63 6b 3d 3e 4f 62 |us: <Obs|tack=>Ob|
|00000b60| 73 74 61 63 6b 3e 20 2a | 20 4e 65 78 74 3a 20 3c |stack> *| Next: <|
|00000b70| 53 74 72 69 6e 67 3d 3e | 53 74 72 69 6e 67 3e 20 |String=>|String> |
|00000b80| 2a 20 55 70 3a 20 3c 54 | 6f 70 3d 3e 21 52 6f 6f |* Up: <T|op=>!Roo|
|00000b90| 74 3e 0a 0a 23 57 72 61 | 70 20 6f 6e 0a 7b 66 48 |t>..#Wra|p on.{fH|
|00000ba0| 32 7d 54 68 65 20 41 6c | 6c 6f 63 52 69 6e 67 20 |2}The Al|locRing |
|00000bb0| 63 6c 61 73 73 7b 66 7d | 0a 0a 41 6e 20 41 6c 6c |class{f}|..An All|
|00000bc0| 6f 63 52 69 6e 67 20 69 | 73 20 61 20 62 6f 75 6e |ocRing i|s a boun|
|00000bd0| 64 65 64 20 72 69 6e 67 | 20 28 63 69 72 63 75 6c |ded ring| (circul|
|00000be0| 61 72 20 6c 69 73 74 29 | 2c 20 65 61 63 68 20 6f |ar list)|, each o|
|00000bf0| 66 20 77 68 6f 73 65 20 | 65 6c 65 6d 65 6e 74 73 |f whose |elements|
|00000c00| 0a 63 6f 6e 74 61 69 6e | 73 20 61 20 70 6f 69 6e |.contain|s a poin|
|00000c10| 74 65 72 20 74 6f 20 73 | 6f 6d 65 20 73 70 61 63 |ter to s|ome spac|
|00000c20| 65 20 61 6c 6c 6f 63 61 | 74 65 64 20 76 69 61 20 |e alloca|ted via |
|00000c30| 7b 66 43 6f 64 65 7d 6e | 65 77 0a 63 68 61 72 5b |{fCode}n|ew.char[|
|00000c40| 73 6f 6d 65 5c 5f 73 69 | 7a 65 5d 7b 66 7d 2e 20 |some\_si|ze]{f}. |
|00000c50| 54 68 65 20 65 6e 74 72 | 69 65 73 20 61 72 65 20 |The entr|ies are |
|00000c60| 75 73 65 64 20 63 79 63 | 6c 69 63 6c 79 2e 20 20 |used cyc|licly. |
|00000c70| 54 68 65 20 73 69 7a 65 | 2c 20 6e 2c 20 6f 66 20 |The size|, n, of |
|00000c80| 74 68 65 0a 72 69 6e 67 | 20 69 73 20 66 69 78 65 |the.ring| is fixe|
|00000c90| 64 20 61 74 20 63 6f 6e | 73 74 72 75 63 74 69 6f |d at con|structio|
|00000ca0| 6e 2e 20 41 66 74 65 72 | 20 74 68 61 74 2c 20 65 |n. After| that, e|
|00000cb0| 76 65 72 79 20 6e 74 68 | 20 75 73 65 20 6f 66 20 |very nth| use of |
|00000cc0| 74 68 65 20 72 69 6e 67 | 0a 77 69 6c 6c 20 72 65 |the ring|.will re|
|00000cd0| 75 73 65 20 28 6f 72 20 | 72 65 61 6c 6c 6f 63 61 |use (or |realloca|
|00000ce0| 74 65 29 20 74 68 65 20 | 73 61 6d 65 20 73 70 61 |te) the |same spa|
|00000cf0| 63 65 2e 20 41 6c 6c 6f | 63 52 69 6e 67 73 20 61 |ce. Allo|cRings a|
|00000d00| 72 65 20 6e 65 65 64 65 | 64 20 69 6e 0a 6f 72 64 |re neede|d in.ord|
|00000d10| 65 72 20 74 6f 20 74 65 | 6d 70 6f 72 61 72 69 6c |er to te|mporaril|
|00000d20| 79 20 68 6f 6c 64 20 63 | 68 75 6e 6b 73 20 6f 66 |y hold c|hunks of|
|00000d30| 20 73 70 61 63 65 20 74 | 68 61 74 20 61 72 65 20 | space t|hat are |
|00000d40| 6e 65 65 64 65 64 20 74 | 72 61 6e 73 69 65 6e 74 |needed t|ransient|
|00000d50| 6c 79 2c 0a 62 75 74 20 | 61 63 72 6f 73 73 20 63 |ly,.but |across c|
|00000d60| 6f 6e 73 74 72 75 63 74 | 6f 72 2d 64 65 73 74 72 |onstruct|or-destr|
|00000d70| 75 63 74 6f 72 20 73 63 | 6f 70 65 73 2e 20 54 68 |uctor sc|opes. Th|
|00000d80| 65 79 20 6d 61 69 6e 6c | 79 20 75 73 65 66 75 6c |ey mainl|y useful|
|00000d90| 20 66 6f 72 20 73 74 6f | 72 69 6e 67 0a 73 74 72 | for sto|ring.str|
|00000da0| 69 6e 67 73 20 63 6f 6e | 74 61 69 6e 69 6e 67 20 |ings con|taining |
|00000db0| 66 6f 72 6d 61 74 74 65 | 64 20 63 68 61 72 61 63 |formatte|d charac|
|00000dc0| 74 65 72 73 20 74 6f 20 | 70 72 69 6e 74 20 61 63 |ters to |print ac|
|00000dd0| 72 6f 73 73 20 76 61 72 | 69 6f 75 73 0a 66 75 6e |ross var|ious.fun|
|00000de0| 63 74 69 6f 6e 73 20 61 | 6e 64 20 63 6f 65 72 63 |ctions a|nd coerc|
|00000df0| 69 6f 6e 73 2e 20 54 68 | 65 73 65 20 73 74 72 69 |ions. Th|ese stri|
|00000e00| 6e 67 73 20 61 72 65 20 | 6e 65 65 64 65 64 20 61 |ngs are |needed a|
|00000e10| 63 72 6f 73 73 20 72 6f | 75 74 69 6e 65 73 2c 20 |cross ro|utines, |
|00000e20| 73 6f 0a 6d 61 79 20 6e | 6f 74 20 62 65 20 64 65 |so.may n|ot be de|
|00000e30| 6c 65 74 65 64 20 69 6e | 20 61 6e 79 20 6f 6e 65 |leted in| any one|
|00000e40| 20 6f 66 20 74 68 65 6d | 2c 20 62 75 74 20 73 68 | of them|, but sh|
|00000e50| 6f 75 6c 64 20 62 65 20 | 72 65 63 6f 76 65 72 65 |ould be |recovere|
|00000e60| 64 20 61 74 20 73 6f 6d | 65 0a 70 6f 69 6e 74 2e |d at som|e.point.|
|00000e70| 20 49 6e 20 6f 74 68 65 | 72 20 77 6f 72 64 73 2c | In othe|r words,|
|00000e80| 20 61 6e 20 41 6c 6c 6f | 63 52 69 6e 67 20 69 73 | an Allo|cRing is|
|00000e90| 20 61 6e 20 65 78 74 72 | 65 6d 65 6c 79 20 73 69 | an extr|emely si|
|00000ea0| 6d 70 6c 65 20 6d 69 6e | 64 65 64 0a 67 61 72 62 |mple min|ded.garb|
|00000eb0| 61 67 65 20 63 6f 6c 6c | 65 63 74 69 6f 6e 20 6d |age coll|ection m|
|00000ec0| 65 63 68 61 6e 69 73 6d | 2e 20 54 68 65 20 47 4e |echanism|. The GN|
|00000ed0| 55 20 43 2b 2b 20 6c 69 | 62 72 61 72 79 20 75 73 |U C++ li|brary us|
|00000ee0| 65 64 20 74 6f 20 75 73 | 65 20 6f 6e 65 0a 41 6c |ed to us|e one.Al|
|00000ef0| 6c 6f 63 52 69 6e 67 20 | 66 6f 72 20 73 75 63 68 |locRing |for such|
|00000f00| 20 66 6f 72 6d 61 74 74 | 69 6e 67 20 70 75 72 70 | formatt|ing purp|
|00000f10| 6f 73 65 73 2c 20 62 75 | 74 20 69 74 20 69 73 20 |oses, bu|t it is |
|00000f20| 62 65 69 6e 67 20 70 68 | 61 73 65 64 20 6f 75 74 |being ph|ased out|
|00000f30| 2c 0a 61 6e 64 20 69 73 | 20 6e 6f 77 20 6f 6e 6c |,.and is| now onl|
|00000f40| 79 20 75 73 65 64 20 62 | 79 20 6f 62 73 6f 6c 65 |y used b|y obsole|
|00000f50| 74 65 20 66 75 6e 63 74 | 69 6f 6e 73 2e 0a 54 68 |te funct|ions..Th|
|00000f60| 65 73 65 20 64 61 79 73 | 2c 20 41 6c 6c 6f 63 52 |ese days|, AllocR|
|00000f70| 69 6e 67 73 20 61 72 65 | 20 70 72 6f 62 61 62 6c |ings are| probabl|
|00000f80| 79 20 6e 6f 74 20 76 65 | 72 79 20 75 73 65 66 75 |y not ve|ry usefu|
|00000f90| 6c 2e 0a 0a 53 75 70 70 | 6f 72 74 20 69 6e 63 6c |l...Supp|ort incl|
|00000fa0| 75 64 65 73 3a 0a 0a 23 | 49 6e 64 65 6e 74 20 2b |udes:..#|Indent +|
|00000fb0| 34 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |4..#Inde|nt.{fCod|
|00000fc0| 65 7d 41 6c 6c 6f 63 52 | 69 6e 67 20 61 28 69 6e |e}AllocR|ing a(in|
|00000fd0| 74 20 6e 29 7b 66 7d 0a | 23 49 6e 64 65 6e 74 20 |t n){f}.|#Indent |
|00000fe0| 2b 34 0a 63 6f 6e 73 74 | 72 75 63 74 73 20 61 6e |+4.const|ructs an|
|00000ff0| 20 41 6c 6c 6f 63 20 72 | 69 6e 67 20 77 69 74 68 | Alloc r|ing with|
|00001000| 20 6e 20 65 6e 74 72 69 | 65 73 2c 20 61 6c 6c 20 | n entri|es, all |
|00001010| 6e 75 6c 6c 2e 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b |null...#|Indent.{|
|00001020| 66 43 6f 64 65 7d 76 6f | 69 64 5c 2a 20 6d 65 6d |fCode}vo|id\* mem|
|00001030| 20 3d 20 61 2e 61 6c 6c | 6f 63 28 73 7a 29 7b 66 | = a.all|oc(sz){f|
|00001040| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 6d 6f 76 |}.#Inden|t +4.mov|
|00001050| 65 73 20 74 68 65 20 72 | 69 6e 67 20 70 6f 69 6e |es the r|ing poin|
|00001060| 74 65 72 20 74 6f 20 74 | 68 65 20 6e 65 78 74 20 |ter to t|he next |
|00001070| 65 6e 74 72 79 2c 20 61 | 6e 64 20 72 65 75 73 65 |entry, a|nd reuse|
|00001080| 73 20 74 68 65 20 73 70 | 61 63 65 0a 69 66 20 74 |s the sp|ace.if t|
|00001090| 68 65 69 72 20 69 73 20 | 65 6e 6f 75 67 68 2c 20 |heir is |enough, |
|000010a0| 61 6c 73 6f 20 61 6c 6c | 6f 63 61 74 65 73 20 73 |also all|ocates s|
|000010b0| 70 61 63 65 20 76 69 61 | 20 6e 65 77 20 63 68 61 |pace via| new cha|
|000010c0| 72 5b 73 7a 5d 2e 0a 0a | 23 49 6e 64 65 6e 74 0a |r[sz]...|#Indent.|
|000010d0| 7b 66 43 6f 64 65 7d 69 | 6e 74 20 70 72 65 73 65 |{fCode}i|nt prese|
|000010e0| 6e 74 20 3d 20 61 2e 63 | 6f 6e 74 61 69 6e 73 28 |nt = a.c|ontains(|
|000010f0| 76 6f 69 64 5c 2a 20 70 | 74 72 29 7b 66 7d 0a 23 |void\* p|tr){f}.#|
|00001100| 49 6e 64 65 6e 74 20 2b | 34 0a 72 65 74 75 72 6e |Indent +|4.return|
|00001110| 73 20 74 72 75 65 20 69 | 66 20 70 74 72 20 69 73 |s true i|f ptr is|
|00001120| 20 68 65 6c 64 20 69 6e | 20 6f 6e 65 20 6f 66 20 | held in| one of |
|00001130| 74 68 65 20 72 69 6e 67 | 20 65 6e 74 72 69 65 73 |the ring| entries|
|00001140| 2e 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |...#Inde|nt.{fCod|
|00001150| 65 7d 61 2e 63 6c 65 61 | 72 28 29 7b 66 7d 0a 23 |e}a.clea|r(){f}.#|
|00001160| 49 6e 64 65 6e 74 20 2b | 34 0a 64 65 6c 65 74 65 |Indent +|4.delete|
|00001170| 73 20 61 6c 6c 20 73 70 | 61 63 65 20 70 6f 69 6e |s all sp|ace poin|
|00001180| 74 65 64 20 74 6f 20 69 | 6e 20 61 6e 79 20 65 6e |ted to i|n any en|
|00001190| 74 72 79 2e 20 54 68 69 | 73 20 69 73 20 63 61 6c |try. Thi|s is cal|
|000011a0| 6c 65 64 0a 61 75 74 6f | 6d 61 74 69 63 61 6c 6c |led.auto|maticall|
|000011b0| 79 20 75 70 6f 6e 20 64 | 65 73 74 72 75 63 74 69 |y upon d|estructi|
|000011c0| 6f 6e 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 |on...#In|dent.{fC|
|000011d0| 6f 64 65 7d 61 2e 66 72 | 65 65 28 76 6f 69 64 5c |ode}a.fr|ee(void\|
|000011e0| 2a 20 70 74 72 29 7b 66 | 7d 0a 23 49 6e 64 65 6e |* ptr){f|}.#Inden|
|000011f0| 74 20 2b 34 0a 49 66 20 | 70 74 72 20 69 73 20 6f |t +4.If |ptr is o|
|00001200| 6e 65 20 6f 66 20 74 68 | 65 20 65 6e 74 72 69 65 |ne of th|e entrie|
|00001210| 73 2c 20 63 61 6c 6c 73 | 20 64 65 6c 65 74 65 20 |s, calls| delete |
|00001220| 6f 66 20 74 68 65 20 70 | 6f 69 6e 74 65 72 2c 0a |of the p|ointer,.|
|00001230| 61 6e 64 20 72 65 73 65 | 74 73 20 74 6f 20 65 6e |and rese|ts to en|
|00001240| 74 72 79 20 70 6f 69 6e | 74 65 72 20 74 6f 20 6e |try poin|ter to n|
|00001250| 75 6c 6c 2e 0a 0a 0a 23 | 49 6e 64 65 6e 74 0a 0a |ull....#|Indent..|
|00001260| 46 52 45 45 60 01 00 00 | 2c 00 00 00 80 00 00 00 |FREE`...|,.......|
|00001270| 46 ff ff ff 56 96 fb 2a | b8 0a 00 00 33 00 00 00 |F...V..*|....3...|
|00001280| 00 00 00 00 21 52 6f 6f | 74 00 00 00 38 0b 00 00 |....!Roo|t...8...|
|00001290| 46 ff ff ff c0 af fb 2a | 28 07 00 00 33 00 00 00 |F......*|(...3...|
|000012a0| 00 00 00 00 41 6c 6c 6f | 63 52 69 6e 67 00 00 00 |....Allo|cRing...|
|000012b0| c0 13 00 00 46 ff ff ff | 08 d8 fb 2a d7 0e 00 00 |....F...|...*....|
|000012c0| 13 00 00 00 00 00 00 00 | 42 61 67 00 98 22 00 00 |........|Bag.."..|
|000012d0| 46 ff ff ff 58 be fb 2a | ff 2f 00 00 13 00 00 00 |F...X..*|./......|
|000012e0| 00 00 00 00 42 69 74 00 | 98 52 00 00 46 ff ff ff |....Bit.|.R..F...|
|000012f0| a6 a9 fb 2a 39 0c 00 00 | 13 00 00 00 00 00 00 00 |...*9...|........|
|00001300| 42 75 69 6c 74 69 6e 00 | d4 5e 00 00 46 ff ff ff |Builtin.|.^..F...|
|00001310| e3 b9 fb 2a 3d 0a 00 00 | 13 00 00 00 00 00 00 00 |...*=...|........|
|00001320| 43 6f 6d 70 6c 65 78 00 | 14 69 00 00 46 ff ff ff |Complex.|.i..F...|
|00001330| fb 9b fb 2a 95 04 00 00 | 13 00 00 00 00 00 00 00 |...*....|........|
|00001340| 43 6f 6e 74 72 69 62 75 | 74 6f 00 00 ac 6d 00 00 |Contribu|to...m..|
|00001350| 46 ff ff ff 17 a0 fb 2a | 22 0a 00 00 13 00 00 00 |F......*|".......|
|00001360| 00 00 00 00 43 6f 6e 76 | 65 6e 74 69 6f 6e 00 00 |....Conv|ention..|
|00001370| d0 77 00 00 46 ff ff ff | 13 9b fb 2a 0c 63 00 00 |.w..F...|...*.c..|
|00001380| 13 00 00 00 00 00 00 00 | 43 6f 70 79 69 6e 67 00 |........|Copying.|
|00001390| dc da 00 00 46 ff ff ff | 1f c3 fb 2a 49 0c 00 00 |....F...|...*I...|
|000013a0| 13 00 00 00 00 00 00 00 | 43 75 72 73 65 73 00 00 |........|Curses..|
|000013b0| ff ff ff ff ff ff ff ff | ff ff ff ff ff ff ff ff |........|........|
|000013c0| 44 41 54 41 d7 0e 00 00 | 42 61 67 0a 50 72 65 76 |DATA....|Bag.Prev|
|000013d0| 69 6f 75 73 3a 20 3c 53 | 65 74 3d 3e 53 65 74 3e |ious: <S|et=>Set>|
|000013e0| 20 2a 20 4e 65 78 74 3a | 20 3c 4d 61 70 3d 3e 4d | * Next:| <Map=>M|
|000013f0| 61 70 3e 20 2a 20 55 70 | 3a 20 3c 54 6f 70 3d 3e |ap> * Up|: <Top=>|
|00001400| 21 52 6f 6f 74 3e 0a 0a | 23 57 72 61 70 20 6f 6e |!Root>..|#Wrap on|
|00001410| 0a 7b 66 48 32 7d 42 61 | 67 20 63 6c 61 73 73 20 |.{fH2}Ba|g class |
|00001420| 70 72 6f 74 6f 74 79 70 | 65 73 7b 66 7d 0a 0a 42 |prototyp|es{f}..B|
|00001430| 61 67 20 63 6c 61 73 73 | 65 73 20 6d 61 69 6e 74 |ag class|es maint|
|00001440| 61 69 6e 20 75 6e 62 6f | 75 6e 64 65 64 20 63 6f |ain unbo|unded co|
|00001450| 6c 6c 65 63 74 69 6f 6e | 73 20 6f 66 20 69 74 65 |llection|s of ite|
|00001460| 6d 73 20 70 6f 74 65 6e | 74 69 61 6c 6c 79 0a 63 |ms poten|tially.c|
|00001470| 6f 6e 74 61 69 6e 69 6e | 67 20 20 64 75 70 6c 69 |ontainin|g dupli|
|00001480| 63 61 74 65 20 65 6c 65 | 6d 65 6e 74 73 2e 0a 0a |cate ele|ments...|
|00001490| 54 68 65 73 65 20 61 72 | 65 20 63 75 72 72 65 6e |These ar|e curren|
|000014a0| 74 6c 79 20 69 6d 70 6c | 65 6d 65 6e 74 65 64 20 |tly impl|emented |
|000014b0| 69 6e 20 73 65 76 65 72 | 61 6c 20 77 61 79 73 2c |in sever|al ways,|
|000014c0| 20 64 69 66 66 65 72 69 | 6e 67 20 69 6e 0a 72 65 | differi|ng in.re|
|000014d0| 70 72 65 73 65 6e 74 61 | 74 69 6f 6e 20 73 74 72 |presenta|tion str|
|000014e0| 61 74 65 67 79 2c 20 61 | 6c 67 6f 72 69 74 68 6d |ategy, a|lgorithm|
|000014f0| 69 63 20 65 66 66 69 63 | 69 65 6e 63 79 2c 20 61 |ic effic|iency, a|
|00001500| 6e 64 20 61 70 70 72 6f | 70 72 69 61 74 65 6e 65 |nd appro|priatene|
|00001510| 73 73 20 66 6f 72 0a 76 | 61 72 69 6f 75 73 20 74 |ss for.v|arious t|
|00001520| 61 73 6b 73 2e 20 28 4c | 69 73 74 65 64 20 6e 65 |asks. (L|isted ne|
|00001530| 78 74 20 74 6f 20 65 61 | 63 68 20 61 72 65 20 61 |xt to ea|ch are a|
|00001540| 76 65 72 61 67 65 20 28 | 66 6f 6c 6c 6f 77 65 64 |verage (|followed|
|00001550| 20 62 79 20 77 6f 72 73 | 74 2d 63 61 73 65 2c 0a | by wors|t-case,.|
|00001560| 69 66 20 64 69 66 66 65 | 72 65 6e 74 29 20 74 69 |if diffe|rent) ti|
|00001570| 6d 65 20 63 6f 6d 70 6c | 65 78 69 74 69 65 73 20 |me compl|exities |
|00001580| 66 6f 72 20 5b 61 5d 20 | 61 64 64 69 6e 67 2c 20 |for [a] |adding, |
|00001590| 5b 66 5d 20 66 69 6e 64 | 69 6e 67 20 28 76 69 61 |[f] find|ing (via|
|000015a0| 20 73 65 65 6b 2c 0a 63 | 6f 6e 74 61 69 6e 73 29 | seek,.c|ontains)|
|000015b0| 2c 20 5b 64 5d 20 64 65 | 6c 65 74 69 6e 67 20 65 |, [d] de|leting e|
|000015c0| 6c 65 6d 65 6e 74 73 29 | 2e 0a 0a 0a 23 49 6e 64 |lements)|....#Ind|
|000015d0| 65 6e 74 20 2b 34 0a 0a | 23 49 6e 64 65 6e 74 0a |ent +4..|#Indent.|
|000015e0| 7b 66 43 6f 64 65 7d 58 | 50 42 61 67 73 7b 66 7d |{fCode}X|PBags{f}|
|000015f0| 0a 23 49 6e 64 65 6e 74 | 20 2b 34 0a 69 6d 70 6c |.#Indent| +4.impl|
|00001600| 65 6d 65 6e 74 20 75 6e | 6f 72 64 65 72 65 64 20 |ement un|ordered |
|00001610| 42 61 67 73 20 76 69 61 | 20 58 50 6c 65 78 65 73 |Bags via| XPlexes|
|00001620| 2e 0a 28 5b 61 20 4f 28 | 31 29 5d 2c 20 5b 66 20 |..([a O(|1)], [f |
|00001630| 4f 28 6e 29 5d 2c 20 5b | 64 20 4f 28 6e 29 5d 29 |O(n)], [|d O(n)])|
|00001640| 2e 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |...#Inde|nt.{fCod|
|00001650| 65 7d 4f 58 50 42 61 67 | 73 7b 66 7d 0a 23 49 6e |e}OXPBag|s{f}.#In|
|00001660| 64 65 6e 74 20 2b 34 0a | 69 6d 70 6c 65 6d 65 6e |dent +4.|implemen|
|00001670| 74 20 6f 72 64 65 72 65 | 64 20 42 61 67 73 20 76 |t ordere|d Bags v|
|00001680| 69 61 20 58 50 6c 65 78 | 65 73 2e 0a 28 5b 61 20 |ia XPlex|es..([a |
|00001690| 4f 28 6e 29 5d 2c 20 5b | 66 20 4f 28 6c 6f 67 20 |O(n)], [|f O(log |
|000016a0| 6e 29 5d 2c 20 5b 64 20 | 4f 28 6e 29 5d 29 2e 0a |n)], [d |O(n)])..|
|000016b0| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|000016c0| 53 4c 42 61 67 73 7b 66 | 7d 0a 23 49 6e 64 65 6e |SLBags{f|}.#Inden|
|000016d0| 74 20 2b 34 0a 69 6d 70 | 6c 65 6d 65 6e 74 20 75 |t +4.imp|lement u|
|000016e0| 6e 6f 72 64 65 72 65 64 | 20 42 61 67 73 20 76 69 |nordered| Bags vi|
|000016f0| 61 20 6c 69 6e 6b 65 64 | 20 6c 69 73 74 73 0a 28 |a linked| lists.(|
|00001700| 5b 61 20 4f 28 31 29 5d | 2c 20 5b 66 20 4f 28 6e |[a O(1)]|, [f O(n|
|00001710| 29 5d 2c 20 5b 64 20 4f | 28 6e 29 5d 29 2e 0a 0a |)], [d O|(n)])...|
|00001720| 23 49 6e 64 65 6e 74 0a | 7b 66 43 6f 64 65 7d 4f |#Indent.|{fCode}O|
|00001730| 53 4c 42 61 67 73 7b 66 | 7d 0a 23 49 6e 64 65 6e |SLBags{f|}.#Inden|
|00001740| 74 20 2b 34 0a 69 6d 70 | 6c 65 6d 65 6e 74 20 6f |t +4.imp|lement o|
|00001750| 72 64 65 72 65 64 20 42 | 61 67 73 20 76 69 61 20 |rdered B|ags via |
|00001760| 6c 69 6e 6b 65 64 20 6c | 69 73 74 73 0a 28 5b 61 |linked l|ists.([a|
|00001770| 20 4f 28 6e 29 5d 2c 20 | 5b 66 20 4f 28 6e 29 5d | O(n)], |[f O(n)]|
|00001780| 2c 20 5b 64 20 4f 28 6e | 29 5d 29 2e 0a 0a 23 49 |, [d O(n|)])...#I|
|00001790| 6e 64 65 6e 74 0a 7b 66 | 43 6f 64 65 7d 53 70 6c |ndent.{f|Code}Spl|
|000017a0| 61 79 42 61 67 73 7b 66 | 7d 0a 23 49 6e 64 65 6e |ayBags{f|}.#Inden|
|000017b0| 74 20 2b 34 0a 69 6d 70 | 6c 65 6d 65 6e 74 20 6f |t +4.imp|lement o|
|000017c0| 72 64 65 72 65 64 20 42 | 61 67 73 20 76 69 61 20 |rdered B|ags via |
|000017d0| 53 6c 65 61 74 6f 72 20 | 61 6e 64 20 54 61 72 6a |Sleator |and Tarj|
|000017e0| 61 6e 27 73 20 28 4a 41 | 43 4d 20 31 39 38 35 29 |an's (JA|CM 1985)|
|000017f0| 0a 73 70 6c 61 79 20 74 | 72 65 65 73 2e 20 54 68 |.splay t|rees. Th|
|00001800| 65 20 61 6c 67 6f 72 69 | 74 68 6d 73 20 75 73 65 |e algori|thms use|
|00001810| 20 61 20 76 65 72 73 69 | 6f 6e 20 6f 66 20 60 60 | a versi|on of ``|
|00001820| 73 69 6d 70 6c 65 20 74 | 6f 70 2d 64 6f 77 6e 0a |simple t|op-down.|
|00001830| 73 70 6c 61 79 69 6e 67 | 27 27 20 28 64 65 73 63 |splaying|'' (desc|
|00001840| 72 69 62 65 64 20 6f 6e | 20 70 61 67 65 20 36 36 |ribed on| page 66|
|00001850| 39 20 6f 66 20 74 68 65 | 20 61 72 74 69 63 6c 65 |9 of the| article|
|00001860| 29 2e 0a 28 41 6d 6f 72 | 74 69 7a 65 64 3a 20 5b |)..(Amor|tized: [|
|00001870| 61 20 4f 28 6c 6f 67 20 | 6e 29 5d 2c 20 5b 66 20 |a O(log |n)], [f |
|00001880| 4f 28 6c 6f 67 20 6e 29 | 5d 2c 20 5b 64 20 4f 28 |O(log n)|], [d O(|
|00001890| 6c 6f 67 20 6e 29 5d 29 | 2e 0a 0a 23 49 6e 64 65 |log n)])|...#Inde|
|000018a0| 6e 74 0a 7b 66 43 6f 64 | 65 7d 56 48 42 61 67 73 |nt.{fCod|e}VHBags|
|000018b0| 7b 66 7d 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 69 |{f}.#Ind|ent +4.i|
|000018c0| 6d 70 6c 65 6d 65 6e 74 | 20 75 6e 6f 72 64 65 72 |mplement| unorder|
|000018d0| 65 64 20 42 61 67 73 20 | 76 69 61 20 68 61 73 68 |ed Bags |via hash|
|000018e0| 20 74 61 62 6c 65 73 2e | 0a 54 68 65 20 74 61 62 | tables.|.The tab|
|000018f0| 6c 65 73 20 61 72 65 20 | 61 75 74 6f 6d 61 74 69 |les are |automati|
|00001900| 63 61 6c 6c 79 20 72 65 | 73 69 7a 65 64 20 77 68 |cally re|sized wh|
|00001910| 65 6e 20 74 68 65 69 72 | 20 63 61 70 61 63 69 74 |en their| capacit|
|00001920| 79 20 69 73 20 65 78 68 | 61 75 73 74 65 64 2e 0a |y is exh|austed..|
|00001930| 28 5b 61 20 4f 28 31 29 | 5c 2f 4f 28 6e 29 5d 2c |([a O(1)|\/O(n)],|
|00001940| 20 5b 66 20 4f 28 31 29 | 5c 2f 4f 28 6e 29 5d 2c | [f O(1)|\/O(n)],|
|00001950| 20 5b 64 20 4f 28 31 29 | 5c 2f 4f 28 6e 29 5d 29 | [d O(1)|\/O(n)])|
|00001960| 2e 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |...#Inde|nt.{fCod|
|00001970| 65 7d 43 48 42 61 67 73 | 7b 66 7d 0a 23 49 6e 64 |e}CHBags|{f}.#Ind|
|00001980| 65 6e 74 20 2b 34 0a 69 | 6d 70 6c 65 6d 65 6e 74 |ent +4.i|mplement|
|00001990| 20 75 6e 6f 72 64 65 72 | 65 64 20 42 61 67 73 20 | unorder|ed Bags |
|000019a0| 76 69 61 20 63 68 61 69 | 6e 65 64 20 68 61 73 68 |via chai|ned hash|
|000019b0| 20 74 61 62 6c 65 73 2e | 0a 28 5b 61 20 4f 28 31 | tables.|.([a O(1|
|000019c0| 29 5c 2f 4f 28 6e 29 5d | 2c 20 5b 66 20 4f 28 31 |)\/O(n)]|, [f O(1|
|000019d0| 29 5c 2f 4f 28 6e 29 5d | 2c 20 5b 64 20 4f 28 31 |)\/O(n)]|, [d O(1|
|000019e0| 29 5c 2f 4f 28 6e 29 5d | 29 2e 0a 0a 0a 23 49 6e |)\/O(n)]|)....#In|
|000019f0| 64 65 6e 74 0a 0a 54 68 | 65 20 69 6d 70 6c 65 6d |dent..Th|e implem|
|00001a00| 65 6e 74 61 74 69 6f 6e | 73 20 64 69 66 66 65 72 |entation|s differ|
|00001a10| 20 69 6e 20 77 68 65 74 | 68 65 72 20 74 68 65 69 | in whet|her thei|
|00001a20| 72 20 63 6f 6e 73 74 72 | 75 63 74 6f 72 73 0a 72 |r constr|uctors.r|
|00001a30| 65 71 75 69 72 65 20 61 | 6e 20 61 72 67 75 6d 65 |equire a|n argume|
|00001a40| 6e 74 20 74 6f 20 73 70 | 65 63 69 66 79 20 74 68 |nt to sp|ecify th|
|00001a50| 65 69 72 20 69 6e 69 74 | 69 61 6c 20 63 61 70 61 |eir init|ial capa|
|00001a60| 63 69 74 79 2e 20 49 6e | 69 74 69 61 6c 0a 63 61 |city. In|itial.ca|
|00001a70| 70 61 63 69 74 69 65 73 | 20 61 72 65 20 72 65 71 |pacities| are req|
|00001a80| 75 69 72 65 64 20 66 6f | 72 20 70 6c 65 78 20 61 |uired fo|r plex a|
|00001a90| 6e 64 20 68 61 73 68 20 | 74 61 62 6c 65 20 62 61 |nd hash |table ba|
|00001aa0| 73 65 64 20 42 61 67 73 | 2e 20 20 49 66 20 6e 6f |sed Bags|. If no|
|00001ab0| 6e 65 20 69 73 0a 67 69 | 76 65 6e 20 7b 66 43 6f |ne is.gi|ven {fCo|
|00001ac0| 64 65 7d 44 45 46 41 55 | 4c 54 5c 5f 49 4e 49 54 |de}DEFAU|LT\_INIT|
|00001ad0| 49 41 4c 5c 5f 43 41 50 | 41 43 49 54 59 7b 66 7d |IAL\_CAP|ACITY{f}|
|00001ae0| 20 28 66 72 6f 6d 20 7b | 66 43 69 74 65 7d 5c 3c | (from {|fCite}\<|
|00001af0| 54 5c 3e 64 65 66 73 2e | 68 7b 66 7d 29 20 69 73 |T\>defs.|h{f}) is|
|00001b00| 20 75 73 65 64 2e 0a 0a | 42 61 67 73 20 73 75 70 | used...|Bags sup|
|00001b10| 70 6f 72 74 20 74 68 65 | 20 66 6f 6c 6c 6f 77 69 |port the| followi|
|00001b20| 6e 67 20 6f 70 65 72 61 | 74 69 6f 6e 73 2c 20 66 |ng opera|tions, f|
|00001b30| 6f 72 20 73 6f 6d 65 20 | 63 6c 61 73 73 20 7b 66 |or some |class {f|
|00001b40| 43 6f 64 65 7d 42 61 67 | 7b 66 7d 2c 0a 69 6e 73 |Code}Bag|{f},.ins|
|00001b50| 74 61 6e 63 65 73 20 7b | 66 43 6f 64 65 7d 61 7b |tances {|fCode}a{|
|00001b60| 66 7d 20 61 6e 64 20 7b | 66 43 6f 64 65 7d 62 7b |f} and {|fCode}b{|
|00001b70| 66 7d 2c 20 7b 66 43 6f | 64 65 7d 50 69 78 20 69 |f}, {fCo|de}Pix i|
|00001b80| 6e 64 7b 66 7d 2c 20 61 | 6e 64 20 62 61 73 65 20 |nd{f}, a|nd base |
|00001b90| 0a 65 6c 65 6d 65 6e 74 | 20 7b 66 43 6f 64 65 7d |.element| {fCode}|
|00001ba0| 78 7b 66 7d 2e 20 53 69 | 6e 63 65 20 61 6c 6c 20 |x{f}. Si|nce all |
|00001bb0| 69 6d 70 6c 65 6d 65 6e | 74 61 74 69 6f 6e 73 20 |implemen|tations |
|00001bc0| 61 72 65 20 76 69 72 74 | 75 61 6c 20 64 65 72 69 |are virt|ual deri|
|00001bd0| 76 65 64 20 63 6c 61 73 | 73 65 73 0a 6f 66 20 74 |ved clas|ses.of t|
|00001be0| 68 65 20 7b 66 43 6f 64 | 65 7d 5c 3c 54 5c 3e 42 |he {fCod|e}\<T\>B|
|00001bf0| 61 67 7b 66 7d 20 63 6c | 61 73 73 2c 20 69 74 20 |ag{f} cl|ass, it |
|00001c00| 69 73 20 70 6f 73 73 69 | 62 6c 65 20 74 6f 20 6d |is possi|ble to m|
|00001c10| 69 78 20 61 6e 64 20 6d | 61 74 63 68 20 6f 70 65 |ix and m|atch ope|
|00001c20| 72 61 74 69 6f 6e 73 0a | 61 63 72 6f 73 73 20 64 |rations.|across d|
|00001c30| 69 66 66 65 72 65 6e 74 | 20 69 6d 70 6c 65 6d 65 |ifferent| impleme|
|00001c40| 6e 74 61 74 69 6f 6e 73 | 2c 20 61 6c 74 68 6f 75 |ntations|, althou|
|00001c50| 67 68 2c 20 61 73 20 75 | 73 75 61 6c 2c 20 6f 70 |gh, as u|sual, op|
|00001c60| 65 72 61 74 69 6f 6e 73 | 0a 61 72 65 20 67 65 6e |erations|.are gen|
|00001c70| 65 72 61 6c 6c 79 20 66 | 61 73 74 65 72 20 77 68 |erally f|aster wh|
|00001c80| 65 6e 20 74 68 65 20 70 | 61 72 74 69 63 75 6c 61 |en the p|articula|
|00001c90| 72 20 63 6c 61 73 73 65 | 73 20 61 72 65 20 73 70 |r classe|s are sp|
|00001ca0| 65 63 69 66 69 65 64 0a | 69 6e 20 66 75 6e 63 74 |ecified.|in funct|
|00001cb0| 69 6f 6e 73 20 6f 70 65 | 72 61 74 69 6e 67 20 6f |ions ope|rating o|
|00001cc0| 6e 20 42 61 67 73 2e 20 | 0a 0a 50 69 78 2d 62 61 |n Bags. |..Pix-ba|
|00001cd0| 73 65 64 20 6f 70 65 72 | 61 74 69 6f 6e 73 20 61 |sed oper|ations a|
|00001ce0| 72 65 20 6d 6f 72 65 20 | 66 75 6c 6c 79 20 64 65 |re more |fully de|
|00001cf0| 73 63 72 69 62 65 64 20 | 69 6e 20 74 68 65 20 73 |scribed |in the s|
|00001d00| 65 63 74 69 6f 6e 0a 6f | 6e 20 50 69 78 65 73 2e |ection.o|n Pixes.|
|00001d10| 20 5c 2a 4e 6f 74 65 20 | 3c 50 69 78 3d 3e 50 69 | \*Note |<Pix=>Pi|
|00001d20| 78 3e 0a 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 0a |x>..#Ind|ent +4..|
|00001d30| 23 49 6e 64 65 6e 74 0a | 7b 66 43 6f 64 65 7d 42 |#Indent.|{fCode}B|
|00001d40| 61 67 20 61 3b 20 6f 72 | 20 42 61 67 20 61 28 69 |ag a; or| Bag a(i|
|00001d50| 6e 74 20 69 6e 69 74 69 | 61 6c 5c 5f 73 69 7a 65 |nt initi|al\_size|
|00001d60| 29 7b 66 7d 0a 23 49 6e | 64 65 6e 74 20 2b 34 0a |){f}.#In|dent +4.|
|00001d70| 44 65 63 6c 61 72 65 73 | 20 61 20 74 6f 20 62 65 |Declares| a to be|
|00001d80| 20 61 6e 20 65 6d 70 74 | 79 20 42 61 67 2e 20 54 | an empt|y Bag. T|
|00001d90| 68 65 20 73 65 63 6f 6e | 64 20 76 65 72 73 69 6f |he secon|d versio|
|00001da0| 6e 20 69 73 20 61 6c 6c | 6f 77 65 64 20 69 6e 0a |n is all|owed in.|
|00001db0| 42 61 67 20 63 6c 61 73 | 73 65 73 20 74 68 61 74 |Bag clas|ses that|
|00001dc0| 20 72 65 71 75 69 72 65 | 20 69 6e 69 74 69 61 6c | require| initial|
|00001dd0| 20 63 61 70 61 63 69 74 | 79 20 6f 72 20 73 69 7a | capacit|y or siz|
|00001de0| 69 6e 67 20 73 70 65 63 | 69 66 69 63 61 74 69 6f |ing spec|ificatio|
|00001df0| 6e 73 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 |ns...#In|dent.{fC|
|00001e00| 6f 64 65 7d 61 2e 65 6d | 70 74 79 28 29 7b 66 7d |ode}a.em|pty(){f}|
|00001e10| 0a 23 49 6e 64 65 6e 74 | 20 2b 34 0a 72 65 74 75 |.#Indent| +4.retu|
|00001e20| 72 6e 73 20 74 72 75 65 | 20 69 66 20 61 20 69 73 |rns true| if a is|
|00001e30| 20 65 6d 70 74 79 2e 0a | 0a 23 49 6e 64 65 6e 74 | empty..|.#Indent|
|00001e40| 0a 7b 66 43 6f 64 65 7d | 61 2e 6c 65 6e 67 74 68 |.{fCode}|a.length|
|00001e50| 28 29 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |(){f}.#I|ndent +4|
|00001e60| 0a 72 65 74 75 72 6e 73 | 20 74 68 65 20 6e 75 6d |.returns| the num|
|00001e70| 62 65 72 20 6f 66 20 65 | 6c 65 6d 65 6e 74 73 20 |ber of e|lements |
|00001e80| 69 6e 20 61 2e 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b |in a...#|Indent.{|
|00001e90| 66 43 6f 64 65 7d 69 6e | 64 20 3d 20 61 2e 61 64 |fCode}in|d = a.ad|
|00001ea0| 64 28 78 29 7b 66 7d 0a | 23 49 6e 64 65 6e 74 20 |d(x){f}.|#Indent |
|00001eb0| 2b 34 0a 69 6e 73 65 72 | 74 73 20 78 20 69 6e 74 |+4.inser|ts x int|
|00001ec0| 6f 20 61 2c 20 72 65 74 | 75 72 6e 69 6e 67 20 69 |o a, ret|urning i|
|00001ed0| 74 73 20 69 6e 64 65 78 | 2e 0a 0a 23 49 6e 64 65 |ts index|...#Inde|
|00001ee0| 6e 74 0a 7b 66 43 6f 64 | 65 7d 61 2e 64 65 6c 28 |nt.{fCod|e}a.del(|
|00001ef0| 78 29 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |x){f}.#I|ndent +4|
|00001f00| 0a 64 65 6c 65 74 65 73 | 20 6f 6e 65 20 6f 63 63 |.deletes| one occ|
|00001f10| 75 72 72 65 6e 63 65 20 | 6f 66 20 78 20 66 72 6f |urrence |of x fro|
|00001f20| 6d 20 61 2e 0a 0a 23 49 | 6e 64 65 6e 74 0a 7b 66 |m a...#I|ndent.{f|
|00001f30| 43 6f 64 65 7d 61 2e 72 | 65 6d 6f 76 65 28 78 29 |Code}a.r|emove(x)|
|00001f40| 7b 66 7d 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 64 |{f}.#Ind|ent +4.d|
|00001f50| 65 6c 65 74 65 73 20 61 | 6c 6c 20 6f 63 63 75 72 |eletes a|ll occur|
|00001f60| 72 65 6e 63 65 73 20 6f | 66 20 78 20 66 72 6f 6d |rences o|f x from|
|00001f70| 20 61 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 | a...#In|dent.{fC|
|00001f80| 6f 64 65 7d 61 2e 63 6c | 65 61 72 28 29 7b 66 7d |ode}a.cl|ear(){f}|
|00001f90| 0a 23 49 6e 64 65 6e 74 | 20 2b 34 0a 64 65 6c 65 |.#Indent| +4.dele|
|00001fa0| 74 65 73 20 61 6c 6c 20 | 65 6c 65 6d 65 6e 74 73 |tes all |elements|
|00001fb0| 20 66 72 6f 6d 20 61 3b | 0a 0a 23 49 6e 64 65 6e | from a;|..#Inden|
|00001fc0| 74 0a 7b 66 43 6f 64 65 | 7d 61 2e 63 6f 6e 74 61 |t.{fCode|}a.conta|
|00001fd0| 69 6e 73 28 78 29 7b 66 | 7d 0a 23 49 6e 64 65 6e |ins(x){f|}.#Inden|
|00001fe0| 74 20 2b 34 0a 72 65 74 | 75 72 6e 73 20 74 72 75 |t +4.ret|urns tru|
|00001ff0| 65 20 69 66 20 78 20 69 | 73 20 69 6e 20 61 2e 0a |e if x i|s in a..|
|00002000| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|00002010| 61 2e 6e 6f 66 28 78 29 | 7b 66 7d 0a 23 49 6e 64 |a.nof(x)|{f}.#Ind|
|00002020| 65 6e 74 20 2b 34 0a 72 | 65 74 75 72 6e 73 20 74 |ent +4.r|eturns t|
|00002030| 68 65 20 6e 75 6d 62 65 | 72 20 6f 66 20 6f 63 63 |he numbe|r of occ|
|00002040| 75 72 72 65 6e 63 65 73 | 20 6f 66 20 78 20 69 6e |urrences| of x in|
|00002050| 20 61 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 | a...#In|dent.{fC|
|00002060| 6f 64 65 7d 61 28 69 6e | 64 29 7b 66 7d 0a 23 49 |ode}a(in|d){f}.#I|
|00002070| 6e 64 65 6e 74 20 2b 34 | 0a 72 65 74 75 72 6e 73 |ndent +4|.returns|
|00002080| 20 61 20 72 65 66 65 72 | 65 6e 63 65 20 74 6f 20 | a refer|ence to |
|00002090| 74 68 65 20 69 74 65 6d | 20 69 6e 64 65 78 65 64 |the item| indexed|
|000020a0| 20 62 79 20 69 6e 64 2e | 0a 0a 23 49 6e 64 65 6e | by ind.|..#Inden|
|000020b0| 74 0a 7b 66 43 6f 64 65 | 7d 69 6e 74 20 3d 20 61 |t.{fCode|}int = a|
|000020c0| 2e 66 69 72 73 74 28 29 | 7b 66 7d 0a 23 49 6e 64 |.first()|{f}.#Ind|
|000020d0| 65 6e 74 20 2b 34 0a 72 | 65 74 75 72 6e 73 20 74 |ent +4.r|eturns t|
|000020e0| 68 65 20 50 69 78 20 6f | 66 20 66 69 72 73 74 20 |he Pix o|f first |
|000020f0| 69 74 65 6d 20 69 6e 20 | 74 68 65 20 42 61 67 20 |item in |the Bag |
|00002100| 6f 72 20 30 20 69 66 20 | 74 68 65 20 42 61 67 20 |or 0 if |the Bag |
|00002110| 69 73 20 65 6d 70 74 79 | 2e 20 0a 46 6f 72 20 6f |is empty|. .For o|
|00002120| 72 64 65 72 65 64 20 42 | 61 67 73 2c 20 74 68 69 |rdered B|ags, thi|
|00002130| 73 20 69 73 20 74 68 65 | 20 50 69 78 20 6f 66 20 |s is the| Pix of |
|00002140| 74 68 65 20 6c 65 61 73 | 74 20 65 6c 65 6d 65 6e |the leas|t elemen|
|00002150| 74 2e 0a 0a 23 49 6e 64 | 65 6e 74 0a 7b 66 43 6f |t...#Ind|ent.{fCo|
|00002160| 64 65 7d 61 2e 6e 65 78 | 74 28 69 6e 64 29 7b 66 |de}a.nex|t(ind){f|
|00002170| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 61 64 76 |}.#Inden|t +4.adv|
|00002180| 61 6e 63 65 73 20 69 6e | 64 20 74 6f 20 74 68 65 |ances in|d to the|
|00002190| 20 50 69 78 20 6f 66 20 | 6e 65 78 74 20 65 6c 65 | Pix of |next ele|
|000021a0| 6d 65 6e 74 2c 20 6f 72 | 20 30 20 69 66 20 74 68 |ment, or| 0 if th|
|000021b0| 65 72 65 20 61 72 65 20 | 6e 6f 20 6d 6f 72 65 2e |ere are |no more.|
|000021c0| 0a 0a 23 49 6e 64 65 6e | 74 0a 7b 66 43 6f 64 65 |..#Inden|t.{fCode|
|000021d0| 7d 69 6e 64 20 3d 20 61 | 2e 73 65 65 6b 28 78 2e |}ind = a|.seek(x.|
|000021e0| 20 50 69 78 20 66 72 6f | 6d 20 3d 20 30 29 7b 66 | Pix fro|m = 0){f|
|000021f0| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 53 65 74 |}.#Inden|t +4.Set|
|00002200| 73 20 69 6e 64 20 74 6f | 20 74 68 65 20 50 69 78 |s ind to| the Pix|
|00002210| 20 6f 66 20 74 68 65 20 | 6e 65 78 74 20 6f 63 63 | of the |next occ|
|00002220| 75 72 72 65 6e 63 65 20 | 78 2c 20 6f 72 20 30 20 |urrence |x, or 0 |
|00002230| 69 66 20 74 68 65 72 65 | 20 61 72 65 20 6e 6f 6e |if there| are non|
|00002240| 65 2e 0a 49 66 20 66 72 | 6f 6d 20 69 73 20 30 2c |e..If fr|om is 0,|
|00002250| 20 74 68 65 20 66 69 72 | 73 74 20 6f 63 63 75 72 | the fir|st occur|
|00002260| 72 65 6e 63 65 20 69 73 | 20 72 65 74 75 72 6e 65 |rence is| returne|
|00002270| 64 2c 20 65 6c 73 65 20 | 74 68 65 20 66 6f 6c 6c |d, else |the foll|
|00002280| 6f 77 69 6e 67 20 66 72 | 6f 6d 2e 0a 0a 0a 23 49 |owing fr|om....#I|
|00002290| 6e 64 65 6e 74 0a 0a 00 | 44 41 54 41 ff 2f 00 00 |ndent...|DATA./..|
|000022a0| 42 69 74 0a 50 72 65 76 | 69 6f 75 73 3a 20 3c 46 |Bit.Prev|ious: <F|
|000022b0| 69 78 3d 3e 46 69 78 3e | 20 2a 20 4e 65 78 74 3a |ix=>Fix>| * Next:|
|000022c0| 20 3c 52 61 6e 64 6f 6d | 3d 3e 52 61 6e 64 6f 6d | <Random|=>Random|
|000022d0| 3e 20 2a 20 55 70 3a 20 | 3c 54 6f 70 3d 3e 21 52 |> * Up: |<Top=>!R|
|000022e0| 6f 6f 74 3e 0a 0a 23 57 | 72 61 70 20 6f 6e 0a 7b |oot>..#W|rap on.{|
|000022f0| 66 48 32 7d 43 6c 61 73 | 73 65 73 20 66 6f 72 20 |fH2}Clas|ses for |
|00002300| 42 69 74 20 6d 61 6e 69 | 70 75 6c 61 74 69 6f 6e |Bit mani|pulation|
|00002310| 7b 66 7d 0a 0a 6c 69 62 | 67 2b 2b 20 70 72 6f 76 |{f}..lib|g++ prov|
|00002320| 69 64 65 73 20 73 65 76 | 65 72 61 6c 20 64 69 66 |ides sev|eral dif|
|00002330| 66 65 72 65 6e 74 20 63 | 6c 61 73 73 65 73 20 73 |ferent c|lasses s|
|00002340| 75 70 70 6f 72 74 69 6e | 67 20 74 68 65 20 75 73 |upportin|g the us|
|00002350| 65 0a 61 6e 64 20 6d 61 | 6e 69 70 75 6c 61 74 69 |e.and ma|nipulati|
|00002360| 6f 6e 20 6f 66 20 63 6f | 6c 6c 65 63 74 69 6f 6e |on of co|llection|
|00002370| 73 20 6f 66 20 62 69 74 | 73 20 69 6e 20 64 69 66 |s of bit|s in dif|
|00002380| 66 65 72 65 6e 74 20 77 | 61 79 73 2e 0a 0a 23 49 |ferent w|ays...#I|
|00002390| 6e 64 65 6e 74 20 2b 34 | 0a 0a 0a 20 8f 20 43 6c |ndent +4|... . Cl|
|000023a0| 61 73 73 20 7b 66 43 6f | 64 65 7d 49 6e 74 65 67 |ass {fCo|de}Integ|
|000023b0| 65 72 7b 66 7d 20 70 72 | 6f 76 69 64 65 73 20 60 |er{f} pr|ovides `|
|000023c0| 60 69 6e 74 65 67 65 72 | 27 27 20 73 65 6d 61 6e |`integer|'' seman|
|000023d0| 74 69 63 73 2e 20 49 74 | 20 73 75 70 70 6f 72 74 |tics. It| support|
|000023e0| 73 0a 6d 61 6e 69 70 75 | 6c 61 74 69 6f 6e 20 6f |s.manipu|lation o|
|000023f0| 66 20 62 69 74 73 20 69 | 6e 20 77 61 79 73 20 74 |f bits i|n ways t|
|00002400| 68 61 74 20 61 72 65 20 | 6f 66 74 65 6e 20 75 73 |hat are |often us|
|00002410| 65 66 75 6c 20 77 68 65 | 6e 20 74 72 65 61 74 69 |eful whe|n treati|
|00002420| 6e 67 20 62 69 74 20 61 | 72 72 61 79 73 0a 61 73 |ng bit a|rrays.as|
|00002430| 20 6e 75 6d 65 72 69 63 | 61 6c 20 28 69 6e 74 65 | numeric|al (inte|
|00002440| 67 65 72 29 20 71 75 61 | 6e 74 69 74 69 65 73 2e |ger) qua|ntities.|
|00002450| 20 20 54 68 69 73 20 63 | 6c 61 73 73 20 69 73 20 | This c|lass is |
|00002460| 64 65 73 63 72 69 62 65 | 64 20 65 6c 73 65 77 68 |describe|d elsewh|
|00002470| 65 72 65 2e 0a 0a 0a 20 | 8f 20 43 6c 61 73 73 20 |ere.... |. Class |
|00002480| 7b 66 43 6f 64 65 7d 42 | 69 74 53 65 74 7b 66 7d |{fCode}B|itSet{f}|
|00002490| 20 70 72 6f 76 69 64 65 | 73 20 60 60 73 65 74 27 | provide|s ``set'|
|000024a0| 27 20 73 65 6d 61 6e 74 | 69 63 73 2e 20 49 74 20 |' semant|ics. It |
|000024b0| 73 75 70 70 6f 72 74 73 | 20 6f 70 65 72 61 74 69 |supports| operati|
|000024c0| 6f 6e 73 0a 75 73 65 66 | 75 6c 20 77 68 65 6e 20 |ons.usef|ul when |
|000024d0| 74 72 65 61 74 69 6e 67 | 20 63 6f 6c 6c 65 63 74 |treating| collect|
|000024e0| 69 6f 6e 73 20 6f 66 20 | 62 69 74 73 20 61 73 20 |ions of |bits as |
|000024f0| 72 65 70 72 65 73 65 6e | 74 69 6e 67 20 70 6f 74 |represen|ting pot|
|00002500| 65 6e 74 69 61 6c 6c 79 | 0a 69 6e 66 69 6e 69 74 |entially|.infinit|
|00002510| 65 20 73 65 74 73 20 6f | 66 20 69 6e 74 65 67 65 |e sets o|f intege|
|00002520| 72 73 2e 0a 0a 0a 20 8f | 20 43 6c 61 73 73 20 7b |rs.... .| Class {|
|00002530| 66 43 6f 64 65 7d 42 69 | 74 53 65 74 33 32 7b 66 |fCode}Bi|tSet32{f|
|00002540| 7d 20 73 75 70 70 6f 72 | 74 73 20 66 69 78 65 64 |} suppor|ts fixed|
|00002550| 2d 6c 65 6e 67 74 68 20 | 42 69 74 53 65 74 73 20 |-length |BitSets |
|00002560| 68 6f 6c 64 69 6e 67 20 | 65 78 61 63 74 6c 79 0a |holding |exactly.|
|00002570| 33 32 20 62 69 74 73 2e | 0a 0a 0a 20 8f 20 43 6c |32 bits.|... . Cl|
|00002580| 61 73 73 20 7b 66 43 6f | 64 65 7d 42 69 74 53 65 |ass {fCo|de}BitSe|
|00002590| 74 32 35 36 7b 66 7d 20 | 73 75 70 70 6f 72 74 73 |t256{f} |supports|
|000025a0| 20 66 69 78 65 64 2d 6c | 65 6e 67 74 68 20 42 69 | fixed-l|ength Bi|
|000025b0| 74 53 65 74 73 20 68 6f | 6c 64 69 6e 67 20 65 78 |tSets ho|lding ex|
|000025c0| 61 63 74 6c 79 0a 32 35 | 36 20 62 69 74 73 2e 0a |actly.25|6 bits..|
|000025d0| 0a 0a 20 8f 20 43 6c 61 | 73 73 20 7b 66 43 6f 64 |.. . Cla|ss {fCod|
|000025e0| 65 7d 42 69 74 53 74 72 | 69 6e 67 7b 66 7d 20 70 |e}BitStr|ing{f} p|
|000025f0| 72 6f 76 69 64 65 73 20 | 60 60 73 74 72 69 6e 67 |rovides |``string|
|00002600| 27 27 20 28 6f 72 20 60 | 60 76 65 63 74 6f 72 27 |'' (or `|`vector'|
|00002610| 27 29 20 73 65 6d 61 6e | 74 69 63 73 2e 20 0a 49 |') seman|tics. .I|
|00002620| 74 20 73 75 70 70 6f 72 | 74 73 20 6f 70 65 72 61 |t suppor|ts opera|
|00002630| 74 69 6f 6e 73 20 75 73 | 65 66 75 6c 20 77 68 65 |tions us|eful whe|
|00002640| 6e 20 74 72 65 61 74 69 | 6e 67 20 63 6f 6c 6c 65 |n treati|ng colle|
|00002650| 63 74 69 6f 6e 73 20 6f | 66 20 62 69 74 73 20 61 |ctions o|f bits a|
|00002660| 73 20 0a 73 74 72 69 6e | 67 73 20 6f 66 20 7a 65 |s .strin|gs of ze|
|00002670| 72 6f 73 20 61 6e 64 20 | 6f 6e 65 73 2e 0a 0a 0a |ros and |ones....|
|00002680| 23 49 6e 64 65 6e 74 0a | 0a 54 68 65 73 65 20 63 |#Indent.|.These c|
|00002690| 6c 61 73 73 65 73 20 61 | 6c 73 6f 20 64 69 66 66 |lasses a|lso diff|
|000026a0| 65 72 20 69 6e 20 74 68 | 65 20 66 6f 6c 6c 6f 77 |er in th|e follow|
|000026b0| 69 6e 67 20 77 61 79 73 | 3a 0a 0a 23 49 6e 64 65 |ing ways|:..#Inde|
|000026c0| 6e 74 20 2b 34 0a 0a 0a | 0a 20 8f 20 42 69 74 53 |nt +4...|. . BitS|
|000026d0| 65 74 73 20 61 72 65 20 | 6c 6f 67 69 63 61 6c 6c |ets are |logicall|
|000026e0| 79 20 69 6e 66 69 6e 69 | 74 65 2e 20 54 68 65 69 |y infini|te. Thei|
|000026f0| 72 20 73 70 61 63 65 20 | 69 73 20 64 79 6e 61 6d |r space |is dynam|
|00002700| 69 63 61 6c 6c 79 20 61 | 6c 74 65 72 65 64 20 74 |ically a|ltered t|
|00002710| 6f 0a 61 64 6a 75 73 74 | 20 74 6f 20 74 68 65 20 |o.adjust| to the |
|00002720| 73 6d 61 6c 6c 65 73 74 | 20 6e 75 6d 62 65 72 20 |smallest| number |
|00002730| 6f 66 20 63 6f 6e 73 65 | 63 75 74 69 76 65 20 62 |of conse|cutive b|
|00002740| 69 74 73 20 61 63 74 75 | 61 6c 6c 79 20 72 65 71 |its actu|ally req|
|00002750| 75 69 72 65 64 20 74 6f | 0a 72 65 70 72 65 73 65 |uired to|.represe|
|00002760| 6e 74 20 74 68 65 20 73 | 65 74 73 2e 20 49 6e 74 |nt the s|ets. Int|
|00002770| 65 67 65 72 73 20 61 6c | 73 6f 20 68 61 76 65 20 |egers al|so have |
|00002780| 74 68 69 73 20 70 72 6f | 70 65 72 74 79 2e 20 42 |this pro|perty. B|
|00002790| 69 74 53 74 72 69 6e 67 | 73 20 61 72 65 0a 6c 6f |itString|s are.lo|
|000027a0| 67 69 63 61 6c 6c 79 20 | 66 69 6e 69 74 65 2c 20 |gically |finite, |
|000027b0| 62 75 74 20 74 68 65 69 | 72 20 73 69 7a 65 73 20 |but thei|r sizes |
|000027c0| 61 72 65 20 69 6e 74 65 | 72 6e 61 6c 6c 79 20 64 |are inte|rnally d|
|000027d0| 79 6e 61 6d 69 63 61 6c | 6c 79 20 6d 61 6e 61 67 |ynamical|ly manag|
|000027e0| 65 64 20 74 6f 0a 6d 61 | 69 6e 74 61 69 6e 20 70 |ed to.ma|intain p|
|000027f0| 72 6f 70 65 72 20 6c 65 | 6e 67 74 68 2e 20 54 68 |roper le|ngth. Th|
|00002800| 69 73 20 6d 65 61 6e 73 | 20 74 68 61 74 2c 20 66 |is means| that, f|
|00002810| 6f 72 20 65 78 61 6d 70 | 6c 65 2c 20 42 69 74 53 |or examp|le, BitS|
|00002820| 74 72 69 6e 67 73 20 61 | 72 65 0a 63 6f 6e 63 61 |trings a|re.conca|
|00002830| 74 65 6e 61 74 61 62 6c | 65 20 77 68 69 6c 65 20 |tenatabl|e while |
|00002840| 42 69 74 53 65 74 73 20 | 61 6e 64 20 49 6e 74 65 |BitSets |and Inte|
|00002850| 67 65 72 73 20 61 72 65 | 20 6e 6f 74 2e 20 0a 0a |gers are| not. ..|
|00002860| 0a 20 8f 20 42 69 74 53 | 65 74 33 32 20 61 6e 64 |. . BitS|et32 and|
|00002870| 20 42 69 74 53 65 74 32 | 35 36 20 68 61 76 65 20 | BitSet2|56 have |
|00002880| 70 72 65 63 69 73 65 6c | 79 20 74 68 65 20 73 61 |precisel|y the sa|
|00002890| 6d 65 20 70 72 6f 70 65 | 72 74 69 65 73 20 61 73 |me prope|rties as|
|000028a0| 20 42 69 74 53 65 74 73 | 2c 0a 65 78 63 65 70 74 | BitSets|,.except|
|000028b0| 20 74 68 61 74 20 74 68 | 65 79 20 75 73 65 20 63 | that th|ey use c|
|000028c0| 6f 6e 73 74 61 6e 74 20 | 66 69 78 65 64 20 6c 65 |onstant |fixed le|
|000028d0| 6e 67 74 68 20 62 69 74 | 20 76 65 63 74 6f 72 73 |ngth bit| vectors|
|000028e0| 2e 0a 0a 0a 20 8f 20 57 | 68 69 6c 65 20 61 6c 6c |.... . W|hile all|
|000028f0| 20 63 6c 61 73 73 65 73 | 20 73 75 70 70 6f 72 74 | classes| support|
|00002900| 20 62 61 73 69 63 20 75 | 6e 61 72 79 20 61 6e 64 | basic u|nary and|
|00002910| 20 62 69 6e 61 72 79 20 | 6f 70 65 72 61 74 69 6f | binary |operatio|
|00002920| 6e 73 20 7b 66 43 6f 64 | 65 7d 7e 2c 20 26 2c 0a |ns {fCod|e}~, &,.|
|00002930| 7c 2c 20 5e 2c 20 2d 7b | 66 7d 2c 20 74 68 65 20 ||, ^, -{|f}, the |
|00002940| 73 65 6d 61 6e 74 69 63 | 73 20 64 69 66 66 65 72 |semantic|s differ|
|00002950| 2e 20 42 69 74 53 65 74 | 73 20 70 65 72 66 6f 72 |. BitSet|s perfor|
|00002960| 6d 20 62 69 74 20 6f 70 | 65 72 61 74 69 6f 6e 73 |m bit op|erations|
|00002970| 20 74 68 61 74 0a 70 72 | 65 63 69 73 65 6c 79 20 | that.pr|ecisely |
|00002980| 6d 69 72 72 6f 72 20 74 | 68 6f 73 65 20 66 6f 72 |mirror t|hose for|
|00002990| 20 69 6e 66 69 6e 69 74 | 65 20 73 65 74 73 2e 20 | infinit|e sets. |
|000029a0| 46 6f 72 20 65 78 61 6d | 70 6c 65 2c 20 63 6f 6d |For exam|ple, com|
|000029b0| 70 6c 65 6d 65 6e 74 69 | 6e 67 20 61 6e 0a 65 6d |plementi|ng an.em|
|000029c0| 70 74 79 20 42 69 74 53 | 65 74 20 72 65 74 75 72 |pty BitS|et retur|
|000029d0| 6e 73 20 6f 6e 65 20 72 | 65 70 72 65 73 65 6e 74 |ns one r|epresent|
|000029e0| 69 6e 67 20 61 6e 20 69 | 6e 66 69 6e 69 74 65 20 |ing an i|nfinite |
|000029f0| 6e 75 6d 62 65 72 20 6f | 66 20 73 65 74 20 62 69 |number o|f set bi|
|00002a00| 74 73 2e 0a 4f 70 65 72 | 61 74 69 6f 6e 73 20 6f |ts..Oper|ations o|
|00002a10| 6e 20 42 69 74 53 74 72 | 69 6e 67 73 20 61 6e 64 |n BitStr|ings and|
|00002a20| 20 49 6e 74 65 67 65 72 | 73 20 6f 70 65 72 61 74 | Integer|s operat|
|00002a30| 65 20 6f 6e 6c 79 20 6f | 6e 20 74 68 6f 73 65 20 |e only o|n those |
|00002a40| 62 69 74 73 0a 61 63 74 | 75 61 6c 6c 79 20 70 72 |bits.act|ually pr|
|00002a50| 65 73 65 6e 74 20 69 6e | 20 74 68 65 20 72 65 70 |esent in| the rep|
|00002a60| 72 65 73 65 6e 74 61 74 | 69 6f 6e 2e 20 20 46 6f |resentat|ion. Fo|
|00002a70| 72 20 42 69 74 53 74 72 | 69 6e 67 73 20 61 6e 64 |r BitStr|ings and|
|00002a80| 20 49 6e 74 65 67 65 72 | 73 2c 0a 74 68 65 20 74 | Integer|s,.the t|
|00002a90| 68 65 20 7b 66 43 6f 64 | 65 7d 26 7b 66 7d 20 6f |he {fCod|e}&{f} o|
|00002aa0| 70 65 72 61 74 69 6f 6e | 20 72 65 74 75 72 6e 73 |peration| returns|
|00002ab0| 20 61 20 42 69 74 53 74 | 72 69 6e 67 20 77 69 74 | a BitSt|ring wit|
|00002ac0| 68 20 61 20 6c 65 6e 67 | 74 68 20 65 71 75 61 6c |h a leng|th equal|
|00002ad0| 20 74 6f 0a 74 68 65 20 | 6d 69 6e 69 6d 75 6d 20 | to.the |minimum |
|00002ae0| 6c 65 6e 67 74 68 20 6f | 66 20 74 68 65 20 6f 70 |length o|f the op|
|00002af0| 65 72 61 6e 64 73 2c 20 | 61 6e 64 20 7b 66 43 6f |erands, |and {fCo|
|00002b00| 64 65 7d 7c 2c 20 5e 7b | 66 7d 20 72 65 74 75 72 |de}|, ^{|f} retur|
|00002b10| 6e 20 6f 6e 65 20 77 69 | 74 68 0a 6c 65 6e 67 74 |n one wi|th.lengt|
|00002b20| 68 20 6f 66 20 74 68 65 | 20 6d 61 78 69 6d 75 6d |h of the| maximum|
|00002b30| 2e 0a 0a 0a 20 8f 20 4f | 6e 6c 79 20 42 69 74 53 |.... . O|nly BitS|
|00002b40| 74 72 69 6e 67 73 20 73 | 75 70 70 6f 72 74 20 73 |trings s|upport s|
|00002b50| 75 62 73 74 72 69 6e 67 | 20 65 78 74 72 61 63 74 |ubstring| extract|
|00002b60| 69 6f 6e 20 61 6e 64 20 | 62 69 74 20 70 61 74 74 |ion and |bit patt|
|00002b70| 65 72 6e 20 6d 61 74 63 | 68 69 6e 67 2e 0a 0a 0a |ern matc|hing....|
|00002b80| 23 49 6e 64 65 6e 74 0a | 0a 7b 66 48 33 7d 42 69 |#Indent.|.{fH3}Bi|
|00002b90| 74 53 65 74 7b 66 7d 0a | 0a 42 69 74 53 65 74 73 |tSet{f}.|.BitSets|
|00002ba0| 20 61 72 65 20 6f 62 6a | 65 63 74 73 20 74 68 61 | are obj|ects tha|
|00002bb0| 74 20 63 6f 6e 74 61 69 | 6e 20 6c 6f 67 69 63 61 |t contai|n logica|
|00002bc0| 6c 6c 79 20 69 6e 66 69 | 6e 69 74 65 20 73 65 74 |lly infi|nite set|
|00002bd0| 73 20 6f 66 20 6e 6f 6e | 6e 65 67 61 74 69 76 65 |s of non|negative|
|00002be0| 0a 69 6e 74 65 67 65 72 | 73 2e 20 20 52 65 70 72 |.integer|s. Repr|
|00002bf0| 65 73 65 6e 74 61 74 69 | 6f 6e 61 6c 20 64 65 74 |esentati|onal det|
|00002c00| 61 69 6c 73 20 61 72 65 | 20 64 69 73 63 75 73 73 |ails are| discuss|
|00002c10| 65 64 20 69 6e 20 74 68 | 65 20 52 65 70 72 65 73 |ed in th|e Repres|
|00002c20| 65 6e 74 61 74 69 6f 6e | 0a 63 68 61 70 74 65 72 |entation|.chapter|
|00002c30| 2e 20 42 65 63 61 75 73 | 65 20 74 68 65 79 20 61 |. Becaus|e they a|
|00002c40| 72 65 20 6c 6f 67 69 63 | 61 6c 6c 79 20 69 6e 66 |re logic|ally inf|
|00002c50| 69 6e 69 74 65 2c 20 61 | 6c 6c 20 42 69 74 53 65 |inite, a|ll BitSe|
|00002c60| 74 73 20 70 6f 73 73 65 | 73 73 20 61 0a 74 72 61 |ts posse|ss a.tra|
|00002c70| 69 6c 69 6e 67 2c 20 69 | 6e 66 69 6e 69 74 65 6c |iling, i|nfinitel|
|00002c80| 79 20 72 65 70 6c 69 63 | 61 74 65 64 20 30 20 6f |y replic|ated 0 o|
|00002c90| 72 20 31 20 62 69 74 2c | 20 63 61 6c 6c 65 64 20 |r 1 bit,| called |
|00002ca0| 74 68 65 20 60 60 76 69 | 72 74 75 61 6c 20 62 69 |the ``vi|rtual bi|
|00002cb0| 74 27 27 2c 20 61 6e 64 | 0a 69 6e 64 69 63 61 74 |t'', and|.indicat|
|00002cc0| 65 64 20 76 69 61 20 30 | 5c 2a 20 6f 72 20 31 5c |ed via 0|\* or 1\|
|00002cd0| 2a 2e 0a 0a 42 69 74 53 | 65 74 33 32 20 61 6e 64 |*...BitS|et32 and|
|00002ce0| 20 42 69 74 53 65 74 32 | 35 36 20 68 61 76 65 20 | BitSet2|56 have |
|00002cf0| 74 68 65 79 20 73 61 6d | 65 20 70 72 6f 70 65 72 |they sam|e proper|
|00002d00| 74 69 65 73 2c 20 65 78 | 63 65 70 74 20 74 68 65 |ties, ex|cept the|
|00002d10| 79 20 61 72 65 0a 6f 66 | 20 66 69 78 65 64 20 6c |y are.of| fixed l|
|00002d20| 65 6e 67 74 68 2c 20 61 | 6e 64 20 74 68 75 73 20 |ength, a|nd thus |
|00002d30| 68 61 76 65 20 6e 6f 20 | 76 69 72 74 75 61 6c 20 |have no |virtual |
|00002d40| 62 69 74 2e 20 0a 0a 42 | 69 74 53 65 74 73 20 6d |bit. ..B|itSets m|
|00002d50| 61 79 20 62 65 20 63 6f | 6e 73 74 72 75 63 74 65 |ay be co|nstructe|
|00002d60| 64 20 61 73 20 66 6f 6c | 6c 6f 77 73 3a 0a 0a 23 |d as fol|lows:..#|
|00002d70| 49 6e 64 65 6e 74 20 2b | 34 0a 0a 23 49 6e 64 65 |Indent +|4..#Inde|
|00002d80| 6e 74 0a 7b 66 43 6f 64 | 65 7d 42 69 74 53 65 74 |nt.{fCod|e}BitSet|
|00002d90| 20 61 3b 7b 66 7d 0a 23 | 49 6e 64 65 6e 74 20 2b | a;{f}.#|Indent +|
|00002da0| 34 0a 64 65 63 6c 61 72 | 65 73 20 61 6e 20 65 6d |4.declar|es an em|
|00002db0| 70 74 79 20 42 69 74 53 | 65 74 2e 0a 0a 23 49 6e |pty BitS|et...#In|
|00002dc0| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 42 69 74 53 |dent.{fC|ode}BitS|
|00002dd0| 65 74 20 61 20 3d 20 61 | 74 6f 42 69 74 53 65 74 |et a = a|toBitSet|
|00002de0| 28 22 30 30 31 30 30 30 | 22 29 3b 7b 66 7d 0a 23 |("001000|");{f}.#|
|00002df0| 49 6e 64 65 6e 74 20 2b | 34 0a 73 65 74 73 20 61 |Indent +|4.sets a|
|00002e00| 20 74 6f 20 74 68 65 20 | 42 69 74 53 65 74 20 30 | to the |BitSet 0|
|00002e10| 30 31 30 5c 2a 2c 20 72 | 65 61 64 69 6e 67 20 6c |010\*, r|eading l|
|00002e20| 65 66 74 2d 74 6f 2d 72 | 69 67 68 74 2e 20 54 68 |eft-to-r|ight. Th|
|00002e30| 65 20 60 60 30 5c 2a 27 | 27 0a 69 6e 64 69 63 61 |e ``0\*'|'.indica|
|00002e40| 74 65 73 20 74 68 61 74 | 20 74 68 65 20 73 65 74 |tes that| the set|
|00002e50| 20 65 6e 64 73 20 77 69 | 74 68 20 61 6e 20 69 6e | ends wi|th an in|
|00002e60| 66 69 6e 69 74 65 20 6e | 75 6d 62 65 72 20 6f 66 |finite n|umber of|
|00002e70| 20 7a 65 72 6f 0a 28 63 | 6c 65 61 72 29 20 62 69 | zero.(c|lear) bi|
|00002e80| 74 73 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 |ts...#In|dent.{fC|
|00002e90| 6f 64 65 7d 42 69 74 53 | 65 74 20 61 20 3d 20 61 |ode}BitS|et a = a|
|00002ea0| 74 6f 42 69 74 53 65 74 | 28 22 30 30 31 30 31 5c |toBitSet|("00101\|
|00002eb0| 2a 22 29 3b 7b 66 7d 0a | 23 49 6e 64 65 6e 74 20 |*");{f}.|#Indent |
|00002ec0| 2b 34 0a 73 65 74 73 20 | 61 20 74 6f 20 74 68 65 |+4.sets |a to the|
|00002ed0| 20 42 69 74 53 65 74 20 | 30 30 31 30 31 5c 2a 2c | BitSet |00101\*,|
|00002ee0| 20 77 68 65 72 65 20 60 | 60 31 5c 2a 27 27 20 6d | where `|`1\*'' m|
|00002ef0| 65 61 6e 73 20 74 68 61 | 74 20 74 68 65 20 73 65 |eans tha|t the se|
|00002f00| 74 20 65 6e 64 73 0a 77 | 69 74 68 20 61 6e 20 69 |t ends.w|ith an i|
|00002f10| 6e 66 69 6e 69 74 65 20 | 6e 75 6d 62 65 72 20 6f |nfinite |number o|
|00002f20| 66 20 6f 6e 65 20 28 73 | 65 74 29 20 62 69 74 73 |f one (s|et) bits|
|00002f30| 2e 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |...#Inde|nt.{fCod|
|00002f40| 65 7d 42 69 74 53 65 74 | 20 61 20 3d 20 6c 6f 6e |e}BitSet| a = lon|
|00002f50| 67 74 6f 42 69 74 53 65 | 74 28 28 6c 6f 6e 67 29 |gtoBitSe|t((long)|
|00002f60| 32 33 29 3b 7b 66 7d 0a | 23 49 6e 64 65 6e 74 20 |23);{f}.|#Indent |
|00002f70| 2b 34 0a 73 65 74 73 20 | 61 20 74 6f 20 74 68 65 |+4.sets |a to the|
|00002f80| 20 42 69 74 53 65 74 20 | 31 31 31 30 31 30 5c 2a | BitSet |111010\*|
|00002f90| 2c 20 74 68 65 20 62 69 | 6e 61 72 79 20 72 65 70 |, the bi|nary rep|
|00002fa0| 72 65 73 65 6e 74 61 74 | 69 6f 6e 20 6f 66 20 64 |resentat|ion of d|
|00002fb0| 65 63 69 6d 61 6c 20 32 | 33 2e 0a 0a 23 49 6e 64 |ecimal 2|3...#Ind|
|00002fc0| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 42 69 74 53 65 |ent.{fCo|de}BitSe|
|00002fd0| 74 20 61 20 3d 20 75 74 | 6f 42 69 74 53 65 74 28 |t a = ut|oBitSet(|
|00002fe0| 28 75 6e 73 69 67 6e 65 | 64 29 32 33 29 3b 7b 66 |(unsigne|d)23);{f|
|00002ff0| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 73 65 74 |}.#Inden|t +4.set|
|00003000| 73 20 61 20 74 6f 20 74 | 68 65 20 42 69 74 53 65 |s a to t|he BitSe|
|00003010| 74 20 31 31 31 30 31 30 | 5c 2a 2c 20 74 68 65 20 |t 111010|\*, the |
|00003020| 62 69 6e 61 72 79 20 72 | 65 70 72 65 73 65 6e 74 |binary r|epresent|
|00003030| 61 74 69 6f 6e 20 6f 66 | 20 64 65 63 69 6d 61 6c |ation of| decimal|
|00003040| 20 32 33 2e 0a 0a 0a 23 | 49 6e 64 65 6e 74 0a 0a | 23....#|Indent..|
|00003050| 54 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 66 75 |The foll|owing fu|
|00003060| 6e 63 74 69 6f 6e 73 20 | 61 6e 64 20 6f 70 65 72 |nctions |and oper|
|00003070| 61 74 6f 72 73 20 61 72 | 65 20 70 72 6f 76 69 64 |ators ar|e provid|
|00003080| 65 64 20 28 41 73 73 75 | 6d 65 20 74 68 65 0a 64 |ed (Assu|me the.d|
|00003090| 65 63 6c 61 72 61 74 69 | 6f 6e 20 6f 66 20 42 69 |eclarati|on of Bi|
|000030a0| 74 53 65 74 73 20 61 20 | 3d 20 30 30 31 31 30 31 |tSets a |= 001101|
|000030b0| 30 5c 2a 2c 20 62 20 3d | 20 31 30 31 31 30 31 5c |0\*, b =| 101101\|
|000030c0| 2a 2c 20 74 68 72 6f 75 | 67 68 6f 75 74 2c 20 61 |*, throu|ghout, a|
|000030d0| 73 0a 65 78 61 6d 70 6c | 65 73 29 2e 0a 0a 23 49 |s.exampl|es)...#I|
|000030e0| 6e 64 65 6e 74 20 2b 34 | 0a 0a 23 49 6e 64 65 6e |ndent +4|..#Inden|
|000030f0| 74 0a 7b 66 43 6f 64 65 | 7d 7e 61 7b 66 7d 0a 23 |t.{fCode|}~a{f}.#|
|00003100| 49 6e 64 65 6e 74 20 2b | 34 0a 72 65 74 75 72 6e |Indent +|4.return|
|00003110| 73 20 74 68 65 20 63 6f | 6d 70 6c 65 6d 65 6e 74 |s the co|mplement|
|00003120| 20 6f 66 20 61 2c 20 6f | 72 20 31 31 30 30 31 30 | of a, o|r 110010|
|00003130| 31 5c 2a 20 69 6e 20 74 | 68 69 73 20 63 61 73 65 |1\* in t|his case|
|00003140| 2e 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |...#Inde|nt.{fCod|
|00003150| 65 7d 61 2e 63 6f 6d 70 | 6c 65 6d 65 6e 74 28 29 |e}a.comp|lement()|
|00003160| 7b 66 7d 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 73 |{f}.#Ind|ent +4.s|
|00003170| 65 74 73 20 61 20 74 6f | 20 7e 61 2e 0a 0a 23 49 |ets a to| ~a...#I|
|00003180| 6e 64 65 6e 74 0a 7b 66 | 43 6f 64 65 7d 61 20 26 |ndent.{f|Code}a &|
|00003190| 20 62 3b 20 61 20 26 3d | 20 62 3b 7b 66 7d 0a 23 | b; a &=| b;{f}.#|
|000031a0| 49 6e 64 65 6e 74 20 2b | 34 0a 72 65 74 75 72 6e |Indent +|4.return|
|000031b0| 73 20 61 20 69 6e 74 65 | 72 73 65 63 74 65 64 20 |s a inte|rsected |
|000031c0| 77 69 74 68 20 62 2c 20 | 6f 72 20 30 30 31 31 30 |with b, |or 00110|
|000031d0| 31 30 5c 2a 2e 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b |10\*...#|Indent.{|
|000031e0| 66 43 6f 64 65 7d 61 20 | 7c 20 62 3b 20 61 20 7c |fCode}a || b; a ||
|000031f0| 3d 20 62 3b 7b 66 7d 0a | 23 49 6e 64 65 6e 74 20 |= b;{f}.|#Indent |
|00003200| 2b 34 0a 72 65 74 75 72 | 6e 73 20 61 20 75 6e 69 |+4.retur|ns a uni|
|00003210| 6f 6e 65 64 20 77 69 74 | 68 20 62 2c 20 6f 72 20 |oned wit|h b, or |
|00003220| 31 30 31 31 31 31 31 5c | 2a 2e 0a 0a 23 49 6e 64 |1011111\|*...#Ind|
|00003230| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 61 20 2d 20 62 |ent.{fCo|de}a - b|
|00003240| 3b 20 61 20 2d 3d 20 62 | 3b 7b 66 7d 0a 23 49 6e |; a -= b|;{f}.#In|
|00003250| 64 65 6e 74 20 2b 34 0a | 72 65 74 75 72 6e 73 20 |dent +4.|returns |
|00003260| 74 68 65 20 73 65 74 20 | 64 69 66 66 65 72 65 6e |the set |differen|
|00003270| 63 65 20 6f 66 20 61 20 | 61 6e 64 20 62 2c 20 6f |ce of a |and b, o|
|00003280| 72 20 30 30 30 30 31 30 | 5c 2a 2e 0a 0a 23 49 6e |r 000010|\*...#In|
|00003290| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 61 20 5e 20 |dent.{fC|ode}a ^ |
|000032a0| 62 3b 20 61 20 5e 3d 20 | 62 3b 7b 66 7d 0a 23 49 |b; a ^= |b;{f}.#I|
|000032b0| 6e 64 65 6e 74 20 2b 34 | 0a 72 65 74 75 72 6e 73 |ndent +4|.returns|
|000032c0| 20 74 68 65 20 73 79 6d | 6d 65 74 72 69 63 20 64 | the sym|metric d|
|000032d0| 69 66 66 65 72 65 6e 63 | 65 20 6f 66 20 61 20 61 |ifferenc|e of a a|
|000032e0| 6e 64 20 62 2c 20 6f 72 | 20 31 30 30 30 31 30 31 |nd b, or| 1000101|
|000032f0| 5c 2a 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 |\*...#In|dent.{fC|
|00003300| 6f 64 65 7d 61 2e 65 6d | 70 74 79 28 29 7b 66 7d |ode}a.em|pty(){f}|
|00003310| 0a 23 49 6e 64 65 6e 74 | 20 2b 34 0a 72 65 74 75 |.#Indent| +4.retu|
|00003320| 72 6e 73 20 74 72 75 65 | 20 69 66 20 61 20 69 73 |rns true| if a is|
|00003330| 20 61 6e 20 65 6d 70 74 | 79 20 73 65 74 2e 0a 0a | an empt|y set...|
|00003340| 23 49 6e 64 65 6e 74 0a | 7b 66 43 6f 64 65 7d 61 |#Indent.|{fCode}a|
|00003350| 20 3d 3d 20 62 3b 7b 66 | 7d 0a 23 49 6e 64 65 6e | == b;{f|}.#Inden|
|00003360| 74 20 2b 34 0a 72 65 74 | 75 72 6e 73 20 74 72 75 |t +4.ret|urns tru|
|00003370| 65 20 69 66 20 61 20 61 | 6e 64 20 62 20 63 6f 6e |e if a a|nd b con|
|00003380| 74 61 69 6e 20 74 68 65 | 20 73 61 6d 65 20 73 65 |tain the| same se|
|00003390| 74 2e 0a 0a 23 49 6e 64 | 65 6e 74 0a 7b 66 43 6f |t...#Ind|ent.{fCo|
|000033a0| 64 65 7d 61 20 5c 3c 3d | 20 62 3b 7b 66 7d 0a 23 |de}a \<=| b;{f}.#|
|000033b0| 49 6e 64 65 6e 74 20 2b | 34 0a 72 65 74 75 72 6e |Indent +|4.return|
|000033c0| 73 20 74 72 75 65 20 69 | 66 20 61 20 69 73 20 61 |s true i|f a is a|
|000033d0| 20 73 75 62 73 65 74 20 | 6f 66 20 62 2e 0a 0a 23 | subset |of b...#|
|000033e0| 49 6e 64 65 6e 74 0a 7b | 66 43 6f 64 65 7d 61 20 |Indent.{|fCode}a |
|000033f0| 5c 3c 20 62 3b 7b 66 7d | 0a 23 49 6e 64 65 6e 74 |\< b;{f}|.#Indent|
|00003400| 20 2b 34 0a 72 65 74 75 | 72 6e 73 20 74 72 75 65 | +4.retu|rns true|
|00003410| 20 69 66 20 61 20 69 73 | 20 61 20 70 72 6f 70 65 | if a is| a prope|
|00003420| 72 20 73 75 62 73 65 74 | 20 6f 66 20 62 3b 0a 0a |r subset| of b;..|
|00003430| 23 49 6e 64 65 6e 74 0a | 7b 66 43 6f 64 65 7d 61 |#Indent.|{fCode}a|
|00003440| 20 21 3d 20 62 3b 20 61 | 20 5c 3e 3d 20 62 3b 20 | != b; a| \>= b; |
|00003450| 61 20 5c 3e 20 62 3b 7b | 66 7d 0a 23 49 6e 64 65 |a \> b;{|f}.#Inde|
|00003460| 6e 74 20 2b 34 0a 61 72 | 65 20 74 68 65 20 63 6f |nt +4.ar|e the co|
|00003470| 6e 76 65 72 73 65 73 20 | 6f 66 20 74 68 65 20 61 |nverses |of the a|
|00003480| 62 6f 76 65 2e 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b |bove...#|Indent.{|
|00003490| 66 43 6f 64 65 7d 61 2e | 73 65 74 28 37 29 7b 66 |fCode}a.|set(7){f|
|000034a0| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 73 65 74 |}.#Inden|t +4.set|
|000034b0| 73 20 74 68 65 20 37 74 | 68 20 28 63 6f 75 6e 74 |s the 7t|h (count|
|000034c0| 69 6e 67 20 66 72 6f 6d | 20 30 29 20 62 69 74 20 |ing from| 0) bit |
|000034d0| 6f 66 20 61 2c 20 73 65 | 74 74 69 6e 67 20 61 20 |of a, se|tting a |
|000034e0| 74 6f 20 30 30 31 31 31 | 31 30 31 30 5c 2a 0a 0a |to 00111|1010\*..|
|000034f0| 23 49 6e 64 65 6e 74 0a | 7b 66 43 6f 64 65 7d 61 |#Indent.|{fCode}a|
|00003500| 2e 63 6c 65 61 72 28 32 | 29 7b 66 7d 0a 23 49 6e |.clear(2|){f}.#In|
|00003510| 64 65 6e 74 20 2b 34 0a | 63 6c 65 61 72 73 20 74 |dent +4.|clears t|
|00003520| 68 65 20 32 6e 64 20 62 | 69 74 20 62 69 74 20 6f |he 2nd b|it bit o|
|00003530| 66 20 61 2c 20 73 65 74 | 74 69 6e 67 20 61 20 74 |f a, set|ting a t|
|00003540| 6f 20 30 30 30 31 31 31 | 31 30 5c 2a 0a 0a 23 49 |o 000111|10\*..#I|
|00003550| 6e 64 65 6e 74 0a 7b 66 | 43 6f 64 65 7d 61 2e 63 |ndent.{f|Code}a.c|
|00003560| 6c 65 61 72 28 29 7b 66 | 7d 0a 23 49 6e 64 65 6e |lear(){f|}.#Inden|
|00003570| 74 20 2b 34 0a 63 6c 65 | 61 72 73 20 61 6c 6c 20 |t +4.cle|ars all |
|00003580| 62 69 74 73 20 6f 66 20 | 61 3b 0a 0a 23 49 6e 64 |bits of |a;..#Ind|
|00003590| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 61 2e 73 65 74 |ent.{fCo|de}a.set|
|000035a0| 28 29 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |(){f}.#I|ndent +4|
|000035b0| 0a 73 65 74 73 20 61 6c | 6c 20 62 69 74 73 20 6f |.sets al|l bits o|
|000035c0| 66 20 61 3b 0a 0a 23 49 | 6e 64 65 6e 74 0a 7b 66 |f a;..#I|ndent.{f|
|000035d0| 43 6f 64 65 7d 61 2e 69 | 6e 76 65 72 74 28 30 29 |Code}a.i|nvert(0)|
|000035e0| 7b 66 7d 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 63 |{f}.#Ind|ent +4.c|
|000035f0| 6f 6d 70 6c 65 6d 65 6e | 74 73 20 74 68 65 20 30 |omplemen|ts the 0|
|00003600| 74 68 20 62 69 74 20 6f | 66 20 61 2c 20 73 65 74 |th bit o|f a, set|
|00003610| 74 69 6e 67 20 61 20 74 | 6f 20 31 30 30 31 31 31 |ting a t|o 100111|
|00003620| 31 30 5c 2a 0a 0a 23 49 | 6e 64 65 6e 74 0a 7b 66 |10\*..#I|ndent.{f|
|00003630| 43 6f 64 65 7d 61 2e 73 | 65 74 28 30 2c 31 29 7b |Code}a.s|et(0,1){|
|00003640| 66 7d 0a 23 49 6e 64 65 | 6e 74 20 2b 34 0a 73 65 |f}.#Inde|nt +4.se|
|00003650| 74 73 20 74 68 65 20 30 | 74 68 20 74 68 72 6f 75 |ts the 0|th throu|
|00003660| 67 68 20 31 73 74 20 62 | 69 74 73 20 6f 66 20 61 |gh 1st b|its of a|
|00003670| 2c 20 73 65 74 74 69 6e | 67 20 61 20 74 6f 20 31 |, settin|g a to 1|
|00003680| 31 30 31 31 31 31 31 30 | 5c 2a 0a 54 68 65 20 74 |10111110|\*.The t|
|00003690| 77 6f 2d 61 72 67 75 6d | 65 6e 74 20 76 65 72 73 |wo-argum|ent vers|
|000036a0| 69 6f 6e 73 20 6f 66 20 | 63 6c 65 61 72 20 61 6e |ions of |clear an|
|000036b0| 64 20 69 6e 76 65 72 74 | 20 61 72 65 20 73 69 6d |d invert| are sim|
|000036c0| 69 6c 61 72 2e 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b |ilar...#|Indent.{|
|000036d0| 66 43 6f 64 65 7d 61 2e | 74 65 73 74 28 33 29 7b |fCode}a.|test(3){|
|000036e0| 66 7d 0a 23 49 6e 64 65 | 6e 74 20 2b 34 0a 72 65 |f}.#Inde|nt +4.re|
|000036f0| 74 75 72 6e 73 20 74 72 | 75 65 20 69 66 20 74 68 |turns tr|ue if th|
|00003700| 65 20 33 72 64 20 62 69 | 74 20 6f 66 20 61 20 69 |e 3rd bi|t of a i|
|00003710| 73 20 73 65 74 2e 0a 0a | 23 49 6e 64 65 6e 74 0a |s set...|#Indent.|
|00003720| 7b 66 43 6f 64 65 7d 61 | 2e 74 65 73 74 28 33 2c |{fCode}a|.test(3,|
|00003730| 20 35 29 7b 66 7d 0a 23 | 49 6e 64 65 6e 74 20 2b | 5){f}.#|Indent +|
|00003740| 34 0a 72 65 74 75 72 6e | 73 20 74 72 75 65 20 69 |4.return|s true i|
|00003750| 66 20 61 6e 79 20 6f 66 | 20 62 69 74 73 20 33 20 |f any of| bits 3 |
|00003760| 74 68 72 6f 75 67 68 20 | 35 20 61 72 65 20 73 65 |through |5 are se|
|00003770| 74 2e 0a 0a 23 49 6e 64 | 65 6e 74 0a 7b 66 43 6f |t...#Ind|ent.{fCo|
|00003780| 64 65 7d 69 6e 74 20 69 | 20 3d 20 61 5b 33 5d 3b |de}int i| = a[3];|
|00003790| 20 61 5b 33 5d 20 3d 20 | 30 3b 7b 66 7d 0a 23 49 | a[3] = |0;{f}.#I|
|000037a0| 6e 64 65 6e 74 20 2b 34 | 0a 54 68 65 20 73 75 62 |ndent +4|.The sub|
|000037b0| 73 63 72 69 70 74 20 6f | 70 65 72 61 74 6f 72 20 |script o|perator |
|000037c0| 61 6c 6c 6f 77 73 20 62 | 69 74 73 20 74 6f 20 62 |allows b|its to b|
|000037d0| 65 20 69 6e 73 70 65 63 | 74 65 64 20 61 6e 64 20 |e inspec|ted and |
|000037e0| 63 68 61 6e 67 65 64 0a | 76 69 61 20 73 74 61 6e |changed.|via stan|
|000037f0| 64 61 72 64 20 73 75 62 | 73 63 72 69 70 74 20 73 |dard sub|script s|
|00003800| 65 6d 61 6e 74 69 63 73 | 2c 20 75 73 69 6e 67 20 |emantics|, using |
|00003810| 61 20 66 72 69 65 6e 64 | 20 63 6c 61 73 73 20 42 |a friend| class B|
|00003820| 69 74 53 65 74 42 69 74 | 2e 0a 54 68 65 20 75 73 |itSetBit|..The us|
|00003830| 65 20 6f 66 20 74 68 65 | 20 73 75 62 73 63 72 69 |e of the| subscri|
|00003840| 70 74 20 6f 70 65 72 61 | 74 6f 72 20 61 5b 69 5d |pt opera|tor a[i]|
|00003850| 20 72 61 74 68 65 72 20 | 74 68 61 6e 20 61 2e 74 | rather |than a.t|
|00003860| 65 73 74 28 69 29 20 0a | 72 65 71 75 69 72 65 73 |est(i) .|requires|
|00003870| 20 73 6f 6d 65 77 68 61 | 74 20 67 72 65 61 74 65 | somewha|t greate|
|00003880| 72 20 6f 76 65 72 68 65 | 61 64 2e 0a 0a 23 49 6e |r overhe|ad...#In|
|00003890| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 61 2e 66 69 |dent.{fC|ode}a.fi|
|000038a0| 72 73 74 28 31 29 20 6f | 72 20 61 2e 66 69 72 73 |rst(1) o|r a.firs|
|000038b0| 74 28 29 7b 66 7d 0a 23 | 49 6e 64 65 6e 74 20 2b |t(){f}.#|Indent +|
|000038c0| 34 0a 72 65 74 75 72 6e | 73 20 74 68 65 20 69 6e |4.return|s the in|
|000038d0| 64 65 78 20 6f 66 20 74 | 68 65 20 66 69 72 73 74 |dex of t|he first|
|000038e0| 20 73 65 74 20 62 69 74 | 20 6f 66 20 61 20 28 32 | set bit| of a (2|
|000038f0| 20 69 6e 20 74 68 69 73 | 20 63 61 73 65 29 2c 20 | in this| case), |
|00003900| 0a 6f 72 20 2d 31 20 69 | 66 20 6e 6f 20 62 69 74 |.or -1 i|f no bit|
|00003910| 73 20 61 72 65 20 73 65 | 74 2e 0a 0a 23 49 6e 64 |s are se|t...#Ind|
|00003920| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 61 2e 66 69 72 |ent.{fCo|de}a.fir|
|00003930| 73 74 28 30 29 7b 66 7d | 0a 23 49 6e 64 65 6e 74 |st(0){f}|.#Indent|
|00003940| 20 2b 34 0a 72 65 74 75 | 72 6e 73 20 74 68 65 20 | +4.retu|rns the |
|00003950| 69 6e 64 65 78 20 6f 66 | 20 74 68 65 20 66 69 72 |index of| the fir|
|00003960| 73 74 20 63 6c 65 61 72 | 20 62 69 74 20 6f 66 20 |st clear| bit of |
|00003970| 61 20 28 30 20 69 6e 20 | 74 68 69 73 20 63 61 73 |a (0 in |this cas|
|00003980| 65 29 2c 20 0a 6f 72 20 | 2d 31 20 69 66 20 6e 6f |e), .or |-1 if no|
|00003990| 20 62 69 74 73 20 61 72 | 65 20 63 6c 65 61 72 2e | bits ar|e clear.|
|000039a0| 0a 0a 23 49 6e 64 65 6e | 74 0a 7b 66 43 6f 64 65 |..#Inden|t.{fCode|
|000039b0| 7d 61 2e 6e 65 78 74 28 | 32 2c 20 31 29 20 6f 72 |}a.next(|2, 1) or|
|000039c0| 20 61 2e 6e 65 78 74 28 | 32 29 7b 66 7d 0a 23 49 | a.next(|2){f}.#I|
|000039d0| 6e 64 65 6e 74 20 2b 34 | 0a 72 65 74 75 72 6e 73 |ndent +4|.returns|
|000039e0| 20 74 68 65 20 69 6e 64 | 65 78 20 6f 66 20 74 68 | the ind|ex of th|
|000039f0| 65 20 6e 65 78 74 20 62 | 69 74 20 61 66 74 65 72 |e next b|it after|
|00003a00| 20 70 6f 73 69 74 69 6f | 6e 20 32 20 74 68 61 74 | positio|n 2 that|
|00003a10| 20 69 73 20 73 65 74 20 | 28 33 0a 69 6e 20 74 68 | is set |(3.in th|
|00003a20| 69 73 20 63 61 73 65 29 | 20 6f 72 20 2d 31 2e 20 |is case)| or -1. |
|00003a30| 7b 66 43 6f 64 65 7d 66 | 69 72 73 74 7b 66 7d 20 |{fCode}f|irst{f} |
|00003a40| 61 6e 64 20 7b 66 43 6f | 64 65 7d 6e 65 78 74 7b |and {fCo|de}next{|
|00003a50| 66 7d 20 6d 61 79 20 62 | 65 20 75 73 65 64 20 61 |f} may b|e used a|
|00003a60| 73 0a 69 74 65 72 61 74 | 6f 72 73 2c 20 61 73 20 |s.iterat|ors, as |
|00003a70| 69 6e 20 0a 7b 66 43 6f | 64 65 7d 66 6f 72 20 28 |in .{fCo|de}for (|
|00003a80| 69 6e 74 20 69 20 3d 20 | 61 2e 66 69 72 73 74 28 |int i = |a.first(|
|00003a90| 29 3b 20 69 20 5c 3e 3d | 20 30 3b 20 69 20 3d 20 |); i \>=| 0; i = |
|00003aa0| 61 2e 6e 65 78 74 28 69 | 29 29 2e 2e 2e 7b 66 7d |a.next(i|))...{f}|
|00003ab0| 2e 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |...#Inde|nt.{fCod|
|00003ac0| 65 7d 61 2e 6c 61 73 74 | 28 31 29 7b 66 7d 0a 23 |e}a.last|(1){f}.#|
|00003ad0| 49 6e 64 65 6e 74 20 2b | 34 0a 72 65 74 75 72 6e |Indent +|4.return|
|00003ae0| 73 20 74 68 65 20 69 6e | 64 65 78 20 6f 66 20 74 |s the in|dex of t|
|00003af0| 68 65 20 72 69 67 68 74 | 6d 6f 73 74 20 73 65 74 |he right|most set|
|00003b00| 20 62 69 74 2c 20 6f 72 | 20 2d 31 20 69 66 20 74 | bit, or| -1 if t|
|00003b10| 68 65 72 65 20 6f 72 20 | 6e 6f 20 73 65 74 0a 62 |here or |no set.b|
|00003b20| 69 74 73 20 6f 72 20 61 | 6c 6c 20 73 65 74 20 62 |its or a|ll set b|
|00003b30| 69 74 73 2e 0a 0a 23 49 | 6e 64 65 6e 74 0a 7b 66 |its...#I|ndent.{f|
|00003b40| 43 6f 64 65 7d 61 2e 70 | 72 65 76 28 33 2c 20 30 |Code}a.p|rev(3, 0|
|00003b50| 29 7b 66 7d 0a 23 49 6e | 64 65 6e 74 20 2b 34 0a |){f}.#In|dent +4.|
|00003b60| 72 65 74 75 72 6e 73 20 | 74 68 65 20 69 6e 64 65 |returns |the inde|
|00003b70| 78 20 6f 66 20 74 68 65 | 20 70 72 65 76 69 6f 75 |x of the| previou|
|00003b80| 73 20 63 6c 65 61 72 20 | 62 69 74 20 62 65 66 6f |s clear |bit befo|
|00003b90| 72 65 20 70 6f 73 69 74 | 69 6f 6e 20 33 2e 0a 0a |re posit|ion 3...|
|00003ba0| 23 49 6e 64 65 6e 74 0a | 7b 66 43 6f 64 65 7d 61 |#Indent.|{fCode}a|
|00003bb0| 2e 63 6f 75 6e 74 28 31 | 29 7b 66 7d 0a 23 49 6e |.count(1|){f}.#In|
|00003bc0| 64 65 6e 74 20 2b 34 0a | 72 65 74 75 72 6e 73 20 |dent +4.|returns |
|00003bd0| 74 68 65 20 6e 75 6d 62 | 65 72 20 6f 66 20 73 65 |the numb|er of se|
|00003be0| 74 20 62 69 74 73 20 69 | 6e 20 61 2c 20 6f 72 20 |t bits i|n a, or |
|00003bf0| 2d 31 20 69 66 20 74 68 | 65 72 65 20 61 72 65 20 |-1 if th|ere are |
|00003c00| 0a 61 6e 20 69 6e 66 69 | 6e 69 74 65 20 6e 75 6d |.an infi|nite num|
|00003c10| 62 65 72 2e 0a 0a 23 49 | 6e 64 65 6e 74 0a 7b 66 |ber...#I|ndent.{f|
|00003c20| 43 6f 64 65 7d 61 2e 76 | 69 72 74 75 61 6c 5c 5f |Code}a.v|irtual\_|
|00003c30| 62 69 74 28 29 7b 66 7d | 0a 23 49 6e 64 65 6e 74 |bit(){f}|.#Indent|
|00003c40| 20 2b 34 0a 72 65 74 75 | 72 6e 73 20 74 68 65 20 | +4.retu|rns the |
|00003c50| 74 72 61 69 6c 69 6e 67 | 20 28 69 6e 66 69 6e 69 |trailing| (infini|
|00003c60| 74 65 6c 79 20 72 65 70 | 6c 69 63 61 74 65 64 29 |tely rep|licated)|
|00003c70| 20 62 69 74 20 6f 66 20 | 61 2e 0a 0a 23 49 6e 64 | bit of |a...#Ind|
|00003c80| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 61 20 3d 20 61 |ent.{fCo|de}a = a|
|00003c90| 74 6f 42 69 74 53 65 74 | 28 22 61 62 61 62 58 22 |toBitSet|("ababX"|
|00003ca0| 2c 20 27 61 27 2c 20 27 | 62 27 2c 20 27 58 27 29 |, 'a', '|b', 'X')|
|00003cb0| 3b 7b 66 7d 0a 23 49 6e | 64 65 6e 74 20 2b 34 0a |;{f}.#In|dent +4.|
|00003cc0| 63 6f 6e 76 65 72 74 73 | 20 74 68 65 20 63 68 61 |converts| the cha|
|00003cd0| 72 5c 2a 20 73 74 72 69 | 6e 67 20 69 6e 74 6f 20 |r\* stri|ng into |
|00003ce0| 61 20 62 69 74 73 65 74 | 2c 20 77 69 74 68 20 27 |a bitset|, with '|
|00003cf0| 61 27 20 64 65 6e 6f 74 | 69 6e 67 20 66 61 6c 73 |a' denot|ing fals|
|00003d00| 65 2c 0a 27 62 27 20 64 | 65 6e 6f 74 69 6e 67 20 |e,.'b' d|enoting |
|00003d10| 74 72 75 65 2c 20 61 6e | 64 20 27 58 27 20 64 65 |true, an|d 'X' de|
|00003d20| 6e 6f 74 69 6e 67 20 69 | 6e 66 69 6e 69 74 65 20 |noting i|nfinite |
|00003d30| 72 65 70 6c 69 63 61 74 | 69 6f 6e 2e 0a 0a 23 49 |replicat|ion...#I|
|00003d40| 6e 64 65 6e 74 0a 7b 66 | 43 6f 64 65 7d 61 2e 70 |ndent.{f|Code}a.p|
|00003d50| 72 69 6e 74 6f 6e 28 63 | 6f 75 74 2c 20 27 2d 27 |rinton(c|out, '-'|
|00003d60| 2c 20 27 2e 27 2c 20 30 | 29 7b 66 7d 0a 23 49 6e |, '.', 0|){f}.#In|
|00003d70| 64 65 6e 74 20 2b 34 0a | 70 72 69 6e 74 73 20 7b |dent +4.|prints {|
|00003d80| 66 43 6f 64 65 7d 61 7b | 66 7d 20 74 6f 20 7b 66 |fCode}a{|f} to {f|
|00003d90| 43 6f 64 65 7d 63 6f 75 | 74 7b 66 7d 20 72 65 70 |Code}cou|t{f} rep|
|00003da0| 72 65 73 65 6e 74 65 64 | 20 77 69 74 68 0a 7b 66 |resented| with.{f|
|00003db0| 43 6f 64 65 7d 27 2d 27 | 7b 66 7d 20 66 6f 72 20 |Code}'-'|{f} for |
|00003dc0| 66 61 6c 73 65 73 2c 20 | 7b 66 43 6f 64 65 7d 27 |falses, |{fCode}'|
|00003dd0| 2e 27 7b 66 7d 20 66 6f | 72 20 74 72 75 65 73 2c |.'{f} fo|r trues,|
|00003de0| 20 61 6e 64 20 6e 6f 20 | 72 65 70 6c 69 63 61 74 | and no |replicat|
|00003df0| 69 6f 6e 20 6d 61 72 6b | 65 72 2e 0a 0a 23 49 6e |ion mark|er...#In|
|00003e00| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 63 6f 75 74 |dent.{fC|ode}cout|
|00003e10| 20 5c 3c 5c 3c 20 61 7b | 66 7d 0a 23 49 6e 64 65 | \<\< a{|f}.#Inde|
|00003e20| 6e 74 20 2b 34 0a 70 72 | 69 6e 74 73 20 7b 66 43 |nt +4.pr|ints {fC|
|00003e30| 6f 64 65 7d 61 7b 66 7d | 20 74 6f 20 7b 66 43 6f |ode}a{f}| to {fCo|
|00003e40| 64 65 7d 63 6f 75 74 7b | 66 7d 20 28 72 65 70 72 |de}cout{|f} (repr|
|00003e50| 65 73 65 6e 74 69 6e 67 | 20 6c 61 73 65 73 20 62 |esenting| lases b|
|00003e60| 79 20 7b 66 43 6f 64 65 | 7d 27 66 27 7b 66 7d 2c |y {fCode|}'f'{f},|
|00003e70| 0a 74 72 75 65 73 20 62 | 79 20 7b 66 43 6f 64 65 |.trues b|y {fCode|
|00003e80| 7d 27 74 27 7b 66 7d 2c | 20 61 6e 64 20 75 73 69 |}'t'{f},| and usi|
|00003e90| 6e 67 20 7b 66 43 6f 64 | 65 7d 27 5c 2a 27 7b 66 |ng {fCod|e}'\*'{f|
|00003ea0| 7d 20 61 73 20 74 68 65 | 20 72 65 70 6c 69 63 61 |} as the| replica|
|00003eb0| 74 69 6f 6e 20 6d 61 72 | 6b 65 72 29 2e 0a 0a 23 |tion mar|ker)...#|
|00003ec0| 49 6e 64 65 6e 74 0a 7b | 66 43 6f 64 65 7d 64 69 |Indent.{|fCode}di|
|00003ed0| 66 66 28 78 2c 20 79 2c | 20 7a 29 7b 66 7d 0a 23 |ff(x, y,| z){f}.#|
|00003ee0| 49 6e 64 65 6e 74 20 2b | 34 0a 41 20 66 61 73 74 |Indent +|4.A fast|
|00003ef0| 65 72 20 77 61 79 20 74 | 6f 20 73 61 79 20 7a 20 |er way t|o say z |
|00003f00| 3d 20 78 20 2d 20 79 2e | 0a 0a 23 49 6e 64 65 6e |= x - y.|..#Inden|
|00003f10| 74 0a 7b 66 43 6f 64 65 | 7d 61 6e 64 28 78 2c 20 |t.{fCode|}and(x, |
|00003f20| 79 2c 20 7a 29 7b 66 7d | 0a 23 49 6e 64 65 6e 74 |y, z){f}|.#Indent|
|00003f30| 20 2b 34 0a 41 20 66 61 | 73 74 65 72 20 77 61 79 | +4.A fa|ster way|
|00003f40| 20 74 6f 20 73 61 79 20 | 7a 20 3d 20 78 20 26 20 | to say |z = x & |
|00003f50| 79 2e 0a 0a 23 49 6e 64 | 65 6e 74 0a 7b 66 43 6f |y...#Ind|ent.{fCo|
|00003f60| 64 65 7d 6f 72 28 78 2c | 20 79 2c 20 7a 29 7b 66 |de}or(x,| y, z){f|
|00003f70| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 41 20 66 |}.#Inden|t +4.A f|
|00003f80| 61 73 74 65 72 20 77 61 | 79 20 74 6f 20 73 61 79 |aster wa|y to say|
|00003f90| 20 7a 20 3d 20 78 20 7c | 20 79 2e 0a 0a 23 49 6e | z = x || y...#In|
|00003fa0| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 78 6f 72 28 |dent.{fC|ode}xor(|
|00003fb0| 78 2c 20 79 2c 20 7a 29 | 7b 66 7d 0a 23 49 6e 64 |x, y, z)|{f}.#Ind|
|00003fc0| 65 6e 74 20 2b 34 0a 41 | 20 66 61 73 74 65 72 20 |ent +4.A| faster |
|00003fd0| 77 61 79 20 74 6f 20 73 | 61 79 20 7a 20 3d 20 78 |way to s|ay z = x|
|00003fe0| 20 5e 20 79 2e 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b | ^ y...#|Indent.{|
|00003ff0| 66 43 6f 64 65 7d 63 6f | 6d 70 6c 65 6d 65 6e 74 |fCode}co|mplement|
|00004000| 28 78 2c 20 7a 29 7b 66 | 7d 0a 23 49 6e 64 65 6e |(x, z){f|}.#Inden|
|00004010| 74 20 2b 34 0a 41 20 66 | 61 73 74 65 72 20 77 61 |t +4.A f|aster wa|
|00004020| 79 20 74 6f 20 73 61 79 | 20 7a 20 3d 20 7e 78 2e |y to say| z = ~x.|
|00004030| 0a 0a 0a 23 49 6e 64 65 | 6e 74 0a 0a 7b 66 48 33 |...#Inde|nt..{fH3|
|00004040| 7d 42 69 74 53 74 72 69 | 6e 67 7b 66 7d 0a 0a 42 |}BitStri|ng{f}..B|
|00004050| 69 74 53 74 72 69 6e 67 | 73 20 61 72 65 20 6f 62 |itString|s are ob|
|00004060| 6a 65 63 74 73 20 74 68 | 61 74 20 63 6f 6e 74 61 |jects th|at conta|
|00004070| 69 6e 20 61 72 62 69 74 | 72 61 72 79 2d 6c 65 6e |in arbit|rary-len|
|00004080| 67 74 68 20 73 74 72 69 | 6e 67 73 20 6f 66 0a 7a |gth stri|ngs of.z|
|00004090| 65 72 6f 65 73 20 61 6e | 64 20 6f 6e 65 73 2e 20 |eroes an|d ones. |
|000040a0| 42 69 74 53 74 72 69 6e | 67 73 20 70 6f 73 73 65 |BitStrin|gs posse|
|000040b0| 73 73 20 73 6f 6d 65 20 | 66 65 61 74 75 72 65 73 |ss some |features|
|000040c0| 20 74 68 61 74 20 6d 61 | 6b 65 20 74 68 65 6d 0a | that ma|ke them.|
|000040d0| 62 65 68 61 76 65 20 6c | 69 6b 65 20 73 65 74 73 |behave l|ike sets|
|000040e0| 2c 20 61 6e 64 20 6f 74 | 68 65 72 73 20 74 68 61 |, and ot|hers tha|
|000040f0| 74 20 62 65 68 61 76 65 | 20 61 73 20 73 74 72 69 |t behave| as stri|
|00004100| 6e 67 73 2e 20 54 68 65 | 79 20 61 72 65 0a 75 73 |ngs. The|y are.us|
|00004110| 65 66 75 6c 20 69 6e 20 | 61 70 70 6c 69 63 61 74 |eful in |applicat|
|00004120| 69 6f 6e 73 20 28 73 75 | 63 68 20 61 73 20 73 69 |ions (su|ch as si|
|00004130| 67 6e 61 74 75 72 65 2d | 62 61 73 65 64 20 61 6c |gnature-|based al|
|00004140| 67 6f 72 69 74 68 6d 73 | 29 20 77 68 65 72 65 0a |gorithms|) where.|
|00004150| 62 6f 74 68 20 63 61 70 | 61 62 69 6c 69 74 69 65 |both cap|abilitie|
|00004160| 73 20 61 72 65 20 6e 65 | 65 64 65 64 2e 20 20 52 |s are ne|eded. R|
|00004170| 65 70 72 65 73 65 6e 74 | 61 74 69 6f 6e 61 6c 20 |epresent|ational |
|00004180| 64 65 74 61 69 6c 73 20 | 61 72 65 0a 64 69 73 63 |details |are.disc|
|00004190| 75 73 73 65 64 20 69 6e | 20 74 68 65 20 52 65 70 |ussed in| the Rep|
|000041a0| 72 65 73 65 6e 74 61 74 | 69 6f 6e 20 63 68 61 70 |resentat|ion chap|
|000041b0| 74 65 72 2e 20 20 4d 6f | 73 74 20 63 61 70 61 62 |ter. Mo|st capab|
|000041c0| 69 6c 69 74 69 65 73 20 | 61 72 65 0a 65 78 61 63 |ilities |are.exac|
|000041d0| 74 20 61 6e 61 6c 6f 67 | 73 20 6f 66 20 74 68 6f |t analog|s of tho|
|000041e0| 73 65 20 73 75 70 70 6f | 72 74 65 64 20 69 6e 20 |se suppo|rted in |
|000041f0| 74 68 65 20 42 69 74 53 | 65 74 20 61 6e 64 20 53 |the BitS|et and S|
|00004200| 74 72 69 6e 67 0a 63 6c | 61 73 73 65 73 2e 20 20 |tring.cl|asses. |
|00004210| 41 20 42 69 74 53 75 62 | 53 74 72 69 6e 67 20 69 |A BitSub|String i|
|00004220| 73 20 75 73 65 64 20 77 | 69 74 68 20 73 75 62 73 |s used w|ith subs|
|00004230| 74 72 69 6e 67 20 6f 70 | 65 72 61 74 69 6f 6e 73 |tring op|erations|
|00004240| 20 61 6c 6f 6e 67 0a 74 | 68 65 20 73 61 6d 65 20 | along.t|he same |
|00004250| 6c 69 6e 65 73 20 61 73 | 20 74 68 65 20 53 74 72 |lines as| the Str|
|00004260| 69 6e 67 20 53 75 62 53 | 74 72 69 6e 67 20 63 6c |ing SubS|tring cl|
|00004270| 61 73 73 2e 20 20 41 20 | 42 69 74 50 61 74 74 65 |ass. A |BitPatte|
|00004280| 72 6e 20 63 6c 61 73 73 | 0a 69 73 20 75 73 65 64 |rn class|.is used|
|00004290| 20 66 6f 72 20 6d 61 73 | 6b 65 64 20 62 69 74 20 | for mas|ked bit |
|000042a0| 70 61 74 74 65 72 6e 20 | 73 65 61 72 63 68 69 6e |pattern |searchin|
|000042b0| 67 2e 0a 0a 4f 6e 6c 79 | 20 61 20 64 65 66 61 75 |g...Only| a defau|
|000042c0| 6c 74 20 63 6f 6e 73 74 | 72 75 63 74 6f 72 20 69 |lt const|ructor i|
|000042d0| 73 20 73 75 70 70 6f 72 | 74 65 64 2e 20 20 54 68 |s suppor|ted. Th|
|000042e0| 65 20 64 65 63 6c 61 72 | 61 74 69 6f 6e 0a 7b 66 |e declar|ation.{f|
|000042f0| 43 6f 64 65 7d 42 69 74 | 53 74 72 69 6e 67 20 61 |Code}Bit|String a|
|00004300| 3b 7b 66 7d 20 69 6e 69 | 74 69 61 6c 69 7a 65 73 |;{f} ini|tializes|
|00004310| 20 61 20 74 6f 20 62 65 | 20 61 6e 20 65 6d 70 74 | a to be| an empt|
|00004320| 79 20 42 69 74 53 74 72 | 69 6e 67 2e 0a 42 69 74 |y BitStr|ing..Bit|
|00004330| 53 74 72 69 6e 67 73 20 | 6d 61 79 20 6f 66 74 65 |Strings |may ofte|
|00004340| 6e 20 62 65 20 69 6e 69 | 74 69 61 6c 69 7a 65 64 |n be ini|tialized|
|00004350| 20 76 69 61 20 7b 66 43 | 6f 64 65 7d 61 74 6f 42 | via {fC|ode}atoB|
|00004360| 69 74 53 74 72 69 6e 67 | 7b 66 7d 0a 61 6e 64 20 |itString|{f}.and |
|00004370| 7b 66 43 6f 64 65 7d 6c | 6f 6e 67 74 6f 42 69 74 |{fCode}l|ongtoBit|
|00004380| 53 74 72 69 6e 67 7b 66 | 7d 2e 0a 0a 53 65 74 20 |String{f|}...Set |
|00004390| 6f 70 65 72 61 74 69 6f | 6e 73 20 28 7b 66 43 6f |operatio|ns ({fCo|
|000043a0| 64 65 7d 20 7e 2c 20 63 | 6f 6d 70 6c 65 6d 65 6e |de} ~, c|omplemen|
|000043b0| 74 2c 20 26 2c 20 26 3d | 2c 20 7c 2c 20 7c 3d 2c |t, &, &=|, |, |=,|
|000043c0| 20 2d 2c 20 5e 2c 20 5e | 3d 7b 66 7d 29 0a 62 65 | -, ^, ^|={f}).be|
|000043d0| 68 61 76 65 20 6a 75 73 | 74 20 61 73 20 74 68 65 |have jus|t as the|
|000043e0| 20 42 69 74 53 65 74 20 | 76 65 72 73 69 6f 6e 73 | BitSet |versions|
|000043f0| 2c 20 65 78 63 65 70 74 | 20 74 68 61 74 20 74 68 |, except| that th|
|00004400| 65 72 65 20 69 73 20 6e | 6f 0a 60 60 76 69 72 74 |ere is n|o.``virt|
|00004410| 75 61 6c 20 62 69 74 27 | 27 3a 20 63 6f 6d 70 6c |ual bit'|': compl|
|00004420| 65 6d 65 6e 74 69 6e 67 | 20 63 6f 6d 70 6c 65 6d |ementing| complem|
|00004430| 65 6e 74 73 20 6f 6e 6c | 79 20 74 68 6f 73 65 20 |ents onl|y those |
|00004440| 62 69 74 73 20 69 6e 20 | 74 68 65 0a 42 69 74 53 |bits in |the.BitS|
|00004450| 74 72 69 6e 67 2c 20 61 | 6e 64 20 61 6c 6c 20 62 |tring, a|nd all b|
|00004460| 69 6e 61 72 79 20 6f 70 | 65 72 61 74 69 6f 6e 73 |inary op|erations|
|00004470| 20 61 63 72 6f 73 73 20 | 75 6e 65 71 75 61 6c 20 | across |unequal |
|00004480| 6c 65 6e 67 74 68 0a 42 | 69 74 53 74 72 69 6e 67 |length.B|itString|
|00004490| 73 20 61 73 73 75 6d 65 | 20 61 20 76 69 72 74 75 |s assume| a virtu|
|000044a0| 61 6c 20 62 69 74 20 6f | 66 20 7a 65 72 6f 2e 20 |al bit o|f zero. |
|000044b0| 54 68 65 20 7b 66 43 6f | 64 65 7d 26 7b 66 7d 20 |The {fCo|de}&{f} |
|000044c0| 6f 70 65 72 61 74 69 6f | 6e 0a 72 65 74 75 72 6e |operatio|n.return|
|000044d0| 73 20 61 20 42 69 74 53 | 74 72 69 6e 67 20 77 69 |s a BitS|tring wi|
|000044e0| 74 68 20 61 20 6c 65 6e | 67 74 68 20 65 71 75 61 |th a len|gth equa|
|000044f0| 6c 20 74 6f 20 74 68 65 | 20 6d 69 6e 69 6d 75 6d |l to the| minimum|
|00004500| 20 6c 65 6e 67 74 68 20 | 6f 66 0a 74 68 65 20 6f | length |of.the o|
|00004510| 70 65 72 61 6e 64 73 2c | 20 61 6e 64 20 7b 66 43 |perands,| and {fC|
|00004520| 6f 64 65 7d 7c 2c 20 5e | 7b 66 7d 20 72 65 74 75 |ode}|, ^|{f} retu|
|00004530| 72 6e 20 6f 6e 65 20 77 | 69 74 68 20 6c 65 6e 67 |rn one w|ith leng|
|00004540| 74 68 20 6f 66 20 74 68 | 65 0a 6d 61 78 69 6d 75 |th of th|e.maximu|
|00004550| 6d 2e 0a 0a 53 65 74 2d | 62 61 73 65 64 20 72 65 |m...Set-|based re|
|00004560| 6c 61 74 69 6f 6e 61 6c | 20 6f 70 65 72 61 74 69 |lational| operati|
|00004570| 6f 6e 73 20 28 7b 66 43 | 6f 64 65 7d 3d 3d 2c 20 |ons ({fC|ode}==, |
|00004580| 21 3d 2c 20 5c 3c 3d 2c | 20 5c 3c 2c 20 5c 3e 3d |!=, \<=,| \<, \>=|
|00004590| 2c 20 5c 3e 7b 66 7d 29 | 0a 66 6f 6c 6c 6f 77 20 |, \>{f})|.follow |
|000045a0| 74 68 65 20 73 61 6d 65 | 20 72 75 6c 65 73 2e 20 |the same| rules. |
|000045b0| 41 20 73 74 72 69 6e 67 | 2d 6c 69 6b 65 20 6c 65 |A string|-like le|
|000045c0| 78 69 63 6f 67 72 61 70 | 68 69 63 20 63 6f 6d 70 |xicograp|hic comp|
|000045d0| 61 72 69 73 6f 6e 0a 66 | 75 6e 63 74 69 6f 6e 2c |arison.f|unction,|
|000045e0| 20 7b 66 43 6f 64 65 7d | 6c 63 6f 6d 70 61 72 65 | {fCode}|lcompare|
|000045f0| 7b 66 7d 2c 20 74 65 73 | 74 73 20 74 68 65 20 6c |{f}, tes|ts the l|
|00004600| 65 78 69 63 6f 67 72 61 | 70 68 69 63 20 72 65 6c |exicogra|phic rel|
|00004610| 61 74 69 6f 6e 20 62 65 | 74 77 65 65 6e 0a 74 77 |ation be|tween.tw|
|00004620| 6f 20 42 69 74 53 74 72 | 69 6e 67 73 2e 20 46 6f |o BitStr|ings. Fo|
|00004630| 72 20 65 78 61 6d 70 6c | 65 2c 20 6c 63 6f 6d 70 |r exampl|e, lcomp|
|00004640| 61 72 65 28 31 31 30 30 | 2c 20 30 31 30 31 29 20 |are(1100|, 0101) |
|00004650| 72 65 74 75 72 6e 73 20 | 31 2c 0a 73 69 6e 63 65 |returns |1,.since|
|00004660| 20 74 68 65 20 66 69 72 | 73 74 20 42 69 74 53 74 | the fir|st BitSt|
|00004670| 72 69 6e 67 20 73 74 61 | 72 74 73 20 77 69 74 68 |ring sta|rts with|
|00004680| 20 31 20 61 6e 64 20 74 | 68 65 20 73 65 63 6f 6e | 1 and t|he secon|
|00004690| 64 20 77 69 74 68 20 30 | 2e 0a 0a 49 6e 64 69 76 |d with 0|...Indiv|
|000046a0| 69 64 75 61 6c 20 62 69 | 74 20 73 65 74 74 69 6e |idual bi|t settin|
|000046b0| 67 2c 20 74 65 73 74 69 | 6e 67 2c 20 61 6e 64 20 |g, testi|ng, and |
|000046c0| 69 74 65 72 61 74 6f 72 | 20 6f 70 65 72 61 74 69 |iterator| operati|
|000046d0| 6f 6e 73 20 0a 28 7b 66 | 43 6f 64 65 7d 73 65 74 |ons .({f|Code}set|
|000046e0| 2c 20 63 6c 65 61 72 2c | 20 69 6e 76 65 72 74 2c |, clear,| invert,|
|000046f0| 20 74 65 73 74 2c 20 66 | 69 72 73 74 2c 20 6e 65 | test, f|irst, ne|
|00004700| 78 74 2c 20 6c 61 73 74 | 2c 20 70 72 65 76 7b 66 |xt, last|, prev{f|
|00004710| 7d 29 0a 61 72 65 20 61 | 6c 73 6f 20 6c 69 6b 65 |}).are a|lso like|
|00004720| 20 74 68 6f 73 65 20 66 | 6f 72 20 42 69 74 53 65 | those f|or BitSe|
|00004730| 74 73 2e 20 42 69 74 53 | 74 72 69 6e 67 73 20 61 |ts. BitS|trings a|
|00004740| 72 65 20 61 75 74 6f 6d | 61 74 69 63 61 6c 6c 79 |re autom|atically|
|00004750| 0a 65 78 70 61 6e 64 65 | 64 20 77 68 65 6e 20 73 |.expande|d when s|
|00004760| 65 74 74 69 6e 67 20 62 | 69 74 73 20 61 74 20 70 |etting b|its at p|
|00004770| 6f 73 69 74 69 6f 6e 73 | 20 67 72 65 61 74 65 72 |ositions| greater|
|00004780| 20 74 68 61 6e 20 74 68 | 65 69 72 0a 63 75 72 72 | than th|eir.curr|
|00004790| 65 6e 74 20 6c 65 6e 67 | 74 68 2e 0a 0a 54 68 65 |ent leng|th...The|
|000047a0| 20 73 74 72 69 6e 67 2d | 62 61 73 65 64 20 63 61 | string-|based ca|
|000047b0| 70 61 62 69 6c 69 74 69 | 65 73 20 61 72 65 20 6a |pabiliti|es are j|
|000047c0| 75 73 74 20 61 73 20 74 | 68 6f 73 65 20 66 6f 72 |ust as t|hose for|
|000047d0| 20 63 6c 61 73 73 20 53 | 74 72 69 6e 67 2e 0a 42 | class S|tring..B|
|000047e0| 69 74 53 74 72 69 6e 67 | 73 20 6d 61 79 20 62 65 |itString|s may be|
|000047f0| 20 63 6f 6e 63 61 74 65 | 6e 61 74 65 64 20 28 7b | concate|nated ({|
|00004800| 66 43 6f 64 65 7d 2b 2c | 20 2b 3d 7b 66 7d 29 2c |fCode}+,| +={f}),|
|00004810| 20 73 65 61 72 63 68 65 | 64 0a 28 7b 66 43 6f 64 | searche|d.({fCod|
|00004820| 65 7d 69 6e 64 65 78 2c | 20 63 6f 6e 74 61 69 6e |e}index,| contain|
|00004830| 73 2c 20 6d 61 74 63 68 | 65 73 7b 66 7d 29 2c 20 |s, match|es{f}), |
|00004840| 61 6e 64 20 65 78 74 72 | 61 63 74 65 64 20 69 6e |and extr|acted in|
|00004850| 74 6f 0a 42 69 74 53 75 | 62 53 74 72 69 6e 67 73 |to.BitSu|bStrings|
|00004860| 20 28 7b 66 43 6f 64 65 | 7d 62 65 66 6f 72 65 2c | ({fCode|}before,|
|00004870| 20 61 74 2c 20 61 66 74 | 65 72 7b 66 7d 29 20 77 | at, aft|er{f}) w|
|00004880| 68 69 63 68 20 6d 61 79 | 20 62 65 20 61 73 73 69 |hich may| be assi|
|00004890| 67 6e 65 64 20 61 6e 64 | 0a 6f 74 68 65 72 77 69 |gned and|.otherwi|
|000048a0| 73 65 20 6d 61 6e 69 70 | 75 6c 61 74 65 64 2e 20 |se manip|ulated. |
|000048b0| 4f 74 68 65 72 20 73 74 | 72 69 6e 67 2d 62 61 73 |Other st|ring-bas|
|000048c0| 65 64 20 75 74 69 6c 69 | 74 79 20 66 75 6e 63 74 |ed utili|ty funct|
|000048d0| 69 6f 6e 73 0a 28 7b 66 | 43 6f 64 65 7d 72 65 76 |ions.({f|Code}rev|
|000048e0| 65 72 73 65 2c 20 63 6f | 6d 6d 6f 6e 5c 5f 70 72 |erse, co|mmon\_pr|
|000048f0| 65 66 69 78 2c 20 63 6f | 6d 6d 6f 6e 5c 5f 73 75 |efix, co|mmon\_su|
|00004900| 66 66 69 78 7b 66 7d 29 | 20 61 72 65 20 61 6c 73 |ffix{f})| are als|
|00004910| 6f 20 70 72 6f 76 69 64 | 65 64 2e 0a 54 68 65 73 |o provid|ed..Thes|
|00004920| 65 20 68 61 76 65 20 74 | 68 65 20 73 61 6d 65 20 |e have t|he same |
|00004930| 63 61 70 61 62 69 6c 69 | 74 69 65 73 20 61 6e 64 |capabili|ties and|
|00004940| 20 64 65 73 63 72 69 70 | 74 69 6f 6e 73 20 61 73 | descrip|tions as|
|00004950| 20 74 68 6f 73 65 0a 66 | 6f 72 20 53 74 72 69 6e | those.f|or Strin|
|00004960| 67 73 2e 0a 0a 53 74 72 | 69 6e 67 2d 6f 72 69 65 |gs...Str|ing-orie|
|00004970| 6e 74 65 64 20 6f 70 65 | 72 61 74 69 6f 6e 73 20 |nted ope|rations |
|00004980| 63 61 6e 20 61 6c 73 6f | 20 62 65 20 70 65 72 66 |can also| be perf|
|00004990| 6f 72 6d 65 64 20 77 69 | 74 68 20 61 20 6d 61 73 |ormed wi|th a mas|
|000049a0| 6b 20 76 69 61 0a 63 6c | 61 73 73 20 42 69 74 50 |k via.cl|ass BitP|
|000049b0| 61 74 74 65 72 6e 2e 20 | 42 69 74 50 61 74 74 65 |attern. |BitPatte|
|000049c0| 72 6e 73 20 63 6f 6e 73 | 69 73 74 20 6f 66 20 74 |rns cons|ist of t|
|000049d0| 77 6f 20 42 69 74 53 74 | 72 69 6e 67 73 2c 20 61 |wo BitSt|rings, a|
|000049e0| 0a 70 61 74 74 65 72 6e | 20 61 6e 64 20 61 20 6d |.pattern| and a m|
|000049f0| 61 73 6b 2e 20 4f 6e 20 | 73 65 61 72 63 68 69 6e |ask. On |searchin|
|00004a00| 67 20 61 6e 64 20 6d 61 | 74 63 68 69 6e 67 2c 20 |g and ma|tching, |
|00004a10| 62 69 74 73 20 69 6e 20 | 74 68 65 20 70 61 74 74 |bits in |the patt|
|00004a20| 65 72 6e 0a 74 68 61 74 | 20 63 6f 72 72 65 73 70 |ern.that| corresp|
|00004a30| 6f 6e 64 20 74 6f 20 30 | 20 62 69 74 73 20 69 6e |ond to 0| bits in|
|00004a40| 20 74 68 65 20 6d 61 73 | 6b 20 61 72 65 20 69 67 | the mas|k are ig|
|00004a50| 6e 6f 72 65 64 2e 20 28 | 54 68 65 20 6d 61 73 6b |nored. (|The mask|
|00004a60| 20 6d 61 79 0a 62 65 20 | 73 68 6f 72 74 65 72 20 | may.be |shorter |
|00004a70| 74 68 61 6e 20 74 68 65 | 20 70 61 74 74 65 72 6e |than the| pattern|
|00004a80| 2c 20 69 6e 20 77 68 69 | 63 68 20 63 61 73 65 20 |, in whi|ch case |
|00004a90| 74 72 61 69 6c 69 6e 67 | 20 6d 61 73 6b 20 62 69 |trailing| mask bi|
|00004aa0| 74 73 20 61 72 65 0a 61 | 73 73 75 6d 65 64 20 74 |ts are.a|ssumed t|
|00004ab0| 6f 20 62 65 20 30 29 2e | 20 54 68 65 20 70 61 74 |o be 0).| The pat|
|00004ac0| 74 65 72 6e 20 61 6e 64 | 20 6d 61 73 6b 20 61 72 |tern and| mask ar|
|00004ad0| 65 20 62 6f 74 68 20 70 | 75 62 6c 69 63 20 76 61 |e both p|ublic va|
|00004ae0| 72 69 61 62 6c 65 73 2c | 0a 61 6e 64 20 6d 61 79 |riables,|.and may|
|00004af0| 20 62 65 20 69 6e 64 69 | 76 69 64 75 61 6c 6c 79 | be indi|vidually|
|00004b00| 20 73 75 62 6a 65 63 74 | 65 64 20 74 6f 20 6f 74 | subject|ed to ot|
|00004b10| 68 65 72 20 62 69 74 20 | 6f 70 65 72 61 74 69 6f |her bit |operatio|
|00004b20| 6e 73 2e 0a 0a 43 6f 6e | 76 65 72 74 69 6e 67 20 |ns...Con|verting |
|00004b30| 74 6f 20 63 68 61 72 5c | 2a 20 61 6e 64 20 70 72 |to char\|* and pr|
|00004b40| 69 6e 74 69 6e 67 20 28 | 7b 66 43 6f 64 65 7d 28 |inting (|{fCode}(|
|00004b50| 61 74 6f 42 69 74 53 74 | 72 69 6e 67 2c 0a 61 74 |atoBitSt|ring,.at|
|00004b60| 6f 42 69 74 50 61 74 74 | 65 72 6e 2c 20 70 72 69 |oBitPatt|ern, pri|
|00004b70| 6e 74 6f 6e 2c 20 6f 73 | 74 72 65 61 6d 20 5c 3c |nton, os|tream \<|
|00004b80| 5c 3c 29 7b 66 7d 29 20 | 61 72 65 20 61 6c 73 6f |\<){f}) |are also|
|00004b90| 20 61 73 20 69 6e 20 42 | 69 74 53 65 74 73 2c 20 | as in B|itSets, |
|00004ba0| 0a 65 78 63 65 70 74 20 | 74 68 61 74 20 6e 6f 20 |.except |that no |
|00004bb0| 76 69 72 74 75 61 6c 20 | 62 69 74 20 69 73 20 75 |virtual |bit is u|
|00004bc0| 73 65 64 2c 20 61 6e 64 | 20 61 6e 20 27 58 27 20 |sed, and| an 'X' |
|00004bd0| 69 6e 20 61 20 42 69 74 | 50 61 74 74 65 72 6e 20 |in a Bit|Pattern |
|00004be0| 6d 65 61 6e 73 0a 74 68 | 61 74 20 74 68 65 20 70 |means.th|at the p|
|00004bf0| 61 74 74 65 72 6e 20 62 | 69 74 20 69 73 20 6d 61 |attern b|it is ma|
|00004c00| 73 6b 65 64 20 6f 75 74 | 2e 0a 0a 54 68 65 20 66 |sked out|...The f|
|00004c10| 6f 6c 6c 6f 77 69 6e 67 | 20 66 65 61 74 75 72 65 |ollowing| feature|
|00004c20| 73 20 61 72 65 20 75 6e | 69 71 75 65 20 74 6f 20 |s are un|ique to |
|00004c30| 42 69 74 53 74 72 69 6e | 67 73 2e 20 0a 0a 41 73 |BitStrin|gs. ..As|
|00004c40| 73 75 6d 65 20 64 65 63 | 6c 61 72 61 74 69 6f 6e |sume dec|laration|
|00004c50| 73 20 6f 66 20 42 69 74 | 53 74 72 69 6e 67 20 61 |s of Bit|String a|
|00004c60| 20 3d 20 61 74 6f 42 69 | 74 53 74 72 69 6e 67 28 | = atoBi|tString(|
|00004c70| 22 30 31 30 31 30 31 31 | 30 22 29 20 61 6e 64 20 |"0101011|0") and |
|00004c80| 62 20 3d 0a 61 74 6f 42 | 69 74 53 54 72 69 6e 67 |b =.atoB|itSTring|
|00004c90| 28 22 31 31 30 31 22 29 | 2e 0a 0a 23 49 6e 64 65 |("1101")|...#Inde|
|00004ca0| 6e 74 20 2b 34 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b |nt +4..#|Indent.{|
|00004cb0| 66 43 6f 64 65 7d 61 20 | 3d 20 62 20 2b 20 63 3b |fCode}a |= b + c;|
|00004cc0| 7b 66 7d 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 53 |{f}.#Ind|ent +4.S|
|00004cd0| 65 74 73 20 61 20 74 6f | 20 74 68 65 20 63 6f 6e |ets a to| the con|
|00004ce0| 63 61 74 65 6e 61 74 69 | 6f 6e 20 6f 66 20 62 20 |catenati|on of b |
|00004cf0| 61 6e 64 20 63 3b 0a 0a | 23 49 6e 64 65 6e 74 0a |and c;..|#Indent.|
|00004d00| 7b 66 43 6f 64 65 7d 61 | 20 3d 20 62 20 2b 20 30 |{fCode}a| = b + 0|
|00004d10| 3b 20 61 20 3d 20 62 20 | 2b 20 31 3b 7b 66 7d 0a |; a = b |+ 1;{f}.|
|00004d20| 23 49 6e 64 65 6e 74 20 | 2b 34 0a 73 65 74 73 20 |#Indent |+4.sets |
|00004d30| 61 20 74 6f 20 62 2c 20 | 61 70 70 65 6e 64 65 64 |a to b, |appended|
|00004d40| 20 77 69 74 68 20 61 20 | 7a 65 72 6f 20 28 6f 6e | with a |zero (on|
|00004d50| 65 29 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 |e)...#In|dent.{fC|
|00004d60| 6f 64 65 7d 61 20 2b 3d | 20 62 3b 7b 66 7d 0a 23 |ode}a +=| b;{f}.#|
|00004d70| 49 6e 64 65 6e 74 20 2b | 34 0a 61 70 70 65 6e 64 |Indent +|4.append|
|00004d80| 73 20 62 20 74 6f 20 61 | 3b 0a 0a 23 49 6e 64 65 |s b to a|;..#Inde|
|00004d90| 6e 74 0a 7b 66 43 6f 64 | 65 7d 61 20 2b 3d 20 30 |nt.{fCod|e}a += 0|
|00004da0| 3b 20 61 20 2b 3d 20 31 | 3b 7b 66 7d 0a 23 49 6e |; a += 1|;{f}.#In|
|00004db0| 64 65 6e 74 20 2b 34 0a | 61 70 70 65 6e 64 73 20 |dent +4.|appends |
|00004dc0| 61 20 7a 65 72 6f 20 28 | 6f 6e 65 29 20 74 6f 20 |a zero (|one) to |
|00004dd0| 61 2e 0a 0a 23 49 6e 64 | 65 6e 74 0a 7b 66 43 6f |a...#Ind|ent.{fCo|
|00004de0| 64 65 7d 61 20 5c 3c 5c | 3c 20 32 3b 20 61 20 5c |de}a \<\|< 2; a \|
|00004df0| 3c 5c 3c 3d 20 32 7b 66 | 7d 0a 23 49 6e 64 65 6e |<\<= 2{f|}.#Inden|
|00004e00| 74 20 2b 34 0a 72 65 74 | 75 72 6e 20 61 20 77 69 |t +4.ret|urn a wi|
|00004e10| 74 68 20 32 20 7a 65 72 | 6f 73 20 70 72 65 70 65 |th 2 zer|os prepe|
|00004e20| 6e 64 65 64 2c 20 73 65 | 74 74 69 6e 67 20 61 20 |nded, se|tting a |
|00004e30| 74 6f 20 30 30 30 31 30 | 31 30 31 31 30 2e 20 28 |to 00010|10110. (|
|00004e40| 4e 6f 74 65 0a 74 68 65 | 20 6e 65 63 65 73 73 61 |Note.the| necessa|
|00004e50| 72 79 20 63 6f 6e 66 75 | 73 69 6f 6e 20 6f 66 20 |ry confu|sion of |
|00004e60| 5c 3c 5c 3c 20 61 6e 64 | 20 5c 3e 5c 3e 20 6f 70 |\<\< and| \>\> op|
|00004e70| 65 72 61 74 6f 72 73 2e | 20 46 6f 72 20 63 6f 6e |erators.| For con|
|00004e80| 73 69 73 74 65 6e 63 79 | 0a 77 69 74 68 20 74 68 |sistency|.with th|
|00004e90| 65 20 69 6e 74 65 67 65 | 72 20 76 65 72 73 69 6f |e intege|r versio|
|00004ea0| 6e 73 2c 20 5c 3c 5c 3c | 20 73 68 69 66 74 73 20 |ns, \<\<| shifts |
|00004eb0| 6c 6f 77 20 62 69 74 73 | 20 74 6f 20 68 69 67 68 |low bits| to high|
|00004ec0| 2c 20 65 76 65 6e 20 74 | 68 6f 75 67 68 0a 74 68 |, even t|hough.th|
|00004ed0| 65 79 20 61 72 65 20 70 | 72 69 6e 74 65 64 20 6c |ey are p|rinted l|
|00004ee0| 6f 77 20 62 69 74 73 20 | 66 69 72 73 74 2e 29 0a |ow bits |first.).|
|00004ef0| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|00004f00| 61 20 5c 3e 5c 3e 20 33 | 3b 20 61 20 5c 3e 5c 3e |a \>\> 3|; a \>\>|
|00004f10| 3d 20 33 7b 66 7d 0a 23 | 49 6e 64 65 6e 74 20 2b |= 3{f}.#|Indent +|
|00004f20| 34 0a 72 65 74 75 72 6e | 20 61 20 77 69 74 68 20 |4.return| a with |
|00004f30| 74 68 65 20 66 69 72 73 | 74 20 33 20 62 69 74 73 |the firs|t 3 bits|
|00004f40| 20 64 65 6c 65 74 65 64 | 2c 20 73 65 74 74 69 6e | deleted|, settin|
|00004f50| 67 20 61 20 74 6f 20 31 | 30 31 31 30 2e 0a 0a 23 |g a to 1|0110...#|
|00004f60| 49 6e 64 65 6e 74 0a 7b | 66 43 6f 64 65 7d 61 2e |Indent.{|fCode}a.|
|00004f70| 6c 65 66 74 5c 5f 74 72 | 69 6d 28 30 29 7b 66 7d |left\_tr|im(0){f}|
|00004f80| 0a 23 49 6e 64 65 6e 74 | 20 2b 34 0a 64 65 6c 65 |.#Indent| +4.dele|
|00004f90| 74 65 73 20 61 6c 6c 20 | 30 20 62 69 74 73 20 6f |tes all |0 bits o|
|00004fa0| 6e 20 74 68 65 20 6c 65 | 66 74 20 6f 66 20 61 2c |n the le|ft of a,|
|00004fb0| 20 73 65 74 74 69 6e 67 | 20 61 20 74 6f 20 31 30 | setting| a to 10|
|00004fc0| 31 30 31 31 30 2e 0a 0a | 23 49 6e 64 65 6e 74 0a |10110...|#Indent.|
|00004fd0| 7b 66 43 6f 64 65 7d 61 | 2e 72 69 67 68 74 5c 5f |{fCode}a|.right\_|
|00004fe0| 74 72 69 6d 28 30 29 7b | 66 7d 0a 23 49 6e 64 65 |trim(0){|f}.#Inde|
|00004ff0| 6e 74 20 2b 34 0a 64 65 | 6c 65 74 65 73 20 61 6c |nt +4.de|letes al|
|00005000| 6c 20 74 72 61 69 6c 69 | 6e 67 20 30 20 62 69 74 |l traili|ng 0 bit|
|00005010| 73 20 6f 66 20 61 2c 20 | 73 65 74 74 69 6e 67 20 |s of a, |setting |
|00005020| 61 20 74 6f 20 30 31 30 | 31 30 31 31 2e 0a 0a 23 |a to 010|1011...#|
|00005030| 49 6e 64 65 6e 74 0a 7b | 66 43 6f 64 65 7d 63 61 |Indent.{|fCode}ca|
|00005040| 74 28 78 2c 20 79 2c 20 | 7a 29 7b 66 7d 0a 23 49 |t(x, y, |z){f}.#I|
|00005050| 6e 64 65 6e 74 20 2b 34 | 0a 41 20 66 61 73 74 65 |ndent +4|.A faste|
|00005060| 72 20 77 61 79 20 74 6f | 20 73 61 79 20 7a 20 3d |r way to| say z =|
|00005070| 20 78 20 2b 20 79 2e 0a | 0a 23 49 6e 64 65 6e 74 | x + y..|.#Indent|
|00005080| 0a 7b 66 43 6f 64 65 7d | 64 69 66 66 28 78 2c 20 |.{fCode}|diff(x, |
|00005090| 79 2c 20 7a 29 7b 66 7d | 0a 23 49 6e 64 65 6e 74 |y, z){f}|.#Indent|
|000050a0| 20 2b 34 0a 41 20 66 61 | 73 74 65 72 20 77 61 79 | +4.A fa|ster way|
|000050b0| 20 74 6f 20 73 61 79 20 | 7a 20 3d 20 78 20 2d 20 | to say |z = x - |
|000050c0| 79 2e 0a 0a 23 49 6e 64 | 65 6e 74 0a 7b 66 43 6f |y...#Ind|ent.{fCo|
|000050d0| 64 65 7d 61 6e 64 28 78 | 2c 20 79 2c 20 7a 29 7b |de}and(x|, y, z){|
|000050e0| 66 7d 0a 23 49 6e 64 65 | 6e 74 20 2b 34 0a 41 20 |f}.#Inde|nt +4.A |
|000050f0| 66 61 73 74 65 72 20 77 | 61 79 20 74 6f 20 73 61 |faster w|ay to sa|
|00005100| 79 20 7a 20 3d 20 78 20 | 26 20 79 2e 0a 0a 23 49 |y z = x |& y...#I|
|00005110| 6e 64 65 6e 74 0a 7b 66 | 43 6f 64 65 7d 6f 72 28 |ndent.{f|Code}or(|
|00005120| 78 2c 20 79 2c 20 7a 29 | 7b 66 7d 0a 23 49 6e 64 |x, y, z)|{f}.#Ind|
|00005130| 65 6e 74 20 2b 34 0a 41 | 20 66 61 73 74 65 72 20 |ent +4.A| faster |
|00005140| 77 61 79 20 74 6f 20 73 | 61 79 20 7a 20 3d 20 78 |way to s|ay z = x|
|00005150| 20 7c 20 79 2e 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b | | y...#|Indent.{|
|00005160| 66 43 6f 64 65 7d 78 6f | 72 28 78 2c 20 79 2c 20 |fCode}xo|r(x, y, |
|00005170| 7a 29 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |z){f}.#I|ndent +4|
|00005180| 0a 41 20 66 61 73 74 65 | 72 20 77 61 79 20 74 6f |.A faste|r way to|
|00005190| 20 73 61 79 20 7a 20 3d | 20 78 20 5e 20 79 2e 0a | say z =| x ^ y..|
|000051a0| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|000051b0| 6c 73 68 69 66 74 28 78 | 2c 20 79 2c 20 7a 29 7b |lshift(x|, y, z){|
|000051c0| 66 7d 0a 23 49 6e 64 65 | 6e 74 20 2b 34 0a 41 20 |f}.#Inde|nt +4.A |
|000051d0| 66 61 73 74 65 72 20 77 | 61 79 20 74 6f 20 73 61 |faster w|ay to sa|
|000051e0| 79 20 7a 20 3d 20 78 20 | 5c 3c 5c 3c 20 79 2e 0a |y z = x |\<\< y..|
|000051f0| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|00005200| 72 73 68 69 66 74 28 78 | 2c 20 79 2c 20 7a 29 7b |rshift(x|, y, z){|
|00005210| 66 7d 0a 23 49 6e 64 65 | 6e 74 20 2b 34 0a 41 20 |f}.#Inde|nt +4.A |
|00005220| 66 61 73 74 65 72 20 77 | 61 79 20 74 6f 20 73 61 |faster w|ay to sa|
|00005230| 79 20 7a 20 3d 20 78 20 | 5c 3e 5c 3e 20 79 2e 0a |y z = x |\>\> y..|
|00005240| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|00005250| 63 6f 6d 70 6c 65 6d 65 | 6e 74 28 78 2c 20 7a 29 |compleme|nt(x, z)|
|00005260| 7b 66 7d 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 41 |{f}.#Ind|ent +4.A|
|00005270| 20 66 61 73 74 65 72 20 | 77 61 79 20 74 6f 20 73 | faster |way to s|
|00005280| 61 79 20 7a 20 3d 20 7e | 78 2e 0a 0a 0a 23 49 6e |ay z = ~|x....#In|
|00005290| 64 65 6e 74 0a 0a 0a 63 | 44 41 54 41 39 0c 00 00 |dent...c|DATA9...|
|000052a0| 42 75 69 6c 74 69 6e 0a | 50 72 65 76 69 6f 75 73 |Builtin.|Previous|
|000052b0| 3a 20 3c 48 65 61 64 65 | 72 73 3d 3e 48 65 61 64 |: <Heade|rs=>Head|
|000052c0| 65 72 73 3e 20 2a 20 4e | 65 78 74 3a 20 3c 4e 65 |ers> * N|ext: <Ne|
|000052d0| 77 3d 3e 4e 65 77 3e 20 | 2a 20 55 70 3a 20 3c 54 |w=>New> |* Up: <T|
|000052e0| 6f 70 3d 3e 21 52 6f 6f | 74 3e 0a 0a 23 57 72 61 |op=>!Roo|t>..#Wra|
|000052f0| 70 20 6f 6e 0a 7b 66 48 | 32 7d 55 74 69 6c 69 74 |p on.{fH|2}Utilit|
|00005300| 79 20 66 75 6e 63 74 69 | 6f 6e 73 20 66 6f 72 20 |y functi|ons for |
|00005310| 62 75 69 6c 74 20 69 6e | 20 74 79 70 65 73 7b 66 |built in| types{f|
|00005320| 7d 0a 0a 46 69 6c 65 73 | 20 7b 66 43 69 74 65 7d |}..Files| {fCite}|
|00005330| 62 75 69 6c 74 69 6e 2e | 68 7b 66 7d 20 61 6e 64 |builtin.|h{f} and|
|00005340| 20 63 6f 72 72 65 73 70 | 6f 6e 64 69 6e 67 20 7b | corresp|onding {|
|00005350| 66 43 69 74 65 7d 2e 63 | 63 7b 66 7d 20 69 6d 70 |fCite}.c|c{f} imp|
|00005360| 6c 65 6d 65 6e 74 61 74 | 69 6f 6e 0a 66 69 6c 65 |lementat|ion.file|
|00005370| 73 20 63 6f 6e 74 61 69 | 6e 20 76 61 72 69 6f 75 |s contai|n variou|
|00005380| 73 20 63 6f 6e 76 65 6e | 69 65 6e 74 0a 69 6e 6c |s conven|ient.inl|
|00005390| 69 6e 65 20 61 6e 64 20 | 6e 6f 6e 2d 69 6e 6c 69 |ine and |non-inli|
|000053a0| 6e 65 20 75 74 69 6c 69 | 74 79 20 66 75 6e 63 74 |ne utili|ty funct|
|000053b0| 69 6f 6e 73 2e 20 54 68 | 65 73 65 20 69 6e 63 6c |ions. Th|ese incl|
|000053c0| 75 64 65 20 75 73 65 66 | 75 6c 0a 65 6e 75 6d 65 |ude usef|ul.enume|
|000053d0| 72 61 74 69 6f 6e 20 74 | 79 70 65 73 2c 20 73 75 |ration t|ypes, su|
|000053e0| 63 68 20 61 73 20 7b 66 | 43 6f 64 65 7d 54 52 55 |ch as {f|Code}TRU|
|000053f0| 45 7b 66 7d 2c 20 7b 66 | 43 6f 64 65 7d 46 41 4c |E{f}, {f|Code}FAL|
|00005400| 53 45 7b 66 7d 20 2c 74 | 68 65 20 74 79 70 65 0a |SE{f} ,t|he type.|
|00005410| 64 65 66 69 6e 69 74 69 | 6f 6e 20 66 6f 72 20 70 |definiti|on for p|
|00005420| 6f 69 6e 74 65 72 73 20 | 74 6f 20 6c 69 62 67 2b |ointers |to libg+|
|00005430| 2b 20 65 72 72 6f 72 20 | 68 61 6e 64 6c 69 6e 67 |+ error |handling|
|00005440| 20 66 75 6e 63 74 69 6f | 6e 73 2c 20 61 6e 64 0a | functio|ns, and.|
|00005450| 74 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 66 75 |the foll|owing fu|
|00005460| 6e 63 74 69 6f 6e 73 2e | 0a 0a 23 49 6e 64 65 6e |nctions.|..#Inden|
|00005470| 74 20 2b 34 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 |t +4.#In|dent.{fC|
|00005480| 6f 64 65 7d 6c 6f 6e 67 | 20 61 62 73 28 6c 6f 6e |ode}long| abs(lon|
|00005490| 67 20 78 29 3b 20 64 6f | 75 62 6c 65 20 61 62 73 |g x); do|uble abs|
|000054a0| 28 64 6f 75 62 6c 65 20 | 78 29 3b 7b 66 7d 0a 23 |(double |x);{f}.#|
|000054b0| 49 6e 64 65 6e 74 20 2b | 34 0a 69 6e 6c 69 6e 65 |Indent +|4.inline|
|000054c0| 20 76 65 72 73 69 6f 6e | 73 20 6f 66 20 61 62 73 | version|s of abs|
|000054d0| 2e 20 4e 6f 74 65 20 74 | 68 61 74 20 74 68 65 20 |. Note t|hat the |
|000054e0| 73 74 61 6e 64 61 72 64 | 20 6c 69 62 63 2e 61 20 |standard| libc.a |
|000054f0| 76 65 72 73 69 6f 6e 2c | 0a 7b 66 43 6f 64 65 7d |version,|.{fCode}|
|00005500| 69 6e 74 20 61 62 73 28 | 69 6e 74 29 7b 66 7d 20 |int abs(|int){f} |
|00005510| 69 73 20 7b 66 45 6d 70 | 68 61 73 69 73 7d 6e 6f |is {fEmp|hasis}no|
|00005520| 74 7b 66 7d 20 64 65 63 | 6c 61 72 65 64 20 61 73 |t{f} dec|lared as|
|00005530| 20 69 6e 6c 69 6e 65 2e | 0a 0a 23 49 6e 64 65 6e | inline.|..#Inden|
|00005540| 74 0a 7b 66 43 6f 64 65 | 7d 76 6f 69 64 20 63 6c |t.{fCode|}void cl|
|00005550| 65 61 72 62 69 74 28 6c | 6f 6e 67 26 20 78 2c 20 |earbit(l|ong& x, |
|00005560| 6c 6f 6e 67 20 62 29 3b | 7b 66 7d 0a 23 49 6e 64 |long b);|{f}.#Ind|
|00005570| 65 6e 74 20 2b 34 0a 63 | 6c 65 61 72 73 20 74 68 |ent +4.c|lears th|
|00005580| 65 20 62 27 74 68 20 62 | 69 74 20 6f 66 20 78 20 |e b'th b|it of x |
|00005590| 28 69 6e 6c 69 6e 65 29 | 2e 0a 0a 23 49 6e 64 65 |(inline)|...#Inde|
|000055a0| 6e 74 0a 7b 66 43 6f 64 | 65 7d 76 6f 69 64 20 73 |nt.{fCod|e}void s|
|000055b0| 65 74 62 69 74 28 6c 6f | 6e 67 26 20 78 2c 20 6c |etbit(lo|ng& x, l|
|000055c0| 6f 6e 67 20 62 29 3b 7b | 66 7d 0a 23 49 6e 64 65 |ong b);{|f}.#Inde|
|000055d0| 6e 74 20 2b 34 0a 73 65 | 74 73 20 74 68 65 20 62 |nt +4.se|ts the b|
|000055e0| 27 74 68 20 62 69 74 20 | 6f 66 20 78 20 28 69 6e |'th bit |of x (in|
|000055f0| 6c 69 6e 65 29 0a 0a 23 | 49 6e 64 65 6e 74 0a 7b |line)..#|Indent.{|
|00005600| 66 43 6f 64 65 7d 69 6e | 74 20 74 65 73 74 62 69 |fCode}in|t testbi|
|00005610| 74 28 6c 6f 6e 67 20 78 | 2c 20 6c 6f 6e 67 20 62 |t(long x|, long b|
|00005620| 29 3b 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |);{f}.#I|ndent +4|
|00005630| 0a 72 65 74 75 72 6e 73 | 20 74 68 65 20 62 27 74 |.returns| the b't|
|00005640| 68 20 62 69 74 20 6f 66 | 20 78 20 28 69 6e 6c 69 |h bit of| x (inli|
|00005650| 6e 65 29 2e 0a 0a 23 49 | 6e 64 65 6e 74 0a 7b 66 |ne)...#I|ndent.{f|
|00005660| 43 6f 64 65 7d 69 6e 74 | 20 65 76 65 6e 28 6c 6f |Code}int| even(lo|
|00005670| 6e 67 20 79 29 3b 7b 66 | 7d 0a 23 49 6e 64 65 6e |ng y);{f|}.#Inden|
|00005680| 74 20 2b 34 0a 72 65 74 | 75 72 6e 73 20 74 72 75 |t +4.ret|urns tru|
|00005690| 65 20 69 66 20 78 20 69 | 73 20 65 76 65 6e 20 28 |e if x i|s even (|
|000056a0| 69 6e 6c 69 6e 65 29 2e | 0a 0a 23 49 6e 64 65 6e |inline).|..#Inden|
|000056b0| 74 0a 7b 66 43 6f 64 65 | 7d 69 6e 74 20 6f 64 64 |t.{fCode|}int odd|
|000056c0| 28 6c 6f 6e 67 20 79 29 | 3b 7b 66 7d 0a 23 49 6e |(long y)|;{f}.#In|
|000056d0| 64 65 6e 74 20 2b 34 0a | 72 65 74 75 72 6e 73 20 |dent +4.|returns |
|000056e0| 74 72 75 65 20 69 73 20 | 78 20 69 73 20 6f 64 64 |true is |x is odd|
|000056f0| 20 28 69 6e 6c 69 6e 65 | 29 2e 0a 0a 23 49 6e 64 | (inline|)...#Ind|
|00005700| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 69 6e 74 20 73 |ent.{fCo|de}int s|
|00005710| 69 67 6e 28 6c 6f 6e 67 | 20 78 29 3b 20 69 6e 74 |ign(long| x); int|
|00005720| 20 73 69 67 6e 28 64 6f | 75 62 6c 65 20 78 29 3b | sign(do|uble x);|
|00005730| 7b 66 7d 0a 23 49 6e 64 | 65 6e 74 20 2b 34 0a 72 |{f}.#Ind|ent +4.r|
|00005740| 65 74 75 72 6e 73 20 2d | 31 2c 20 30 2c 20 6f 72 |eturns -|1, 0, or|
|00005750| 20 31 2c 20 69 6e 64 69 | 63 61 74 69 6e 67 20 77 | 1, indi|cating w|
|00005760| 68 65 74 68 65 72 20 78 | 20 69 73 20 6c 65 73 73 |hether x| is less|
|00005770| 20 74 68 61 6e 2c 20 65 | 71 75 61 6c 20 74 6f 2c | than, e|qual to,|
|00005780| 20 6f 72 0a 67 72 65 61 | 74 65 72 20 74 68 61 6e | or.grea|ter than|
|00005790| 20 7a 65 72 6f 20 28 69 | 6e 6c 69 6e 65 29 2e 0a | zero (i|nline)..|
|000057a0| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|000057b0| 6c 6f 6e 67 20 67 63 64 | 28 6c 6f 6e 67 20 78 2c |long gcd|(long x,|
|000057c0| 20 6c 6f 6e 67 20 79 29 | 3b 7b 66 7d 0a 23 49 6e | long y)|;{f}.#In|
|000057d0| 64 65 6e 74 20 2b 34 0a | 72 65 74 75 72 6e 73 20 |dent +4.|returns |
|000057e0| 74 68 65 20 67 72 65 61 | 74 65 73 74 20 63 6f 6d |the grea|test com|
|000057f0| 6d 6f 6e 20 64 69 76 69 | 73 6f 72 20 6f 66 20 78 |mon divi|sor of x|
|00005800| 20 61 6e 64 20 79 2e 0a | 0a 23 49 6e 64 65 6e 74 | and y..|.#Indent|
|00005810| 0a 7b 66 43 6f 64 65 7d | 6c 6f 6e 67 20 6c 63 6d |.{fCode}|long lcm|
|00005820| 28 6c 6f 6e 67 20 78 2c | 20 6c 6f 6e 67 20 79 29 |(long x,| long y)|
|00005830| 3b 7b 66 7d 0a 23 49 6e | 64 65 6e 74 20 2b 34 0a |;{f}.#In|dent +4.|
|00005840| 72 65 74 75 72 6e 73 20 | 74 68 65 20 6c 65 61 73 |returns |the leas|
|00005850| 74 20 63 6f 6d 6d 6f 6e | 20 6d 75 6c 74 69 70 6c |t common| multipl|
|00005860| 65 20 6f 66 20 78 20 61 | 6e 64 20 79 2e 0a 0a 23 |e of x a|nd y...#|
|00005870| 49 6e 64 65 6e 74 0a 7b | 66 43 6f 64 65 7d 6c 6f |Indent.{|fCode}lo|
|00005880| 6e 67 20 6c 67 28 6c 6f | 6e 67 20 78 29 3b 7b 66 |ng lg(lo|ng x);{f|
|00005890| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 72 65 74 |}.#Inden|t +4.ret|
|000058a0| 75 72 6e 73 20 74 68 65 | 20 66 6c 6f 6f 72 20 6f |urns the| floor o|
|000058b0| 66 20 74 68 65 20 62 61 | 73 65 20 32 20 6c 6f 67 |f the ba|se 2 log|
|000058c0| 20 6f 66 20 78 2e 0a 0a | 23 49 6e 64 65 6e 74 0a | of x...|#Indent.|
|000058d0| 7b 66 43 6f 64 65 7d 6c | 6f 6e 67 20 70 6f 77 28 |{fCode}l|ong pow(|
|000058e0| 6c 6f 6e 67 20 78 2c 20 | 6c 6f 6e 67 20 79 29 3b |long x, |long y);|
|000058f0| 20 64 6f 75 62 6c 65 20 | 70 6f 77 28 64 6f 75 62 | double |pow(doub|
|00005900| 6c 65 20 78 2c 20 6c 6f | 6e 67 20 79 29 3b 7b 66 |le x, lo|ng y);{f|
|00005910| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 72 65 74 |}.#Inden|t +4.ret|
|00005920| 75 72 6e 73 20 78 20 74 | 6f 20 74 68 65 20 69 6e |urns x t|o the in|
|00005930| 74 65 67 65 72 20 70 6f | 77 65 72 20 79 20 75 73 |teger po|wer y us|
|00005940| 69 6e 67 20 76 69 61 20 | 74 68 65 20 69 74 65 72 |ing via |the iter|
|00005950| 61 74 69 76 65 20 4f 28 | 6c 6f 67 20 79 29 0a 60 |ative O(|log y).`|
|00005960| 60 52 75 73 73 69 61 6e | 20 70 65 61 73 61 6e 74 |`Russian| peasant|
|00005970| 27 27 20 6d 65 74 68 6f | 64 2e 0a 0a 23 49 6e 64 |'' metho|d...#Ind|
|00005980| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 6c 6f 6e 67 20 |ent.{fCo|de}long |
|00005990| 73 71 72 28 6c 6f 6e 67 | 20 78 29 3b 20 64 6f 75 |sqr(long| x); dou|
|000059a0| 62 6c 65 20 73 71 72 28 | 64 6f 75 62 6c 65 20 78 |ble sqr(|double x|
|000059b0| 29 3b 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |);{f}.#I|ndent +4|
|000059c0| 0a 72 65 74 75 72 6e 73 | 20 78 20 73 71 75 61 72 |.returns| x squar|
|000059d0| 65 64 20 28 69 6e 6c 69 | 6e 65 29 2e 0a 0a 23 49 |ed (inli|ne)...#I|
|000059e0| 6e 64 65 6e 74 0a 7b 66 | 43 6f 64 65 7d 6c 6f 6e |ndent.{f|Code}lon|
|000059f0| 67 20 73 71 72 74 28 6c | 6f 6e 67 20 79 29 3b 7b |g sqrt(l|ong y);{|
|00005a00| 66 7d 0a 23 49 6e 64 65 | 6e 74 20 2b 34 0a 72 65 |f}.#Inde|nt +4.re|
|00005a10| 74 75 72 6e 73 20 74 68 | 65 20 66 6c 6f 6f 72 20 |turns th|e floor |
|00005a20| 6f 66 20 74 68 65 20 73 | 71 75 61 72 65 20 72 6f |of the s|quare ro|
|00005a30| 6f 74 20 6f 66 20 78 2e | 0a 0a 23 49 6e 64 65 6e |ot of x.|..#Inden|
|00005a40| 74 0a 7b 66 43 6f 64 65 | 7d 75 6e 73 69 67 6e 65 |t.{fCode|}unsigne|
|00005a50| 64 20 69 6e 74 20 68 61 | 73 68 70 6a 77 28 63 6f |d int ha|shpjw(co|
|00005a60| 6e 73 74 20 63 68 61 72 | 5c 2a 20 73 29 3b 7b 66 |nst char|\* s);{f|
|00005a70| 7d 0a 23 49 6e 64 65 6e | 74 20 2b 34 0a 61 20 68 |}.#Inden|t +4.a h|
|00005a80| 61 73 68 20 66 75 6e 63 | 74 69 6f 6e 20 66 6f 72 |ash func|tion for|
|00005a90| 20 6e 75 6c 6c 2d 74 65 | 72 6d 69 6e 61 74 65 64 | null-te|rminated|
|00005aa0| 20 63 68 61 72 5c 2a 20 | 73 74 72 69 6e 67 73 20 | char\* |strings |
|00005ab0| 75 73 69 6e 67 20 74 68 | 65 0a 6d 65 74 68 6f 64 |using th|e.method|
|00005ac0| 20 64 65 73 63 72 69 62 | 65 64 20 69 6e 20 41 68 | describ|ed in Ah|
|00005ad0| 6f 2c 20 53 65 74 68 69 | 2c 20 26 20 55 6c 6c 6d |o, Sethi|, & Ullm|
|00005ae0| 61 6e 2c 20 70 20 34 33 | 36 2e 0a 0a 23 49 6e 64 |an, p 43|6...#Ind|
|00005af0| 65 6e 74 0a 7b 66 43 6f | 64 65 7d 75 6e 73 69 67 |ent.{fCo|de}unsig|
|00005b00| 6e 65 64 20 69 6e 74 20 | 6d 75 6c 74 69 70 6c 69 |ned int |multipli|
|00005b10| 63 61 74 69 76 65 68 61 | 73 68 28 69 6e 74 20 78 |cativeha|sh(int x|
|00005b20| 29 3b 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |);{f}.#I|ndent +4|
|00005b30| 0a 61 20 68 61 73 68 20 | 66 75 6e 63 74 69 6f 6e |.a hash |function|
|00005b40| 20 66 6f 72 20 69 6e 74 | 65 67 65 72 73 20 74 68 | for int|egers th|
|00005b50| 61 74 20 72 65 74 75 72 | 6e 73 20 74 68 65 20 6c |at retur|ns the l|
|00005b60| 6f 77 65 72 20 62 69 74 | 73 20 6f 66 20 0a 6d 75 |ower bit|s of .mu|
|00005b70| 6c 74 69 70 6c 79 69 6e | 67 20 78 20 62 79 20 74 |ltiplyin|g x by t|
|00005b80| 68 65 20 67 6f 6c 64 65 | 6e 20 72 61 74 69 6f 20 |he golde|n ratio |
|00005b90| 74 69 6d 65 73 20 70 6f | 77 28 32 2c 20 33 32 29 |times po|w(2, 32)|
|00005ba0| 2e 20 0a 53 65 65 20 4b | 6e 75 74 68 2c 20 56 6f |. .See K|nuth, Vo|
|00005bb0| 6c 20 33 2c 20 70 20 35 | 30 38 2e 0a 0a 23 49 6e |l 3, p 5|08...#In|
|00005bc0| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 75 6e 73 69 |dent.{fC|ode}unsi|
|00005bd0| 67 6e 65 64 20 69 6e 74 | 20 66 6f 6c 64 68 61 73 |gned int| foldhas|
|00005be0| 68 28 64 6f 75 62 6c 65 | 20 78 29 3b 7b 66 7d 0a |h(double| x);{f}.|
|00005bf0| 23 49 6e 64 65 6e 74 20 | 2b 34 0a 61 20 68 61 73 |#Indent |+4.a has|
|00005c00| 68 20 66 75 6e 63 74 69 | 6f 6e 20 66 6f 72 20 64 |h functi|on for d|
|00005c10| 6f 75 62 6c 65 73 20 74 | 68 61 74 20 65 78 63 6c |oubles t|hat excl|
|00005c20| 75 73 69 76 65 2d 6f 72 | 27 73 20 74 68 65 20 66 |usive-or|'s the f|
|00005c30| 69 72 73 74 20 61 6e 64 | 0a 73 65 63 6f 6e 64 20 |irst and|.second |
|00005c40| 77 6f 72 64 73 20 6f 66 | 20 78 2c 20 72 65 74 75 |words of| x, retu|
|00005c50| 72 6e 69 6e 67 20 74 68 | 65 20 72 65 73 75 6c 74 |rning th|e result|
|00005c60| 20 61 73 20 61 6e 20 69 | 6e 74 65 67 65 72 2e 0a | as an i|nteger..|
|00005c70| 0a 23 49 6e 64 65 6e 74 | 0a 7b 66 43 6f 64 65 7d |.#Indent|.{fCode}|
|00005c80| 64 6f 75 62 6c 65 20 73 | 74 61 72 74 5c 5f 74 69 |double s|tart\_ti|
|00005c90| 6d 65 72 28 29 7b 66 7d | 0a 23 49 6e 64 65 6e 74 |mer(){f}|.#Indent|
|00005ca0| 20 2b 34 0a 53 74 61 72 | 74 73 20 61 20 70 72 6f | +4.Star|ts a pro|
|00005cb0| 63 65 73 73 20 74 69 6d | 65 72 2e 0a 0a 23 49 6e |cess tim|er...#In|
|00005cc0| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 64 6f 75 62 |dent.{fC|ode}doub|
|00005cd0| 6c 65 20 72 65 74 75 72 | 6e 5c 5f 65 6c 61 70 73 |le retur|n\_elaps|
|00005ce0| 65 64 5c 5f 74 69 6d 65 | 28 64 6f 75 62 6c 65 20 |ed\_time|(double |
|00005cf0| 6c 61 73 74 5c 5f 74 69 | 6d 65 29 7b 66 7d 0a 23 |last\_ti|me){f}.#|
|00005d00| 49 6e 64 65 6e 74 20 2b | 34 0a 52 65 74 75 72 6e |Indent +|4.Return|
|00005d10| 73 20 74 68 65 20 70 72 | 6f 63 65 73 73 20 74 69 |s the pr|ocess ti|
|00005d20| 6d 65 20 73 69 6e 63 65 | 20 6c 61 73 74 5c 5f 74 |me since| last\_t|
|00005d30| 69 6d 65 2e 20 0a 49 66 | 20 6c 61 73 74 5c 5f 74 |ime. .If| last\_t|
|00005d40| 69 6d 65 20 3d 3d 20 30 | 20 72 65 74 75 72 6e 73 |ime == 0| returns|
|00005d50| 20 74 68 65 20 74 69 6d | 65 20 73 69 6e 63 65 20 | the tim|e since |
|00005d60| 74 68 65 20 6c 61 73 74 | 20 73 74 61 72 74 5c 5f |the last| start\_|
|00005d70| 74 69 6d 65 72 2e 20 0a | 52 65 74 75 72 6e 73 20 |timer. .|Returns |
|00005d80| 2d 31 20 69 66 20 73 74 | 61 72 74 5c 5f 74 69 6d |-1 if st|art\_tim|
|00005d90| 65 72 20 77 61 73 20 6e | 6f 74 20 66 69 72 73 74 |er was n|ot first|
|00005da0| 20 63 61 6c 6c 65 64 2e | 0a 0a 0a 23 49 6e 64 65 | called.|...#Inde|
|00005db0| 6e 74 0a 0a 46 69 6c 65 | 20 7b 66 43 69 74 65 7d |nt..File| {fCite}|
|00005dc0| 4d 61 78 69 6d 61 2e 68 | 7b 66 7d 20 69 6e 63 6c |Maxima.h|{f} incl|
|00005dd0| 75 64 65 73 20 76 65 72 | 73 69 6f 6e 73 20 6f 66 |udes ver|sions of|
|00005de0| 20 7b 66 43 6f 64 65 7d | 4d 41 58 2c 20 4d 49 4e | {fCode}|MAX, MIN|
|00005df0| 7b 66 7d 0a 66 6f 72 20 | 62 75 69 6c 74 69 6e 20 |{f}.for |builtin |
|00005e00| 74 79 70 65 73 2e 0a 0a | 46 69 6c 65 20 7b 66 43 |types...|File {fC|
|00005e10| 69 74 65 7d 63 6f 6d 70 | 61 72 65 2e 68 7b 66 7d |ite}comp|are.h{f}|
|00005e20| 20 69 6e 63 6c 75 64 65 | 73 20 76 65 72 73 69 6f | include|s versio|
|00005e30| 6e 73 20 6f 66 20 7b 66 | 43 6f 64 65 7d 63 6f 6d |ns of {f|Code}com|
|00005e40| 70 61 72 65 28 78 2c 20 | 79 29 7b 66 7d 0a 66 6f |pare(x, |y){f}.fo|
|00005e50| 72 20 62 75 69 6c 74 69 | 6e 20 74 79 70 65 73 2e |r builti|n types.|
|00005e60| 20 54 68 65 73 65 20 72 | 65 74 75 72 6e 20 6e 65 | These r|eturn ne|
|00005e70| 67 61 74 69 76 65 20 69 | 66 20 74 68 65 20 66 69 |gative i|f the fi|
|00005e80| 72 73 74 20 61 72 67 75 | 6d 65 6e 74 0a 69 73 20 |rst argu|ment.is |
|00005e90| 6c 65 73 73 20 74 68 61 | 6e 20 74 68 65 20 73 65 |less tha|n the se|
|00005ea0| 63 6f 6e 64 2c 20 7a 65 | 72 6f 20 66 6f 72 20 65 |cond, ze|ro for e|
|00005eb0| 71 75 61 6c 2c 20 61 6e | 64 20 70 6f 73 69 74 69 |qual, an|d positi|
|00005ec0| 76 65 20 66 6f 72 20 67 | 72 65 61 74 65 72 2e 0a |ve for g|reater..|
|00005ed0| 0a 00 00 00 44 41 54 41 | 3d 0a 00 00 43 6f 6d 70 |....DATA|=...Comp|
|00005ee0| 6c 65 78 0a 50 72 65 76 | 69 6f 75 73 3a 20 3c 52 |lex.Prev|ious: <R|
|00005ef0| 61 74 69 6f 6e 61 6c 3d | 3e 52 61 74 69 6f 6e 61 |ational=|>Rationa|
|00005f00| 6c 3e 20 2a 20 4e 65 78 | 74 3a 20 3c 46 69 78 3d |l> * Nex|t: <Fix=|
|00005f10| 3e 46 69 78 3e 20 2a 20 | 55 70 3a 20 3c 54 6f 70 |>Fix> * |Up: <Top|
|00005f20| 3d 3e 21 52 6f 6f 74 3e | 0a 0a 23 57 72 61 70 20 |=>!Root>|..#Wrap |
|00005f30| 6f 6e 0a 7b 66 48 32 7d | 54 68 65 20 43 6f 6d 70 |on.{fH2}|The Comp|
|00005f40| 6c 65 78 20 63 6c 61 73 | 73 2e 7b 66 7d 0a 0a 43 |lex clas|s.{f}..C|
|00005f50| 6c 61 73 73 20 7b 66 43 | 6f 64 65 7d 43 6f 6d 70 |lass {fC|ode}Comp|
|00005f60| 6c 65 78 7b 66 7d 20 69 | 73 20 69 6d 70 6c 65 6d |lex{f} i|s implem|
|00005f70| 65 6e 74 65 64 20 69 6e | 20 61 20 77 61 79 20 73 |ented in| a way s|
|00005f80| 69 6d 69 6c 61 72 20 74 | 6f 20 74 68 61 74 0a 64 |imilar t|o that.d|
|00005f90| 65 73 63 72 69 62 65 64 | 20 62 79 20 53 74 72 6f |escribed| by Stro|
|00005fa0| 75 73 74 72 75 70 2e 20 | 49 6e 20 6b 65 65 70 69 |ustrup. |In keepi|
|00005fb0| 6e 67 20 77 69 74 68 20 | 6c 69 62 67 2b 2b 20 63 |ng with |libg++ c|
|00005fc0| 6f 6e 76 65 6e 74 69 6f | 6e 73 2c 0a 74 68 65 20 |onventio|ns,.the |
|00005fd0| 63 6c 61 73 73 20 69 73 | 20 6e 61 6d 65 64 20 7b |class is| named {|
|00005fe0| 66 43 6f 64 65 7d 43 6f | 6d 70 6c 65 78 7b 66 7d |fCode}Co|mplex{f}|
|00005ff0| 2c 20 6e 6f 74 20 7b 66 | 43 6f 64 65 7d 63 6f 6d |, not {f|Code}com|
|00006000| 70 6c 65 78 7b 66 7d 2e | 0a 43 6f 6d 70 6c 65 78 |plex{f}.|.Complex|
|00006010| 20 61 72 69 74 68 6d 65 | 74 69 63 20 61 6e 64 20 | arithme|tic and |
|00006020| 72 65 6c 61 74 69 6f 6e | 61 6c 20 6f 70 65 72 61 |relation|al opera|
|00006030| 74 6f 72 73 20 61 72 65 | 20 70 72 6f 76 69 64 65 |tors are| provide|
|00006040| 64 20 0a 28 7b 66 43 6f | 64 65 7d 2b 2c 20 2d 2c |d .({fCo|de}+, -,|
|00006050| 20 5c 2a 2c 20 5c 2f 2c | 20 2b 3d 2c 20 2d 3d 2c | \*, \/,| +=, -=,|
|00006060| 20 5c 2a 3d 2c 20 5c 2f | 3d 2c 20 3d 3d 2c 20 21 | \*=, \/|=, ==, !|
|00006070| 3d 7b 66 7d 29 2e 20 0a | 41 74 74 65 6d 70 74 65 |={f}). .|Attempte|
|00006080| 64 20 64 69 76 69 73 69 | 6f 6e 20 62 79 20 28 30 |d divisi|on by (0|
|00006090| 2c 20 30 29 20 74 72 69 | 67 67 65 72 73 20 61 6e |, 0) tri|ggers an|
|000060a0| 20 65 78 63 65 70 74 69 | 6f 6e 2e 0a 0a 43 6f 6d | excepti|on...Com|
|000060b0| 70 6c 65 78 20 6e 75 6d | 62 65 72 73 20 6d 61 79 |plex num|bers may|
|000060c0| 20 62 65 20 63 6f 6e 73 | 74 72 75 63 74 65 64 20 | be cons|tructed |
|000060d0| 61 6e 64 20 75 73 65 64 | 20 69 6e 20 74 68 65 20 |and used| in the |
|000060e0| 66 6f 6c 6c 6f 77 69 6e | 67 20 77 61 79 73 3a 0a |followin|g ways:.|
|000060f0| 0a 23 49 6e 64 65 6e 74 | 20 2b 34 0a 0a 23 49 6e |.#Indent| +4..#In|
|00006100| 64 65 6e 74 0a 7b 66 43 | 6f 64 65 7d 43 6f 6d 70 |dent.{fC|ode}Comp|
|00006110| 6c 65 78 20 78 3b 7b 66 | 7d 0a 23 49 6e 64 65 6e |lex x;{f|}.#Inden|
|00006120| 74 20 2b 34 0a 44 65 63 | 6c 61 72 65 73 20 61 6e |t +4.Dec|lares an|
|00006130| 20 75 6e 69 6e 69 74 69 | 61 6c 69 7a 65 64 20 43 | uniniti|alized C|
|00006140| 6f 6d 70 6c 65 78 2e 0a | 0a 23 49 6e 64 65 6e 74 |omplex..|.#Indent|
|00006150| 0a 7b 66 43 6f 64 65 7d | 43 6f 6d 70 6c 65 78 20 |.{fCode}|Complex |
|00006160| 78 20 3d 20 32 3b 20 43 | 6f 6d 70 6c 65 78 20 79 |x = 2; C|omplex y|
|00006170| 28 32 2e 30 29 3b 7b 66 | 7d 0a 23 49 6e 64 65 6e |(2.0);{f|}.#Inden|
|00006180| 74 20 2b 34 0a 53 65 74 | 20 78 20 61 6e 64 20 79 |t +4.Set| x and y|
|00006190| 20 74 6f 20 74 68 65 20 | 43 6f 6d 70 6c 65 78 20 | to the |Complex |
|000061a0| 76 61 6c 75 65 20 28 32 | 2e 30 2c 20 30 2e 30 29 |value (2|.0, 0.0)|
|000061b0| 3b 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |;..#Inde|nt.{fCod|
|000061c0| 65 7d 43 6f 6d 70 6c 65 | 78 20 78 28 32 2c 20 33 |e}Comple|x x(2, 3|
|000061d0| 29 3b 7b 66 7d 0a 23 49 | 6e 64 65 6e 74 20 2b 34 |);{f}.#I|ndent +4|
|000061e0| 0a 53 65 74 73 20 78 20 | 74 6f 20 74 68 65 20 43 |.Sets x |to the C|
|000061f0| 6f 6d 70 6c 65 78 20 76 | 61 6c 75 65 20 28 32 2c |omplex v|alue (2,|
|00006200| 20 33 29 3b 0a 0a 23 49 | 6e 64 65 6e 74 0a 7b 66 | 3);..#I|ndent.{f|
|00006210| 43 6f 64 65 7d 43 6f 6d | 70 6c 65 78 20 75 28 78 |Code}Com|plex u(x|
|00006220| 29 3b 20 43 6f 6d 70 6c | 65 78 20 76 20 3d 20 78 |); Compl|ex v = x|
|00006230| 3b 7b 66 7d 0a 23 49 6e | 64 65 6e 74 20 2b 34 0a |;{f}.#In|dent +4.|
|00006240| 53 65 74 20 75 20 61 6e | 64 20 76 20 74 6f 20 74 |Set u an|d v to t|
|00006250| 68 65 20 73 61 6d 65 20 | 76 61 6c 75 65 20 61 73 |he same |value as|
|00006260| 20 78 2e 0a 0a 23 49 6e | 64 65 6e 74 0a 7b 66 43 | x...#In|dent.{fC|
|00006270| 6f 64 65 7d 64 6f 75 62 | 6c 65 20 72 65 61 6c 28 |ode}doub|le real(|
|00006280| 43 6f 6d 70 6c 65 78 26 | 20 78 29 3b 7b 66 7d 0a |Complex&| x);{f}.|
|00006290| 23 49 6e 64 65 6e 74 20 | 2b 34 0a 72 65 74 75 72 |#Indent |+4.retur|
|000062a0| 6e 73 20 74 68 65 20 72 | 65 61 6c 20 70 61 72 74 |ns the r|eal part|
|000062b0| 20 6f 66 20 78 2e 0a 0a | 23 49 6e 64 65 6e 74 0a | of x...|#Indent.|
|000062c0| 7b 66 43 6f 64 65 7d 64 | 6f 75 62 6c 65 20 69 6d |{fCode}d|ouble im|
|000062d0| 61 67 28 43 6f 6d 70 6c | 65 78 26 20 78 29 3b 7b |ag(Compl|ex& x);{|
|000062e0| 66 7d 0a 23 49 6e 64 65 | 6e 74 20 2b 34 0a 72 65 |f}.#Inde|nt +4.re|
|000062f0| 74 75 72 6e 73 20 74 68 | 65 20 69 6d 61 67 69 6e |turns th|e imagin|
|00006300| 61 72 79 20 70 61 72 74 | 20 6f 66 20 78 2e 0a 0a |ary part| of x...|
|00006310| 23 49 6e 64 65 6e 74 0a | 7b 66 43 6f 64 65 7d 64 |#Indent.|{fCode}d|
|00006320| 6f 75 62 6c 65 20 61 62 | 73 28 43 6f 6d 70 6c 65 |ouble ab|s(Comple|
|00006330| 78 26 20 78 29 3b 7b 66 | 7d 0a 23 49 6e 64 65 6e |x& x);{f|}.#Inden|
|00006340| 74 20 2b 34 0a 72 65 74 | 75 72 6e 73 20 74 68 65 |t +4.ret|urns the|
|00006350| 20 6d 61 67 6e 69 74 75 | 64 65 20 6f 66 20 78 2e | magnitu|de of x.|
|00006360| 0a 0a 23 49 6e 64 65 6e | 74 0a 7b 66 43 6f 64 65 |..#Inden|t.{fCode|
|00006370| 7d 64 6f 75 62 6c 65 20 | 6e 6f 72 6d 28 43 6f 6d |}double |norm(Com|
|00006380| 70 6c 65 78 26 20 78 29 | 3b 7b 66 7d 0a 23 49 6e |plex& x)|;{f}.#In|
|00006390| 64 65 6e 74 20 2b 34 0a | 72 65 74 75 72 6e 73 20 |dent +4.|returns |
|000063a0| 74 68 65 20 73 71 75 61 | 72 65 20 6f 66 20 74 68 |the squa|re of th|
|000063b0| 65 20 6d 61 67 6e 69 74 | 75 64 65 20 6f 66 20 78 |e magnit|ude of x|
|000063c0| 2e 0a 0a 23 49 6e 64 65 | 6e 74 0a 7b 66 43 6f 64 |...#Inde|nt.{fCod|
|000063d0| 65 7d 64 6f 75 62 6c 65 | 20 61 72 67 28 43 6f 6d |e}double| arg(Com|
|000063e0| 70 6c 65 78 26 20 78 29 | 3b 7b 66 7d 0a 23 49 6e |plex& x)|;{f}.#In|
|000063f0| 64 65 6e 74 20 2b 34 0a | 72 65 74 75 72 6e 73 20 |dent +4.|returns |
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
