1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file expriter.c 26 * @ingroup OTHER_CFILES 27 * @brief functions for iterating over algebraic expressions 28 * @author Benjamin Mueller 29 * @author Stefan Vigerske 30 */ 31 32 /* enable this to record where active iterators were initialized 33 * (not thread-safe; problematic when using several SCIP instances concurrently) 34 */ 35 /* #define SCIP_DEBUG_EXPRITER */ 36 37 #include <assert.h> 38 39 #include "scip/expr.h" 40 #include "scip/pub_misc.h" 41 #include "scip/struct_expr.h" 42 #include "scip/struct_stat.h" 43 44 #define MINDFSSIZE 16 /**< minimum stack size for DFS*/ 45 #define MINBFSSIZE 16 /**< minimum queue size for BFS */ 46 47 #ifdef SCIP_DEBUG_EXPRITER 48 #include <execinfo.h> 49 #include <string.h> 50 #include <stdlib.h> 51 52 #define MAXSUBSCIPDEPTH 10 /**< minimal subscip-depth to no longer store backtrace */ 53 #define MAXBACKTRACE 20 /**< maximal length of backtrace to store */ 54 55 /** backtrace when iterator was initialized 56 * - store per subscip-depth (easier than storing per SCIP instance) 57 * - store per iterator position that can be active concurrently 58 * - one string for each entry in backtrace 59 * - each entry up to 200 characters 60 */ 61 char iterinitbacktrace[MAXSUBSCIPDEPTH][SCIP_EXPRITER_MAXNACTIVE][MAXBACKTRACE][200]; 62 #endif 63 64 /* 65 * local functions 66 */ 67 68 #ifdef SCIP_DEBUG_EXPRITER 69 /** obtain current backtrace and store it in iterinitbacktrace */ 70 static 71 void storeBacktrace( 72 int subscipdepth, /**< current subscip depth */ 73 int iterpos /**< iterator position where to store backtrace */ 74 ) 75 { 76 void* array[MAXBACKTRACE]; 77 char** strings; 78 int size; 79 int i; 80 81 assert(subscipdepth >= 0); 82 assert(iterpos >= 0); 83 assert(iterpos < SCIP_EXPRITER_MAXNACTIVE); 84 85 if( subscipdepth > MAXSUBSCIPDEPTH ) 86 return; 87 88 size = backtrace(array, MAXBACKTRACE); 89 strings = backtrace_symbols(array, size); 90 if( strings == NULL ) 91 size = 0; 92 93 for( i = 0; i < size; i++ ) 94 strncpy(iterinitbacktrace[subscipdepth][iterpos][i], strings[i], sizeof(iterinitbacktrace[0][0][0])); 95 96 /* '\0' for remining backtrace entries */ 97 while( size < MAXBACKTRACE ) 98 iterinitbacktrace[subscipdepth][iterpos][size++][0] = '\0'; 99 100 free(strings); 101 } 102 103 static 104 void printBacktraces( 105 int subscipdepth /**< current subscip depth */ 106 ) 107 { 108 int i, j; 109 110 assert(subscipdepth >= 0); 111 if( subscipdepth >= MAXSUBSCIPDEPTH ) 112 { 113 SCIPerrorMessage("subscip depth %d too high to report active iterators", subscipdepth); 114 return; 115 } 116 117 for( i = 0; i < SCIP_EXPRITER_MAXNACTIVE-1; ++i ) 118 { 119 SCIPerrorMessage("Active iterator %d created at:\n", i); 120 for( j = 0; j < MAXBACKTRACE; ++j ) 121 { 122 if( iterinitbacktrace[subscipdepth][i][j][0] == '\0' ) 123 break; 124 SCIPerrorMessage(" %s\n", iterinitbacktrace[subscipdepth][i][j]); 125 } 126 } 127 } 128 #else 129 #define storeBacktrace(subscipdepth, iterpos) 130 131 /*lint -e{715}*/ 132 static 133 void printBacktraces( 134 int subscipdepth /**< current subscip depth */ 135 ) 136 { /*lint --e{715}*/ 137 SCIPerrorMessage("Rebuild with SCIP_DEBUG_EXPRITER defined in src/scip/expriter.c to see where currently " 138 "active iterators were initialized.\n"); 139 } 140 #endif 141 142 static 143 void deinit( 144 SCIP_EXPRITER* iterator /**< expression iterator */ 145 ) 146 { 147 assert(iterator != NULL ); 148 149 if( !iterator->initialized ) 150 return; 151 152 if( iterator->iterindex >= 0 ) 153 { 154 /* the iterindex must be the one of the last initialized iterator */ 155 assert(iterator->iterindex == iterator->stat->nactiveexpriter-1); 156 157 /* tell core that this iterator is no longer active */ 158 --iterator->stat->nactiveexpriter; 159 160 iterator->iterindex = -1; 161 } 162 163 switch( iterator->itertype ) 164 { 165 case SCIP_EXPRITER_BFS : 166 { 167 assert(iterator->queue != NULL); 168 169 SCIPqueueFree(&iterator->queue); 170 171 break; 172 } 173 174 case SCIP_EXPRITER_RTOPOLOGIC : 175 { 176 assert(iterator->dfsnvisited != NULL); 177 assert(iterator->dfsexprs != NULL); 178 179 /* free dfs arrays */ 180 BMSfreeBlockMemoryArray(iterator->blkmem, &iterator->dfsnvisited, iterator->dfssize); 181 BMSfreeBlockMemoryArray(iterator->blkmem, &iterator->dfsexprs, iterator->dfssize); 182 iterator->dfssize = 0; 183 184 break; 185 } 186 187 case SCIP_EXPRITER_DFS : 188 default: break; 189 } 190 } 191 192 /** ensures minimum stack size of iterator's data */ 193 static 194 SCIP_RETCODE ensureStackSize( 195 SCIP_EXPRITER* iterator, /**< expression iterator */ 196 int size /**< minimum requires size */ 197 ) 198 { 199 assert(iterator != NULL); 200 assert(iterator->blkmem != NULL); 201 assert(iterator->itertype == SCIP_EXPRITER_RTOPOLOGIC); 202 assert(size >= 0); 203 204 if( size > iterator->dfssize ) 205 { 206 int newsize = size * 2; 207 208 SCIP_ALLOC( BMSreallocBlockMemoryArray(iterator->blkmem, &iterator->dfsexprs, iterator->dfssize, newsize) ); 209 SCIP_ALLOC( BMSreallocBlockMemoryArray(iterator->blkmem, &iterator->dfsnvisited, iterator->dfssize, newsize) ); 210 iterator->dfssize = newsize; 211 } 212 213 return SCIP_OKAY; 214 } 215 216 /** adds an expression to the DFS stack */ 217 static 218 void reverseTopologicalInsert( 219 SCIP_EXPRITER* iterator, /**< expression iterator */ 220 SCIP_EXPR* expr /**< expression */ 221 ) 222 { 223 assert(iterator != NULL); 224 assert(expr != NULL); 225 226 SCIP_CALL_ABORT( ensureStackSize(iterator, iterator->dfsnexprs + 1) ); 227 iterator->dfsexprs[iterator->dfsnexprs] = expr; 228 iterator->dfsnvisited[iterator->dfsnexprs] = 0; 229 ++(iterator->dfsnexprs); 230 } 231 232 /** moves to the next expression according to a reverse topological order */ 233 static 234 SCIP_EXPR* doReverseTopologicalNext( 235 SCIP_EXPRITER* iterator /**< expression iterator */ 236 ) 237 { 238 SCIP_EXPR* expr; 239 int childidx; 240 241 assert(iterator != NULL); 242 assert(iterator->itertype == SCIP_EXPRITER_RTOPOLOGIC); 243 244 /* no expression left */ 245 if( iterator->dfsnexprs == 0 ) 246 return NULL; 247 248 /* get expression on the top of the stack */ 249 expr = iterator->dfsexprs[iterator->dfsnexprs - 1]; 250 childidx = iterator->dfsnvisited[iterator->dfsnexprs - 1]; 251 252 /* remove the expression if all children have been visited */ 253 if( childidx >= SCIPexprGetNChildren(expr) ) 254 { 255 --(iterator->dfsnexprs); 256 return expr; 257 } 258 /* go to the next child */ 259 else 260 { 261 SCIP_EXPR* child = SCIPexprGetChildren(expr)[childidx]; 262 assert(child != NULL); 263 264 /* mark that the child has been visited */ 265 ++(iterator->dfsnvisited[iterator->dfsnexprs-1]); 266 267 /* do left-most step */ 268 while( SCIPexprGetNChildren(child) > 0 ) 269 { 270 /* add child to the DFS stack */ 271 reverseTopologicalInsert(iterator, child); 272 273 /* mark that the child has been visited; note that child is on top of the DFS stack */ 274 ++(iterator->dfsnvisited[iterator->dfsnexprs-1]); 275 276 child = SCIPexprGetChildren(child)[0]; 277 } 278 279 /* return last child; NOTE this child is not been added to the stack */ 280 return child; 281 } 282 } 283 284 /** moves to the next expression according to the BFS rule */ 285 static 286 SCIP_EXPR* doBfsNext( 287 SCIP_EXPRITER* iterator /**< expression iterator */ 288 ) 289 { 290 SCIP_EXPR* expr; 291 int i; 292 293 assert(iterator != NULL); 294 assert(iterator->itertype == SCIP_EXPRITER_BFS); 295 assert(iterator->queue != NULL); 296 297 /* no expression left */ 298 if( SCIPqueueIsEmpty(iterator->queue) ) 299 return NULL; 300 301 expr = (SCIP_EXPR*) SCIPqueueRemove(iterator->queue); 302 assert(expr != NULL); 303 304 assert(iterator->visitedtag == 0 || iterator->iterindex >= 0); 305 assert(iterator->visitedtag == 0 || iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE); 306 /* we should have set the visitedtag when adding the expression to the queue */ 307 assert(iterator->visitedtag == 0 || expr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag); 308 309 /* add all (possibly non-visited) children to the queue */ 310 for( i = 0; i < SCIPexprGetNChildren(expr); ++i ) 311 { 312 SCIP_EXPR* child = SCIPexprGetChildren(expr)[i]; 313 assert(child != NULL); 314 315 if( iterator->visitedtag != 0 ) 316 { 317 assert(iterator->iterindex >= 0); 318 assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE); 319 320 /* skip children that have already been visited or have already been added to the queue */ 321 if( child->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag ) 322 continue; 323 324 /* mark child as being in the queue (will be inserted next) */ 325 child->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag; 326 } 327 328 /* add child to the queue */ 329 SCIP_CALL_ABORT( SCIPqueueInsert(iterator->queue, child) ); 330 } 331 332 return expr; 333 } 334 335 /** moves to the next expression according to the DFS rule */ 336 static 337 SCIP_EXPR* doDfsNext( 338 SCIP_EXPRITER* iterator /**< expression iterator */ 339 ) 340 { 341 SCIP_EXPRITERDATA* iterdata; 342 343 assert(iterator != NULL); 344 assert(iterator->itertype == SCIP_EXPRITER_DFS); 345 assert(iterator->iterindex >= 0); 346 347 if( iterator->curr == NULL ) 348 return NULL; 349 350 iterdata = &iterator->curr->iterdata[iterator->iterindex]; 351 352 switch( iterator->dfsstage ) 353 { 354 case SCIP_EXPRITER_VISITEDCHILD: 355 /* consider next child */ 356 ++iterdata->currentchild; 357 /* fall through */ /* no break */ /*lint -fallthrough*/ 358 359 case SCIP_EXPRITER_ENTEREXPR: 360 { 361 /* if there is an unvisited child (left), then go into visitingchild stage, otherwise go to leave stage */ 362 iterator->dfsstage = SCIP_EXPRITER_LEAVEEXPR; /* expect that we will leave expr, and change mind to visitingchild below */ 363 while( iterdata->currentchild < iterator->curr->nchildren ) 364 { 365 if( iterator->visitedtag == 0 || iterator->visitedtag != iterator->curr->children[iterdata->currentchild]->iterdata[iterator->iterindex].visitedtag ) 366 { 367 /* if visitedtag is not used or child "currentchild" has not been visited yet, then go into visitingchild stage for this child */ 368 iterator->dfsstage = SCIP_EXPRITER_VISITINGCHILD; 369 break; 370 } 371 ++iterdata->currentchild; 372 } 373 /* if leaving expr, then currentchild should be at nchildren */ 374 assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterdata->currentchild == iterator->curr->nchildren); 375 /* if visiting child, then currentchild should be a valid index */ 376 assert(iterator->dfsstage == SCIP_EXPRITER_LEAVEEXPR || iterdata->currentchild < iterator->curr->nchildren); 377 /* if visiting child, then either we don't care whether we visited it already or it has not been visited yet */ 378 assert(iterator->dfsstage == SCIP_EXPRITER_LEAVEEXPR || iterator->visitedtag == 0 379 || iterator->visitedtag != iterator->curr->children[iterdata->currentchild]->iterdata[iterator->iterindex].visitedtag); 380 381 return iterator->curr; 382 } 383 384 case SCIP_EXPRITER_VISITINGCHILD: 385 { 386 SCIP_EXPR* child; 387 388 assert(iterdata->currentchild < iterator->curr->nchildren); 389 390 /* remember the parent and set the first child that should be visited of the new root */ 391 child = iterator->curr->children[iterdata->currentchild]; 392 child->iterdata[iterator->iterindex].parent = iterator->curr; 393 child->iterdata[iterator->iterindex].currentchild = 0; 394 395 /* visit child */ 396 iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR; 397 398 return child; 399 } 400 401 case SCIP_EXPRITER_LEAVEEXPR: 402 { 403 /* go back to parent expression */ 404 405 /* remember that this expression has been visited */ 406 iterdata->visitedtag = iterator->visitedtag; 407 408 /* be in visitedchild stage for the parent */ 409 iterator->dfsstage = SCIP_EXPRITER_VISITEDCHILD; 410 411 return iterdata->parent; 412 } 413 414 default: 415 /* unknown stage */ 416 SCIPABORT(); 417 return NULL; 418 } 419 } 420 421 /* 422 * private functions (expr.h) 423 */ 424 425 /** creates an expression iterator */ 426 SCIP_RETCODE SCIPexpriterCreate( 427 SCIP_STAT* stat, /**< dynamic problem statistics */ 428 BMS_BLKMEM* blkmem, /**< block memory */ 429 SCIP_EXPRITER** iterator /**< buffer to store expression iterator */ 430 ) 431 { 432 assert(stat != NULL); 433 assert(blkmem != NULL); 434 assert(iterator != NULL); 435 436 SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, iterator) ); 437 438 (*iterator)->stat = stat; 439 (*iterator)->blkmem = blkmem; 440 441 return SCIP_OKAY; 442 } 443 444 /** frees an expression iterator */ 445 void SCIPexpriterFree( 446 SCIP_EXPRITER** iterator /**< pointer to the expression iterator */ 447 ) 448 { 449 assert(iterator != NULL); 450 assert(*iterator != NULL); 451 assert((*iterator)->blkmem != NULL); 452 453 deinit(*iterator); 454 455 assert((*iterator)->queue == NULL); 456 assert((*iterator)->dfsnvisited == NULL); 457 assert((*iterator)->dfsexprs == NULL); 458 459 /* free iterator */ 460 BMSfreeBlockMemory((*iterator)->blkmem, iterator); 461 } 462 463 /* 464 * public functions (pub_expr.h) 465 */ 466 467 #ifdef NDEBUG 468 #undef SCIPexpriterIsInit 469 #undef SCIPexpriterGetCurrent 470 #undef SCIPexpriterGetStageDFS 471 #undef SCIPexpriterGetChildIdxDFS 472 #undef SCIPexpriterGetChildExprDFS 473 #undef SCIPexpriterGetParentDFS 474 #undef SCIPexpriterGetCurrentUserData 475 #undef SCIPexpriterGetChildUserDataDFS 476 #undef SCIPexpriterGetExprUserData 477 #undef SCIPexpriterSetCurrentUserData 478 #undef SCIPexpriterSetExprUserData 479 #undef SCIPexpriterSetChildUserData 480 #undef SCIPexpriterIsEnd 481 #endif 482 483 /** returns whether expression iterator is currently initialized */ 484 SCIP_Bool SCIPexpriterIsInit( 485 SCIP_EXPRITER* iterator /**< expression iterator */ 486 ) 487 { 488 assert(iterator != NULL); 489 490 return iterator->initialized; 491 } 492 493 /** initializes an expression iterator 494 * 495 * @note If `expr` is NULL, then iterator will be set into ended-state (SCIPexpriterIsEnd() is TRUE). Useful if following with SCIPexpriterRestartDFS(). 496 * 497 * If type is DFS, then `stopstages` will be set to \ref SCIP_EXPRITER_ENTEREXPR. 498 * Use `SCIPexpriterSetStagesDFS` to change this. 499 */ 500 SCIP_RETCODE SCIPexpriterInit( 501 SCIP_EXPRITER* iterator, /**< expression iterator */ 502 SCIP_EXPR* expr, /**< expression of the iterator, can be NULL */ 503 SCIP_EXPRITER_TYPE type, /**< type of expression iterator */ 504 SCIP_Bool allowrevisit /**< whether expression are allowed to be visited more than once */ 505 ) 506 { 507 assert(iterator != NULL); 508 509 deinit(iterator); 510 511 /* store the new type of the iterator */ 512 iterator->itertype = type; 513 514 /* get iterindex, if necessary */ 515 if( !allowrevisit || type == SCIP_EXPRITER_DFS ) 516 { 517 if( iterator->stat->nactiveexpriter + 1 >= SCIP_EXPRITER_MAXNACTIVE ) 518 { 519 SCIPerrorMessage("Maximal number of active expression iterators reached at subscip-depth %d.\n", 520 iterator->stat->subscipdepth); 521 printBacktraces(iterator->stat->subscipdepth); 522 return SCIP_MAXDEPTHLEVEL; 523 } 524 525 iterator->iterindex = iterator->stat->nactiveexpriter++; 526 527 storeBacktrace(iterator->stat->subscipdepth, iterator->iterindex); 528 } 529 else 530 { 531 iterator->iterindex = -1; 532 } 533 534 /* get new tag to recognize visited expressions */ 535 if( !allowrevisit ) 536 { 537 iterator->visitedtag = ++iterator->stat->exprlastvisitedtag; 538 } 539 else 540 { 541 iterator->visitedtag = 0L; 542 } 543 544 switch( iterator->itertype ) 545 { 546 case SCIP_EXPRITER_BFS: 547 { 548 SCIP_CALL( SCIPqueueCreate(&iterator->queue, MINBFSSIZE, 2.0) ); 549 550 assert(iterator->queue != NULL); 551 SCIPqueueClear(iterator->queue); 552 553 if( expr == NULL ) 554 { 555 iterator->curr = NULL; 556 break; 557 } 558 559 SCIP_CALL( SCIPqueueInsert(iterator->queue, expr) ); 560 561 if( iterator->visitedtag != 0 ) 562 { 563 assert(iterator->iterindex >= 0); 564 assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE); 565 assert(expr->iterdata[iterator->iterindex].visitedtag != iterator->visitedtag); 566 567 /* mark expression as being in the queue */ 568 expr->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag; 569 } 570 571 iterator->curr = SCIPexpriterGetNext(iterator); 572 break; 573 } 574 575 case SCIP_EXPRITER_RTOPOLOGIC : 576 { 577 SCIP_CALL( ensureStackSize(iterator, MINDFSSIZE) ); 578 579 if( expr != NULL ) 580 { 581 reverseTopologicalInsert(iterator, expr); 582 iterator->curr = SCIPexpriterGetNext(iterator); 583 } 584 else 585 { 586 iterator->curr = NULL; 587 } 588 589 break; 590 } 591 592 case SCIP_EXPRITER_DFS : 593 { 594 assert(iterator->iterindex >= 0); 595 596 iterator->stopstages = SCIP_EXPRITER_ENTEREXPR; 597 iterator->curr = expr; 598 599 if( expr == NULL ) 600 break; 601 602 expr->iterdata[iterator->iterindex].currentchild = 0; 603 expr->iterdata[iterator->iterindex].parent = NULL; 604 iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR; 605 606 break; 607 } 608 } 609 610 iterator->initialized = TRUE; 611 612 return SCIP_OKAY; 613 } 614 615 /** restarts an already initialized expression iterator in DFS mode 616 * 617 * The expression iterator will continue from the given expression, not revisiting expressions that 618 * this iterator has already been visited (if initialized with `allowrevisit=FALSE`) and giving access 619 * to the same iterator specified expression data that may have been set already. 620 * Also the stop-stages are not reset. 621 * 622 * If revisiting is forbidden and given expr has already been visited, then the iterator will behave 623 * as on the end of iteration (SCIPexpriterIsEnd() is TRUE). 624 * If the enterexpr stage is not one of the stop stages, then the iterator will be moved forward 625 * (SCIPexpriterGetNext() is called). 626 * 627 * @return The current expression. 628 */ 629 SCIP_EXPR* SCIPexpriterRestartDFS( 630 SCIP_EXPRITER* iterator, /**< expression iterator */ 631 SCIP_EXPR* expr /**< expression of the iterator */ 632 ) 633 { 634 assert(iterator != NULL); 635 assert(iterator->initialized); 636 assert(iterator->itertype == SCIP_EXPRITER_DFS); 637 638 /* if we forbid revisiting and root expr has already been visited, then set curr to NULL, that is, be at end of iterator */ 639 if( iterator->visitedtag > 0 && expr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag ) 640 { 641 iterator->curr = NULL; 642 return NULL; 643 } 644 645 /* set current to given expr, make it the root, and set stage to enterexpr */ 646 iterator->curr = expr; 647 expr->iterdata[iterator->iterindex].currentchild = 0; 648 expr->iterdata[iterator->iterindex].parent = NULL; 649 iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR; 650 651 if( (iterator->stopstages & SCIP_EXPRITER_ENTEREXPR) == 0 ) 652 return SCIPexpriterGetNext(iterator); 653 654 return iterator->curr; 655 } 656 657 /** specifies in which stages to stop a DFS iterator 658 * 659 * Parameter `stopstages` should be a bitwise OR of different \ref SCIP_EXPRITER_STAGE values 660 * 661 * If the current stage is not one of the `stopstages`, then the iterator will be moved on. 662 */ 663 void SCIPexpriterSetStagesDFS( 664 SCIP_EXPRITER* iterator, /**< expression iterator */ 665 SCIP_EXPRITER_STAGE stopstages /**< the stages in which to stop when iterating via DFS */ 666 ) 667 { 668 assert(iterator != NULL); 669 670 if( (iterator->dfsstage & stopstages) == 0 ) 671 { 672 iterator->stopstages = stopstages; 673 (void) SCIPexpriterGetNext(iterator); 674 } 675 else 676 { 677 iterator->stopstages = stopstages; 678 } 679 } 680 681 /** gets the current expression that the expression iterator points to */ 682 SCIP_EXPR* SCIPexpriterGetCurrent( 683 SCIP_EXPRITER* iterator /**< expression iterator */ 684 ) 685 { 686 assert(iterator != NULL); 687 688 return iterator->curr; 689 } 690 691 /** gets the current stage that the expression iterator is in when using DFS 692 * 693 * If the iterator has finished (SCIPexpriterIsEnd() is TRUE), then the stage is undefined. 694 */ 695 SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS( 696 SCIP_EXPRITER* iterator /**< expression iterator */ 697 ) 698 { 699 assert(iterator != NULL); 700 assert(iterator->itertype == SCIP_EXPRITER_DFS); 701 702 return iterator->dfsstage; 703 } 704 705 /** gets the index of the child that the expression iterator considers when in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD */ 706 int SCIPexpriterGetChildIdxDFS( 707 SCIP_EXPRITER* iterator /**< expression iterator */ 708 ) 709 { 710 assert(iterator != NULL); 711 assert(iterator->curr != NULL); 712 assert(iterator->iterindex >= 0); 713 assert(iterator->itertype == SCIP_EXPRITER_DFS); 714 assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD); 715 716 return iterator->curr->iterdata[iterator->iterindex].currentchild; 717 } 718 719 /** gets the child expression that the expression iterator considers when in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD */ 720 SCIP_EXPR* SCIPexpriterGetChildExprDFS( 721 SCIP_EXPRITER* iterator /**< expression iterator */ 722 ) 723 { 724 assert(iterator != NULL); 725 assert(iterator->curr != NULL); 726 assert(iterator->iterindex >= 0); 727 assert(iterator->itertype == SCIP_EXPRITER_DFS); 728 assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD); 729 assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0); 730 assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren); 731 732 return iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild]; 733 } 734 735 /** gives the parent of the current expression of an expression iteration if in DFS mode 736 * 737 * @return the expression from which the current expression has been accessed 738 */ 739 SCIP_EXPR* SCIPexpriterGetParentDFS( 740 SCIP_EXPRITER* iterator /**< expression iterator */ 741 ) 742 { 743 assert(iterator != NULL); 744 assert(iterator->curr != NULL); 745 assert(iterator->iterindex >= 0); 746 assert(iterator->itertype == SCIP_EXPRITER_DFS); 747 748 return iterator->curr->iterdata[iterator->iterindex].parent; 749 } 750 751 /** gives the iterator specific user data of the current expression 752 * 753 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE 754 */ 755 SCIP_EXPRITER_USERDATA SCIPexpriterGetCurrentUserData( 756 SCIP_EXPRITER* iterator /**< expression iterator */ 757 ) 758 { 759 assert(iterator != NULL); 760 assert(iterator->curr != NULL); 761 assert(iterator->iterindex >= 0); 762 763 return iterator->curr->iterdata[iterator->iterindex].userdata; 764 } 765 766 /** gives the iterator specific user data of the current expressions current child 767 * 768 * @note The expression iterator mode must be in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD 769 */ 770 SCIP_EXPRITER_USERDATA SCIPexpriterGetChildUserDataDFS( 771 SCIP_EXPRITER* iterator /**< expression iterator */ 772 ) 773 { 774 assert(iterator != NULL); 775 assert(iterator->curr != NULL); 776 assert(iterator->iterindex >= 0); 777 assert(iterator->itertype == SCIP_EXPRITER_DFS); 778 assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD); 779 assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0); 780 assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren); 781 782 return iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild]->iterdata[iterator->iterindex].userdata; 783 } 784 785 /** gives the iterator specific user data of a given expression 786 * 787 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE 788 */ 789 SCIP_EXPRITER_USERDATA SCIPexpriterGetExprUserData( 790 SCIP_EXPRITER* iterator, /**< expression iterator */ 791 SCIP_EXPR* expr /**< expression for which to get the userdata of this iterator */ 792 ) 793 { 794 assert(iterator != NULL); 795 assert(expr != NULL); 796 assert(iterator->iterindex >= 0); 797 798 return expr->iterdata[iterator->iterindex].userdata; 799 } 800 801 /** sets the iterator specific user data of the current expression for an expression iteration if in DFS mode 802 * 803 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE 804 */ 805 void SCIPexpriterSetCurrentUserData( 806 SCIP_EXPRITER* iterator, /**< expression iterator */ 807 SCIP_EXPRITER_USERDATA userdata /**< data to be stored */ 808 ) 809 { 810 assert(iterator != NULL); 811 assert(iterator->curr != NULL); 812 assert(iterator->iterindex >= 0); 813 814 iterator->curr->iterdata[iterator->iterindex].userdata = userdata; 815 } 816 817 /** sets the iterator specific user data of a given expression 818 * 819 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE 820 */ 821 void SCIPexpriterSetExprUserData( 822 SCIP_EXPRITER* iterator, /**< expression iterator */ 823 SCIP_EXPR* expr, /**< expression where to set iterator data */ 824 SCIP_EXPRITER_USERDATA userdata /**< data to be stored in current child */ 825 ) 826 { 827 assert(iterator != NULL); 828 assert(iterator->iterindex >= 0); 829 830 expr->iterdata[iterator->iterindex].userdata = userdata; 831 } 832 833 /** sets the iterator specific user data of the current expressions current child 834 * 835 * @note The expression iterator mode must be in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD 836 */ 837 void SCIPexpriterSetChildUserData( 838 SCIP_EXPRITER* iterator, /**< expression iterator */ 839 SCIP_EXPRITER_USERDATA userdata /**< data to be stored in current child */ 840 ) 841 { 842 assert(iterator != NULL); 843 assert(iterator->curr != NULL); 844 assert(iterator->iterindex >= 0); 845 assert(iterator->itertype == SCIP_EXPRITER_DFS); 846 assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD); 847 assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0); 848 assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren); 849 850 iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild]->iterdata[iterator->iterindex].userdata = userdata; 851 } 852 853 /** moves the iterator to the next expression according to the mode of the expression iterator 854 * 855 * @return the next expression, if any, and NULL otherwise 856 */ 857 SCIP_EXPR* SCIPexpriterGetNext( 858 SCIP_EXPRITER* iterator /**< expression iterator */ 859 ) 860 { 861 /* move to the next expression according to iterator type */ 862 switch( iterator->itertype ) 863 { 864 case SCIP_EXPRITER_BFS: 865 { 866 iterator->curr = doBfsNext(iterator); 867 break; 868 } 869 870 case SCIP_EXPRITER_RTOPOLOGIC : 871 { 872 iterator->curr = doReverseTopologicalNext(iterator); 873 if( iterator->visitedtag != 0 ) 874 { 875 assert(iterator->iterindex >= 0); 876 assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE); 877 878 /* skip already visited expressions */ 879 while( iterator->curr != NULL ) 880 { 881 if( iterator->curr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag ) 882 { 883 /* if curr has already been visited, get next one 884 * TODO this isn't really efficient, since we still walk through already visited expressions 885 */ 886 iterator->curr = doReverseTopologicalNext(iterator); 887 } 888 else 889 { 890 /* curr has not been visited yet, so mark it as visited and interrupt loop */ 891 iterator->curr->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag; 892 break; 893 } 894 } 895 } 896 break; 897 } 898 899 case SCIP_EXPRITER_DFS : 900 { 901 assert(iterator->iterindex >= 0); 902 903 /* get next until we are in a stopstage again 904 * this might give expressions more than once, depending on what the stopstages are 905 */ 906 do 907 { 908 iterator->curr = doDfsNext(iterator); 909 } 910 while( iterator->curr != NULL && (iterator->dfsstage & iterator->stopstages) == 0 ); 911 912 break; 913 } 914 } 915 916 return iterator->curr; 917 } 918 919 /** moves a DFS iterator to one of the next expressions 920 * 921 * - If in \ref SCIP_EXPRITER_ENTEREXPR stage, then all children of that expression will be skipped. 922 * If \ref SCIP_EXPRITER_LEAVEEXPR is one of the `stopstages`, then it will be the next stage. Otherwise, the iterator will move further on (go to the parent, etc). 923 * - If in \ref SCIP_EXPRITER_VISITINGCHILD stage, then the child that was going to be visited next will be skipped and the iterator will be moved on to the next child (if any). 924 * - If in \ref SCIP_EXPRITER_VISITEDCHILD stage, then all remaining children will be skipped and we move on to the \ref SCIP_EXPRITER_LEAVEEXPR stage (if a stop stage, otherwise further on). 925 * - It is not allowed to call this function when in \ref SCIP_EXPRITER_LEAVEEXPR stage. 926 * 927 * @return the next expression, if any, and NULL otherwise 928 */ 929 SCIP_EXPR* SCIPexpriterSkipDFS( 930 SCIP_EXPRITER* iterator /**< expression iterator */ 931 ) 932 { 933 assert(iterator != NULL); 934 assert(iterator->curr != NULL); 935 assert(iterator->itertype == SCIP_EXPRITER_DFS); 936 assert(iterator->iterindex >= 0); 937 938 switch( iterator->dfsstage ) 939 { 940 case SCIP_EXPRITER_ENTEREXPR : 941 case SCIP_EXPRITER_VISITEDCHILD : 942 { 943 /* move directly to leaveexpr */ 944 iterator->dfsstage = SCIP_EXPRITER_LEAVEEXPR; 945 /* if leaveexpr is not a stopstage, then move on */ 946 while( iterator->curr != NULL && (iterator->dfsstage & iterator->stopstages) == 0 ) 947 iterator->curr = doDfsNext(iterator); 948 return iterator->curr; 949 } 950 951 case SCIP_EXPRITER_VISITINGCHILD : 952 { 953 /* skip the child to be visited */ 954 /* pretend we just visited this child and get next */ 955 iterator->dfsstage = SCIP_EXPRITER_VISITEDCHILD; 956 return SCIPexpriterGetNext(iterator); 957 } 958 959 case SCIP_EXPRITER_LEAVEEXPR : 960 default : 961 SCIPerrorMessage("SCIPexpriterSkipDFS called in invalid stage %u", iterator->dfsstage); 962 SCIPABORT(); 963 return iterator->curr; 964 } 965 } 966 967 /** returns whether the iterator visited all expressions already */ 968 SCIP_Bool SCIPexpriterIsEnd( 969 SCIP_EXPRITER* iterator /**< expression iterator */ 970 ) 971 { 972 assert(iterator != NULL); 973 974 return iterator->curr == NULL; 975 } 976