/* 

    The Sorting routines live here.
    I used the quick sort algorithm as implimemted by Manx to sort a
    list of indices, and then I rearranged the data to conform to the
    sorted list. In order to do the sort, there must be one free element
    available in the array.

    Written by Steve (Raz) Berry.

    1/8/89
*/

#include "flist.h"
#include <libraries/arpbase.h>

extern long (*finfo[MAXDIR])[4];  
extern char (*fname[MAXDIR])[FCHARS];
extern char (*comm[MAXDIR])[FCHARS];
extern char (*fstring[MAXDIR])[LEN_DATSTRING];
extern char (*ftime[MAXDIR])[LEN_DATSTRING];
extern long numfiles, top, row, line;
extern struct AnchorPath *ap;
extern char strbuf[256];

extern void swap();
long lastsort = -1;

sort(which)
int which;
{
    if (numfiles > MAXDIR -1) {
        auto_req("Can't sort list - No space");
        return;
    }

    switch (which) {
        case 0:
            sortname();
            lastsort = 0;
            break;
        case 1:
            sortsize();
            lastsort = 1;
            break;
        case 2:
            sortdate();
            lastsort = 2;
            break;
        case 3:
            sortpattern();
            break;
        case 4:
            sortday();
            lastsort = 4;
            break;
    }
}

cmp(s1,s2)
long *s1, *s2;
{
    return Strcmp(fname[*s1], fname[*s2]);
}

sortname()
{
    long list[MAXDIR];
    register long i;

    for (i = 0;i<numfiles;i++)
        list[i] = i;

    qsort(list, numfiles, 4L, cmp);

    sortme(list);
}

cmp1(s1,s2)
long *s1,*s2;  
{
    return ((*finfo[*s1])[2] > (*finfo[*s2])[2]) ? 1 : 
           ((*finfo[*s1])[2] < (*finfo[*s2])[2]) ? -1 : 0;
}

sortsize()
{
    long list[MAXDIR];
    register long i;

    for (i = 0;i < numfiles;i++)
        list[i] = i;

    qsort(list, numfiles, 4L, cmp1);

    sortme(list);
}

cmp2(s1,s2)
long *s1, *s2;
{
    return Strcmp(ftime[*s1], ftime[*s2]);
}

sortdate()
{
    long list[MAXDIR]; 
    register long i;
    
    for (i = 0;i < numfiles;i++)
        list[i] = i;

    qsort(list, numfiles, 4L, cmp2);

    sortme(list);
}

cmp3(s1,s2)
long *s1, *s2;
{
    return Strcmp(fstring[*s1], fstring[*s2]);
}

sortday()
{
    long list[MAXDIR]; 
    register long i;
    
    for (i = 0;i < numfiles;i++)
        list[i] = i;

    qsort(list, numfiles, 4L, cmp3);

    sortme(list);
}

/* 
    Here we sort by pattern... actually we just reget the directory based
    on the input string.
*/

long sortpattern()
{
    char buf[256];
	struct Window *strptr;
    long rc;

    strbuf[0] = '\0';
    strptr = make_gadget("Enter search Pattern");

    if (strptr == NULL) {
        auto_req("Couldn't open Requestor!");
        return BAD_COMMAND;
    }

    drawcur();

    wait_for_event(strptr);

    blankcur();

    if (strbuf[0] == '\0')
        return NULL;

    rc = FindFirst(strbuf,ap);

    if (rc == NULL){
        Fillarray();    /* fill the arrays with the names and info */
        top = 0;
        row = 0;    
        line = 0;
    }
    else {
        if (rc != ERROR_NO_MORE_ENTRIES){
            sprintf(buf,"Bad pattern -%s- !",strbuf);
            auto_req(buf);
            FindFirst("*",ap);
            Fillarray();
            top = 0;
            row = 0;    
            line = 0;
        } else
            numfiles = 0;
    }

    return rc;
}

/*  Here's the deal... Now that I have the list of indices all sorted,
    I figured that arranging the list to match the indices would be
    simple. WRONG. This was the hardest part by far. Next time I will
    arrange my arrays as structures and sort them in place.
    I'll probably also use a Heapsort routine 
    (it's a better general purpose routine) as well. */

/* More sorting for the resultant list */

find(index, list)
long list[MAXDIR];
{
    register long i;
#ifdef DEBUG
    if (index <0){
        auto_req("index of -1!");
        return 0;
    }
#endif
    for (i=0;index != list[i];i++);

    return i;
}

swapall(one, two)
long one, two;
{
    swap(&finfo[one], &finfo[two]);
    swap(&fname[one], &fname[two]);
    swap(&comm[one], &comm[two]);
    swap(&fstring[one], &fstring[two]);
    swap(&ftime[one], &ftime[two]);
}

/* This routine actually rearanges the list into the proper order */

sortme(list)
long list[MAXDIR];
{
    register long sa, pos, i;
    long first = -1,index;

    sa = numfiles;
    index = 0;

    while(1) {

        for(i=0;((list[i] == -1) || (list[i] == i)) && (i < numfiles);i++);

        if (i >= numfiles)
            break;
        index = i;
        first = -1;

        for (i=0;i<numfiles;i++) {      /* prime the pipe */
            pos = find(index, list);
            if (pos != index) {
                if (first == -1)
                    first = index;
                swapall(index, pos);
                swapall(index, sa);
                list[pos] = -1;
                index = pos;
            } else
                list[index++] = -1;
            if (first != -1)
                break;
        }

        for (i=0;pos != first;i++) {    /* follow the thread to the end */
            pos = find(index, list);
            swapall(sa, pos);
            list[pos] = -1;
            index = pos;
        }
    }
}