ARGoS
3
A parallel, multi-engine simulator for swarm robotics
|
00001 00007 #ifndef SET_H 00008 #define SET_H 00009 00010 #include <cstddef> 00011 #include <iterator> 00012 00013 namespace argos { 00014 00019 template <class T> 00020 struct SSetElement { 00021 T Data; 00022 SSetElement* Previous; 00023 SSetElement* Next; 00024 00025 SSetElement(const T& t_data, 00026 SSetElement* ps_prev = NULL, 00027 SSetElement* ps_next = NULL) : 00028 Data(t_data), 00029 Previous(ps_prev), 00030 Next(ps_next) {} 00031 }; 00032 00038 template<class CONTAINED_TYPE, class REFERENCED_TYPE> 00039 class CSetIterator { 00040 00041 public: 00042 00043 typedef std::forward_iterator_tag iterator_category; 00044 typedef REFERENCED_TYPE value_type; 00045 typedef std::ptrdiff_t difference_type; 00046 typedef REFERENCED_TYPE& reference; 00047 typedef REFERENCED_TYPE* pointer; 00048 00049 public: 00050 00051 CSetIterator(SSetElement<CONTAINED_TYPE>* ps_elem = NULL) : 00052 m_psElem(ps_elem) {} 00053 00054 CSetIterator(const CSetIterator& c_it) : 00055 m_psElem(c_it.m_psElem) {} 00056 00057 CSetIterator& operator=(const CSetIterator& c_it) { 00058 if(this != &c_it) { 00059 m_psElem = c_it.m_psElem; 00060 } 00061 return *this; 00062 } 00063 00064 reference operator*() { 00065 return m_psElem->Data; 00066 } 00067 00068 pointer operator->() { 00069 return &(m_psElem->Data); 00070 } 00071 00072 CSetIterator& operator++() { 00073 m_psElem = m_psElem->Next; 00074 return *this; 00075 } 00076 00077 bool operator==(const CSetIterator& c_it) { 00078 return (m_psElem == c_it.m_psElem); 00079 } 00080 00081 bool operator!=(const CSetIterator& c_it) { 00082 return (m_psElem != c_it.m_psElem); 00083 } 00084 00085 SSetElement<CONTAINED_TYPE>* m_psElem; 00086 00087 }; 00088 00099 template <class T> 00100 class CSet { 00101 00102 public: 00103 00104 typedef CSetIterator<T, T> iterator; 00105 00106 class const_iterator : public CSetIterator<T, const T> { 00107 public: 00108 const_iterator(const iterator& c_it) : CSetIterator<T, const T>(c_it.m_psElem) {} 00109 const_iterator& operator=(const iterator& c_it) { 00110 CSetIterator<T, const T>::m_psElem = c_it.m_psElem; 00111 return *this; 00112 } 00113 bool operator==(const iterator& c_it) { return (CSetIterator<T, const T>::m_psElem == c_it.m_psElem); } 00114 bool operator!=(const iterator& c_it) { return (CSetIterator<T, const T>::m_psElem != c_it.m_psElem); } 00115 }; 00116 00117 public: 00118 00123 CSet() : 00124 m_psFirst(NULL), 00125 m_psLast(NULL), 00126 m_unSize(0) {} 00127 00133 CSet(const CSet& c_set) : 00134 m_psFirst(NULL), 00135 m_psLast(NULL), 00136 m_unSize(0) { 00137 *this = c_set; 00138 } 00139 00143 ~CSet() { 00144 clear(); 00145 } 00146 00152 CSet& operator=(const CSet& c_set) { 00153 /* Is the passed set a different set? */ 00154 if(this != &c_set) { 00155 /* Yes, copy from it */ 00156 /* First, erase this set's contents */ 00157 clear(); 00158 /* Is the other set empty? */ 00159 if(! c_set.empty()) { 00160 /* Not empty, there's at least one element to copy */ 00161 /* Start by copying the size of the other set into this one */ 00162 m_unSize = c_set.m_unSize; 00163 /* Create the first element */ 00164 m_psFirst = new SSetElement<T>(c_set.m_psFirst->Data); 00165 /* Is the size of the other set 1? */ 00166 if(m_unSize == 1) { 00167 /* Yes, the first element is also the last one */ 00168 m_psLast = m_psFirst; 00169 } 00170 else { 00171 /* There's more than just one element */ 00172 /* Copy all the elements starting from the second */ 00173 /* Current element on other set to be copied */ 00174 SSetElement<T>* psCurElemOnOther = c_set.m_psFirst->Next; 00175 /* Last copied element on this set */ 00176 SSetElement<T>* psLastElemOnThis = m_psFirst; 00177 /* Current element on this set being created */ 00178 SSetElement<T>* psCurElemOnThis = NULL; 00179 /* Go on until we hit the end of the list on the other set */ 00180 while(psCurElemOnOther != NULL) { 00181 /* Create a new element for this set, setting as previous psLastElemOnThis */ 00182 psCurElemOnThis = new SSetElement<T>(psCurElemOnOther->Data, psLastElemOnThis); 00183 /* Set the next of psLastElemOnThis to the element just created */ 00184 psLastElemOnThis->Next = psCurElemOnThis; 00185 /* Advance with the last element on this */ 00186 psLastElemOnThis = psCurElemOnThis; 00187 /* Advance with the element to copy on the other set */ 00188 psCurElemOnOther = psCurElemOnOther->Next; 00189 } 00190 /* At this point, psCurElemOnThis corresponds to the last element of the list */ 00191 m_psLast = psCurElemOnThis; 00192 } 00193 } 00194 } 00195 return *this; 00196 } 00197 00202 inline bool empty() const { 00203 return m_unSize == 0; 00204 } 00205 00210 inline size_t size() const { 00211 return m_unSize; 00212 } 00213 00214 inline T& first() { 00215 return m_psFirst->Data; 00216 } 00217 00218 inline const T& first() const { 00219 return m_psFirst->Data; 00220 } 00221 00222 inline T& last() { 00223 return m_psLast->Data; 00224 } 00225 00226 inline const T& last() const { 00227 return m_psLast->Data; 00228 } 00229 00235 void insert(const T& t_element) { 00236 /* Is the list empty? */ 00237 if(m_unSize == 0) { 00238 /* Yes, the first and last element coincide */ 00239 m_psFirst = new SSetElement<T>(t_element); 00240 m_psLast = m_psFirst; 00241 m_unSize = 1; 00242 } 00243 else { 00244 /* No, we have at least 1 element */ 00245 /* Search for the element in the list that will be the next 00246 of the element to add */ 00247 SSetElement<T>* psNextElem = m_psFirst; 00248 while(psNextElem != NULL && 00249 psNextElem->Data < t_element) { 00250 psNextElem = psNextElem->Next; 00251 } 00252 /* Did we get to the end of the list? */ 00253 if(psNextElem == NULL) { 00254 /* Yes, add the new element after the last one */ 00255 SSetElement<T>* psNewElem = new SSetElement<T>(t_element, m_psLast); 00256 m_psLast->Next = psNewElem; 00257 m_psLast = psNewElem; 00258 ++m_unSize; 00259 return; 00260 } 00261 /* Is the element already present? */ 00262 if(psNextElem->Data == t_element) { 00263 /* Yes, nothing to add */ 00264 return; 00265 } 00266 /* Is the next element the first in the list? */ 00267 if(psNextElem == m_psFirst) { 00268 /* Yes, we must add the new element as the new first */ 00269 SSetElement<T>* psNewElem = new SSetElement<T>(t_element, NULL, m_psFirst); 00270 m_psFirst->Previous = psNewElem; 00271 m_psFirst = psNewElem; 00272 ++m_unSize; 00273 return; 00274 } 00275 /* If we get here, it's because we have to add the new element in the middle */ 00276 SSetElement<T>* psNewElem = new SSetElement<T>(t_element, psNextElem->Previous, psNextElem); 00277 psNextElem->Previous->Next = psNewElem; 00278 psNextElem->Previous = psNewElem; 00279 ++m_unSize; 00280 } 00281 } 00282 00287 void erase(const T& t_element) { 00288 /* Is the list empty? */ 00289 if(m_unSize == 0) { 00290 /* Yes, nothing to do */ 00291 return; 00292 } 00293 /* Is the list composed of a single element? */ 00294 if(m_unSize == 1) { 00295 /* Is that the element we want to eliminate? */ 00296 if(m_psFirst->Data == t_element) { 00297 /* Yes, erase it! */ 00298 delete m_psFirst; 00299 m_psFirst = NULL; 00300 m_psLast = NULL; 00301 m_unSize = 0; 00302 } 00303 return; 00304 } 00305 /* If we get here, it's because the trivial cases 00306 don't apply */ 00307 /* Look for the passed element */ 00308 SSetElement<T>* psElem = find_impl(t_element); 00309 /* Did we find it? */ 00310 if(psElem != NULL) { 00311 /* Yes, let's erase it */ 00312 /* Are we removing the first element? */ 00313 if(psElem == m_psFirst) { 00314 /* Yes, we need to update m_psFirst */ 00315 m_psFirst = m_psFirst->Next; 00316 m_psFirst->Previous = NULL; 00317 delete psElem; 00318 --m_unSize; 00319 return; 00320 } 00321 /* Are we removing the last element? */ 00322 if(psElem == m_psLast) { 00323 /* Yes, we need to update m_psLast */ 00324 m_psLast = m_psLast->Previous; 00325 m_psLast->Next = NULL; 00326 delete psElem; 00327 --m_unSize; 00328 return; 00329 } 00330 /* If we get here, it's because we need to remove 00331 an element in the middle */ 00332 psElem->Previous->Next = psElem->Next; 00333 psElem->Next->Previous = psElem->Previous; 00334 delete psElem; 00335 --m_unSize; 00336 } 00337 } 00338 00343 inline void erase(iterator& c_it) { 00344 erase(*c_it); 00345 } 00346 00350 void clear() { 00351 if(m_unSize == 0) { 00352 return; 00353 } 00354 if(m_unSize == 1) { 00355 delete m_psFirst; 00356 m_psFirst = NULL; 00357 m_psLast = NULL; 00358 m_unSize = 0; 00359 return; 00360 } 00361 SSetElement<T>* psCurElem = m_psFirst; 00362 SSetElement<T>* psNextElem = psCurElem->Next; 00363 while(psCurElem != NULL) { 00364 delete psCurElem; 00365 psCurElem = psNextElem; 00366 if(psCurElem != NULL) { 00367 psNextElem = psNextElem->Next; 00368 } 00369 } 00370 m_psFirst = NULL; 00371 m_psLast = NULL; 00372 m_unSize = 0; 00373 } 00374 00380 inline bool exists(const T& t_element) { 00381 return find_impl(t_element) != NULL; 00382 } 00383 00388 inline iterator begin() const { 00389 return iterator(m_psFirst); 00390 } 00391 00396 inline iterator end() const { 00397 return iterator(); 00398 } 00399 00404 inline iterator find(const T& t_element) { 00405 return iterator(find_impl(t_element)); 00406 } 00407 00408 private: 00409 00410 SSetElement<T>* find_impl(const T& t_element) const { 00411 if(m_psFirst == NULL) { 00412 return NULL; 00413 } 00414 SSetElement<T>* psElem = m_psFirst; 00415 while(psElem != NULL && 00416 psElem->Data < t_element) { 00417 psElem = psElem->Next; 00418 } 00419 if(psElem == NULL) { 00420 return NULL; 00421 } 00422 else { 00423 return (psElem->Data == t_element) ? psElem : NULL; 00424 } 00425 } 00426 00427 private: 00428 00429 SSetElement<T>* m_psFirst; 00430 SSetElement<T>* m_psLast; 00431 size_t m_unSize; 00432 00433 }; 00434 00435 } 00436 00437 #endif