Set.hh revision 6145:15cca6ab723a 
1
2/*
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/*
31 * Set.h
32 *
33 * Description:
34 *
35 * $Id$
36 *
37 */
38
39// Define this to use the BigSet class which is slower, but supports
40// sets of size larger than 32.
41
42// #define BIGSET
43
44#define OPTBIGSET
45
46#ifdef OPTBIGSET
47#include "OptBigSet.hh"
48#else
49
50#ifdef BIGSET
51#include "BigSet.hh" // code to supports sets larger than 32
52#else
53
54#ifndef SET_H
55#define SET_H
56
57#include "Global.hh"
58#include "Vector.hh"
59#include "NodeID.hh"
60#include "RubyConfig.hh"
61
62class Set {
63public:
64  // Constructors
65  // creates and empty set
66  Set();
67  Set(int size);
68
69  // used during the replay mechanism
70  //  Set(const char *str);
71
72  //  Set(const Set& obj);
73  //  Set& operator=(const Set& obj);
74
75  // Destructor
76  // ~Set();
77
78  // Public Methods
79
80  void add(NodeID newElement);
81  void addSet(const Set& set);
82  void addRandom();
83  void remove(NodeID newElement);
84  void removeSet(const Set& set);
85  void clear();
86  void broadcast();
87  int count() const;
88  bool isEqual(const Set& set);
89
90  Set OR(const Set& orSet) const;  // return the logical OR of this set and orSet
91  Set AND(const Set& andSet) const;  // return the logical AND of this set and andSet
92
93  // Returns true if the intersection of the two sets is non-empty
94  bool intersectionIsNotEmpty(const Set& other_set) const;
95
96  // Returns true if the intersection of the two sets is empty
97  bool intersectionIsEmpty(const Set& other_set) const;
98
99  bool isSuperset(const Set& test) const;
100  bool isSubset(const Set& test) const { return test.isSuperset(*this); }
101  bool isElement(NodeID element) const;
102  bool isBroadcast() const;
103  bool isEmpty() const;
104
105  NodeID smallestElement() const;
106
107  //  int size() const;
108  void setSize (int size);
109
110  // get element for a index
111  NodeID elementAt(int index);
112  int getSize() const { return m_size; }
113
114  // DEPRECATED METHODS
115  void addToSet(NodeID newElement) { add(newElement); }  // Deprecated
116  void removeFromSet(NodeID newElement) { remove(newElement); }  // Deprecated
117  void clearSet() { clear(); }   // Deprecated
118  void setBroadcast() { broadcast(); }   // Deprecated
119  bool presentInSet(NodeID element) const { return isElement(element); }  // Deprecated
120
121  void print(ostream& out) const;
122private:
123  // Private Methods
124
125  // Data Members (m_ prefix)
126  int m_size;
127  uint32 m_bits;  // Set as a bit vector
128  uint32 m_mask;  // a 000001111 mask where the number of 1s is equal to m_size
129
130};
131
132// Output operator declaration
133ostream& operator<<(ostream& out, const Set& obj);
134
135// ******************* Definitions *******************
136
137// Output operator definition
138extern inline
139ostream& operator<<(ostream& out, const Set& obj)
140{
141  obj.print(out);
142  out << flush;
143  return out;
144}
145
146#endif //SET_H
147#endif //BIGSET
148#endif //OPTBIGSET
149
150