00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #ifndef DOMAIN_MAP_H
00012 #define DOMAIN_MAP_H
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066 #include "Utility/Pooled.h"
00067 #include "Utility/PAssert.h"
00068
00069 #ifdef IPPL_STDSTL
00070
00071 #include <list>
00072 using std::list;
00073 #include <iterator>
00074 #ifndef __MWERKS__
00075
00076 #endif
00077
00078 #include <utility>
00079 using std::pair;
00080
00081 #else
00082
00083 #include <list.h>
00084 #include <iterator.h>
00085 #include <pair.h>
00086
00087 #endif // IPPL_STDSTL
00088
00089 #include <stddef.h>
00090
00091 template < class Key, class T , class Touches, class Contains, class Split >
00092 class DomainMap
00093 {
00094 public:
00095 typedef DomainMap<Key,T,Touches,Contains,Split> DomainMap_t;
00096 typedef unsigned size_type;
00097
00098 typedef Key key_type;
00099 typedef T mapped_type;
00100
00101 struct value_type {
00102 Key first;
00103 T second;
00104 value_type() {}
00105 value_type(const Key& k, const T& t)
00106 : first(k),
00107 second(t){
00108 }
00109 };
00110
00111
00112 private:
00113
00114
00115
00116 class Node : public Pooled<Node>
00117 {
00118 public:
00119 typedef list<value_type> cont_type;
00120 Key MyDomain;
00121 Node *Left,*Right;
00122 Node *Parent;
00123 cont_type cont;
00124
00125
00126 Node(const Key& d, Node* p=0) : MyDomain(d),Left(0),Right(0),Parent(p) {}
00127
00128 ~Node() {
00129 if (Left ) delete Left;
00130 if (Right) delete Right;
00131 }
00132
00133
00134
00135
00137
00138
00139
00140
00141
00142 void insert(const value_type& d, bool noSplit=false) {
00143 TAU_TYPE_STRING(taustr, CT(*this) + " void (value_type)");
00144 TAU_PROFILE("DomainMap::Node::insert()", taustr, TAU_DOMAINMAP);
00145
00146 Key left_domain;
00147 Key right_domain;
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157 if (noSplit) {
00158 cont.push_back(d);
00159 return;
00160 }
00161
00162
00163
00164
00165 if ( Left && Right ) {
00166
00167 if ( Contains::test(Left->MyDomain,d.first) )
00168 Left->insert(d);
00169 else if ( Contains::test(Right->MyDomain,d.first) )
00170 Right->insert(d);
00171 else
00172 cont.push_back(d);
00173
00174 }
00175 else if ( Left==0 && Right==0 ) {
00176
00177 if ( Split::test(left_domain, right_domain, MyDomain) ) {
00178 if ( Contains::test(left_domain, d.first) ) {
00179
00180 Left = new Node( left_domain, this );
00181 Left->insert(d);
00182 }
00183 else if ( Contains::test(right_domain, d.first) ) {
00184
00185 Right = new Node( right_domain, this );
00186 Right->insert(d);
00187 }
00188 else {
00189
00190 cont.push_back(d);
00191 }
00192 }
00193 else {
00194
00195 cont.push_back(d);
00196 }
00197
00198 }
00199 else if ( Right ) {
00200
00201 if ( Contains::test(Right->MyDomain, d.first) ) {
00202
00203 Right->insert(d);
00204 }
00205 else {
00206
00207 Split::test(left_domain, right_domain, MyDomain);
00208 if ( Contains::test(left_domain,d.first) ) {
00209
00210 Left = new Node( left_domain, this );
00211 Left->insert(d);
00212 }
00213 else {
00214
00215 cont.push_back(d);
00216 }
00217 }
00218
00219 }
00220 else if ( Left ) {
00221
00222 if ( Contains::test(Left->MyDomain, d.first) ) {
00223
00224 Left->insert(d);
00225 }
00226 else {
00227
00228 Split::test(left_domain,right_domain,MyDomain);
00229 if ( Contains::test(right_domain,d.first) ) {
00230
00231 Right = new Node( right_domain, this );
00232 Right->insert(d);
00233 }
00234 else {
00235
00236 cont.push_back(d);
00237 }
00238 }
00239 }
00240 }
00241
00242 };
00243
00244 friend class Node;
00245
00246 public:
00247
00248
00249 class const_iterator;
00250
00251
00252
00253 class iterator {
00254 friend class DomainMap<Key,T,Touches,Contains,Split>;
00255 friend class const_iterator;
00256
00257 public:
00258
00259
00260 iterator() : p(0) { }
00261
00262
00263 iterator(Node *pp, typename Node::cont_type::iterator vv)
00264 : p(pp), v(vv)
00265 {
00266 }
00267
00268
00269 bool operator==(const iterator& rhs) const
00270 {
00271 return (p==rhs.p)&&((p==0)||(v==rhs.v));
00272 }
00273 bool operator!=(const iterator& rhs) const
00274 {
00275 return !(*this == rhs);
00276 }
00277
00278
00279 value_type& operator*()
00280 {
00281 PAssert(p != 0);
00282 return *v;
00283 }
00284
00285
00286 iterator& operator++() { op_pp(); return *this; }
00287
00288
00289
00291
00292 void op_pp()
00293 {
00294 TAU_TYPE_STRING(taustr, CT(*this) + " void ()");
00295 TAU_PROFILE("DomainMap::iterator::op_pp()", taustr, TAU_DOMAINMAP);
00296
00297 PAssert(p != 0);
00298
00299 if ( (++v) == p->cont.end() ) {
00300
00301 do {
00302
00303 if ( p->Right ) {
00304
00305 p = p->Right;
00306 while ( p->Left )
00307 p = p->Left;
00308 }
00309 else {
00310
00311 Node *y = p->Parent;
00312 while (y && (p==y->Right)) {
00313 p = y;
00314 y = y->Parent;
00315 }
00316 p = y;
00317 }
00318
00319 } while (p && ((v=p->cont.begin())==p->cont.end()));
00320 }
00321 }
00322 Node *p;
00323 typename Node::cont_type::iterator v;
00324 };
00325
00326
00327 class const_iterator {
00328 friend class DomainMap<Key,T,Touches,Contains,Split>;
00329
00330 public:
00331
00332 const_iterator() : p(0) {}
00333
00334
00335 const_iterator(Node *pp, typename Node::cont_type::iterator vv)
00336 : p(pp), v(vv) {}
00337
00338
00339 const_iterator(const iterator& iter) : p(iter.p), v(iter.v) {}
00340
00341
00342 bool operator==(const const_iterator& rhs) const
00343 {
00344 return (p==rhs.p)&&((p==0)||(v==rhs.v));
00345 }
00346 bool operator!=(const const_iterator& rhs) const
00347 {
00348 return !(*this == rhs);
00349 }
00350
00351
00352 value_type operator*() const
00353 {
00354 PAssert(p != 0);
00355 return *v;
00356 }
00357
00358
00359 const_iterator& operator++() { op_pp(); return *this; }
00360
00361 private:
00362
00364
00365 void op_pp()
00366 {
00367 TAU_TYPE_STRING(taustr, CT(*this) + " void ()");
00368 TAU_PROFILE("DomainMap::const_iterator::op_pp()", taustr, TAU_DOMAINMAP);
00369
00370 PAssert(p != 0);
00371
00372 if ( (++v) == p->cont.end() ) {
00373
00374 do {
00375
00376 if ( p->Right ) {
00377
00378 p = p->Right;
00379 while ( p->Left )
00380 p = p->Left;
00381 }
00382 else {
00383
00384
00385 Node *y = p->Parent;
00386 while (y && (p==y->Right)) {
00387 p = y;
00388 y = y->Parent;
00389 }
00390 p = y;
00391 }
00392
00393 } while (p && ((v=p->cont.begin())==p->cont.end()));
00394 }
00395 }
00396 Node *p;
00397 typename Node::cont_type::iterator v;
00398 };
00399
00400
00401
00402 class touch_iterator {
00403 friend class DomainMap<Key,T,Touches,Contains,Split>;
00404 public:
00405
00406 typedef forward_iterator_tag iterator_category;
00407 typedef typename DomainMap_t::value_type value_type;
00408 typedef typename DomainMap_t::value_type *pointer;
00409 typedef typename DomainMap_t::value_type &reference;
00410 typedef ptrdiff_t difference_type;
00411
00412
00413 touch_iterator() : p(0) { }
00414
00415
00416 bool operator==(const touch_iterator& rhs) const
00417 {
00418 return (p==rhs.p)&&((p==0)||(v==rhs.v));
00419 }
00420 bool operator!=(const touch_iterator& rhs) const
00421 {
00422 return !(*this == rhs);
00423 }
00424
00425
00426 value_type& operator*()
00427 {
00428 PAssert(p != 0);
00429 return *v;
00430 }
00431
00432 value_type* operator->()
00433 {
00434 PAssert(p != 0);
00435 return &(*v);
00436 }
00437
00438
00439 operator iterator()
00440 {
00441 return iterator(p,v);
00442 }
00443
00444
00445 touch_iterator& operator++() { op_pp(); return *this; }
00446
00447 private:
00448
00450
00451 void op_pp()
00452 {
00453 TAU_TYPE_STRING(taustr, CT(*this) + " void ()");
00454 TAU_PROFILE("DomainMap::iterator::op_pp()", taustr, TAU_DOMAINMAP);
00455
00456 PAssert(p != 0);
00457
00458
00459 while ( (++v) != p->cont.end() )
00460 if ( Touches::test(TouchThis,(*v).first) )
00461 return;
00462
00463 do {
00464
00465
00466
00467 Node *y = p->Right;
00468 if ( y && Touches::test(TouchThis,y->MyDomain) ) {
00469
00470 p = y;
00471 for (y=y->Left; y && Touches::test(TouchThis,y->MyDomain); y=y->Left )
00472 p = y;
00473 }
00474 else {
00475
00476
00477
00478 for (y=p->Parent; y && (p==y->Right); y=y->Parent)
00479 p = y;
00480 p = y;
00481 }
00482
00483 if (p) {
00484 for ( v = p->cont.begin() ; v != p->cont.end() ; ++v )
00485 if ( Touches::test(TouchThis,(*v).first) )
00486 return;
00487 }
00488
00489 } while (p);
00490
00491 }
00492 Node *p;
00493 typename Node::cont_type::iterator v;
00494 Key TouchThis;
00495 };
00496
00497
00498
00499
00500
00501
00502 DomainMap(const Key& d)
00503 : Root(new Node(d)), Size(0)
00504 {
00505 }
00506
00507 DomainMap()
00508 : Root(0), Size(0)
00509 {
00510 }
00511
00512
00513 DomainMap( const DomainMap<Key,T,Touches,Contains,Split>& );
00514 void operator=(const DomainMap<Key,T,Touches,Contains,Split>& );
00515
00516
00517 ~DomainMap() { delete Root; }
00518
00519
00520 iterator begin() { return Leftmost; }
00521 iterator end() { return iterator(); }
00522 const_iterator begin() const { return const_iterator(Leftmost); }
00523 const_iterator end() const { return const_iterator(); }
00524
00525
00526
00527 void insert(const value_type& d, bool noSplit=false);
00528
00529
00530 pair<touch_iterator,touch_iterator> touch_range(const Key& t) const;
00531
00532
00533 size_type size() const { return Size; }
00534
00535 private:
00536
00537 friend class iterator;
00538 friend class const_iterator;
00539 friend class touch_iterator;
00540
00541 Touches touches;
00542 Contains contains;
00543 Split split;
00544
00545 Node* Root;
00546 iterator Leftmost;
00547 unsigned Size;
00548
00549
00550 void insert_noupdate(const value_type& d)
00551 {
00552 Root->insert(d);
00553 Size += 1;
00554 }
00555
00556 void update_leftmost();
00557 };
00558
00560
00561 #include "DomainMap/DomainMap.cpp"
00562
00563 #endif // DOMAIN_MAP_H
00564
00565
00566
00567
00568
00569