space_hash_native.h
Go to the documentation of this file.
1 
7 #ifndef SPACE_HASH_NATIVE_H
8 #define SPACE_HASH_NATIVE_H
9 
10 #include <argos3/core/simulator/space/space_hash.h>
11 
12 namespace argos {
13 
18  template <class Element, class Updater>
19  class CSpaceHashNative : public CSpaceHash<Element,Updater> {
20 
21  private:
22 
26  struct SBucket {
27 
32  struct SBucketData {
36  Element* Elem;
45 
53  SBucketData(Element& c_element,
54  SInt32 n_i,
55  SInt32 n_j,
56  SInt32 n_k,
57  SBucketData* ps_next = NULL) :
58  Elem(&c_element),
59  I(n_i),
60  J(n_j),
61  K(n_k),
62  Next(ps_next) {}
63 
64  };
65 
69  UInt64 StoreTimestamp;
70 
74  SBucketData* ElementList;
75 
80  SBucket() :
81  StoreTimestamp(0),
82  ElementList(NULL) {}
83 
89  ~SBucket() {
90  Clear();
91  }
92 
97  inline bool Empty() const {
98  return (ElementList == NULL);
99  }
100 
105  inline void Clear() {
106  if(!Empty()) {
107  SBucketData* psCur = ElementList;
108  SBucketData* psNext = psCur->Next;
109  do {
110  delete psCur;
111  psCur = psNext;
112  if(psCur) psNext = psCur->Next;
113  } while(psCur);
114  ElementList = NULL;
115  }
116  }
117 
125  inline void Add(Element& c_element,
126  SInt32 n_i,
127  SInt32 n_j,
128  SInt32 n_k) {
129  if(Empty()) ElementList = new SBucketData(c_element, n_i, n_j, n_k);
130  else ElementList = new SBucketData(c_element, n_i, n_j, n_k, ElementList);
131  }
132 
140  bool Exists(const Element& c_element,
141  SInt32 n_i,
142  SInt32 n_j,
143  SInt32 n_k) {
144  SBucketData* psCur = ElementList;
145  while(psCur) {
146  if(psCur->Elem == &c_element &&
147  psCur->I == n_i &&
148  psCur->J == n_j &&
149  psCur->K == n_k) return true;
150  psCur = psCur->Next;
151  }
152  return false;
153  }
154 
155  };
156 
157  public:
158 
167  m_psBuckets(NULL),
168  m_unCurrentStoreTimestamp(0) {}
169 
174  Clear();
175  delete[] m_psBuckets;
176  }
177 
181  inline void Clear() {
182  for(size_t i = 0; i < CSpaceHash<Element,Updater>::GetSize(); ++i) {
183  m_psBuckets[i].Clear();
184  }
185  }
186 
192  inline virtual void SetSize(size_t un_size) {
194  m_psBuckets = new SBucket[CSpaceHash<Element,Updater>::GetSize()];
196  }
197 
203  inline virtual void Update() {
204  /* Set the current store time stamp */
205  m_unCurrentStoreTimestamp++;
206  /* Call base class method */
208  }
209 
217  inline virtual void UpdateCell(SInt32 n_i,
218  SInt32 n_j,
219  SInt32 n_k,
220  Element& c_element) {
221  /* Calculate the hash of the current position */
223  /* Get a reference to the bucket */
224  SBucket& sBucket = m_psBuckets[nHash];
225  /* Check if the bucket's content is obsolete */
226  if(sBucket.StoreTimestamp == m_unCurrentStoreTimestamp) {
227  /* Add the current element to the bucket */
228  if(! sBucket.Exists(c_element, n_i, n_j, n_k)) {
229  sBucket.Add(c_element, n_i, n_j, n_k);
230  }
231  }
232  else {
233  /* The bucket's content is obsolete, erase it */
234  sBucket.Clear();
235  /* Set the store timestamp to the current time */
236  sBucket.StoreTimestamp = m_unCurrentStoreTimestamp;
237  /* Add the current element to the bucket */
238  sBucket.Add(c_element, n_i, n_j, n_k);
239  }
240  }
241 
249  virtual bool CheckCell(SInt32 n_i,
250  SInt32 n_j,
251  SInt32 n_k,
252  typename CSpaceHash<Element,Updater>::TElementList& t_elements) {
253  /* In the beginning, no new elements have been found */
254  bool bNewElements = false;
255  /* Calculate the hash of the current position */
257  /* Get a reference to the bucket */
258  SBucket& sBucket = m_psBuckets[nHash];
259  /* Visit the bucket IF:
260  1. its data is up-to-date AND
261  2. it is not empty
262  */
263  if((sBucket.StoreTimestamp == m_unCurrentStoreTimestamp) && /* 1. */
264  !sBucket.Empty()) /* 2. */ {
265  /* Check the bucket's elements */
266  for(typename SBucket::SBucketData* psCur = sBucket.ElementList;
267  psCur;
268  psCur = psCur->Next) {
269  /* Check that the element is in the wanted cell */
270  if(n_i == psCur->I &&
271  n_j == psCur->J &&
272  n_k == psCur->K) {
273  /* We have a new element to add to the list */
274  bNewElements = true;
275  t_elements.insert(psCur->Elem);
276  }
277  }
278  }
279  return bNewElements;
280  }
281 
282  virtual void Dump(CARGoSLog& c_os) {
283  for(size_t i = 0; i < CSpaceHash<Element,Updater>::GetSize(); ++i) {
284  if((m_psBuckets[i].StoreTimestamp == m_unCurrentStoreTimestamp) &&
285  !m_psBuckets[i].Empty()) {
286  c_os << "BUCKET " << i << std::endl;
287  for(typename SBucket::SBucketData* psCur = m_psBuckets[i].ElementList;
288  psCur;
289  psCur = psCur->Next) {
290  c_os << " "
291  << psCur->Elem->GetId()
292  << " ("
293  << psCur->I
294  << ","
295  << psCur->J
296  << ","
297  << psCur->K
298  << ")"
299  << std::endl;
300  }
301  }
302  }
303  }
304 
305  private:
306 
310  SBucket* m_psBuckets;
311 
319  UInt64 m_unCurrentStoreTimestamp;
320 
321  };
322 
323 }
324 
325 #endif
signed int SInt32
32-bit signed integer.
Definition: datatypes.h:93
unsigned long long UInt64
64-bit unsigned integer.
Definition: datatypes.h:107
The namespace containing all the ARGoS related code.
Definition: ci_actuator.h:12
virtual void SetSize(size_t un_size)
Sets the size of the space hash.
Definition: space_hash.h:103
size_t GetSize()
Returns the size of the space hash.
Definition: space_hash.h:94
UInt32 CoordinateHash(SInt32 n_i, SInt32 n_j, SInt32 n_k)
Calculates the hash of a space hash coordinate.
Definition: space_hash.h:220
Defines the basic space hash.
Definition: space_hash.h:300
virtual void Update()
Updates the entire space hash.
Definition: space_hash.h:309
A space hash implementation that does not rely on std::map or std::tr1:unordered_map.
virtual void SetSize(size_t un_size)
Sets the size of the space hash.
CSpaceHashNative()
Class constructor.
~CSpaceHashNative()
Class destructor.
virtual void Update()
Updates the entire space hash.
virtual void Dump(CARGoSLog &c_os)
virtual bool CheckCell(SInt32 n_i, SInt32 n_j, SInt32 n_k, typename CSpaceHash< Element, Updater >::TElementList &t_elements)
Looks for elements to process in a cell.
virtual void UpdateCell(SInt32 n_i, SInt32 n_j, SInt32 n_k, Element &c_element)
Adds an element to a cell of the space hash.
void Clear()
Empties all the buckets in the space hash.
An item of data held by each bucket.
SBucketData * Next
Pointer to the next data item in the list, or NULL if this is the last.
Element * Elem
The element indexed by this data item.
SInt32 I
The space hash cell coordinate corresponding to this data item.
SBucketData(Element &c_element, SInt32 n_i, SInt32 n_j, SInt32 n_k, SBucketData *ps_next=NULL)
Struct constructor.