Thu, 19 Mar 2009 09:13:24 -0700
Merge
duke@435 | 1 | /* |
duke@435 | 2 | * Copyright 1997 Sun Microsystems, Inc. All Rights Reserved. |
duke@435 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@435 | 4 | * |
duke@435 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@435 | 6 | * under the terms of the GNU General Public License version 2 only, as |
duke@435 | 7 | * published by the Free Software Foundation. |
duke@435 | 8 | * |
duke@435 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@435 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@435 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@435 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@435 | 13 | * accompanied this code). |
duke@435 | 14 | * |
duke@435 | 15 | * You should have received a copy of the GNU General Public License version |
duke@435 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@435 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@435 | 18 | * |
duke@435 | 19 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
duke@435 | 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
duke@435 | 21 | * have any questions. |
duke@435 | 22 | * |
duke@435 | 23 | */ |
duke@435 | 24 | |
duke@435 | 25 | #ifndef _SET_ |
duke@435 | 26 | #define _SET_ |
duke@435 | 27 | // Sets - An Abstract Data Type |
duke@435 | 28 | |
duke@435 | 29 | // Should not manually include these in AVM framework. %%%%% - Ungar |
duke@435 | 30 | // #ifndef _PORT_ |
duke@435 | 31 | // #include "port.hpp" |
duke@435 | 32 | // #endif // _PORT_ |
duke@435 | 33 | //INTERFACE |
duke@435 | 34 | |
duke@435 | 35 | class SparseSet; |
duke@435 | 36 | class VectorSet; |
duke@435 | 37 | class ListSet; |
duke@435 | 38 | class CoSet; |
duke@435 | 39 | |
duke@435 | 40 | class ostream; |
duke@435 | 41 | class SetI_; |
duke@435 | 42 | |
duke@435 | 43 | // These sets can grow or shrink, based on the initial size and the largest |
duke@435 | 44 | // element currently in them. Basically, they allow a bunch of bits to be |
duke@435 | 45 | // grouped together, tested, set & cleared, intersected, etc. The basic |
duke@435 | 46 | // Set class is an abstract class, and cannot be constructed. Instead, |
duke@435 | 47 | // one of VectorSet, SparseSet, or ListSet is created. Each variation has |
duke@435 | 48 | // different asymptotic running times for different operations, and different |
duke@435 | 49 | // constants of proportionality as well. |
duke@435 | 50 | // {n = number of elements, N = largest element} |
duke@435 | 51 | |
duke@435 | 52 | // VectorSet SparseSet ListSet |
duke@435 | 53 | // Create O(N) O(1) O(1) |
duke@435 | 54 | // Clear O(N) O(1) O(1) |
duke@435 | 55 | // Insert O(1) O(1) O(log n) |
duke@435 | 56 | // Delete O(1) O(1) O(log n) |
duke@435 | 57 | // Member O(1) O(1) O(log n) |
duke@435 | 58 | // Size O(N) O(1) O(1) |
duke@435 | 59 | // Copy O(N) O(n) O(n) |
duke@435 | 60 | // Union O(N) O(n) O(n log n) |
duke@435 | 61 | // Intersect O(N) O(n) O(n log n) |
duke@435 | 62 | // Difference O(N) O(n) O(n log n) |
duke@435 | 63 | // Equal O(N) O(n) O(n log n) |
duke@435 | 64 | // ChooseMember O(N) O(1) O(1) |
duke@435 | 65 | // Sort O(1) O(n log n) O(1) |
duke@435 | 66 | // Forall O(N) O(n) O(n) |
duke@435 | 67 | // Complement O(1) O(1) O(1) |
duke@435 | 68 | |
duke@435 | 69 | // TIME: N/32 n 8*n Accesses |
duke@435 | 70 | // SPACE: N/8 4*N+4*n 8*n Bytes |
duke@435 | 71 | |
duke@435 | 72 | // Create: Make an empty set |
duke@435 | 73 | // Clear: Remove all the elements of a Set |
duke@435 | 74 | // Insert: Insert an element into a Set; duplicates are ignored |
duke@435 | 75 | // Delete: Removes an element from a Set |
duke@435 | 76 | // Member: Tests for membership in a Set |
duke@435 | 77 | // Size: Returns the number of members of a Set |
duke@435 | 78 | // Copy: Copy or assign one Set to another |
duke@435 | 79 | // Union: Union 2 sets together |
duke@435 | 80 | // Intersect: Intersect 2 sets together |
duke@435 | 81 | // Difference: Compute A & !B; remove from set A those elements in set B |
duke@435 | 82 | // Equal: Test for equality between 2 sets |
duke@435 | 83 | // ChooseMember Pick a random member |
duke@435 | 84 | // Sort: If no other operation changes the set membership, a following |
duke@435 | 85 | // Forall will iterate the members in ascending order. |
duke@435 | 86 | // Forall: Iterate over the elements of a Set. Operations that modify |
duke@435 | 87 | // the set membership during iteration work, but the iterator may |
duke@435 | 88 | // skip any member or duplicate any member. |
duke@435 | 89 | // Complement: Only supported in the Co-Set variations. It adds a small |
duke@435 | 90 | // constant-time test to every Set operation. |
duke@435 | 91 | // |
duke@435 | 92 | // PERFORMANCE ISSUES: |
duke@435 | 93 | // If you "cast away" the specific set variation you are using, and then do |
duke@435 | 94 | // operations on the basic "Set" object you will pay a virtual function call |
duke@435 | 95 | // to get back the specific set variation. On the other hand, using the |
duke@435 | 96 | // generic Set means you can change underlying implementations by just |
duke@435 | 97 | // changing the initial declaration. Examples: |
duke@435 | 98 | // void foo(VectorSet vs1, VectorSet vs2) { vs1 |= vs2; } |
duke@435 | 99 | // "foo" must be called with a VectorSet. The vector set union operation |
duke@435 | 100 | // is called directly. |
duke@435 | 101 | // void foo(Set vs1, Set vs2) { vs1 |= vs2; } |
duke@435 | 102 | // "foo" may be called with *any* kind of sets; suppose it is called with |
duke@435 | 103 | // VectorSets. Two virtual function calls are used to figure out the that vs1 |
duke@435 | 104 | // and vs2 are VectorSets. In addition, if vs2 is not a VectorSet then a |
duke@435 | 105 | // temporary VectorSet copy of vs2 will be made before the union proceeds. |
duke@435 | 106 | // |
duke@435 | 107 | // VectorSets have a small constant. Time and space are proportional to the |
duke@435 | 108 | // largest element. Fine for dense sets and largest element < 10,000. |
duke@435 | 109 | // SparseSets have a medium constant. Time is proportional to the number of |
duke@435 | 110 | // elements, space is proportional to the largest element. |
duke@435 | 111 | // Fine (but big) with the largest element < 100,000. |
duke@435 | 112 | // ListSets have a big constant. Time *and space* are proportional to the |
duke@435 | 113 | // number of elements. They work well for a few elements of *any* size |
duke@435 | 114 | // (i.e. sets of pointers)! |
duke@435 | 115 | |
duke@435 | 116 | //------------------------------Set-------------------------------------------- |
duke@435 | 117 | class Set : public ResourceObj { |
duke@435 | 118 | public: |
duke@435 | 119 | |
duke@435 | 120 | // Creates a new, empty set. |
duke@435 | 121 | // DO NOT CONSTRUCT A Set. THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY |
duke@435 | 122 | Set(Arena *arena) : _set_arena(arena) {}; |
duke@435 | 123 | |
duke@435 | 124 | // Creates a new set from an existing set |
duke@435 | 125 | // DO NOT CONSTRUCT A Set. THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY |
duke@435 | 126 | Set(const Set &) {}; |
duke@435 | 127 | |
duke@435 | 128 | // Set assignment; deep-copy guts |
duke@435 | 129 | virtual Set &operator =(const Set &s)=0; |
duke@435 | 130 | virtual Set &clone(void) const=0; |
duke@435 | 131 | |
duke@435 | 132 | // Virtual destructor |
duke@435 | 133 | virtual ~Set() {}; |
duke@435 | 134 | |
duke@435 | 135 | // Add member to set |
duke@435 | 136 | virtual Set &operator <<=(uint elem)=0; |
duke@435 | 137 | // virtual Set operator << (uint elem); |
duke@435 | 138 | |
duke@435 | 139 | // Delete member from set |
duke@435 | 140 | virtual Set &operator >>=(uint elem)=0; |
duke@435 | 141 | // virtual Set operator >> (uint elem); |
duke@435 | 142 | |
duke@435 | 143 | // Membership test. Result is Zero (absent)/ Non-Zero (present) |
duke@435 | 144 | virtual int operator [](uint elem) const=0; |
duke@435 | 145 | |
duke@435 | 146 | // Intersect sets |
duke@435 | 147 | virtual Set &operator &=(const Set &s)=0; |
duke@435 | 148 | // virtual Set operator & (const Set &s) const; |
duke@435 | 149 | |
duke@435 | 150 | // Union sets |
duke@435 | 151 | virtual Set &operator |=(const Set &s)=0; |
duke@435 | 152 | // virtual Set operator | (const Set &s) const; |
duke@435 | 153 | |
duke@435 | 154 | // Difference sets |
duke@435 | 155 | virtual Set &operator -=(const Set &s)=0; |
duke@435 | 156 | // virtual Set operator - (const Set &s) const; |
duke@435 | 157 | |
duke@435 | 158 | // Tests for equality. Result is Zero (false)/ Non-Zero (true) |
duke@435 | 159 | virtual int operator ==(const Set &s) const=0; |
duke@435 | 160 | int operator !=(const Set &s) const { return !(*this == s); } |
duke@435 | 161 | virtual int disjoint(const Set &s) const=0; |
duke@435 | 162 | |
duke@435 | 163 | // Tests for strict subset. Result is Zero (false)/ Non-Zero (true) |
duke@435 | 164 | virtual int operator < (const Set &s) const=0; |
duke@435 | 165 | int operator > (const Set &s) const { return s < *this; } |
duke@435 | 166 | |
duke@435 | 167 | // Tests for subset. Result is Zero (false)/ Non-Zero (true) |
duke@435 | 168 | virtual int operator <=(const Set &s) const=0; |
duke@435 | 169 | int operator >=(const Set &s) const { return s <= *this; } |
duke@435 | 170 | |
duke@435 | 171 | // Return any member of the Set. Undefined if the Set is empty. |
duke@435 | 172 | virtual uint getelem(void) const=0; |
duke@435 | 173 | |
duke@435 | 174 | // Clear all the elements in the Set |
duke@435 | 175 | virtual void Clear(void)=0; |
duke@435 | 176 | |
duke@435 | 177 | // Return the number of members in the Set |
duke@435 | 178 | virtual uint Size(void) const=0; |
duke@435 | 179 | |
duke@435 | 180 | // If an iterator follows a "Sort()" without any Set-modifying operations |
duke@435 | 181 | // inbetween then the iterator will visit the elements in ascending order. |
duke@435 | 182 | virtual void Sort(void)=0; |
duke@435 | 183 | |
duke@435 | 184 | // Convert a set to printable string in an allocated buffer. |
duke@435 | 185 | // The caller must deallocate the string. |
duke@435 | 186 | virtual char *setstr(void) const; |
duke@435 | 187 | |
duke@435 | 188 | // Print the Set on "stdout". Can be conveniently called in the debugger |
duke@435 | 189 | void print() const; |
duke@435 | 190 | |
duke@435 | 191 | // Parse text from the string into the Set. Return length parsed. |
duke@435 | 192 | virtual int parse(const char *s); |
duke@435 | 193 | |
duke@435 | 194 | // Convert a generic Set to a specific Set |
duke@435 | 195 | /* Removed for MCC BUG |
duke@435 | 196 | virtual operator const SparseSet* (void) const; |
duke@435 | 197 | virtual operator const VectorSet* (void) const; |
duke@435 | 198 | virtual operator const ListSet * (void) const; |
duke@435 | 199 | virtual operator const CoSet * (void) const; */ |
duke@435 | 200 | virtual const SparseSet *asSparseSet(void) const; |
duke@435 | 201 | virtual const VectorSet *asVectorSet(void) const; |
duke@435 | 202 | virtual const ListSet *asListSet (void) const; |
duke@435 | 203 | virtual const CoSet *asCoSet (void) const; |
duke@435 | 204 | |
duke@435 | 205 | // Hash the set. Sets of different types but identical elements will NOT |
duke@435 | 206 | // hash the same. Same set type, same elements WILL hash the same. |
duke@435 | 207 | virtual int hash() const = 0; |
duke@435 | 208 | |
duke@435 | 209 | protected: |
duke@435 | 210 | friend class SetI; |
duke@435 | 211 | friend class CoSet; |
duke@435 | 212 | virtual class SetI_ *iterate(uint&) const=0; |
duke@435 | 213 | |
duke@435 | 214 | // Need storeage for the set |
duke@435 | 215 | Arena *_set_arena; |
duke@435 | 216 | }; |
duke@435 | 217 | typedef Set&((*Set_Constructor)(Arena *arena)); |
duke@435 | 218 | extern Set &ListSet_Construct(Arena *arena); |
duke@435 | 219 | extern Set &VectorSet_Construct(Arena *arena); |
duke@435 | 220 | extern Set &SparseSet_Construct(Arena *arena); |
duke@435 | 221 | |
duke@435 | 222 | //------------------------------Iteration-------------------------------------- |
duke@435 | 223 | // Loop thru all elements of the set, setting "elem" to the element numbers |
duke@435 | 224 | // in random order. Inserted or deleted elements during this operation may |
duke@435 | 225 | // or may not be iterated over; untouched elements will be affected once. |
duke@435 | 226 | |
duke@435 | 227 | // Usage: for( SetI i(s); i.test(); i++ ) { body = i.elem; } ...OR... |
duke@435 | 228 | // for( i.reset(s); i.test(); i++ ) { body = i.elem; } |
duke@435 | 229 | |
duke@435 | 230 | class SetI_ : public ResourceObj { |
duke@435 | 231 | protected: |
duke@435 | 232 | friend class SetI; |
duke@435 | 233 | virtual ~SetI_(); |
duke@435 | 234 | virtual uint next(void)=0; |
duke@435 | 235 | virtual int test(void)=0; |
duke@435 | 236 | }; |
duke@435 | 237 | |
duke@435 | 238 | class SetI { |
duke@435 | 239 | protected: |
duke@435 | 240 | SetI_ *impl; |
duke@435 | 241 | public: |
duke@435 | 242 | uint elem; // The publically accessible element |
duke@435 | 243 | |
duke@435 | 244 | SetI( const Set *s ) { impl = s->iterate(elem); } |
duke@435 | 245 | ~SetI() { delete impl; } |
duke@435 | 246 | void reset( const Set *s ) { delete impl; impl = s->iterate(elem); } |
duke@435 | 247 | void operator ++(void) { elem = impl->next(); } |
duke@435 | 248 | int test(void) { return impl->test(); } |
duke@435 | 249 | }; |
duke@435 | 250 | |
duke@435 | 251 | #endif // _SET_ |