00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #ifndef __VGTL_DAGBASE_H_
00031 #define __VGTL_DAGBASE_H_
00032
00033 #include <vgtl_helpers.h>
00034 #include <vgtl_intadapt.h>
00035
00036 __VGTL_BEGIN_NAMESPACE
00037
00039
00043 template <class _Tp, class _Ctr, class _Iterator>
00044 class _DG_node
00045 {
00046 private:
00047 typedef void* _Void_pointer;
00048 typedef _Iterator _Ctr_iterator;
00049 typedef _DG_node<_Tp,_Ctr,_Iterator> _Self;
00050
00051 public:
00053 _Tp _C_data;
00055 _Ctr _C_parents;
00057 _Ctr _C_children;
00059 int _C_visited;
00060
00062 _DG_node() {
00063 _C_visited=0;
00064 __VGTL_TRY {
00065 std::_Construct(&_C_data);
00066 std::_Construct(&_C_children);
00067 std::_Construct(&_C_parents);
00068 }
00069 __VGTL_UNWIND( );
00070 }
00071
00073 ~_DG_node() {
00074 std::_Destroy(&_C_data);
00075 std::_Destroy(&_C_children);
00076 std::_Destroy(&_C_parents);
00077 }
00078
00080 void clear_children()
00081 { _C_children.erase(_C_children.begin(), _C_children.end()); }
00083 void clear_parents()
00084 { _C_parents.erase(_C_parents.begin(), _C_parents.end()); }
00085
00087 _Ctr_iterator get_childentry_iterator(const _Void_pointer __p)
00088 { _Ctr_iterator __tmp;
00089 _Ctr_iterator __end = _C_children.end();
00090 for(__tmp = _C_children.begin(); __tmp != __end; ++__tmp)
00091 if(*__tmp == __p) break;
00092 return __tmp;
00093 }
00094
00096 _Ctr_iterator get_parententry_iterator(const _Void_pointer __p)
00097 { _Ctr_iterator __tmp;
00098 _Ctr_iterator __end = _C_parents.end();
00099 for(__tmp = _C_parents.begin(); __tmp != __end; ++__tmp)
00100 if(*__tmp == __p) break;
00101 return __tmp;
00102 }
00103
00104
00105 #ifdef __VGTL_MEMBER_TEMPLATES
00106
00110 template <class _Output_Iterator>
00111 void add_all_children(_Output_Iterator fi, _Self* _parent);
00112
00113
00118 template <class _Output_Iterator>
00119 void add_all_parents(_Output_Iterator fi, _Self* _child);
00120
00122 template <class Compare>
00123 void sort_child_edges(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
00124 {
00125 sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
00126 }
00127
00129 template <class Compare>
00130 void sort_parent_edges(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
00131 {
00132 sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
00133 }
00134 #endif
00135 };
00136
00137 #ifdef __VGTL_MEMBER_TEMPLATES
00138 template <class _Tp, class _Ctr, class _Iterator>
00139 template <class _Output_Iterator>
00140 inline void
00141 _DG_node<_Tp,_Ctr,_Iterator>::
00142 add_all_children(_Output_Iterator fi, _Self* _parent)
00143 { _Ctr_iterator it;
00144 for(it = _C_children.begin();
00145 it != _C_children.end();
00146 ++it)
00147 {
00148 *fi++ = *it;
00149 ((_Self*)*it)->_C_parents.insert(((_Self*)*it)->_C_parents.end(), _parent);
00150 }
00151 };
00152
00153 template <class _Tp, class _Ctr, class _Iterator>
00154 template <class _Output_Iterator>
00155 inline void
00156 _DG_node<_Tp,_Ctr,_Iterator>::
00157 add_all_parents(_Output_Iterator fi, _Self* _child)
00158 { _Ctr_iterator it;
00159 for(it = _C_parents.begin();
00160 it != _C_parents.end();
00161 ++it)
00162 {
00163 *fi++ = *it;
00164 ((_Self*)*it)->_C_children.insert(((_Self*)*it)->_C_children.end(), _child);
00165 }
00166 };
00167 #endif
00168
00169 #ifdef __VGTL_USE_STD_ALLOCATORS
00170
00172
00183 template <class _Tp, class _Ctr, class _I, class _Allocator, bool _IsStatic>
00184 class _DG_alloc_base {
00185 public:
00186 typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
00187 allocator_type;
00188 allocator_type get_allocator() const { return _Node_allocator; }
00189
00190 _DG_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
00191
00192 protected:
00194 _DG_node<_Tp,_Ctr,_I>* _C_get_node()
00195 { return _Node_allocator.allocate(1); }
00197 void _C_put_node(_DG_node<_Tp,_Ctr,_I>* __p)
00198 { _Node_allocator.deallocate(__p, 1); }
00199
00200 protected:
00201 typename std::_Alloc_traits<_DG_node<_Tp,_Ctr,_I>, _Allocator>::allocator_type
00202 _Node_allocator;
00203
00204 protected:
00206 _DG_node<_Tp,_Ctr,_I>* _C_ground;
00208 _DG_node<_Tp,_Ctr,_I>* _C_sky;
00210 int _C_mark;
00211 };
00212
00214
00225 template <class _Tp, class _Ctr, class _I, class _Allocator>
00226 class _DG_alloc_base<_Tp, _Ctr, _I, _Allocator, true> {
00227 public:
00228 typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
00229 allocator_type;
00230 allocator_type get_allocator() const { return allocator_type(); }
00231
00232 _DG_alloc_base(const allocator_type&) {}
00233
00234 protected:
00235 typedef typename std::_Alloc_traits<_DG_node<_Tp,_Ctr,_I>, _Allocator>::_Alloc_type
00236 _Alloc_type;
00238 _DG_node<_Tp,_Ctr,_I>* _C_get_node()
00239 { return _Alloc_type::allocate(1); }
00241 void _C_put_node(_DG_node<_Tp,_Ctr,_I>* __p)
00242 { _Alloc_type::deallocate(__p, 1); }
00243
00244 protected:
00246 _DG_node<_Tp,_Ctr,_I>* _C_ground;
00248 _DG_node<_Tp,_Ctr,_I>* _C_sky;
00250 int _C_mark;
00251 };
00252
00253
00255
00259 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
00260 class _DG_base
00261 : public _DG_alloc_base<_Tp, _Ctr, _Iterator, _Alloc,
00262 std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00263 {
00264 public:
00265 typedef _DG_alloc_base<_Tp, _Ctr, _Iterator, _Alloc,
00266 std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00267 _Base;
00269 typedef typename _Base::allocator_type allocator_type;
00270
00272 typedef _Ctr container_type;
00274 typedef _Iterator children_iterator;
00276 typedef _Iterator parents_iterator;
00277
00278
00280 _DG_base(const allocator_type& __a) : _Base(__a) {
00281 _C_ground = _C_get_node();
00282 _C_sky = _C_get_node();
00283 _C_mark = 0;
00284 __VGTL_TRY {
00285 std::_Construct(&_C_ground->_C_children);
00286 std::_Construct(&_C_ground->_C_parents);
00287 std::_Construct(&_C_ground->_C_data);
00288 std::_Construct(&_C_sky->_C_children);
00289 std::_Construct(&_C_sky->_C_parents);
00290 std::_Construct(&_C_sky->_C_data);
00291 }
00292 __VGTL_UNWIND(_C_put_node(_C_ground); _C_put_node(_C_sky));
00293 _C_ground->_C_children.push_back((void*)_C_sky);
00294 _C_sky->_C_parents.push_back((void*)_C_ground);
00295 _C_ground->_C_visited=0;
00296 _C_sky->_C_visited=0;
00297 }
00298
00300 ~_DG_base() {
00301 clear();
00302
00303
00304 }
00305
00306 protected:
00308 void clear_graph(_DG_node<_Tp,_Ctr,_Iterator>* _node);
00309
00310 public:
00312 void clear();
00314 void clear_children()
00315 { _C_ground->clear_children(); }
00317 void clear_parents()
00318 { _C_sky->clear_parents(); }
00319
00322 template <class _Output_Iterator>
00323 void add_all_children(_Output_Iterator fi,
00324 _DG_node<_Tp,_Ctr,_Iterator>* _parent);
00327 template <class _Output_Iterator>
00328 void add_all_parents(_Output_Iterator fi,
00329 _DG_node<_Tp,_Ctr,_Iterator>* _child);
00330 };
00331 #else
00332
00333
00335
00341 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
00342 class _DG_base
00343 {
00344 public:
00346 typedef _Alloc allocator_type;
00348 allocator_type get_allocator() const { return allocator_type(); }
00349
00351 typedef _Ctr container_type;
00353 typedef _Iterator children_iterator;
00355 typedef _Iterator parents_iterator;
00356
00358 _DG_base(const allocator_type&) {
00359 _C_ground = _C_get_node();
00360 _C_sky = _C_get_node();
00361 _C_mark = 0;
00362 __VGTL_TRY {
00363 std::_Construct(&_C_ground->_C_children);
00364 std::_Construct(&_C_ground->_C_parents);
00365 std::_Construct(&_C_sky->_C_children);
00366 std::_Construct(&_C_sky->_C_parents);
00367 }
00368 __VGTL_UNWIND(_C_put_node(_C_ground); _C_put_node(_C_sky));
00369 _C_ground->_C_children.push_back((void*)_C_sky);
00370 _C_sky->_C_parents.push_back((void*)_C_ground);
00371 _C_ground->_C_visited=0;
00372 _C_sky->_C_visited=0;
00373 }
00375 ~_DG_base() {
00376 clear();
00377
00378
00379 }
00380
00381 protected:
00383 void clear_graph(_DG_node<_Tp,_Ctr,_Iterator>* _node);
00384
00385 public:
00387 void clear();
00388
00389 protected:
00390 typedef simple_alloc<_DG_node<_Tp,_Ctr,_Iterator>, _Alloc> _Alloc_type;
00392 _DG_node<_Tp,_Ctr,_Iterator>* _C_get_node()
00393 { return _Alloc_type::allocate(1); }
00395 void _C_put_node(_DG_node<_Tp,_Ctr,_Iterator>* __p)
00396 { _Alloc_type::deallocate(__p, 1); }
00397
00398 protected:
00400 _DG_node<_Tp,_Ctr,_Iterator>* _C_ground;
00402 _DG_node<_Tp,_Ctr,_Iterator>* _C_sky;
00404 int _C_mark;
00405
00407 void clear_children()
00408 { _C_ground->clear_children(); }
00410 void clear_parents()
00411 { _C_sky->clear_parents(); }
00412
00415 template <class _Output_Iterator>
00416 void add_all_children(_Output_Iterator fi,
00417 _DG_node<_Tp,_Ctr,_Iterator>* _parent);
00420 template <class _Output_Iterator>
00421 void add_all_parents(_Output_Iterator fi,
00422 _DG_node<_Tp,_Ctr,_Iterator>* _child);
00423 };
00424
00425 #endif
00426
00427
00428 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
00429 void
00430 _DG_base<_Tp,_Ctr,_Iterator,_Alloc>::clear_graph(
00431 _DG_node<_Tp,_Ctr,_Iterator>* _node)
00432 {
00433 _Ctr* chld = &_node->_C_children;
00434 _Iterator it;
00435
00436 if(_node->_C_parents.size() <= 1)
00437 {
00438
00439 for(it = chld->begin(); it != chld->end(); ++it)
00440 clear_graph((_DG_node<_Tp,_Ctr,_Iterator>*)(*it));
00441 _node->_C_children.erase(_node->_C_children.begin(),
00442 _node->_C_children.end());
00443
00444 std::_Destroy(&_node->_C_children);
00445 std::_Destroy(&_node->_C_data);
00446 }
00447 if(_node->_C_parents.size() >= 1)
00448 _node->_C_parents.erase(_node->_C_parents.begin());
00449 if(_node->_C_parents.size() == 0)
00450 {
00451 std::_Destroy(&_node->_C_parents);
00452 _C_put_node(_node);
00453 }
00454 }
00455
00456 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
00457 template <class _Output_Iterator>
00458 inline void
00459 _DG_base<_Tp,_Ctr,_Iterator,_Alloc>::add_all_children(_Output_Iterator fi,
00460 _DG_node<_Tp,_Ctr,_Iterator>* _parent)
00461 { _C_ground->add_all_children(fi, _parent); };
00462
00463 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
00464 template <class _Output_Iterator>
00465 inline void
00466 _DG_base<_Tp,_Ctr,_Iterator,_Alloc>::add_all_parents(_Output_Iterator fi,
00467 _DG_node<_Tp,_Ctr,_Iterator>* _child)
00468 { _C_sky->add_all_parents(fi, _child); };
00469
00470 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
00471 void
00472 _DG_base<_Tp,_Ctr,_Iterator,_Alloc>::clear()
00473 {
00474 clear_graph(this->_C_ground);
00475
00476
00477
00478
00479 }
00480
00481 #if 0
00482
00483
00484
00485 template <class _Tp>
00486 class dag_node : public _DG_node<_Tp, vector<void*>, vector<void*>::iterator>
00487 {
00488 }
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527 template <class _Tp>
00528 class dag_base
00529 {
00530 protected:
00531 dag_node<_Tp>* _C_ground;
00532 dag_node<_Tp>* _C_sky;
00533 int _C_mark;
00534
00535 public:
00536 dag_base();
00537 ~dag_base();
00538
00539 private:
00540
00541 void clear_graph(dag_node<_Tp>* _node);
00542
00543 public:
00544 void clear();
00545
00546 dag_node<_Tp>* _C_get_node();
00547 void _C_put_node(dag_node<_Tp>* __p);
00548
00549 protected:
00550 void clear_children();
00551 void clear_parents();
00552
00553
00554 template <class _Output_Iterator>
00555 void add_all_children(_Output_Iterator fi, dag_node<_Tp>* _parent);
00556 void add_all_parents(_Output_Iterator fi, dag_node<_Tp>* _child);
00557 }
00558
00559 #endif
00560
00561 __VGTL_END_NAMESPACE
00562
00563
00564 #endif // __VGTL_DAGBASE_H_