[Aptitude-devel] r2943 - branches/aptitude-0.3/aptitude/src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Fri, 08 Apr 2005 01:39:12 +0000
Author: dburrows
Date: Fri Apr 8 01:39:11 2005
New Revision: 2943
Modified:
branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc
Log:
Make it even less efficient by using a unique set object to store
the list of broken dependencies per-solution.
Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h (original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h Fri Apr 8 01:39:11 2005
@@ -182,7 +182,7 @@
std::map<package, action> actions;
/** The full list of currently broken dependencies. */
- std::vector<dep> broken_deps;
+ std::set<dep> broken_deps;
/** The reference count of this solution. */
mutable unsigned int refcount;
@@ -222,19 +222,19 @@
* broken dependencies, and the given score. Used to generate
* the root node of the search.
*/
- solution_rep(const std::vector<dep> &_broken_deps,
+ solution_rep(const std::set<dep> &_broken_deps,
int _score)
- :broken_deps(_broken_deps), refcount(1),
+ :broken_deps(_broken_deps.begin(), _broken_deps.end()), refcount(1),
score(_score), action_score(0)
{
}
- const std::vector<dep> &get_broken_deps() const
+ const std::set<dep> &get_broken_deps() const
{
return broken_deps;
}
- std::vector<dep> &get_broken_deps()
+ std::set<dep> &get_broken_deps()
{
return broken_deps;
}
@@ -280,7 +280,7 @@
{
}
- solution(const std::vector<dep> &broken_deps,
+ solution(const std::set<dep> &broken_deps,
int score)
:real_soln(new solution_rep(broken_deps, score))
{
@@ -344,7 +344,7 @@
* in this solution. The list will live at least as long as
* the reference from which it was retrieved.
*/
- const std::vector<dep> &get_broken() const
+ const std::set<dep> &get_broken() const
{
return real_soln->get_broken_deps();
}
@@ -483,9 +483,16 @@
const version &v,
const dep &d)
{
+ std::cout << "Testing whether " << d << " is broken." << std::endl;
+
if(!ver_installed(s, v, d.get_source()))
return false;
+ std::cout << "Made it past the vacuity test." << std::endl;
+
+ // Could be somewhat inefficient for APT; think about how to
+ // mitigate that by offering higher-level "imagine this situation;
+ // is this dep broken?" operations in the universe.
for(typename dep::solver_iterator i=d.solvers_begin();
i!=d.solvers_end(); ++i)
{
@@ -513,7 +520,7 @@
new_action_score+=version_scores[v.get_id()];
new_action_score-=version_scores[v.get_package().current_version().get_id()];
- std::vector<dep> new_broken;
+ std::set<dep> new_broken;
// Check all revdeps of the old AND new package versions, and all
// previously broken deps. Is there any way to speed this up?
// For instance, by keeping a cache of already-examined deps.
@@ -529,18 +536,18 @@
for(typename version::revdep_iterator rd=old_version.revdeps_begin();
rd!=old_version.revdeps_end(); ++rd)
if(dep_broken(s, v, *rd))
- new_broken.push_back(*rd);
+ new_broken.insert(*rd);
for(typename version::revdep_iterator rd=v.revdeps_begin();
rd!=v.revdeps_end(); ++rd)
if(dep_broken(s, v, *rd))
- new_broken.push_back(*rd);
+ new_broken.insert(*rd);
- const std::vector<dep> &old_broken=s.get_broken();
- for(typename std::vector<dep>::const_iterator bd=old_broken.begin();
+ const std::set<dep> &old_broken=s.get_broken();
+ for(typename std::set<dep>::const_iterator bd=old_broken.begin();
bd!=old_broken.end(); ++bd)
if(dep_broken(s, v, *bd))
- new_broken.push_back(*bd);
+ new_broken.insert(*bd);
open.push(solution(action(v), s,
new_action_score+broken_score*new_broken.size(),
@@ -590,7 +597,7 @@
*/
void process_solution(const solution &s)
{
- for(typename std::vector<dep>::const_iterator bi=s.get_broken().begin();
+ for(typename std::set<dep>::const_iterator bi=s.get_broken().begin();
bi!=s.get_broken().end(); ++bi)
generate_successors(s, *bi);
}
@@ -665,12 +672,12 @@
// should enqueue a new root node.
if(open.empty())
{
- std::vector<dep> broken;
+ std::set<dep> broken;
// Find all the broken deps.
for(typename PackageUniverse::broken_dep_iterator bi=universe.broken_begin();
bi!=universe.broken_end(); ++bi)
- broken.push_back(*bi);
+ broken.insert(*bi);
open.push(solution(broken, broken.size()*broken_score));
}
@@ -686,7 +693,7 @@
std::cout << " with broken deps [";
- for(typename std::vector<dep>::const_iterator i=s.get_broken().begin();
+ for(typename std::set<dep>::const_iterator i=s.get_broken().begin();
i!=s.get_broken().end(); ++i)
{
if(i!=s.get_broken().begin())
Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc (original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc Fri Apr 8 01:39:11 2005
@@ -225,25 +225,33 @@
vector<dummy_version *> target_set;
dummy_dep(const dummy_dep &other);
+
+ unsigned int ID;
public:
typedef vector<dummy_version *>::const_iterator solver_iterator;
dummy_dep(const dummy_version *_source,
- const vector<dummy_version *> &_target_set)
- :source(_source), target_set(_target_set)
+ const vector<dummy_version *> &_target_set,
+ unsigned int _ID)
+ :source(_source), target_set(_target_set), ID(_ID)
{
}
- bool operator==(const dummy_dep &other)
+ bool operator==(const dummy_dep &other) const
{
return this==&other;
}
- bool operator!=(const dummy_dep &other)
+ bool operator!=(const dummy_dep &other) const
{
return this!=&other;
}
+ bool operator<(const dummy_dep &other) const
+ {
+ return ID<other.ID;
+ }
+
const dummy_version &get_source() const {return *source;}
solver_iterator solvers_begin() const
@@ -413,6 +421,11 @@
return real_dep!=other.real_dep;
}
+ bool operator<(const dep &other) const
+ {
+ return (*real_dep)<(*other.real_dep);
+ }
+
version get_source() const
{
return version(&real_dep->get_source());
@@ -547,7 +560,7 @@
targets.push_back(pfound->second->version_from_name(i->second));
}
- deps.push_back(new dummy_dep(pkg->version_from_name(pkg_ver), targets));
+ deps.push_back(new dummy_dep(pkg->version_from_name(pkg_ver), targets, deps.size()));
dummy_dep *newdep=deps.back();
for(vector<dummy_version *>::const_iterator i=targets.begin();