Print fixed width list sorted by column

Question

I have a list of varying length where items is strings of varying length. I want to print them by (a mirrored N)/order by column.

Major points being:

• Columns shall have fixed width == widest data in that column.
• It shall be as compact as possible.
• Number of columns is varying/induced by available width of canvas.
• Order of items should not be rearranged.
• (Item lists printed column wise on a horizontal order disgusts me.)

Optionally:

• Distribution should optionally favour either lower left or upper right.

I currently use this in terminal by bash, C etc. but other uses is not hard to imagine.

Result of calculations should be:

• columns
• lines
• width of each column

As, by this, one can fairly easy print the data in a fixed with column table.

Main question: Is there is some nifty way to do this. (I'm inspired by Knuth's Computer musings.)

My current approach is rather straight forward. Hard to specify the question without some gory details so here we go:

---

Data Examples

E.g. (by index of string array):

0  4  8 12   or    0  4  8 12     or   0  3  6  9 12 15
1  5  9 13         1  5  9 13          1  4  7 10 13
2  6 10 14         2  6 10             2  5  8 11 14
3  7 11 15         3  7 11             

favouring lower left     favouring upper right
0  4  8 12               0  4  8 11
1  5  9 13               1  5  9 12
2  6 10                  2  6 10 13
3  7 11                  3  7

E.g. (by data - actual output):

0) Item number 00000 4) Item Number 04        8) Item Number 008   12) Item Number 00012
1) Item Number 00001 5) Item Number 5         9) Item Number 00009 13) Item Number 0013 
2) Item Number 02    6) Item Number 00000006 10) Item Number 10   
3) Item Number 003   7) Item Number 7        11) Item Number 11

---

Current implementation

As of now I do this by (approximately) e.g. in bash:

1. Adding the length of each item to array lens and track longest item.
2. Add width for number + 1 for ) + 1 for space to longest item.
3. Calculate maximum columns given that width.
4. Re-calculating width of item number (The one before ')' in the print.) for each column.
5. Calculating actual longest width for items in each column.

6. Re-calculating:

    while `lines` > 1 ; do
   
         * Available width = Canvas width - total print width
         * Test:
               Find longest item in last column as if columns was increased by 1.
         * If longest_in_last_column_test < available width
                increase columns by 1.
                recalculate all column widths.
           Else
                break
           End If
    done
   

7. Print list.

---

Thoughts

Cant' help but wonder if there is some way to calculate this by other means. E.g. by using matrix mathematics, - or perhaps some nice algorithm out there.

Perhaps hard in bash, but in C by pointers to structs or object related languages.

Exempli gratia:

struct item {
    int len;
    char *val;
}

struct item items = {{5, "Hello"}, {3, "You"}, ...}

Which would give a matrix of typically

# index:length
0:5 1:2 2:1 3:3 4:5 
5:2 6:6 7:9 8:1 9:6

Then by having the restraint of sum of each row being <= available width, e.g. 25, rearrange matrix.

longest: 5 5 9 6 => sum 25
--------------------------
         5 3 6 1 => sum 15
         5 5 9 6 => sum 25
         1 2 1   => sum  4

Answer 1

Here's what I've come up with:

struct Item
{
    uint prefix_length; // for the prefix numbers; e.g. "100) " would be length 5
    uint item_length;   // length of the item
    char *item;         // string contents
}

struct Column
{
    uint starting_index;
    uint num_items;
    uint max_prefix_length;
    uint max_item_length;
}

/*

Initialization

Make a list of Items and initialize their prefix_lengths based on where they are in the list and w/e other characters the prefix will have (i.e. number length + paren + buffer space).

Then make a (dynamic) list of Columns, the same length as the number of Items, with the starting_index of each column set to its index in the list (so that it corresponds to an Item) and num_items set to 1. The max_prefix_length and max_item_length should be initialized to the corresponding values of the Item to which the Column is pointing.

Items: [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [...]
         ^     ^     ^     ^     ^     ^     ^     ^
Cols:    0     1     2     3     4     5     6    ...

Main Loop

The first thing to do in the main loop would be to iterate across the Columns, incrementing num_items by 1 and incrementing starting_index by 0 for the first Column, by 1 for the second Column, by 2 for the third Column, etc.

After the first iteration this will give you:

Items: [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [...]
         ^     ^     ^     ^     ^     ^     ^     ^
Cols:    +--0--+     +--1--+     +--2--+     +--3--+  ...

The second iteration would get:

Items: [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [...]
         ^           ^     ^           ^     ^
Cols:    +-----0-----+     +-----1-----+     +-----2-...

Note that you'll have to remove any Columns whose starting_index becomes larger than the number of items in the Items list.

After incrementing these values, set the max_prefix_length of each Column to the corresponding value of the last Item it points to. For the max_item_length, sadly, you'll have to iterate over the Items the Column spans to find the max item_length.

The termination condition of the main loop will be to see whether the sum of the max_prefix_length + max_item_length of all the columns (plus whatever buffer space between the columns you want) is less than the total width you have. (Don't forget the edge condition of an Item that has a length greater than the total width.) EDIT: Sadly this termination condition would require you to keep the result of the last iteration around, since the loop would only terminate after an invalid result was found.

If there were some way of doing a walking maximum for the items spanned by each column, that would be awesome (but sadly I can't think of one at the moment).

---

Of course, after writing all this out I see that it's basically coming at this from the opposite direction as your algorithm; maybe it'll give you some ideas though.