|
0
|
1 /*
|
|
|
2 * Copyright 1997 Sun Microsystems, Inc. All Rights Reserved.
|
|
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
|
4 *
|
|
|
5 * This code is free software; you can redistribute it and/or modify it
|
|
|
6 * under the terms of the GNU General Public License version 2 only, as
|
|
|
7 * published by the Free Software Foundation.
|
|
|
8 *
|
|
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT
|
|
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
12 * version 2 for more details (a copy is included in the LICENSE file that
|
|
|
13 * accompanied this code).
|
|
|
14 *
|
|
|
15 * You should have received a copy of the GNU General Public License version
|
|
|
16 * 2 along with this work; if not, write to the Free Software Foundation,
|
|
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
|
18 *
|
|
|
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
|
21 * have any questions.
|
|
|
22 *
|
|
|
23 */
|
|
|
24
|
|
|
25 #ifndef _VECTOR_SET_
|
|
|
26 #define _VECTOR_SET_
|
|
|
27 // Vector Sets - An Abstract Data Type
|
|
|
28 //INTERFACE
|
|
|
29
|
|
|
30 // These sets can grow or shrink, based on the initial size and the largest
|
|
|
31 // element currently in them. Slow and bulky for sparse sets, these sets
|
|
|
32 // are super for dense sets. They are fast and compact when dense.
|
|
|
33
|
|
|
34 // TIME:
|
|
|
35 // O(1) - Insert, Delete, Member, Sort
|
|
|
36 // O(max_element) - Create, Clear, Size, Copy, Union, Intersect, Difference,
|
|
|
37 // Equal, ChooseMember, Forall
|
|
|
38
|
|
|
39 // SPACE: (max_element)/(8*sizeof(int))
|
|
|
40
|
|
|
41
|
|
|
42 //------------------------------VectorSet--------------------------------------
|
|
|
43 class VectorSet : public Set {
|
|
|
44 friend class VectorSetI; // Friendly iterator class
|
|
|
45 protected:
|
|
|
46 uint size; // Size of data IN LONGWORDS (32bits)
|
|
|
47 uint32 *data; // The data, bit packed
|
|
|
48
|
|
|
49 void slamin( const VectorSet& s ); // Initialize one set with another
|
|
|
50 int compare(const VectorSet &s) const; // Compare set contents
|
|
|
51 void grow(uint newsize); // Grow vector to required bitsize
|
|
|
52
|
|
|
53 public:
|
|
|
54 VectorSet(Arena *arena); // Creates a new, empty set.
|
|
|
55 VectorSet(const VectorSet &s) : Set(s._set_arena) {slamin(s);} // Set clone; deep-copy guts
|
|
|
56 Set &operator =(const Set &s); // Set clone; deep-copy guts
|
|
|
57 VectorSet &operator =(const VectorSet &s) // Set clone; deep-copy guts
|
|
|
58 { if( &s != this ) { slamin(s); } return *this; }
|
|
|
59 ~VectorSet() {}
|
|
|
60 Set &clone(void) const { return *(new VectorSet(*this)); }
|
|
|
61
|
|
|
62 Set &operator <<=(uint elem); // Add member to set
|
|
|
63 VectorSet operator << (uint elem) // Add member to new set
|
|
|
64 { VectorSet foo(*this); foo <<= elem; return foo; }
|
|
|
65 Set &operator >>=(uint elem); // Delete member from set
|
|
|
66 VectorSet operator >> (uint elem) // Delete member from new set
|
|
|
67 { VectorSet foo(*this); foo >>= elem; return foo; }
|
|
|
68
|
|
|
69 VectorSet &operator &=(const VectorSet &s); // Intersect sets into first set
|
|
|
70 Set &operator &=(const Set &s); // Intersect sets into first set
|
|
|
71 VectorSet operator & (const VectorSet &s) const
|
|
|
72 { VectorSet foo(*this); foo &= s; return foo; }
|
|
|
73
|
|
|
74 VectorSet &operator |=(const VectorSet &s); // Intersect sets into first set
|
|
|
75 Set &operator |=(const Set &s); // Intersect sets into first set
|
|
|
76 VectorSet operator | (const VectorSet &s) const
|
|
|
77 { VectorSet foo(*this); foo |= s; return foo; }
|
|
|
78
|
|
|
79 VectorSet &operator -=(const VectorSet &s); // Intersect sets into first set
|
|
|
80 Set &operator -=(const Set &s); // Intersect sets into first set
|
|
|
81 VectorSet operator - (const VectorSet &s) const
|
|
|
82 { VectorSet foo(*this); foo -= s; return foo; }
|
|
|
83
|
|
|
84 int operator ==(const VectorSet &s) const; // True if sets are equal
|
|
|
85 int operator ==(const Set &s) const; // True if sets are equal
|
|
|
86 int operator < (const VectorSet &s) const; // True if strict subset
|
|
|
87 int operator < (const Set &s) const; // True if strict subset
|
|
|
88 int operator <=(const VectorSet &s) const; // True if subset relation holds.
|
|
|
89 int operator <=(const Set &s) const; // True if subset relation holds.
|
|
|
90 int disjoint (const Set &s) const; // True if sets are disjoint
|
|
|
91
|
|
|
92 int operator [](uint elem) const; // Test for membership
|
|
|
93 uint getelem(void) const; // Return a random element
|
|
|
94 void Clear(void); // Clear a set
|
|
|
95 uint Size(void) const; // Number of elements in the Set.
|
|
|
96 void Sort(void); // Sort before iterating
|
|
|
97 int hash() const; // Hash function
|
|
|
98
|
|
|
99 /* Removed for MCC BUG
|
|
|
100 operator const VectorSet* (void) const { return this; } */
|
|
|
101 const VectorSet *asVectorSet() const { return this; }
|
|
|
102
|
|
|
103 // Expose internals for speed-critical fast iterators
|
|
|
104 uint word_size() const { return size; }
|
|
|
105 uint32 *EXPOSE() const { return data; }
|
|
|
106
|
|
|
107 // Fast inlined "test and set". Replaces the idiom:
|
|
|
108 // if( visited[idx] ) return;
|
|
|
109 // visited <<= idx;
|
|
|
110 // With:
|
|
|
111 // if( visited.test_set(idx) ) return;
|
|
|
112 //
|
|
|
113 int test_set( uint elem ) {
|
|
|
114 uint word = elem >> 5; // Get the longword offset
|
|
|
115 if( word >= size ) // Beyond the last?
|
|
|
116 return test_set_grow(elem); // Then grow; set; return 0;
|
|
|
117 uint32 mask = 1L << (elem & 31); // Get bit mask
|
|
|
118 uint32 datum = data[word] & mask;// Get bit
|
|
|
119 data[word] |= mask; // Set bit
|
|
|
120 return datum; // Return bit
|
|
|
121 }
|
|
|
122 int test_set_grow( uint elem ) { // Insert & return 0;
|
|
|
123 (*this) <<= elem; // Insert into set
|
|
|
124 return 0; // Return 0!
|
|
|
125 }
|
|
|
126
|
|
|
127 // Fast inlined test
|
|
|
128 int test( uint elem ) const {
|
|
|
129 uint word = elem >> 5; // Get the longword offset
|
|
|
130 if( word >= size ) return 0; // Beyond the last?
|
|
|
131 uint32 mask = 1L << (elem & 31); // Get bit mask
|
|
|
132 return data[word] & mask; // Get bit
|
|
|
133 }
|
|
|
134
|
|
|
135 // Fast inlined set
|
|
|
136 void set( uint elem ) {
|
|
|
137 uint word = elem >> 5; // Get the longword offset
|
|
|
138 if( word >= size ) { // Beyond the last?
|
|
|
139 test_set_grow(elem); // Then grow and set
|
|
|
140 } else {
|
|
|
141 uint32 mask = 1L << (elem & 31); // Get bit mask
|
|
|
142 data[word] |= mask; // Set bit
|
|
|
143 }
|
|
|
144 }
|
|
|
145
|
|
|
146
|
|
|
147 private:
|
|
|
148 friend class VSetI_;
|
|
|
149 SetI_ *iterate(uint&) const;
|
|
|
150 };
|
|
|
151
|
|
|
152 //------------------------------Iteration--------------------------------------
|
|
|
153 // Loop thru all elements of the set, setting "elem" to the element numbers
|
|
|
154 // in random order. Inserted or deleted elements during this operation may
|
|
|
155 // or may not be iterated over; untouched elements will be affected once.
|
|
|
156 // Usage: for( VectorSetI i(s); i.test(); i++ ) { body = i.elem; }
|
|
|
157
|
|
|
158 class VSetI_ : public SetI_ {
|
|
|
159 friend class VectorSet;
|
|
|
160 friend class VectorSetI;
|
|
|
161 const VectorSet *s;
|
|
|
162 uint i, j;
|
|
|
163 uint32 mask;
|
|
|
164 VSetI_(const VectorSet *vset);
|
|
|
165 uint next(void);
|
|
|
166 int test(void) { return i < s->size; }
|
|
|
167 };
|
|
|
168
|
|
|
169 class VectorSetI : public SetI {
|
|
|
170 public:
|
|
|
171 VectorSetI( const VectorSet *s ) : SetI(s) { }
|
|
|
172 void operator ++(void) { elem = ((VSetI_*)impl)->next(); }
|
|
|
173 int test(void) { return ((VSetI_*)impl)->test(); }
|
|
|
174 };
|
|
|
175
|
|
|
176 #endif // _VECTOR_SET_
|
