Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
share|improve this question
    
If you could summarize the crux of your question that might help? Your actual question is probably in there somewhere but there's a lot to look over here. –  Jimmy Hoffa Feb 11 '13 at 20:03
    
@JimmyHoffa: Reading it over you're correct. I'll rewrite or delete. –  Sukminder Feb 11 '13 at 20:08

1 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.

share|improve this answer
    
Thanks for reply! I have looked at various ways on this. I'm not able to find a "very smart" way to do this, but I use the base from my core in my Q - as this gives the possibility to eliminate quite a few checks, take advantage of previous calculations more efficiently etc. –  Sukminder Feb 23 '13 at 19:02
    
This does seem like the sort of problem that someone would have come up with a clever solution to. Mine was only off the top of my head. I hope you do find a smart(er) way to do this! –  paul Feb 25 '13 at 13:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.