00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
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
00044
00045
00046
00047
00048
00049 template<typename T,typename U,bool UIsObject=false> class CBinaryRelation {
00050 private:
00051
00052
00053 typedef typename detail::MatrixWrapper<U,UIsObject>::MatrixType MatrixType;
00054 public:
00055 typedef U (*SimpleFunctionByReturnValue)(T,T);
00056 typedef U (*FunctionByReturnValue)(const T &,const T &);
00057 typedef void (*FunctionByReferencePass)(const T &,const T &,U &);
00058 typedef typename std::set<T>::const_iterator const_iterator;
00059 typedef typename std::set<T>::const_reverse_iterator const_reverse_iterator;
00060 typedef CMatrixRowAccessor<U> AccessorForFirstElement;
00061 typedef CMatrixColumnAccessor<U> AccessorForSecondElement;
00062 typedef CConstMatrixRowAccessor<U> ConstAccessorForFirstElement;
00063 typedef CConstMatrixColumnAccessor<U> ConstAccessorForSecondElement;
00064 private:
00065 std::set<T> elements;
00066 MatrixType relation;
00067
00068
00069
00070
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
00079
00080 explicit inline CBinaryRelation(const std::set<T> &els):elements(els),relation(els.size(),els.size()) {}
00081
00082
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
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
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
00114
00115 inline void setRelationValue(size_t e1,size_t e2,const U &newVal) {
00116 relation.get_unsafe(e1,e2)=newVal;
00117 }
00118
00119
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
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
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
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
00157
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
00167
00168 inline const_iterator begin() const {
00169 return elements.begin();
00170 }
00171
00172
00173
00174 inline const_iterator end() const {
00175 return elements.end();
00176 }
00177
00178
00179
00180 inline const_reverse_iterator rbegin() const {
00181 return elements.rbegin();
00182 }
00183
00184
00185
00186 inline const_reverse_iterator rend() const {
00187 return elements.rend();
00188 }
00189
00190
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
00200
00201 inline AccessorForFirstElement getRelationFrom(size_t i) {
00202 return AccessorForFirstElement(relation,i);
00203 }
00204
00205
00206
00207 inline ConstAccessorForFirstElement getRelationFrom(size_t i) const {
00208 return ConstAccessorForFirstElement(relation,i);
00209 }
00210
00211
00212
00213 inline AccessorForSecondElement getRelationTo(size_t i) {
00214 return AccessorForSecondElement(relation,i);
00215 }
00216
00217
00218
00219 inline ConstAccessorForSecondElement getRelationTo(size_t i) const {
00220 return ConstAccessorForSecondElement(relation,i);
00221 }
00222
00223
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
00233
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
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
00265
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
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
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
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
00318
00319
00320
00321
00322
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
00336
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
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
00363
00364 size_t insertElements(const std::set<T> &els) {
00365 if (els.empty()) return 0;
00366
00367
00368
00369 std::vector<size_t> added;
00370
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
00379 }
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
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
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
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
00427
00428 inline size_t size() const {
00429 return elements.size();
00430 }
00431 };
00432
00433 namespace detail {
00434
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
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 }}
00448 #endif