Changeset 383:a8a22a96d495 in lemon-1.2
- Timestamp:
- 11/21/08 11:10:25 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/elevator.h
r382 r383 28 28 /// 29 29 30 #include <test/test_tools.h> 30 #include <lemon/bits/traits.h> 31 31 32 namespace lemon { 32 33 … … 45 46 ///\sa LinkedElevator 46 47 /// 47 ///\param Graph the underlying graph type48 ///\param Graph Type of the underlying graph. 48 49 ///\param Item Type of the items the data is assigned to (Graph::Node, 49 ///Graph:: Edge, Graph::UEdge)50 ///Graph::Arc, Graph::Edge). 50 51 template<class Graph, class Item> 51 52 class Elevator … … 101 102 ///Constructor with given maximum level. 102 103 /// 103 ///\param g The underlying graph104 ///\param max_level Set the range of the possible labels to105 /// [0...\c max_level]106 Elevator(const Graph &g ,int max_level) :107 _g(g ),104 ///\param graph The underlying graph. 105 ///\param max_level The maximum allowed level. 106 ///Set the range of the possible labels to <tt>[0..max_level]</tt>. 107 Elevator(const Graph &graph,int max_level) : 108 _g(graph), 108 109 _max_level(max_level), 109 110 _item_num(_max_level), 110 _where(g ),111 _level(g ,0),111 _where(graph), 112 _level(graph,0), 112 113 _items(_max_level), 113 114 _first(_max_level+2), … … 118 119 ///Constructor. 119 120 /// 120 ///\param g The underlying graph121 /// The range of the possible labels is [0...\c max_level],121 ///\param graph The underlying graph. 122 ///Set the range of the possible labels to <tt>[0..max_level]</tt>, 122 123 ///where \c max_level is equal to the number of labeled items in the graph. 123 Elevator(const Graph &g ) :124 _g(g ),125 _max_level(countItems<Graph, Item>(g )),124 Elevator(const Graph &graph) : 125 _g(graph), 126 _max_level(countItems<Graph, Item>(graph)), 126 127 _item_num(_max_level), 127 _where(g ),128 _level(g ,0),128 _where(graph), 129 _level(graph,0), 129 130 _items(_max_level), 130 131 _first(_max_level+2), … … 168 169 return _first[l+1]-_first[l]; 169 170 } 170 ///Return true if the level is empty.171 ///Return true if level \c l is empty. 171 172 bool emptyLevel(int l) const 172 173 { … … 183 184 return _last_active[l]-_first[l]+1; 184 185 } 185 ///Return true if there is no tactive item on level \c l.186 ///Return true if there is no active item on level \c l. 186 187 bool activeFree(int l) const 187 188 { … … 202 203 ///Return a highest level active item. 203 204 204 ///Return a highest level active item. 205 /// 206 ///\return the highest level active item or INVALID if there is no active 205 ///Return a highest level active item or INVALID if there is no active 207 206 ///item. 208 207 Item highestActive() const … … 211 210 } 212 211 213 ///Return a highest active level. 214 215 ///Return a highest active level. 216 /// 217 ///\return the level of the highest active item or -1 if there is no active 212 ///Return the highest active level. 213 214 ///Return the level of the highest active item or -1 if there is no active 218 215 ///item. 219 216 int highestActiveLevel() const … … 234 231 } 235 232 236 ///Lift the highest active item .233 ///Lift the highest active item to the given level. 237 234 238 235 ///Lift the item returned by highestActive() to level \c new_level. … … 256 253 } 257 254 258 ///Lift the highest active item .255 ///Lift the highest active item to the top level. 259 256 260 257 ///Lift the item returned by highestActive() to the top level and 261 ///deactivates it. 262 /// 263 ///\warning \c new_level must be strictly higher 264 ///than the current level. 265 /// 258 ///deactivate it. 266 259 void liftHighestActiveToTop() 267 260 { … … 290 283 ///@{ 291 284 292 ///Returns an active item on level \c l. 293 294 ///Returns an active item on level \c l. 295 /// 296 ///Returns an active item on level \c l or \ref INVALID if there is no such 285 ///Return an active item on level \c l. 286 287 ///Return an active item on level \c l or \ref INVALID if there is no such 297 288 ///an item. (\c l must be from the range [0...\c max_level]. 298 289 Item activeOn(int l) const … … 301 292 } 302 293 303 ///Lift s the active item returned by \c activeOn() member function.304 305 ///Lift s the active item returned by \c activeOn() member function294 ///Lift the active item returned by \c activeOn(level) by one. 295 296 ///Lift the active item returned by \ref activeOn() "activeOn(level)" 306 297 ///by one. 307 298 Item liftActiveOn(int level) … … 313 304 } 314 305 315 ///Lift s the active item returned by \c activeOn() member function.316 317 ///Lift s the active item returned by \c activeOn() member function306 ///Lift the active item returned by \c activeOn(level) to the given level. 307 308 ///Lift the active item returned by \ref activeOn() "activeOn(level)" 318 309 ///to the given level. 319 310 void liftActiveOn(int level, int new_level) … … 332 323 } 333 324 334 ///Lift s the active item returned by \c activeOn() member function.335 336 ///Lift s the active item returned by \c activeOn() member function337 ///to the top level .325 ///Lift the active item returned by \c activeOn(level) to the top level. 326 327 ///Lift the active item returned by \ref activeOn() "activeOn(level)" 328 ///to the top level and deactivate it. 338 329 void liftActiveToTop(int level) 339 330 { … … 385 376 ///Move an inactive item to the top but one level (in a dirty way). 386 377 387 ///This function moves an inactive item to the top but one level. 388 ///It makes the underlying datastructure corrupt, so use is only if 389 ///you really know what it is for. 378 ///This function moves an inactive item from the top level to the top 379 ///but one level (in a dirty way). 380 ///\warning It makes the underlying datastructure corrupt, so use it 381 ///only if you really know what it is for. 390 382 ///\pre The item is on the top level. 391 383 void dirtyTopButOne(Item i) { … … 393 385 } 394 386 395 ///Lift all items on and above a level to the top (and deactivate them).396 397 ///This function lifts all items on and above level \c l to \c398 /// maxLevel(), and alsodeactivates them.387 ///Lift all items on and above the given level to the top level. 388 389 ///This function lifts all items on and above level \c l to the top 390 ///level and deactivates them. 399 391 void liftToTop(int l) 400 392 { … … 421 413 422 414 ///\name Initialization 423 ///Using th is function you can initialize the levels of the item.415 ///Using these functions you can initialize the levels of the items. 424 416 ///\n 425 ///This initializatios is started with calling \c initStart(). 426 ///Then the 427 ///items should be listed levels by levels statring with the lowest one 428 ///(with level 0). This is done by using \c initAddItem() 429 ///and \c initNewLevel(). Finally \c initFinish() must be called. 430 ///The items not listed will be put on the highest level. 417 ///The initialization must be started with calling \c initStart(). 418 ///Then the items should be listed level by level starting with the 419 ///lowest one (level 0) using \c initAddItem() and \c initNewLevel(). 420 ///Finally \c initFinish() must be called. 421 ///The items not listed are put on the highest level. 431 422 ///@{ 432 423 433 424 ///Start the initialization process. 434 435 425 void initStart() 436 426 { … … 450 440 451 441 ///Add an item to the current level. 452 453 442 void initAddItem(Item i) 454 443 { … … 470 459 471 460 ///Finalize the initialization process. 472 473 461 void initFinish() 474 462 { … … 501 489 ///\sa Elevator 502 490 /// 503 ///\param Graph the underlying graph type491 ///\param Graph Type of the underlying graph. 504 492 ///\param Item Type of the items the data is assigned to (Graph::Node, 505 ///Graph:: Edge, Graph::UEdge)493 ///Graph::Arc, Graph::Edge). 506 494 template <class Graph, class Item> 507 495 class LinkedElevator { … … 534 522 ///Constructor with given maximum level. 535 523 /// 536 ///\param g The underlying graph537 ///\param max_level Set the range of the possible labels to538 /// [0...\c max_level]524 ///\param graph The underlying graph. 525 ///\param max_level The maximum allowed level. 526 ///Set the range of the possible labels to <tt>[0..max_level]</tt>. 539 527 LinkedElevator(const Graph& graph, int max_level) 540 528 : _graph(graph), _max_level(max_level), _item_num(_max_level), … … 547 535 ///Constructor. 548 536 /// 549 ///\param g The underlying graph550 /// The range of the possible labels is [0...\c max_level],537 ///\param graph The underlying graph. 538 ///Set the range of the possible labels to <tt>[0..max_level]</tt>, 551 539 ///where \c max_level is equal to the number of labeled items in the graph. 552 540 LinkedElevator(const Graph& graph) … … 658 646 } 659 647 660 ///Return true if there is no tactive item on level \c l.648 ///Return true if there is no active item on level \c l. 661 649 bool activeFree(int l) const { 662 650 return _first[l] == INVALID || !_active[_first[l]]; … … 676 664 ///Return a highest level active item. 677 665 678 ///Return a highest level active item. 679 /// 680 ///\return the highest level active item or INVALID if there is no 681 ///active item. 666 ///Return a highest level active item or INVALID if there is no active 667 ///item. 682 668 Item highestActive() const { 683 669 return _highest_active >= 0 ? _first[_highest_active] : INVALID; 684 670 } 685 671 686 ///Return a highest active level. 687 688 ///Return a highest active level. 689 /// 690 ///\return the level of the highest active item or -1 if there is 691 ///no active item. 672 ///Return the highest active level. 673 674 ///Return the level of the highest active item or -1 if there is no active 675 ///item. 692 676 int highestActiveLevel() const { 693 677 return _highest_active; … … 720 704 } 721 705 722 ///Lift the highest active item .706 ///Lift the highest active item to the given level. 723 707 724 708 ///Lift the item returned by highestActive() to level \c new_level. … … 748 732 } 749 733 750 ///Lift the highest active to top.734 ///Lift the highest active item to the top level. 751 735 752 736 ///Lift the item returned by highestActive() to the top level and 753 ///deactivates the item. 754 /// 737 ///deactivate it. 755 738 void liftHighestActiveToTop() { 756 739 Item i = _first[_highest_active]; … … 774 757 ///@{ 775 758 776 ///Returns an active item on level \c l. 777 778 ///Returns an active item on level \c l. 779 /// 780 ///Returns an active item on level \c l or \ref INVALID if there is no such 759 ///Return an active item on level \c l. 760 761 ///Return an active item on level \c l or \ref INVALID if there is no such 781 762 ///an item. (\c l must be from the range [0...\c max_level]. 782 763 Item activeOn(int l) const … … 785 766 } 786 767 787 ///Lift s the active item returned by \c activeOn() member function.788 789 ///Lift s the active item returned by \c activeOn() member function768 ///Lift the active item returned by \c activeOn(l) by one. 769 770 ///Lift the active item returned by \ref activeOn() "activeOn(l)" 790 771 ///by one. 791 772 Item liftActiveOn(int l) … … 814 795 } 815 796 816 /// \brief Lifts the active item returned by \c activeOn() member function.817 /// 818 /// Lifts the active item returned by \c activeOn() member function819 /// 797 ///Lift the active item returned by \c activeOn(l) to the given level. 798 799 ///Lift the active item returned by \ref activeOn() "activeOn(l)" 800 ///to the given level. 820 801 void liftActiveOn(int l, int new_level) 821 802 { … … 843 824 } 844 825 845 ///Lift s the active item returned by \c activeOn() member function.846 847 ///Lift s the active item returned by \c activeOn() member function848 ///to the top level .826 ///Lift the active item returned by \c activeOn(l) to the top level. 827 828 ///Lift the active item returned by \ref activeOn() "activeOn(l)" 829 ///to the top level and deactivate it. 849 830 void liftActiveToTop(int l) 850 831 { … … 901 882 ///Move an inactive item to the top but one level (in a dirty way). 902 883 903 ///This function moves an inactive item to the top but one level. 904 ///It makes the underlying datastructure corrupt, so use is only if 905 ///you really know what it is for. 884 ///This function moves an inactive item from the top level to the top 885 ///but one level (in a dirty way). 886 ///\warning It makes the underlying datastructure corrupt, so use it 887 ///only if you really know what it is for. 906 888 ///\pre The item is on the top level. 907 889 void dirtyTopButOne(Item i) { … … 909 891 } 910 892 911 ///Lift all items on and above a level to the top (and deactivate them).912 913 ///This function lifts all items on and above level \c l to \c914 /// maxLevel(), and alsodeactivates them.893 ///Lift all items on and above the given level to the top level. 894 895 ///This function lifts all items on and above level \c l to the top 896 ///level and deactivates them. 915 897 void liftToTop(int l) { 916 898 for (int i = l + 1; _first[i] != INVALID; ++i) { … … 937 919 938 920 ///\name Initialization 939 ///Using th is function you can initialize the levels of the item.921 ///Using these functions you can initialize the levels of the items. 940 922 ///\n 941 ///This initializatios is started with calling \c initStart(). 942 ///Then the 943 ///items should be listed levels by levels statring with the lowest one 944 ///(with level 0). This is done by using \c initAddItem() 945 ///and \c initNewLevel(). Finally \c initFinish() must be called. 946 ///The items not listed will be put on the highest level. 923 ///The initialization must be started with calling \c initStart(). 924 ///Then the items should be listed level by level starting with the 925 ///lowest one (level 0) using \c initAddItem() and \c initNewLevel(). 926 ///Finally \c initFinish() must be called. 927 ///The items not listed are put on the highest level. 947 928 ///@{ 948 929 949 930 ///Start the initialization process. 950 951 931 void initStart() { 952 932 … … 963 943 964 944 ///Add an item to the current level. 965 966 945 void initAddItem(Item i) { 967 946 _level.set(i, _init_level); … … 988 967 989 968 ///Finalize the initialization process. 990 991 969 void initFinish() { 992 970 _highest_active = -1;
Note: See TracChangeset
for help on using the changeset viewer.