Jpp
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
JHashCollection.hh
Go to the documentation of this file.
1 #ifndef __JTOOLS__JHASHCOLLECTION__
2 #define __JTOOLS__JHASHCOLLECTION__
3 
4 #include <vector>
5 #include <utility>
6 
7 #include "JLang/JClass.hh"
8 #include "JLang/JException.hh"
10 #include "JTools/JRouter.hh"
11 #include "JIO/JSerialisable.hh"
12 
13 
14 /**
15  * \file
16  *
17  * General purpose class for a hash collection of unique elements.
18  * \author mdejong
19  */
20 namespace JTOOLS {}
21 namespace JPP { using namespace JTOOLS; }
22 
23 namespace JTOOLS {
24 
25  using JLANG::JClass;
27  using JIO::JReader;
28  using JIO::JWriter;
29 
30 
31  /**
32  * General purpose class for hash collection of unique elements.
33  *
34  * The elements in a hash collection are unique according to the specified evaluation.
35  * The evaluation of elements corresponds to a unary method returning an integer value for a given element;
36  * The default evaluator is JHashEvaluator.
37  *
38  * For the binary I/O of a collection of elements, the data structure of the elements
39  * should provide for an implementation of the following operators:
40  * <pre>
41  * JReader& operator>>(JReader& in);
42  * JWriter& operator<<(JWriter& out);
43  * </pre>
44  */
45  template<class JElement_t, class JEvaluator_t = JHashEvaluator>
47  public std::vector<JElement_t>
48  {
49  public:
50 
51  typedef JElement_t value_type;
52  typedef JEvaluator_t evaluator_type;
53 
55 
56  typedef typename container_type::const_iterator const_iterator;
57  typedef typename container_type::const_reverse_iterator const_reverse_iterator;
58  typedef typename container_type::iterator iterator;
59  typedef typename container_type::reverse_iterator reverse_iterator;
60 
62 
63 
64  /**
65  * Constructor.
66  *
67  * \param evaluator evaluator
68  */
69  JHashCollection(const JEvaluator_t& evaluator = JEvaluator_t()) :
70  getValue(evaluator),
71  router (-1) // default address
72  {}
73 
74 
75  /**
76  * Clear.
77  */
78  virtual void clear()
79  {
80  // reset internal router
81 
82  for (iterator i = this->begin(); i != this->end(); ++i) {
83  router.put(this->getValue(*i), router.getDefaultAddress());
84  }
85 
86  container_type::clear();
87  }
88 
89 
90  /**
91  * Find element with given value.
92  *
93  * \param value value
94  * \return position of element with given value or end()
95  */
96  template<class T>
97  const_iterator find(const T& value) const
98  {
99  const int ival = this->getValue(value);
100 
101  if (router.has(ival)) {
102 
103  const_iterator i = this->begin();
104 
105  std::advance(i, router.get(ival));
106 
107  return i;
108  }
109 
110  return this->end();
111  }
112 
113 
114  /**
115  * Find element with given value.
116  *
117  * \param value value
118  * \return position of element with given value or end()
119  */
120  template<class T>
121  iterator find(const T& value)
122  {
123  const int ival = this->getValue(value);
124 
125  if (router.has(ival)) {
126 
127  iterator i = this->begin();
128 
129  std::advance(i, router.get(ival));
130 
131  return i;
132  }
133 
134  return this->end();
135  }
136 
137 
138  /**
139  * Get element with given value.
140  *
141  * This method will throw an exception if given value is not present following the prerequisite of constness.
142  *
143  * \param value value
144  * \return element
145  */
146  template<class T>
147  value_type& get(const T value)
148  {
149  const int ival = this->getValue(value);
150 
151  if (!this->router.has(ival)) {
152  this->insert(value);
153  }
154 
155  return container_type::operator[](router.get(ival)).second;
156  }
157 
158 
159  /**
160  * Get element with given value.
161  *
162  * This method will throw an exception if given value is not present following the prerequisite of constness.
163  *
164  * \param value value
165  * \return element
166  */
167  template<class T>
168  const value_type& get(const T value) const
169  {
170  const int ival = this->getValue(value);
171 
172  if (router.has(ival))
173  return container_type::operator[](router.get(ival)).second;
174  else
175  THROW(JIndexOutOfRange, "JHasCollection::get(): invalid value.");
176  }
177 
178 
179  /**
180  * Insert element.
181  *
182  * \param element element
183  * \return (position, status), where status is true if inserted; else false
184  */
186  {
187  using namespace std;
188 
189  const int ival = this->getValue(element);
190 
191  if (!this->router.has(ival)) {
192 
193  container_type::push_back(element);
194 
195  iterator i = this->rbegin().base();
196 
197  router.put(ival, distance(this->begin(), i));
198 
199  return pair_type(i, true);
200 
201  } else {
202 
203  return pair_type(this->end(), false);
204  }
205  }
206 
207 
208  /**
209  * Erase element at given position.
210  *
211  * \param pos valid position
212  */
213  void erase(iterator pos)
214  {
215  this->router.put(this->getValue(*pos), this->router.getDefaultAddress());
216 
217  iterator i = container_type::erase(pos);
218 
219  for ( ; i != this->end(); ++i) {
220  this->router.put(this->getValue(*i), distance(this->begin(), i));
221  }
222  }
223 
224 
225  /**
226  * Erase elements in given range.
227  *
228  * \param __begin begin position (included)
229  * \param __end end position (excluded)
230  */
231  void erase(iterator __begin, iterator __end)
232  {
233  for (iterator i = __begin; i != __end; ++i) {
234  this->router.put(this->getValue(*i), this->router.getDefaultAddress());
235  }
236 
237  iterator i = container_type::erase(__begin, __end);
238 
239  for ( ; i != this->end(); ++i) {
240  this->router.put(this->getValue(*i), distance(this->begin(), i));
241  }
242  }
243 
244 
245  /**
246  * Erase element with given value.
247  *
248  * \param value value
249  * \return true if element has been erased; else false
250  */
251  template<class T>
252  bool erase(const T& value)
253  {
254  const int ival = this->getValue(value);
255 
256  if (this->router.has(ival)) {
257 
258  iterator pos = this->begin();
259 
260  std::advance(pos, this->router.get(ival));
261 
262  this->erase(pos);
263 
264  return true;
265  }
266 
267  return false;
268  }
269 
270 
271  /**
272  * Test whether given value is present.
273  *
274  * \param value value
275  * \return true if present; else false
276  */
277  template<class T>
278  bool has(const T& value) const
279  {
280  return router.has(this->getValue(value));
281  }
282 
283 
284  /**
285  * Read hash collection from input.
286  *
287  * \param in reader
288  * \param object hash collection
289  * \return reader
290  */
291  friend inline JReader& operator>>(JReader& in, JHashCollection& object)
292  {
293  int n;
294 
295  in >> n;
296 
297  for (value_type element; n != 0 && in >> element; --n) {
298  object.insert(element);
299  }
300 
301  return in;
302  }
303 
304 
305  /**
306  * Write hash collection to output.
307  *
308  * \param out writer
309  * \param object hash collection
310  * \return writer
311  */
312  friend inline JWriter& operator<<(JWriter& out, const JHashCollection& object)
313  {
314  int n = object.size();
315 
316  out << n;
317 
318  for (typename JHashCollection::const_iterator i = object.begin(); i != object.end(); ++i) {
319  out << *i;
320  }
321 
322  return out;
323  }
324 
325 
326  /**
327  * Function object for evaluation of element.
328  */
329  JEvaluator_t getValue;
330 
331 
332  protected:
333  /**
334  * Insert element.
335  *
336  * \param pos position
337  * \param element element
338  * \return position
339  */
341  {
342  return container_type::insert(pos, element);
343  }
344 
346 
347  private:
348  void operator[](int);
349  void resize();
350  void push_back();
351  void pop_back();
352  };
353 }
354 
355 #endif
friend JWriter & operator<<(JWriter &out, const JHashCollection &object)
Write hash collection to output.
Exceptions.
Interface for binary output.
virtual pair_type insert(typename JClass< value_type >::argument_type element)
Insert element.
#define THROW(JException_t, A)
Marco for throwing exception with std::ostream compatible message.
Definition: JException.hh:633
void erase(iterator __begin, iterator __end)
Erase elements in given range.
std::pair< const_iterator, bool > pair_type
iterator find(const T &value)
Find element with given value.
JArgument< T >::argument_type argument_type
Definition: JClass.hh:64
void erase(iterator pos)
Erase element at given position.
bool erase(const T &value)
Erase element with given value.
const_iterator find(const T &value) const
Find element with given value.
General purpose class for hash collection of unique elements.
container_type::const_iterator const_iterator
Interface for binary input.
iterator insert(iterator pos, typename JClass< value_type >::argument_type element)
Insert element.
friend JReader & operator>>(JReader &in, JHashCollection &object)
Read hash collection from input.
counter_type advance(counter_type &counter, const counter_type value, const counter_type limit=std::numeric_limits< counter_type >::max())
Advance counter.
Definition: JCounter.hh:35
virtual void clear()
Clear.
Template for generic class types.
Definition: JClass.hh:62
container_type::reverse_iterator reverse_iterator
container_type::iterator iterator
container_type::const_reverse_iterator const_reverse_iterator
std::vector< value_type > container_type
Exception for accessing an index in a collection that is outside of its range.
Definition: JException.hh:90
bool has(const T &value) const
Test whether given value is present.
JHashCollection(const JEvaluator_t &evaluator=JEvaluator_t())
Constructor.
JEvaluator_t getValue
Function object for evaluation of element.