#include <u.h>
#include <libc.h>
#include <bio.h>
#include <draw.h>
#include <fcall.h>

struct dir_entry {
    char *filename;
    char *qfilename;
    int rlen;
    Dir *d;
};

struct dir_block {
    char *dir_name;
    Dir *dirs;
    int n_entries, alc_entries;
    struct dir_entry **entries;
};

#define CMP(x,y) ( (x) == (y) ? 0 : ( (x) < (y) ? -1 : 1) )

#define GUTTER 2

#define USAGE "usage: l [-cdflmnqQrRsStTu1] [file ...]"

void exit(char *fmt,...);
int out(char *fmt, ...);
void perform_arg(char *s, struct dir_block *b);
void init_dir_block(struct dir_block *b, char *s);
void add_dir_entry(struct dir_block *b, Dir *d, char *name);
void perform_dir(char *s);
void print_dir_block(struct dir_block *b);
void print_name(struct dir_entry *e);
void print_columnar_dir_block(struct dir_block *b);
int compute_max_cols(struct dir_block *b);
int compute_rows(struct dir_block *b, int cols);
int compute_total_width(struct dir_block *b, int rows, int cols);
int get_width(struct dir_block *b, int rows, int cols, int n);
void print_columnar(struct dir_block *b, int rows, int cols);
char* colour(struct dir_entry *d);
int nrunes(char *s);
void format_dir_entry(struct dir_entry *);
char* asciitime(long);
void do_widths(Dir*);
int get_screen_width(void);
void free_dir_block(struct dir_block *b) ;
int strcasecmp (const char *s1, const char *s2);
void help(void);

typedef int bool;
#define TRUE 1
#define FALSE 0

bool    header;   /* print headers or not */
bool    sub_dir;  /* whether sub directory printed or not */
bool	dflag;    /* List directory, not its contents. */
bool	lflag;    /* List in long format */
bool	fflag;    /* List file names with directory path */
bool	mflag;    /* List the name of the user who most recently modified the file */
bool	nflag;    /* Don't sort the listing. */
bool	qflag;    /* List the qid (see stat(2)) of each file */
bool	Qflag;    /* Don't put quotes around file names which contain special chars */
bool	Sflag;    /* Sort by file size */
bool	rflag;    /* Reverse the order of sort. */
bool	sflag;    /* Give size in Kbytes for each entry. */
bool	tflag;    /* Sort by time modified */
bool	Tflag;    /* Print the character t before each file if it has the temporary flag set */
bool	uflag;    /* Under -t sort by time of last access; under -l print time of last access. */
bool    oneFlag;  /* List one file per line */
bool    cflag;    /* Force console mode output (columns and colours) */
bool    Rflag;    /* Recursively list sub-directories */

ulong	clk;

int     screen_width;
int	swidth;			/* max width of -s size */
int	qwidth;			/* max width of -q version */
int	vwidth;			/* max width of dev */
int	uwidth;			/* max width of userid */
int	mwidth;			/* max width of muid */
int	lwidth;			/* max width of length */
int	gwidth;			/* max width of groupid */
Biobuf	bin;
char    *reset;

void
main(int argc, char *argv[])
{
    int i;
    struct dir_block b;
    char outpath[128];

    Binit(&bin, 1, OWRITE);
    ARGBEGIN{
	case 'd':	dflag++; break;
	case 'l':	lflag++; break;
	case 'f':	fflag++; break;
	case 'm':	mflag++; break;
	case 'n':	nflag++; break;
	case 'q':	qflag++; break;
	case 'Q':	Qflag++; break;
	case 'r':	rflag++; break;
	case 's':	sflag++; break;
	case 'S':	Sflag++; break;
	case 't':	tflag++; break;
	case 'T':	Tflag++; break;
	case 'u':	uflag++; break;
	case '1':	oneFlag++; break;
	case 'R':	Rflag++; break;
	case 'c':	cflag++; break;
        case '?':	help(); break;
	default:	exit(USAGE "\n       try l -? for option help");
    }ARGEND

    if ((fd2path(1, outpath, sizeof outpath)) == 0) {
        int l;
        l = strlen(outpath);
        if (l >= 5 && strcmp(outpath + l - 5, "/cons") == 0)
            ++cflag;
    }

    quotefmtinstall();
    fmtinstall('M', dirmodefmt);
    clk = time(0);
    if (cflag) {
        screen_width = get_screen_width();
        if (screen_width < 0)
            screen_width = 80;
        reset = "\033[m";
    } else
        reset = "";
    
    init_dir_block(&b, nil);

    if ((argc > 1 || Rflag) && !(fflag && oneFlag))
        header = TRUE;

    if (argc > 0) {
        for (i = 0; i < argc; ++i) {
            perform_arg(argv[i], &b);
        }         
    } else {
        perform_arg(".", &b);
    }

    print_dir_block(&b);
    free_dir_block(&b);

    exits(0);
}

void
perform_arg(char *s, struct dir_block *b)
{
    Dir *st;

    if (!(st = dirstat(s)))
        exit("Couldn't stat %s: %r", s);

    if (st->mode & DMDIR) {
       if (dflag)
           add_dir_entry(b, st, s);
       else
           perform_dir(s);
   } else {
        if (!fflag) {
            char *p;
            p = strrchr(s, '/');
            if (p)
                s = p + 1;
        }
        add_dir_entry(b, st, s);
   }
}

void
help()
{
    print(USAGE "\nList directory contents.\n");
    print("-c   Force console mode output (columns and colours).\n");
    print("-d   List directory, not its contents.\n");
    print("-f   List file names with directory path.\n");
    print("-l   List in long format.\n");
    print("-m   List the name of the user who most recently modified the file.\n");
    print("-n   Don't sort the listing.\n");
    print("-q   List the qid (see stat(2)) of each file.\n");
    print("-Q   Don't put quotes around file names which contain special chars.\n");
    print("-r   Reverse the order of sort.\n");
    print("-R   Recursively list sub-directories.\n");
    print("-s   Give size in Kbytes for each entry.\n");
    print("-S   Sort by file size.\n");
    print("-t   Sort by time modified.\n");
    print("-T   Print the character t before each file if it has the temporary flag set.\n");
    print("-u   Under -t, sort by time of last access; under -l print time of last access.\n");
    print("-1   List one file per line.\n");
    exits(0);
}

void
exit(char *fmt,...)
{
    va_list ap;
    Bflush(&bin);
    va_start(ap, fmt);
    vfprint(2, fmt, ap);
    va_end(ap);
    fprint(2, "\n");
    exits("errors");
}

int
out(char *fmt, ...)
{
    int i;
    va_list ap;
    va_start(ap, fmt);
    i = Bvprint(&bin, fmt, ap);
    va_end(ap);
    return i;
}

void
perform_dir(char *s)
{
    struct dir_block b;
    Dir *st;
    int fd;
    long n, i;

    init_dir_block(&b, s);

    fd = open(s, OREAD);
    if (fd < 0)
        exit("Couldn't open %s: %r", s);
    n = dirreadall(fd, &st);
    close(fd);
    if (n < 0)
        exit("Couldn't read dir %s: %r", s);
    b.dirs = st;

    for (i = 0; i < n; ++i) {
        char *t;
        if (s[strlen(s) - 1] == '/')
            t = smprint("%s%s", s, st[i].name);
        else
            t = smprint("%s/%s", s, st[i].name);
        if (fflag)
            add_dir_entry(&b, st + i, t);
        else
            add_dir_entry(&b, st + i, st[i].name);
        if (Rflag && (st[i].mode & DMDIR))
            perform_dir(t);
        free(t);
    }
    print_dir_block(&b);
    free_dir_block(&b);
}

void
init_dir_block(struct dir_block *b, char *s)
{
   b->dir_name = s;
   b->n_entries = 0;
   b->alc_entries = 0;
   b->entries = nil;
   b->dirs = nil;
}

int
nrunes(char *s)
{
    Rune r;
    int i = 0;
    while (*s) {
        s += chartorune(&r, s);
        ++i;
    }
    return i;
}

void
add_dir_entry(struct dir_block *b, Dir *d, char *name)
{
    struct dir_entry *e;
    if (b->alc_entries == b->n_entries) {
        struct dir_entry **p;
        b->alc_entries += 100;
        if ((p = realloc(b->entries, b->alc_entries * sizeof(Dir *))) == nil)
            exit("couldn't realloc memory");
        b->entries = p;
    }
    if ((e = malloc(sizeof(struct dir_entry))) == nil)
        exit("couldn't alloc memory");
    e->d = d;
    e->filename = strdup(name);
    if (Qflag)
        e->qfilename = e->filename;
    else
        e->qfilename = quotestrdup(name);
    e->rlen = nrunes(e->qfilename);
    b->entries[b->n_entries++] = e;
}

void
free_dir_block(struct dir_block *b) 
{
   int i;
   free(b->dirs);
   for (i = 0; i < b->n_entries; ++i) {
      free(b->entries[i]->filename);
      if (!Qflag)
          free(b->entries[i]->qfilename);
      free(b->entries[i]);
   }
   free(b->entries);
}

int
comp(void *elem1, void *elem2)
{
    int i;
    struct dir_entry *x, *y;

    x = *((struct dir_entry **)elem1);
    y = *((struct dir_entry **)elem2);

    if (tflag) {
        if (uflag)
            i = CMP(y->d->atime, x->d->atime);
        else
            i = CMP(y->d->mtime, x->d->mtime);
        if (i == 0)
            i = strcasecmp(x->filename, y->filename);
    } else if (Sflag) {
        i = CMP(y->d->length, x->d->length);
        if (i == 0)
            i = strcasecmp(x->filename, y->filename);
    } else
        i = strcasecmp(x->filename, y->filename);

    if (i == 0)
        i = CMP(x->d, y->d);

    if (rflag)
        i = -i;
    return i;
}

void
print_dir_block(struct dir_block *b)
{
    if (header) {
        if (b->dir_name) {
            if (sub_dir)
                out("\n");
            out("Directory of %s\n", b->dir_name);
            sub_dir = TRUE;
        } else {
            if (b->n_entries > 0 && sub_dir)
                out("\n-----\n");
        }
    }
    if (!nflag)
        qsort(b->entries, b->n_entries, sizeof(struct dir_entry *), comp); 

    if (!cflag || oneFlag || sflag || Tflag || qflag || mflag || lflag) {
        int i;
        swidth = qwidth = mwidth = vwidth = uwidth = gwidth = lwidth = 0;
        for (i = 0; i < b->n_entries; ++i)
            do_widths(b->entries[i]->d);
        for (i = 0; i < b->n_entries; ++i)
            format_dir_entry(b->entries[i]);
    } else
        print_columnar_dir_block(b);
}

char*
colour(struct dir_entry *e)
{
    if (!cflag)
        return "";
    if (e->d->mode & DMDIR)
        return "\033[35m";
    else if (e->d->mode & 0100)
        return "\033[32m";
    return "\033[m";
}

void
print_columnar_dir_block(struct dir_block *b)
{
    int r, c;

    c = compute_max_cols(b);
    r = compute_rows(b, c);

    print_columnar(b, r, c);
}

void
print_columnar(struct dir_block *b, int rows, int cols) 
{
    int i, j, k, *w, size = b->n_entries;

    if (cols == 0)
        return;

    if ((w = malloc(cols * sizeof(int))) == nil)
        exit("couldn't alloc memory");

    for (i = 0; i < cols - 1; ++i)
        w[i] = get_width(b, rows, cols, i) + GUTTER;

    for (i = 0; i < rows; ++i) {
        for (j = 0;; ++j) {
            struct dir_entry *d;
            k = i + j*rows;
            d = b->entries[k];
            /* Check for end of line.  Note that if j=cols-1 then
             * k + rows = i + rows*cols >= size so in the first
             * branch, j < cols-1
             */
            if (k + rows < size)
                out("%s%-*s%s", colour(d), w[j], d->qfilename, reset);
            else {
                out("%s%s%s\n", colour(d), d->qfilename, reset);
                break;
            }
        }
    }

    free(w);
}

int
compute_max_cols(struct dir_block *b) 
{
    int cols, best, size = b->n_entries;
    
    if (size < 2) 
        return size;

    cols = 2;
    best = 1;
    while (cols <= size) {
        int rows = compute_rows(b, cols);

        if (rows > 0) {
            int w = compute_total_width(b, rows, cols);
            if (w > screen_width)
                break;
            best = cols;
        }
        ++cols;
    }
    return best;
}

int
compute_rows(struct dir_block *b, int cols) 
{
    int rows, size = b->n_entries;

    if (cols < 2)
        return size;

    rows = size / cols;
    if (size % cols != 0)
        ++rows;

    /* Check if the end of the first row is in range... if not
     * then these dimensions don't fit (eg 49 in 8 columns doesn't
     * fit - the last column would be empty).
     */
    if (rows * (cols-1) >= size)
        return -1;

    return rows;
}

int
compute_total_width(struct dir_block *b, int rows, int cols) 
{
    int i, w = GUTTER * (cols-1);
    for (i = 0; i < cols; ++i) {
        w += get_width(b, rows, cols, i);
    }
    return w;
}

/* The width of column n */
int
get_width(struct dir_block *b, int rows, int cols, int n) 
{
    int i, t, w=0,
        size = b->n_entries,
        start = n*rows,
        end = (n == cols-1 ? size:start+rows);

    for (i = start; i < end; ++i) {
        t = b->entries[i]->rlen;
        if (t > w)
            w = t;
    }

    return w;
}

void
do_widths(Dir *db)
{
    char buf[256];
    int n;

    if (sflag) {
        n = sprint(buf, "%llud", (db->length+1023)/1024);
        if (n > swidth)
            swidth = n;
    }
    if (qflag) {
        n = sprint(buf, "%lud", db->qid.vers);
        if (n > qwidth)
            qwidth = n;
    }
    if (mflag) {
        snprint(buf, sizeof buf, "[%q]", db->muid);
        n = nrunes(buf);
        if (n > mwidth)
            mwidth = n;
    }
    if (lflag) {
        n = sprint(buf, "%ud", db->dev);
        if (n > vwidth)
            vwidth = n;
        snprint(buf, sizeof buf, "%q", db->uid);
        n = nrunes(buf);
        if (n > uwidth)
            uwidth = n;
        snprint(buf, sizeof buf, "%q", db->gid);
        n = nrunes(buf);
        if (n > gwidth)
            gwidth = n;
        n = sprint(buf, "%llud", db->length);
        if (n > lwidth)
            lwidth = n;
    }
}

void
format_dir_entry(struct dir_entry *e)
{
    int i;
    Dir *db;

    db = e->d;

    if (sflag)
        out("%*llud ",
               swidth, (db->length+1023)/1024);
    if (mflag){
        int n;
        n = out("[%q] ", db->muid) - 1;
        for(i = 0; i < mwidth - n; i++)
            out(" ");
    }
    if (qflag)
        out("(%.16llux %*lud %.2ux) ",
               db->qid.path,
               qwidth, db->qid.vers,
               db->qid.type);
    if (Tflag)
        out("%c ", (db->mode&DMTMP)? 't': '-');

    if (lflag)
        out("%M %C %*ud %*q %*q %*llud %s ",
               db->mode, db->type,
               vwidth, db->dev,
               -uwidth, db->uid,
               -gwidth, db->gid,
               lwidth, db->length,
               asciitime(uflag? db->atime: db->mtime));
    out("%s%s%s\n", colour(e), e->qfilename, reset);
}

char*
asciitime(long l)
{
    static char buf[32];
    char *t;

    t = ctime(l);
    /* 6 months in the past or a day in the future */
    if (l<clk-180L*24*60*60 || clk+24L*60*60<l){
        memmove(buf, t+4, 7);		/* month and day */
        memmove(buf+7, t+23, 5);		/* year */
    }else
        memmove(buf, t+4, 12);		/* skip day of week */
    buf[12] = 0;
    return buf;
}

int
strcasecmp(const char *s1, const char *s2)
{
    int j;
    while (1) {
        j = tolower((unsigned char)*s1) - tolower((unsigned char)*s2);
        if (j) 
            return j;
        if (*s1 == '\0') 
            break;
        s1++; s2++;
    }
    return 0;
}

int
get_screen_width(void)
{
    int n, fd, wm;
    char *wdir, winfile[128], buf[128], *f[10], *p;
    Font *font = 0;
    int linewidth;
    
    if (access("/dev/acme", OREAD) >= 0){
        if ((fd = open("/dev/acme/ctl", OREAD)) < 0)
            return -1;
        n = read(fd, buf, sizeof buf-1);
        close(fd);
        if (n <= 0)
            return -1;
        buf[n] = 0;
        n = tokenize(buf, f, nelem(f));
        if (n < 7)
            return -1;
        if ((font = openfont(nil, f[6])) == nil)
            return -1;
        linewidth = atoi(f[5]);
    } else {
        if ((wdir = getenv("wdir")) == nil)
            wdir = "/dev";

        /* Try the wininfo file first; failing that use the window image file */
        snprint(winfile, sizeof(winfile), "%s/wininfo", wdir);
        if ((fd = open(winfile, OREAD)) < 0){
            snprint(winfile, sizeof(winfile), "%s/window", wdir);
            if ((fd = open(winfile, OREAD)) < 0)
                return -1;
            /* Skip over pixel format string */
            read(fd, buf, 12);
        }

        /* Window rectangle is 4 12-char fields. */
        n = read(fd, buf, 48);
        close(fd);
        if (n < 48)
            return -1;
        buf[48] = 0;
        n = tokenize(buf, f, nelem(f));
        if (n != 4)
            return -1;

        if ((p = getenv("font")) == nil)
            return -1;
        if ((font = openfont(nil, p)) == nil)
            return -1;

        /*
         *  the text area in a riox window is 18 pixels less than the enclosing window, after deducting the borders.
         */
        linewidth = atoi(f[2]) - atoi(f[0]) - (2*Borderwidth + 18);
    }

    wm = stringnwidth(font, "M", 1);
    freefont(font);

    return linewidth / wm;
}