1 ////////////////////////////////////////////////////////////////////////////////
2 // $Id: set.h,v 1.9 2006/11/18 03:12:35 dmouldin Exp $
4 // Visual Leak Detector - Lightweight STL-like Set Template
5 // Copyright (c) 2006 Dan Moulding
7 // This library is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU Lesser General Public
9 // License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 // Lesser General Public License for more details.
17 // You should have received a copy of the GNU Lesser General Public
18 // License along with this library; if not, write to the Free Software
19 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 // See COPYING.txt for the full terms of the GNU Lesser General Public License.
23 ////////////////////////////////////////////////////////////////////////////////
29 "This header should only be included by Visual Leak Detector when building it from source. \
30 Applications should never include this header."
33 #include "tree.h" // Provides access to the Tree template class.
35 ////////////////////////////////////////////////////////////////////////////////
37 // The Set Template Class
39 // This is a lightweight STL-like set template. It makes use of the Tree class
40 // template to enable fast insert, find, and erase operations.
42 // Note that while this is a STL-like class, it is not a full STL-compliant
43 // implementation of the STL set container. It contains just the bare minimum
44 // functionality required by Visual Leak Detector. Because of its "lightweight"
45 // nature, this set class has a noticeable performance advantage over some
46 // other standard STL set implementations.
48 template <typename Tk>
56 // Plainly constructed iterators don't reference anything.
61 // operator != - Inequality operator for Set Iterators. Two Set
62 // Iterators are considered equal if and only if they both reference
63 // the same key in the same Set.
65 // - other (IN): The other Set Iterator to compare against.
69 // Returns true if the specified Set Iterator is not equal to this
70 // Set Iterator; otherwise, returns false.
72 BOOL operator != (const Iterator &other) const
74 return ((m_tree != other.m_tree) || (m_node != other.m_node));
77 // operator * - Dereference operator for Set Iterators.
79 // Note: The reference returned by this function is "const", so the
80 // value referenced by the Iterator may not be modified through the
81 // Iterator. This is a departure from STL iterator behavior.
83 // Also, dereferencing an Iterator which does not reference a valid
84 // value in the Set is undefined and will almost certainly cause a
89 // Returns a const reference to the key in the Map referenced by the
92 const Tk& operator * () const
97 // operator ++ - Prefix increment operator for Set Iterators. Causes the
98 // Iterator to reference the in-oder successor of the key currently
99 // referenced by the Iterator. If the Iterator is currently
100 // referencing the largest key in the Map, then the resulting Iterator
101 // will reference the Set's end (the NULL pair).
103 // Note: Incrementing an Iterator which does not reference a valid
104 // key in the Set is undefined and will almost certainly cause a
109 // Returns the Iterator after it has been incremented.
111 Iterator& operator ++ (int)
113 m_node = m_tree->next(m_node);
117 // operator ++ - Postfix increment operator for Map Iterators. Causes
118 // the Iterator to reference the in-order successor of the key/value
119 // pair currently referenced by the Iterator. If the Iterator is
120 // currently referencing the largest key/value pair in the Map, then
121 // the resulting Iterator will reference the Map's end (the NULL
124 // Note: Incrementing an Iterator which does not reference a valid
125 // key/value pair in the Map is undefined and will almost certainly
130 // Returns the Iterator before it has been incremented.
132 Iterator operator ++ ()
134 typename Tree<Tk>::node_t *cur = m_node;
136 m_node = m_tree->next(m_node);
137 return Iterator(m_tree, cur);
140 // operator - - Subtraction operator for Set Iterators. Causes the
141 // the Iterator to reference a key that is an in-order predecessor of
142 // the currently refereced key.
144 // - num (IN): Number indicating the number of preceding keys to
145 // decrement the iterator.
149 // Returns an Iterator referencing the key that precedes the original
150 // Iterator by "num" keys.
152 Iterator operator - (SIZE_T num) const
155 typename Tree<Tk>::node_t *cur = m_node;
157 cur = m_tree->prev(m_node);
158 for (count = 0; count < num; count++) {
159 cur = m_tree->prev(m_node);
161 return Iterator(m_tree, NULL);
164 return Iterator(m_tree, cur);
167 // operator == - Equality operator for Set Iterators. Set Iterators are
168 // considered equal if and only if they both refernce the same
169 // key in the same Set.
171 // - other (IN): The other Set Iterator to compare against.
175 // Returns true if the specified Set Iterator is equal to this Set
176 // Iterator; otherwise returns false.
178 BOOL operator == (const Iterator &other) const
180 return ((m_tree == other.m_tree) && (m_node == other.m_node));
184 // Private constructor. Only the Set class itself may use this
185 // constructor. It is used for constructing Iterators which reference
186 // specific nodes in the internal tree's structure.
187 Iterator (const Tree<Tk> *tree, typename Tree<Tk>::node_t *node)
194 typename Tree<Tk>::node_t *m_node; // Pointer to the node referenced by the Set Iterator.
195 const Tree<Tk> *m_tree; // Pointer to the tree containing the referenced node.
197 // The Set class is a friend of Set Iterators.
198 friend class Set<Tk>;
201 // Muterator class - This class provides a mutable Iterator (the regular
202 // Iterators are const Iterators). By dereferencing a Muterator, you get
203 // a modifiable element.
205 // Caution: Modifing an element in a way that changes its sorting value
206 // will corrupt the Set container. Muterators should only be used when
207 // you are absolutely certain you will not be using it to make a
208 // modification that changes the sort order of the referenced element.
210 class Muterator : public Iterator
213 // operator = - Assignment operator for Set Muterators. Can be used to
214 // copy a Muterator from an existing Iterator, such that the Muterator
215 // references the same element referenced by the Iterator.
216 Muterator& operator = (const Iterator& other) {
217 *(Iterator*)this = other;
221 // operator * - Dereference operator for Set Muterators.
223 // Note: Dereferencing a Muterator which does not reference a valid
224 // value in the Set is undefined and will almost certainly cause a
229 // Returns a reference to the key in the Map referenced by the
238 // begin - Obtains an Iterator referencing the beginning of the Set (i.e.
239 // the lowest key currently stored in the Set).
243 // Returns an Iterator referencing the first key in the Set. If no keys
244 // are currenly stored in the Set, returns the "NULL" Iterator.
246 Iterator begin () const
248 return Iterator(&m_tree, m_tree.begin());
251 // end - Obtains an Iterator referencing the end of the Set. The end of
252 // the Set does not reference an actual key. Instead it represents a
253 // "null" key which signifies the end (i.e. just beyond largest key
254 // currently stored in the Set). Also known as the "NULL" Iterator.
258 // Returns the "NULL" Iterator, signifying the end of the Set.
260 Iterator end () const
262 return Iterator(&m_tree, NULL);
265 // erase - Erases a key from the Set.
267 // - it (IN): Iterator referencing the key to be erased from the Set.
273 VOID erase (Iterator& it)
275 m_tree.erase(it.m_node);
278 // erase - Erases a key from the Set.
280 // - key (IN): The key to be erased from the Set.
286 VOID erase (const Tk &key)
291 // find - Finds a key in the Set.
293 // - key (IN): The key to be found.
297 // Returns an Iterator referencing the found key. If the key could not
298 // be found, then the "NULL" Iterator is returned.
300 Iterator find (const Tk &key) const
302 return Iterator(&m_tree, m_tree.find(key));
305 // insert - Inserts a key into the Set.
307 // - key (IN): The key to be inserted.
311 // Returns an Iterator referencing the key after it has been inserted
312 // into the Set. If an element with an identical key value already exists
313 // in the Set, then the NULL Iterator is returned.
315 Iterator insert (const Tk &key)
317 return Iterator(&m_tree, m_tree.insert(key));
320 // reserve - Sets the reserve size of the Set. The reserve size is the
321 // number of keys for which space should be pre-allocated to avoid
322 // frequent heap hits when inserting new keys into the Set.
324 // - count (IN): The number of keys for which to reserve space in advance.
328 // Returns the reserve size previously in use by the Set.
330 size_t reserve (size_t count)
332 return m_tree.reserve(count);
337 Tree<Tk> m_tree; // The keys are actually stored in a tree.