merged from debian-experimental

12 files changed, 995 insertions, 479 deletions

diff --git a/apt-pkg/cacheset.cc b/apt-pkg/cacheset.cc
index 6b95eab70..b892ab4bf 100644
--- a/apt-pkg/cacheset.cc
+++ b/apt-pkg/cacheset.cc
@@ -29,7 +29,7 @@
 									/*}}}*/
 namespace APT {
 // FromTask - Return all packages in the cache from a specific task	/*{{{*/
-PackageSet PackageSet::FromTask(pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper) {
+bool PackageContainerInterface::FromTask(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper) {
 	size_t const archfound = pattern.find_last_of(':');
 	std::string arch = "native";
 	if (archfound != std::string::npos) {
@@ -38,13 +38,16 @@ PackageSet PackageSet::FromTask(pkgCacheFile &Cache, std::string pattern, CacheS
 	}
 
 	if (pattern[pattern.length() -1] != '^')
-		return APT::PackageSet(TASK);
+		return false;
 	pattern.erase(pattern.length()-1);
 
 	if (unlikely(Cache.GetPkgCache() == 0 || Cache.GetDepCache() == 0))
-		return APT::PackageSet(TASK);
+		return false;
+
+	bool const wasEmpty = pci->empty();
+	if (wasEmpty == true)
+		pci->setConstructor(TASK);
 
-	PackageSet pkgset(TASK);
 	// get the records
 	pkgRecords Recs(Cache);
 
@@ -54,9 +57,10 @@ PackageSet PackageSet::FromTask(pkgCacheFile &Cache, std::string pattern, CacheS
 	snprintf(S, sizeof(S), "^Task:.*[, ]%s([, ]|$)", pattern.c_str());
 	if(regcomp(&Pattern,S, REG_EXTENDED | REG_NOSUB | REG_NEWLINE) != 0) {
 		_error->Error("Failed to compile task regexp");
-		return pkgset;
+		return false;
 	}
 
+	bool found = false;
 	for (pkgCache::GrpIterator Grp = Cache->GrpBegin(); Grp.end() == false; ++Grp) {
 		pkgCache::PkgIterator Pkg = Grp.FindPkg(arch);
 		if (Pkg.end() == true)
@@ -75,22 +79,33 @@ PackageSet PackageSet::FromTask(pkgCacheFile &Cache, std::string pattern, CacheS
 		if (regexec(&Pattern, buf, 0, 0, 0) != 0)
 			continue;
 
-		pkgset.insert(Pkg);
+		pci->insert(Pkg);
+		helper.showTaskSelection(Pkg, pattern);
+		found = true;
 	}
 	regfree(&Pattern);
 
-	if (pkgset.empty() == true)
-		return helper.canNotFindTask(Cache, pattern);
+	if (found == false) {
+		helper.canNotFindTask(pci, Cache, pattern);
+		pci->setConstructor(UNKNOWN);
+		return false;
+	}
+
+	if (wasEmpty == false && pci->getConstructor() != UNKNOWN)
+		pci->setConstructor(UNKNOWN);
 
-	helper.showTaskSelection(pkgset, pattern);
-	return pkgset;
+	return true;
 }
 									/*}}}*/
 // FromRegEx - Return all packages in the cache matching a pattern	/*{{{*/
-PackageSet PackageSet::FromRegEx(pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper) {
+bool PackageContainerInterface::FromRegEx(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper) {
 	static const char * const isregex = ".?+*|[^$";
 	if (pattern.find_first_of(isregex) == std::string::npos)
-		return PackageSet(REGEX);
+		return false;
+
+	bool const wasEmpty = pci->empty();
+	if (wasEmpty == true)
+		pci->setConstructor(REGEX);
 
 	size_t archfound = pattern.find_last_of(':');
 	std::string arch = "native";
@@ -103,11 +118,11 @@ PackageSet PackageSet::FromRegEx(pkgCacheFile &Cache, std::string pattern, Cache
 	}
 
 	if (unlikely(Cache.GetPkgCache() == 0))
-		return PackageSet(REGEX);
+		return false;
 
 	APT::CacheFilter::PackageNameMatchesRegEx regexfilter(pattern);
 
-	PackageSet pkgset(REGEX);
+	bool found = false;
 	for (pkgCache::GrpIterator Grp = Cache.GetPkgCache()->GrpBegin(); Grp.end() == false; ++Grp) {
 		if (regexfilter(Grp) == false)
 			continue;
@@ -123,18 +138,25 @@ PackageSet PackageSet::FromRegEx(pkgCacheFile &Cache, std::string pattern, Cache
 				continue;
 		}
 
-		pkgset.insert(Pkg);
+		pci->insert(Pkg);
+		helper.showRegExSelection(Pkg, pattern);
+		found = true;
 	}
 
-	if (pkgset.empty() == true)
-		return helper.canNotFindRegEx(Cache, pattern);
+	if (found == false) {
+		helper.canNotFindRegEx(pci, Cache, pattern);
+		pci->setConstructor(UNKNOWN);
+		return false;
+	}
+
+	if (wasEmpty == false && pci->getConstructor() != UNKNOWN)
+		pci->setConstructor(UNKNOWN);
 
-	helper.showRegExSelection(pkgset, pattern);
-	return pkgset;
+	return true;
 }
 									/*}}}*/
 // FromName - Returns the package defined  by this string		/*{{{*/
-pkgCache::PkgIterator PackageSet::FromName(pkgCacheFile &Cache,
+pkgCache::PkgIterator PackageContainerInterface::FromName(pkgCacheFile &Cache,
 			std::string const &str, CacheSetHelper &helper) {
 	std::string pkg = str;
 	size_t archfound = pkg.find_last_of(':');
@@ -160,144 +182,131 @@ pkgCache::PkgIterator PackageSet::FromName(pkgCacheFile &Cache,
 	return Pkg;
 }
 									/*}}}*/
-// GroupedFromCommandLine - Return all versions specified on commandline/*{{{*/
-std::map<unsigned short, PackageSet> PackageSet::GroupedFromCommandLine(
-		pkgCacheFile &Cache, const char **cmdline,
-		std::list<PackageSet::Modifier> const &mods,
-		unsigned short const &fallback, CacheSetHelper &helper) {
-	std::map<unsigned short, PackageSet> pkgsets;
-	for (const char **I = cmdline; *I != 0; ++I) {
-		unsigned short modID = fallback;
-		std::string str = *I;
-		bool modifierPresent = false;
-		for (std::list<PackageSet::Modifier>::const_iterator mod = mods.begin();
-		     mod != mods.end(); ++mod) {
-			size_t const alength = strlen(mod->Alias);
-			switch(mod->Pos) {
-			case PackageSet::Modifier::POSTFIX:
-				if (str.compare(str.length() - alength, alength,
-						mod->Alias, 0, alength) != 0)
-					continue;
-				str.erase(str.length() - alength);
-				modID = mod->ID;
-				break;
-			case PackageSet::Modifier::PREFIX:
-				continue;
-			case PackageSet::Modifier::NONE:
-				continue;
-			}
-			modifierPresent = true;
-			break;
-		}
-		if (modifierPresent == true) {
-			bool const errors = helper.showErrors(false);
-			pkgCache::PkgIterator Pkg = FromName(Cache, *I, helper);
-			helper.showErrors(errors);
-			if (Pkg.end() == false) {
-				pkgsets[fallback].insert(Pkg);
-				continue;
-			}
-		}
-		pkgsets[modID].insert(PackageSet::FromString(Cache, str, helper));
-	}
-	return pkgsets;
-}
-									/*}}}*/
-// FromCommandLine - Return all packages specified on commandline	/*{{{*/
-PackageSet PackageSet::FromCommandLine(pkgCacheFile &Cache, const char **cmdline, CacheSetHelper &helper) {
-	PackageSet pkgset;
-	for (const char **I = cmdline; *I != 0; ++I) {
-		PackageSet pset = FromString(Cache, *I, helper);
-		pkgset.insert(pset.begin(), pset.end());
-	}
-	return pkgset;
-}
-									/*}}}*/
 // FromString - Return all packages matching a specific string		/*{{{*/
-PackageSet PackageSet::FromString(pkgCacheFile &Cache, std::string const &str, CacheSetHelper &helper) {
+bool PackageContainerInterface::FromString(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string const &str, CacheSetHelper &helper) {
+	bool found = true;
 	_error->PushToStack();
 
-	PackageSet pkgset;
 	pkgCache::PkgIterator Pkg = FromName(Cache, str, helper);
 	if (Pkg.end() == false)
-		pkgset.insert(Pkg);
-	else {
-		pkgset = FromTask(Cache, str, helper);
-		if (pkgset.empty() == true) {
-			pkgset = FromRegEx(Cache, str, helper);
-			if (pkgset.empty() == true)
-				pkgset = helper.canNotFindPackage(Cache, str);
-		}
+		pci->insert(Pkg);
+	else if (FromTask(pci, Cache, str, helper) == false &&
+		 FromRegEx(pci, Cache, str, helper) == false)
+	{
+		helper.canNotFindPackage(pci, Cache, str);
+		found = false;
 	}
 
-	if (pkgset.empty() == false)
+	if (found == true)
 		_error->RevertToStack();
 	else
 		_error->MergeWithStack();
-	return pkgset;
+	return found;
 }
 									/*}}}*/
-// GroupedFromCommandLine - Return all versions specified on commandline/*{{{*/
-std::map<unsigned short, VersionSet> VersionSet::GroupedFromCommandLine(
-		pkgCacheFile &Cache, const char **cmdline,
-		std::list<VersionSet::Modifier> const &mods,
-		unsigned short const &fallback, CacheSetHelper &helper) {
-	std::map<unsigned short, VersionSet> versets;
-	for (const char **I = cmdline; *I != 0; ++I) {
-		unsigned short modID = fallback;
-		VersionSet::Version select = VersionSet::NEWEST;
-		std::string str = *I;
-		bool modifierPresent = false;
-		for (std::list<VersionSet::Modifier>::const_iterator mod = mods.begin();
-		     mod != mods.end(); ++mod) {
-			if (modID == fallback && mod->ID == fallback)
-				select = mod->SelectVersion;
-			size_t const alength = strlen(mod->Alias);
-			switch(mod->Pos) {
-			case VersionSet::Modifier::POSTFIX:
-				if (str.compare(str.length() - alength, alength,
-						mod->Alias, 0, alength) != 0)
-					continue;
-				str.erase(str.length() - alength);
-				modID = mod->ID;
-				select = mod->SelectVersion;
-				break;
-			case VersionSet::Modifier::PREFIX:
-				continue;
-			case VersionSet::Modifier::NONE:
+// FromCommandLine - Return all packages specified on commandline	/*{{{*/
+bool PackageContainerInterface::FromCommandLine(PackageContainerInterface * const pci, pkgCacheFile &Cache, const char **cmdline, CacheSetHelper &helper) {
+	bool found = false;
+	for (const char **I = cmdline; *I != 0; ++I)
+		found |= PackageContainerInterface::FromString(pci, Cache, *I, helper);
+	return found;
+}
+									/*}}}*/
+// FromModifierCommandLine - helper doing the work for PKG:GroupedFromCommandLine	/*{{{*/
+bool PackageContainerInterface::FromModifierCommandLine(unsigned short &modID, PackageContainerInterface * const pci,
+							pkgCacheFile &Cache, const char * cmdline,
+							std::list<Modifier> const &mods, CacheSetHelper &helper) {
+	std::string str = cmdline;
+	bool modifierPresent = false;
+	for (std::list<Modifier>::const_iterator mod = mods.begin();
+	     mod != mods.end(); ++mod) {
+		size_t const alength = strlen(mod->Alias);
+		switch(mod->Pos) {
+		case Modifier::POSTFIX:
+			if (str.compare(str.length() - alength, alength,
+					mod->Alias, 0, alength) != 0)
 				continue;
-			}
-			modifierPresent = true;
+			str.erase(str.length() - alength);
+			modID = mod->ID;
 			break;
+		case Modifier::PREFIX:
+			continue;
+		case Modifier::NONE:
+			continue;
 		}
-
-		if (modifierPresent == true) {
-			bool const errors = helper.showErrors(false);
-			VersionSet const vset = VersionSet::FromString(Cache, std::string(*I), select, helper, true);
-			helper.showErrors(errors);
-			if (vset.empty() == false) {
-				versets[fallback].insert(vset);
+		modifierPresent = true;
+		break;
+	}
+	if (modifierPresent == true) {
+		bool const errors = helper.showErrors(false);
+		pkgCache::PkgIterator Pkg = FromName(Cache, cmdline, helper);
+		helper.showErrors(errors);
+		if (Pkg.end() == false) {
+			pci->insert(Pkg);
+			return true;
+		}
+	}
+	return FromString(pci, Cache, str, helper);
+}
+									/*}}}*/
+// FromModifierCommandLine - helper doing the work for VER:GroupedFromCommandLine	/*{{{*/
+bool VersionContainerInterface::FromModifierCommandLine(unsigned short &modID,
+							VersionContainerInterface * const vci,
+							pkgCacheFile &Cache, const char * cmdline,
+							std::list<Modifier> const &mods,
+							CacheSetHelper &helper) {
+	Version select = NEWEST;
+	std::string str = cmdline;
+	bool modifierPresent = false;
+	unsigned short fallback = modID;
+	for (std::list<Modifier>::const_iterator mod = mods.begin();
+	     mod != mods.end(); ++mod) {
+		if (modID == fallback && mod->ID == fallback)
+			select = mod->SelectVersion;
+		size_t const alength = strlen(mod->Alias);
+		switch(mod->Pos) {
+		case Modifier::POSTFIX:
+			if (str.compare(str.length() - alength, alength,
+					mod->Alias, 0, alength) != 0)
 				continue;
-			}
+			str.erase(str.length() - alength);
+			modID = mod->ID;
+			select = mod->SelectVersion;
+			break;
+		case Modifier::PREFIX:
+			continue;
+		case Modifier::NONE:
+			continue;
 		}
-		versets[modID].insert(VersionSet::FromString(Cache, str, select , helper));
+		modifierPresent = true;
+		break;
 	}
-	return versets;
+
+	if (modifierPresent == true) {
+		bool const errors = helper.showErrors(false);
+		bool const found = VersionContainerInterface::FromString(vci, Cache, cmdline, select, helper, true);
+		helper.showErrors(errors);
+		if (found == true)
+			return true;
+	}
+	return FromString(vci, Cache, str, select, helper);
 }
 									/*}}}*/
 // FromCommandLine - Return all versions specified on commandline	/*{{{*/
-APT::VersionSet VersionSet::FromCommandLine(pkgCacheFile &Cache, const char **cmdline,
-		APT::VersionSet::Version const &fallback, CacheSetHelper &helper) {
-	VersionSet verset;
+bool VersionContainerInterface::FromCommandLine(VersionContainerInterface * const vci,
+						pkgCacheFile &Cache, const char **cmdline,
+						Version const &fallback, CacheSetHelper &helper) {
+	bool found = false;
 	for (const char **I = cmdline; *I != 0; ++I)
-		verset.insert(VersionSet::FromString(Cache, *I, fallback, helper));
-	return verset;
+		found |= VersionContainerInterface::FromString(vci, Cache, *I, fallback, helper);
+	return found;
 }
 									/*}}}*/
 // FromString - Returns all versions spedcified by a string		/*{{{*/
-APT::VersionSet VersionSet::FromString(pkgCacheFile &Cache, std::string pkg,
-		APT::VersionSet::Version const &fallback, CacheSetHelper &helper,
-		bool const &onlyFromName) {
+bool VersionContainerInterface::FromString(VersionContainerInterface * const vci,
+					   pkgCacheFile &Cache, std::string pkg,
+					   Version const &fallback, CacheSetHelper &helper,
+					   bool const onlyFromName) {
 	std::string ver;
 	bool verIsRel = false;
 	size_t const vertag = pkg.find_last_of("/=");
@@ -308,19 +317,20 @@ APT::VersionSet VersionSet::FromString(pkgCacheFile &Cache, std::string pkg,
 	}
 	PackageSet pkgset;
 	if (onlyFromName == false)
-		pkgset = PackageSet::FromString(Cache, pkg, helper);
+		PackageContainerInterface::FromString(&pkgset, Cache, pkg, helper);
 	else {
-		pkgset.insert(PackageSet::FromName(Cache, pkg, helper));
+		pkgset.insert(PackageContainerInterface::FromName(Cache, pkg, helper));
 	}
 
-	VersionSet verset;
 	bool errors = true;
 	if (pkgset.getConstructor() != PackageSet::UNKNOWN)
 		errors = helper.showErrors(false);
+
+	bool found = false;
 	for (PackageSet::const_iterator P = pkgset.begin();
 	     P != pkgset.end(); ++P) {
 		if (vertag == std::string::npos) {
-			verset.insert(VersionSet::FromPackage(Cache, P, fallback, helper));
+			found |= VersionContainerInterface::FromPackage(vci, Cache, P, fallback, helper);
 			continue;
 		}
 		pkgCache::VerIterator V;
@@ -350,75 +360,78 @@ APT::VersionSet VersionSet::FromString(pkgCacheFile &Cache, std::string pkg,
 		if (V.end() == true)
 			continue;
 		helper.showSelectedVersion(P, V, ver, verIsRel);
-		verset.insert(V);
+		vci->insert(V);
+		found = true;
 	}
 	if (pkgset.getConstructor() != PackageSet::UNKNOWN)
 		helper.showErrors(errors);
-	return verset;
+	return found;
 }
 									/*}}}*/
 // FromPackage - versions from package based on fallback		/*{{{*/
-VersionSet VersionSet::FromPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &P,
-		VersionSet::Version const &fallback, CacheSetHelper &helper) {
-	VersionSet verset;
+bool VersionContainerInterface::FromPackage(VersionContainerInterface * const vci,
+					    pkgCacheFile &Cache,
+					    pkgCache::PkgIterator const &P,
+					    Version const &fallback,
+					    CacheSetHelper &helper) {
 	pkgCache::VerIterator V;
 	bool showErrors;
+	bool found = false;
 	switch(fallback) {
-	case VersionSet::ALL:
+	case ALL:
 		if (P->VersionList != 0)
 			for (V = P.VersionList(); V.end() != true; ++V)
-				verset.insert(V);
+				found |= vci->insert(V);
 		else
-			verset.insert(helper.canNotFindAllVer(Cache, P));
+			helper.canNotFindAllVer(vci, Cache, P);
 		break;
-	case VersionSet::CANDANDINST:
-		verset.insert(getInstalledVer(Cache, P, helper));
-		verset.insert(getCandidateVer(Cache, P, helper));
+	case CANDANDINST:
+		found |= vci->insert(getInstalledVer(Cache, P, helper));
+		found |= vci->insert(getCandidateVer(Cache, P, helper));
 		break;
-	case VersionSet::CANDIDATE:
-		verset.insert(getCandidateVer(Cache, P, helper));
+	case CANDIDATE:
+		found |= vci->insert(getCandidateVer(Cache, P, helper));
 		break;
-	case VersionSet::INSTALLED:
-		verset.insert(getInstalledVer(Cache, P, helper));
+	case INSTALLED:
+		found |= vci->insert(getInstalledVer(Cache, P, helper));
 		break;
-	case VersionSet::CANDINST:
+	case CANDINST:
 		showErrors = helper.showErrors(false);
 		V = getCandidateVer(Cache, P, helper);
 		if (V.end() == true)
 			V = getInstalledVer(Cache, P, helper);
 		helper.showErrors(showErrors);
 		if (V.end() == false)
-			verset.insert(V);
+			found |= vci->insert(V);
 		else
-			verset.insert(helper.canNotFindInstCandVer(Cache, P));
+			helper.canNotFindInstCandVer(vci, Cache, P);
 		break;
-	case VersionSet::INSTCAND:
+	case INSTCAND:
 		showErrors = helper.showErrors(false);
 		V = getInstalledVer(Cache, P, helper);
 		if (V.end() == true)
 			V = getCandidateVer(Cache, P, helper);
 		helper.showErrors(showErrors);
 		if (V.end() == false)
-			verset.insert(V);
+			found |= vci->insert(V);
 		else
-			verset.insert(helper.canNotFindInstCandVer(Cache, P));
+			helper.canNotFindInstCandVer(vci, Cache, P);
 		break;
-	case VersionSet::NEWEST:
+	case NEWEST:
 		if (P->VersionList != 0)
-			verset.insert(P.VersionList());
+			found |= vci->insert(P.VersionList());
 		else
-			verset.insert(helper.canNotFindNewestVer(Cache, P));
+			helper.canNotFindNewestVer(Cache, P);
 		break;
 	}
-	return verset;
+	return found;
 }
 									/*}}}*/
 // getCandidateVer - Returns the candidate version of the given package	/*{{{*/
-pkgCache::VerIterator VersionSet::getCandidateVer(pkgCacheFile &Cache,
+pkgCache::VerIterator VersionContainerInterface::getCandidateVer(pkgCacheFile &Cache,
 		pkgCache::PkgIterator const &Pkg, CacheSetHelper &helper) {
 	pkgCache::VerIterator Cand;
-	if (Cache.IsPolicyBuilt() == true || Cache.IsDepCacheBuilt() == false)
-	{
+	if (Cache.IsPolicyBuilt() == true || Cache.IsDepCacheBuilt() == false) {
 		if (unlikely(Cache.GetPolicy() == 0))
 			return pkgCache::VerIterator(Cache);
 		Cand = Cache.GetPolicy()->GetCandidateVer(Pkg);
@@ -431,13 +444,14 @@ pkgCache::VerIterator VersionSet::getCandidateVer(pkgCacheFile &Cache,
 }
 									/*}}}*/
 // getInstalledVer - Returns the installed version of the given package	/*{{{*/
-pkgCache::VerIterator VersionSet::getInstalledVer(pkgCacheFile &Cache,
+pkgCache::VerIterator VersionContainerInterface::getInstalledVer(pkgCacheFile &Cache,
 		pkgCache::PkgIterator const &Pkg, CacheSetHelper &helper) {
 	if (Pkg->CurrentVer == 0)
 		return helper.canNotFindInstalledVer(Cache, Pkg);
 	return Pkg.CurrentVer();
 }
 									/*}}}*/
+
 // canNotFindPkgName - handle the case no package has this name		/*{{{*/
 pkgCache::PkgIterator CacheSetHelper::canNotFindPkgName(pkgCacheFile &Cache,
 			std::string const &str) {
@@ -447,46 +461,40 @@ pkgCache::PkgIterator CacheSetHelper::canNotFindPkgName(pkgCacheFile &Cache,
 }
 									/*}}}*/
 // canNotFindTask - handle the case no package is found for a task	/*{{{*/
-PackageSet CacheSetHelper::canNotFindTask(pkgCacheFile &Cache, std::string pattern) {
+void CacheSetHelper::canNotFindTask(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern) {
 	if (ShowError == true)
 		_error->Insert(ErrorType, _("Couldn't find task '%s'"), pattern.c_str());
-	return PackageSet();
 }
 									/*}}}*/
 // canNotFindRegEx - handle the case no package is found by a regex	/*{{{*/
-PackageSet CacheSetHelper::canNotFindRegEx(pkgCacheFile &Cache, std::string pattern) {
+void CacheSetHelper::canNotFindRegEx(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern) {
 	if (ShowError == true)
 		_error->Insert(ErrorType, _("Couldn't find any package by regex '%s'"), pattern.c_str());
-	return PackageSet();
 }
 									/*}}}*/
 // canNotFindPackage - handle the case no package is found from a string/*{{{*/
-PackageSet CacheSetHelper::canNotFindPackage(pkgCacheFile &Cache, std::string const &str) {
-	return PackageSet();
+void CacheSetHelper::canNotFindPackage(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string const &str) {
 }
 									/*}}}*/
 // canNotFindAllVer							/*{{{*/
-VersionSet CacheSetHelper::canNotFindAllVer(pkgCacheFile &Cache,
+void CacheSetHelper::canNotFindAllVer(VersionContainerInterface * const vci, pkgCacheFile &Cache,
 		pkgCache::PkgIterator const &Pkg) {
 	if (ShowError == true)
 		_error->Insert(ErrorType, _("Can't select versions from package '%s' as it is purely virtual"), Pkg.FullName(true).c_str());
-	return VersionSet();
 }
 									/*}}}*/
 // canNotFindInstCandVer						/*{{{*/
-VersionSet CacheSetHelper::canNotFindInstCandVer(pkgCacheFile &Cache,
+void CacheSetHelper::canNotFindInstCandVer(VersionContainerInterface * const vci, pkgCacheFile &Cache,
 		pkgCache::PkgIterator const &Pkg) {
 	if (ShowError == true)
 		_error->Insert(ErrorType, _("Can't select installed nor candidate version from package '%s' as it has neither of them"), Pkg.FullName(true).c_str());
-	return VersionSet();
 }
 									/*}}}*/
 // canNotFindInstCandVer						/*{{{*/
-VersionSet CacheSetHelper::canNotFindCandInstVer(pkgCacheFile &Cache,
+void CacheSetHelper::canNotFindCandInstVer(VersionContainerInterface * const vci, pkgCacheFile &Cache,
 		pkgCache::PkgIterator const &Pkg) {
 	if (ShowError == true)
 		_error->Insert(ErrorType, _("Can't select installed nor candidate version from package '%s' as it has neither of them"), Pkg.FullName(true).c_str());
-	return VersionSet();
 }
 									/*}}}*/
 // canNotFindNewestVer							/*{{{*/
@@ -513,4 +521,21 @@ pkgCache::VerIterator CacheSetHelper::canNotFindInstalledVer(pkgCacheFile &Cache
 	return pkgCache::VerIterator(Cache, 0);
 }
 									/*}}}*/
+// showTaskSelection							/*{{{*/
+void CacheSetHelper::showTaskSelection(pkgCache::PkgIterator const &pkg,
+				       std::string const &pattern) {
+}
+									/*}}}*/
+// showRegExSelection							/*{{{*/
+void CacheSetHelper::showRegExSelection(pkgCache::PkgIterator const &pkg,
+					std::string const &pattern) {
+}
+									/*}}}*/
+// showSelectedVersion							/*{{{*/
+void CacheSetHelper::showSelectedVersion(pkgCache::PkgIterator const &Pkg,
+					 pkgCache::VerIterator const Ver,
+					 std::string const &ver,
+					 bool const verIsRel) {
+}
+									/*}}}*/
 }
diff --git a/apt-pkg/cacheset.h b/apt-pkg/cacheset.h
index 3b1118bdc..d1e396e0f 100644
--- a/apt-pkg/cacheset.h
+++ b/apt-pkg/cacheset.h
@@ -14,7 +14,9 @@
 #include <list>
 #include <map>
 #include <set>
+#include <list>
 #include <string>
+#include <iterator>
 
 #include <apt-pkg/error.h>
 #include <apt-pkg/pkgcache.h>
@@ -23,8 +25,9 @@
 class pkgCacheFile;
 
 namespace APT {
-class PackageSet;
-class VersionSet;
+class PackageContainerInterface;
+class VersionContainerInterface;
+
 class CacheSetHelper {							/*{{{*/
 /** \class APT::CacheSetHelper
     Simple base class with a lot of virtual methods which can be overridden
@@ -35,25 +38,28 @@ class CacheSetHelper {							/*{{{*/
     printed out.
 */
 public:									/*{{{*/
-	CacheSetHelper(bool const &ShowError = true,
+	CacheSetHelper(bool const ShowError = true,
 		GlobalError::MsgType ErrorType = GlobalError::ERROR) :
 			ShowError(ShowError), ErrorType(ErrorType) {};
 	virtual ~CacheSetHelper() {};
 
-	virtual void showTaskSelection(PackageSet const &pkgset, std::string const &pattern) {};
-	virtual void showRegExSelection(PackageSet const &pkgset, std::string const &pattern) {};
+	virtual void showTaskSelection(pkgCache::PkgIterator const &pkg, std::string const &pattern);
+	virtual void showRegExSelection(pkgCache::PkgIterator const &pkg, std::string const &pattern);
 	virtual void showSelectedVersion(pkgCache::PkgIterator const &Pkg, pkgCache::VerIterator const Ver,
-				 std::string const &ver, bool const &verIsRel) {};
+				 std::string const &ver, bool const verIsRel);
 
-	virtual pkgCache::PkgIterator canNotFindPkgName(pkgCacheFile &Cache, std::string const &str);
-	virtual PackageSet canNotFindTask(pkgCacheFile &Cache, std::string pattern);
-	virtual PackageSet canNotFindRegEx(pkgCacheFile &Cache, std::string pattern);
-	virtual PackageSet canNotFindPackage(pkgCacheFile &Cache, std::string const &str);
-	virtual VersionSet canNotFindAllVer(pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg);
-	virtual VersionSet canNotFindInstCandVer(pkgCacheFile &Cache,
+	virtual void canNotFindTask(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern);
+	virtual void canNotFindRegEx(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern);
+	virtual void canNotFindPackage(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string const &str);
+
+	virtual void canNotFindAllVer(VersionContainerInterface * const vci, pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg);
+	virtual void canNotFindInstCandVer(VersionContainerInterface * const vci, pkgCacheFile &Cache,
 				pkgCache::PkgIterator const &Pkg);
-	virtual VersionSet canNotFindCandInstVer(pkgCacheFile &Cache,
+	virtual void canNotFindCandInstVer(VersionContainerInterface * const vci,
+				pkgCacheFile &Cache,
 				pkgCache::PkgIterator const &Pkg);
+
+	virtual pkgCache::PkgIterator canNotFindPkgName(pkgCacheFile &Cache, std::string const &str);
 	virtual pkgCache::VerIterator canNotFindNewestVer(pkgCacheFile &Cache,
 				pkgCache::PkgIterator const &Pkg);
 	virtual pkgCache::VerIterator canNotFindCandidateVer(pkgCacheFile &Cache,
@@ -62,7 +68,7 @@ public:									/*{{{*/
 				pkgCache::PkgIterator const &Pkg);
 
 	bool showErrors() const { return ShowError; };
-	bool showErrors(bool const &newValue) { if (ShowError == newValue) return ShowError; else return ((ShowError = newValue) == false); };
+	bool showErrors(bool const newValue) { if (ShowError == newValue) return ShowError; else return ((ShowError = newValue) == false); };
 	GlobalError::MsgType errorType() const { return ErrorType; };
 	GlobalError::MsgType errorType(GlobalError::MsgType const &newValue)
 	{
@@ -79,53 +85,134 @@ protected:
 	bool ShowError;
 	GlobalError::MsgType ErrorType;
 };									/*}}}*/
-class PackageSet : public std::set<pkgCache::PkgIterator> {		/*{{{*/
-/** \class APT::PackageSet
-
-    Simple wrapper around a std::set to provide a similar interface to
-    a set of packages as to the complete set of all packages in the
-    pkgCache. */
-public:									/*{{{*/
-	/** \brief smell like a pkgCache::PkgIterator */
-	class const_iterator : public std::set<pkgCache::PkgIterator>::const_iterator {/*{{{*/
+class PackageContainerInterface {					/*{{{*/
+/** \class PackageContainerInterface
+
+ * Interface ensuring that all operations can be executed on the yet to
+ * define concrete PackageContainer - access to all methods is possible,
+ * but in general the wrappers provided by the PackageContainer template
+ * are nicer to use.
+
+ * This class mostly protects use from the need to write all implementation
+ * of the methods working on containers in the template */
+public:
+	class const_iterator {						/*{{{*/
 	public:
-		const_iterator(std::set<pkgCache::PkgIterator>::const_iterator x) :
-			 std::set<pkgCache::PkgIterator>::const_iterator(x) {}
-
-		operator pkgCache::PkgIterator(void) { return **this; }
-
-		inline const char *Name() const {return (**this).Name(); }
-		inline std::string FullName(bool const &Pretty) const { return (**this).FullName(Pretty); }
-		inline std::string FullName() const { return (**this).FullName(); }
-		inline const char *Section() const {return (**this).Section(); }
-		inline bool Purge() const {return (**this).Purge(); }
-		inline const char *Arch() const {return (**this).Arch(); }
-		inline pkgCache::GrpIterator Group() const { return (**this).Group(); }
-		inline pkgCache::VerIterator VersionList() const { return (**this).VersionList(); }
-		inline pkgCache::VerIterator CurrentVer() const { return (**this).CurrentVer(); }
-		inline pkgCache::DepIterator RevDependsList() const { return (**this).RevDependsList(); }
-		inline pkgCache::PrvIterator ProvidesList() const { return (**this).ProvidesList(); }
-		inline pkgCache::PkgIterator::OkState State() const { return (**this).State(); }
-		inline const char *CandVersion() const { return (**this).CandVersion(); }
-		inline const char *CurVersion() const { return (**this).CurVersion(); }
-		inline pkgCache *Cache() const { return (**this).Cache(); };
-		inline unsigned long Index() const {return (**this).Index();};
+		virtual pkgCache::PkgIterator getPkg() const = 0;
+		operator pkgCache::PkgIterator(void) const { return getPkg(); }
+
+		inline const char *Name() const {return getPkg().Name(); }
+		inline std::string FullName(bool const Pretty) const { return getPkg().FullName(Pretty); }
+		inline std::string FullName() const { return getPkg().FullName(); }
+		inline const char *Section() const {return getPkg().Section(); }
+		inline bool Purge() const {return getPkg().Purge(); }
+		inline const char *Arch() const {return getPkg().Arch(); }
+		inline pkgCache::GrpIterator Group() const { return getPkg().Group(); }
+		inline pkgCache::VerIterator VersionList() const { return getPkg().VersionList(); }
+		inline pkgCache::VerIterator CurrentVer() const { return getPkg().CurrentVer(); }
+		inline pkgCache::DepIterator RevDependsList() const { return getPkg().RevDependsList(); }
+		inline pkgCache::PrvIterator ProvidesList() const { return getPkg().ProvidesList(); }
+		inline pkgCache::PkgIterator::OkState State() const { return getPkg().State(); }
+		inline const char *CandVersion() const { return getPkg().CandVersion(); }
+		inline const char *CurVersion() const { return getPkg().CurVersion(); }
+		inline pkgCache *Cache() const { return getPkg().Cache(); };
+		inline unsigned long Index() const {return getPkg().Index();};
 		// we have only valid iterators here
 		inline bool end() const { return false; };
 
-		friend std::ostream& operator<<(std::ostream& out, const_iterator i) { return operator<<(out, (*i)); }
+		inline pkgCache::Package const * operator->() const {return &*getPkg();};
+	};
+									/*}}}*/
+
+	virtual bool insert(pkgCache::PkgIterator const &P) = 0;
+	virtual bool empty() const = 0;
+	virtual void clear() = 0;
+
+	enum Constructor { UNKNOWN, REGEX, TASK };
+	virtual void setConstructor(Constructor const &con) = 0;
+	virtual Constructor getConstructor() const = 0;
 
-		inline pkgCache::Package const * operator->() const {
-			return &***this;
-		};
+	static bool FromTask(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper);
+	static bool FromRegEx(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper);
+	static pkgCache::PkgIterator FromName(pkgCacheFile &Cache, std::string const &pattern, CacheSetHelper &helper);
+	static bool FromString(PackageContainerInterface * const pci, pkgCacheFile &Cache, std::string const &pattern, CacheSetHelper &helper);
+	static bool FromCommandLine(PackageContainerInterface * const pci, pkgCacheFile &Cache, const char **cmdline, CacheSetHelper &helper);
+
+	struct Modifier {
+		enum Position { NONE, PREFIX, POSTFIX };
+		unsigned short ID;
+		const char * const Alias;
+		Position Pos;
+		Modifier (unsigned short const &id, const char * const alias, Position const &pos) : ID(id), Alias(alias), Pos(pos) {};
+	};
+
+	static bool FromModifierCommandLine(unsigned short &modID, PackageContainerInterface * const pci,
+					    pkgCacheFile &Cache, const char * cmdline,
+					    std::list<Modifier> const &mods, CacheSetHelper &helper);
+};
+									/*}}}*/
+template<class Container> class PackageContainer : public PackageContainerInterface {/*{{{*/
+/** \class APT::PackageContainer
+
+    Simple wrapper around a container class like std::set to provide a similar
+    interface to a set of packages as to the complete set of all packages in the
+    pkgCache. */
+	Container _cont;
+public:									/*{{{*/
+	/** \brief smell like a pkgCache::PkgIterator */
+	class const_iterator : public PackageContainerInterface::const_iterator,/*{{{*/
+			       public std::iterator<std::forward_iterator_tag, typename Container::const_iterator> {
+		typename Container::const_iterator _iter;
+	public:
+		const_iterator(typename Container::const_iterator i) : _iter(i) {}
+		pkgCache::PkgIterator getPkg(void) const { return *_iter; }
+		inline pkgCache::PkgIterator operator*(void) const { return *_iter; };
+		operator typename Container::const_iterator(void) const { return _iter; }
+		inline const_iterator& operator++() { ++_iter; return *this; }
+		inline const_iterator operator++(int) { const_iterator tmp(*this); operator++(); return tmp; }
+		inline bool operator!=(const_iterator const &i) const { return _iter != i._iter; };
+		inline bool operator==(const_iterator const &i) const { return _iter == i._iter; };
+		friend std::ostream& operator<<(std::ostream& out, const_iterator i) { return operator<<(out, *i); }
+	};
+	class iterator : public PackageContainerInterface::const_iterator,
+			 public std::iterator<std::forward_iterator_tag, typename Container::iterator> {
+		typename Container::iterator _iter;
+	public:
+		iterator(typename Container::iterator i) : _iter(i) {}
+		pkgCache::PkgIterator getPkg(void) const { return *_iter; }
+		inline pkgCache::PkgIterator operator*(void) const { return *_iter; };
+		operator typename Container::iterator(void) const { return _iter; }
+		operator typename PackageContainer<Container>::const_iterator() { return PackageContainer<Container>::const_iterator(_iter); }
+		inline iterator& operator++() { ++_iter; return *this; }
+		inline iterator operator++(int) { iterator tmp(*this); operator++(); return tmp; }
+		inline bool operator!=(iterator const &i) const { return _iter != i._iter; };
+		inline bool operator==(iterator const &i) const { return _iter == i._iter; };
+		friend std::ostream& operator<<(std::ostream& out, iterator i) { return operator<<(out, *i); }
 	};
-	// 103. set::iterator is required to be modifiable, but this allows modification of keys
-	typedef APT::PackageSet::const_iterator iterator;
 									/*}}}*/
 
-	using std::set<pkgCache::PkgIterator>::insert;
-	inline void insert(pkgCache::PkgIterator const &P) { if (P.end() == false) std::set<pkgCache::PkgIterator>::insert(P); };
-	inline void insert(PackageSet const &pkgset) { insert(pkgset.begin(), pkgset.end()); };
+	bool insert(pkgCache::PkgIterator const &P) { if (P.end() == true) return false; _cont.insert(P); return true; };
+	template<class Cont> void insert(PackageContainer<Cont> const &pkgcont) { _cont.insert((typename Cont::const_iterator)pkgcont.begin(), (typename Cont::const_iterator)pkgcont.end()); };
+	void insert(const_iterator begin, const_iterator end) { _cont.insert(begin, end); };
+
+	bool empty() const { return _cont.empty(); };
+	void clear() { return _cont.clear(); };
+	void erase(iterator position) { _cont.erase((typename Container::iterator)position); };
+	size_t erase(const pkgCache::PkgIterator x) { return _cont.erase(x); };
+	void erase(iterator first, iterator last) { _cont.erase(first, last); };
+	size_t size() const { return _cont.size(); };
+
+	const_iterator begin() const { return const_iterator(_cont.begin()); };
+	const_iterator end() const { return const_iterator(_cont.end()); };
+	iterator begin() { return iterator(_cont.begin()); };
+	iterator end() { return iterator(_cont.end()); };
+	const_iterator find(pkgCache::PkgIterator const &P) const { return const_iterator(_cont.find(P)); };
+
+	void setConstructor(Constructor const &by) { ConstructedBy = by; };
+	Constructor getConstructor() const { return ConstructedBy; };
+
+	PackageContainer() : ConstructedBy(UNKNOWN) {};
+	PackageContainer(Constructor const &by) : ConstructedBy(by) {};
 
 	/** \brief returns all packages in the cache who belong to the given task
 
@@ -135,8 +222,12 @@ public:									/*{{{*/
 	    \param Cache the packages are in
 	    \param pattern name of the task
 	    \param helper responsible for error and message handling */
-	static APT::PackageSet FromTask(pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper);
-	static APT::PackageSet FromTask(pkgCacheFile &Cache, std::string const &pattern) {
+	static PackageContainer FromTask(pkgCacheFile &Cache, std::string const &pattern, CacheSetHelper &helper) {
+		PackageContainer cont(TASK);
+		PackageContainerInterface::FromTask(&cont, Cache, pattern, helper);
+		return cont;
+	}
+	static PackageContainer FromTask(pkgCacheFile &Cache, std::string const &pattern) {
 		CacheSetHelper helper;
 		return FromTask(Cache, pattern, helper);
 	}
@@ -149,32 +240,43 @@ public:									/*{{{*/
 	    \param Cache the packages are in
 	    \param pattern regular expression for package names
 	    \param helper responsible for error and message handling */
-	static APT::PackageSet FromRegEx(pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper);
-	static APT::PackageSet FromRegEx(pkgCacheFile &Cache, std::string const &pattern) {
+	static PackageContainer FromRegEx(pkgCacheFile &Cache, std::string pattern, CacheSetHelper &helper) {
+		PackageContainer cont(REGEX);
+		PackageContainerInterface::FromRegEx(&cont, Cache, pattern, helper);
+		return cont;
+	}
+
+	static PackageContainer FromRegEx(pkgCacheFile &Cache, std::string const &pattern) {
 		CacheSetHelper helper;
 		return FromRegEx(Cache, pattern, helper);
 	}
 
-	/** \brief returns all packages specified by a string
+	/** \brief returns a package specified by a string
 
-	    \param Cache the packages are in
-	    \param string String the package name(s) should be extracted from
+	    \param Cache the package is in
+	    \param pattern String the package name should be extracted from
 	    \param helper responsible for error and message handling */
-	static APT::PackageSet FromString(pkgCacheFile &Cache, std::string const &string, CacheSetHelper &helper);
-	static APT::PackageSet FromString(pkgCacheFile &Cache, std::string const &string) {
+	static pkgCache::PkgIterator FromName(pkgCacheFile &Cache, std::string const &pattern, CacheSetHelper &helper) {
+		return PackageContainerInterface::FromName(Cache, pattern, helper);
+	}
+	static pkgCache::PkgIterator FromName(pkgCacheFile &Cache, std::string const &pattern) {
 		CacheSetHelper helper;
-		return FromString(Cache, string, helper);
+		return PackageContainerInterface::FromName(Cache, pattern, helper);
 	}
 
-	/** \brief returns a package specified by a string
+	/** \brief returns all packages specified by a string
 
-	    \param Cache the package is in
-	    \param string String the package name should be extracted from
+	    \param Cache the packages are in
+	    \param pattern String the package name(s) should be extracted from
 	    \param helper responsible for error and message handling */
-	static pkgCache::PkgIterator FromName(pkgCacheFile &Cache, std::string const &string, CacheSetHelper &helper);
-	static pkgCache::PkgIterator FromName(pkgCacheFile &Cache, std::string const &string) {
+	static PackageContainer FromString(pkgCacheFile &Cache, std::string const &pattern, CacheSetHelper &helper) {
+		PackageContainer cont;
+		PackageContainerInterface::FromString(&cont, Cache, pattern, helper);
+		return cont;
+	}
+	static PackageContainer FromString(pkgCacheFile &Cache, std::string const &pattern) {
 		CacheSetHelper helper;
-		return FromName(Cache, string, helper);
+		return FromString(Cache, pattern, helper);
 	}
 
 	/** \brief returns all packages specified on the commandline
@@ -184,20 +286,16 @@ public:									/*{{{*/
 	    \param Cache the packages are in
 	    \param cmdline Command line the package names should be extracted from
 	    \param helper responsible for error and message handling */
-	static APT::PackageSet FromCommandLine(pkgCacheFile &Cache, const char **cmdline, CacheSetHelper &helper);
-	static APT::PackageSet FromCommandLine(pkgCacheFile &Cache, const char **cmdline) {
+	static PackageContainer FromCommandLine(pkgCacheFile &Cache, const char **cmdline, CacheSetHelper &helper) {
+		PackageContainer cont;
+		PackageContainerInterface::FromCommandLine(&cont, Cache, cmdline, helper);
+		return cont;
+	}
+	static PackageContainer FromCommandLine(pkgCacheFile &Cache, const char **cmdline) {
 		CacheSetHelper helper;
 		return FromCommandLine(Cache, cmdline, helper);
 	}
 
-	struct Modifier {
-		enum Position { NONE, PREFIX, POSTFIX };
-		unsigned short ID;
-		const char * const Alias;
-		Position Pos;
-		Modifier (unsigned short const &id, const char * const alias, Position const &pos) : ID(id), Alias(alias), Pos(pos) {};
-	};
-
 	/** \brief group packages by a action modifiers
 
 	    At some point it is needed to get from the same commandline
@@ -209,76 +307,93 @@ public:									/*{{{*/
 	    \param mods list of modifiers the method should accept
 	    \param fallback the default modifier group for a package
 	    \param helper responsible for error and message handling */
-	static std::map<unsigned short, PackageSet> GroupedFromCommandLine(
-		pkgCacheFile &Cache, const char **cmdline,
-		std::list<PackageSet::Modifier> const &mods,
-		unsigned short const &fallback, CacheSetHelper &helper);
-	static std::map<unsigned short, PackageSet> GroupedFromCommandLine(
-		pkgCacheFile &Cache, const char **cmdline,
-		std::list<PackageSet::Modifier> const &mods,
-		unsigned short const &fallback) {
+	static std::map<unsigned short, PackageContainer> GroupedFromCommandLine(
+										 pkgCacheFile &Cache,
+										 const char **cmdline,
+										 std::list<Modifier> const &mods,
+										 unsigned short const &fallback,
+										 CacheSetHelper &helper) {
+		std::map<unsigned short, PackageContainer> pkgsets;
+		for (const char **I = cmdline; *I != 0; ++I) {
+			unsigned short modID = fallback;
+			PackageContainer pkgset;
+			PackageContainerInterface::FromModifierCommandLine(modID, &pkgset, Cache, *I, mods, helper);
+			pkgsets[modID].insert(pkgset);
+		}
+		return pkgsets;
+	}
+	static std::map<unsigned short, PackageContainer> GroupedFromCommandLine(
+										 pkgCacheFile &Cache,
+										 const char **cmdline,
+										 std::list<Modifier> const &mods,
+										 unsigned short const &fallback) {
 		CacheSetHelper helper;
 		return GroupedFromCommandLine(Cache, cmdline,
 				mods, fallback, helper);
 	}
-
-	enum Constructor { UNKNOWN, REGEX, TASK };
-	Constructor getConstructor() const { return ConstructedBy; };
-
-	PackageSet() : ConstructedBy(UNKNOWN) {};
-	PackageSet(Constructor const &by) : ConstructedBy(by) {};
 									/*}}}*/
 private:								/*{{{*/
 	Constructor ConstructedBy;
 									/*}}}*/
 };									/*}}}*/
-class VersionSet : public std::set<pkgCache::VerIterator> {		/*{{{*/
-/** \class APT::VersionSet
 
-    Simple wrapper around a std::set to provide a similar interface to
-    a set of versions as to the complete set of all versions in the
-    pkgCache. */
-public:									/*{{{*/
+template<> template<class Cont> void PackageContainer<std::list<pkgCache::PkgIterator> >::insert(PackageContainer<Cont> const &pkgcont) {
+	for (typename PackageContainer<Cont>::const_iterator p = pkgcont.begin(); p != pkgcont.end(); ++p)
+		_cont.push_back(*p);
+};
+// these two are 'inline' as otherwise the linker has problems with seeing these untemplated
+// specializations again and again - but we need to see them, so that library users can use them
+template<> inline bool PackageContainer<std::list<pkgCache::PkgIterator> >::insert(pkgCache::PkgIterator const &P) {
+	if (P.end() == true)
+		return false;
+	_cont.push_back(P);
+	return true;
+};
+template<> inline void PackageContainer<std::list<pkgCache::PkgIterator> >::insert(const_iterator begin, const_iterator end) {
+	for (const_iterator p = begin; p != end; ++p)
+		_cont.push_back(*p);
+};
+typedef PackageContainer<std::set<pkgCache::PkgIterator> > PackageSet;
+typedef PackageContainer<std::list<pkgCache::PkgIterator> > PackageList;
+
+class VersionContainerInterface {					/*{{{*/
+/** \class APT::VersionContainerInterface
+
+    Same as APT::PackageContainerInterface, just for Versions */
+public:
 	/** \brief smell like a pkgCache::VerIterator */
-	class const_iterator : public std::set<pkgCache::VerIterator>::const_iterator {/*{{{*/
+	class const_iterator {						/*{{{*/
 	public:
-		const_iterator(std::set<pkgCache::VerIterator>::const_iterator x) :
-			 std::set<pkgCache::VerIterator>::const_iterator(x) {}
-
-		operator pkgCache::VerIterator(void) { return **this; }
-
-		inline pkgCache *Cache() const { return (**this).Cache(); };
-		inline unsigned long Index() const {return (**this).Index();};
+		virtual pkgCache::VerIterator getVer() const = 0;
+		operator pkgCache::VerIterator(void) { return getVer(); }
+
+		inline pkgCache *Cache() const { return getVer().Cache(); };
+		inline unsigned long Index() const {return getVer().Index();};
+		inline int CompareVer(const pkgCache::VerIterator &B) const { return getVer().CompareVer(B); };
+		inline const char *VerStr() const { return getVer().VerStr(); };
+		inline const char *Section() const { return getVer().Section(); };
+		inline const char *Arch() const { return getVer().Arch(); };
+		inline pkgCache::PkgIterator ParentPkg() const { return getVer().ParentPkg(); };
+		inline pkgCache::DescIterator DescriptionList() const { return getVer().DescriptionList(); };
+		inline pkgCache::DescIterator TranslatedDescription() const { return getVer().TranslatedDescription(); };
+		inline pkgCache::DepIterator DependsList() const { return getVer().DependsList(); };
+		inline pkgCache::PrvIterator ProvidesList() const { return getVer().ProvidesList(); };
+		inline pkgCache::VerFileIterator FileList() const { return getVer().FileList(); };
+		inline bool Downloadable() const { return getVer().Downloadable(); };
+		inline const char *PriorityType() const { return getVer().PriorityType(); };
+		inline std::string RelStr() const { return getVer().RelStr(); };
+		inline bool Automatic() const { return getVer().Automatic(); };
+		inline pkgCache::VerFileIterator NewestFile() const { return getVer().NewestFile(); };
 		// we have only valid iterators here
 		inline bool end() const { return false; };
 
-		inline pkgCache::Version const * operator->() const {
-			return &***this;
-		};
-
-		inline int CompareVer(const pkgCache::VerIterator &B) const { return (**this).CompareVer(B); };
-		inline const char *VerStr() const { return (**this).VerStr(); };
-		inline const char *Section() const { return (**this).Section(); };
-		inline const char *Arch() const { return (**this).Arch(); };
-		inline pkgCache::PkgIterator ParentPkg() const { return (**this).ParentPkg(); };
-		inline pkgCache::DescIterator DescriptionList() const { return (**this).DescriptionList(); };
-		inline pkgCache::DescIterator TranslatedDescription() const { return (**this).TranslatedDescription(); };
-		inline pkgCache::DepIterator DependsList() const { return (**this).DependsList(); };
-		inline pkgCache::PrvIterator ProvidesList() const { return (**this).ProvidesList(); };
-		inline pkgCache::VerFileIterator FileList() const { return (**this).FileList(); };
-		inline bool Downloadable() const { return (**this).Downloadable(); };
-		inline const char *PriorityType() const { return (**this).PriorityType(); };
-		inline std::string RelStr() const { return (**this).RelStr(); };
-		inline bool Automatic() const { return (**this).Automatic(); };
-		inline pkgCache::VerFileIterator NewestFile() const { return (**this).NewestFile(); };
+		inline pkgCache::Version const * operator->() const { return &*getVer(); };
 	};
 									/*}}}*/
-	// 103. set::iterator is required to be modifiable, but this allows modification of keys
-	typedef APT::VersionSet::const_iterator iterator;
 
-	using std::set<pkgCache::VerIterator>::insert;
-	inline void insert(pkgCache::VerIterator const &V) { if (V.end() == false) std::set<pkgCache::VerIterator>::insert(V); };
-	inline void insert(VersionSet const &verset) { insert(verset.begin(), verset.end()); };
+	virtual bool insert(pkgCache::VerIterator const &V) = 0;
+	virtual bool empty() const = 0;
+	virtual void clear() = 0;
 
 	/** \brief specifies which version(s) will be returned if non is given */
 	enum Version {
@@ -298,6 +413,116 @@ public:									/*{{{*/
 		NEWEST
 	};
 
+	struct Modifier {
+		enum Position { NONE, PREFIX, POSTFIX };
+		unsigned short ID;
+		const char * const Alias;
+		Position Pos;
+		Version SelectVersion;
+		Modifier (unsigned short const &id, const char * const alias, Position const &pos,
+			  Version const &select) : ID(id), Alias(alias), Pos(pos),
+			 SelectVersion(select) {};
+	};
+
+	static bool FromCommandLine(VersionContainerInterface * const vci, pkgCacheFile &Cache,
+				    const char **cmdline, Version const &fallback,
+				    CacheSetHelper &helper);
+
+	static bool FromString(VersionContainerInterface * const vci, pkgCacheFile &Cache,
+			       std::string pkg, Version const &fallback, CacheSetHelper &helper,
+			       bool const onlyFromName = false);
+
+	static bool FromPackage(VersionContainerInterface * const vci, pkgCacheFile &Cache,
+				pkgCache::PkgIterator const &P, Version const &fallback,
+				CacheSetHelper &helper);
+
+	static bool FromModifierCommandLine(unsigned short &modID,
+					    VersionContainerInterface * const vci,
+					    pkgCacheFile &Cache, const char * cmdline,
+					    std::list<Modifier> const &mods,
+					    CacheSetHelper &helper);
+
+
+	static bool FromDependency(VersionContainerInterface * const vci,
+				   pkgCacheFile &Cache,
+				   pkgCache::DepIterator const &D,
+				   Version const &selector,
+				   CacheSetHelper &helper);
+
+protected:								/*{{{*/
+
+	/** \brief returns the candidate version of the package
+
+	    \param Cache to be used to query for information
+	    \param Pkg we want the candidate version from this package */
+	static pkgCache::VerIterator getCandidateVer(pkgCacheFile &Cache,
+		pkgCache::PkgIterator const &Pkg, CacheSetHelper &helper);
+
+	/** \brief returns the installed version of the package
+
+	    \param Cache to be used to query for information
+	    \param Pkg we want the installed version from this package */
+	static pkgCache::VerIterator getInstalledVer(pkgCacheFile &Cache,
+		pkgCache::PkgIterator const &Pkg, CacheSetHelper &helper);
+									/*}}}*/
+};
+									/*}}}*/
+template<class Container> class VersionContainer : public VersionContainerInterface {/*{{{*/
+/** \class APT::VersionContainer
+
+    Simple wrapper around a container class like std::set to provide a similar
+    interface to a set of versions as to the complete set of all versions in the
+    pkgCache. */
+	Container _cont;
+public:									/*{{{*/
+	/** \brief smell like a pkgCache::VerIterator */
+	class const_iterator : public VersionContainerInterface::const_iterator,
+			       public std::iterator<std::forward_iterator_tag, typename Container::const_iterator> {/*{{{*/
+		typename Container::const_iterator _iter;
+	public:
+		const_iterator(typename Container::const_iterator i) : _iter(i) {}
+		pkgCache::VerIterator getVer(void) const { return *_iter; }
+		inline pkgCache::VerIterator operator*(void) const { return *_iter; };
+		operator typename Container::const_iterator(void) const { return _iter; }
+		inline const_iterator& operator++() { ++_iter; return *this; }
+		inline const_iterator operator++(int) { const_iterator tmp(*this); operator++(); return tmp; }
+		inline bool operator!=(const_iterator const &i) const { return _iter != i._iter; };
+		inline bool operator==(const_iterator const &i) const { return _iter == i._iter; };
+		friend std::ostream& operator<<(std::ostream& out, const_iterator i) { return operator<<(out, *i); }
+	};
+	class iterator : public VersionContainerInterface::const_iterator,
+			 public std::iterator<std::forward_iterator_tag, typename Container::iterator> {
+		typename Container::iterator _iter;
+	public:
+		iterator(typename Container::iterator i) : _iter(i) {}
+		pkgCache::VerIterator getVer(void) const { return *_iter; }
+		inline pkgCache::VerIterator operator*(void) const { return *_iter; };
+		operator typename Container::iterator(void) const { return _iter; }
+		operator typename VersionContainer<Container>::const_iterator() { return VersionContainer<Container>::const_iterator(_iter); }
+		inline iterator& operator++() { ++_iter; return *this; }
+		inline iterator operator++(int) { iterator tmp(*this); operator++(); return tmp; }
+		inline bool operator!=(iterator const &i) const { return _iter != i._iter; };
+		inline bool operator==(iterator const &i) const { return _iter == i._iter; };
+		friend std::ostream& operator<<(std::ostream& out, iterator i) { return operator<<(out, *i); }
+	};
+									/*}}}*/
+
+	bool insert(pkgCache::VerIterator const &V) { if (V.end() == true) return false; _cont.insert(V); return true; };
+	template<class Cont> void insert(VersionContainer<Cont> const &vercont) { _cont.insert((typename Cont::const_iterator)vercont.begin(), (typename Cont::const_iterator)vercont.end()); };
+	void insert(const_iterator begin, const_iterator end) { _cont.insert(begin, end); };
+	bool empty() const { return _cont.empty(); };
+	void clear() { return _cont.clear(); };
+	void erase(iterator position) { _cont.erase((typename Container::iterator)position); };
+	size_t erase(const pkgCache::VerIterator x) { return _cont.erase(x); };
+	void erase(iterator first, iterator last) { _cont.erase(first, last); };
+	size_t size() const { return _cont.size(); };
+
+	const_iterator begin() const { return const_iterator(_cont.begin()); };
+	const_iterator end() const { return const_iterator(_cont.end()); };
+	iterator begin() { return iterator(_cont.begin()); };
+	iterator end() { return iterator(_cont.end()); };
+	const_iterator find(pkgCache::VerIterator const &V) const { return const_iterator(_cont.find(V)); };
+
 	/** \brief returns all versions specified on the commandline
 
 	    Get all versions from the commandline, uses given default version if
@@ -305,26 +530,34 @@ public:									/*{{{*/
 	    \param Cache the packages and versions are in
 	    \param cmdline Command line the versions should be extracted from
 	    \param helper responsible for error and message handling */
-	static APT::VersionSet FromCommandLine(pkgCacheFile &Cache, const char **cmdline,
-			APT::VersionSet::Version const &fallback, CacheSetHelper &helper);
-	static APT::VersionSet FromCommandLine(pkgCacheFile &Cache, const char **cmdline,
-			APT::VersionSet::Version const &fallback) {
+	static VersionContainer FromCommandLine(pkgCacheFile &Cache, const char **cmdline,
+			Version const &fallback, CacheSetHelper &helper) {
+		VersionContainer vercon;
+		VersionContainerInterface::FromCommandLine(&vercon, Cache, cmdline, fallback, helper);
+		return vercon;
+	}
+	static VersionContainer FromCommandLine(pkgCacheFile &Cache, const char **cmdline,
+			Version const &fallback) {
 		CacheSetHelper helper;
 		return FromCommandLine(Cache, cmdline, fallback, helper);
 	}
-	static APT::VersionSet FromCommandLine(pkgCacheFile &Cache, const char **cmdline) {
+	static VersionContainer FromCommandLine(pkgCacheFile &Cache, const char **cmdline) {
 		return FromCommandLine(Cache, cmdline, CANDINST);
 	}
 
-	static APT::VersionSet FromString(pkgCacheFile &Cache, std::string pkg,
-			APT::VersionSet::Version const &fallback, CacheSetHelper &helper,
-			bool const &onlyFromName = false);
-	static APT::VersionSet FromString(pkgCacheFile &Cache, std::string pkg,
-			APT::VersionSet::Version const &fallback) {
+	static VersionContainer FromString(pkgCacheFile &Cache, std::string const &pkg,
+			Version const &fallback, CacheSetHelper &helper,
+			bool const onlyFromName = false) {
+		VersionContainer vercon;
+		VersionContainerInterface::FromString(&vercon, Cache, pkg, fallback, helper);
+		return vercon;
+	}
+	static VersionContainer FromString(pkgCacheFile &Cache, std::string pkg,
+			Version const &fallback) {
 		CacheSetHelper helper;
 		return FromString(Cache, pkg, fallback, helper);
 	}
-	static APT::VersionSet FromString(pkgCacheFile &Cache, std::string pkg) {
+	static VersionContainer FromString(pkgCacheFile &Cache, std::string pkg) {
 		return FromString(Cache, pkg, CANDINST);
 	}
 
@@ -334,57 +567,80 @@ public:									/*{{{*/
 	    \param P the package in question
 	    \param fallback the version(s) you want to get
 	    \param helper the helper used for display and error handling */
-	static APT::VersionSet FromPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &P,
-		VersionSet::Version const &fallback, CacheSetHelper &helper);
-	static APT::VersionSet FromPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &P,
-			APT::VersionSet::Version const &fallback) {
+	static VersionContainer FromPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &P,
+		Version const &fallback, CacheSetHelper &helper) {
+		VersionContainer vercon;
+		VersionContainerInterface::FromPackage(&vercon, Cache, P, fallback, helper);
+		return vercon;
+	}
+	static VersionContainer FromPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &P,
+					    Version const &fallback) {
 		CacheSetHelper helper;
 		return FromPackage(Cache, P, fallback, helper);
 	}
-	static APT::VersionSet FromPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &P) {
-		return FromPackage(Cache, P, CANDINST);
+	static VersionContainer FromPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &P) {
+		return FromPackage(Cache, P, CANDIDATE);
 	}
 
-	struct Modifier {
-		enum Position { NONE, PREFIX, POSTFIX };
-		unsigned short ID;
-		const char * const Alias;
-		Position Pos;
-		VersionSet::Version SelectVersion;
-		Modifier (unsigned short const &id, const char * const alias, Position const &pos,
-			  VersionSet::Version const &select) : ID(id), Alias(alias), Pos(pos),
-			 SelectVersion(select) {};
-	};
+	static std::map<unsigned short, VersionContainer> GroupedFromCommandLine(
+										 pkgCacheFile &Cache,
+										 const char **cmdline,
+										 std::list<Modifier> const &mods,
+										 unsigned short const fallback,
+										 CacheSetHelper &helper) {
+		std::map<unsigned short, VersionContainer> versets;
+		for (const char **I = cmdline; *I != 0; ++I) {
+			unsigned short modID = fallback;
+			VersionContainer verset;
+			VersionContainerInterface::FromModifierCommandLine(modID, &verset, Cache, *I, mods, helper);
+			versets[modID].insert(verset);
+		}
+		return versets;
 
-	static std::map<unsigned short, VersionSet> GroupedFromCommandLine(
-		pkgCacheFile &Cache, const char **cmdline,
-		std::list<VersionSet::Modifier> const &mods,
-		unsigned short const &fallback, CacheSetHelper &helper);
-	static std::map<unsigned short, VersionSet> GroupedFromCommandLine(
+	}
+	static std::map<unsigned short, VersionContainer> GroupedFromCommandLine(
 		pkgCacheFile &Cache, const char **cmdline,
-		std::list<VersionSet::Modifier> const &mods,
-		unsigned short const &fallback) {
+		std::list<Modifier> const &mods,
+		unsigned short const fallback) {
 		CacheSetHelper helper;
 		return GroupedFromCommandLine(Cache, cmdline,
 				mods, fallback, helper);
 	}
-									/*}}}*/
-protected:								/*{{{*/
 
-	/** \brief returns the candidate version of the package
-
-	    \param Cache to be used to query for information
-	    \param Pkg we want the candidate version from this package */
-	static pkgCache::VerIterator getCandidateVer(pkgCacheFile &Cache,
-		pkgCache::PkgIterator const &Pkg, CacheSetHelper &helper);
-
-	/** \brief returns the installed version of the package
-
-	    \param Cache to be used to query for information
-	    \param Pkg we want the installed version from this package */
-	static pkgCache::VerIterator getInstalledVer(pkgCacheFile &Cache,
-		pkgCache::PkgIterator const &Pkg, CacheSetHelper &helper);
+	static VersionContainer FromDependency(pkgCacheFile &Cache, pkgCache::DepIterator const &D,
+					       Version const &selector, CacheSetHelper &helper) {
+		VersionContainer vercon;
+		VersionContainerInterface::FromDependency(&vercon, Cache, D, selector, helper);
+		return vercon;
+	}
+	static VersionContainer FromDependency(pkgCacheFile &Cache, pkgCache::DepIterator const &D,
+					       Version const &selector) {
+		CacheSetHelper helper;
+		return FromPackage(Cache, D, selector, helper);
+	}
+	static VersionContainer FromDependency(pkgCacheFile &Cache, pkgCache::DepIterator const &D) {
+		return FromPackage(Cache, D, CANDIDATE);
+	}
 									/*}}}*/
 };									/*}}}*/
+
+template<> template<class Cont> void VersionContainer<std::list<pkgCache::VerIterator> >::insert(VersionContainer<Cont> const &vercont) {
+	for (typename VersionContainer<Cont>::const_iterator v = vercont.begin(); v != vercont.end(); ++v)
+		_cont.push_back(*v);
+};
+// these two are 'inline' as otherwise the linker has problems with seeing these untemplated
+// specializations again and again - but we need to see them, so that library users can use them
+template<> inline bool VersionContainer<std::list<pkgCache::VerIterator> >::insert(pkgCache::VerIterator const &V) {
+	if (V.end() == true)
+		return false;
+	_cont.push_back(V);
+	return true;
+};
+template<> inline void VersionContainer<std::list<pkgCache::VerIterator> >::insert(const_iterator begin, const_iterator end) {
+	for (const_iterator v = begin; v != end; ++v)
+		_cont.push_back(*v);
+};
+typedef VersionContainer<std::set<pkgCache::VerIterator> > VersionSet;
+typedef VersionContainer<std::list<pkgCache::VerIterator> > VersionList;
 }
 #endif
diff --git a/apt-pkg/cdrom.cc b/apt-pkg/cdrom.cc
index d1bc1f3ba..07983e44f 100644
--- a/apt-pkg/cdrom.cc
+++ b/apt-pkg/cdrom.cc
@@ -78,27 +78,43 @@ bool pkgCdrom::FindPackages(string CD,
    {
       SigList.push_back(CD);
    }
+
    /* Aha! We found some package files. We assume that everything under 
       this dir is controlled by those package files so we don't look down
       anymore */
-   if (stat("Packages",&Buf) == 0 || stat("Packages.gz",&Buf) == 0 ||
-       stat("Packages.bz2",&Buf) == 0 || stat("Packages.xz",&Buf) == 0)
-   {
-      List.push_back(CD);
+    std::vector<std::string> types = APT::Configuration::getCompressionTypes();
+    types.push_back("");
+    for (std::vector<std::string>::const_iterator t = types.begin();
+         t != types.end(); ++t)
+    {
+       std::string filename = std::string("Packages");
+       if ((*t).size() > 0)
+          filename.append("."+*t);
+       if (stat(filename.c_str(), &Buf) == 0)
+       {
+          List.push_back(CD);
       
-      // Continue down if thorough is given
-      if (_config->FindB("APT::CDROM::Thorough",false) == false)
-	 return true;
-   }
-   if (stat("Sources.xz",&Buf) == 0 || stat("Sources.bz2",&Buf) == 0 ||
-       stat("Sources.gz",&Buf) == 0 || stat("Sources",&Buf) == 0)
-   {
-      SList.push_back(CD);
+          // Continue down if thorough is given
+          if (_config->FindB("APT::CDROM::Thorough",false) == false)
+             return true;
+          break;
+       }
+    }
+    for (std::vector<std::string>::const_iterator t = types.begin();
+         t != types.end(); ++t)
+    {
+       std::string filename = std::string("Sources");
+       if ((*t).size() > 0)
+          filename.append("."+*t);
+       {
+          SList.push_back(CD);
       
-      // Continue down if thorough is given
-      if (_config->FindB("APT::CDROM::Thorough",false) == false)
-	 return true;
-   }
+          // Continue down if thorough is given
+          if (_config->FindB("APT::CDROM::Thorough",false) == false)
+             return true;
+          break;
+       }
+    }
 
    // see if we find translatin indexes
    if (stat("i18n",&Buf) == 0)
@@ -111,12 +127,15 @@ bool pkgCdrom::FindPackages(string CD,
 	    if (_config->FindB("Debug::aptcdrom",false) == true)
 	       std::clog << "found translations: " << Dir->d_name << "\n";
 	    string file = Dir->d_name;
-	    if(file.substr(file.size()-3,file.size()) == ".gz" ||
-	       file.substr(file.size()-3,file.size()) == ".xz")
-	       file = file.substr(0,file.size()-3);
-	    if(file.substr(file.size()-4,file.size()) == ".bz2")
-	       file = file.substr(0,file.size()-4);
-	    TransList.push_back(CD+"i18n/"+ file);
+            for (std::vector<std::string>::const_iterator t = types.begin();
+                 t != types.end(); ++t)
+            {
+               std::string needle = "." + *t;
+               if(file.substr(file.size()-needle.size()) == needle)
+                  file = file.substr(0, file.size()-needle.size());
+               TransList.push_back(CD+"i18n/"+ file);
+               break;
+            }
 	 }
       }
       closedir(D);
@@ -262,13 +281,19 @@ bool pkgCdrom::DropRepeats(vector<string> &List,const char *Name)
    for (unsigned int I = 0; I != List.size(); I++)
    {
       struct stat Buf;
-      if (stat((List[I] + Name).c_str(),&Buf) != 0 &&
-	  stat((List[I] + Name + ".gz").c_str(),&Buf) != 0 && 
-	  stat((List[I] + Name + ".bz2").c_str(),&Buf) != 0 && 
-	  stat((List[I] + Name + ".xz").c_str(),&Buf) != 0)
-	 _error->Errno("stat","Failed to stat %s%s",List[I].c_str(),
-		       Name);
-      Inodes[I] = Buf.st_ino;
+      std::vector<std::string> types = APT::Configuration::getCompressionTypes();
+      types.push_back("");
+      for (std::vector<std::string>::const_iterator t = types.begin();
+           t != types.end(); ++t)
+      {
+         std::string filename = List[I] + Name;
+         if ((*t).size() > 0)
+            filename.append("." + *t);
+         if (stat(filename.c_str(), &Buf) != 0)
+            _error->Errno("stat","Failed to stat %s%s",List[I].c_str(),
+                          Name);
+         Inodes[I] = Buf.st_ino;
+      }
    }
    
    if (_error->PendingError() == true) {
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 456e4b012..0dbedf323 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -23,7 +23,9 @@
 #include <apt-pkg/pkgsystem.h>
 #include <apt-pkg/tagfile.h>
 #include <apt-pkg/progress.h>
+#include <apt-pkg/cacheset.h>
 
+#include <algorithm>
 #include <iostream>
 #include <sstream>
 #include <set>
@@ -941,6 +943,51 @@ bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
 // DepCache::MarkInstall - Put the package in the install state		/*{{{*/
 // ---------------------------------------------------------------------
 /* */
+struct CompareProviders {
+   pkgCache::PkgIterator const Pkg;
+   CompareProviders(pkgCache::DepIterator const &Dep) : Pkg(Dep.TargetPkg()) {};
+   //bool operator() (APT::VersionList::iterator const &AV, APT::VersionList::iterator const &BV)
+   bool operator() (pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
+   {
+      pkgCache::PkgIterator const A = AV.ParentPkg();
+      pkgCache::PkgIterator const B = BV.ParentPkg();
+      // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
+      if (A->Group != B->Group)
+      {
+	 if (A->Group == Pkg->Group && B->Group != Pkg->Group)
+	    return false;
+	 else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
+	    return true;
+      }
+      // we like essentials
+      if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
+      {
+	 if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+	    return false;
+	 else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+	    return true;
+      }
+      // higher priority seems like a good idea
+      if (AV->Priority != BV->Priority)
+	 return AV->Priority < BV->Priority;
+      // prefer native architecture
+      if (strcmp(A.Arch(), B.Arch()) != 0)
+      {
+	 if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
+	    return false;
+	 else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
+	    return true;
+	 std::vector<std::string> archs = APT::Configuration::getArchitectures();
+	 for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
+	    if (*a == A.Arch())
+	       return false;
+	    else if (*a == B.Arch())
+	       return true;
+      }
+      // unable to decide…
+      return A->ID < B->ID;
+   }
+};
 bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 			      unsigned long Depth, bool FromUser,
 			      bool ForceImportantDeps)
@@ -1103,41 +1150,28 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 
       /* This bit is for processing the possibilty of an install/upgrade
          fixing the problem */
-      SPtrArray<Version *> List = Start.AllTargets();
       if (Start->Type != Dep::DpkgBreaks &&
 	  (DepState[Start->ID] & DepCVer) == DepCVer)
       {
-	 // Right, find the best version to install..
-	 Version **Cur = List;
-	 PkgIterator P = Start.TargetPkg();
-	 PkgIterator InstPkg(*Cache,0);
-	 
-	 // See if there are direct matches (at the start of the list)
-	 for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
+	 APT::VersionList verlist;
+	 pkgCache::VerIterator Cand = PkgState[Start.TargetPkg()->ID].CandidateVerIter(*this);
+	 if (Cand.end() == false && VS().CheckDep(Cand.VerStr(), Start->CompareOp, Start.TargetVer()) == true)
+	    verlist.insert(Cand);
+	 for (PrvIterator Prv = Start.TargetPkg().ProvidesList(); Prv.end() != true; ++Prv)
 	 {
-	    PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
-	    if (PkgState[Pkg->ID].CandidateVer != *Cur)
+	    pkgCache::VerIterator V = Prv.OwnerVer();
+	    pkgCache::VerIterator Cand = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
+	    if (Cand.end() == true || V != Cand ||
+		VS().CheckDep(Cand.VerStr(), Start->CompareOp, Start.TargetVer()) == false)
 	       continue;
-	    InstPkg = Pkg;
-	    break;
+	    verlist.insert(Cand);
 	 }
+	 CompareProviders comp(Start);
+	 APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
 
-	 // Select the highest priority providing package
-	 if (InstPkg.end() == true)
-	 {
-	    pkgPrioSortList(*Cache,Cur);
-	    for (; *Cur != 0; Cur++)
-	    {
-	       PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
-	       if (PkgState[Pkg->ID].CandidateVer != *Cur)
-		  continue;
-	       InstPkg = Pkg;
-	       break;
-	    }
-	 }
-	 
-	 if (InstPkg.end() == false)
+	 if (InstVer != verlist.end())
 	 {
+	    pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
 	    if(DebugAutoInstall == true)
 	       std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
 			 << " as " << Start.DepType() << " of " << Pkg.Name()
@@ -1155,7 +1189,7 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
  	       // mark automatic dependency
  	       MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
  	       // Set the autoflag, after MarkInstall because MarkInstall unsets it
- 	       if (P->CurrentVer == 0)
+ 	       if (InstPkg->CurrentVer == 0)
  		  PkgState[InstPkg->ID].Flags |= Flag::Auto;
  	    }
 	 }
@@ -1167,6 +1201,7 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
          upgrade the package. */
       if (Start.IsNegative() == true)
       {
+	 SPtrArray<Version *> List = Start.AllTargets();
 	 for (Version **I = List; *I != 0; I++)
 	 {
 	    VerIterator Ver(*this,*I);
diff --git a/apt-pkg/edsp.h b/apt-pkg/edsp.h
index c14309422..07bbbdd03 100644
--- a/apt-pkg/edsp.h
+++ b/apt-pkg/edsp.h
@@ -10,13 +10,11 @@
 #define PKGLIB_EDSP_H
 
 #include <apt-pkg/pkgcache.h>
+#include <apt-pkg/cacheset.h>
 
 #include <list>
 #include <string>
 
-namespace APT {
-	class PackageSet;
-};
 class pkgDepCache;
 class OpProgress;
 
diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h
index 7e32a3a96..fd1a02149 100644
--- a/apt-pkg/pkgcache.h
+++ b/apt-pkg/pkgcache.h
@@ -198,6 +198,7 @@ class pkgCache								/*{{{*/
    inline PkgFileIterator FileEnd();
 
    inline bool MultiArchCache() const { return MultiArchEnabled; };
+   inline char const * const NativeArch() const;
 
    // Make me a function
    pkgVersioningSystem *VS;
@@ -213,7 +214,6 @@ class pkgCache								/*{{{*/
 private:
    bool MultiArchEnabled;
    PkgIterator SingleArchFindPkg(const std::string &Name);
-   inline char const * const NativeArch() const;
 };
 									/*}}}*/
 // Header structure							/*{{{*/
diff --git a/cmdline/apt-cache.cc b/cmdline/apt-cache.cc
index 82a31c9b1..65d7b0ccd 100644
--- a/cmdline/apt-cache.cc
+++ b/cmdline/apt-cache.cc
@@ -65,12 +65,12 @@ public:
       return CacheSetHelper::canNotFindNewestVer(Cache, Pkg);
    }
 
-   virtual APT::VersionSet canNotFindAllVer(pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg) {
+   virtual void canNotFindAllVer(APT::VersionContainerInterface * vci, pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg) {
       virtualPkgs.insert(Pkg);
-      return CacheSetHelper::canNotFindAllVer(Cache, Pkg);
+      CacheSetHelper::canNotFindAllVer(vci, Cache, Pkg);
    }
 
-   CacheSetHelperVirtuals(bool const &ShowErrors = true, GlobalError::MsgType const &ErrorType = GlobalError::NOTICE) : CacheSetHelper(ShowErrors, ErrorType) {}
+   CacheSetHelperVirtuals(bool const ShowErrors = true, GlobalError::MsgType const &ErrorType = GlobalError::NOTICE) : CacheSetHelper(ShowErrors, ErrorType) {}
 };
 									/*}}}*/
 // LocalitySort - Sort a version list by package file locality		/*{{{*/
@@ -108,7 +108,7 @@ void LocalitySort(pkgCache::DescFile **begin,
 // UnMet - Show unmet dependencies					/*{{{*/
 // ---------------------------------------------------------------------
 /* */
-bool ShowUnMet(pkgCache::VerIterator const &V, bool const &Important)
+bool ShowUnMet(pkgCache::VerIterator const &V, bool const Important)
 {
 	 bool Header = false;
 	 for (pkgCache::DepIterator D = V.DependsList(); D.end() == false;)
@@ -199,9 +199,9 @@ bool UnMet(CommandLine &CmdL)
    else
    {
       CacheSetHelperVirtuals helper(true, GlobalError::NOTICE);
-      APT::VersionSet verset = APT::VersionSet::FromCommandLine(CacheFile, CmdL.FileList + 1,
-				APT::VersionSet::CANDIDATE, helper);
-      for (APT::VersionSet::iterator V = verset.begin(); V != verset.end(); ++V)
+      APT::VersionList verset = APT::VersionList::FromCommandLine(CacheFile, CmdL.FileList + 1,
+				APT::VersionList::CANDIDATE, helper);
+      for (APT::VersionList::iterator V = verset.begin(); V != verset.end(); ++V)
 	 if (ShowUnMet(V, Important) == false)
 	    return false;
    }
@@ -215,9 +215,9 @@ bool DumpPackage(CommandLine &CmdL)
 {
    pkgCacheFile CacheFile;
    APT::CacheSetHelper helper(true, GlobalError::NOTICE);
-   APT::PackageSet pkgset = APT::PackageSet::FromCommandLine(CacheFile, CmdL.FileList + 1, helper);
+   APT::PackageList pkgset = APT::PackageList::FromCommandLine(CacheFile, CmdL.FileList + 1, helper);
 
-   for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+   for (APT::PackageList::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
    {
       cout << "Package: " << Pkg.FullName(true) << endl;
       cout << "Versions: " << endl;
@@ -588,7 +588,7 @@ bool ShowDepends(CommandLine &CmdL, bool const RevDepends)
       return false;
 
    CacheSetHelperVirtuals helper(false);
-   APT::VersionSet verset = APT::VersionSet::FromCommandLine(CacheFile, CmdL.FileList + 1, APT::VersionSet::CANDIDATE, helper);
+   APT::VersionList verset = APT::VersionList::FromCommandLine(CacheFile, CmdL.FileList + 1, APT::VersionList::CANDIDATE, helper);
    if (verset.empty() == true && helper.virtualPkgs.empty() == true)
       return _error->Error(_("No packages found"));
    std::vector<bool> Shown(Cache->Head().PackageCount);
@@ -1365,10 +1365,10 @@ bool ShowPackage(CommandLine &CmdL)
 {
    pkgCacheFile CacheFile;
    CacheSetHelperVirtuals helper(true, GlobalError::NOTICE);
-   APT::VersionSet::Version const select = _config->FindB("APT::Cache::AllVersions", true) ?
-			APT::VersionSet::ALL : APT::VersionSet::CANDIDATE;
-   APT::VersionSet const verset = APT::VersionSet::FromCommandLine(CacheFile, CmdL.FileList + 1, select, helper);
-   for (APT::VersionSet::const_iterator Ver = verset.begin(); Ver != verset.end(); ++Ver)
+   APT::VersionList::Version const select = _config->FindB("APT::Cache::AllVersions", true) ?
+			APT::VersionList::ALL : APT::VersionList::CANDIDATE;
+   APT::VersionList const verset = APT::VersionList::FromCommandLine(CacheFile, CmdL.FileList + 1, select, helper);
+   for (APT::VersionList::const_iterator Ver = verset.begin(); Ver != verset.end(); ++Ver)
       if (DisplayRecord(CacheFile, Ver) == false)
 	 return false;
 
@@ -1531,8 +1531,8 @@ bool Policy(CommandLine &CmdL)
 
    // Print out detailed information for each package
    APT::CacheSetHelper helper(true, GlobalError::NOTICE);
-   APT::PackageSet pkgset = APT::PackageSet::FromCommandLine(CacheFile, CmdL.FileList + 1, helper);
-   for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+   APT::PackageList pkgset = APT::PackageList::FromCommandLine(CacheFile, CmdL.FileList + 1, helper);
+   for (APT::PackageList::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
    {
       cout << Pkg.FullName(true) << ":" << endl;
 
@@ -1608,8 +1608,8 @@ bool Madison(CommandLine &CmdL)
    for (const char **I = CmdL.FileList + 1; *I != 0; I++)
    {
       _error->PushToStack();
-      APT::PackageSet pkgset = APT::PackageSet::FromString(CacheFile, *I, helper);
-      for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+      APT::PackageList pkgset = APT::PackageList::FromString(CacheFile, *I, helper);
+      for (APT::PackageList::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
       {
          for (pkgCache::VerIterator V = Pkg.VersionList(); V.end() == false; ++V)
          {
diff --git a/cmdline/apt-get.cc b/cmdline/apt-get.cc
index d2e44aae0..c140d5f5c 100644
--- a/cmdline/apt-get.cc
+++ b/cmdline/apt-get.cc
@@ -628,20 +628,18 @@ public:
 		explicitlyNamed = true;
 	}
 
-	virtual void showTaskSelection(APT::PackageSet const &pkgset, string const &pattern) {
-		for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
-			ioprintf(out, _("Note, selecting '%s' for task '%s'\n"),
-				 Pkg.FullName(true).c_str(), pattern.c_str());
+	virtual void showTaskSelection(pkgCache::PkgIterator const &Pkg, string const &pattern) {
+		ioprintf(out, _("Note, selecting '%s' for task '%s'\n"),
+				Pkg.FullName(true).c_str(), pattern.c_str());
 		explicitlyNamed = false;
 	}
-	virtual void showRegExSelection(APT::PackageSet const &pkgset, string const &pattern) {
-		for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
-			ioprintf(out, _("Note, selecting '%s' for regex '%s'\n"),
-				 Pkg.FullName(true).c_str(), pattern.c_str());
+	virtual void showRegExSelection(pkgCache::PkgIterator const &Pkg, string const &pattern) {
+		ioprintf(out, _("Note, selecting '%s' for regex '%s'\n"),
+				Pkg.FullName(true).c_str(), pattern.c_str());
 		explicitlyNamed = false;
 	}
 	virtual void showSelectedVersion(pkgCache::PkgIterator const &Pkg, pkgCache::VerIterator const Ver,
-				 string const &ver, bool const &verIsRel) {
+				 string const &ver, bool const verIsRel) {
 		if (ver == Ver.VerStr())
 			return;
 		selectedByRelease.push_back(make_pair(Ver, ver));
@@ -707,7 +705,7 @@ public:
 		APT::VersionSet const verset = tryVirtualPackage(Cache, Pkg, APT::VersionSet::CANDIDATE);
 		if (verset.empty() == false)
 			return *(verset.begin());
-		if (ShowError == true) {
+		else if (ShowError == true) {
 			_error->Error(_("Package '%s' has no installation candidate"),Pkg.FullName(true).c_str());
 			virtualPkgs.insert(Pkg);
 		}
@@ -744,6 +742,19 @@ public:
 				Prov = PPkg;
 				found_one = true;
 			} else if (PPkg != Prov) {
+				// same group, so it's a foreign package
+				if (PPkg->Group == Prov->Group) {
+					// do we already have the requested arch?
+					if (strcmp(Pkg.Arch(), Prov.Arch()) == 0 ||
+					    strcmp(Prov.Arch(), "all") == 0 ||
+					    unlikely(strcmp(PPkg.Arch(), Prov.Arch()) == 0)) // packages have only on candidate, but just to be sure
+						continue;
+					// see which architecture we prefer more and switch to it
+					std::vector<std::string> archs = APT::Configuration::getArchitectures();
+					if (std::find(archs.begin(), archs.end(), PPkg.Arch()) < std::find(archs.begin(), archs.end(), Prov.Arch()))
+						Prov = PPkg;
+					continue;
+				}
 				found_one = false; // we found at least two
 				break;
 			}
@@ -769,7 +780,7 @@ struct TryToInstall {
    unsigned long AutoMarkChanged;
    APT::PackageSet doAutoInstallLater;
 
-   TryToInstall(pkgCacheFile &Cache, pkgProblemResolver *PM, bool const &FixBroken) : Cache(&Cache), Fix(PM),
+   TryToInstall(pkgCacheFile &Cache, pkgProblemResolver *PM, bool const FixBroken) : Cache(&Cache), Fix(PM),
 			FixBroken(FixBroken), AutoMarkChanged(0) {};
 
    void operator() (pkgCache::VerIterator const &Ver) {
@@ -2295,8 +2306,8 @@ bool DoDownload(CommandLine &CmdL)
       return false;
    
    APT::CacheSetHelper helper(c0out);
-   APT::VersionSet verset = APT::VersionSet::FromCommandLine(Cache,
-		CmdL.FileList + 1, APT::VersionSet::CANDIDATE, helper);
+   APT::VersionList verset = APT::VersionList::FromCommandLine(Cache,
+		CmdL.FileList + 1, APT::VersionList::CANDIDATE, helper);
 
    if (verset.empty() == true)
       return false;
@@ -2308,7 +2319,7 @@ bool DoDownload(CommandLine &CmdL)
 
    pkgRecords Recs(Cache);
    pkgSourceList *SrcList = Cache.GetSourceList();
-   for (APT::VersionSet::const_iterator Ver = verset.begin(); 
+   for (APT::VersionList::const_iterator Ver = verset.begin(); 
         Ver != verset.end(); 
         ++Ver) 
    {
@@ -3170,14 +3181,14 @@ bool DoChangelog(CommandLine &CmdL)
       return false;
    
    APT::CacheSetHelper helper(c0out);
-   APT::VersionSet verset = APT::VersionSet::FromCommandLine(Cache,
-		CmdL.FileList + 1, APT::VersionSet::CANDIDATE, helper);
+   APT::VersionList verset = APT::VersionList::FromCommandLine(Cache,
+		CmdL.FileList + 1, APT::VersionList::CANDIDATE, helper);
    if (verset.empty() == true)
       return false;
    pkgAcquire Fetcher;
 
    if (_config->FindB("APT::Get::Print-URIs", false) == true)
-      for (APT::VersionSet::const_iterator Ver = verset.begin();
+      for (APT::VersionList::const_iterator Ver = verset.begin();
 	   Ver != verset.end(); ++Ver)
 	 return DownloadChangelog(Cache, Fetcher, Ver, "");
 
@@ -3200,7 +3211,7 @@ bool DoChangelog(CommandLine &CmdL)
 	 return _error->Errno("mkdtemp", "mkdtemp failed");
    }
 
-   for (APT::VersionSet::const_iterator Ver = verset.begin(); 
+   for (APT::VersionList::const_iterator Ver = verset.begin(); 
         Ver != verset.end(); 
         ++Ver) 
    {
diff --git a/cmdline/apt-mark.cc b/cmdline/apt-mark.cc
index 339cbdf44..dbbef5013 100644
--- a/cmdline/apt-mark.cc
+++ b/cmdline/apt-mark.cc
@@ -34,14 +34,14 @@ bool DoAuto(CommandLine &CmdL)
    if (unlikely(Cache == NULL || DepCache == NULL))
       return false;
 
-   APT::PackageSet pkgset = APT::PackageSet::FromCommandLine(CacheFile, CmdL.FileList + 1);
+   APT::PackageList pkgset = APT::PackageList::FromCommandLine(CacheFile, CmdL.FileList + 1);
    if (pkgset.empty() == true)
       return _error->Error(_("No packages found"));
 
    bool MarkAuto = strcasecmp(CmdL.FileList[0],"auto") == 0;
    int AutoMarkChanged = 0;
 
-   for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+   for (APT::PackageList::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
    {
       if (Pkg->CurrentVer == 0)
       {
@@ -81,7 +81,7 @@ bool DoMarkAuto(CommandLine &CmdL)
    if (unlikely(Cache == NULL || DepCache == NULL))
       return false;
 
-   APT::PackageSet pkgset = APT::PackageSet::FromCommandLine(CacheFile, CmdL.FileList + 1);
+   APT::PackageList pkgset = APT::PackageList::FromCommandLine(CacheFile, CmdL.FileList + 1);
    if (pkgset.empty() == true)
       return _error->Error(_("No packages found"));
 
@@ -89,7 +89,7 @@ bool DoMarkAuto(CommandLine &CmdL)
    bool const Verbose = _config->FindB("APT::MarkAuto::Verbose", false);
    int AutoMarkChanged = 0;
 
-   for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+   for (APT::PackageList::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
    {
       if (Pkg->CurrentVer == 0 ||
 	  (((*DepCache)[Pkg].Flags & pkgCache::Flag::Auto) == pkgCache::Flag::Auto) == MarkAuto)
@@ -157,13 +157,13 @@ bool DoHold(CommandLine &CmdL)
    if (unlikely(Cache == NULL))
       return false;
 
-   APT::PackageSet pkgset = APT::PackageSet::FromCommandLine(CacheFile, CmdL.FileList + 1);
+   APT::PackageList pkgset = APT::PackageList::FromCommandLine(CacheFile, CmdL.FileList + 1);
    if (pkgset.empty() == true)
       return _error->Error(_("No packages found"));
 
    bool const MarkHold = strcasecmp(CmdL.FileList[0],"hold") == 0;
 
-   for (APT::PackageSet::iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+   for (APT::PackageList::iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
    {
       if ((Pkg->SelectedState == pkgCache::State::Hold) == MarkHold)
       {
@@ -181,7 +181,7 @@ bool DoHold(CommandLine &CmdL)
 
    if (_config->FindB("APT::Mark::Simulate", false) == true)
    {
-      for (APT::PackageSet::iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+      for (APT::PackageList::iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
       {
 	 if (MarkHold == false)
 	    ioprintf(c1out,_("%s set on hold.\n"), Pkg.FullName(true).c_str());
@@ -201,7 +201,7 @@ bool DoHold(CommandLine &CmdL)
    if (dpkg == NULL)
       return _error->Errno("DoHold", "fdopen on dpkg stdin failed");
 
-   for (APT::PackageSet::iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
+   for (APT::PackageList::iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg)
    {
       if (MarkHold == true)
       {
diff --git a/debian/changelog b/debian/changelog
index ac1eb16e6..db146d75f 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -12,15 +12,31 @@ apt (0.8.16~exp9) UNRELEASED; urgency=low
   [ Julian Andres Klode ]
   * apt-pkg/cdrom.cc:
     - Accept .bz2, .xz files in addition to .gz files (Closes: #649451)
-
-  [ Colin Watson ]
-  * Convert libapt-pkg4.12 and libapt-inst1.4 to Multi-Arch: same.
   
   [ Michael Vogt ]
+  * apt-pkg/cdrom.cc:
+    - use aptconfiguration to get the supported compression types
   * debian/control:
     - bump debhelper build-dep to debhelper (>= 8.1.3~)
     - set libapt-pkg-dev to multi-arch: same too
+ 
+  [ Colin Watson ]
+  * Convert libapt-pkg4.12 and libapt-inst1.4 to Multi-Arch: same.
 
+  [ David Kalnischkies ]
+  * apt-pkg/cacheset.cc:
+    - make the cachesets real containers which can embedding any container
+      to be able to use the same interface regardless of set or list usage
+    - provide a {Package,Version}List similar to {Package,Version}Set
+  * cmdline/apt-{get,cache,mark}.cc:
+    - use Lists instead of Sets if input order should be preserved for
+      commands accepting lists of packages, e.g. policy (Closes: #625960)
+  * apt-pkg/depcache.cc:
+    - prefer native providers over foreigns even if the chain is foreign
+  * cmdline/apt-get.cc:
+    - ignore foreign architectures if we check if a provides has only one
+      resolver as it's basically the same for the user, so no need to choose
+  
  -- Julian Andres Klode <jak@debian.org>  Mon, 21 Nov 2011 18:46:36 +0100
 
 apt (0.8.16~exp8) experimental; urgency=low
diff --git a/test/integration/Packages-pdiff-usage-new b/test/integration/Packages-pdiff-usage-new
index 9157596a7..4f374b37f 100644
--- a/test/integration/Packages-pdiff-usage-new
+++ b/test/integration/Packages-pdiff-usage-new
@@ -1,16 +1,3 @@
-Package: newstuff
-Version: 1.0
-Architecture: i386
-Maintainer: Joe Sixpack <joe@example.org>
-Installed-Size: 101
-Filename: pool/newstuff_1.0_i386.deb
-Size: 101100
-MD5sum: 311aeeadf78324aaff1ceaf3e1f76671
-SHA1: 3c695e028f7a1ae324deeddaaa1242desa81088c
-SHA256: b46fd154615edefab321cc56a5cc0e7deaef23e2da3e4f129727fd660f28f050
-Description: some cool and shiny new stuff
- This package will appear in the next mirror update
-
 Package: apt
 Priority: important
 Section: admin
@@ -35,3 +22,16 @@ Description: Advanced front-end for dpkg
  .
  APT features complete installation ordering, multiple source capability
  and several other unique features, see the Users Guide in apt-doc.
+
+Package: newstuff
+Version: 1.0
+Architecture: i386
+Maintainer: Joe Sixpack <joe@example.org>
+Installed-Size: 101
+Filename: pool/newstuff_1.0_i386.deb
+Size: 101100
+MD5sum: 311aeeadf78324aaff1ceaf3e1f76671
+SHA1: 3c695e028f7a1ae324deeddaaa1242desa81088c
+SHA256: b46fd154615edefab321cc56a5cc0e7deaef23e2da3e4f129727fd660f28f050
+Description: some cool and shiny new stuff
+ This package will appear in the next mirror update
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
new file mode 100755
index 000000000..332466d96
--- /dev/null
+++ b/test/integration/test-multiarch-foreign
@@ -0,0 +1,150 @@
+#!/bin/sh
+set -e
+
+TESTDIR=$(readlink -f $(dirname $0))
+. $TESTDIR/framework
+setupenvironment
+configarchitecture 'amd64' 'i386' 'armel'
+
+insertpackage 'unstable' 'cool-foo' 'amd64,i386' '1.0' 'Depends: foo'
+insertpackage 'unstable' 'foo' 'amd64,i386,armel' '1.0' 'Multi-Arch: foreign'
+
+insertpackage 'unstable' 'cool-bar' 'amd64,i386' '1.0' 'Depends: bar-provider'
+insertpackage 'unstable' 'bar' 'amd64,i386,armel' '1.0' 'Provides: bar-provider
+Multi-Arch: foreign'
+
+setupaptarchive
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following extra packages will be installed:
+  foo
+The following NEW packages will be installed:
+  cool-foo:i386 foo
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst foo (1.0 unstable [amd64])
+Inst cool-foo:i386 (1.0 unstable [i386])
+Conf foo (1.0 unstable [amd64])
+Conf cool-foo:i386 (1.0 unstable [i386])' aptget install cool-foo:i386 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following extra packages will be installed:
+  foo
+The following NEW packages will be installed:
+  cool-foo foo
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst foo (1.0 unstable [amd64])
+Inst cool-foo (1.0 unstable [amd64])
+Conf foo (1.0 unstable [amd64])
+Conf cool-foo (1.0 unstable [amd64])' aptget install cool-foo:amd64 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  cool-foo foo
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst foo (1.0 unstable [amd64])
+Inst cool-foo (1.0 unstable [amd64])
+Conf foo (1.0 unstable [amd64])
+Conf cool-foo (1.0 unstable [amd64])' aptget install cool-foo:amd64 foo:amd64 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  cool-foo foo:i386
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst foo:i386 (1.0 unstable [i386])
+Inst cool-foo (1.0 unstable [amd64])
+Conf foo:i386 (1.0 unstable [i386])
+Conf cool-foo (1.0 unstable [amd64])' aptget install cool-foo:amd64 foo:i386 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  cool-foo foo:armel
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst foo:armel (1.0 unstable [armel])
+Inst cool-foo (1.0 unstable [amd64])
+Conf foo:armel (1.0 unstable [armel])
+Conf cool-foo (1.0 unstable [amd64])' aptget install cool-foo:amd64 foo:armel -s
+
+
+
+
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following extra packages will be installed:
+  bar
+The following NEW packages will be installed:
+  bar cool-bar:i386
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar (1.0 unstable [amd64])
+Inst cool-bar:i386 (1.0 unstable [i386])
+Conf bar (1.0 unstable [amd64])
+Conf cool-bar:i386 (1.0 unstable [i386])' aptget install cool-bar:i386 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following extra packages will be installed:
+  bar
+The following NEW packages will be installed:
+  bar cool-bar
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar (1.0 unstable [amd64])
+Inst cool-bar (1.0 unstable [amd64])
+Conf bar (1.0 unstable [amd64])
+Conf cool-bar (1.0 unstable [amd64])' aptget install cool-bar:amd64 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  bar cool-bar
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar (1.0 unstable [amd64])
+Inst cool-bar (1.0 unstable [amd64])
+Conf bar (1.0 unstable [amd64])
+Conf cool-bar (1.0 unstable [amd64])' aptget install cool-bar:amd64 bar:amd64 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  bar:i386 cool-bar
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar:i386 (1.0 unstable [i386])
+Inst cool-bar (1.0 unstable [amd64])
+Conf bar:i386 (1.0 unstable [i386])
+Conf cool-bar (1.0 unstable [amd64])' aptget install cool-bar:amd64 bar:i386 -s
+
+testequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  bar:armel cool-bar
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar:armel (1.0 unstable [armel])
+Inst cool-bar (1.0 unstable [amd64])
+Conf bar:armel (1.0 unstable [armel])
+Conf cool-bar (1.0 unstable [amd64])' aptget install cool-bar:amd64 bar:armel -s
+
+testequal "Reading package lists...
+Building dependency tree...
+Note, selecting 'bar' instead of 'bar-provider'
+The following NEW packages will be installed:
+  bar cool-bar
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar (1.0 unstable [amd64])
+Inst cool-bar (1.0 unstable [amd64])
+Conf bar (1.0 unstable [amd64])
+Conf cool-bar (1.0 unstable [amd64])" aptget install cool-bar bar-provider -s -q=0
+
+testequal "Reading package lists...
+Building dependency tree...
+Note, selecting 'bar:i386' instead of 'bar-provider:i386'
+The following NEW packages will be installed:
+  bar:i386 cool-bar
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar:i386 (1.0 unstable [i386])
+Inst cool-bar (1.0 unstable [amd64])
+Conf bar:i386 (1.0 unstable [i386])
+Conf cool-bar (1.0 unstable [amd64])" aptget install cool-bar bar-provider:i386 -s -q=0