set.h
Go to the documentation of this file.
1 
7 #ifndef SET_H
8 #define SET_H
9 
10 #include <cstddef>
11 #include <iterator>
12 
13 namespace argos {
14 
19  template <class T>
20  struct SSetElement {
21  T Data;
24 
25  SSetElement(const T& t_data,
26  SSetElement* ps_prev = NULL,
27  SSetElement* ps_next = NULL) :
28  Data(t_data),
29  Previous(ps_prev),
30  Next(ps_next) {}
31  };
32 
38  template<class CONTAINED_TYPE, class REFERENCED_TYPE>
39  class CSetIterator {
40 
41  public:
42 
43  typedef std::forward_iterator_tag iterator_category;
44  typedef REFERENCED_TYPE value_type;
45  typedef std::ptrdiff_t difference_type;
46  typedef REFERENCED_TYPE& reference;
47  typedef REFERENCED_TYPE* pointer;
48 
49  public:
50 
52  m_psElem(ps_elem) {}
53 
54  CSetIterator(const CSetIterator& c_it) :
55  m_psElem(c_it.m_psElem) {}
56 
58  if(this != &c_it) {
59  m_psElem = c_it.m_psElem;
60  }
61  return *this;
62  }
63 
65  return m_psElem->Data;
66  }
67 
69  return &(m_psElem->Data);
70  }
71 
74  return *this;
75  }
76 
77  bool operator==(const CSetIterator& c_it) {
78  return (m_psElem == c_it.m_psElem);
79  }
80 
81  bool operator!=(const CSetIterator& c_it) {
82  return (m_psElem != c_it.m_psElem);
83  }
84 
86 
87  };
88 
100  template <class T, class C = std::less<T> >
101  class CSet {
102 
103  public:
104 
106 
107  class const_iterator : public CSetIterator<T, const T> {
108  public:
109  const_iterator(const iterator& c_it) : CSetIterator<T, const T>(c_it.m_psElem) {}
112  return *this;
113  }
114  bool operator==(const iterator& c_it) { return (CSetIterator<T, const T>::m_psElem == c_it.m_psElem); }
115  bool operator!=(const iterator& c_it) { return (CSetIterator<T, const T>::m_psElem != c_it.m_psElem); }
116  };
117 
118  public:
119 
124  CSet() :
125  m_psFirst(NULL),
126  m_psLast(NULL),
127  m_unSize(0) {}
128 
134  CSet(const CSet& c_set) :
135  m_psFirst(NULL),
136  m_psLast(NULL),
137  m_unSize(0) {
138  *this = c_set;
139  }
140 
144  ~CSet() {
145  clear();
146  }
147 
153  CSet& operator=(const CSet& c_set) {
154  /* Is the passed set a different set? */
155  if(this != &c_set) {
156  /* Yes, copy from it */
157  /* First, erase this set's contents */
158  clear();
159  /* Is the other set empty? */
160  if(! c_set.empty()) {
161  /* Not empty, there's at least one element to copy */
162  /* Start by copying the size of the other set into this one */
163  m_unSize = c_set.m_unSize;
164  /* Create the first element */
165  m_psFirst = new SSetElement<T>(c_set.m_psFirst->Data);
166  /* Is the size of the other set 1? */
167  if(m_unSize == 1) {
168  /* Yes, the first element is also the last one */
169  m_psLast = m_psFirst;
170  }
171  else {
172  /* There's more than just one element */
173  /* Copy all the elements starting from the second */
174  /* Current element on other set to be copied */
175  SSetElement<T>* psCurElemOnOther = c_set.m_psFirst->Next;
176  /* Last copied element on this set */
177  SSetElement<T>* psLastElemOnThis = m_psFirst;
178  /* Current element on this set being created */
179  SSetElement<T>* psCurElemOnThis = NULL;
180  /* Go on until we hit the end of the list on the other set */
181  while(psCurElemOnOther != NULL) {
182  /* Create a new element for this set, setting as previous psLastElemOnThis */
183  psCurElemOnThis = new SSetElement<T>(psCurElemOnOther->Data, psLastElemOnThis);
184  /* Set the next of psLastElemOnThis to the element just created */
185  psLastElemOnThis->Next = psCurElemOnThis;
186  /* Advance with the last element on this */
187  psLastElemOnThis = psCurElemOnThis;
188  /* Advance with the element to copy on the other set */
189  psCurElemOnOther = psCurElemOnOther->Next;
190  }
191  /* At this point, psCurElemOnThis corresponds to the last element of the list */
192  m_psLast = psCurElemOnThis;
193  }
194  }
195  }
196  return *this;
197  }
198 
203  inline bool empty() const {
204  return m_unSize == 0;
205  }
206 
211  inline size_t size() const {
212  return m_unSize;
213  }
214 
215  inline T& first() {
216  return m_psFirst->Data;
217  }
218 
219  inline const T& first() const {
220  return m_psFirst->Data;
221  }
222 
223  inline T& last() {
224  return m_psLast->Data;
225  }
226 
227  inline const T& last() const {
228  return m_psLast->Data;
229  }
230 
236  void insert(const T& t_element, C comp = C()) {
237  /* Is the list empty? */
238  if(m_unSize == 0) {
239  /* Yes, the first and last element coincide */
240  m_psFirst = new SSetElement<T>(t_element);
241  m_psLast = m_psFirst;
242  m_unSize = 1;
243  }
244  else {
245  /* No, we have at least 1 element */
246  /* Search for the element in the list that will be the next
247  of the element to add */
248  SSetElement<T>* psNextElem = m_psFirst;
249  while(psNextElem != NULL &&
250  comp(psNextElem->Data, t_element)) {
251  psNextElem = psNextElem->Next;
252  }
253  /* Did we get to the end of the list? */
254  if(psNextElem == NULL) {
255  /* Yes, add the new element after the last one */
256  SSetElement<T>* psNewElem = new SSetElement<T>(t_element, m_psLast);
257  m_psLast->Next = psNewElem;
258  m_psLast = psNewElem;
259  ++m_unSize;
260  return;
261  }
262  /* Is the element already present? */
263  if(psNextElem->Data == t_element) {
264  /* Yes, nothing to add */
265  return;
266  }
267  /* Is the next element the first in the list? */
268  if(psNextElem == m_psFirst) {
269  /* Yes, we must add the new element as the new first */
270  SSetElement<T>* psNewElem = new SSetElement<T>(t_element, NULL, m_psFirst);
271  m_psFirst->Previous = psNewElem;
272  m_psFirst = psNewElem;
273  ++m_unSize;
274  return;
275  }
276  /* If we get here, it's because we have to add the new element in the middle */
277  SSetElement<T>* psNewElem = new SSetElement<T>(t_element, psNextElem->Previous, psNextElem);
278  psNextElem->Previous->Next = psNewElem;
279  psNextElem->Previous = psNewElem;
280  ++m_unSize;
281  }
282  }
283 
288  void erase(const T& t_element) {
289  /* Is the list empty? */
290  if(m_unSize == 0) {
291  /* Yes, nothing to do */
292  return;
293  }
294  /* Is the list composed of a single element? */
295  if(m_unSize == 1) {
296  /* Is that the element we want to eliminate? */
297  if(m_psFirst->Data == t_element) {
298  /* Yes, erase it! */
299  delete m_psFirst;
300  m_psFirst = NULL;
301  m_psLast = NULL;
302  m_unSize = 0;
303  }
304  return;
305  }
306  /* If we get here, it's because the trivial cases
307  don't apply */
308  /* Look for the passed element */
309  SSetElement<T>* psElem = find_impl(t_element);
310  /* Did we find it? */
311  if(psElem != NULL) {
312  /* Yes, let's erase it */
313  /* Are we removing the first element? */
314  if(psElem == m_psFirst) {
315  /* Yes, we need to update m_psFirst */
316  m_psFirst = m_psFirst->Next;
317  m_psFirst->Previous = NULL;
318  delete psElem;
319  --m_unSize;
320  return;
321  }
322  /* Are we removing the last element? */
323  if(psElem == m_psLast) {
324  /* Yes, we need to update m_psLast */
325  m_psLast = m_psLast->Previous;
326  m_psLast->Next = NULL;
327  delete psElem;
328  --m_unSize;
329  return;
330  }
331  /* If we get here, it's because we need to remove
332  an element in the middle */
333  psElem->Previous->Next = psElem->Next;
334  psElem->Next->Previous = psElem->Previous;
335  delete psElem;
336  --m_unSize;
337  }
338  }
339 
344  inline void erase(iterator& c_it) {
345  erase(*c_it);
346  }
347 
351  void clear() {
352  if(m_unSize == 0) {
353  return;
354  }
355  if(m_unSize == 1) {
356  delete m_psFirst;
357  m_psFirst = NULL;
358  m_psLast = NULL;
359  m_unSize = 0;
360  return;
361  }
362  SSetElement<T>* psCurElem = m_psFirst;
363  SSetElement<T>* psNextElem = psCurElem->Next;
364  while(psCurElem != NULL) {
365  delete psCurElem;
366  psCurElem = psNextElem;
367  if(psCurElem != NULL) {
368  psNextElem = psNextElem->Next;
369  }
370  }
371  m_psFirst = NULL;
372  m_psLast = NULL;
373  m_unSize = 0;
374  }
375 
381  inline bool exists(const T& t_element) {
382  return find_impl(t_element) != NULL;
383  }
384 
389  inline iterator begin() const {
390  return iterator(m_psFirst);
391  }
392 
397  inline iterator end() const {
398  return iterator();
399  }
400 
405  inline iterator find(const T& t_element) {
406  return iterator(find_impl(t_element));
407  }
408 
409  private:
410 
411  SSetElement<T>* find_impl(const T& t_element, C comp = C()) const {
412  if(m_psFirst == NULL) {
413  return NULL;
414  }
415  SSetElement<T>* psElem = m_psFirst;
416  while(psElem != NULL &&
417  comp(psElem->Data, t_element)) {
418  psElem = psElem->Next;
419  }
420  if(psElem == NULL) {
421  return NULL;
422  }
423  else {
424  return (psElem->Data == t_element) ? psElem : NULL;
425  }
426  }
427 
428  private:
429 
430  SSetElement<T>* m_psFirst;
431  SSetElement<T>* m_psLast;
432  size_t m_unSize;
433 
434  };
435 
436 }
437 
438 #endif
The namespace containing all the ARGoS related code.
Definition: ci_actuator.h:12
The data container of CSet.
Definition: set.h:20
SSetElement(const T &t_data, SSetElement *ps_prev=NULL, SSetElement *ps_next=NULL)
Definition: set.h:25
SSetElement * Previous
Definition: set.h:22
SSetElement * Next
Definition: set.h:23
The CSet iterator.
Definition: set.h:39
bool operator==(const CSetIterator &c_it)
Definition: set.h:77
CSetIterator & operator=(const CSetIterator &c_it)
Definition: set.h:57
CSetIterator(SSetElement< CONTAINED_TYPE > *ps_elem=NULL)
Definition: set.h:51
REFERENCED_TYPE value_type
Definition: set.h:44
CSetIterator(const CSetIterator &c_it)
Definition: set.h:54
pointer operator->()
Definition: set.h:68
std::forward_iterator_tag iterator_category
Definition: set.h:43
bool operator!=(const CSetIterator &c_it)
Definition: set.h:81
std::ptrdiff_t difference_type
Definition: set.h:45
reference operator*()
Definition: set.h:64
REFERENCED_TYPE & reference
Definition: set.h:46
SSetElement< CONTAINED_TYPE > * m_psElem
Definition: set.h:85
CSetIterator & operator++()
Definition: set.h:72
REFERENCED_TYPE * pointer
Definition: set.h:47
Defines a very simple double-linked list that stores unique elements.
Definition: set.h:101
void erase(iterator &c_it)
Removes the passed element from the list.
Definition: set.h:344
T & first()
Definition: set.h:215
void erase(const T &t_element)
Removes the passed element from the list.
Definition: set.h:288
CSet(const CSet &c_set)
Class copy constructor.
Definition: set.h:134
const T & last() const
Definition: set.h:227
size_t size() const
Returns the number of elements in the list.
Definition: set.h:211
CSet()
Class constructor.
Definition: set.h:124
iterator find(const T &t_element)
Searches for an element in the list.
Definition: set.h:405
bool empty() const
Returns true if the list is empty.
Definition: set.h:203
iterator begin() const
Returns an iterator to the first element.
Definition: set.h:389
bool exists(const T &t_element)
Returns true if the given element is in the list.
Definition: set.h:381
const T & first() const
Definition: set.h:219
void clear()
Erases the contents of the list.
Definition: set.h:351
CSetIterator< T, T > iterator
Definition: set.h:105
CSet & operator=(const CSet &c_set)
Assignment operator.
Definition: set.h:153
T & last()
Definition: set.h:223
void insert(const T &t_element, C comp=C())
Inserts an element to the list.
Definition: set.h:236
iterator end() const
Returns an invalid iterator.
Definition: set.h:397
~CSet()
Class destructor.
Definition: set.h:144
bool operator!=(const iterator &c_it)
Definition: set.h:115
bool operator==(const iterator &c_it)
Definition: set.h:114
const_iterator & operator=(const iterator &c_it)
Definition: set.h:110
const_iterator(const iterator &c_it)
Definition: set.h:109