Main MRPT website > C++ reference
MRPT logo

CBinaryRelation.h

Go to the documentation of this file.
00001 /* +---------------------------------------------------------------------------+
00002    |          The Mobile Robot Programming Toolkit (MRPT) C++ library          |
00003    |                                                                           |
00004    |                   http://mrpt.sourceforge.net/                            |
00005    |                                                                           |
00006    |   Copyright (C) 2005-2011  University of Malaga                           |
00007    |                                                                           |
00008    |    This software was written by the Machine Perception and Intelligent    |
00009    |      Robotics Lab, University of Malaga (Spain).                          |
00010    |    Contact: Jose-Luis Blanco  <jlblanco@ctima.uma.es>                     |
00011    |                                                                           |
00012    |  This file is part of the MRPT project.                                   |
00013    |                                                                           |
00014    |     MRPT is free software: you can redistribute it and/or modify          |
00015    |     it under the terms of the GNU General Public License as published by  |
00016    |     the Free Software Foundation, either version 3 of the License, or     |
00017    |     (at your option) any later version.                                   |
00018    |                                                                           |
00019    |   MRPT is distributed in the hope that it will be useful,                 |
00020    |     but WITHOUT ANY WARRANTY; without even the implied warranty of        |
00021    |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         |
00022    |     GNU General Public License for more details.                          |
00023    |                                                                           |
00024    |     You should have received a copy of the GNU General Public License     |
00025    |     along with MRPT.  If not, see <http://www.gnu.org/licenses/>.         |
00026    |                                                                           |
00027    +---------------------------------------------------------------------------+ */
00028 #ifndef CBINARYRELATION_H_
00029 #define CBINARYRELATION_H_
00030 
00031 #include <mrpt/math/CMatrixTemplate.h>
00032 #include <mrpt/math/matrix_adaptors.h>
00033 
00034 #include <set>
00035 #include <iterator>
00036 #include <algorithm>
00037 #include <utility>
00038 
00039 namespace mrpt  {       namespace math  {
00040         using std::vector;
00041 
00042         /**
00043           * 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).
00044           * 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
00045           * with the return value of a function. Although it theoretically supports objects with non-trivial constructors or destructors (indicated by specifying
00046           * "true" as the thrid parameter of the template instantiation), certain operations will cause memory leaks and may even cause undefined behaviour, so it's
00047           * reccomended to use only basic types for the parameter U. The parameter T may be any complex object, however, like a smart pointer.
00048           */
00049         template<typename T,typename U,bool UIsObject=false> class CBinaryRelation      {
00050         private:
00051                 //TODO: VIRTUALIZE INSERTROWSANDCOLS!!! AND REIMPLEMENT IN CMATRIXTEMPLATEOBJECTS.
00052 
00053                 typedef typename detail::MatrixWrapper<U,UIsObject>::MatrixType MatrixType;     //!<Matrix type used to store the actual relation.
00054         public:
00055                 typedef U (*SimpleFunctionByReturnValue)(T,T);  //!< Simple function type, used to initialize chunks of the matrix.
00056                 typedef U (*FunctionByReturnValue)(const T &,const T &);        //!<Function type which obtains the relation value by a return value.
00057                 typedef void (*FunctionByReferencePass)(const T &,const T &,U &);       //!<Function type which obtains the relation value by reference pass.
00058                 typedef typename std::set<T>::const_iterator const_iterator;    //!<Constant iterator through the set elements.
00059                 typedef typename std::set<T>::const_reverse_iterator const_reverse_iterator;    //!<Constant reverse iterator through the set elements.
00060                 typedef CMatrixRowAccessor<U> AccessorForFirstElement;  //!<Accessor type to every value related to any element A, i.e., f(A,x).
00061                 typedef CMatrixColumnAccessor<U> AccessorForSecondElement;      //!<Accessor type to every value related to any element B, i.e., f(x,B).
00062                 typedef CConstMatrixRowAccessor<U> ConstAccessorForFirstElement;        //!<Const accessor type to every value related to any element A, i.e., f(A,x).
00063                 typedef CConstMatrixColumnAccessor<U> ConstAccessorForSecondElement;    //!<Const accessor type to every value related to any element B, i.e., f(x,B).
00064         private:
00065                 std::set<T> elements;   //!<Actual set of elements.
00066                 MatrixType relation;    //!<Matrix storing the relation.
00067 
00068                 /**
00069                   * Template used to make the function interface independent from the function type.
00070                   *  (wrapper for the global method - needed to make this compile under GCC).
00071                   */
00072                 template<typename FunctionType> inline void applyFunction(FunctionType fun,size_t e1,size_t e2,const T &T1,const T &T2) {
00073                         detail::applyFunction<T,U,UIsObject,FunctionType>(*this,fun,e1,e2,T1,T2);
00074                 }
00075 
00076         public:
00077                 /**
00078                   * Default constructor, doesn't initialize the relation.
00079                   */
00080                 explicit inline CBinaryRelation(const std::set<T> &els):elements(els),relation(els.size(),els.size())   {}
00081                 /**
00082                   * Constructor which initializes the relation using a given function.
00083                   */
00084                 template<typename FunctionType> inline CBinaryRelation(const std::set<T> &els,FunctionType fun):elements(els),relation(els.size(),els.size())   {
00085                         initializeWith(fun);
00086                 }
00087                 /**
00088                   * Initialize the whole relation with a given function.
00089                   */
00090                 template<typename FunctionType> void initializeWith(FunctionType fun)   {
00091                         typename std::set<T>::const_iterator it=elements.begin();
00092                         for (size_t i=0;i<elements.size();++i,++it)     {
00093                                 typename std::set<T>::const_iterator jt=elements.begin();
00094                                 for (size_t j=0;j<elements.size();++j,++jt) applyFunction(fun,i,j,*it,*jt);
00095                         }
00096                 }
00097                 /**
00098                   * Initialize the whole relation with a given function, assuming that the relation is symmetrical.
00099                   */
00100                 template<typename FunctionType> void initializeSymmetricallyWith(FunctionType fun)      {
00101                         typename std::set<T>::const_iterator it=elements.begin();
00102                         for (size_t i=0;i<elements.size();++i,++it)     {
00103                                 applyFunction(fun,i,i,*it,*it);
00104                                 typename std::set<T>::const_iterator jt=it;
00105                                 jt++;
00106                                 for (size_t j=i+1;j<elements.size();++j,++jt)   {
00107                                         applyFunction(fun,i,j,*it,*jt);
00108                                         relation(j,i)=relation(i,j);
00109                                 }
00110                         }
00111                 }
00112                 /**
00113                   * Manually set a relationship value, given the indices.
00114                   */
00115                 inline void setRelationValue(size_t e1,size_t e2,const U &newVal)       {
00116                         relation.get_unsafe(e1,e2)=newVal;
00117                 }
00118                 /**
00119                   * Get a relation value, given the indices.
00120                   */
00121                 inline const U &getRelationValue(size_t e1,size_t e2) const     {
00122                         return relation.get_unsafe(e1,e2);
00123                 }
00124                 inline const U &operator()(size_t e1,size_t e2) const   {
00125                         return getRelationValue(e1,e2);
00126                 }
00127                 /**
00128                   * Get a reference to a relation value given its indices, which allows both querying and setting the value.
00129                   */
00130                 inline U &getRelationValue(size_t e1,size_t e2) {
00131                         return relation.get_unsafe(e1,e2);
00132                 }
00133                 inline U &operator()(size_t e1,size_t e2)       {
00134                         return getRelationValue(e1,e2);
00135                 }
00136                 /**
00137                   * Manually set a relationship value, given the elements. Returns false if any of the elements is not present.
00138                   */
00139                 inline bool setRelationValue(const T &t1,const T &t2,const U &newVal)   {
00140                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00141                         typename std::set<T>::const_iterator it1=std::find(b,e,t1),it2=std::find(b,e,t2);
00142                         if (it1==e||it2==e) return false;
00143                         setRelationValue(static_cast<size_t>(std::distance(b,it1)),static_cast<size_t>(std::distance(b,it2)),newVal);
00144                         return true;
00145                 }
00146                 /**
00147                   * Get a relation value, given the elements. Throws domain_error if any of the elements is not present.
00148                   */
00149                 inline U getRelationValue(const T &t1,const T &t2) const        {
00150                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00151                         typename std::set<T>::const_iterator it1=std::find(b,e,t1),it2=std::find(b,e,t2);
00152                         if (it1==e||it2==e) throw std::domain_error("Element not found");
00153                         return getRelationValue(static_cast<size_t>(std::distance(b,it1)),static_cast<size_t>(std::distance(b,it2)));
00154                 }
00155                 /**
00156                   * 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
00157                   * present.
00158                   */
00159                 inline U &getRelationValue(const T &t1,const T &t2)     {
00160                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00161                         typename std::set<T>::const_iterator it1=std::find(b,e,t1),it2=std::find(b,e,t2);
00162                         if (it1==e||it2==e) throw std::domain_error("Element not found");
00163                         return getRelationValue(static_cast<size_t>(std::distance(b,it1)),static_cast<size_t>(distance(b,it2)));
00164                 }
00165                 /**
00166                   * Gets an iterator to the starting point of the elements set.
00167                   */
00168                 inline const_iterator begin() const     {
00169                         return elements.begin();
00170                 }
00171                 /**
00172                   * Gets an iterator to the ending point of the elements set.
00173                   */
00174                 inline const_iterator end() const       {
00175                         return elements.end();
00176                 }
00177                 /**
00178                   * Gets a reverse iterator to the ending point of the elements set.
00179                   */
00180                 inline const_reverse_iterator rbegin() const    {
00181                         return elements.rbegin();
00182                 }
00183                 /**
00184                   * Gets a reverse iterator to the starting point of the elements set.
00185                   */
00186                 inline const_reverse_iterator rend() const      {
00187                         return elements.rend();
00188                 }
00189                 /**
00190                   * Operator for direct access to a element given its index.
00191                   */
00192                 T operator[](size_t i) const    {
00193                         ASSERT_BELOW_(i,elements.size())
00194                         typename std::set<T>::const_iterator it=elements.begin();
00195                         std::advance(it,i);
00196                         return *it;
00197                 }
00198                 /**
00199                   * Gets an accessor for every value related to an element A given its index, i.e., every f(A,x). This accessor is iterable.
00200                   */
00201                 inline AccessorForFirstElement getRelationFrom(size_t i)        {
00202                         return AccessorForFirstElement(relation,i);
00203                 }
00204                 /**
00205                   * 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.
00206                   */
00207                 inline ConstAccessorForFirstElement getRelationFrom(size_t i) const     {
00208                         return ConstAccessorForFirstElement(relation,i);
00209                 }
00210                 /**
00211                   * Gets an accessor for every value related to an element B given its index, i.e., every f(x,B). This accessor is iterable.
00212                   */
00213                 inline AccessorForSecondElement getRelationTo(size_t i) {
00214                         return AccessorForSecondElement(relation,i);
00215                 }
00216                 /**
00217                   * 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.
00218                   */
00219                 inline ConstAccessorForSecondElement getRelationTo(size_t i) const      {
00220                         return ConstAccessorForSecondElement(relation,i);
00221                 }
00222                 /**
00223                   * 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.
00224                   */
00225                 inline AccessorForFirstElement getRelationFrom(const T &t)      {
00226                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00227                         typename std::set<T>::const_iterator it=std::find(b,e,t);
00228                         if (it==e) throw std::domain_error("Element not found");
00229                         return getRelationFrom(static_cast<size_t>(std::distance(b,it)));
00230                 }
00231                 /**
00232                   * 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
00233                   * present.
00234                   */
00235                 inline ConstAccessorForFirstElement getRelationFrom(const T &t) const   {
00236                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00237                         typename std::set<T>::const_iterator it=std::find(b,e,t);
00238                         if (it==e) throw std::domain_error("Element not found");
00239                         return getRelationFrom(static_cast<size_t>(std::distance(b,it)));
00240                 }
00241                 inline void getRelationFrom(size_t i,vector<U> &vec)    {
00242                         size_t N=elements.size();
00243                         ASSERT_(i<N);
00244                         vec.resize(N);
00245                         ConstAccessorForFirstElement access(relation,i);
00246                         std::copy(access.begin(),access.end(),vec.begin());
00247                 }
00248                 inline void getRelationFrom(const T &t,vector<U> &vec)  {
00249                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00250                         typename std::set<T>::const_iterator it=std::find(b,e,t);
00251                         if (it==e) throw std::domain_error("Element not found");
00252                         getRelationFrom(static_cast<size_t>(std::distance(b,it)),vec);
00253                 }
00254                 /**
00255                   * 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.
00256                   */
00257                 inline AccessorForSecondElement getRelationTo(const T &t)       {
00258                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00259                         typename std::set<T>::const_iterator it=std::find(b,e,t);
00260                         if (it==e) throw std::domain_error("Element not found");
00261                         return getRelationTo(static_cast<size_t>(std::distance(b,it)));
00262                 }
00263                 /**
00264                   * 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
00265                   * present.
00266                   */
00267                 inline ConstAccessorForSecondElement getRelationTo(const T &t) const    {
00268                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00269                         typename std::set<T>::const_iterator it=std::find(b,e,t);
00270                         if (it==e) throw std::domain_error("Element not found");
00271                         return getRelationTo(static_cast<size_t>(std::distance(b,it)));
00272                 }
00273                 inline void getRelationTo(size_t i,vector<U> &vec)      {
00274                         size_t N=elements.size();
00275                         ASSERT_(i<N);
00276                         vec.resize(N);
00277                         ConstAccessorForSecondElement access(relation,i);
00278                         std::copy(access.begin(),access.end(),vec.begin());
00279                 }
00280                 inline void getRelationTo(const T &t,vector<U> &vec)    {
00281                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00282                         typename std::set<T>::const_iterator it=std::find(b,e,t);
00283                         if (it==e) throw std::domain_error("Element not found");
00284                         getRelationTo(static_cast<size_t>(std::distance(b,it)),vec);
00285                 }
00286                 /**
00287                   * Removes an element at a concrete position.
00288                   */
00289                 void removeElementAt(size_t i)  {
00290                         ASSERT_(i<elements.size());
00291                         typename std::set<T>::const_iterator it=elements.begin();
00292                         std::advance(it,i);
00293                         elements.erase(i);
00294                         set<size_t> ii;
00295                         ii.insert(i);
00296                         relation.removeRowsAndCols(ii,ii);
00297                 }
00298                 /**
00299                   * Removes an element. Returns false if the element was not present and thus could'nt be eliminated.
00300                   */
00301                 bool removeElement(const T &el) {
00302                         typename std::set<T>::const_iterator b=elements.begin(),e=elements.end();
00303                         typename std::set<T>::const_iterator it=std::find(e,b,el);
00304                         if (it==e) return false;
00305                         removeElementAt(std::distance(b,it));
00306                         return true;
00307                 }
00308                 /**
00309                   * Removes a set of elements. Returns the number of elements which were actually erased.
00310                   */
00311                 size_t removeElements(const set<T> &vals)       {
00312                         set<size_t> positions;
00313                         for (typename set<T>::const_iterator it=vals.begin();it!=vals.end();++it)       {
00314                                 typename set<T>::iterator elsIt=std::find(elements.begin(),elements.end(),*it);
00315                                 if (elsIt!=elements.end()) positions.insert(std::distance(elements.begin(),elsIt));
00316                         }
00317 /*                      for (set<size_t>::const_reverse_iterator it=positions.rbegin();it!=positions.rend();++it)       {
00318                                 typename std::set<T>::const_iterator it2=elements.begin();
00319                                 std::advance(it2,*it);
00320                                 elements.erase(it2);
00321                         }
00322                         relation.removeRowsAndCols(positions,positions);*/
00323                         removeElementsAt(positions);
00324                         return positions.size();
00325                 }
00326                 void removeElementsAt(const set<size_t> &poss)  {
00327                         relation.removeRowsAndCols(poss,poss);
00328                         for (set<size_t>::const_reverse_iterator it=poss.rbegin();it!=poss.rend();++it) {
00329                                 typename std::set<T>::const_iterator it2=elements.begin();
00330                                 std::advance(it2,*it);
00331                                 elements.erase(it2);
00332                         }
00333                 }
00334                 /**
00335                   * 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
00336                   * inserted.
00337                   */
00338                 std::pair<bool,size_t> insertElement(const T &el)       {
00339                         std::pair<typename std::set<T>::iterator,bool> ins=elements.insert(el);
00340                         size_t dist=std::distance(elements.begin(),ins.first);
00341                         if (ins.second) {
00342                                 std::multiset<size_t> newEls;
00343                                 newEls.insert(dist);
00344                                 relation.insertRowsAndCols(newEls,newEls);
00345                                 return std::make_pair(true,dist);
00346                         }       else return std::make_pair(false,dist);
00347                 }
00348                 /**
00349                   * Inserts an element and initializes its relationship values, even if it was already present.
00350                   */
00351                 template<typename FunctionType> std::pair<bool,size_t> insertElement(const T &el,FunctionType fun)      {
00352                         std::pair<bool,size_t> ins=insertElement(el);
00353                         size_t pos=ins.second;
00354                         for (size_t i=0;i<elements.size();++i)  {
00355                                 const T &newEl=operator[](i);
00356                                 applyFunction(fun,pos,i,el,newEl);
00357                                 applyFunction(fun,i,pos,newEl,el);
00358                         }
00359                         return ins;
00360                 }
00361                 /**
00362                   * Inserts a set of elements into the relation. Does not initialize the actual relation.
00363                   */
00364                 size_t insertElements(const std::set<T> &els)   {
00365                         if (els.empty()) return 0;
00366                         //This code is much more complex than it should! Trying, for efficiency, to avoid multiple calls to insertElement makes things a lot harder.
00367                         //It raises the complexity level to N², but alleviates it greatly by making a single memory allocation. Multiple calls to insertElement will be
00368                         //faster only if the number of elements in the set is really large.
00369                         std::vector<size_t> added;
00370                         //std::vector<size_t> exist;
00371                         added.reserve(els.size());
00372                         for (typename std::set<T>::const_iterator it=els.begin();it!=els.end();++it)    {
00373                                 std::pair<typename std::set<T>::iterator,bool> ins=elements.insert(*it);
00374                                 size_t dist=std::distance(elements.begin(),ins.first);
00375                                 if (ins.second) {
00376                                         added.push_back(dist);
00377                                         for (std::vector<size_t>::iterator it2=added.begin();it2!=added.end();++it2) if (*it2>=dist) ++(*it2);
00378                                         //for (std::vector<size_t>::iterator it2=exist.begin();it2!=exist.end();++it2) if (*it2>=dist) ++(*it2);
00379                                 }//     else exist.push_back(dist);
00380                         }
00381                         std::sort(added.begin(),added.end());
00382                         for (size_t j=1;j<added.size();++j) added[j]-=j;
00383                         std::multiset<size_t> poss(added.begin(),added.end());
00384                         relation.insertRowsAndCols(poss,poss);
00385                         return added.size();
00386                 }
00387                 /**
00388                   * Inserts a set of elements into the relation, initializing the actual relation with a given function.
00389                   */
00390                 template<typename FunctionType> size_t insertElements(const std::set<T> &els,FunctionType fun)  {
00391                         if (els.empty()) return 0;
00392                         size_t howMany=insertElements(els);
00393                         std::set<size_t> poss;
00394                         {
00395                                 //Little scope for "begin" and "end"...
00396                                 typename std::set<T>::const_iterator begin=elements.begin(),end=elements.end();
00397                                 for (typename std::set<T>::const_iterator it=els.begin();it!=els.end();++it) poss.insert(std::distance(begin,find(begin,end,*it)));
00398                         }
00399                         std::set<size_t> nPoss;
00400                         std::set<size_t>::const_iterator begin=poss.begin(),end=poss.end();
00401                         for (size_t i=0;i<elements.size();++i) if (std::find(begin,end,i)==end) nPoss.insert(i);
00402                         vector<const T *> proxy;
00403                         proxy.reserve(poss.size());
00404                         for (std::set<size_t>::const_iterator it=begin;it!=end;++it)    {
00405                                 const T &e1=operator[](*it);
00406                                 proxy.push_back(&e1);
00407                                 size_t i=0;
00408                                 for (typename std::set<T>::const_iterator it2=elements.begin();it2!=elements.end();++it2,++i) applyFunction(fun,*it,i,e1,*it2);
00409                         }
00410                         for (std::set<size_t>::const_iterator it=nPoss.begin();it!=nPoss.end();++it)    {
00411                                 const T &e1=operator[](*it);
00412                                 typename std::vector<const T *>::const_iterator itV=proxy.begin();
00413                                 for (std::set<size_t>::const_iterator it2=poss.begin();it2!=poss.end();++it2,++itV) applyFunction(fun,*it,*it2,e1,**itV);
00414                         }
00415                         return howMany;
00416                 }
00417                 /**
00418                   * Completely resets the relation, using a new set of elements. Does not initialize the relation.
00419                   */
00420                 void setElements(const std::set<T> &newEls)     {
00421                         relation.setSize(0,0);
00422                         elements=newEls;
00423                         relation.setSize(newEls.size(),newEls.size());
00424                 }
00425                 /**
00426                   * Returns the amount of elements present in the relation.
00427                   */
00428                 inline size_t size() const      {
00429                         return elements.size();
00430                 }
00431         };
00432 
00433         namespace detail {
00434                 // generic version (specialization is after definition of CBinaryRelation):
00435                 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) {
00436                         o.getRelationValue(e1,e2)=fun(T1,T2);
00437                 }
00438 
00439                 /** Template specialization by reference type.
00440                   */
00441                 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)    {
00442                         fun(T1,T2,o.getRelationValue(e1,e2));
00443                 }
00444         }
00445 
00446 
00447 }}      //End of namespaces
00448 #endif



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:16:28 UTC 2011