r383:a8a22a96d495
Fri, 21 Nov 2008 11:10:25
[Not Reviewed]
0 comments (0 inline)
0
1
0
88
110
| ... | ... |
@@ -28,5 +28,6 @@ |
| 28 | 28 |
/// |
| 29 | 29 |
|
| 30 |
#include < |
|
| 30 |
#include <lemon/bits/traits.h> |
|
| 31 |
|
|
| 31 | 32 |
namespace lemon {
|
| 32 | 33 |
|
| ... | ... |
@@ -45,7 +46,7 @@ |
| 45 | 46 |
///\sa LinkedElevator |
| 46 | 47 |
/// |
| 47 |
///\param Graph the underlying graph |
|
| 48 |
///\param Graph Type of the underlying graph. |
|
| 48 | 49 |
///\param Item Type of the items the data is assigned to (Graph::Node, |
| 49 |
///Graph:: |
|
| 50 |
///Graph::Arc, Graph::Edge). |
|
| 50 | 51 |
template<class Graph, class Item> |
| 51 | 52 |
class Elevator |
| ... | ... |
@@ -101,13 +102,13 @@ |
| 101 | 102 |
///Constructor with given maximum level. |
| 102 | 103 |
/// |
| 103 |
///\param g The underlying graph |
|
| 104 |
///\param max_level Set the range of the possible labels to |
|
| 105 |
///[0...\c max_level] |
|
| 106 |
Elevator(const Graph &g,int max_level) : |
|
| 107 |
|
|
| 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,13 +119,13 @@ |
| 118 | 119 |
///Constructor. |
| 119 | 120 |
/// |
| 120 |
///\param g The underlying graph |
|
| 121 |
///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 |
|
|
| 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,5 +169,5 @@ |
| 168 | 169 |
return _first[l+1]-_first[l]; |
| 169 | 170 |
} |
| 170 |
///Return true if |
|
| 171 |
///Return true if level \c l is empty. |
|
| 171 | 172 |
bool emptyLevel(int l) const |
| 172 | 173 |
{
|
| ... | ... |
@@ -183,5 +184,5 @@ |
| 183 | 184 |
return _last_active[l]-_first[l]+1; |
| 184 | 185 |
} |
| 185 |
///Return true if there is |
|
| 186 |
///Return true if there is no active item on level \c l. |
|
| 186 | 187 |
bool activeFree(int l) const |
| 187 | 188 |
{
|
| ... | ... |
@@ -202,7 +203,5 @@ |
| 202 | 203 |
///Return a highest level active item. |
| 203 | 204 |
|
| 204 |
///Return a highest level active item. |
|
| 205 |
/// |
|
| 206 |
/// |
|
| 205 |
///Return a highest level active item or INVALID if there is no active |
|
| 207 | 206 |
///item. |
| 208 | 207 |
Item highestActive() const |
| ... | ... |
@@ -211,9 +210,7 @@ |
| 211 | 210 |
} |
| 212 | 211 |
|
| 213 |
///Return |
|
| 212 |
///Return the highest active level. |
|
| 214 | 213 |
|
| 215 |
///Return a highest active level. |
|
| 216 |
/// |
|
| 217 |
/// |
|
| 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,5 +231,5 @@ |
| 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,12 +253,8 @@ |
| 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,9 +283,7 @@ |
| 290 | 283 |
///@{
|
| 291 | 284 |
|
| 292 |
/// |
|
| 285 |
///Return an active item on level \c l. |
|
| 293 | 286 |
|
| 294 |
///Returns an active item on level \c l. |
|
| 295 |
/// |
|
| 296 |
/// |
|
| 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,7 +292,7 @@ |
| 301 | 292 |
} |
| 302 | 293 |
|
| 303 |
/// |
|
| 294 |
///Lift the active item returned by \c activeOn(level) by one. |
|
| 304 | 295 |
|
| 305 |
/// |
|
| 296 |
///Lift the active item returned by \ref activeOn() "activeOn(level)" |
|
| 306 | 297 |
///by one. |
| 307 | 298 |
Item liftActiveOn(int level) |
| ... | ... |
@@ -313,7 +304,7 @@ |
| 313 | 304 |
} |
| 314 | 305 |
|
| 315 |
/// |
|
| 306 |
///Lift the active item returned by \c activeOn(level) to the given level. |
|
| 316 | 307 |
|
| 317 |
/// |
|
| 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,8 +323,8 @@ |
| 332 | 323 |
} |
| 333 | 324 |
|
| 334 |
/// |
|
| 325 |
///Lift the active item returned by \c activeOn(level) to the top level. |
|
| 335 | 326 |
|
| 336 |
///Lifts the active item returned by \c activeOn() member function |
|
| 337 |
///to the top level. |
|
| 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,7 +376,8 @@ |
| 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 |
/// |
|
| 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,8 +385,8 @@ |
| 393 | 385 |
} |
| 394 | 386 |
|
| 395 |
///Lift all items on and above |
|
| 387 |
///Lift all items on and above the given level to the top level. |
|
| 396 | 388 |
|
| 397 |
///This function lifts all items on and above level \c l to \c |
|
| 398 |
///maxLevel(), and also deactivates them. |
|
| 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,16 +413,14 @@ |
| 421 | 413 |
|
| 422 | 414 |
///\name Initialization |
| 423 |
///Using |
|
| 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,5 +440,4 @@ |
| 450 | 440 |
|
| 451 | 441 |
///Add an item to the current level. |
| 452 |
|
|
| 453 | 442 |
void initAddItem(Item i) |
| 454 | 443 |
{
|
| ... | ... |
@@ -470,5 +459,4 @@ |
| 470 | 459 |
|
| 471 | 460 |
///Finalize the initialization process. |
| 472 |
|
|
| 473 | 461 |
void initFinish() |
| 474 | 462 |
{
|
| ... | ... |
@@ -501,7 +489,7 @@ |
| 501 | 489 |
///\sa Elevator |
| 502 | 490 |
/// |
| 503 |
///\param Graph the underlying graph |
|
| 491 |
///\param Graph Type of the underlying graph. |
|
| 504 | 492 |
///\param Item Type of the items the data is assigned to (Graph::Node, |
| 505 |
///Graph:: |
|
| 493 |
///Graph::Arc, Graph::Edge). |
|
| 506 | 494 |
template <class Graph, class Item> |
| 507 | 495 |
class LinkedElevator {
|
| ... | ... |
@@ -534,7 +522,7 @@ |
| 534 | 522 |
///Constructor with given maximum level. |
| 535 | 523 |
/// |
| 536 |
///\param g The underlying graph |
|
| 537 |
///\param max_level Set the range of the possible labels to |
|
| 538 |
/// |
|
| 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,6 +535,6 @@ |
| 547 | 535 |
///Constructor. |
| 548 | 536 |
/// |
| 549 |
///\param g The underlying graph |
|
| 550 |
///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,5 +646,5 @@ |
| 658 | 646 |
} |
| 659 | 647 |
|
| 660 |
///Return true if there is |
|
| 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,18 +664,14 @@ |
| 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 |
|
| 672 |
///Return the highest active level. |
|
| 687 | 673 |
|
| 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. |
|
| 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,5 +704,5 @@ |
| 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,9 +732,8 @@ |
| 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,9 +757,7 @@ |
| 774 | 757 |
///@{
|
| 775 | 758 |
|
| 776 |
/// |
|
| 759 |
///Return an active item on level \c l. |
|
| 777 | 760 |
|
| 778 |
///Returns an active item on level \c l. |
|
| 779 |
/// |
|
| 780 |
/// |
|
| 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,7 +766,7 @@ |
| 785 | 766 |
} |
| 786 | 767 |
|
| 787 |
/// |
|
| 768 |
///Lift the active item returned by \c activeOn(l) by one. |
|
| 788 | 769 |
|
| 789 |
/// |
|
| 770 |
///Lift the active item returned by \ref activeOn() "activeOn(l)" |
|
| 790 | 771 |
///by one. |
| 791 | 772 |
Item liftActiveOn(int l) |
| ... | ... |
@@ -814,8 +795,8 @@ |
| 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 function |
|
| 819 |
/// to the given level. |
|
| 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,8 +824,8 @@ |
| 843 | 824 |
} |
| 844 | 825 |
|
| 845 |
/// |
|
| 826 |
///Lift the active item returned by \c activeOn(l) to the top level. |
|
| 846 | 827 |
|
| 847 |
///Lifts the active item returned by \c activeOn() member function |
|
| 848 |
///to the top level. |
|
| 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,7 +882,8 @@ |
| 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 |
/// |
|
| 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,8 +891,8 @@ |
| 909 | 891 |
} |
| 910 | 892 |
|
| 911 |
///Lift all items on and above |
|
| 893 |
///Lift all items on and above the given level to the top level. |
|
| 912 | 894 |
|
| 913 |
///This function lifts all items on and above level \c l to \c |
|
| 914 |
///maxLevel(), and also deactivates them. |
|
| 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,16 +919,14 @@ |
| 937 | 919 |
|
| 938 | 920 |
///\name Initialization |
| 939 |
///Using |
|
| 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,5 +943,4 @@ |
| 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,5 +967,4 @@ |
| 988 | 967 |
|
| 989 | 968 |
///Finalize the initialization process. |
| 990 |
|
|
| 991 | 969 |
void initFinish() {
|
| 992 | 970 |
_highest_active = -1; |
0 comments (0 inline)