deferred class ABSTRACT_BACKTRACKING
Summary
This class is intended to explore structures that match the and/or pattern. The and/or pattern is found for example in the evaluation of the regular expressions, in the evaluation of Prolog queries, in solving some generic problem of artificial intelligence.
The instances of the class inheriting ABSTRACT_BACKTRACKING are typically used through code like the following one that enumerate all the solutions:
        from
           init_exploration(explorer)
           explorer.search_first
        until
           explorer.is_off
        loop
           treat_solution(explorer)
           explorer.search_next
        end
The exploration is the enumeration of all the paths in an abstract structure made of alternatives or sequences of goals to satisfy.
The class ABSTRACT_BACKTRACKING does not make any assumption on what is explored. That is its strength because it can be used in many situations. In such a case, nothing is said about what is a solution and what is a context. The implementations usually have to provide it.
A good understanding of how that class works is required if you intend to use it. See also the more easy-to-use class BACKTRACKING.
See tutorial/backtracking for examples.
The deferred features are 'evaluate_current_state'. 'context_clear', 'context_push', 'context_restore', 'context_restore_and_pop', 'context_cut'.
When the feature 'evaluate_current_state' is called, the implementor must perform actions to process the exploration. Here are some of the common things that can be done (note that one or more of these actions can be done):
  + stand-alone actions
    - replace the current state by an other state.
    - call 'backtrack': cancel the exploration of the current
      alternative and explore the next alternative.
    - call 'continue': explore the continuation of the
      current alternative.
  + actions that can be mixed but that need to be completed by
    one of the above actions
    - create a sequence of future path to evaluate and push it
      to the continuation path by calling 'push_sequence'.
    - create an alternative of future alternate path and push it
      to the alternative stack by calling 'push_alternative'.
    - push a cut point by calling 'push_cut_point'.
    - remove all alternatives until upper cut point by calling 'cut'.
    - remove all alternatives by calling 'cut_all'.
Because the exploration of and/or abstractions can be huge, that class requires to manage alternatives and sequences in pools.
Direct parents
Insert list: ABSTRACT_BACKTRACKING_GLOBALS
Known children
Inherit list: BACKTRACKING
Class invariant
Overview
Features
Common client features
{ANY}
Control of the exploration
{ANY}
Internal
{}
Internal deferred
{}
Specific to sequences
{ABSTRACT_BACKTRACKING_SEQUENCE}
Specific to alternatives
{ABSTRACT_BACKTRACKING_ALTERNATIVE}
internal: allocation and collection
{}
{ANY}
search_first
effective procedure
{ANY}
Resets all and searches the first solution.
The current state must be set. It is the first state, the root of the search. When the feature returns, 'search_is_success' must be checked to know if a solution was found. When search_is_success=False, it means that there is no solution at all. Conversely, if search_is_success=True, then the first solution is found and 'search_next' can be called to get the next solution if it exists.
ensure
search_next
effective procedure
{ANY}
Searches the next solution.
When the feature returns, 'search_is_success' must be checked to know if a solution was found. When search_is_success=False at the end, it means that there is no more solution. Conversely, if search_is_success=True, then a solution is found and 'search_next' can be called again to get the next solution.
require ensure
search_is_success: BOOLEAN
writable attribute
{ANY}
True when search is successful
is_off: BOOLEAN
effective function
{ANY}
True when search is finished
ensure
clear
effective procedure
{ANY}
Clears the current state to nothing.
ensure
is_cleared: BOOLEAN
effective function
{ANY}
True if no partial data remain in the current state
ensure
  • no_solution_when_cleared: Result implies is_off
push_sequence (sequence: ABSTRACT_BACKTRACKING_SEQUENCE)
effective procedure
{ANY}
Pushes the sequence in front of the continuation path.
require
  • sequence_not_void: sequence /= Void
ensure
push_alternative (alternative: ABSTRACT_BACKTRACKING_ALTERNATIVE)
effective procedure
{ANY}
Pushes the alternative before the continuation path.
require
  • alternative_not_void: alternative /= Void
ensure
continue
effective procedure
{ANY}
Continues the exploration of the current path.
backtrack
effective procedure
{ANY}
Stops the exploration of the current path and tries to explore the next alternative path.
push_cut_point
effective procedure
{ANY}
Inserts a cut point into the continuation path.
The inserted cut point records the current top of the alternatives.
cut
effective procedure
{ANY}
Removes the alternatives until the one recorded by the next cut point in the continuation path.
cut_all
effective procedure
{ANY}
Cuts all alternatives.
stop_search_loop: BOOLEAN
writable attribute
{}
True if at the end of a search.
This occurs if either a solution is found (and then search_is_success=True) or no solution is found (and then search_is_success=False). That feature should be modified only by continue and backtrack.
search
effective procedure
{}
Common search loop to search_first and search_next
cut_until (alternative: ABSTRACT_BACKTRACKING_ALTERNATIVE)
effective procedure
{}
Cut all alternatives until 'alternative'.
To cut an alternative is currently to remove it.
ensure
evaluate_current_state
deferred procedure
{}
That feature is called to evaluate the current state.
Called repeatedly by search until stop_search_loop.
context_clear
deferred procedure
{}
Clear any saved context.
Called by the features clear and search_first.
context_push
deferred procedure
{}
Push the current context.
Called each time that an alternative begins.
context_restore
deferred procedure
{}
Restore the context to the last saved one.
The saved context MUST remain available for future use. Called each time that a new alternative (of the previous alternative point) is starting.
context_restore_and_pop
deferred procedure
{}
Restore the context to the last saved one and drop it.
The saved context MUST be removed. Called each time that the last alternative (of the previous alternative point) is starting. Should be similar to context_restore followed by context_cut.
context_cut
deferred procedure
{}
Remove the last saved context.
Called by cut, cut_all or cut_until.
Stack of sequences represented by its top (can be Void)
current_continuation: ABSTRACT_BACKTRACKING_SEQUENCE
writable attribute
The current continuation path
pop_sequence
effective procedure
Removes the current sequence and replace it by the next sequence in the continuation path.
require
Stack of alternatives represented by its top (can be Void)
continue_alternative
effective procedure
Returns to the alternative on the top of the stack and put its saved continuation path as the current continuation path.
require ensure
pop_alternative
effective procedure
Returns to the alternative on the top of the stack and put its saved continuation path as the current continuation path.
Remove the alternative from the stack of alternatives. Same as continue_alternative but also removes the alternative.
require ensure
remove_top_sequence
effective procedure
{}
Removes the top sequence.
require ensure
remove_top_alternative
effective procedure
{}
Removes the top alternative.
require ensure
once function
{ANY}
Bank of cut points