/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / UnionFind.cpp

< prev

next >

MacOS 8.1

Win98

DOS

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 0d 55 6e 69 6f 6e 46 | 69 6e 64 2e 63 70 70 00 |..UnionF|ind.cpp.|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 43 57 49 | 45 01 00 00 00 00 00 00 |.TEXTCWI|E.......|
|00000050| 00 00 00 00 00 07 7a 00 | 00 01 9a b3 b1 9e 33 b3 |......z.|......3.|
|00000060| b1 9e 33 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |..3.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 cf c0 00 00 |........|........|
|00000080| 23 69 6e 63 6c 75 64 65 | 20 22 55 6e 69 6f 6e 46 |#include| "UnionF|
|00000090| 69 6e 64 2e 68 22 0d 0d | 23 69 6e 63 6c 75 64 65 |ind.h"..|#include|
|000000a0| 20 22 58 4c 6f 6e 67 4c | 69 73 74 2e 68 22 0d 0d | "XLongL|ist.h"..|
|000000b0| 0d 55 6e 69 6f 6e 46 69 | 6e 64 3a 3a 55 6e 69 6f |.UnionFi|nd::Unio|
|000000c0| 6e 46 69 6e 64 28 29 20 | 7b 0d 09 6d 44 69 6d 53 |nFind() |{..mDimS|
|000000d0| 69 7a 65 20 3d 20 30 3b | 0d 09 6d 45 6c 65 6d 65 |ize = 0;|..mEleme|
|000000e0| 6e 74 73 20 3d 20 4e 55 | 4c 4c 3b 0d 7d 0d 0d 55 |nts = NU|LL;.}..U|
|000000f0| 6e 69 6f 6e 46 69 6e 64 | 3a 3a 7e 55 6e 69 6f 6e |nionFind|::~Union|
|00000100| 46 69 6e 64 28 29 20 7b | 0d 09 69 66 20 28 20 6d |Find() {|..if ( m|
|00000110| 45 6c 65 6d 65 6e 74 73 | 20 29 0d 09 09 64 65 6c |Elements| )...del|
|00000120| 65 74 65 20 6d 45 6c 65 | 6d 65 6e 74 73 3b 0d 7d |ete mEle|ments;.}|
|00000130| 0d 0d 0d 6c 6f 6e 67 20 | 55 6e 69 6f 6e 46 69 6e |...long |UnionFin|
|00000140| 64 3a 3a 46 69 6e 64 28 | 20 6c 6f 6e 67 20 69 6e |d::Find(| long in|
|00000150| 41 20 29 20 7b 0d 09 6c | 6f 6e 67 20 69 2c 20 6e |A ) {..l|ong i, n|
|00000160| 65 77 53 69 7a 65 2c 20 | 6e 65 78 74 3b 0d 09 75 |ewSize, |next;..u|
|00000170| 6e 73 69 67 6e 65 64 20 | 73 68 6f 72 74 2a 20 6e |nsigned |short* n|
|00000180| 65 77 6d 65 6d 3b 0d 0d | 09 2f 2f 20 45 78 70 61 |ewmem;..|.// Expa|
|00000190| 6e 64 20 6f 75 72 20 6c | 69 73 74 20 6f 66 20 65 |nd our l|ist of e|
|000001a0| 6c 65 6d 65 6e 74 73 20 | 69 66 20 77 65 20 6e 65 |lements |if we ne|
|000001b0| 65 64 20 74 6f 2e 2e 2e | 09 09 0d 09 69 66 20 28 |ed to...|....if (|
|000001c0| 20 69 6e 41 20 3e 3d 20 | 6d 44 69 6d 53 69 7a 65 | inA >= |mDimSize|
|000001d0| 20 29 20 7b 0d 0d 09 09 | 6e 65 77 53 69 7a 65 20 | ) {....|newSize |
|000001e0| 3d 20 69 6e 41 20 2b 20 | 32 30 3b 0d 09 09 6e 65 |= inA + |20;...ne|
|000001f0| 77 6d 65 6d 20 3d 20 6e | 65 77 20 75 6e 73 69 67 |wmem = n|ew unsig|
|00000200| 6e 65 64 20 73 68 6f 72 | 74 5b 20 6e 65 77 53 69 |ned shor|t[ newSi|
|00000210| 7a 65 20 2b 20 31 20 5d | 3b 0d 09 09 66 6f 72 20 |ze + 1 ]|;...for |
|00000220| 28 20 69 20 3d 20 30 3b | 20 69 20 3c 20 6d 44 69 |( i = 0;| i < mDi|
|00000230| 6d 53 69 7a 65 3b 20 69 | 2b 2b 20 29 0d 09 09 09 |mSize; i|++ )....|
|00000240| 6e 65 77 6d 65 6d 5b 20 | 69 20 5d 20 3d 20 6d 45 |newmem[ |i ] = mE|
|00000250| 6c 65 6d 65 6e 74 73 5b | 20 69 20 5d 3b 0d 09 09 |lements[| i ];...|
|00000260| 64 65 6c 65 74 65 20 6d | 45 6c 65 6d 65 6e 74 73 |delete m|Elements|
|00000270| 3b 0d 09 09 66 6f 72 20 | 28 20 69 20 3d 20 6d 44 |;...for |( i = mD|
|00000280| 69 6d 53 69 7a 65 3b 20 | 69 20 3c 20 6e 65 77 53 |imSize; |i < newS|
|00000290| 69 7a 65 3b 20 69 2b 2b | 20 29 0d 09 09 09 6e 65 |ize; i++| )....ne|
|000002a0| 77 6d 65 6d 5b 20 69 20 | 5d 20 3d 20 69 3b 0d 09 |wmem[ i |] = i;..|
|000002b0| 09 6d 44 69 6d 53 69 7a | 65 20 3d 20 6e 65 77 53 |.mDimSiz|e = newS|
|000002c0| 69 7a 65 3b 0d 09 09 6d | 45 6c 65 6d 65 6e 74 73 |ize;...m|Elements|
|000002d0| 20 3d 20 6e 65 77 6d 65 | 6d 3b 0d 09 7d 0d 0d 0d | = newme|m;..}...|
|000002e0| 0d 09 2f 2f 20 46 69 6e | 64 20 77 2f 20 70 61 74 |..// Fin|d w/ pat|
|000002f0| 68 20 63 6f 6d 70 72 65 | 73 73 69 6f 6e 0d 09 77 |h compre|ssion..w|
|00000300| 68 69 6c 65 20 28 20 6d | 45 6c 65 6d 65 6e 74 73 |hile ( m|Elements|
|00000310| 5b 20 69 6e 41 20 5d 20 | 21 3d 20 69 6e 41 20 29 |[ inA ] |!= inA )|
|00000320| 20 7b 0d 09 09 6e 65 78 | 74 20 3d 20 6d 45 6c 65 | {...nex|t = mEle|
|00000330| 6d 65 6e 74 73 5b 20 69 | 6e 41 20 5d 3b 0d 09 09 |ments[ i|nA ];...|
|00000340| 69 66 20 28 20 6d 45 6c | 65 6d 65 6e 74 73 5b 20 |if ( mEl|ements[ |
|00000350| 6e 65 78 74 20 5d 20 3d | 3d 20 6e 65 78 74 20 29 |next ] =|= next )|
|00000360| 0d 09 09 09 72 65 74 75 | 72 6e 20 6e 65 78 74 3b |....retu|rn next;|
|00000370| 0d 09 09 65 6c 73 65 20 | 7b 0d 09 09 09 69 6e 41 |...else |{....inA|
|00000380| 20 3d 20 6d 45 6c 65 6d | 65 6e 74 73 5b 20 69 6e | = mElem|ents[ in|
|00000390| 41 20 5d 20 3d 20 6d 45 | 6c 65 6d 65 6e 74 73 5b |A ] = mE|lements[|
|000003a0| 20 6e 65 78 74 20 5d 3b | 0d 09 09 7d 0d 09 7d 0d | next ];|...}..}.|
|000003b0| 09 0d 09 0d 09 72 65 74 | 75 72 6e 20 69 6e 41 3b |.....ret|urn inA;|
|000003c0| 0d 7d 0d 0d 0d 6c 6f 6e | 67 20 55 6e 69 6f 6e 46 |.}...lon|g UnionF|
|000003d0| 69 6e 64 3a 3a 4c 61 72 | 67 65 73 74 53 65 74 28 |ind::Lar|gestSet(|
|000003e0| 20 6c 6f 6e 67 2a 20 6f | 75 74 53 69 7a 65 20 29 | long* o|utSize )|
|000003f0| 20 7b 0d 09 75 6e 73 69 | 67 6e 65 64 20 73 68 6f | {..unsi|gned sho|
|00000400| 72 74 2a 20 74 61 6c 6c | 79 20 3d 20 6e 65 77 20 |rt* tall|y = new |
|00000410| 75 6e 73 69 67 6e 65 64 | 20 73 68 6f 72 74 5b 20 |unsigned| short[ |
|00000420| 6d 44 69 6d 53 69 7a 65 | 20 5d 3b 0d 09 6c 6f 6e |mDimSize| ];..lon|
|00000430| 67 20 6d 61 78 2c 20 73 | 65 74 2c 20 69 3b 0d 09 |g max, s|et, i;..|
|00000440| 0d 09 0d 09 66 6f 72 20 | 28 20 69 20 3d 20 30 3b |....for |( i = 0;|
|00000450| 20 69 20 3c 20 6d 44 69 | 6d 53 69 7a 65 3b 20 69 | i < mDi|mSize; i|
|00000460| 2b 2b 20 29 0d 09 09 74 | 61 6c 6c 79 5b 20 69 20 |++ )...t|ally[ i |
|00000470| 5d 20 3d 20 30 3b 0d 09 | 09 0d 09 66 6f 72 20 28 |] = 0;..|...for (|
|00000480| 20 69 20 3d 20 30 3b 20 | 69 20 3c 20 6d 44 69 6d | i = 0; |i < mDim|
|00000490| 53 69 7a 65 3b 20 69 2b | 2b 20 29 0d 09 09 74 61 |Size; i+|+ )...ta|
|000004a0| 6c 6c 79 5b 20 46 69 6e | 64 28 20 69 20 29 20 5d |lly[ Fin|d( i ) ]|
|000004b0| 2b 2b 3b 0d 09 09 0d 09 | 6d 61 78 20 3d 20 30 3b |++;.....|max = 0;|
|000004c0| 0d 09 73 65 74 20 3d 20 | 30 3b 0d 09 66 6f 72 20 |..set = |0;..for |
|000004d0| 28 20 69 20 3d 20 30 3b | 20 69 20 3c 20 6d 44 69 |( i = 0;| i < mDi|
|000004e0| 6d 53 69 7a 65 3b 20 69 | 2b 2b 20 29 20 7b 0d 09 |mSize; i|++ ) {..|
|000004f0| 09 69 66 20 28 20 74 61 | 6c 6c 79 5b 20 69 20 5d |.if ( ta|lly[ i ]|
|00000500| 20 3e 20 6d 61 78 20 29 | 20 7b 0d 09 09 09 6d 61 | > max )| {....ma|
|00000510| 78 20 3d 20 74 61 6c 6c | 79 5b 20 69 20 5d 3b 0d |x = tall|y[ i ];.|
|00000520| 09 09 09 73 65 74 20 3d | 20 69 3b 0d 09 09 7d 0d |...set =| i;...}.|
|00000530| 09 7d 0d 09 0d 09 64 65 | 6c 65 74 65 20 5b 5d 74 |.}....de|lete []t|
|00000540| 61 6c 6c 79 3b 0d 09 0d | 09 69 66 20 28 20 6f 75 |ally;...|.if ( ou|
|00000550| 74 53 69 7a 65 20 29 0d | 09 09 2a 6f 75 74 53 69 |tSize ).|..*outSi|
|00000560| 7a 65 20 3d 20 6d 61 78 | 3b 0d 09 09 0d 09 72 65 |ze = max|;.....re|
|00000570| 74 75 72 6e 20 73 65 74 | 3b 0d 7d 0d 0d 0d 76 6f |turn set|;.}...vo|
|00000580| 69 64 20 55 6e 69 6f 6e | 46 69 6e 64 3a 3a 45 6e |id Union|Find::En|
|00000590| 75 6d 65 72 61 74 65 53 | 65 74 28 20 6c 6f 6e 67 |umerateS|et( long|
|000005a0| 20 69 6e 53 65 74 49 44 | 2c 20 58 4c 6f 6e 67 4c | inSetID|, XLongL|
|000005b0| 69 73 74 26 20 6f 75 74 | 53 65 74 20 29 20 7b 0d |ist& out|Set ) {.|
|000005c0| 09 6c 6f 6e 67 20 69 3b | 0d 09 0d 09 6f 75 74 53 |.long i;|....outS|
|000005d0| 65 74 2e 52 65 6d 6f 76 | 65 41 6c 6c 28 29 3b 0d |et.Remov|eAll();.|
|000005e0| 09 66 6f 72 20 28 20 69 | 20 3d 20 30 3b 20 69 20 |.for ( i| = 0; i |
|000005f0| 3c 20 6d 44 69 6d 53 69 | 7a 65 3b 20 69 2b 2b 20 |< mDimSi|ze; i++ |
|00000600| 29 20 7b 0d 09 09 69 66 | 20 28 20 46 69 6e 64 28 |) {...if| ( Find(|
|00000610| 20 69 20 29 20 3d 3d 20 | 69 6e 53 65 74 49 44 20 | i ) == |inSetID |
|00000620| 29 0d 09 09 09 6f 75 74 | 53 65 74 2e 41 64 64 28 |)....out|Set.Add(|
|00000630| 20 69 20 29 3b 0d 09 7d | 0d 7d 0d 0d 0d 76 6f 69 | i );..}|.}...voi|
|00000640| 64 20 55 6e 69 6f 6e 46 | 69 6e 64 3a 3a 55 6e 69 |d UnionF|ind::Uni|
|00000650| 6f 6e 28 20 6c 6f 6e 67 | 20 69 6e 41 2c 20 6c 6f |on( long| inA, lo|
|00000660| 6e 67 20 69 6e 42 20 29 | 20 7b 0d 09 0d 09 2f 2f |ng inB )| {....//|
|00000670| 20 44 6f 20 74 68 65 20 | 75 6e 69 6f 6e 0d 09 6d | Do the |union..m|
|00000680| 45 6c 65 6d 65 6e 74 73 | 5b 20 46 69 6e 64 28 20 |Elements|[ Find( |
|00000690| 69 6e 42 20 29 20 5d 20 | 3d 20 46 69 6e 64 28 20 |inB ) ] |= Find( |
|000006a0| 69 6e 41 20 29 3b 0d 7d | 0d 0d 0d 0d 0d 0d 0d 6c |inA );.}|.......l|
|000006b0| 6f 6e 67 20 55 6e 69 6f | 6e 46 69 6e 64 3a 3a 4e |ong Unio|nFind::N|
|000006c0| 75 6d 53 65 74 73 28 29 | 20 7b 0d 09 6c 6f 6e 67 |umSets()| {..long|
|000006d0| 20 69 2c 20 6e 75 6d 53 | 65 74 73 20 3d 20 30 3b | i, numS|ets = 0;|
|000006e0| 0d 09 0d 09 66 6f 72 20 | 28 20 69 20 3d 20 30 3b |....for |( i = 0;|
|000006f0| 20 69 20 3c 20 6d 44 69 | 6d 53 69 7a 65 3b 20 69 | i < mDi|mSize; i|
|00000700| 2b 2b 20 29 20 7b 0d 09 | 09 69 66 20 28 20 6d 45 |++ ) {..|.if ( mE|
|00000710| 6c 65 6d 65 6e 74 73 5b | 20 69 20 5d 20 3d 3d 20 |lements[| i ] == |
|00000720| 69 20 29 0d 09 09 09 6e | 75 6d 53 65 74 73 2b 2b |i )....n|umSets++|
|00000730| 3b 0d 09 7d 0d 09 0d 09 | 72 65 74 75 72 6e 20 6e |;..}....|return n|
|00000740| 75 6d 53 65 74 73 3b 0d | 7d 0d 0d 0d 0d 76 6f 69 |umSets;.|}....voi|
|00000750| 64 20 55 6e 69 6f 6e 46 | 69 6e 64 3a 3a 47 65 74 |d UnionF|ind::Get|
|00000760| 53 65 74 73 28 20 58 4c | 6f 6e 67 4c 69 73 74 26 |Sets( XL|ongList&|
|00000770| 20 6f 75 74 53 65 74 73 | 20 29 20 7b 0d 09 6c 6f | outSets| ) {..lo|
|00000780| 6e 67 20 69 3b 0d 09 0d | 09 6f 75 74 53 65 74 73 |ng i;...|.outSets|
|00000790| 2e 52 65 6d 6f 76 65 41 | 6c 6c 28 29 3b 0d 09 66 |.RemoveA|ll();..f|
|000007a0| 6f 72 20 28 20 69 20 3d | 20 30 3b 20 69 20 3c 20 |or ( i =| 0; i < |
|000007b0| 6d 44 69 6d 53 69 7a 65 | 3b 20 69 2b 2b 20 29 20 |mDimSize|; i++ ) |
|000007c0| 7b 0d 09 09 69 66 20 28 | 20 6d 45 6c 65 6d 65 6e |{...if (| mElemen|
|000007d0| 74 73 5b 20 69 20 5d 20 | 3d 3d 20 69 20 29 0d 09 |ts[ i ] |== i )..|
|000007e0| 09 09 6f 75 74 53 65 74 | 73 2e 41 64 64 28 20 69 |..outSet|s.Add( i|
|000007f0| 20 29 3b 0d 09 7d 0d 7d | 0d 0d 00 00 00 00 00 00 | );..}.}|........|
|00000800| 00 00 01 00 00 00 01 54 | 00 00 00 54 00 00 00 46 |.......T|...T...F|
|00000810| 9d fb 21 ca 8c 82 89 64 | 7c 41 6a 99 79 51 64 6e |..!....d||Aj.yQdn|
|00000820| 7d f3 25 b1 11 70 1b cd | 60 a0 cc c4 f4 96 f2 44 |}.%..p..|`......D|
|00000830| 67 e9 4a f7 d8 40 d9 51 | 9b ba 83 48 8e 11 0e 7b |g.J..@.Q|...H...{|
|00000840| 80 35 0e 52 86 6a 9a 14 | ff 80 18 4f e4 3b b8 ee |.5.R.j..|...O.;..|
|00000850| a6 81 30 b1 92 02 30 93 | d4 d9 a9 7a cd 79 81 1d |..0...0.|...z.y..|
|00000860| 81 7c ff ef b6 a0 c3 54 | f3 d7 d7 ea e4 c4 3f 77 |.|.....T|......?w|
|00000870| 86 62 16 42 56 4d 63 e7 | df a7 b4 86 af bb 78 f8 |.b.BVMc.|......x.|
|00000880| c5 a9 fa 7d 65 5c 10 d8 | 1a ea fa 9b ed 8c 49 f5 |...}e\..|......I.|
|00000890| fe 8f b1 64 74 60 49 06 | cc 76 93 f6 0f bd 82 12 |...dt`I.|.v......|
|000008a0| f1 e0 87 75 59 60 1b 7d | 83 4d 74 c3 80 ed 67 61 |...uY`.}|.Mt...ga|
|000008b0| 7d a9 99 00 eb d8 c1 13 | 48 5e 38 6c 06 1d 30 b5 |}.......|H^8l..0.|
|000008c0| 7f 1a 43 4e 5c e4 e7 e5 | 6c 21 0c 02 82 09 64 37 |..CN\...|l!....d7|
|000008d0| a2 af 16 27 01 b8 ed d4 | 54 72 16 d4 1c d1 6b 31 |...'....|Tr....k1|
|000008e0| 8f 08 5b 09 cb b6 df 31 | 1b 0a 78 7b a5 64 9a ff |..[....1|..x{.d..|
|000008f0| a9 6d d6 d5 02 11 e2 06 | 56 56 6d 7f 0f 54 cf 1b |.m......|VVm..T..|
|00000900| 00 00 00 48 00 09 4d 6f | 6e 61 63 6f 00 00 00 00 |...H..Mo|naco....|
|00000910| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000920| 00 00 00 00 00 00 00 03 | 00 04 00 3e 00 0d 02 43 |........|...>...C|
|00000930| 02 63 00 3e 00 0d 02 43 | 02 63 b3 7f e1 91 00 00 |.c.>...C|.c......|
|00000940| 05 9f 00 00 05 9f 00 00 | 02 fa 01 00 00 00 00 04 |........|........|
|00000950| 00 01 00 01 00 00 01 00 | 00 00 01 54 00 00 00 54 |........|...T...T|
|00000960| 00 00 00 46 04 f9 76 98 | 16 68 00 00 00 1c 00 46 |...F..v.|.h.....F|
|00000970| 00 01 4d 50 53 52 00 00 | 00 12 4d 57 42 42 00 00 |..MPSR..|..MWBB..|
|00000980| 00 1e 03 ed ff ff 00 00 | 00 00 00 00 00 00 03 f0 |........|........|
|00000990| ff ff 00 00 00 4c 00 00 | 00 00 00 00 00 00 00 00 |.....L..|........|
|000009a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+