diff options
Diffstat (limited to 'src/generic/problemresolver')
| -rw-r--r-- | src/generic/problemresolver/Makefile.am | 1 | ||||
| -rw-r--r-- | src/generic/problemresolver/problemresolver.h | 151 | ||||
| -rw-r--r-- | src/generic/problemresolver/promotion_set.h | 61 | ||||
| -rw-r--r-- | src/generic/problemresolver/search_graph.h | 16 | ||||
| -rw-r--r-- | src/generic/problemresolver/solution.h | 16 | ||||
| -rw-r--r-- | src/generic/problemresolver/tier.cc | 27 | ||||
| -rw-r--r-- | src/generic/problemresolver/tier.h | 289 | ||||
| -rw-r--r-- | src/generic/problemresolver/tier_limits.cc | 6 | ||||
| -rw-r--r-- | src/generic/problemresolver/tier_limits.h | 6 | ||||
| -rw-r--r-- | src/generic/problemresolver/tier_operation.cc | 33 | ||||
| -rw-r--r-- | src/generic/problemresolver/tier_operation.h | 17 |
11 files changed, 77 insertions, 546 deletions
diff --git a/src/generic/problemresolver/Makefile.am b/src/generic/problemresolver/Makefile.am index bb7a1798..f64997e3 100644 --- a/src/generic/problemresolver/Makefile.am +++ b/src/generic/problemresolver/Makefile.am @@ -16,7 +16,6 @@ libgeneric_problemresolver_a_SOURCES = \ problemresolver.h \ promotion_set.h sanity_check_universe.h \ search_graph.h solution.h \ - tier.cc tier.h \ tier_limits.cc tier_limits.h \ tier_operation.cc tier_operation.h diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h index 1d79c100..62609701 100644 --- a/src/generic/problemresolver/problemresolver.h +++ b/src/generic/problemresolver/problemresolver.h @@ -548,14 +548,15 @@ public: */ bool finished; - /** \brief The search tier of the next solution to consider. + /** \brief The search tier operation of the next solution to + * consider. */ - tier current_tier; + tier_operation current_tier_op; queue_counts() : open(0), closed(0), deferred(0), conflicts(0), promotions(0), finished(false), - current_tier(tier_limits::minimum_tier) + current_tier_op() { } }; @@ -604,10 +605,9 @@ private: // Note that *lower* tiers come "before" higher tiers, hence the // reversed comparison there. - if(step1.effective_step_tier < step2.effective_step_tier) - return true; - else if(step2.effective_step_tier < step1.effective_step_tier) - return false; + int tier_op_cmp = step1.final_step_tier_op.compare(step2.final_step_tier_op); + if(tier_op_cmp != 0) + return tier_op_cmp < 0; else if(step2.score < step1.score) return true; else if(step1.score < step2.score) @@ -846,23 +846,6 @@ private: /** \brief Counts how many steps are deferred. */ int num_deferred; - /** \brief The current minimum search tier. - * - * Solutions generated below this tier are discarded. Defaults to - * minimum_tier. - */ - tier minimum_search_tier; - - /** \brief The current maximum search tier. - * - * Solutions generated above this tier are placed into deferred. - * This is advanced automatically when the current tier is - * exhausted; it can also be advanced manually by the user. - * - * Defaults to minimum_tier. - */ - tier maximum_search_tier; - /** Solutions generated "in the future", stored by reference to * their step numbers. * @@ -1285,7 +1268,7 @@ private: non_incipient); if(non_incipient.get_has_value() && - s.effective_step_tier < non_incipient.get_value().get_tier()) + s.final_step_tier_op < non_incipient.get_value().get_tier()) LOG_ERROR(logger, "In step " << s.step_num << ": the embedded promotion " << non_incipient.get_value() << " was not applied."); else @@ -1294,7 +1277,7 @@ private: promotions.find_highest_promotion_for(s.actions); if(found_promotion != promotions.end() && - s.effective_step_tier < found_promotion->get_tier()) + s.final_step_tier_op < found_promotion->get_tier()) LOG_ERROR(logger, "In step " << s.step_num << ": the embedded promotion " << *found_promotion << " was not applied."); } @@ -1356,27 +1339,15 @@ private: #endif } - /** \return \b true if the given tier is one that should cause - * solvers and search steps to be discarded. - */ - bool is_discard_tier(const tier &t) const - { - return - t.get_structural_level() >= tier_limits::already_generated_structural_level; - } - /** \return \b true if the given tier operation will always cause - * the given step to be discarded. + * any step to be discarded. * * \param op the operation to test. - * - * \param s the step to test; is_discard_op returns \b true iff - * applying the tier operation to this step's base tier - * results in a discarding tier. */ - bool is_discard_op(const tier_operation &op, const step &s) const + bool is_discard_op(const tier_operation &op) const { - return is_discard_tier(op.apply(s.base_step_tier)); + return + op.get_structural_level() >= tier_limits::already_generated_structural_level; } /** \return \b true if the given step is "irrelevant": that is, @@ -1386,8 +1357,8 @@ private: */ bool irrelevant(const step &s) { - const tier &s_tier = s.effective_step_tier; - if(is_discard_tier(s_tier)) + const tier_operation &s_tier = s.final_step_tier_op; + if(is_discard_op(s_tier)) { LOG_TRACE(logger, "Step " << s.step_num << " is irrelevant: its tier " << s_tier << " indicates it should be discarded."); return true; @@ -1405,14 +1376,14 @@ private: } /** \brief Adjust the tier of a step, keeping everything consistent. */ - void set_step_tier(int step_num, - const tier &t) + void set_base_step_tier_op(int step_num, + const tier_operation &t_op) { step &s(graph.get_step(step_num)); - s.base_step_tier = t; + s.base_step_tier_op = t_op; - update_effective_step_tier(step_num); + update_final_step_tier_op(step_num); } /** \brief Update the operation that computes the *effective* tier @@ -1427,42 +1398,42 @@ private: s.effective_step_tier_op = t_op; - update_effective_step_tier(step_num); + update_final_step_tier_op(step_num); } /** \brief Update the effective tier of a step. * - * This should only be invoked by set_base_step_tier and + * This should only be invoked by set_base_step_tier_op and * set_effective_step_tier_op. It recomputes the effective tier * from its components and performs any follow-up work that's * needed to enforce consistency. */ - void update_effective_step_tier(int step_num) + void update_final_step_tier_op(int step_num) { step &s(graph.get_step(step_num)); - tier new_effective_step_tier = - s.effective_step_tier_op.apply(s.base_step_tier); + tier_operation new_final_step_tier_op = + s.effective_step_tier_op + s.base_step_tier_op; - if(s.effective_step_tier == new_effective_step_tier) + if(s.final_step_tier_op == new_final_step_tier_op) return; - if(s.is_blessed_solution && is_discard_tier(new_effective_step_tier)) + if(s.is_blessed_solution && is_discard_op(new_final_step_tier_op)) { LOG_TRACE(logger, "Step " << s.step_num - << " is a blessed solution; ignoring the attempt to promote it to tier " << new_effective_step_tier); + << " is a blessed solution; ignoring the attempt to promote it to tier " << new_final_step_tier_op); return; } - LOG_TRACE(logger, "Setting the effective tier of step " << step_num - << " to " << new_effective_step_tier); + LOG_TRACE(logger, "Setting the final tier of step " << step_num + << " to " << new_final_step_tier_op); bool was_in_pending = (pending.erase(step_num) > 0); bool was_in_pending_future_solutions = (pending_future_solutions.erase(step_num) > 0); - if(s.effective_step_tier >= tier_limits::defer_tier && - !is_discard_tier(s.effective_step_tier)) + if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level && + !is_discard_op(s.final_step_tier_op)) { if(was_in_pending) --num_deferred; @@ -1470,7 +1441,7 @@ private: --num_deferred; } - s.effective_step_tier = new_effective_step_tier; + s.final_step_tier_op = new_final_step_tier_op; if(was_in_pending) @@ -1479,15 +1450,15 @@ private: pending_future_solutions.insert(step_num); - if(s.effective_step_tier >= tier_limits::defer_tier && - !is_discard_tier(s.effective_step_tier)) + if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level && + !is_discard_op(s.final_step_tier_op)) { if(was_in_pending) ++num_deferred; if(was_in_pending_future_solutions) ++num_deferred; } - else if(s.effective_step_tier < tier_limits::defer_tier) + else if(s.final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level) { // Clear the "finished" flag if this is now a pending // candidate. @@ -2495,7 +2466,7 @@ private: bool operator()(const promotion &p) const { if(blessed) - return !resolver.is_discard_op(p.get_tier_op(), s); + return !resolver.is_discard_op(p.get_tier_op() + s.base_step_tier_op); else return true; } @@ -2845,8 +2816,8 @@ private: */ void recompute_effective_step_tier_op(step &s) { - LOG_TRACE(logger, "Recomputing the effective tier operation of step " << s.step_num - << " (was " << s.effective_step_tier << ")"); + LOG_TRACE(logger, "Recomputing the final tier operation of step " << s.step_num + << " (was " << s.final_step_tier_op << ")"); tier_operation new_tier_op(tier_limits::minimum_op); s.unresolved_deps.for_each(find_dep_tier_op_upper_bound(new_tier_op, *this)); @@ -2953,7 +2924,7 @@ private: // checks whether t_op consists only of maximizing operations that // are below the current search tier, in which case there's no // point in saving it. - if(t_op.apply(get_current_search_tier()) == get_current_search_tier() && + if(t_op + get_current_search_tier() == get_current_search_tier() && s.effective_step_tier_op.is_above_or_equal(t_op)) return; @@ -3125,7 +3096,7 @@ private: // to the point that the solver should be ejected, or the tier // should just be bumped up a bit. Either way, we might end up // changing the tier of the whole step. - if(is_discard_op(new_tier_op, s)) + if(is_discard_op(new_tier_op + s.base_step_tier_op)) { // \todo this throws away information about whether we're at // the already-generated tier. This isn't that important, @@ -3536,9 +3507,9 @@ private: output.action_score = parent.action_score; output.score = parent.score; output.reason = c; - output.base_step_tier = c_op.apply(parent.base_step_tier); + output.base_step_tier_op = c_op + parent.base_step_tier_op; output.effective_step_tier_op = tier_operation(); - output.effective_step_tier = output.effective_step_tier_op.apply(output.base_step_tier); + output.final_step_tier_op = output.effective_step_tier_op + output.base_step_tier_op; output.is_deferred_listener = build_is_deferred_listener(c); output.unresolved_deps = parent.unresolved_deps; output.unresolved_deps_by_num_solvers = parent.unresolved_deps_by_num_solvers; @@ -3634,10 +3605,10 @@ private: extend_score_to_new_step(output, c); LOG_TRACE(logger, "Generated step " << output.step_num - << " (" << output.actions.size() << " actions): " << output.actions << ";T" << output.effective_step_tier + << " (" << output.actions.size() << " actions): " << output.actions << ";T" << output.final_step_tier_op << "S" << output.score); - if(is_discard_tier(output.effective_step_tier)) + if(is_discard_op(output.final_step_tier_op)) ++num_deferred; pending.insert(output.step_num); @@ -3777,8 +3748,6 @@ public: solver_executing(false), solver_cancelled(false), pending(step_goodness_compare(graph)), num_deferred(0), - minimum_search_tier(tier_limits::minimum_tier), - maximum_search_tier(tier_limits::minimum_tier), pending_future_solutions(step_goodness_compare(graph)), closed(), promotions(_universe, *this), @@ -4228,7 +4197,7 @@ public: counts.conflicts = promotions.conflicts_size(); counts.promotions = promotions.size() - counts.conflicts; counts.finished = finished; - counts.current_tier = get_current_search_tier(); + counts.current_tier_op = get_current_search_tier(); } /** If no resolver is running, run through the deferred list and @@ -4249,12 +4218,12 @@ public: * solution that would be considered (or minimum_search_tier if * pending is empty). */ - const tier &get_current_search_tier() const + tier_operation get_current_search_tier() const { if(pending.empty()) - return tier_limits::minimum_tier; + return tier_operation(); else - return graph.get_step(*pending.begin()).effective_step_tier; + return graph.get_step(*pending.begin()).final_step_tier_op; } private: @@ -4265,7 +4234,7 @@ private: { return !pending.empty() && - graph.get_step(*pending.begin()).effective_step_tier < tier_limits::defer_tier; + graph.get_step(*pending.begin()).final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level; } /** \brief Returns \b true if the pending future solutions queue @@ -4275,7 +4244,7 @@ private: { return !pending_future_solutions.empty() && - graph.get_step(*pending_future_solutions.begin()).effective_step_tier < tier_limits::defer_tier; + graph.get_step(*pending_future_solutions.begin()).final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level; } // Counts how many action hits existed in a promotion, allowing up @@ -4461,10 +4430,10 @@ private: step &s = graph.get_step(step_num); LOG_INFO(logger, "Examining step " << step_num - << " (" << s.actions.size() << " actions): " << s.actions << ";T" << s.effective_step_tier + << " (" << s.actions.size() << " actions): " << s.actions << ";T" << s.final_step_tier_op << "S" << s.score); - if(s.effective_step_tier >= tier_limits::defer_tier) + if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level) { LOG_ERROR(logger, "Internal error: the tier of step " << s.step_num @@ -4487,7 +4456,7 @@ private: } // The step might have been promoted to the defer tier by // check_for_new_promotions. - else if(s.effective_step_tier >= tier_limits::defer_tier) + else if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level) { LOG_DEBUG(logger, "Skipping newly deferred step " << s.step_num); // Stick it back into the open queue. @@ -4504,7 +4473,7 @@ private: if(s.unresolved_deps.empty()) { LOG_INFO(logger, " --- Found solution at step " << s.step_num - << ": " << s.actions << ";T" << s.effective_step_tier + << ": " << s.actions << ";T" << s.final_step_tier_op << "S" << s.score); // Remember this solution, so we don't try to return it @@ -4528,7 +4497,7 @@ private: // was a forced dependency and we should process that // successor before returning. if(s.first_child != -1 && graph.get_step(s.first_child).is_last_child && - graph.get_step(s.first_child).effective_step_tier < tier_limits::defer_tier) + graph.get_step(s.first_child).final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level) { LOG_TRACE(logger, "Following forced dependency resolution from step " << step_num << " to step " << s.first_child); @@ -4614,9 +4583,9 @@ public: if(initial_broken.empty()) root.score += weights.full_solution_score; - root.base_step_tier = tier_limits::minimum_tier; + root.base_step_tier_op = tier_operation(); root.effective_step_tier_op = tier_operation(); - root.effective_step_tier = tier_limits::minimum_tier; + root.final_step_tier_op = tier_operation(); root.promotion_queue_location = promotion_queue_tail; for(typename imm::set<dep>::const_iterator it = initial_broken.begin(); @@ -4624,7 +4593,7 @@ public: add_unresolved_dep(root, *it); LOG_TRACE(logger, "Inserting the root at step " << root.step_num - << " with tier " << root.effective_step_tier); + << " with tier " << root.final_step_tier_op); pending.insert(root.step_num); } @@ -4686,14 +4655,14 @@ public: { int best_future_solution = *pending_future_solutions.begin(); step &best_future_solution_step = graph.get_step(best_future_solution); - if(best_future_solution_step.effective_step_tier < tier_limits::defer_tier) + if(best_future_solution_step.final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level) { sanity_check_not_deferred(best_future_solution_step); solution rval(best_future_solution_step.actions, initial_state, best_future_solution_step.score, - best_future_solution_step.effective_step_tier); + best_future_solution_step.final_step_tier_op); LOG_INFO(logger, " *** Converged after " << odometer << " steps."); diff --git a/src/generic/problemresolver/promotion_set.h b/src/generic/problemresolver/promotion_set.h index 29397748..c90dec0f 100644 --- a/src/generic/problemresolver/promotion_set.h +++ b/src/generic/problemresolver/promotion_set.h @@ -1647,67 +1647,6 @@ private: choices.for_each(find_results_f); } - /** \brief Predicate testing whether an entry reference refers to - * something in a particular tier. - */ - struct entry_ref_in_tier_pred - { - tier selected_tier; - - entry_ref_in_tier_pred(const tier &_selected_tier) - : selected_tier(_selected_tier) - { - } - - bool operator()(entry_ref r) const - { - return r->p.get_tier() == selected_tier; - } - }; - - /** \brief Predicate testing whether an entry reference refers to - * something between two tiers. - */ - struct entry_ref_between_tiers_pred - { - tier begin_tier, end_tier; - - /** \brief Create a new entry_ref_in_tier_pred. - * - * \param _begin_tier The first tier to select. - * \param _end_tier The first tier to *not* select. - */ - entry_ref_between_tiers_pred(const tier &_begin_tier, const tier &_end_tier) - : begin_tier(_begin_tier), end_tier(_end_tier) - { - } - - bool operator()(entry_ref r) const - { - const tier &r_tier(r->p.get_tier()); - - return r_tier >= begin_tier && r_tier < end_tier; - } - }; - - /** \brief Predicate testing whether an entry reference is strictly - * below a particular tier. - */ - struct entry_ref_strictly_below_tier_pred - { - tier selected_tier; - - entry_ref_strictly_below_tier_pred(const tier &_selected_tier) - : selected_tier(_selected_tier) - { - } - - bool operator()(entry_ref r) const - { - return r->p.get_tier() < selected_tier; - } - }; - /** \brief Collect the versions and soft dependencies related * to a single choice. */ diff --git a/src/generic/problemresolver/search_graph.h b/src/generic/problemresolver/search_graph.h index c99de55c..a467e0ad 100644 --- a/src/generic/problemresolver/search_graph.h +++ b/src/generic/problemresolver/search_graph.h @@ -790,12 +790,13 @@ public: */ int action_score; - /** \brief The true tier of this step. + /** \brief The tier operation induced by the actions performed at + * this step. * * This is the tier *before* any forward-looking operations are * applied to it. */ - tier base_step_tier; + tier_operation base_step_tier_op; /** \brief The cumulative effect of all forward-looking operations * applied to this step. @@ -809,12 +810,13 @@ public: */ tier_operation effective_step_tier_op; - /** \brief The effective tier of this step. + /** \brief The tier of this step after taking into account + * knowledge about the available solutions to its dependencies. * * This tier is step_tier combined with any inferred tier * operations, and is used to sort the step in the search queue. */ - tier effective_step_tier; + tier_operation final_step_tier_op; /** \brief A side-effecting expression that fires when the most * recently added action becomes deferred or un-deferred. @@ -1790,11 +1792,11 @@ private: { bool operator()(const promotion &p) const { - const tier &p_tier(p.get_tier()); + const tier_operation &p_tier_op(p.get_tier_op()); return - p_tier >= tier_limits::defer_tier && - p_tier < tier_limits::already_generated_tier; + p_tier_op.get_structural_level() >= tier_limits::defer_structural_level && + p_tier_op.get_structural_level() < tier_limits::already_generated_structural_level; } }; diff --git a/src/generic/problemresolver/solution.h b/src/generic/problemresolver/solution.h index 23c57f42..538314fa 100644 --- a/src/generic/problemresolver/solution.h +++ b/src/generic/problemresolver/solution.h @@ -31,7 +31,7 @@ #include <generic/util/refcounted_base.h> #include "choice.h" #include "choice_set.h" -#include "tier.h" +#include "tier_operation.h" /** \brief The solution class for the problem resolver. * @@ -294,7 +294,7 @@ private: * Informational only; not considered when comparing solutions by * identity. */ - tier sol_tier; + tier_operation sol_tier_op; /** The reference count of this solution. */ mutable unsigned int refcount; @@ -307,10 +307,10 @@ private: solution_rep(const choice_set &_choices, const resolver_initial_state<PackageUniverse> &_initial_state, int _score, - const tier &_sol_tier) + const tier_operation &_sol_tier_op) : initial_state(_initial_state), choices(_choices), score(_score), - sol_tier(_sol_tier), + sol_tier_op(_sol_tier_op), refcount(1) { } @@ -326,7 +326,7 @@ private: } int get_score() const {return score;} - const tier &get_tier() const { return sol_tier; } + const tier_operation &get_tier() const { return sol_tier_op; } version version_of(const package &pkg) const { @@ -394,8 +394,8 @@ public: generic_solution(const choice_set &choices, const resolver_initial_state<PackageUniverse> &initial_state, int score, - const tier &sol_tier) - : real_soln(new solution_rep(choices, initial_state, score, sol_tier)) + const tier_operation &sol_tier_op) + : real_soln(new solution_rep(choices, initial_state, score, sol_tier_op)) { } @@ -487,7 +487,7 @@ public: } /** \return The tier at which this solution was calculated. */ - const tier &get_tier() const + const tier_operation &get_tier() const { return real_soln->get_tier(); } diff --git a/src/generic/problemresolver/tier.cc b/src/generic/problemresolver/tier.cc index c2369d5f..8ef840c2 100644 --- a/src/generic/problemresolver/tier.cc +++ b/src/generic/problemresolver/tier.cc @@ -33,30 +33,3 @@ std::ostream &operator<<(std::ostream &out, const level &l) return out; } - -std::ostream &operator<<(std::ostream &out, const tier &t) -{ - out << "("; - - const int t_structural_level = t.get_structural_level(); - - if(t_structural_level == tier_limits::conflict_structural_level) - out << "conflict"; - else if(t_structural_level == tier_limits::already_generated_structural_level) - out << "already-generated"; - else if(t_structural_level == tier_limits::defer_structural_level) - out << "defer"; - else if(t_structural_level == tier_limits::minimum_level) - out << "minimum"; - else - out << t_structural_level; - - for(tier::user_level_iterator it = t.user_levels_begin(); - it != t.user_levels_end(); ++it) - out << ", " << *it; - - out << ")"; - - return out; -} - diff --git a/src/generic/problemresolver/tier.h b/src/generic/problemresolver/tier.h index f608c7cb..b358078d 100644 --- a/src/generic/problemresolver/tier.h +++ b/src/generic/problemresolver/tier.h @@ -271,293 +271,4 @@ namespace aptitude } } -/** \brief Represents the tier of a search node. - * - * The resolver is \e guaranteed to produce solutions in increasing - * order by tier. This is as opposed to score, which is merely used - * in a best-effort manner. - * - * A tier is a sequence of levels (as defined above). By convention, - * each tier in a search should have the same length; tiers are - * compared lexicographically. - * - * The first level in the tier is reserved by the resolver to store - * "structural" priorities (for instance, to mark nodes as conflicted - * or deferred); to make things simpler for client code that doesn't - * care about this information, that level is stored and accessed - * separately from the main list. - */ -class tier -{ - /** \brief The object that actually stores the tier data. */ - struct tier_impl - { - // Level set by the resolver itself to control the search - // algorithm. This is always increased in an upper-bound / cutoff - // fashion. - int structural_level; - - // Levels set by client code to customize the search order. - std::vector<level> user_levels; - - // Cache the hash value. Initialized during construction. - std::size_t hash_value; - - /** \brief Initialize a tier object from a collection of user levels. - * - * The structural level is set to INT_MIN. - */ - template<typename Iterator> - tier_impl(Iterator user_levels_begin, Iterator user_levels_end) - : structural_level(INT_MIN), - user_levels(user_levels_begin, user_levels_end), - hash_value(0) - { - hash_value = get_hash_value(); - } - - /** \brief Initialize a tier object with no user levels. - * - * This will be the smallest tier in its structural level. - */ - tier_impl(int _structural_level) - : structural_level(_structural_level), - user_levels(), - hash_value(0) - { - hash_value = get_hash_value(); - } - - /** \brief Initialize a tier object given its contents. */ - template<typename Iterator> - tier_impl(int _structural_level, - Iterator user_levels_begin, Iterator user_levels_end) - : structural_level(_structural_level), - user_levels(user_levels_begin, user_levels_end), - hash_value(0) - { - hash_value = get_hash_value(); - } - - std::size_t get_hash_value() const - { - std::size_t rval = 0; - - boost::hash_combine(rval, structural_level); - for(std::vector<level>::const_iterator it = user_levels.begin(); - it != user_levels.end(); ++it) - boost::hash_combine(rval, *it); - - return rval; - } - - bool operator==(const tier_impl &other) const - { - return - structural_level == other.structural_level && - user_levels == other.user_levels; - } - - bool operator!=(const tier_impl &other) const - { - return - structural_level != other.structural_level || - user_levels != other.user_levels; - } - }; - - class tier_impl_hasher - { - public: - std::size_t operator()(const tier_impl &impl) const - { - return impl.hash_value; - } - }; - - typedef boost::shared_ptr<tier_impl> tier_impl_ref; - - tier_impl_ref impl_ref; - - tier(const tier_impl_ref &_impl_ref) - : impl_ref(_impl_ref) - { - } - - const tier_impl &get_impl() const - { - return *impl_ref; - } - -public: - /** \brief A default-constructed tier is the smallest possible tier. */ - tier() - : impl_ref(boost::make_shared<tier_impl>(INT_MIN)) - { - } - - /** \brief Create a new tier object with structural level INT_MIN. - * - * \param user_level_begin The beginning of a range of levels to - * insert into the user level list. - * - * \param user_level_end The end of a range of levels to insert - * into the user level list. - */ - template<typename Iterator> - tier(Iterator user_levels_begin, Iterator user_levels_end) - : impl_ref(boost::make_shared<tier_impl>(user_levels_begin, user_levels_end)) - { - } - - /** \brief Create a new tier object with the given structural level - * and no user levels. - * - * The new tier will be the smallest tier in its structural level. - */ - tier(int structural_level) - : impl_ref(boost::make_shared<tier_impl>(structural_level)) - { - } - - /** \brief Create a new tier object. - * - * \param structural_level The structural level to store in the new - * level object. - * - * \param user_level_begin The beginning of a range of levels to - * insert into the user level list. - * - * \param user_level_end The end of a range of levels to insert - * into the user level list. - */ - template<typename Iterator> - tier(int structural_level, - Iterator user_levels_begin, Iterator user_levels_end) - : impl_ref(boost::make_shared<tier_impl>(structural_level, user_levels_begin, user_levels_end)) - { - } - - /** \brief Create a new tier object in which this object's - * structural level has been modified. - * - * \param new_structural_level The structural level of the new - * level object. - * - * \return a tier object with the same user levels as this object - * and the given structural level. - */ - tier set_structural_level(int new_structural_level) const - { - const tier_impl &impl(get_impl()); - - return tier(boost::make_shared<tier_impl>(new_structural_level, - impl.user_levels.begin(), - impl.user_levels.end())); - } - - /** \brief Retrieve the value of the structural level slot. */ - int get_structural_level() const { return get_impl().structural_level; } - - typedef std::vector<level>::const_iterator user_level_iterator; - - /** \brief Get a reference to the first user level as a - * random-access iterator. - */ - user_level_iterator user_levels_begin() const { return get_impl().user_levels.begin(); } - /** \brief Get a reference to the end of the user level list as a - * random-access iterator. - */ - user_level_iterator user_levels_end() const { return get_impl().user_levels.end(); } - - /** \brief Retrieve one user level from this tier. */ - const level &get_user_level(int index) const { return get_impl().user_levels[index]; } - - /** \brief Retrieve the number of user levels in this tier. */ - std::size_t get_num_user_levels() const { return get_impl().user_levels.size(); } - - std::size_t get_hash_value() const - { - return get_impl().hash_value; - } - - tier &operator=(const tier &other) - { - impl_ref = other.impl_ref; - - return *this; - } - - /** \brief Compare two tiers. - * - * Tiers are compared lexicographically, ignoring level states. - */ - int compare(const tier &other) const - { - const tier_impl &impl(get_impl()); - const tier_impl &other_impl(other.get_impl()); - - using aptitude::util::compare3; - - const int cmp = compare3(impl.structural_level, other_impl.structural_level); - if(cmp != 0) - return cmp; - else - return compare3(impl.user_levels, other_impl.user_levels); - } - - bool operator==(const tier &other) const - { - return compare(other) == 0; - } - - bool operator!=(const tier &other) const - { - return compare(other) != 0; - } - - bool operator<(const tier &other) const - { - return compare(other) < 0; - } - - bool operator<=(const tier &other) const - { - return compare(other) <= 0; - } - - bool operator>(const tier &other) const - { - return compare(other) > 0; - } - - bool operator>=(const tier &other) const - { - return compare(other) >= 0; - } -}; - -inline std::size_t hash_value(const tier &t) -{ - return t.get_hash_value(); -} - -namespace aptitude -{ - namespace util - { - template<> - class compare3_f<tier> - { - public: - int operator()(const tier &t1, const tier &t2) const - { - return t1.compare(t2); - } - }; - } -} - -std::ostream &operator<<(std::ostream &, const tier &t); - #endif // TIER_H diff --git a/src/generic/problemresolver/tier_limits.cc b/src/generic/problemresolver/tier_limits.cc index 495f895f..02ce4b6b 100644 --- a/src/generic/problemresolver/tier_limits.cc +++ b/src/generic/problemresolver/tier_limits.cc @@ -26,12 +26,6 @@ const int tier_limits::defer_structural_level; const int tier_limits::already_generated_structural_level; const int tier_limits::minimum_level; -const tier tier_limits::maximum_tier(tier_limits::maximum_level); -const tier tier_limits::conflict_tier(tier_limits::conflict_structural_level); -const tier tier_limits::already_generated_tier(tier_limits::already_generated_structural_level); -const tier tier_limits::defer_tier(tier_limits::defer_structural_level); -const tier tier_limits::minimum_tier(tier_limits::minimum_level); - const tier_operation tier_limits::increase_to_maximum_op(tier_operation::make_advance_structural_level(maximum_level)); const tier_operation tier_limits::increase_to_conflict_op(tier_operation::make_advance_structural_level(conflict_structural_level)); const tier_operation tier_limits::increase_to_already_generated_op(tier_operation::make_advance_structural_level(already_generated_structural_level)); diff --git a/src/generic/problemresolver/tier_limits.h b/src/generic/problemresolver/tier_limits.h index 567d5ea1..0f7b8e4d 100644 --- a/src/generic/problemresolver/tier_limits.h +++ b/src/generic/problemresolver/tier_limits.h @@ -55,12 +55,6 @@ public: */ static const int minimum_level = INT_MIN; - static const tier maximum_tier; - static const tier conflict_tier; - static const tier already_generated_tier; - static const tier defer_tier; - static const tier minimum_tier; - /** \brief Tier operations that just increase the structural level. */ // @{ diff --git a/src/generic/problemresolver/tier_operation.cc b/src/generic/problemresolver/tier_operation.cc index 180c0825..e5907f96 100644 --- a/src/generic/problemresolver/tier_operation.cc +++ b/src/generic/problemresolver/tier_operation.cc @@ -59,39 +59,6 @@ tier_operation::op_impl::op_impl(const op_impl &op1, const op_impl &op2, combine actions.insert(actions.end(), it2, op2.actions.end()); } -tier tier_operation::op_impl::apply(const tier &t) const -{ - int out_structural_level = - std::max<int>(t.get_structural_level(), structural_level); - std::vector<level> out_user_levels(t.user_levels_begin(), t.user_levels_end()); - - if(!actions.empty()) - { - // If the actions array will modify slots off the end of the - // tier's list of levels, we first pre-extend that list. - if(out_user_levels.size() <= actions.back().first) - { - level_index - gap_size = actions.back().first + 1 - out_user_levels.size(); - - out_user_levels.insert(out_user_levels.end(), - gap_size, - level()); - } - - for(std::vector<std::pair<level_index, level> >::const_iterator it = - actions.begin(); it != actions.end(); ++it) - { - level &target(out_user_levels[it->first]); - target = level::combine(target, it->second); - } - } - - return tier(out_structural_level, - out_user_levels.begin(), - out_user_levels.end()); -} - bool tier_operation::op_impl::is_above_or_equal(const op_impl &other) const { std::vector<std::pair<level_index, level> >::const_iterator diff --git a/src/generic/problemresolver/tier_operation.h b/src/generic/problemresolver/tier_operation.h index aac1dd19..f5e05642 100644 --- a/src/generic/problemresolver/tier_operation.h +++ b/src/generic/problemresolver/tier_operation.h @@ -163,14 +163,6 @@ class tier_operation actions == other.actions; } - /** \brief Apply the operation to the tier. - * - * Each level is combined with the corresponding level in the - * target tier. If there is no corresponding level, it is copied - * directly (which is exactly the desired behavior). - */ - tier apply(const tier &t) const; - /** \brief Compare two operations by their identity. */ int compare(const op_impl &other) const; @@ -342,15 +334,6 @@ public: return impl_flyweight != other.impl_flyweight; } - /** \brief Apply this operation to a tier. - * - * \param t The tier that this operation should modify. - */ - tier apply(const tier &t) const - { - return get_impl().apply(t); - } - /** \brief Write a description of a tier operation to an ostream. */ void dump(std::ostream &out) const |