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