/* 
   Copyright (C) 85, 88, 90, 91, 1995-2004 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */      

/* Written by Richard Stallman, David MacKenzie and Stephen Jungels.  */

#include <sys/types.h>
#include <sys/ioctl.h>
#include <sys/termios.h>
#include <sys/unistd.h>
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <setjmp.h>
#include <signal.h>

#define PROGRAM_NAME cols
#define AUTHORS "Richard Stallman", "David MacKenzie"

#define true 1
#define false 0
#define MAX(a, b) ((a) < (b) ? (b) : (a))
#define MIN(a, b) ((a) < (b) ? (a) : (b))


struct fileinfo
  {
    /* The file name. */
    char *name;
  };

static void clear_files (void);
static void indent (size_t from, size_t to);
static size_t calculate_columns (int by_columns);
static void print_current_files (void);
static void print_file_name_and_frills (const struct fileinfo *f);
static void print_horizontal (void);
static void print_many_per_line (void);
static void gobble_file (const char *name);
static void usage();
static void version();

/* The name the program was run with, stripped of any leading path. */
char *program_name;

/* The table of files in the current directory:

   `files' points to a vector of `struct fileinfo', one per file.
   `nfiles' is the number of elements space has been allocated for.
   `files_index' is the number actually in use.  */

static struct fileinfo *files;
static size_t nfiles;
static size_t files_index;

/* The line length to use for breaking lines in many-per-line format.
   Can be set with -w.  */

static size_t line_length;

/* Option flags */

/*
   many_per_line for just names, many per line, sorted vertically.
   horizontal for just names, many per line, sorted horizontally.
   */

enum format
  {
    many_per_line,		/* -C */
    horizontal,			/* -x */
  };

static enum format format;

/* The number of chars per hardware tab stop.  Setting this to zero
   inhibits the use of TAB characters for separating columns.  -T */
static size_t tabsize;

/* Nonzero if a non-fatal error has occurred.  */
static int exit_status;

/* Information about filling a column.  */
struct column_info
{
  int valid_len;
  size_t line_len;
  size_t *col_arr;
};

/* Array with information about column filledness.  */
static struct column_info *column_info;

/* Maximum number of columns ever possible for this display.  */
static size_t max_idx;

/* The minimum width of a colum is 3: 1 character for the name and 2
   for the separating white space.  */
#define MIN_COLUMN_WIDTH	3

/* An array of file handles */
FILE *inputfile, **inputfiles;
size_t ninputs;
size_t inputindex;

/* Expandable argument list */
char **myargv;
size_t myargc;
size_t nargs;

int
insert_arg (char *arg, size_t index)
{
  int i;

  if (index > myargc)
    return (-1);
  myargc++;
  if (myargc > nargs)
    {
      myargv = realloc (myargv, 2 * nargs * sizeof *myargv);
      nargs *= 2;
    }
  for (i = index; i < myargc; i++)
    {
      char *temp;
      temp = myargv[i];
      myargv[i] = arg;
      arg = temp;
    }
  return (myargc);
}



void
dump_myargs ()
{
  int i;
  for (i=0; i<myargc; i++)
    printf ("%s ", myargv[i]);
  printf ("\n");
}



int
main (int argc, char **argv)
{
  char line[512];

  program_name = argv[0];
  exit_status = 0;
  tabsize = 0;
  format = many_per_line;
  line_length = 0;

  /* The following options should be supported, as with ls :
     -C : columnar format (default)
     -x : horizontal format
     -w, --width= : set line length, overriding env variable COLUMNS
     -T, --tabsize=: set tab size
  */

  ninputs=10;
  inputindex=0;
  inputfiles = malloc (ninputs * sizeof *inputfiles);

  /* copy arguments to expandable list */

  nargs = 20;
  myargc = 0;
  myargv = malloc (nargs * sizeof *myargv);
  int i; 
  for (i = 0; i < argc; i++)
    insert_arg (argv[i], myargc);

  i=1; 
  while (i<myargc)
    {
      if (strcmp ("-h", myargv[i]) == 0 || strcmp ("--help", myargv[i]) == 0)
	{
	  usage();
	  exit (0);
	}
      else if (strcmp ("-v", myargv[i]) == 0 || strcmp ("--version", myargv[i]) == 0)
	{
	  version();
	  exit (0);
	}
      else if (strcmp ("-C", myargv[i]) == 0)
	format = many_per_line;
      else if (strcmp ("-x", myargv[i]) == 0)
	format = horizontal;
      else if (strcmp ("-w", myargv[i]) == 0)
	{
	  if (i<myargc-1) 
	    {
	      i++;
	      unsigned long int tmp_ulong;
	      tmp_ulong = strtoul (myargv[i], NULL, 10);
	      if (0 < tmp_ulong && tmp_ulong <= SIZE_MAX)
		{
		  line_length = tmp_ulong;
		}
	      else
		{
		  fprintf (stderr,
			   "cols: ignoring invalid width: %s\n", myargv[i]);
		  i--;
		}
	    }
	  else
	    {
	      fprintf (stderr,
		       "cols: no argument supplied for -w\n");
	    }
	}

      else if (strncmp ("--width=", myargv[i], 8) == 0)
	{
	  unsigned long int tmp_ulong;
	  char *width = myargv[i]+8;
	  tmp_ulong = strtoul (width, NULL, 10);
	  if (0 < tmp_ulong && tmp_ulong <= SIZE_MAX)
	  {
	    line_length = tmp_ulong;
	  }
	  else
	  {
	    fprintf (stderr,
    	  	     "cols: ignoring invalid width: %s\n", width);
	  }
	}

      else if (strcmp ("-T", myargv[i]) == 0)
	{
	  if (i<myargc-1) 
	    {
	      i++;
	      unsigned long int tmp_ulong;
	      tmp_ulong = strtoul (myargv[i], NULL, 10);
	      if (0 < tmp_ulong && tmp_ulong <= SIZE_MAX)
		{
		  tabsize = tmp_ulong;
		}
	      else
		{
		  fprintf (stderr,
			   "cols: ignoring invalid tab size: %s\n", myargv[i]);
		  i--;
		}
	    }
	  else
	    {
	      fprintf (stderr,
		       "col: no argument supplied for -T\n");
	    }
	}

      else if (strncmp ("--tabsize=", myargv[i], 10) == 0)
	{
	  unsigned long int tmp_ulong;
	  char *tab = myargv[i]+10;
	  tmp_ulong = strtoul (tab, NULL, 10);
	  if (0 < tmp_ulong && tmp_ulong <= SIZE_MAX)
	    {
	      tabsize = tmp_ulong;
	    }
	  else
	    {
	      fprintf (stderr,
		       "cols: ignoring invalid tab size: %s\n", tab);
	    }
	}

      else if (strncmp ("-", myargv[i], 1) == 0 && strlen (myargv[i]) > 2)
	{
	  /* blindly expand grouped options to individual options */
	  int j = i + 1;
	  int k = 1;
	  while (k < strlen (myargv[i]))
	    {
	      int c = *(myargv[i]+k);
	      char *arg = malloc (3 * sizeof *arg);
	      *(arg) = '-';
	      *(arg+1) = c;
	      *(arg+2) = '\0';
	      insert_arg (arg, j);
	      /*dump_myargs();*/
	      j++;
	      k++;
	    }
	}

      else /* anything else is taken as a file */
	{
	  inputfile = fopen (myargv[i], "r");
	  if (inputfile==NULL)
	    {
	      fprintf (stderr,
		       "cols: could not open file %s for reading\n", myargv[i]);
	      exit (1);
	    }
	  else
	    {
	      if (inputindex == ninputs)
		{
		  inputfiles = realloc (inputfiles, 2 * ninputs * sizeof *inputfiles);
		  ninputs *= 2;
		}
	      inputfiles[inputindex++] = inputfile;
	    }
	}

      i++;
    }

  if (line_length == 0)
    {
      line_length = 80;
      char const *p = getenv ("COLUMNS");
      if (p && *p)
	{
	  unsigned long int tmp_ulong;
	  tmp_ulong = strtoul (p, NULL, 10);
	  if (0 < tmp_ulong && tmp_ulong <= SIZE_MAX)
	    {
	      line_length = tmp_ulong;
	    }
	  else
	    {
	      fprintf (stderr,
		       "cols: ignoring invalid width in environment variable COLUMNS: %s", p);
	    }
	}
#ifdef TIOCGWINSZ
      {
	struct winsize ws;
    
	if (ioctl (STDOUT_FILENO, TIOCGWINSZ, &ws) != -1
	    && 0 < ws.ws_col /* && ws.ws_col <= SIZE_MAX */ )
	  {
	    line_length = ws.ws_col;
	  }
      }
#endif
    }

  if (inputindex == 0)
    {
      inputfiles[inputindex++] = stdin;
    }

  max_idx = MAX(1, line_length / MIN_COLUMN_WIDTH);

  nfiles = 100;
  files = calloc (nfiles, sizeof *files);
  /*files = xnmalloc (nfiles, sizeof *files);*/
  files_index = 0;

  for (i=0; i<inputindex; i++)
    {
      while (fgets(line, 512, inputfiles[i]) != NULL)
	{
	  gobble_file(line);
	}
      fclose (inputfiles[i]);
    }

  if (files_index)
    {
      print_current_files ();
    }

  exit (exit_status);
}

/* Empty the table of files. */

static void
clear_files (void)
{
  register size_t i;

  for (i = 0; i < files_index; i++)
    {
      free (files[i].name);
    }

  files_index = 0;
}


static void
gobble_file (const char *name)
{
  register struct fileinfo *f;

  if (files_index == nfiles)
    {
      files = (struct fileinfo *) realloc (files, 2 * nfiles * sizeof *files);
      /*files = xnrealloc (files, nfiles, 2 * sizeof *files);*/
      nfiles *= 2;
    }

  f = &files[files_index];
  f->name = malloc (strlen(name));
  memset (f->name, 0, strlen(name));
  strncpy (f->name, name, strlen(name)-1);
  files_index++;
}



/* List all the files now in the table.  */

static void
print_current_files (void)
{
  register size_t i;

  switch (format)
    {
    case many_per_line:
      print_many_per_line ();
      break;

    case horizontal:
      print_horizontal ();
      break;
    }
}


/* Print the file name of `f' */

static void
print_file_name_and_frills (const struct fileinfo *f)
{
  printf(f->name);
}

static size_t
length_of_file_name_and_frills (const struct fileinfo *f)
{
  return strlen(f->name);
}

static void
print_many_per_line (void)
{
  size_t row;			/* Current row. */
  size_t cols = calculate_columns (true);
  struct column_info const *line_fmt = &column_info[cols - 1];

  /* Calculate the number of rows that will be in each column except possibly
     for a short column on the right. */
  size_t rows = files_index / cols + (files_index % cols != 0);

  for (row = 0; row < rows; row++)
    {
      size_t col = 0;
      size_t filesno = row;
      size_t pos = 0;

      /* Print the next row.  */
      while (1)
	{
	  size_t name_length = length_of_file_name_and_frills (files + filesno);
	  size_t max_name_length = line_fmt->col_arr[col++];
	  print_file_name_and_frills (files + filesno);

	  filesno += rows;
	  if (filesno >= files_index)
	    break;

	  indent (pos + name_length, pos + max_name_length);
	  pos += max_name_length;
	}
      putchar ('\n');
    }
}

static void
print_horizontal (void)
{
  size_t filesno;
  size_t pos = 0;
  size_t cols = calculate_columns (false);
  struct column_info const *line_fmt = &column_info[cols - 1];
  size_t name_length = length_of_file_name_and_frills (files);
  size_t max_name_length = line_fmt->col_arr[0];

  /* Print first entry.  */
  print_file_name_and_frills (files);

  /* Now the rest.  */
  for (filesno = 1; filesno < files_index; ++filesno)
    {
      size_t col = filesno % cols;

      if (col == 0)
	{
	  putchar ('\n');
	  pos = 0;
	}
      else
	{
	  indent (pos + name_length, pos + max_name_length);
	  pos += max_name_length;
	}

      print_file_name_and_frills (files + filesno);

      name_length = length_of_file_name_and_frills (files + filesno);
      max_name_length = line_fmt->col_arr[col];
    }
  putchar ('\n');
}

/* Assuming cursor is at position FROM, indent up to position TO.
   Use a TAB character instead of two or more spaces whenever possible.  */

static void
indent (size_t from, size_t to)
{
  while (from < to)
    {
      if (tabsize != 0 && to / tabsize > (from + 1) / tabsize)
	{
	  putchar ('\t');
	  from += tabsize - from % tabsize;
	}
      else
	{
	  putchar (' ');
	  from++;
	}
    }
}

/* Allocate enough column info suitable for the current number of
   files and display columns, and initialize the info to represent the
   narrowest possible columns.  */

static void
init_column_info (void)
{
  size_t i;
  size_t max_cols = MIN(max_idx, files_index);

  /* Currently allocated columns in column_info.  */
  static size_t column_info_alloc;

  if (column_info_alloc < max_cols)
    {
      size_t new_column_info_alloc;
      size_t *p;

      if (max_cols < max_idx / 2)
	{
	  /* The number of columns is far less than the display width
	     allows.  Grow the allocation, but only so that it's
	     double the current requirements.  If the display is
	     extremely wide, this avoids allocating a lot of memory
	     that is never needed.  */
	  /*column_info = xnrealloc (column_info, max_cols,
	    2 * sizeof *column_info);*/
	  column_info = realloc (column_info, max_cols *
				   2 * sizeof *column_info);
	  new_column_info_alloc = 2 * max_cols;
	}
      else
	{
	  column_info = realloc (column_info, max_idx * sizeof *column_info);
	  new_column_info_alloc = max_idx;
	}

      /* Allocate the new size_t objects by computing the triangle
	 formula n * (n + 1) / 2, except that we don't need to
	 allocate the part of the triangle that we've already
	 allocated.  Check for address arithmetic overflow.  */
      {
	size_t column_info_growth = new_column_info_alloc - column_info_alloc;
	size_t s = column_info_alloc + 1 + new_column_info_alloc;
	size_t t = s * column_info_growth;
	if (s < new_column_info_alloc || t / column_info_growth != s)
	  {
  	    /*xalloc_die ();*/
            fprintf (stderr, "cols: Malloc fatal error");
	    exit (1);
	  }
	p = calloc (t / 2, sizeof *p);
	/*p = xnmalloc (t / 2, sizeof *p);*/
      }

      /* Grow the triangle by parceling out the cells just allocated.  */
      for (i = column_info_alloc; i < new_column_info_alloc; i++)
	{
	  column_info[i].col_arr = p;
	  p += i + 1;
	}

      column_info_alloc = new_column_info_alloc;
    }

  for (i = 0; i < max_cols; ++i)
    {
      size_t j;

      column_info[i].valid_len = true;
      column_info[i].line_len = (i + 1) * MIN_COLUMN_WIDTH;
      for (j = 0; j <= i; ++j)
	column_info[i].col_arr[j] = MIN_COLUMN_WIDTH;
    }
}

/* Calculate the number of columns needed to represent the current set
   of files in the current display width.  */

static size_t
calculate_columns (int by_columns)
{
  size_t filesno;		/* Index into files. */
  size_t cols;			/* Number of files across. */

  /* Normally the maximum number of columns is determined by the
     screen width.  But if few files are available this might limit it
     as well.  */
  size_t max_cols = MIN(max_idx, files_index);

  init_column_info ();

  /* Compute the maximum number of possible columns.  */
  for (filesno = 0; filesno < files_index; ++filesno)
    {
      size_t name_length = length_of_file_name_and_frills (files + filesno);
      size_t i;

      for (i = 0; i < max_cols; ++i)
	{
	  if (column_info[i].valid_len)
	    {
	      size_t idx = (by_columns
			    ? filesno / ((files_index + i) / (i + 1))
			    : filesno % (i + 1));
	      size_t real_length = name_length + (idx == i ? 0 : 2);

	      if (column_info[i].col_arr[idx] < real_length)
		{
		  column_info[i].line_len += (real_length
					      - column_info[i].col_arr[idx]);
		  column_info[i].col_arr[idx] = real_length;
		  column_info[i].valid_len = (column_info[i].line_len
					      < line_length);
		}
	    }
	}
    }

  /* Find maximum allowed columns.  */
  for (cols = max_cols; 1 < cols; --cols)
    {
      if (column_info[cols - 1].valid_len)
	break;
    }

  return cols;
}
 
void
usage ()
{
      printf ("Usage: %s [OPTION]... [FILE]...\n", program_name);
      fputs ("\
Displays standard input or files in columnar format.\n\
\n\
", stdout);
      fputs ("\
Mandatory arguments to long options are mandatory for short options too.\n\
", stdout);
      fputs ("\
  -C                         list entries by columns\n\
", stdout);
      fputs ("\
  -T, --tabsize=COLS         assume tab stops at each COLS instead of 8\n\
", stdout);
      fputs ("\
  -w, --width=COLS           assume screen width instead of current value\n\
  -x                         list entries by lines instead of by columns\n\
", stdout);
}


void
version()
{
  fputs ("\
cols 1.0\n\
\n\
Copyright (C) 2005 Free Software Foundation, Inc.\n\
  This is free software; see the source for copying conditions.  There is NO\n\
  warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n",
  stdout);
}