implement a more generic ShowList method

apt-get is displaying various lists of package names, which until now it
was building as a string before passing it to ShowList, which inserted
linebreaks at fitting points and showed a title if needed, but it never
really understood what it was working with. With the help of C++11 the
new generic knows not only what it works with, but generates the list on
the fly rather than asking for it and potentially discarding parts of
the input (= the non-default verbose display). It also doubles as a test
for how usable the CacheSets are with C++11.

(Not all callers are adapted yet.)

Git-Dch: Ignore

6 files changed, 299 insertions, 236 deletions

diff --git a/apt-private/private-cachefile.cc b/apt-private/private-cachefile.cc
index 29e665245..2b2050684 100644
--- a/apt-private/private-cachefile.cc
+++ b/apt-private/private-cachefile.cc
@@ -7,7 +7,7 @@
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/pkgcache.h>
-#include <apt-pkg/cacheiterators.h>
+#include <apt-pkg/cacheset.h>
 
 #include <apt-private/private-output.h>
 #include <apt-private/private-cachefile.h>
@@ -21,39 +21,40 @@
 
 using namespace std;
 
-// CacheFile::NameComp - QSort compare by name				/*{{{*/
-// ---------------------------------------------------------------------
-/* */
-pkgCache *CacheFile::SortCache = 0;
-int CacheFile::NameComp(const void *a,const void *b)
+static bool SortPackagesByName(pkgCache * const Owner,
+      map_pointer_t const A, map_pointer_t const B)
 {
-   if (*(pkgCache::Package **)a == 0 || *(pkgCache::Package **)b == 0)
-      return *(pkgCache::Package **)a - *(pkgCache::Package **)b;
-   
-   const pkgCache::Package &A = **(pkgCache::Package **)a;
-   const pkgCache::Package &B = **(pkgCache::Package **)b;
-   const pkgCache::Group * const GA = SortCache->GrpP + A.Group;
-   const pkgCache::Group * const GB = SortCache->GrpP + B.Group;
-
-   return strcmp(SortCache->StrP + GA->Name,SortCache->StrP + GB->Name);
+   if (A == 0)
+      return false;
+   if (B == 0 || A == B)
+      return true;
+   pkgCache::Group const * const GA = Owner->GrpP + A;
+   pkgCache::Group const * const GB = Owner->GrpP + B;
+   return strcmp(Owner->StrP + GA->Name, Owner->StrP + GB->Name) <= 0;
 }
-									/*}}}*/
-// CacheFile::Sort - Sort by name					/*{{{*/
-// ---------------------------------------------------------------------
-/* */
-void CacheFile::Sort()
+SortedPackageUniverse::SortedPackageUniverse(CacheFile &Cache) :
+      PackageUniverse{Cache}, List{Cache.UniverseList}
 {
-   delete [] List;
-   List = new pkgCache::Package *[Cache->Head().PackageCount];
-   memset(List,0,sizeof(*List)*Cache->Head().PackageCount);
-   pkgCache::PkgIterator I = Cache->PkgBegin();
-   for (;I.end() != true; ++I)
-      List[I->ID] = I;
-
-   SortCache = *this;
-   qsort(List,Cache->Head().PackageCount,sizeof(*List),NameComp);
 }
-									/*}}}*/
+void SortedPackageUniverse::LazyInit() const
+{
+   if (List.empty() == false)
+      return;
+   pkgCache * const Owner = data();
+   // In Multi-Arch systems Grps are easier to sort than Pkgs
+   std::vector<map_pointer_t> GrpList;
+   List.reserve(Owner->Head().GroupCount);
+   for (pkgCache::GrpIterator I{Owner->GrpBegin()}; I.end() != true; ++I)
+      GrpList.emplace_back(I - Owner->GrpP);
+   std::stable_sort(GrpList.begin(), GrpList.end(), std::bind( &SortPackagesByName, Owner, std::placeholders::_1, std::placeholders::_2 ));
+   List.reserve(Owner->Head().PackageCount);
+   for (auto G : GrpList)
+   {
+      pkgCache::GrpIterator const Grp(*Owner, Owner->GrpP + G);
+      for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() != true; P = Grp.NextPkg(P))
+	 List.emplace_back(P - Owner->PkgP);
+   }
+}
 // CacheFile::CheckDeps - Open the cache file				/*{{{*/
 // ---------------------------------------------------------------------
 /* This routine generates the caches and then opens the dependency cache
diff --git a/apt-private/private-cachefile.h b/apt-private/private-cachefile.h
index 1fddabfbd..4a68d9733 100644
--- a/apt-private/private-cachefile.h
+++ b/apt-private/private-cachefile.h
@@ -7,12 +7,13 @@
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/macros.h>
 #include <apt-pkg/sourcelist.h>
+#include <apt-pkg/cacheset.h>
+
 #include <apti18n.h>
 
-// FIXME: we need to find a way to export this 
+// FIXME: we need to find a way to export this
 class APT_PUBLIC SourceList : public pkgSourceList
 {
-   
  public:
    // Add custom metaIndex (e.g. local files)
    void AddMetaIndex(metaIndex *mi) {
@@ -22,17 +23,11 @@ class APT_PUBLIC SourceList : public pkgSourceList
 };
 
 // class CacheFile - Cover class for some dependency cache functions	/*{{{*/
-// ---------------------------------------------------------------------
-/* */
 class APT_PUBLIC CacheFile : public pkgCacheFile
 {
-   static pkgCache *SortCache;
-   APT_HIDDEN static int NameComp(const void *a,const void *b) APT_PURE;
-
    public:
-   pkgCache::Package **List;
-   
-   void Sort();
+   std::vector<map_pointer_t> UniverseList;
+
    bool CheckDeps(bool AllowBroken = false);
    bool BuildCaches(bool WithLock = true)
    {
@@ -51,14 +46,10 @@ class APT_PUBLIC CacheFile : public pkgCacheFile
          return _error->Error(_("The list of sources could not be read."));
       return true;
    }
-   bool Open(bool WithLock = true) 
+   bool Open(bool WithLock = true)
    {
       OpTextProgress Prog(*_config);
-      if (pkgCacheFile::Open(&Prog,WithLock) == false)
-	 return false;
-      Sort();
-      
-      return true;
+      return pkgCacheFile::Open(&Prog,WithLock);
    };
    bool OpenForInstall()
    {
@@ -67,11 +58,39 @@ class APT_PUBLIC CacheFile : public pkgCacheFile
       else
 	 return Open(true);
    }
-   CacheFile() : List(0) {};
-   ~CacheFile() {
-      delete[] List;
-   }
 };
 									/*}}}*/
 
+class APT_PUBLIC SortedPackageUniverse : public APT::PackageUniverse
+{
+   std::vector<map_pointer_t> &List;
+   void LazyInit() const;
+
+public:
+   SortedPackageUniverse(CacheFile &Cache);
+
+   class const_iterator : public APT::Container_iterator_base<APT::PackageContainerInterface, SortedPackageUniverse, SortedPackageUniverse::const_iterator, std::vector<map_pointer_t>::const_iterator, pkgCache::PkgIterator>
+   {
+      pkgCache * const Cache;
+      protected:
+	 inline virtual pkgCache::PkgIterator getType(void) const APT_OVERRIDE
+	 {
+	    if (*_iter == 0) return pkgCache::PkgIterator(*Cache);
+	    return pkgCache::PkgIterator(*Cache, Cache->PkgP + *_iter);
+	 }
+      public:
+	 explicit const_iterator(pkgCache * const Owner, std::vector<map_pointer_t>::const_iterator i):
+	    Container_iterator_base<APT::PackageContainerInterface, SortedPackageUniverse, SortedPackageUniverse::const_iterator, std::vector<map_pointer_t>::const_iterator, pkgCache::PkgIterator>(i), Cache(Owner) {}
+
+   };
+   typedef const_iterator iterator;
+
+   APT_PUBLIC const_iterator begin() const { LazyInit(); return const_iterator(data(), List.begin()); }
+   APT_PUBLIC const_iterator end() const { LazyInit(); return const_iterator(data(), List.end()); }
+   APT_PUBLIC const_iterator cbegin() const { LazyInit(); return const_iterator(data(), List.begin()); }
+   APT_PUBLIC const_iterator cend() const { LazyInit(); return const_iterator(data(), List.end()); }
+   APT_PUBLIC iterator begin() { LazyInit(); return iterator(data(), List.begin()); }
+   APT_PUBLIC iterator end() { LazyInit(); return iterator(data(), List.end()); }
+};
+
 #endif
diff --git a/apt-private/private-cacheset.h b/apt-private/private-cacheset.h
index 518f179f3..7cafe4fdd 100644
--- a/apt-private/private-cacheset.h
+++ b/apt-private/private-cacheset.h
@@ -12,6 +12,8 @@
 #include <apt-pkg/cacheiterators.h>
 #include <apt-pkg/macros.h>
 
+#include <apt-private/private-output.h>
+
 #include <algorithm>
 #include <vector>
 #include <string.h>
@@ -21,8 +23,6 @@
 #include <string>
 #include <utility>
 
-#include "private-output.h"
-
 #include <apti18n.h>
 
 class OpProgress;
@@ -174,17 +174,19 @@ public:
 				std::string VersionsList;
 				SPtrArray<bool> Seen = new bool[Cache.GetPkgCache()->Head().PackageCount];
 				memset(Seen,0,Cache.GetPkgCache()->Head().PackageCount*sizeof(*Seen));
+				APT::PackageList pkglist;
 				for (pkgCache::DepIterator Dep = Pkg.RevDependsList();
 				     Dep.end() == false; ++Dep) {
 					if (Dep->Type != pkgCache::Dep::Replaces)
 						continue;
-					if (Seen[Dep.ParentPkg()->ID] == true)
+					pkgCache::PkgIterator const DP = Dep.ParentPkg();
+					if (Seen[DP->ID] == true)
 						continue;
-					Seen[Dep.ParentPkg()->ID] = true;
-					List += Dep.ParentPkg().FullName(true) + " ";
-					//VersionsList += std::string(Dep.ParentPkg().CurVersion) + "\n"; ???
+					Seen[DP->ID] = true;
+					pkglist.insert(DP);
 				}
-				ShowList(c1out,_("However the following packages replace it:"),List,VersionsList);
+				ShowList(c1out, _("However the following packages replace it:"), pkglist,
+				      &AlwaysTrue, &PrettyFullName, &EmptyString);
 			}
 			c1out << std::endl;
 		}
diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index 3474d262a..cdca45755 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -374,11 +374,10 @@ static bool DoAutomaticRemove(CacheFile &Cache)
 
    unsigned long autoRemoveCount = 0;
    APT::PackageSet tooMuch;
-   APT::PackageList autoRemoveList;
+   SortedPackageUniverse Universe(Cache);
    // look over the cache to see what can be removed
-   for (unsigned J = 0; J < Cache->Head().PackageCount; ++J)
+   for (auto const &Pkg: Universe)
    {
-      pkgCache::PkgIterator Pkg(Cache,Cache.List[J]);
       if (Cache[Pkg].Garbage)
       {
 	 if(Pkg.CurrentVer() != 0 || Cache[Pkg].Install())
@@ -395,8 +394,6 @@ static bool DoAutomaticRemove(CacheFile &Cache)
 	 }
 	 else
 	 {
-	    if (hideAutoRemove == false && Cache[Pkg].Delete() == false)
-	       autoRemoveList.insert(Pkg);
 	    // if the package is a new install and already garbage we don't need to
 	    // install it in the first place, so nuke it instead of show it
 	    if (Cache[Pkg].Install() == true && Pkg.CurrentVer() == 0)
@@ -456,18 +453,6 @@ static bool DoAutomaticRemove(CacheFile &Cache)
       } while (Changed == true);
    }
 
-   std::string autoremovelist, autoremoveversions;
-   if (smallList == false && autoRemoveCount != 0)
-   {
-      for (APT::PackageList::const_iterator Pkg = autoRemoveList.begin(); Pkg != autoRemoveList.end(); ++Pkg)
-      {
-	 if (Cache[Pkg].Garbage == false)
-	    continue;
-	 autoremovelist += Pkg.FullName(true) + " ";
-	 autoremoveversions += std::string(Cache[Pkg].CandVersion) + "\n";
-      }
-   }
-
    // Now see if we had destroyed anything (if we had done anything)
    if (Cache->BrokenCount() != 0)
    {
@@ -482,12 +467,17 @@ static bool DoAutomaticRemove(CacheFile &Cache)
    }
 
    // if we don't remove them, we should show them!
-   if (doAutoRemove == false && (autoremovelist.empty() == false || autoRemoveCount != 0))
+   if (doAutoRemove == false && autoRemoveCount != 0)
    {
       if (smallList == false)
+      {
+	 SortedPackageUniverse Universe(Cache);
 	 ShowList(c1out, P_("The following package was automatically installed and is no longer required:",
 	          "The following packages were automatically installed and are no longer required:",
-	          autoRemoveCount), autoremovelist, autoremoveversions);
+	          autoRemoveCount), Universe,
+	       [&Cache](pkgCache::PkgIterator const &Pkg) { return (*Cache)[Pkg].Garbage == true && (*Cache)[Pkg].Delete() == false; },
+	       &PrettyFullName, CandidateVersion(&Cache));
+      }
       else
 	 ioprintf(c1out, P_("%lu package was automatically installed and is no longer required.\n",
 	          "%lu packages were automatically installed and are no longer required.\n", autoRemoveCount), autoRemoveCount);
@@ -651,6 +641,18 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, CacheFile &Cache,
 // DoInstall - Install packages from the command line			/*{{{*/
 // ---------------------------------------------------------------------
 /* Install named packages */
+struct PkgIsExtraInstalled {
+   pkgCacheFile * const Cache;
+   APT::VersionSet const * const verset;
+   PkgIsExtraInstalled(pkgCacheFile * const Cache, APT::VersionSet const * const Container) : Cache(Cache), verset(Container) {}
+   bool operator() (pkgCache::PkgIterator const Pkg)
+   {
+        if ((*Cache)[Pkg].Install() == false)
+           return false;
+        pkgCache::VerIterator const Cand = (*Cache)[Pkg].CandidateVerIter(*Cache);
+        return verset->find(Cand) == verset->end();
+   }
+};
 bool DoInstall(CommandLine &CmdL)
 {
    CacheFile Cache;
@@ -689,35 +691,18 @@ bool DoInstall(CommandLine &CmdL)
 
    /* Print out a list of packages that are going to be installed extra
       to what the user asked */
+   SortedPackageUniverse Universe(Cache);
    if (Cache->InstCount() != verset[MOD_INSTALL].size())
-   {
-      std::string List;
-      std::string VersionsList;
-      for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-      {
-	 pkgCache::PkgIterator I(Cache,Cache.List[J]);
-	 if ((*Cache)[I].Install() == false)
-	    continue;
-	 pkgCache::VerIterator Cand = Cache[I].CandidateVerIter(Cache);
-
-	 if (verset[MOD_INSTALL].find(Cand) != verset[MOD_INSTALL].end())
-	    continue;
-
-	 List += I.FullName(true) + " ";
-	 VersionsList += std::string(Cache[I].CandVersion) + "\n";
-      }
-      
-      ShowList(c1out,_("The following extra packages will be installed:"),List,VersionsList);
-   }
+      ShowList(c1out, _("The following extra packages will be installed:"), Universe,
+	    PkgIsExtraInstalled(&Cache, &verset[MOD_INSTALL]),
+	    &PrettyFullName, CandidateVersion(&Cache));
 
    /* Print out a list of suggested and recommended packages */
    {
       std::string SuggestsList, RecommendsList;
       std::string SuggestsVersions, RecommendsVersions;
-      for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
+      for (auto const &Pkg: Universe)
       {
-	 pkgCache::PkgIterator Pkg(Cache,Cache.List[J]);
-
 	 /* Just look at the ones we want to install */
 	 if ((*Cache)[Pkg].Install() == false)
 	   continue;
@@ -738,7 +723,6 @@ bool DoInstall(CommandLine &CmdL)
 	    for(;;)
 	    {
 	       /* Skip if package is  installed already, or is about to be */
-               std::string target = Start.TargetPkg().FullName(true) + " ";
 	       pkgCache::PkgIterator const TarPkg = Start.TargetPkg();
 	       if (TarPkg->SelectedState == pkgCache::State::Install ||
 		   TarPkg->SelectedState == pkgCache::State::Hold ||
@@ -749,6 +733,7 @@ bool DoInstall(CommandLine &CmdL)
 	       }
 
 	       /* Skip if we already saw it */
+               std::string target = Start.TargetPkg().FullName(true) + " ";
 	       if (int(SuggestsList.find(target)) != -1 || int(RecommendsList.find(target)) != -1)
 	       {
 		  foundInstalledInOrGroup=true;
diff --git a/apt-private/private-output.cc b/apt-private/private-output.cc
index 9944ab002..b77efff86 100644
--- a/apt-private/private-output.cc
+++ b/apt-private/private-output.cc
@@ -25,6 +25,8 @@
 #include <signal.h>
 #include <sys/ioctl.h>
 
+#include <sstream>
+
 #include <apti18n.h>
 									/*}}}*/
 
@@ -491,11 +493,9 @@ void ShowBroken(ostream &out, CacheFile &Cache, bool const Now)
       return;
 
    out << _("The following packages have unmet dependencies:") << endl;
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-   {
-      pkgCache::PkgIterator const I(Cache,Cache.List[J]);
-      ShowBrokenPackage(out, &Cache, I, Now);
-   }
+   SortedPackageUniverse Universe(Cache);
+   for (auto const &Pkg: Universe)
+      ShowBrokenPackage(out, &Cache, Pkg, Now);
 }
 void ShowBroken(ostream &out, pkgCacheFile &Cache, bool const Now)
 {
@@ -503,98 +503,64 @@ void ShowBroken(ostream &out, pkgCacheFile &Cache, bool const Now)
       return;
 
    out << _("The following packages have unmet dependencies:") << endl;
-   for (pkgCache::PkgIterator Pkg = Cache->PkgBegin(); Pkg.end() == false; ++Pkg)
+   APT::PackageUniverse Universe(Cache);
+   for (auto const &Pkg: Universe)
       ShowBrokenPackage(out, &Cache, Pkg, Now);
 }
 									/*}}}*/
 // ShowNew - Show packages to newly install				/*{{{*/
-// ---------------------------------------------------------------------
-/* */
 void ShowNew(ostream &out,CacheFile &Cache)
 {
-   /* Print out a list of packages that are going to be installed extra
-      to what the user asked */
-   string List;
-   string VersionsList;
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-   {
-      pkgCache::PkgIterator I(Cache,Cache.List[J]);
-      if (Cache[I].NewInstall() == true) {
-         List += I.FullName(true) + " ";
-         VersionsList += string(Cache[I].CandVersion) + "\n";
-      }
-   }
-   
-   ShowList(out,_("The following NEW packages will be installed:"),List,VersionsList);
+   SortedPackageUniverse Universe(Cache);
+   ShowList(out,_("The following NEW packages will be installed:"), Universe,
+	 [&Cache](pkgCache::PkgIterator const &Pkg) { return Cache[Pkg].NewInstall(); },
+	 &PrettyFullName,
+	 CandidateVersion(&Cache));
 }
 									/*}}}*/
 // ShowDel - Show packages to delete					/*{{{*/
-// ---------------------------------------------------------------------
-/* */
 void ShowDel(ostream &out,CacheFile &Cache)
 {
-   /* Print out a list of packages that are going to be removed extra
-      to what the user asked */
-   string List;
-   string VersionsList;
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-   {
-      pkgCache::PkgIterator I(Cache,Cache.List[J]);
-      if (Cache[I].Delete() == true)
-      {
-	 if ((Cache[I].iFlags & pkgDepCache::Purge) == pkgDepCache::Purge)
-	    List += I.FullName(true) + "* ";
-	 else
-	    List += I.FullName(true) + " ";
-     
-     VersionsList += string(Cache[I].CandVersion)+ "\n";
-      }
-   }
-   
-   ShowList(out,_("The following packages will be REMOVED:"),List,VersionsList);
+   SortedPackageUniverse Universe(Cache);
+   ShowList(out,_("The following packages will be REMOVED:"), Universe,
+	 [&Cache](pkgCache::PkgIterator const &Pkg) { return Cache[Pkg].Delete(); },
+	 [&Cache](pkgCache::PkgIterator const &Pkg)
+	 {
+	    std::string str = PrettyFullName(Pkg);
+	    if (((*Cache)[Pkg].iFlags & pkgDepCache::Purge) == pkgDepCache::Purge)
+	       str.append("*");
+	    return str;
+	 },
+	 CandidateVersion(&Cache));
 }
 									/*}}}*/
 // ShowKept - Show kept packages					/*{{{*/
-// ---------------------------------------------------------------------
-/* */
 void ShowKept(ostream &out,CacheFile &Cache)
 {
-   string List;
-   string VersionsList;
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-   {	 
-      pkgCache::PkgIterator I(Cache,Cache.List[J]);
-      
-      // Not interesting
-      if (Cache[I].Upgrade() == true || Cache[I].Upgradable() == false ||
-	  I->CurrentVer == 0 || Cache[I].Delete() == true)
-	 continue;
-      
-      List += I.FullName(true) + " ";
-      VersionsList += string(Cache[I].CurVersion) + " => " + Cache[I].CandVersion + "\n";
-   }
-   ShowList(out,_("The following packages have been kept back:"),List,VersionsList);
+   SortedPackageUniverse Universe(Cache);
+   ShowList(out,_("The following packages have been kept back:"), Universe,
+	 [&Cache](pkgCache::PkgIterator const &Pkg)
+	 {
+	    return Cache[Pkg].Upgrade() == false &&
+		   Cache[Pkg].Upgradable() == true &&
+		   Pkg->CurrentVer != 0 &&
+		   Cache[Pkg].Delete() == false;
+	 },
+	 &PrettyFullName,
+	 CurrentToCandidateVersion(&Cache));
 }
 									/*}}}*/
 // ShowUpgraded - Show upgraded packages				/*{{{*/
-// ---------------------------------------------------------------------
-/* */
 void ShowUpgraded(ostream &out,CacheFile &Cache)
 {
-   string List;
-   string VersionsList;
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-   {
-      pkgCache::PkgIterator I(Cache,Cache.List[J]);
-      
-      // Not interesting
-      if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
-	 continue;
-
-      List += I.FullName(true) + " ";
-      VersionsList += string(Cache[I].CurVersion) + " => " + Cache[I].CandVersion + "\n";
-   }
-   ShowList(out,_("The following packages will be upgraded:"),List,VersionsList);
+   SortedPackageUniverse Universe(Cache);
+   ShowList(out,_("The following packages will be upgraded:"), Universe,
+	 [&Cache](pkgCache::PkgIterator const &Pkg)
+	 {
+	    return Cache[Pkg].Upgrade() == true && Cache[Pkg].NewInstall() == false;
+	 },
+	 &PrettyFullName,
+	 CurrentToCandidateVersion(&Cache));
 }
 									/*}}}*/
 // ShowDowngraded - Show downgraded packages				/*{{{*/
@@ -602,74 +568,73 @@ void ShowUpgraded(ostream &out,CacheFile &Cache)
 /* */
 bool ShowDowngraded(ostream &out,CacheFile &Cache)
 {
-   string List;
-   string VersionsList;
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-   {
-      pkgCache::PkgIterator I(Cache,Cache.List[J]);
-      
-      // Not interesting
-      if (Cache[I].Downgrade() == false || Cache[I].NewInstall() == true)
-	 continue;
-
-      List += I.FullName(true) + " ";
-      VersionsList += string(Cache[I].CurVersion) + " => " + Cache[I].CandVersion + "\n";
-   }
-   return ShowList(out,_("The following packages will be DOWNGRADED:"),List,VersionsList);
+   SortedPackageUniverse Universe(Cache);
+   return ShowList(out,_("The following packages will be DOWNGRADED:"), Universe,
+	 [&Cache](pkgCache::PkgIterator const &Pkg)
+	 {
+	    return Cache[Pkg].Downgrade() == true && Cache[Pkg].NewInstall() == false;
+	 },
+	 &PrettyFullName,
+	 CurrentToCandidateVersion(&Cache));
 }
 									/*}}}*/
 // ShowHold - Show held but changed packages				/*{{{*/
-// ---------------------------------------------------------------------
-/* */
 bool ShowHold(ostream &out,CacheFile &Cache)
 {
-   string List;
-   string VersionsList;
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
-   {
-      pkgCache::PkgIterator I(Cache,Cache.List[J]);
-      if (Cache[I].InstallVer != (pkgCache::Version *)I.CurrentVer() &&
-          I->SelectedState == pkgCache::State::Hold) {
-         List += I.FullName(true) + " ";
-		 VersionsList += string(Cache[I].CurVersion) + " => " + Cache[I].CandVersion + "\n";
-      }
-   }
-
-   return ShowList(out,_("The following held packages will be changed:"),List,VersionsList);
+   SortedPackageUniverse Universe(Cache);
+   return ShowList(out,_("The following held packages will be changed:"), Universe,
+	 [&Cache](pkgCache::PkgIterator const &Pkg)
+	 {
+	    return Pkg->SelectedState == pkgCache::State::Hold &&
+		   Cache[Pkg].InstallVer != (pkgCache::Version *)Pkg.CurrentVer();
+	 },
+	 &PrettyFullName,
+	 CurrentToCandidateVersion(&Cache));
 }
 									/*}}}*/
 // ShowEssential - Show an essential package warning			/*{{{*/
 // ---------------------------------------------------------------------
 /* This prints out a warning message that is not to be ignored. It shows
-   all essential packages and their dependents that are to be removed. 
+   all essential packages and their dependents that are to be removed.
    It is insanely risky to remove the dependents of an essential package! */
+struct APT_HIDDEN PrettyFullNameWithDue {
+   std::map<unsigned long long, pkgCache::PkgIterator> due;
+   PrettyFullNameWithDue() {}
+   std::string operator() (pkgCache::PkgIterator const &Pkg)
+   {
+      std::string const A = PrettyFullName(Pkg);
+      std::map<unsigned long long, pkgCache::PkgIterator>::const_iterator d = due.find(Pkg->ID);
+      if (d == due.end())
+        return A;
+
+      std::string const B = PrettyFullName(d->second);
+      std::ostringstream outstr;
+      ioprintf(outstr, _("%s (due to %s)"), A.c_str(), B.c_str());
+      return outstr.str();
+   }
+};
 bool ShowEssential(ostream &out,CacheFile &Cache)
 {
-   string List;
-   string VersionsList;
-   bool *Added = new bool[Cache->Head().PackageCount];
-   for (unsigned int I = 0; I != Cache->Head().PackageCount; I++)
-      Added[I] = false;
-   
-   for (unsigned J = 0; J < Cache->Head().PackageCount; J++)
+   std::vector<bool> Added(Cache->Head().PackageCount, false);
+   APT::PackageDeque pkglist;
+   PrettyFullNameWithDue withdue;
+
+   SortedPackageUniverse Universe(Cache);
+   for (pkgCache::PkgIterator const &I: Universe)
    {
-      pkgCache::PkgIterator I(Cache,Cache.List[J]);
       if ((I->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
 	  (I->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
 	 continue;
-      
+
       // The essential package is being removed
-      if (Cache[I].Delete() == true)
+      if (Cache[I].Delete() == false)
+	 continue;
+
+      if (Added[I->ID] == false)
       {
-	 if (Added[I->ID] == false)
-	 {
-	    Added[I->ID] = true;
-	    List += I.FullName(true) + " ";
-        //VersionsList += string(Cache[I].CurVersion) + "\n"; ???
-	 }
+	 Added[I->ID] = true;
+	 pkglist.insert(I);
       }
-      else
-	 continue;
 
       if (I->CurrentVer == 0)
 	 continue;
@@ -681,27 +646,23 @@ bool ShowEssential(ostream &out,CacheFile &Cache)
 	 if (D->Type != pkgCache::Dep::PreDepends &&
 	     D->Type != pkgCache::Dep::Depends)
 	    continue;
-	 
+
 	 pkgCache::PkgIterator P = D.SmartTargetPkg();
 	 if (Cache[P].Delete() == true)
 	 {
 	    if (Added[P->ID] == true)
 	       continue;
 	    Added[P->ID] = true;
-	    
-	    char S[300];
-	    snprintf(S,sizeof(S),_("%s (due to %s) "),P.FullName(true).c_str(),I.FullName(true).c_str());
-	    List += S;
-        //VersionsList += "\n"; ???
-	 }	 
-      }      
+
+	    pkglist.insert(P);
+	    withdue.due[P->ID] = I;
+	 }
+      }
    }
-   
-   delete [] Added;
    return ShowList(out,_("WARNING: The following essential packages will be removed.\n"
-			 "This should NOT be done unless you know exactly what you are doing!"),List,VersionsList);
+			 "This should NOT be done unless you know exactly what you are doing!"),
+	 pkglist, &AlwaysTrue, withdue, &EmptyString);
 }
-
 									/*}}}*/
 // Stats - Show some statistics						/*{{{*/
 // ---------------------------------------------------------------------
@@ -829,3 +790,33 @@ bool AnalPrompt(const char *Text)
    return false;
 }
 									/*}}}*/
+
+std::string PrettyFullName(pkgCache::PkgIterator const &Pkg)
+{
+   return Pkg.FullName(true);
+}
+std::string CandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg)
+{
+   return (*Cache)[Pkg].CandVersion;
+}
+std::function<std::string(pkgCache::PkgIterator const &)> CandidateVersion(pkgCacheFile * const Cache)
+{
+   return std::bind(static_cast<std::string(*)(pkgCacheFile * const, pkgCache::PkgIterator const&)>(&CandidateVersion), Cache, std::placeholders::_1);
+}
+std::string CurrentToCandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg)
+{
+   return std::string((*Cache)[Pkg].CurVersion) + " => " + (*Cache)[Pkg].CandVersion;
+}
+std::function<std::string(pkgCache::PkgIterator const &)> CurrentToCandidateVersion(pkgCacheFile * const Cache)
+{
+   return std::bind(static_cast<std::string(*)(pkgCacheFile * const, pkgCache::PkgIterator const&)>(&CurrentToCandidateVersion), Cache, std::placeholders::_1);
+}
+bool AlwaysTrue(pkgCache::PkgIterator const &)
+{
+      return true;
+}
+std::string EmptyString(pkgCache::PkgIterator const &)
+{
+   return std::string();
+}
+
diff --git a/apt-private/private-output.h b/apt-private/private-output.h
index d5b57adec..b9151b245 100644
--- a/apt-private/private-output.h
+++ b/apt-private/private-output.h
@@ -1,9 +1,11 @@
 #ifndef APT_PRIVATE_OUTPUT_H
 #define APT_PRIVATE_OUTPUT_H
 
+#include <apt-pkg/configuration.h>
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/macros.h>
 
+#include <functional>
 #include <fstream>
 #include <string>
 #include <iostream>
@@ -32,8 +34,63 @@ void ListSingleVersion(pkgCacheFile &CacheFile, pkgRecords &records,
 APT_PUBLIC void ShowBroken(std::ostream &out, CacheFile &Cache, bool const Now);
 APT_PUBLIC void ShowBroken(std::ostream &out, pkgCacheFile &Cache, bool const Now);
 
-APT_PUBLIC bool ShowList(std::ostream &out, std::string Title, std::string List,
+template<class Container> APT_PUBLIC bool ShowList(std::ostream &out, std::string const &Title,
+      Container const &cont,
+      std::function<bool(pkgCache::PkgIterator const &)> Predicate,
+      std::function<std::string(pkgCache::PkgIterator const &)> PkgDisplay,
+      std::function<std::string(pkgCache::PkgIterator const &)> VerboseDisplay)
+{
+   size_t const ScreenWidth = (::ScreenWidth > 3) ? ::ScreenWidth - 3 : 0;
+   int ScreenUsed = 0;
+   bool const ShowVersions = _config->FindB("APT::Get::Show-Versions", false);
+   bool printedTitle = false;
+
+   for (auto const &Pkg: cont)
+   {
+      if (Predicate(Pkg) == false)
+	 continue;
+
+      if (printedTitle == false)
+      {
+	 out << Title;
+	 printedTitle = true;
+      }
+
+      if (ShowVersions == true)
+      {
+	 out << std::endl << "   " << PkgDisplay(Pkg);
+	 std::string const verbose = VerboseDisplay(Pkg);
+	 if (verbose.empty() == false)
+	    out << " (" << verbose << ")";
+      }
+      else
+      {
+	 std::string const PkgName = PkgDisplay(Pkg);
+	 if (ScreenUsed == 0 || (ScreenUsed + PkgName.length()) >= ScreenWidth)
+	 {
+	    out << std::endl << "  ";
+	    ScreenUsed = 0;
+	 }
+	 else if (ScreenUsed != 0)
+	 {
+	    out << " ";
+	    ++ScreenUsed;
+	 }
+	 out << PkgName;
+	 ScreenUsed += PkgName.length();
+      }
+   }
+
+   if (printedTitle == true)
+   {
+      out << std::endl;
+      return false;
+   }
+   return true;
+}
+APT_DEPRECATED APT_PUBLIC bool ShowList(std::ostream &out, std::string Title, std::string List,
               std::string VersionsList);
+
 void ShowNew(std::ostream &out,CacheFile &Cache);
 void ShowDel(std::ostream &out,CacheFile &Cache);
 void ShowKept(std::ostream &out,CacheFile &Cache);
@@ -49,4 +106,12 @@ void Stats(std::ostream &out, pkgDepCache &Dep);
 bool YnPrompt(bool Default=true);
 bool AnalPrompt(const char *Text);
 
+APT_PUBLIC std::string PrettyFullName(pkgCache::PkgIterator const &Pkg);
+APT_PUBLIC std::string CandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg);
+APT_PUBLIC std::function<std::string(pkgCache::PkgIterator const &)> CandidateVersion(pkgCacheFile * const Cache);
+APT_PUBLIC std::string CurrentToCandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg);
+APT_PUBLIC std::function<std::string(pkgCache::PkgIterator const &)> CurrentToCandidateVersion(pkgCacheFile * const Cache);
+APT_PUBLIC std::string EmptyString(pkgCache::PkgIterator const &);
+APT_PUBLIC bool AlwaysTrue(pkgCache::PkgIterator const &);
+
 #endif