00001 00027 #ifndef MSMAZES_CORE_PATTERN_N_BIT_HPP 00028 #define MSMAZES_CORE_PATTERN_N_BIT_HPP 00029 00030 #include <boost/assert.hpp> // BOOST_ASSERT 00031 #include <boost/mpl/bool.hpp> // boost::mpl::true_ 00032 #include <boost/dynamic_bitset.hpp> // boost::dynamic_bitset 00033 #include <boost/graph/adjacency_list.hpp> // boost::container_gen 00034 #include <msmazes/core/pattern/keywords.hpp> // Boost.Parameter keyword objects 00035 00036 #if BOOST_PP_LESS(BOOST_PARAMETER_MAX_ARITY, 5) 00037 #error Set BOOST_PARAMETER_MAX_ARITY to 5 or higher, please. 00038 #endif 00039 00040 // msmazes::BasePattern and msmazes::BasicCellEqualityPolicy 00041 #include <msmazes/core/pattern/base.hpp> 00042 00043 namespace msmazes { 00044 namespace _n_bit { 00045 00050 template < 00051 typename PatternType 00052 > 00053 struct PatternFormer 00054 { 00055 typedef PatternType 00056 Pattern; 00057 00058 template < 00059 typename ArgumentPack 00060 > 00061 static typename Pattern::CellIndex countCells( 00062 const ArgumentPack& p 00063 ) 00064 { 00065 return (1 << p[init_bit_count_arg]) - 2; 00066 } 00067 00068 template < 00069 typename OutputIterator 00070 , typename ArgumentPack 00071 > 00072 static void makeCells( 00073 OutputIterator cell_iterator 00074 , const ArgumentPack& p 00075 ) 00076 { 00077 typedef typename Pattern::Cell Cell; 00078 00079 const typename Cell::size_type 00080 bit_count = p[init_bit_count_arg]; 00081 const unsigned long 00082 cell_count = 1 << bit_count; 00083 const unsigned long 00084 entrance_index = p[init_entrance_cell_arg]; 00085 const unsigned long 00086 exit_index = p[init_exit_cell_arg]; 00087 00088 for (unsigned long val = 0; val < cell_count; ++val) 00089 { 00090 if ((val != entrance_index) && (val != exit_index)) 00091 { 00092 *cell_iterator = Cell(bit_count, val); 00093 ++cell_iterator; 00094 } 00095 } 00096 } 00097 00098 template < 00099 typename ArgumentPack 00100 > 00101 static bool isLegalEdge( 00102 const typename Pattern::Cell& source 00103 , const typename Pattern::Cell& target 00104 , const ArgumentPack& p 00105 ) 00106 { 00107 const typename Pattern::Cell diff = source ^ target; 00108 00109 return diff.count() == 1; 00110 } 00111 }; 00112 00117 struct parameters 00118 : boost::parameter::parameters< 00119 boost::parameter::required<keyword_tag::init_bit_count_arg> 00120 , boost::parameter::required<keyword_tag::init_entrance_cell_arg> 00121 , boost::parameter::required<keyword_tag::init_entrance_direction_arg> 00122 , boost::parameter::required<keyword_tag::init_exit_cell_arg> 00123 , boost::parameter::required<keyword_tag::init_exit_direction_arg> 00124 > 00125 { 00126 }; 00127 } // namespace _n_bit 00128 00130 00230 template < 00231 #ifndef MSMAZES_DOX 00232 typename CellContainerSelector = boost::vecS 00233 , typename Block = unsigned long 00234 , typename Allocator = std::allocator<Block> 00235 #endif /* MSMAZES_DOX */ 00236 > 00237 class NBitPattern 00238 #ifndef MSMAZES_DOX 00239 : public BasePattern< 00240 boost::undirectedS 00241 , boost::dynamic_bitset<Block,Allocator> 00242 , BasicCellEqualityPolicy 00243 , typename boost::dynamic_bitset<Block,Allocator>::size_type 00244 , typename boost::container_gen< 00245 CellContainerSelector 00246 , boost::dynamic_bitset<Block,Allocator> 00247 >::type 00248 > 00249 #endif /* MSMAZES_DOX */ 00250 { 00251 #ifndef MSMAZES_DOX 00252 private: 00253 typedef BasePattern< 00254 boost::undirectedS 00255 , boost::dynamic_bitset<Block,Allocator> 00256 , BasicCellEqualityPolicy 00257 , typename boost::dynamic_bitset<Block,Allocator>::size_type 00258 , typename boost::container_gen< 00259 CellContainerSelector 00260 , boost::dynamic_bitset<Block,Allocator> 00261 >::type 00262 > 00263 ParentPattern; 00264 #endif /* MSMAZES_DOX */ 00265 00266 public: 00271 #ifdef MSMAZES_DOX 00272 typedef implementation_defined Cell; 00273 #else 00274 typedef typename ParentPattern::Cell 00275 Cell; 00276 #endif /* MSMAZES_DOX */ 00277 00283 #ifdef MSMAZES_DOX 00284 typedef implementation_defined CellEqualityPolicy; 00285 #else 00286 typedef typename ParentPattern::CellEqualityPolicy 00287 CellEqualityPolicy; 00288 #endif /* MSMAZES_DOX */ 00289 00295 #ifdef MSMAZES_DOX 00296 typedef implementation_defined Graph; 00297 #else 00298 typedef typename ParentPattern::Graph 00299 Graph; 00300 #endif /* MSMAZES_DOX */ 00301 00307 #ifdef MSMAZES_DOX 00308 typedef implementation_defined CellIndex; 00309 #else 00310 typedef typename ParentPattern::CellIndex 00311 CellIndex; 00312 #endif /* MSMAZES_DOX */ 00313 00319 #ifdef MSMAZES_DOX 00320 typedef implementation_defined EdgeDirectedCategory; 00321 #else 00322 typedef typename ParentPattern::EdgeDirectedCategory 00323 EdgeDirectedCategory; 00324 #endif /* MSMAZES_DOX */ 00325 00331 #ifdef MSMAZES_DOX 00332 typedef implementation_defined Direction; 00333 #else 00334 typedef typename ParentPattern::Direction 00335 Direction; 00336 #endif /* MSMAZES_DOX */ 00337 00343 #ifdef MSMAZES_DOX 00344 typedef implementation_defined OutDegree; 00345 #else 00346 typedef Direction 00347 OutDegree; 00348 #endif /* MSMAZES_DOX */ 00349 00355 #ifdef MSMAZES_DOX 00356 typedef implementation_defined HasIndexableEndpointCells; 00357 #else 00358 typedef boost::mpl::true_ 00359 HasIndexableEndpointCells; 00360 #endif /* MSMAZES_DOX */ 00361 00362 private: 00363 OutDegree _max_out_degree; 00364 Cell _entrance_cell; 00365 CellIndex _source_index; 00366 CellIndex _target_index; 00367 Cell _exit_cell; 00368 00369 NBitPattern(const NBitPattern& copy) 00370 { 00371 } 00372 00373 public: 00375 00379 NBitPattern() 00380 : ParentPattern() 00381 , _max_out_degree() 00382 , _entrance_cell() 00383 , _source_index() 00384 , _target_index() 00385 , _exit_cell() 00386 { 00387 } 00388 00390 00393 virtual ~NBitPattern() 00394 { 00395 } 00396 00397 #ifdef MSMAZES_DOX 00398 00481 void initialize( 00482 const unsigned long init_bit_count_arg 00483 , const unsigned long init_entrance_cell_arg 00484 , const unsigned long init_exit_cell_arg 00485 , const unsigned long init_entrance_direction_arg 00486 , const unsigned long init_exit_direction_arg 00487 ); 00488 00495 template <typename Params> 00496 void initialize_with_named_params(Params& p) 00497 #else 00498 BOOST_PARAMETER_MEMFUN( 00499 void 00500 , initialize 00501 , 5 00502 , 5 00503 , _n_bit::parameters 00504 ) 00505 #endif /* MSMAZES_DOX */ 00506 { 00507 _max_out_degree = p[init_bit_count_arg]; 00508 00509 unsigned long index = (1 << _max_out_degree) - 2; 00510 00511 const unsigned long entrance_val = p[init_entrance_cell_arg]; 00512 const unsigned long exit_val = p[init_exit_cell_arg]; 00513 00514 BOOST_ASSERT( 00515 (entrance_val < (index + 2)) 00516 && "Your entrance cell is out of bounds." 00517 ); 00518 BOOST_ASSERT( 00519 (exit_val < (index + 2)) 00520 && "Your exit cell is out of bounds." 00521 ); 00522 BOOST_ASSERT( 00523 (entrance_val != exit_val) 00524 && "Your entrance and exit cells cannot be equal." 00525 ); 00526 00527 ParentPattern::initializeWithPatternFormer( 00528 _n_bit::PatternFormer<NBitPattern>() 00529 , p 00530 ); 00531 _entrance_cell = Cell(_max_out_degree, entrance_val); 00532 _source_index = 0; 00533 _target_index = 0; 00534 _exit_cell = Cell(_max_out_degree, exit_val); 00535 00536 const Direction entrance_direction = p[init_entrance_direction_arg]; 00537 const Direction exit_direction = p[init_exit_direction_arg]; 00538 00539 BOOST_ASSERT( 00540 (entrance_direction < _max_out_degree) 00541 && "Your entrance direction is out of bounds." 00542 ); 00543 BOOST_ASSERT( 00544 (exit_direction < _max_out_degree) 00545 && "Your exit direction is out of bounds." 00546 ); 00547 00548 const unsigned long diff = entrance_val ^ exit_val; 00549 00550 BOOST_ASSERT( 00551 (diff != (1UL << entrance_direction)) 00552 && (diff != (1UL << exit_direction)) 00553 && "Your entrance and exit cells cannot be connected to each other." 00554 ); 00555 00556 while (index > 0) 00557 { 00558 const Cell& cell = getCell(--index); 00559 00560 if ( 00561 _n_bit::PatternFormer<NBitPattern>::isLegalEdge( 00562 _entrance_cell 00563 , cell 00564 , p 00565 ) 00566 && ( 00567 getEdgeDirectionDerived(_entrance_cell, cell) 00568 == entrance_direction 00569 ) 00570 ) 00571 { 00572 _source_index = index; 00573 } 00574 00575 if ( 00576 _n_bit::PatternFormer<NBitPattern>::isLegalEdge( 00577 cell 00578 , _exit_cell 00579 , p 00580 ) 00581 && ( 00582 getEdgeDirectionDerived(cell, _exit_cell) 00583 == exit_direction 00584 ) 00585 ) 00586 { 00587 _target_index = index; 00588 } 00589 } 00590 } 00591 00598 inline const Graph& getGraph() const 00599 { 00600 return ParentPattern::getGraph(); 00601 } 00602 00608 inline CellIndex getCellCount() const 00609 { 00610 return ParentPattern::getCellCount(); 00611 } 00612 00618 inline const Cell& getCell(const CellIndex index) const 00619 { 00620 return ParentPattern::getCell(index); 00621 } 00622 00628 inline const Cell& getEntranceCell() const 00629 { 00630 return _entrance_cell; 00631 } 00632 00639 inline const Cell& getSourceCell() const 00640 { 00641 return getCell(_source_index); 00642 } 00643 00650 inline const Cell& getTargetCell() const 00651 { 00652 return getCell(_target_index); 00653 } 00654 00660 inline const Cell& getExitCell() const 00661 { 00662 return _exit_cell; 00663 } 00664 00665 #ifndef MSMAZES_DOX 00666 protected: 00667 Direction 00668 getEdgeDirectionDerived( 00669 const Cell& source 00670 , const Cell& target 00671 ) const 00672 { 00673 const Cell diff = source ^ target; 00674 00675 return diff.find_first(); 00676 } 00677 00678 public: 00679 #endif /* MSMAZES_DOX */ 00680 00686 Direction 00687 getEdgeDirection( 00688 const CellIndex source_index 00689 , const CellIndex target_index 00690 ) const 00691 { 00692 return ParentPattern::getEdgeDirection(source_index, target_index); 00693 } 00694 00700 inline OutDegree getMaxOutDegree() const 00701 { 00702 return _max_out_degree; 00703 } 00704 }; 00705 } // namespace msmazes 00706 00707 #endif /* MSMAZES_CORE_PATTERN_N_BIT_HPP */
Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.