/***********************************************************************/
/* Open Visualization Data Explorer                                    */
/* (C) Copyright IBM Corp. 1989,1999                                   */
/* ALL RIGHTS RESERVED                                                 */
/* This code licensed under the                                        */
/*    "IBM PUBLIC LICENSE - Open Visualization Data Explorer"          */
/***********************************************************************/

#include <dxconfig.h>


#include <dx/dx.h>

#define SORT_ASCENDING	0
#define SORT_DESCENDING	1

static Object SortObject(Object o, int flag);

m_Sort(Object *in, Object *out)
{
    int   sortFlag = SORT_ASCENDING;

    out[0] = NULL;

    if (in[1])
    {
	if (! DXExtractInteger(in[1], &sortFlag))
	{
	    DXSetError(ERROR_BAD_PARAMETER, "sort flag");
	    goto error;
	}

	if (sortFlag < 0 || sortFlag > 1)
	{
	    DXSetError(ERROR_BAD_PARAMETER, "sort flag must be 0 or 1");
	    goto error;
	}
    }

    out[0] = SortObject(in[0], sortFlag);

    if (! out[0])
	goto error;

    return OK;

error:
    if (in[0] != out[0])
	DXFree(out[0]);
    out[0] = NULL;
    return ERROR;
}

static int   *SortArray(Array, int);
static int   *MakeMap(int *, int);
static Array  ReMap(Array, int *);
static Array  ShuffleArray(Array, int *);

static Object
SortObject(Object o, int flag)
{
    int *indices = NULL, *map = NULL;
    Object new = NULL;

    switch(DXGetObjectClass(o))
    {
	case CLASS_GROUP: 
	{
	    int    i;
	    Object child;
	    Group  g = (Group)o;
	    Class  c = DXGetGroupClass(g);

	    if (c == CLASS_COMPOSITEFIELD)
	    {
		DXSetError(ERROR_INVALID_DATA,
			"cannot sort objects of class %s",
			(c == CLASS_COMPOSITEFIELD) ?
			    "composite field" : "multigrid");
		goto error;
	    }

	    new = DXCopy(o, COPY_HEADER);
	    if (! new)
		goto error;

	    if (c == CLASS_GROUP || c == CLASS_MULTIGRID)
	    {
		char *name;

		i = 0;
		while (NULL != (child = DXGetEnumeratedMember(g, i++, &name)))
		{
		    child = SortObject(child, flag);
		    if (! child)
			goto error;
		    
		    if (! DXSetMember((Group)new, name, child))
			goto error;
		}
	    }
	    else
	    {
		float f;

		i = 0;
		while (NULL != (child = DXGetSeriesMember((Series)g, i, &f)))
		{
		    child = SortObject(child, flag);
		    if (! child)
			goto error;
		    
		    if (! DXSetSeriesMember((Series)new, i++, f, child))
			goto error;
		}
	    }

	    break;
	}

	case CLASS_ARRAY:
	{
	    int *indices = SortArray((Array)o, flag);
	    if (! indices)
		goto error;

	    new = (Object)ShuffleArray((Array)o, indices);
	    DXFree((Pointer)indices);

	    if (! new)
		goto error;
	    
	    break;
	}

	case CLASS_FIELD:
	{
	    char *name, *sort_dep, *str;
	    Field f = (Field)o;
	    Array dArray = NULL;
	    Array src, dst = NULL;
	    int i, n;

	    if (DXEmptyField(f))
		break;

	    dArray = (Array)DXGetComponentValue(f, "data");
	    if (! dArray)
	    {
		DXSetError(ERROR_MISSING_DATA, "no data component");
		goto error;
	    }

	    if (! DXGetStringAttribute((Object)dArray, "dep", &sort_dep))
	    {
		DXSetError(ERROR_MISSING_DATA, "no data dependency");
		goto error;
	    }

	    DXGetArrayInfo(dArray, &n, NULL, NULL, NULL, NULL);

	    indices = SortArray(dArray, flag);
	    if (! indices)
		goto error;
	    
	    map = MakeMap(indices, n);
	    if (! map)
		goto error;

	    new = DXCopy(o, COPY_HEADER);
	    if (! new)
		goto error;

	    i = 0;
	    while (NULL != 
		(src = (Array)DXGetEnumeratedComponentValue(f, i++, &name)))
	    {
		if (! strcmp(name, "connections"))
		    str = "connections";
		else if (! DXGetStringAttribute((Object)src, "dep", &str))
		    str = NULL;

		if (str && ! strcmp(str, sort_dep))
		{
		    dst = ShuffleArray(src, indices);
		    if (! dst)
			goto error;

		    if (!DXSetComponentValue((Field)new, name, (Object)dst))
			goto error;
		    
		    src = (Array)DXGetComponentValue((Field)new, name);
		}

		if (DXGetStringAttribute((Object)src, "ref", &str) &&
					    !strcmp(str, sort_dep))
		{
		    dst = ReMap(src, map);
		    if (! dst)
			goto error;

		    if (!DXSetComponentValue((Field)new, name, (Object)dst))
			goto error;
		}
	    }

	    DXFree((Pointer)indices);
	    DXFree((Pointer)map);

	    break;
	}

	case CLASS_XFORM:
	{
	    Object child;
	    Matrix matrix;

	    if (! DXGetXformInfo((Xform)o, &child, &matrix))
		goto error;
	    
	    child = SortObject(child, flag);
	    if (! child)
		goto error;
	    
	    new = (Object)DXNewXform(child, matrix);
	    if (! new)
	    {
		DXDelete(child);
		goto error;
	    }

	    break;
	}

	case CLASS_CLIPPED:
	{
	    Object child;
	    Object clipper;

	    if (! DXGetClippedInfo((Clipped)o, &child, &clipper))
		goto error;
	    
	    child = SortObject(child, flag);
	    if (! child)
		goto error;
	    
	    new = (Object)DXNewClipped(child, clipper);
	    if (! new)
	    {
		DXDelete(child);
		goto error;
	    }

	    break;
	}

	case CLASS_SCREEN:
	{
	    Object child;
	    int z, position;

	    if (! DXGetScreenInfo((Screen)o, &child, &position, &z))
		goto error;
	    
	    child = SortObject(child, flag);
	    if (! child)
		goto error;
	    
	    new = (Object)DXNewScreen(child, position, z);
	    if (! new)
	    {
		DXDelete(child);
		goto error;
	    }

	    break;
	}
    }

    return new;

error:
    DXFree((Pointer)indices);
    DXFree((Pointer)map);
    if (new && new != o)
	DXDelete((Object)new);
    return NULL;
}

#define LT(a,b) 	((a)->value < (b)->value)
#define GT(a,b) 	((a)->value > (b)->value)


typedef struct {int index; double value;} dval;
#define TYPE		dval
#define QUICKSORT 	SortDouble
#define QUICKSORT_LOCAL	SortDoublelocal
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

typedef struct {int index; float value;} fval;
#define TYPE		fval
#define QUICKSORT 	SortFloat
#define QUICKSORT_LOCAL	SortFloat_local
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

typedef struct {int index; int value;} ival;
#define TYPE		ival
#define QUICKSORT 	SortInt
#define QUICKSORT_LOCAL	SortInt_local
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

typedef struct {int index; unsigned int value;} uival;
#define TYPE		uival
#define QUICKSORT 	SortUInt
#define QUICKSORT_LOCAL	SortUInt_local
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

typedef struct {int index; short value;} sval;
#define TYPE		sval
#define QUICKSORT 	SortShort
#define QUICKSORT_LOCAL	SortShort_local
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

typedef struct {int index; unsigned short value;} usval;
#define TYPE 		usval
#define QUICKSORT 	SortUShort
#define QUICKSORT_LOCAL	SortUShort_local
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

typedef struct {int index; char value;} bval;
#define TYPE		bval
#define QUICKSORT 	SortByte
#define QUICKSORT_LOCAL	SortByte_local
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

typedef struct {int index; unsigned char value;} ubval;
#define TYPE 		ubval
#define QUICKSORT 	SortUByte
#define QUICKSORT_LOCAL	SortUByte_local
#include "../libdx/qsort.c"
#undef TYPE
#undef QUICKSORT
#undef QUICKSORT_LOCAL

#define SORTARRAY(type, stype,  sort)				\
{								\
    stype *list;						\
    int  i;							\
    type *data;							\
								\
    list = (stype *)DXAllocate(n*sizeof(stype));		\
    if (! list)							\
	goto error;						\
    								\
    data = (type *)DXGetArrayData(a);				\
    if (! data)							\
    {								\
	DXFree((Pointer)list);					\
	goto error;						\
    }								\
								\
    for (i = 0; i < n; i++)					\
    {								\
	list[i].index = i;					\
	list[i].value = data[i];				\
    }								\
								\
    sort(list, n);						\
								\
    indices = (int *)DXAllocate(n*sizeof(int));			\
    if (! indices)						\
    {								\
	DXFree((Pointer)list);					\
	goto error;						\
    }								\
     								\
    for (i = 0; i < n; i++)					\
	indices[i] = list[i].index;				\
    								\
    DXFree((Pointer)list);					\
}



static int *
SortArray(Array a, int flag)
{
    int      *indices = NULL;
    int      i, n, r, s[32];
    Type     t;
    Category c;

    if (DXGetObjectClass((Object)a) != CLASS_ARRAY)
	goto error;
    
    DXGetArrayInfo(a, &n, &t, &c, &r, s);

    if (r != 0 && (r != 1 || s[0] != 1))
    {
	DXSetError(ERROR_INVALID_DATA,
		"sort object must be scalar or 1-vector");
	goto error;
    }

    switch(t)
    {
	case TYPE_DOUBLE: SORTARRAY(double,         dval,  SortDouble); break;
	case TYPE_FLOAT:  SORTARRAY(float,          fval,  SortFloat);  break;
#if 0
	case TYPE_INT:    SORTARRAY(int,            ival,  SortInt);    break;
#else
	case TYPE_INT:
{								
    ival *list;						
    int  i;							
    int *data;							
								
    list = (ival *)DXAllocate(n*sizeof(ival));		
    if (! list)							
	goto error;						
    								
    data = (int *)DXGetArrayData(a);				
    if (! data)							
    {								
	DXFree((Pointer)list);					
	goto error;						
    }								
								
    for (i = 0; i < n; i++)					
    {								
	list[i].index = i;					
	list[i].value = data[i];				
    }								
								
    SortInt(list, n);						
								
    indices = (int *)DXAllocate(n*sizeof(int));			
    if (! indices)						
    {								
	DXFree((Pointer)list);					
	goto error;						
    }								
     								
    for (i = 0; i < n; i++)					
	indices[i] = list[i].index;				
    								
    DXFree((Pointer)list);					
}
break;
#endif
	case TYPE_UINT:   SORTARRAY(unsigned int,   uival, SortUInt);   break;
	case TYPE_SHORT:  SORTARRAY(short,          sval,  SortShort);  break;
	case TYPE_USHORT: SORTARRAY(unsigned short, usval, SortUShort); break;
	case TYPE_BYTE:   SORTARRAY(char,           bval,  SortByte);   break;
	case TYPE_UBYTE:  SORTARRAY(unsigned char,  ubval, SortUByte);  break;
	default: 
	{
	    DXSetError(ERROR_INVALID_DATA, 
		"invalid data type in sort object");
	    goto error;
	}
    }

    if (flag == SORT_DESCENDING)
    {
	int m = n >> 1;
	n -= 1;

	for (i = 0; i < m; i++)
	{
	    int t = indices[i];
	    indices[i] = indices[n-i];
	    indices[n-i] = t;
	}
    }

    return indices;

error:
    DXFree((Pointer)indices);
    return NULL;
}

static Array
ShuffleArray(Array src, int *indices)
{
    Type t;
    Category c;
    Array dst = NULL;
    int n, r, s[32], size, i;
    unsigned char *sPtr, *dPtr;

    if (DXGetObjectClass((Object)src) != CLASS_ARRAY)
    {
	DXSetError(ERROR_BAD_CLASS, 
	     "component encountered that is not class ARRAY");
	goto error;
    }
	
    DXGetArrayInfo(src, &n, &t, &c, &r, s);

    size = DXGetItemSize(src);

    dst = DXNewArrayV(t, c, r, s);
    if (! dst)
	goto error;

    if (! DXAddArrayData(dst, 0, n, NULL))
	goto error;

    sPtr = (unsigned char *)DXGetArrayData(src);
    dPtr = (unsigned char *)DXGetArrayData(dst);

    if (! sPtr || ! dPtr)
	goto error;
    
    for (i = 0; i < n; i++)
    {
	memcpy(dPtr, sPtr+(indices[i]*size), size);
	dPtr += size;
    }

    return dst;

error:
    DXDelete((Object)dst);
    return NULL;
}

static int *
MakeMap(int *indices, int n)
{
    int i, *map = DXAllocate(n*sizeof(int));
    if (! map)
	goto error;
    
    for (i = 0; i < n; i++)
	map[indices[i]] = i;
    
    return map;

error:
    return NULL;
}
    
static Array
ReMap(Array src, int *map)
{
    Type t;
    Category c;
    Array dst = NULL;
    int n, nr, r, s[32], size, i, j;
    int *sPtr, *dPtr;

    if (DXGetObjectClass((Object)src) != CLASS_ARRAY)
    {
	DXSetError(ERROR_BAD_CLASS, 
	     "component encountered that is not class ARRAY");
	goto error;
    }
	
    DXGetArrayInfo(src, &n, &t, &c, &r, s);

    if (t != TYPE_INT)
    {
	DXSetError(ERROR_INVALID_DATA, "ref component must be type INTEGER");
	goto error;
    }

    size = DXGetItemSize(src);

    dst = DXNewArrayV(t, c, r, s);
    if (! dst)
	goto error;

    if (! DXAddArrayData(dst, 0, n, NULL))
	goto error;

    sPtr = (int *)DXGetArrayData(src);
    dPtr = (int *)DXGetArrayData(dst);

    if (! sPtr || ! dPtr)
	goto error;
    
    nr = n * size/sizeof(int);
    for (i = 0; i < nr; i++)
	*dPtr++ = map[*sPtr++];

    return dst;

error:
    DXDelete((Object)dst);
    return NULL;
}