partition  0.1.1
 All Classes Namespaces Functions Variables Pages
partition.hpp
1 // partition: a container for organizing a set of sequential integers
2 // into non-overlapping groups.
3 // Version: 0.1.1
4 // Copyright 2013 Matthew T. Busche.
5 //
6 // This program is free software: you can redistribute it and/or modify it
7 // under the terms of the GNU General Public License as published by the Free
8 // Software Foundation, either version 3 of the License, or (at your option)
9 // any later version.
10 //
11 // This program is distributed in the hope that it will be useful, but WITHOUT
12 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 // more details.
15 //
16 // You should have received a copy of the GNU General Public License along
17 // with this program. If not, see <http://www.gnu.org/licenses/>.
18 
86 #ifndef PARTITION_HPP
87 #define PARTITION_HPP
88 
89 #include <stdexcept>
90 #include <sstream>
91 #include "partitionSafety.hpp"
92 
93 #ifndef __GNUG__
94 #define __PRETTY_FUNCTION__ ""
95 #endif
96 
97 namespace partition
98 {
99  class PartitionException : public std::runtime_error
100  {
101  public:
102  explicit PartitionException (const std::string& what_arg);
103  };
104 
105  inline void partitionThrow(const char* func, const char* file, int line, const char* msg) {
106  std::ostringstream oss;
107  oss <<
108  "PartitionException: " << msg << "\n" <<
109 #ifdef __GNUG__
110  " thrown from function: " << func << "\n" <<
111 #endif
112  " in file: " << file << "\n" <<
113  " at line: " << line << "\n";
114  throw PartitionException(oss.str());
115  }
116 
117  template<typename M, typename V>
118  class Group;
119 
120  template<typename M, typename V>
121  class Domain
122  {
123  // Forward declartions
124  //
125  private: class Node;
126  public: class Entry;
127 
128  private:
129 
130  int _high;
131  int _low;
132  int _size;
133  int _min;
134 
135  // Unlike most array based containers, Domain does not require
136  // that the first element be indexed by 0. To avoid having to
137  // subtract off the id value of the first array element when
138  // indexing into the Node array, the first entry of the
139  // dynamically allocated array of Nodes is pointed to by (_node +
140  // _low). In this way, _node[x] always gives the Node with id
141  // x and the important method _getNode(int id) can be implemented
142  // efficiently as:
143  //
144  // return _node + id;
145  //
146  // The _node offset is created at the time of array allocation:
147  //
148  // _node = static_cast<Node*>(::operator new (sizeof(Node) * _size)) - _low;
149  //
150  // You'll also note this offset being accounted for when the
151  // array is deleted:
152  //
153  // ::operator delete (_node + _low);
154  //
155  Node* _node;
156 
157  public:
158 
159  class Entry
160  {
161  public:
162  const int id;
163  M member;
164 
165  Entry(int id);
166  Entry(int id, const M& member);
167  };
168 
169  Domain(int size = 0, int min = 0);
170  Domain(const Domain<M,V>& d);
171  template<typename InputIterator> Domain(
172  InputIterator first, InputIterator last, int min = 0);
173 
174  virtual ~Domain();
175 
176  int size() const;
177  int min() const;
178 
179  Group<M,V>* getGroup(int id);
180  const Group<M,V>* getGroup(int id) const;
181 
182  V& getValue(int id);
183  const V& getValue(int id) const;
184 
185  M& getMember(int id);
186  const M& getMember(int id) const;
187  void setMember(int id, const M& m);
188 
189  Entry& getEntry(int id);
190  const Entry& getEntry(int id) const;
191 
192  void addEntry(int id, const M& member = M());
193 
194  void resize(int newSize);
195  void resize(int newSize, int newMin);
196 
197  int high() const;
198  int low() const;
199  int capacity() const;
200  void reserve(int high);
201  void reserve(int high, int low);
202  void compact();
203 
204  private:
205 
206  class Node
207  {
208  public:
209  Group<M,V>* _group;
210  Node* _prev;
211  Node* _next;
212  Entry _entry;
213 
214  Node(int id);
215  Node(int id, const M& member);
216  Node(Group<M,V>* group, Node* prev, Node* next, int id);
217  Node(Group<M,V>* group, Node* prev, Node* next, int id,
218  const M& member);
219  };
220 
221  void _transform(int newHigh, int newLow, int newSize, int newMin);
222  void _initNodeArray(Node* newNode, int newLow, int newSize, int newMin);
223  const Node* _getNode(int id) const;
224  Node* _getNode(int id);
225  void _verifySize (const char* func, const char* file, int line, int size) const;
226  void _verifyRange (const char* func, const char* file, int line, int id) const;
227  void _verifyHighLow(const char* func, const char* file, int line, int high, int low) const;
228  void _verifyInGroup(const char* func, const char* file, int line, const Node* n) const;
229 
230  friend class Group<M,V>;
231  friend class Group<M,V>::Iterator;
232  friend class Group<M,V>::ConstIterator;
233  };
234 
235 
236  template<typename M, typename V>
237  class Group
238  {
239  // Forward declartions and typedefs
240  //
241  public: class Iterator;
242  public: class ConstIterator;
243  public: typedef typename Domain<M,V>::Entry Entry;
244  private: typedef typename Domain<M,V>::Node Node;
245 
246  private:
247 
248  Domain<M,V>* _domain;
249  Node _end;
250  int _size;
251  V _value;
252 
253  public:
254 
255  // Constructors
256  //
257  Group();
258  Group(Domain<M,V>& d);
259  Group(Domain<M,V>& d, const V& v);
260  Group(Domain<M,V>& d, const Group& g);
261  template<typename InputIterator> Group(
262  Domain<M,V>& d,
263  const InputIterator& first,
264  const InputIterator& last);
265 
266  // Destructor
267  //
268  virtual ~Group();
269 
270  // Basic property access
271  //
272  Domain<M,V>* getDomain();
273  const Domain<M,V>* getDomain() const;
274  void setDomain(Domain<M,V>& d);
275 
276  V& getValue();
277  const V& getValue() const;
278  void setValue(const V& v);
279 
280  int size() const;
281  bool contains(int id) const;
282 
283  // Direct Entry access
284  //
285  Entry& peekFront();
286  const Entry& peekFront() const;
287  Entry& peekBack();
288  const Entry& peekBack() const;
289 
290  // Adders
291  //
292  void addFront(int id);
293  void addBack(int id);
294  void addFront(Group& g);
295  void addBack(Group& g);
296  void addAll();
297 
298  // Removers
299  //
300  Entry& removeFront();
301  Entry& removeBack();
302  Entry& remove(int id);
303  void removeAll();
304 
305  // Iterator generators
306  //
307  Iterator front();
308  ConstIterator front() const;
309  Iterator back();
310  ConstIterator back() const;
311  Iterator beforeFront();
312  ConstIterator beforeFront() const;
313  Iterator afterBack();
314  ConstIterator afterBack() const;
315  Iterator find(int id);
316  ConstIterator find(int id) const;
317 
318  Iterator begin();
319  ConstIterator begin() const;
320  Iterator end();
321  ConstIterator end() const;
322 
323  private:
324 
325  void _addAfter(Node* n1, Node* n2);
326  Node* _remove(Node* node);
327  void _verifyDomain (const char* func, const char* file, int line) const;
328  void _verifySameDomain (const char* func, const char* file, int line, const Group<M,V>& g) const;
329  void _verifyDiffDomain (const char* func, const char* file, int line, const Group<M,V>& g) const;
330  void _verifyNotEmpty (const char* func, const char* file, int line) const;
331  void _verifyInGroup (const char* func, const char* file, int line, const Node* n) const;
332  friend class Domain<M,V>;
333 
334  Group(const Group& g);
335  const Group& operator=(const Group& g);
336 
337  public:
338 
339  class Iterator
340  {
341  private:
342 
343  Group* _group;
344  Node* _node;
345 
346  public:
347 
348  Iterator();
349  Iterator(const Iterator& i);
350  Iterator& operator=(const Iterator& i);
351  Iterator& operator++();
352  Iterator& operator--();
353  Iterator operator++(int);
354  Iterator operator--(int);
355  bool isBeforeFront() const;
356  bool isAfterBack() const;
357  bool isAtFront() const;
358  bool isAtBack() const;
359  Entry& operator*() const;
360  Entry* operator->() const;
361  Group* getContainer() const;
362  bool operator==(const Iterator& i) const;
363  bool operator==(const ConstIterator& i) const;
364  bool operator!=(const Iterator& i) const;
365  bool operator!=(const ConstIterator& i) const;
366  void addBefore(int id) const;
367  void addAfter(int id) const;
368  Entry& removeAndInc();
369  Entry& removeAndDec();
370 
371  private:
372 
373  Iterator(Group* group, Node* node);
374  void _verifyGroup(const char* func, const char* file, int line) const;
375  void _verifyNotAtEnd(const char* func, const char* file, int line) const;
376  void _verifyCompare(const char* func, const char* file, int line, const Iterator& i) const;
377  void _verifyCompare(const char* func, const char* file, int line, const ConstIterator& i) const;
378  friend class Group;
379  };
380 
381  class ConstIterator
382  {
383  private:
384 
385  const Group* _group;
386  const Node* _node;
387 
388  public:
389 
390  ConstIterator();
391  ConstIterator(const Iterator& i);
392  ConstIterator(const ConstIterator& i);
393  ConstIterator& operator=(const Iterator& i);
394  ConstIterator& operator=(const ConstIterator& i);
395  ConstIterator& operator++();
396  ConstIterator& operator--();
397  ConstIterator operator++(int);
398  ConstIterator operator--(int);
399  bool isBeforeFront() const;
400  bool isAfterBack() const;
401  bool isAtFront() const;
402  bool isAtBack() const;
403  const Entry& operator*() const;
404  const Entry* operator->() const;
405  const Group* getContainer() const;
406  bool operator==(const Iterator& i) const;
407  bool operator==(const ConstIterator& i) const;
408  bool operator!=(const Iterator& i) const;
409  bool operator!=(const ConstIterator& i) const;
410 
411  private:
412 
413  ConstIterator(const Group* group, const Node* node);
414  void _verifyGroup(const char* func, const char* file, int line) const;
415  void _verifyNotAtEnd(const char* func, const char* file, int line) const;
416  void _verifyCompare(const char* func, const char* file, int line, const Iterator& i) const;
417  void _verifyCompare(const char* func, const char* file, int line, const ConstIterator& i) const;
418  friend class Group;
419  };
420 
421  };
422 
423 #define PARTITION_VERIFY_SIZE(size) _verifySize (__PRETTY_FUNCTION__, __FILE__, __LINE__, size )
424 #define PARTITION_VERIFY_RANGE(id) _verifyRange (__PRETTY_FUNCTION__, __FILE__, __LINE__, id )
425 #define PARTITION_VERIFY_HIGH_LOW(high, low) _verifyHighLow (__PRETTY_FUNCTION__, __FILE__, __LINE__, high, low)
426 #define PARTITION_VERIFY_DOMAIN() _verifyDomain (__PRETTY_FUNCTION__, __FILE__, __LINE__ )
427 #define PARTITION_VERIFY_SAME_DOMAIN(group) _verifySameDomain (__PRETTY_FUNCTION__, __FILE__, __LINE__, group )
428 #define PARTITION_VERIFY_DIFF_DOMAIN(group) _verifyDiffDomain (__PRETTY_FUNCTION__, __FILE__, __LINE__, group )
429 #define PARTITION_VERIFY_NOT_EMPTY() _verifyNotEmpty (__PRETTY_FUNCTION__, __FILE__, __LINE__ )
430 #define PARTITION_VERIFY_IN_GROUP(node) _verifyInGroup (__PRETTY_FUNCTION__, __FILE__, __LINE__, node )
431 #define PARTITION_VERIFY_GROUP() _verifyGroup (__PRETTY_FUNCTION__, __FILE__, __LINE__ )
432 #define PARTITION_VERIFY_NOT_AT_END() _verifyNotAtEnd (__PRETTY_FUNCTION__, __FILE__, __LINE__ )
433 #define PARTITION_VERIFY_COMPARE(i) _verifyCompare (__PRETTY_FUNCTION__, __FILE__, __LINE__, i )
434 
435 // ================
436 // IMPLEMENTATION
437 // ================
438 
453  inline PartitionException::PartitionException(const std::string& what_arg)
454  : runtime_error(what_arg)
455  {
456  }
457 
458 
467  template<typename M, typename V>
468  inline Domain<M,V>::Entry::Entry(int id)
469  : id(id)
470  {
471  }
472 
475  template<typename M, typename V>
476  inline Domain<M,V>::Entry::Entry(int id, const M& member)
477  : id(id),
478  member(member)
479  {
480  }
481 
528  template<typename M, typename V>
529  inline Domain<M,V>::Domain(int size, int min)
530  : _high(0),
531  _low(0),
532  _size(0),
533  _min(0),
534  _node(NULL)
535  {
536  PARTITION_SAFETY_DOMAIN_CONSTRUCTOR(PARTITION_VERIFY_SIZE(size));
537  _transform(min + size, min, size, min);
538  }
539 
544  template<typename M, typename V>
545  inline Domain<M,V>::Domain(const Domain<M,V>& d)
546  : _high(d.min() + d.size()),
547  _low(d.min()),
548  _size(d.size()),
549  _min(d.min())
550  {
551  _node = static_cast<Node*>(::operator new (sizeof(Node) * _size)) - _low;
552  Node* n = _node + _min;
553  const Node* s = d._getNode(_min);
554  for(int i = _min; i < _min + _size; ++i)
555  new (n++) Node(i, (s++)->_entry.member);
556  }
557 
563  template<typename M, typename V> template<typename InputIterator>
564  inline Domain<M,V>::Domain(InputIterator first, InputIterator last, int min)
565  : _high(0),
566  _low(0),
567  _size(0),
568  _min(min),
569  _node(NULL)
570  {
571  int id = min;
572  for(InputIterator i = first; i != last; ++i)
573  addEntry(id++, *i);
574  }
575 
580  template<typename M, typename V>
581  inline Domain<M,V>::~Domain()
582  {
583  resize(0);
584  if(capacity())
585  ::operator delete (_node + _low);
586  }
587 
590  template<typename M, typename V>
591  inline int Domain<M,V>::size() const
592  {
593  return _size;
594  }
595 
598  template<typename M, typename V>
599  inline int Domain<M,V>::min() const
600  {
601  return _min;
602  }
603 
615  template<typename M, typename V>
616  inline Group<M,V>* Domain<M,V>::getGroup(int id)
617  {
618  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
619  return _getNode(id)->_group;
620  }
621 
633  template<typename M, typename V>
634  inline const Group<M,V>* Domain<M,V>::getGroup(int id) const
635  {
636  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
637  return _getNode(id)->_group;
638  }
639 
652  template<typename M, typename V>
653  inline V& Domain<M,V>::getValue(int id)
654  {
655  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
656  Node* n = _getNode(id);
657  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_IN_GROUP(n));
658  return n->_group->_value;
659  }
660 
673  template<typename M, typename V>
674  inline const V& Domain<M,V>::getValue(int id) const
675  {
676  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
677  const Node* n = _getNode(id);
678  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_IN_GROUP(n));
679  return n->_group->_value;
680  }
681 
694  template<typename M, typename V>
695  inline M& Domain<M,V>::getMember(int id)
696  {
697  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
698  return _getNode(id)->_entry.member;
699  }
700 
713  template<typename M, typename V>
714  inline const M& Domain<M,V>::getMember(int id) const
715  {
716  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
717  return _getNode(id)->_entry.member;
718  }
719 
733  template<typename M, typename V>
734  inline void Domain<M,V>::setMember(int id, const M& m)
735  {
736  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
737  _getNode(id)->_entry.member = m;
738  }
739 
752  template<typename M, typename V>
753  inline typename Domain<M,V>::Entry& Domain<M,V>::getEntry(int id)
754  {
755  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
756  return _getNode(id)->_entry;
757  }
758 
771  template<typename M, typename V>
772  inline const typename Domain<M,V>::Entry& Domain<M,V>::getEntry(int id) const
773  {
774  PARTITION_SAFETY_DOMAIN_ACCESSOR(PARTITION_VERIFY_RANGE(id));
775  return _getNode(id)->_entry;
776  }
777 
783  template<typename M, typename V>
784  inline void Domain<M,V>::addEntry(int id, const M& member)
785  {
786  // There are a few cases here.
787  //
788  // First, if the id already exists in the Domain, no call to
789  // _transform is made and the member value of the existing entry is
790  // simply over written to point to the new member value.
791  //
792  // Second, if id is either immediately before or after the existing
793  // Domain range and there is sufficient reserved memory to construct
794  // the new Node without memory reallocation, then no call to
795  // _transform is made, the new Node is constructed locally, and size
796  // and min are adjusted as appropriate.
797  //
798  // Otherwise a call is made to _transform is made (either because a
799  // a memory reallocation is required, or because the id to be added
800  // will result in the size of the Domain growing by more than one.)
801  //
802  // If a call to _transform is made, it is always made so that the
803  // requested Node itself is not constructed, leaving the Domain
804  // with a size one smaller than it will be once the entry is added.
805  // In this way, if a Node must be constructed to hold the given Entry,
806  // it is always constructed locally by this method. (This is done
807  // both to take advantage of the specialized constructor that sets the
808  // member and also to unify the code path with the more typical case
809  // where the size of the Domain is growing by one.)
810  //
811  // The subcase where the capacity is zero is handled differently and
812  // results in the low and min values being reset to match the supplied
813  // id.
814  //
815  if(!_size)
816  _transform(id+1, id, 0, id);
817  else if(id < _min - 1 || id < _low)
818  _transform(_high, id, (_min + _size) - (id + 1), id + 1);
819  else if(id > _min + _size || id >= _high)
820  _transform(id+1, _low, id - _min, _min);
821  if(id >= _min && id < _min + _size)
822  _node[id]._entry.member = member;
823  else
824  {
825  new (_node + id) Node(id, member);
826  ++_size;
827  if(id < _min)
828  _min = id;
829  }
830  }
831 
834  template<typename M, typename V>
835  inline void Domain<M,V>::resize(int newSize)
836  {
837  resize(newSize, _min);
838  }
839 
862  template<typename M, typename V>
863  inline void Domain<M,V>::resize(int newSize, int newMin)
864  {
865  PARTITION_SAFETY_DOMAIN_MEMORY(PARTITION_VERIFY_SIZE(newSize));
866  _transform(newMin + newSize, newMin, newSize, newMin);
867  }
868 
872  template<typename M, typename V>
873  inline int Domain<M,V>::high() const
874  {
875  return _high;
876  }
877 
881  template<typename M, typename V>
882  inline int Domain<M,V>::low() const
883  {
884  return _low;
885  }
886 
889  template<typename M, typename V>
890  inline int Domain<M,V>::capacity() const
891  {
892  return _high - _low;
893  }
894 
897  template<typename M, typename V>
898  inline void Domain<M,V>::reserve(int newHigh)
899  {
900  // Just ignore calls where new high is less than current low.
901  //
902  if(_low > newHigh)
903  return;
904  _transform(newHigh, _low, _size, _min);
905  }
906 
907 
921  template<typename M, typename V>
922  inline void Domain<M,V>::reserve(int newHigh, int newLow)
923  {
924  PARTITION_SAFETY_DOMAIN_MEMORY(PARTITION_VERIFY_HIGH_LOW(newHigh, newLow));
925  _transform(newHigh, newLow, _size, _min);
926  }
927 
932  template<typename M, typename V>
933  inline void Domain<M,V>::compact()
934  {
935  if(capacity() == size())
936  return;
937 
938  int newHigh = _min + _size;
939  int newLow = _min;
940  int newCapacity = newHigh - newLow;
941  Node* newNode = static_cast<Node*> (::operator new (sizeof(Node) * newCapacity)) - newLow;
942  _initNodeArray(newNode, newLow, _size, _min);
943  if(capacity())
944  ::operator delete (_node + _low);
945  _node = newNode;
946  _high = newHigh;
947  _low = newLow;
948  }
949 
958  template<typename M, typename V>
959  inline void Domain<M,V>::_transform(int newHigh, int newLow, int newSize, int newMin)
960  {
961  if(_high == _low)
962  {
963  _high = newLow;
964  _low = newLow;
965  }
966  if(newLow < _low || newHigh > _high)
967  {
968  int growHigh = newHigh <= _high ? 0 : std::max(capacity(), newHigh - _high);
969  int growLow = newLow >= _low ? 0 : std::max(capacity(), _low - newLow);
970  newHigh = _high + growHigh;
971  newLow = _low - growLow;
972  int newCapacity = newHigh - newLow;
973  Node* newNode = static_cast<Node*> (::operator new (sizeof(Node) * newCapacity)) - newLow;
974  _initNodeArray(newNode, newLow, newSize, newMin);
975  if(capacity())
976  ::operator delete (_node + _low);
977  _node = newNode;
978  _high = newHigh;
979  _low = newLow;
980  }
981  else
982  _initNodeArray(_node, _low, newSize, newMin);
983  }
984 
1006  template<typename M, typename V>
1007  inline void Domain<M,V>::_initNodeArray(
1008  Node* newNode, int newLow, int newSize, int newMin)
1009  {
1010  // Throughout this method, the variable i is consistently defined as
1011  // an id from the Domain.
1012 
1013  // 1. If there are elements at the tail of _node that are
1014  // numbered greater than the highest numbered elements of
1015  // newNode then these elements must be removed from their
1016  // groups (since they will no longer exist in the new
1017  // Domain).
1018  //
1019  if(_min + _size > newMin + newSize)
1020  {
1021  int limit = std::max(_min, newMin + newSize);
1022  for(int i = _min + _size - 1; i >= limit; --i)
1023  {
1024  Node* n = _node + i;
1025  if(n->_group)
1026  n->_group->_remove(n);
1027  }
1028  }
1029 
1030  // 2. If there are elements at the head of _node that are
1031  // numbered less than the lowest numbered elements of newNode
1032  // then these elements must be removed from their groups
1033  // (since they will no longer exist in the new Domain).
1034  //
1035  if(_min < newMin)
1036  {
1037  for(int i = std::min(_min + _size, newMin) - 1; i >= _min; --i)
1038  {
1039  Node* n = _node + i;
1040  if(n->_group)
1041  n->_group->_remove(n);
1042  }
1043  }
1044 
1045  // 3. If there are elements at the head of newNode that are
1046  // numbered less lowest numbered elements of _node then these
1047  // elements must be initialized.
1048  //
1049  if(newMin < _min)
1050  {
1051  int limit = std::min(newMin + newSize, _min);
1052  for(int i = newMin; i < limit; ++i)
1053  new (newNode + i) Node(i);
1054  }
1055 
1056  // 4. If newNode is a newly allocated Node array then we need to copy
1057  // elements with common ids from _node to newNode.
1058  //
1059  if(newNode != _node)
1060  {
1061  int limit = std::min(_min + _size, newMin + newSize);
1062  for(int i = std::max(_min, newMin); i < limit; ++i)
1063  {
1064  Node* src = _node + i;
1065  Node* dest = newNode + i;
1066  new (dest) Node(
1067  src->_group,
1068  !src->_group ? NULL : src->_prev == &src->_group->_end ? src->_prev : dest + (src->_prev - src),
1069  !src->_group ? NULL : src->_next == &src->_group->_end ? src->_next : dest + (src->_next - src),
1070  i,
1071  src->_entry.member);
1072 
1073  // We must also offset the front and back pointers of all
1074  // non-empty groups. We only want to do this once so make
1075  // the update when we find the front element of the group.
1076  //
1077  if(src->_group && src->_group->_end._next == src)
1078  {
1079  src->_group->_end._next = dest;
1080  src->_group->_end._prev = dest + (src->_group->_end._prev - src);
1081  }
1082  }
1083  }
1084 
1085  // 5. If there are elements at the tail of newNode that are
1086  // numbered greater than the highest numbered elements of
1087  // _node then these elements must be initialized.
1088  //
1089  if(newMin + newSize > _min + _size)
1090  {
1091  int limit = newMin + newSize;
1092  for(int i = std::max(newMin, _min + _size); i < limit; ++i)
1093  new (newNode + i) Node(i);
1094  }
1095 
1096  // 6. If there are elements at the tail of _node that are
1097  // numbered greater than the highest numbered elements of
1098  // newNode then these elements must be destroyed.
1099  //
1100  if(_min + _size > newMin + newSize)
1101  {
1102  int limit = std::max(_min, newMin + newSize);
1103  for(int i = _min + _size - 1; i >= limit; --i)
1104  (_node + i)->~Node();
1105  }
1106 
1107  // 7. If newNode is a newly allocated Node array then we need to
1108  // destroy elements with common ids in _node.
1109  //
1110  if(newNode != _node)
1111  {
1112  int limit = std::max(_min, newMin);
1113  for(int i = std::min(_min + _size, newMin + newSize) - 1; i >= limit; --i)
1114  (_node + i)->~Node();
1115  }
1116 
1117 
1118  // 8. If there are elements at the head of _node that are
1119  // numbered less than the lowest numbered elements of newNode
1120  // then these elements must be destroyed.
1121  //
1122  if(_min < newMin)
1123  {
1124  for(int i = std::min(_min + _size, newMin) - 1; i >= _min; --i)
1125  (_node + i)->~Node();
1126  }
1127 
1128  // 9. Update the _size and _min settings, but don't update
1129  // _node since it may still need to be deleted by the caller.
1130  //
1131  _size = newSize;
1132  _min = newMin;
1133  }
1134 
1135  template<typename M, typename V>
1136  inline const typename Domain<M,V>::Node* Domain<M,V>::_getNode(int id) const
1137  {
1138  return _node + id;
1139  }
1140 
1141  template<typename M, typename V>
1142  inline typename Domain<M,V>::Node* Domain<M,V>::_getNode(int id)
1143  {
1144  return _node + id;
1145  }
1146 
1147  template<typename M, typename V>
1148  inline void Domain<M,V>::_verifySize(const char* func, const char* file, int line, int size) const
1149  {
1150  if(size < 0)
1151  partitionThrow(func, file, line, "Domain size cannot be negative.");
1152  }
1153 
1154  template<typename M, typename V>
1155  inline void Domain<M,V>::_verifyRange(const char* func, const char* file, int line, int id) const
1156  {
1157  if(id < _min || id >= _min + _size)
1158  partitionThrow(func, file, line, "id is out of Domain range.");
1159  }
1160 
1161  template<typename M, typename V>
1162  inline void Domain<M,V>::_verifyHighLow(const char* func, const char* file, int line, int high, int low) const
1163  {
1164  if(low > high)
1165  partitionThrow(func, file, line, "Attempt to reserve Domain memory with low id greater than high id.");
1166  }
1167 
1168  template<typename M, typename V>
1169  inline void Domain<M,V>::_verifyInGroup(const char* func, const char* file, int line, const Node* n) const
1170  {
1171  if(n->_group == NULL)
1172  partitionThrow(func, file, line, "id is not in a Group.");
1173  }
1174 
1175  //------------------------------
1176  // Node implementation
1177  //------------------------------
1178 
1179  template<typename M, typename V>
1180  inline Domain<M,V>::Node::Node(int id)
1181  : _group(NULL),
1182 #if PARTITION_SL >= PARTITION_ST_DEBUG
1183  _prev(NULL),
1184  _next(NULL),
1185 #endif
1186  _entry(id)
1187  {
1188  }
1189 
1190  template<typename M, typename V>
1191  inline Domain<M,V>::Node::Node(int id, const M& member)
1192  : _group(NULL),
1193 #if PARTITION_SL >= PARTITION_ST_DEBUG
1194  _prev(NULL),
1195  _next(NULL),
1196 #endif
1197  _entry(id, member)
1198  {
1199  }
1200 
1201  template<typename M, typename V>
1202  inline Domain<M,V>::Node::Node(Group<M,V>* group, Node* prev, Node* next, int id)
1203  : _group(group),
1204  _prev(prev),
1205  _next(next),
1206  _entry(id)
1207  {
1208  }
1209 
1210  template<typename M, typename V>
1211  inline Domain<M,V>::Node::Node(Group<M,V>* group, Node* prev, Node* next, int id, const M& member)
1212  : _group(group),
1213  _prev(prev),
1214  _next(next),
1215  _entry(id, member)
1216  {
1217  }
1218 
1219 
1257  template<typename M, typename V>
1258  inline Group<M,V>::Group()
1259  : _domain(NULL),
1260  _end(this, &_end, &_end, 0x80000000),
1261  _size(0)
1262  {
1263  }
1264 
1268  template<typename M, typename V>
1269  inline Group<M,V>::Group(Domain<M,V>& d)
1270  : _domain(&d),
1271  _end(this, &_end, &_end, 0x80000000),
1272  _size(0)
1273  {
1274  }
1275 
1279  template<typename M, typename V>
1280  inline Group<M,V>::Group(Domain<M,V>& d, const V& v)
1281  : _domain(&d),
1282  _end(this, &_end, &_end, 0x80000000),
1283  _size(0),
1284  _value(v)
1285  {
1286  }
1287 
1300  template<typename M, typename V>
1301  inline Group<M,V>::Group(Domain<M,V>& d, const Group& g)
1302  : _domain(&d),
1303  _end(this, &_end, &_end, 0x80000000),
1304  _size(0),
1305  _value(g.getValue())
1306  {
1307  PARTITION_SAFETY_GROUP_CONSTRUCTOR(PARTITION_VERIFY_DIFF_DOMAIN(g));
1308  for(ConstIterator i = g.front(); !i.isAfterBack(); ++i)
1309  addBack(i->id);
1310  }
1311 
1324  template<typename M, typename V> template<typename InputIterator>
1325  inline Group<M,V>::Group(
1326  Domain<M,V>& d,
1327  const InputIterator& first,
1328  const InputIterator& last)
1329 
1330  : _domain(&d),
1331  _end(this, &_end, &_end, 0x80000000),
1332  _size(0)
1333  {
1334  for(InputIterator i = first; i != last; ++i)
1335  addBack(*i);
1336  }
1337 
1340  template<typename M, typename V>
1341  inline Group<M,V>::~Group()
1342  {
1343  removeAll();
1344  }
1345 
1349  template<typename M, typename V>
1350  inline Domain<M,V>* Group<M,V>::getDomain()
1351  {
1352  return _domain;
1353  }
1354 
1358  template<typename M, typename V>
1359  inline const Domain<M,V>* Group<M,V>::getDomain() const
1360  {
1361  return _domain;
1362  }
1363 
1369  template<typename M, typename V>
1370  inline void Group<M,V>::setDomain(Domain<M,V>& d)
1371  {
1372  if(_domain == &d)
1373  return;
1374  removeAll();
1375  _domain = &d;
1376  }
1377 
1381  template<typename M, typename V>
1382  inline V& Group<M,V>::getValue()
1383  {
1384  return _value;
1385  }
1386 
1390  template<typename M, typename V>
1391  inline const V& Group<M,V>::getValue() const
1392  {
1393  return _value;
1394  }
1395 
1398  template<typename M, typename V>
1399  inline void Group<M,V>::setValue(const V& v)
1400  {
1401  this->_value = v;
1402  }
1403 
1406  template<typename M, typename V>
1407  inline int Group<M,V>::size() const
1408  {
1409  return _size;
1410  }
1411 
1425  template<typename M, typename V>
1426  inline bool Group<M,V>::contains(int id) const
1427  {
1428  PARTITION_SAFETY_GROUP_ACCESSOR(PARTITION_VERIFY_DOMAIN());
1429  PARTITION_SAFETY_GROUP_ACCESSOR(_domain->PARTITION_VERIFY_RANGE(id));
1430  return _domain->_getNode(id)->_group == this;
1431  }
1432 
1443  template<typename M, typename V>
1444  inline typename Domain<M,V>::Entry& Group<M,V>::peekFront()
1445  {
1446  PARTITION_SAFETY_GROUP_ACCESSOR(PARTITION_VERIFY_NOT_EMPTY());
1447  return _end._next->_entry;
1448  }
1449 
1460  template<typename M, typename V>
1461  inline const typename Domain<M,V>::Entry& Group<M,V>::peekFront() const
1462  {
1463  PARTITION_SAFETY_GROUP_ACCESSOR(PARTITION_VERIFY_NOT_EMPTY());
1464  return _end._next->_entry;
1465  }
1466 
1477  template<typename M, typename V>
1478  inline typename Domain<M,V>::Entry& Group<M,V>::peekBack()
1479  {
1480  PARTITION_SAFETY_GROUP_ACCESSOR(PARTITION_VERIFY_NOT_EMPTY());
1481  return _end._prev->_entry;
1482  }
1483 
1494  template<typename M, typename V>
1495  inline const typename Domain<M,V>::Entry& Group<M,V>::peekBack() const
1496  {
1497  PARTITION_SAFETY_GROUP_ACCESSOR(PARTITION_VERIFY_NOT_EMPTY());
1498  return _end._prev->_entry;
1499  }
1500 
1515  template<typename M, typename V>
1516  inline void Group<M,V>::addFront(int id)
1517  {
1518  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_DOMAIN());
1519  PARTITION_SAFETY_GROUP_ADD(_domain->PARTITION_VERIFY_RANGE(id));
1520  _addAfter(&_end, _domain->_getNode(id));
1521  }
1522 
1537  template<typename M, typename V>
1538  inline void Group<M,V>::addBack(int id)
1539  {
1540  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_DOMAIN());
1541  PARTITION_SAFETY_GROUP_ADD(_domain->PARTITION_VERIFY_RANGE(id));
1542  _addAfter(_end._prev, _domain->_getNode(id));
1543  }
1544 
1558  template<typename M, typename V>
1559  inline void Group<M,V>::addFront(Group& g)
1560  {
1561  if(this == &g)
1562  return;
1563 
1564  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_DOMAIN());
1565  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_SAME_DOMAIN(g));
1566 
1567  if(g._size == 0)
1568  return;
1569 
1570  Iterator i(this, _end._next);
1571 
1572  Node * na = &_end;
1573  Node * nb = g._end._next;
1574  Node * nc = g._end._prev;
1575  Node * nd = _end._next;
1576 
1577  na->_next = nb;
1578  nb->_prev = na;
1579  nc->_next = nd;
1580  nd->_prev = nc;
1581 
1582  g._end._next = &g._end;
1583  g._end._prev = &g._end;
1584  _size += g._size;
1585  g._size = 0;
1586 
1587  // Still need to update all the Group pointers.
1588  //
1589  while(!(--i).isBeforeFront())
1590  i._node->_group = this;
1591  }
1592 
1606  template<typename M, typename V>
1607  inline void Group<M,V>::addBack(Group& g)
1608  {
1609  if(g._size == 0)
1610  return;
1611 
1612  if(this == &g)
1613  return;
1614 
1615  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_DOMAIN());
1616  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_SAME_DOMAIN(g));
1617 
1618  Iterator i(this, _end._prev);
1619 
1620  Node * na = _end._prev;
1621  Node * nb = g._end._next;
1622  Node * nc = g._end._prev;
1623  Node * nd = &_end;
1624 
1625  na->_next = nb;
1626  nb->_prev = na;
1627  nc->_next = nd;
1628  nd->_prev = nc;
1629 
1630  g._end._next = &g._end;
1631  g._end._prev = &g._end;
1632 
1633  _size += g._size;
1634  g._size = 0;
1635 
1636  // Still need to update all the Group pointers.
1637  //
1638  while(!(++i).isAfterBack())
1639  i._node->_group = this;
1640  }
1641 
1656  template<typename M, typename V>
1657  inline void Group<M,V>::addAll()
1658  {
1659  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_DOMAIN());
1660  int begin = _domain->min();
1661  int end = _domain->min() + _domain->size();
1662  for(int id = begin; id < end; ++id)
1663  addBack(id);
1664  }
1665 
1678  template<typename M, typename V>
1679  inline typename Domain<M,V>::Entry& Group<M,V>::removeFront()
1680  {
1681  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_NOT_EMPTY());
1682  return _remove(_end._next)->_entry;
1683  }
1684 
1697  template<typename M, typename V>
1698  inline typename Domain<M,V>::Entry& Group<M,V>::removeBack()
1699  {
1700  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_NOT_EMPTY());
1701  return _remove(_end._prev)->_entry;
1702  }
1703 
1717  template<typename M, typename V>
1718  inline typename Domain<M,V>::Entry& Group<M,V>::remove(int id)
1719  {
1720  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_DOMAIN());
1721  PARTITION_SAFETY_GROUP_REMOVE(_domain->PARTITION_VERIFY_RANGE(id));
1722  Node* n = _domain->_getNode(id);
1723  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_IN_GROUP(n));
1724  _remove(n);
1725  return n->_entry;
1726  }
1727 
1732  template<typename M, typename V>
1733  inline void Group<M,V>::removeAll()
1734  {
1735  // Could just write:
1736  //
1737  // while(size())
1738  // remove_front();
1739  //
1740  // But this should be considerably faster:
1741  //
1742  Node* n = _end._next;
1743  while(n != &_end)
1744  {
1745  Node* tmp = n;
1746  n = n->_next;
1747  tmp->_group = NULL;
1748 #if PARTITION_SL >= PARTITION_ST_DEBUG
1749  tmp->_prev = NULL;
1750  tmp->_next = NULL;
1751 #endif
1752  }
1753 
1754  _end._next = &_end;
1755  _end._prev = &_end;
1756  _size = 0;
1757  }
1758 
1763  template<typename M, typename V>
1764  inline typename Group<M,V>::Iterator Group<M,V>::front()
1765  {
1766  return Iterator(this, _end._next);
1767  }
1768 
1773  template<typename M, typename V>
1774  inline typename Group<M,V>::ConstIterator Group<M,V>::front() const
1775  {
1776  return ConstIterator(this, _end._next);
1777  }
1778 
1783  template<typename M, typename V>
1784  inline typename Group<M,V>::Iterator Group<M,V>::back()
1785  {
1786  return Iterator(this, _end._prev);
1787  }
1788 
1793  template<typename M, typename V>
1794  inline typename Group<M,V>::ConstIterator Group<M,V>::back() const
1795  {
1796  return ConstIterator(this, _end._prev);
1797  }
1798 
1802  template<typename M, typename V>
1803  inline typename Group<M,V>::Iterator Group<M,V>::beforeFront()
1804  {
1805  return Iterator(this, &_end);
1806  }
1807 
1811  template<typename M, typename V>
1812  inline typename Group<M,V>::ConstIterator Group<M,V>::beforeFront() const
1813  {
1814  return ConstIterator(this, &_end);
1815  }
1816 
1820  template<typename M, typename V>
1821  inline typename Group<M,V>::Iterator Group<M,V>::afterBack()
1822  {
1823  return Iterator(this, &_end);
1824  }
1825 
1829  template<typename M, typename V>
1830  inline typename Group<M,V>::ConstIterator Group<M,V>::afterBack() const
1831  {
1832  return ConstIterator(this, &_end);
1833  }
1834 
1837  template<typename M, typename V>
1838  inline typename Group<M,V>::Iterator Group<M,V>::begin()
1839  {
1840  return front();
1841  }
1842 
1845  template<typename M, typename V>
1846  inline typename Group<M,V>::ConstIterator Group<M,V>::begin() const
1847  {
1848  return front();
1849  }
1850 
1853  template<typename M, typename V>
1854  inline typename Group<M,V>::Iterator Group<M,V>::end()
1855  {
1856  return afterBack();
1857  }
1858 
1861  template<typename M, typename V>
1862  inline typename Group<M,V>::ConstIterator Group<M,V>::end() const
1863  {
1864  return afterBack();
1865  }
1866 
1881  template<typename M, typename V>
1882  inline typename Group<M,V>::Iterator Group<M,V>::find(int id)
1883  {
1884  PARTITION_SAFETY_GROUP_ACCESSOR(PARTITION_VERIFY_DOMAIN());
1885  PARTITION_SAFETY_GROUP_ACCESSOR(_domain->PARTITION_VERIFY_RANGE(id));
1886  Node* n = _domain->_getNode(id);
1887  return Iterator(this, n->_group == this ? n : &_end);
1888  }
1889 
1904  template<typename M, typename V>
1905  inline typename Group<M,V>::ConstIterator Group<M,V>::find(int id) const
1906  {
1907  PARTITION_SAFETY_GROUP_ACCESSOR(PARTITION_VERIFY_DOMAIN());
1908  PARTITION_SAFETY_GROUP_ACCESSOR(_domain->PARTITION_VERIFY_RANGE(id));
1909  const Node* n = _domain->_getNode(id);
1910  return ConstIterator(this, n->_group == this ? n : &_end);
1911  }
1912 
1913  template<typename M, typename V>
1914  inline void Group<M,V>::_addAfter(Node* n1, Node* n2)
1915  {
1916  Node* n3 = n1->_next;
1917  if(n2 == n1 || n2 == n3)
1918  return;
1919  if(n2->_group)
1920  n2->_group->_remove(n2);
1921  n1->_next = n2;
1922  n2->_prev = n1;
1923  n2->_next = n3;
1924  n3->_prev = n2;
1925  n2->_group = this;
1926  ++_size;
1927  }
1928 
1929  template<typename M, typename V>
1930  inline typename Domain<M,V>::Node* Group<M,V>::_remove(Node* node)
1931  {
1932  node->_prev->_next = node->_next;
1933  node->_next->_prev = node->_prev;
1934  --_size;
1935  node->_group = NULL;
1936 #if PARTITION_SL >= PARTITION_ST_DEBUG
1937  node->_prev = NULL;
1938  node->_next = NULL;
1939 #endif
1940  return node;
1941  }
1942 
1943  template<typename M, typename V>
1944  inline void Group<M,V>::_verifyDomain(const char* func, const char* file, int line) const
1945  {
1946  if(_domain == NULL)
1947  partitionThrow(func, file, line, "Group is not associated with a Domain.");
1948  }
1949 
1950  template<typename M, typename V>
1951  inline void Group<M,V>::_verifySameDomain(const char* func, const char* file, int line, const Group<M,V>& g) const
1952  {
1953  if(_domain != g._domain)
1954  partitionThrow(func, file, line, "given Group is associated with a different Domain than this Group.");
1955  }
1956 
1957  template<typename M, typename V>
1958  inline void Group<M,V>::_verifyDiffDomain(const char* func, const char* file, int line, const Group<M,V>& g) const
1959  {
1960  if(_domain == g._domain)
1961  partitionThrow(func, file, line, "given Group is associated with the same Domain as this Group.");
1962  }
1963 
1964  template<typename M, typename V>
1965  inline void Group<M,V>::_verifyNotEmpty(const char* func, const char* file, int line) const
1966  {
1967  if(!_size)
1968  partitionThrow(func, file, line, "Group is empty.");
1969  }
1970 
1971  template<typename M, typename V>
1972  inline void Group<M,V>::_verifyInGroup(const char* func, const char* file, int line, const Node* n) const
1973  {
1974  if(n->_group != this)
1975  partitionThrow(func, file, line, "id is not in this Group.");
1976  }
1977 
2005  template<typename M, typename V>
2006  inline Group<M,V>::Iterator::Iterator()
2007  : _group(NULL),
2008  _node(NULL)
2009  {
2010  }
2011 
2014  template<typename M, typename V>
2015  inline Group<M,V>::Iterator::Iterator(const Iterator& i)
2016  : _group(i._group),
2017  _node(i._node)
2018  {
2019  }
2020 
2023  template<typename M, typename V>
2024  inline typename Group<M,V>::Iterator& Group<M,V>::Iterator::operator=(const Group<M,V>::Iterator& i)
2025  {
2026  _group = i._group;
2027  _node = i._node;
2028  return *this;
2029  }
2030 
2042  template<typename M, typename V>
2043  inline typename Group<M,V>::Iterator& Group<M,V>::Iterator::operator++()
2044  {
2045  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2046  _node = _node->_next;
2047  return *this;
2048  }
2049 
2061  template<typename M, typename V>
2062  inline typename Group<M,V>::Iterator& Group<M,V>::Iterator::operator--()
2063  {
2064  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2065  _node = _node->_prev;
2066  return *this;
2067  }
2068 
2080  template<typename M, typename V>
2081  inline typename Group<M,V>::Iterator Group<M,V>::Iterator::operator++(int)
2082  {
2083  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2084  Iterator ret = *this;
2085  _node = _node->_next;
2086  return ret;
2087  }
2088 
2100  template<typename M, typename V>
2101  inline typename Group<M,V>::Iterator Group<M,V>::Iterator::operator--(int)
2102  {
2103  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2104  Iterator ret = *this;
2105  _node = _node->_prev;
2106  return ret;
2107  }
2108 
2121  template<typename M, typename V>
2122  inline bool Group<M,V>::Iterator::isBeforeFront() const
2123  {
2124  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2125  return _node == &_group->_end;
2126  }
2127 
2140  template<typename M, typename V>
2141  inline bool Group<M,V>::Iterator::isAfterBack() const
2142  {
2143  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2144  return _node == &_group->_end;
2145  }
2146 
2159  template<typename M, typename V>
2160  inline bool Group<M,V>::Iterator::isAtFront() const
2161  {
2162  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2163  return _node == _group->_end._next;
2164  }
2165 
2178  template<typename M, typename V>
2179  inline bool Group<M,V>::Iterator::isAtBack() const
2180  {
2181  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2182  return _node == _group->_end._prev;
2183  }
2184 
2195  template<typename M, typename V>
2196  inline typename Domain<M,V>::Entry& Group<M,V>::Iterator::operator*() const
2197  {
2198  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2199  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_NOT_AT_END());
2200  return _node->_entry;
2201  }
2202 
2213  template<typename M, typename V>
2214  inline typename Domain<M,V>::Entry* Group<M,V>::Iterator::operator->() const
2215  {
2216  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2217  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_NOT_AT_END());
2218  return &_node->_entry;
2219  }
2220 
2223  template<typename M, typename V>
2224  inline Group<M,V>* Group<M,V>::Iterator::getContainer() const
2225  {
2226  return _group;
2227  }
2228 
2240  template<typename M, typename V>
2241  inline bool Group<M,V>::Iterator::operator==(const Iterator& i) const
2242  {
2243  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2244  return i._node == _node;
2245  }
2246 
2258  template<typename M, typename V>
2259  inline bool Group<M,V>::Iterator::operator==(const ConstIterator& i) const
2260  {
2261  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2262  return i._node == _node;
2263  }
2264 
2276  template<typename M, typename V>
2277  inline bool Group<M,V>::Iterator::operator!=(const Iterator& i) const
2278  {
2279  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2280  return i._node != _node;
2281  }
2282 
2294  template<typename M, typename V>
2295  inline bool Group<M,V>::Iterator::operator!=(const ConstIterator& i) const
2296  {
2297  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2298  return i._node != _node;
2299  }
2300 
2316  template<typename M, typename V>
2317  inline void Group<M,V>::Iterator::addBefore(int id) const
2318  {
2319  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_GROUP());
2320  PARTITION_SAFETY_GROUP_ADD(_group->PARTITION_VERIFY_DOMAIN());
2321  PARTITION_SAFETY_GROUP_ADD(_group->_domain->PARTITION_VERIFY_RANGE(id));
2322  _group->_addAfter(_node->_prev, _group->_domain->_getNode(id));
2323  }
2324 
2340  template<typename M, typename V>
2341  inline void Group<M,V>::Iterator::addAfter(int id) const
2342  {
2343  PARTITION_SAFETY_GROUP_ADD(PARTITION_VERIFY_GROUP());
2344  PARTITION_SAFETY_GROUP_ADD(_group->PARTITION_VERIFY_DOMAIN());
2345  PARTITION_SAFETY_GROUP_ADD(_group->_domain->PARTITION_VERIFY_RANGE(id));
2346  _group->_addAfter(_node, _group->_domain->_getNode(id));
2347  }
2348 
2363  template<typename M, typename V>
2364  inline typename Domain<M,V>::Entry& Group<M,V>::Iterator::removeAndInc()
2365  {
2366  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_GROUP());
2367  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_NOT_AT_END());
2368  Node* n = _node;
2369  _node = _node->_next;
2370  _group->_remove(n);
2371  return n->_entry;
2372  }
2373 
2388  template<typename M, typename V>
2389  inline typename Domain<M,V>::Entry& Group<M,V>::Iterator::removeAndDec()
2390  {
2391  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_GROUP());
2392  PARTITION_SAFETY_GROUP_REMOVE(PARTITION_VERIFY_NOT_AT_END());
2393  Node* n = _node;
2394  _node = _node->_prev;
2395  _group->_remove(n);
2396  return n->_entry;
2397  }
2398 
2399  template<typename M, typename V>
2400  inline Group<M,V>::Iterator::Iterator(Group* group, Node* node)
2401  : _group(group),
2402  _node(node)
2403  {
2404  }
2405 
2406  template<typename M, typename V>
2407  inline void Group<M,V>::Iterator::_verifyGroup(const char* func, const char* file, int line) const
2408  {
2409  if(!_group)
2410  partitionThrow(func, file, line, "Iterator is not associated with a Group.");
2411  }
2412 
2413  template<typename M, typename V>
2414  inline void Group<M,V>::Iterator::_verifyNotAtEnd(const char* func, const char* file, int line) const
2415  {
2416  if(_node == &_group->_end)
2417  partitionThrow(func, file, line, "Iterator is before front or after back.");
2418  }
2419 
2420  template<typename M, typename V>
2421  inline void Group<M,V>::Iterator::_verifyCompare(const char* func, const char* file, int line, const Iterator& i) const
2422  {
2423  if(this->_group != i._group)
2424  partitionThrow(func, file, line, "Attempt to compare iterators from different groups.");
2425  }
2426 
2427  template<typename M, typename V>
2428  inline void Group<M,V>::Iterator::_verifyCompare(const char* func, const char* file, int line, const ConstIterator& i) const
2429  {
2430  if(this->_group != i._group)
2431  partitionThrow(func, file, line, "Attempt to compare iterators from different groups.");
2432  }
2433 
2446  template<typename M, typename V>
2447  inline Group<M,V>::ConstIterator::ConstIterator()
2448  : _group(NULL),
2449  _node(NULL)
2450  {
2451  }
2452 
2455  template<typename M, typename V>
2456  inline Group<M,V>::ConstIterator::ConstIterator(const Iterator& i)
2457  : _group(i._group),
2458  _node(i._node)
2459  {
2460  }
2461 
2464  template<typename M, typename V>
2465  inline Group<M,V>::ConstIterator::ConstIterator(const ConstIterator& i)
2466  : _group(i._group),
2467  _node(i._node)
2468  {
2469  }
2470 
2473  template<typename M, typename V>
2474  inline typename Group<M,V>::ConstIterator& Group<M,V>::ConstIterator::operator=(const Iterator& i)
2475  {
2476  _group = i._group;
2477  _node = i._node;
2478  return *this;
2479  }
2480 
2483  template<typename M, typename V>
2484  inline typename Group<M,V>::ConstIterator& Group<M,V>::ConstIterator::operator=(const ConstIterator& i)
2485  {
2486  _group = i._group;
2487  _node = i._node;
2488  return *this;
2489  }
2490 
2502  template<typename M, typename V>
2503  inline typename Group<M,V>::ConstIterator& Group<M,V>::ConstIterator::operator++()
2504  {
2505  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2506  _node = _node->_next;
2507  return *this;
2508  }
2509 
2521  template<typename M, typename V>
2522  inline typename Group<M,V>::ConstIterator& Group<M,V>::ConstIterator::operator--()
2523  {
2524  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2525  _node = _node->_prev;
2526  return *this;
2527  }
2528 
2540  template<typename M, typename V>
2541  inline typename Group<M,V>::ConstIterator Group<M,V>::ConstIterator::operator++(int)
2542  {
2543  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2544  ConstIterator ret = *this;
2545  _node = _node->_next;
2546  return ret;
2547  }
2548 
2560  template<typename M, typename V>
2561  inline typename Group<M,V>::ConstIterator Group<M,V>::ConstIterator::operator--(int)
2562  {
2563  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2564  ConstIterator ret = *this;
2565  _node = _node->_prev;
2566  return ret;
2567  }
2568 
2580  template<typename M, typename V>
2581  inline bool Group<M,V>::ConstIterator::isBeforeFront() const
2582  {
2583  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2584  return _node == &_group->_end;
2585  }
2586 
2598  template<typename M, typename V>
2599  inline bool Group<M,V>::ConstIterator::isAfterBack() const
2600  {
2601  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2602  return _node == &_group->_end;
2603  }
2604 
2616  template<typename M, typename V>
2617  inline bool Group<M,V>::ConstIterator::isAtFront() const
2618  {
2619  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2620  return _node == _group->_end._next;
2621  }
2622 
2634  template<typename M, typename V>
2635  inline bool Group<M,V>::ConstIterator::isAtBack() const
2636  {
2637  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2638  return _node == _group->_end._prev;
2639  }
2640 
2651  template<typename M, typename V>
2652  inline const typename Domain<M,V>::Entry& Group<M,V>::ConstIterator::operator*() const
2653  {
2654  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2655  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_NOT_AT_END());
2656  return _node->_entry;
2657  }
2658 
2669  template<typename M, typename V>
2670  inline const typename Domain<M,V>::Entry* Group<M,V>::ConstIterator::operator->() const
2671  {
2672  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_GROUP());
2673  PARTITION_SAFETY_ITERATOR_DEREF(PARTITION_VERIFY_NOT_AT_END());
2674  return &_node->_entry;
2675  }
2676 
2679  template<typename M, typename V>
2680  inline const Group<M,V>* Group<M,V>::ConstIterator::getContainer() const
2681  {
2682  return _group;
2683  }
2684 
2696  template<typename M, typename V>
2697  inline bool Group<M,V>::ConstIterator::operator==(const Iterator& i) const
2698  {
2699  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2700  return i._node == _node;
2701  }
2702 
2714  template<typename M, typename V>
2715  inline bool Group<M,V>::ConstIterator::operator==(const ConstIterator& i) const
2716  {
2717  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2718  return i._node == _node;
2719  }
2720 
2732  template<typename M, typename V>
2733  inline bool Group<M,V>::ConstIterator::operator!=(const Iterator& i) const
2734  {
2735  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2736  return i._node != _node;
2737  }
2738 
2750  template<typename M, typename V>
2751  inline bool Group<M,V>::ConstIterator::operator!=(const ConstIterator& i) const
2752  {
2753  PARTITION_SAFETY_ITERATOR_COMPARE(PARTITION_VERIFY_COMPARE(i));
2754  return i._node != _node;
2755  }
2756 
2757  template<typename M, typename V>
2758  inline Group<M,V>::ConstIterator::ConstIterator(const Group* group, const Node* node)
2759  : _group(group),
2760  _node(node)
2761  {
2762  }
2763 
2764  template<typename M, typename V>
2765  inline void Group<M,V>::ConstIterator::_verifyGroup(const char* func, const char* file, int line) const
2766  {
2767  if(!_group)
2768  partitionThrow(func, file, line, "Iterator is not associated with a Group.");
2769  }
2770 
2771  template<typename M, typename V>
2772  inline void Group<M,V>::ConstIterator::_verifyNotAtEnd(const char* func, const char* file, int line) const
2773  {
2774  if(_node == &_group->_end)
2775  partitionThrow(func, file, line, "Iterator is before front or after back.");
2776  }
2777 
2778  template<typename M, typename V>
2779  inline void Group<M,V>::ConstIterator::_verifyCompare(const char* func, const char* file, int line, const Iterator& i) const
2780  {
2781  if(this->_group != i._group)
2782  partitionThrow(func, file, line, "Attempt to compare iterators from different groups.");
2783  }
2784 
2785  template<typename M, typename V>
2786  inline void Group<M,V>::ConstIterator::_verifyCompare(const char* func, const char* file, int line, const ConstIterator& i) const
2787  {
2788  if(this->_group != i._group)
2789  partitionThrow(func, file, line, "Attempt to compare iterators from different groups.");
2790  }
2791 }
2792 
2793 #endif
Generated on Fri Apr 12 2013 10:04:22 for partition by   doxygen 1.8.3.1