Columnar output for package lists similar to 'ls'

This change makes it a bit easier to quickly grasp the changes
about to be performed by apt.

It displays package lists in a columnar format by default,
similar to what `ls` produces for files.

A new long option `--no-list-columns` and an associated
`APT::Get::List-Columns` config setting control the behavior.

Usage example, with 60 column wide terminal:

```
$ sudo apt upgrade                                          |
Reading package lists... Done                               |
Building dependency tree... Done                            |
Reading state information... Done                           |
Calculating upgrade... Done                                 |
The following packages were automatically installed and are |
no longer required:                                         |
  libappindicator1 libindicator7                            |
  libdbusmenu-gtk4 linux-image-5.14.0-4-amd64               |
Use 'sudo apt autoremove' to remove them.                   |
The following packages have been kept back:                 |
  criu        linux-headers-amd64 nvidia-settings           |
  libxnvctrl0 nvidia-modprobe     xwayland                  |
0 upgraded, 0 newly installed, 0 to remove and 6 not upgrade|
d.                                                          |
```

The effect becomes more pronounced with more packages (e.g. when
doing a dist-upgrade).

3 files changed, 102 insertions, 11 deletions

diff --git a/apt-private/private-cmndline.cc b/apt-private/private-cmndline.cc
index 79881d034..cbab22031 100644
--- a/apt-private/private-cmndline.cc
+++ b/apt-private/private-cmndline.cc
@@ -184,7 +184,8 @@ static bool addArgumentsAPTGet(std::vector<CommandLine::Args> &Args, char const
       addArg(0, "show-progress", "DpkgPM::Progress", 0);
       addArg('f', "fix-broken", "APT::Get::Fix-Broken", 0);
       addArg(0, "purge", "APT::Get::Purge", 0);
-      addArg('V',"verbose-versions","APT::Get::Show-Versions",0);
+      addArg('V',"verbose-versions", "APT::Get::Show-Versions",0);
+      addArg(0, "list-columns", "APT::Get::List-Columns", 0);
       addArg(0, "autoremove", "APT::Get::AutomaticRemove", 0);
       addArg(0, "auto-remove", "APT::Get::AutomaticRemove", 0);
       addArg(0, "reinstall", "APT::Get::ReInstall", 0);
diff --git a/apt-private/private-output.cc b/apt-private/private-output.cc
index 93b942458..f04c35b8a 100644
--- a/apt-private/private-output.cc
+++ b/apt-private/private-output.cc
@@ -316,6 +316,83 @@ void ListSingleVersion(pkgCacheFile &CacheFile, pkgRecords &records,	/*{{{*/
    out << output;
 }
 									/*}}}*/
+// ShowWithColumns - Show a list in the style of ls			/*{{{*/
+// ---------------------------------------------------------------------
+/* This prints out a vector of strings with the given indent and in as
+   many columns as will fit the screen width.
+   
+   The output looks like:
+  abiword                debootstrap                  gir1.2-upowerglib-1.0
+  abiword-common         dh-make                      google-chrome-beta
+  abiword-plugin-grammar dmeventd                     gstreamer1.0-clutter-3.0
+  binfmt-support         dmsetup                      hostname
+  console-setup          evolution-data-server        iproute2
+  console-setup-linux    evolution-data-server-common
+  coreutils              ffmpeg
+ */
+struct columnInfo
+{
+   bool ValidLen;
+   size_t LineWidth;
+   vector<size_t> RemainingWidths;
+};
+void ShowWithColumns(ostream &out, vector<string> const &List, size_t Indent, size_t ScreenWidth)
+{
+   constexpr size_t MinColumnWidth = 2;
+   constexpr size_t ColumnSpace = 1;
+
+   size_t const ListSize = List.size();
+   size_t const MaxScreenCols = (ScreenWidth - Indent) /
+         MinColumnWidth;
+   size_t const MaxNumCols = min(MaxScreenCols, ListSize);
+
+   vector<columnInfo> ColumnInfo(MaxNumCols);
+   for (size_t I = 0; I < MaxNumCols; ++I) {
+      ColumnInfo[I].ValidLen = true;
+      ColumnInfo[I].LineWidth = (I + 1) * MinColumnWidth;
+      ColumnInfo[I].RemainingWidths.resize(I + 1, MinColumnWidth);
+   }
+
+   for (size_t I = 0; I < ListSize; ++I) {
+      for (size_t J = 0; J < MaxNumCols; ++J) {
+         auto& Col = ColumnInfo[J];
+         if (!Col.ValidLen)
+            continue;
+
+         size_t Idx = I / ((ListSize + J) / (J + 1));
+         size_t RealColLen = List[I].size() + (Idx == J ? 0 : ColumnSpace);
+         if (Col.RemainingWidths[Idx] < RealColLen) {
+            Col.LineWidth += RealColLen - Col.RemainingWidths[Idx];
+            Col.RemainingWidths[Idx] = RealColLen;
+            Col.ValidLen = Col.LineWidth < ScreenWidth;
+         }
+      }
+   }
+   size_t NumCols = MaxNumCols;
+   while (NumCols > 1 && !ColumnInfo[NumCols - 1].ValidLen)
+      --NumCols;
+
+   size_t NumRows = ListSize / NumCols + (ListSize % NumCols != 0);
+   auto const &LineFormat = ColumnInfo[NumCols - 1];
+   for (size_t Row = 0; Row < NumRows; ++Row) {
+      size_t Col = 0;
+      size_t I = Row;
+      out << string(Indent, ' ');
+      while (true) {
+         out << List[I];
+
+         size_t CurLen = List[I].size();
+         size_t MaxLen = LineFormat.RemainingWidths[Col++];
+         I += NumRows;
+         if (I >= ListSize)
+            break;
+
+         out << string(MaxLen - CurLen, ' ');
+      }
+      out << endl;
+   }
+}
+									/*}}}*/
 // ShowBroken - Debugging aide						/*{{{*/
 // ---------------------------------------------------------------------
 /* This prints out the names of all the packages that are broken along
diff --git a/apt-private/private-output.h b/apt-private/private-output.h
index c3e73d592..dcffd1880 100644
--- a/apt-private/private-output.h
+++ b/apt-private/private-output.h
@@ -10,6 +10,7 @@
 #include <functional>
 #include <iostream>
 #include <string>
+#include <vector>
 
 // forward declaration
 class pkgCacheFile;
@@ -35,6 +36,8 @@ 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 void ShowWithColumns(std::ostream &out, const std::vector<std::string> &List, size_t Indent, size_t ScreenWidth);
+
 template<class Container, class PredicateC, class DisplayP, class DisplayV> bool ShowList(std::ostream &out, std::string const &Title,
       Container const &cont,
       PredicateC Predicate,
@@ -44,7 +47,9 @@ template<class Container, class PredicateC, class DisplayP, class DisplayV> bool
    size_t const ScreenWidth = (::ScreenWidth > 3) ? ::ScreenWidth - 3 : 0;
    int ScreenUsed = 0;
    bool const ShowVersions = _config->FindB("APT::Get::Show-Versions", false);
+   bool const ListColumns = _config->FindB("APT::Get::List-Columns", true);
    bool printedTitle = false;
+   std::vector<std::string> PackageList;
 
    for (auto const &Pkg: cont)
    {
@@ -67,24 +72,32 @@ template<class Container, class PredicateC, class DisplayP, class DisplayV> bool
       else
       {
 	 std::string const PkgName = PkgDisplay(Pkg);
-	 if (ScreenUsed == 0 || (ScreenUsed + PkgName.length()) >= ScreenWidth)
-	 {
-	    out << std::endl << "  ";
-	    ScreenUsed = 0;
-	 }
-	 else if (ScreenUsed != 0)
+	 if (ListColumns)
+	    PackageList.push_back(PkgName);
+	 else
 	 {
-	    out << " ";
-	    ++ScreenUsed;
+	    if (ScreenUsed == 0 || (ScreenUsed + PkgName.length()) >= ScreenWidth)
+	    {
+	       out << std::endl
+		   << "  ";
+	       ScreenUsed = 0;
+	    }
+	    else if (ScreenUsed != 0)
+	    {
+	       out << " ";
+	       ++ScreenUsed;
+	    }
+	    out << PkgName;
+	    ScreenUsed += PkgName.length();
 	 }
-	 out << PkgName;
-	 ScreenUsed += PkgName.length();
       }
    }
 
    if (printedTitle == true)
    {
       out << std::endl;
+      if (ListColumns)
+	 ShowWithColumns(out, PackageList, 2, ScreenWidth);
       return false;
    }
    return true;