Main MRPT website > C++ reference
MRPT logo
CBinaryRelation.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | The Mobile Robot Programming Toolkit (MRPT) C++ library |
3  | |
4  | http://www.mrpt.org/ |
5  | |
6  | Copyright (C) 2005-2012 University of Malaga |
7  | |
8  | This software was written by the Machine Perception and Intelligent |
9  | Robotics Lab, University of Malaga (Spain). |
10  | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |
11  | |
12  | This file is part of the MRPT project. |
13  | |
14  | MRPT is free software: you can redistribute it and/or modify |
15  | it under the terms of the GNU General Public License as published by |
16  | the Free Software Foundation, either version 3 of the License, or |
17  | (at your option) any later version. |
18  | |
19  | MRPT is distributed in the hope that it will be useful, |
20  | but WITHOUT ANY WARRANTY; without even the implied warranty of |
21  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22  | GNU General Public License for more details. |
23  | |
24  | You should have received a copy of the GNU General Public License |
25  | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |
26  | |
27  +---------------------------------------------------------------------------+ */
28 #ifndef CBINARYRELATION_H_
29 #define CBINARYRELATION_H_
30 
31 #include <mrpt/math/CMatrixTemplate.h>
32 #include <mrpt/math/matrix_adaptors.h>
33 
34 #include <set>
35 #include <iterator>
36 #include <algorithm>
37 #include <utility>
38 
39 namespace mrpt { namespace math {
40  using std::vector;
41 
42  /**
43  * This class models a binary relation through the elements of any given set. I.e. for each pair of elements (A,B) it assigns two values, f(A,B) and f(B,A).
44  * This class is useful when calling the base function is costly, since it acts like a proxy. It's also useful if the relationship values do not correspond
45  * with the return value of a function. Although it theoretically supports objects with non-trivial constructors or destructors (indicated by specifying
46  * "true" as the thrid parameter of the template instantiation), certain operations will cause memory leaks and may even cause undefined behaviour, so it's
47  * reccomended to use only basic types for the parameter U. The parameter T may be any complex object, however, like a smart pointer.
48  * \ingroup mrpt_base_grp
49  */
50  template<typename T,typename U,bool UIsObject=false> class CBinaryRelation {
51  private:
52  //TODO: VIRTUALIZE INSERTROWSANDCOLS!!! AND REIMPLEMENT IN CMATRIXTEMPLATEOBJECTS.
53 
54  typedef typename detail::MatrixWrapper<U,UIsObject>::MatrixType MatrixType; //!<Matrix type used to store the actual relation.
55  public:
56  typedef U (*SimpleFunctionByReturnValue)(T,T); //!< Simple function type, used to initialize chunks of the matrix.
57  typedef U (*FunctionByReturnValue)(const T &,const T &); //!<Function type which obtains the relation value by a return value.
58  typedef void (*FunctionByReferencePass)(const T &,const T &,U &); //!<Function type which obtains the relation value by reference pass.
59  typedef typename std::set<T>::const_iterator const_iterator; //!<Constant iterator through the set elements.
60  typedef typename std::set<T>::const_reverse_iterator const_reverse_iterator; //!<Constant reverse iterator through the set elements.
61  typedef CMatrixRowAccessor<U> AccessorForFirstElement; //!<Accessor type to every value related to any element A, i.e., f(A,x).
62  typedef CMatrixColumnAccessor<U> AccessorForSecondElement; //!<Accessor type to every value related to any element B, i.e., f(x,B).
63  typedef CConstMatrixRowAccessor<U> ConstAccessorForFirstElement; //!<Const accessor type to every value related to any element A, i.e., f(A,x).
64  typedef CConstMatrixColumnAccessor<U> ConstAccessorForSecondElement; //!<Const accessor type to every value related to any element B, i.e., f(x,B).
65  private:
66  std::set<T> elements; //!<Actual set of elements.
67  MatrixType relation; //!<Matrix storing the relation.
68 
69  /**
70  * Template used to make the function interface independent from the function type.
71  * (wrapper for the global method - needed to make this compile under GCC).
72  */
73  template<typename FunctionType> inline void applyFunction(FunctionType fun,size_t e1,size_t e2,const T &T1,const T &T2) {
74  detail::applyFunction<T,U,UIsObject,FunctionType>(*this,fun,e1,e2,T1,T2);
75  }
76 
77  public:
78  /**
79  * Default constructor, doesn't initialize the relation.
80  */
81  explicit inline CBinaryRelation(const std::set<T> &els):elements(els),relation(els.size(),els.size()) {}
82  /**
83  * Constructor which initializes the relation using a given function.
84  */
85  template<typename FunctionType> inline CBinaryRelation(const std::set<T> &els,FunctionType fun):elements(els),relation(els.size(),els.size()) {
86  initializeWith(fun);
87  }
88  /**
89  * Initialize the whole relation with a given function.
90  */
91  template<typename FunctionType> void initializeWith(FunctionType fun) {
92  typename std::set<T>::const_iterator it=elements.begin();
93  for (size_t i=0;i<elements.size();++i,++it) {
94  typename std::set<T>::const_iterator jt=elements.begin();
95  for (size_t j=0;j<elements.size();++j,++jt) applyFunction(fun,i,j,*it,*jt);
96  }
97  }
98  /**
99  * Initialize the whole relation with a given function, assuming that the relation is symmetrical.
100  */
101  template<typename FunctionType> void initializeSymmetricallyWith(FunctionType fun) {
102  typename std::set<T>::const_iterator it=elements.begin();
103  for (size_t i=0;i<elements.size();++i,++it) {
104  applyFunction(fun,i,i,*it,*it);
105  typename std::set<T>::const_iterator jt=it;
106  jt++;
107  for (size_t j=i+1;j<elements.size();++j,++jt) {
108  applyFunction(fun,i,j,*it,*jt);
109  relation(j,i)=relation(i,j);
110  }
111  }
112  }
113  /**
114  * Manually set a relationship value, given the indices.
115  */
116  inline void setRelationValue(size_t e1,size_t e2,const U &newVal) {
117  relation.get_unsafe(e1,e2)=newVal;
118  }
119  /**
120  * Get a relation value, given the indices.
121  */
122  inline const U &getRelationValue(size_t e1,size_t e2) const {
123  return relation.get_unsafe(e1,e2);
124  }
125  inline const U &operator()(size_t e1,size_t e2) const {
126  return getRelationValue(e1,e2);
127  }
128  /**
129  * Get a reference to a relation value given its indices, which allows both querying and setting the value.
130  */
131  inline U &getRelationValue(size_t e1,size_t e2) {
132  return relation.get_unsafe(e1,e2);
133  }
134  inline U &operator()(size_t e1,size_t e2) {
135  return getRelationValue(e1,e2);
136  }
137  /**
138  * Manually set a relationship value, given the elements. Returns false if any of the elements is not present.
139  */
140  inline bool setRelationValue(const T &t1,const T &t2,const U &newVal) {
141  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
142  typename std::set<T>::const_iterator it1=std::find(b,e,t1),it2=std::find(b,e,t2);
143  if (it1==e||it2==e) return false;
144  setRelationValue(static_cast<size_t>(std::distance(b,it1)),static_cast<size_t>(std::distance(b,it2)),newVal);
145  return true;
146  }
147  /**
148  * Get a relation value, given the elements. Throws domain_error if any of the elements is not present.
149  */
150  inline U getRelationValue(const T &t1,const T &t2) const {
151  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
152  typename std::set<T>::const_iterator it1=std::find(b,e,t1),it2=std::find(b,e,t2);
153  if (it1==e||it2==e) throw std::domain_error("Element not found");
154  return getRelationValue(static_cast<size_t>(std::distance(b,it1)),static_cast<size_t>(std::distance(b,it2)));
155  }
156  /**
157  * Get a reference to a relation value given the elements, which allows both querying and setting. Throws domain_error if any of the elements is not
158  * present.
159  */
160  inline U &getRelationValue(const T &t1,const T &t2) {
161  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
162  typename std::set<T>::const_iterator it1=std::find(b,e,t1),it2=std::find(b,e,t2);
163  if (it1==e||it2==e) throw std::domain_error("Element not found");
164  return getRelationValue(static_cast<size_t>(std::distance(b,it1)),static_cast<size_t>(distance(b,it2)));
165  }
166  /**
167  * Gets an iterator to the starting point of the elements set.
168  */
169  inline const_iterator begin() const {
170  return elements.begin();
171  }
172  /**
173  * Gets an iterator to the ending point of the elements set.
174  */
175  inline const_iterator end() const {
176  return elements.end();
177  }
178  /**
179  * Gets a reverse iterator to the ending point of the elements set.
180  */
181  inline const_reverse_iterator rbegin() const {
182  return elements.rbegin();
183  }
184  /**
185  * Gets a reverse iterator to the starting point of the elements set.
186  */
187  inline const_reverse_iterator rend() const {
188  return elements.rend();
189  }
190  /**
191  * Operator for direct access to a element given its index.
192  */
193  T operator[](size_t i) const {
194  ASSERT_BELOW_(i,elements.size())
195  typename std::set<T>::const_iterator it=elements.begin();
196  std::advance(it,i);
197  return *it;
198  }
199  /**
200  * Gets an accessor for every value related to an element A given its index, i.e., every f(A,x). This accessor is iterable.
201  */
202  inline AccessorForFirstElement getRelationFrom(size_t i) {
203  return AccessorForFirstElement(relation,i);
204  }
205  /**
206  * Gets a constant accessor for every value related to an element A given its index, i.e., every f(A,x). This accessor is iterable.
207  */
208  inline ConstAccessorForFirstElement getRelationFrom(size_t i) const {
209  return ConstAccessorForFirstElement(relation,i);
210  }
211  /**
212  * Gets an accessor for every value related to an element B given its index, i.e., every f(x,B). This accessor is iterable.
213  */
214  inline AccessorForSecondElement getRelationTo(size_t i) {
215  return AccessorForSecondElement(relation,i);
216  }
217  /**
218  * Gets a constant accessor for every value related to an element B given its index, i.e., every f(x,B). This accessor is fully iterable.
219  */
220  inline ConstAccessorForSecondElement getRelationTo(size_t i) const {
221  return ConstAccessorForSecondElement(relation,i);
222  }
223  /**
224  * Gets an iterable accessor for every value related to an element A, i.e., every f(A,x). A domain_error will be thrown if the element is not present.
225  */
226  inline AccessorForFirstElement getRelationFrom(const T &t) {
227  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
228  typename std::set<T>::const_iterator it=std::find(b,e,t);
229  if (it==e) throw std::domain_error("Element not found");
230  return getRelationFrom(static_cast<size_t>(std::distance(b,it)));
231  }
232  /**
233  * Gets an iterable constant accessor for every value related to an element A, i.e., every f(A,x). A domain_error will be thrown if the element is not
234  * present.
235  */
236  inline ConstAccessorForFirstElement getRelationFrom(const T &t) const {
237  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
238  typename std::set<T>::const_iterator it=std::find(b,e,t);
239  if (it==e) throw std::domain_error("Element not found");
240  return getRelationFrom(static_cast<size_t>(std::distance(b,it)));
241  }
242  inline void getRelationFrom(size_t i,vector<U> &vec) {
243  size_t N=elements.size();
244  ASSERT_(i<N);
245  vec.resize(N);
246  ConstAccessorForFirstElement access(relation,i);
247  std::copy(access.begin(),access.end(),vec.begin());
248  }
249  inline void getRelationFrom(const T &t,vector<U> &vec) {
250  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
251  typename std::set<T>::const_iterator it=std::find(b,e,t);
252  if (it==e) throw std::domain_error("Element not found");
253  getRelationFrom(static_cast<size_t>(std::distance(b,it)),vec);
254  }
255  /**
256  * Gets an iterable accessor for every value related to an element B, i.e., every f(x,B). A domain_error will be thrown if the element is not present.
257  */
258  inline AccessorForSecondElement getRelationTo(const T &t) {
259  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
260  typename std::set<T>::const_iterator it=std::find(b,e,t);
261  if (it==e) throw std::domain_error("Element not found");
262  return getRelationTo(static_cast<size_t>(std::distance(b,it)));
263  }
264  /**
265  * Gets an iterable constant accessor for every value related to an alement B, i.e., every f(x,B). A domain_error will be thrown if the element is not
266  * present.
267  */
268  inline ConstAccessorForSecondElement getRelationTo(const T &t) const {
269  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
270  typename std::set<T>::const_iterator it=std::find(b,e,t);
271  if (it==e) throw std::domain_error("Element not found");
272  return getRelationTo(static_cast<size_t>(std::distance(b,it)));
273  }
274  inline void getRelationTo(size_t i,vector<U> &vec) {
275  size_t N=elements.size();
276  ASSERT_(i<N);
277  vec.resize(N);
278  ConstAccessorForSecondElement access(relation,i);
279  std::copy(access.begin(),access.end(),vec.begin());
280  }
281  inline void getRelationTo(const T &t,vector<U> &vec) {
282  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
283  typename std::set<T>::const_iterator it=std::find(b,e,t);
284  if (it==e) throw std::domain_error("Element not found");
285  getRelationTo(static_cast<size_t>(std::distance(b,it)),vec);
286  }
287  /**
288  * Removes an element at a concrete position.
289  */
290  void removeElementAt(size_t i) {
291  ASSERT_(i<elements.size());
292  typename std::set<T>::const_iterator it=elements.begin();
293  std::advance(it,i);
294  elements.erase(i);
295  set<size_t> ii;
296  ii.insert(i);
297  relation.removeRowsAndCols(ii,ii);
298  }
299  /**
300  * Removes an element. Returns false if the element was not present and thus could'nt be eliminated.
301  */
302  bool removeElement(const T &el) {
303  typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
304  typename std::set<T>::const_iterator it=std::find(e,b,el);
305  if (it==e) return false;
306  removeElementAt(std::distance(b,it));
307  return true;
308  }
309  /**
310  * Removes a set of elements. Returns the number of elements which were actually erased.
311  */
312  size_t removeElements(const set<T> &vals) {
313  set<size_t> positions;
314  for (typename set<T>::const_iterator it=vals.begin();it!=vals.end();++it) {
315  typename set<T>::iterator elsIt=std::find(elements.begin(),elements.end(),*it);
316  if (elsIt!=elements.end()) positions.insert(std::distance(elements.begin(),elsIt));
317  }
318 /* for (set<size_t>::const_reverse_iterator it=positions.rbegin();it!=positions.rend();++it) {
319  typename std::set<T>::const_iterator it2=elements.begin();
320  std::advance(it2,*it);
321  elements.erase(it2);
322  }
323  relation.removeRowsAndCols(positions,positions);*/
324  removeElementsAt(positions);
325  return positions.size();
326  }
327  void removeElementsAt(const set<size_t> &poss) {
328  relation.removeRowsAndCols(poss,poss);
329  for (set<size_t>::const_reverse_iterator it=poss.rbegin();it!=poss.rend();++it) {
330  typename std::set<T>::const_iterator it2=elements.begin();
331  std::advance(it2,*it);
332  elements.erase(it2);
333  }
334  }
335  /**
336  * Inserts an element. If the element was present, returns false and its current position. If it wasn't, returns true and the position in which it was
337  * inserted.
338  */
339  std::pair<bool,size_t> insertElement(const T &el) {
340  std::pair<typename std::set<T>::iterator,bool> ins=elements.insert(el);
341  size_t dist=std::distance(elements.begin(),ins.first);
342  if (ins.second) {
343  std::multiset<size_t> newEls;
344  newEls.insert(dist);
345  relation.insertRowsAndCols(newEls,newEls);
346  return std::make_pair(true,dist);
347  } else return std::make_pair(false,dist);
348  }
349  /**
350  * Inserts an element and initializes its relationship values, even if it was already present.
351  */
352  template<typename FunctionType> std::pair<bool,size_t> insertElement(const T &el,FunctionType fun) {
353  std::pair<bool,size_t> ins=insertElement(el);
354  size_t pos=ins.second;
355  for (size_t i=0;i<elements.size();++i) {
356  const T &newEl=operator[](i);
357  applyFunction(fun,pos,i,el,newEl);
358  applyFunction(fun,i,pos,newEl,el);
359  }
360  return ins;
361  }
362  /**
363  * Inserts a set of elements into the relation. Does not initialize the actual relation.
364  */
365  size_t insertElements(const std::set<T> &els) {
366  if (els.empty()) return 0;
367  //This code is much more complex than it should! Trying, for efficiency, to avoid multiple calls to insertElement makes things a lot harder.
368  //It raises the complexity level to N², but alleviates it greatly by making a single memory allocation. Multiple calls to insertElement will be
369  //faster only if the number of elements in the set is really large.
370  std::vector<size_t> added;
371  //std::vector<size_t> exist;
372  added.reserve(els.size());
373  for (typename std::set<T>::const_iterator it=els.begin();it!=els.end();++it) {
374  std::pair<typename std::set<T>::iterator,bool> ins=elements.insert(*it);
375  size_t dist=std::distance(elements.begin(),ins.first);
376  if (ins.second) {
377  added.push_back(dist);
378  for (std::vector<size_t>::iterator it2=added.begin();it2!=added.end();++it2) if (*it2>=dist) ++(*it2);
379  //for (std::vector<size_t>::iterator it2=exist.begin();it2!=exist.end();++it2) if (*it2>=dist) ++(*it2);
380  }// else exist.push_back(dist);
381  }
382  std::sort(added.begin(),added.end());
383  for (size_t j=1;j<added.size();++j) added[j]-=j;
384  std::multiset<size_t> poss(added.begin(),added.end());
385  relation.insertRowsAndCols(poss,poss);
386  return added.size();
387  }
388  /**
389  * Inserts a set of elements into the relation, initializing the actual relation with a given function.
390  */
391  template<typename FunctionType> size_t insertElements(const std::set<T> &els,FunctionType fun) {
392  if (els.empty()) return 0;
393  size_t howMany=insertElements(els);
394  std::set<size_t> poss;
395  {
396  //Little scope for "begin" and "end"...
397  typename std::set<T>::const_iterator begin=elements.begin(),end=elements.end();
398  for (typename std::set<T>::const_iterator it=els.begin();it!=els.end();++it) poss.insert(std::distance(begin,find(begin,end,*it)));
399  }
400  std::set<size_t> nPoss;
401  std::set<size_t>::const_iterator begin=poss.begin(),end=poss.end();
402  for (size_t i=0;i<elements.size();++i) if (std::find(begin,end,i)==end) nPoss.insert(i);
403  vector<const T *> proxy;
404  proxy.reserve(poss.size());
405  for (std::set<size_t>::const_iterator it=begin;it!=end;++it) {
406  const T &e1=operator[](*it);
407  proxy.push_back(&e1);
408  size_t i=0;
409  for (typename std::set<T>::const_iterator it2=elements.begin();it2!=elements.end();++it2,++i) applyFunction(fun,*it,i,e1,*it2);
410  }
411  for (std::set<size_t>::const_iterator it=nPoss.begin();it!=nPoss.end();++it) {
412  const T &e1=operator[](*it);
413  typename std::vector<const T *>::const_iterator itV=proxy.begin();
414  for (std::set<size_t>::const_iterator it2=poss.begin();it2!=poss.end();++it2,++itV) applyFunction(fun,*it,*it2,e1,**itV);
415  }
416  return howMany;
417  }
418  /**
419  * Completely resets the relation, using a new set of elements. Does not initialize the relation.
420  */
421  void setElements(const std::set<T> &newEls) {
422  relation.setSize(0,0);
423  elements=newEls;
424  relation.setSize(newEls.size(),newEls.size());
425  }
426  /**
427  * Returns the amount of elements present in the relation.
428  */
429  inline size_t size() const {
430  return elements.size();
431  }
432  };
433 
434  namespace detail {
435  // generic version (specialization is after definition of CBinaryRelation):
436  template<typename T,typename U,bool UIsObject,typename FunctionType> inline void applyFunction(CBinaryRelation<T,U,UIsObject> &o, FunctionType fun,size_t e1,size_t e2,const T &T1,const T &T2) {
437  o.getRelationValue(e1,e2)=fun(T1,T2);
438  }
439 
440  /** Template specialization by reference type.
441  */
442  template<typename T,typename U,bool UIsObject> inline void applyFunction(CBinaryRelation<T,U,UIsObject> &o,typename CBinaryRelation<T,U,UIsObject>::FunctionByReferencePass fun,size_t e1,size_t e2,const T &T1,const T &T2) {
443  fun(T1,T2,o.getRelationValue(e1,e2));
444  }
445  }
446 
447 
448 }} //End of namespaces
449 #endif


Page generated by Doxygen 1.8.3 for MRPT 0.9.6 SVN: at Fri Feb 15 22:05:02 EST 2013