/*
 * $Header: /home/grantham/cvsroot/projects/modules/tc/tc.c,v 1.27 2000/10/10 16:09:23 grantham Exp $
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "tc.h"

/* SNIPPET "table.c" Inducted Wed Nov 22 09:36:55 2000 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if !defined(MEM_CHART)
#define chartedSetLabel(a)
#endif

#define LEVEL1COUNT 16384
#define LEVEL2COUNT 1024
#define LEVEL3COUNT 256

typedef struct TableLevel3
{
    int EntryCount;
    void *Table[LEVEL3COUNT];
    char IsSet[LEVEL3COUNT];
} TableLevel3;

typedef struct TableLevel2
{
    int EntryCount;
    TableLevel3 *Table[LEVEL2COUNT];
} TableLevel2;

typedef struct TableRoot
{
    size_t EntryCount;
    size_t TotalEntryCount;
    size_t TotalAllocatedBytes;
    int EmptyEntryCount;
    TableLevel2 *Table[LEVEL1COUNT];
} TableRoot;

typedef struct TableIterator {
    int i1, i2, i3;
    unsigned int i;
    TableLevel3 *CurLevel3;
    int CheckLevel1, CheckLevel2;
} TableIterator;

TableRoot *tableNew(void)
{
    TableRoot *tr;

    chartedSetLabel("table root");
    tr = (TableRoot *)calloc(sizeof(TableRoot), 1);
    return tr;
}

TableIterator *tableNewIterator(void)
{
    TableIterator *ti;

    chartedSetLabel("table iterator");
    ti = (TableIterator *)malloc(sizeof(TableIterator));
    return ti;
}

int tableRetrieve(unsigned int a, TableRoot *table, void **ref)
{
    int i1 = a / (LEVEL2COUNT * LEVEL3COUNT);
    int i2 = (a / LEVEL3COUNT) % LEVEL2COUNT;
    int i3 = a % LEVEL3COUNT;

    if(table->Table[i1] == NULL)
        return 0;
    if(table->Table[i1]->Table[i2] == NULL)
        return 0;
    if(!table->Table[i1]->Table[i2]->IsSet[i3])
        return 0;
    if(ref != NULL)
        *ref = table->Table[i1]->Table[i2]->Table[i3];
    return 1;
}

int tableInsert(unsigned int a, TableRoot *table, void *ref)
{
    int i1 = a / (LEVEL2COUNT * LEVEL3COUNT);
    int i2 = (a / LEVEL3COUNT) % LEVEL2COUNT;
    int i3 = a % LEVEL3COUNT;

    if(table->Table[i1] == NULL) {
	chartedSetLabel("table level 2");
        table->Table[i1] = (TableLevel2 *)calloc(1, sizeof(TableLevel2));
	table->TotalAllocatedBytes += sizeof(TableLevel2);
        if(table->Table[i1] == NULL)
            return 0;
    }
    if(table->Table[i1]->Table[i2] == NULL) {
	chartedSetLabel("table level 3");
        table->Table[i1]->Table[i2] =
	    (TableLevel3 *)calloc(1, sizeof(TableLevel3));
	table->TotalAllocatedBytes += sizeof(TableLevel3);
        if(table->Table[i1]->Table[i2] == NULL)
            return 0;
	table->Table[i1]->EntryCount++;
	table->TotalEntryCount += LEVEL3COUNT;
	table->EmptyEntryCount += LEVEL3COUNT;
    }
    if(!table->Table[i1]->Table[i2]->IsSet[i3]) {
	table->Table[i1]->Table[i2]->EntryCount++;
	table->EmptyEntryCount --;
	table->Table[i1]->Table[i2]->IsSet[i3] = 1;
    }
    table->Table[i1]->Table[i2]->Table[i3] = ref;
    return 1;
}

int tableRemove(unsigned int a, TableRoot *table, void **wasref)
{
    int i1 = a / (LEVEL2COUNT * LEVEL3COUNT);
    int i2 = (a / LEVEL3COUNT) % LEVEL2COUNT;
    int i3 = a % LEVEL3COUNT;

    if(table->Table[i1] == NULL)
	return 0;
    if(table->Table[i1]->Table[i2] == NULL)
	return 0;
    if(!table->Table[i1]->Table[i2]->IsSet[i3])
        return 0;
    if(wasref != NULL)
        *wasref = table->Table[i1]->Table[i2]->Table[i3];
    table->Table[i1]->Table[i2]->IsSet[i3] = 0;
    table->EmptyEntryCount ++;
    if(--table->Table[i1]->Table[i2]->EntryCount == 0) {
	table->EmptyEntryCount -= LEVEL3COUNT;
	table->TotalEntryCount -= LEVEL3COUNT;
	free(table->Table[i1]->Table[i2]);
	table->TotalAllocatedBytes -= sizeof(TableLevel3);
	table->Table[i1]->Table[i2] = NULL;
	if(--table->Table[i1]->EntryCount == 0) {
	    table->TotalAllocatedBytes -= sizeof(TableLevel2);
	    free(table->Table[i1]);
	    table->Table[i1] = NULL;
	}
    }
    return 1;
}

void tableResetIterator(TableIterator *ti)
{
    ti->i1 = 0;
    ti->i2 = 0;
    ti->i3 = 0;
    ti->i = 0;
    ti->CheckLevel1 = 1;
    ti->CheckLevel2 = 1;
}

int tableIterate(TableRoot *table, TableIterator *ti, unsigned int *i, void **ref)
{
    int done;

    done = 0;
    while(ti->i1 < LEVEL1COUNT) {
        if(ti->CheckLevel1 && table->Table[ti->i1] == NULL) {
	    ti->i += LEVEL2COUNT * LEVEL3COUNT;
	    ti->i1++;
	    continue;
	} else
	    ti->CheckLevel1 = 0;
        if(ti->CheckLevel2 && table->Table[ti->i1]->Table[ti->i2] == NULL) {
	    ti->i += LEVEL3COUNT;
	    if(++ti->i2 >= LEVEL2COUNT) {
		ti->i2 = 0;
		ti->i1++;
		ti->CheckLevel1 = 1;
	    }
	    continue;
	} else
	    ti->CheckLevel2 = 0;
	if(ti->i3 == 0)
	    ti->CurLevel3 = table->Table[ti->i1]->Table[ti->i2];
	if(ti->CurLevel3->IsSet[ti->i3]) {
	    if(ref != NULL)
		*ref = ti->CurLevel3->Table[ti->i3];
	    if(i != NULL)
		*i = ti->i;
	    done = 1;
	}
	ti->i++;
	if(++ti->i3 >= LEVEL3COUNT) {
	    ti->i3 = 0;
	    ti->CheckLevel2 = 1;
	    if(++ti->i2 >= LEVEL2COUNT) {
		ti->i2 = 0;
		ti->i1++;
		ti->CheckLevel1 = 1;
	    }
	}
	if(done)
	    return 1;
    }
    return 0;
}

void tableDelete(TableRoot *table, void (*datumDelete)(void *datum))
{
    int i1, i2, i3;

    for(i1 = 0; i1 < LEVEL1COUNT; i1++) {
        if(table->Table[i1] != NULL) {
	    for(i2 = 0; i2 < LEVEL2COUNT; i2++) {
		if(table->Table[i1]->Table[i2] != NULL) {
		    for(i3 = 0; i3 < LEVEL3COUNT; i3++) {
			if(table->Table[i1]->Table[i2]->IsSet[i3])
			    datumDelete(table->Table[i1]->Table[i2]->Table[i3]);
		    }
		    free(table->Table[i1]->Table[i2]);
		}
	    }
	    free(table->Table[i1]);
	    table->Table[i1] = NULL;
	}
    }
    table->TotalEntryCount = 0;
    table->EmptyEntryCount = 0;
    table->TotalAllocatedBytes = 0;
}

void tableGetStats(TableRoot *table, size_t *totalBytes, size_t *emptyCount,
    size_t *totalCount)
{
    if(emptyCount != NULL)
        *emptyCount = table->EmptyEntryCount;
    if(totalCount != NULL)
        *totalCount = table->TotalEntryCount;
    if(totalBytes != NULL)
        *totalBytes = table->TotalAllocatedBytes;
}

size_t tableGetIteratorSize(void)
{
    return sizeof(TableIterator);
}

/* "table.c" ENDSNIPPET */

#if !defined(MEM_CHART)
#define chartedSetLabel(a)
#endif

#if defined(DEBUG)
#define ACTC_DEBUG(a) a
#else
#define ACTC_DEBUG(a)
#endif

#if defined(INFO)
#define ACTC_INFO(a) a
#else
#define ACTC_INFO(a)
#endif


#define ACTC_CHECK(a) \
    { \
        int theErrorNow; \
	theErrorNow = (a); \
	if(theErrorNow < 0) \
	    return theErrorNow; \
    }

typedef struct {
    struct ACTCVertex *FinalVert;
} ACTCTriangle;

typedef struct {
    struct ACTCVertex *V2;
    int Count;
    int TriangleCount;
    ACTCTriangle *Triangles;
} ACTCEdge;

typedef struct ACTCVertex {
    unsigned int V;
    int Count;
    struct ACTCVertex **PointsToMe;
    struct ACTCVertex *Next;
    int EdgeCount;
    ACTCEdge *Edges;
} ACTCVertex;

/* private tokens */
#define ACTC_NO_MATCHING_VERT		-0x3000
#define ACTC_FWD_ORDER			0
#define ACTC_REV_ORDER			1

#define MAX_STATIC_VERTS		10000000 /* buh? */

struct _ACTCData {

    /* vertex and edge database */
    int VertexCount;
    TableRoot *Vertices;
    TableIterator *VertexIterator;
    int CurMaxVertValence;
    int CurMinVertValence;
    ACTCVertex **VertexBins;

    /* alternate vertex array if range small enough */
    ACTCVertex *StaticVerts;
    int UsingStaticVerts;
    unsigned int VertRange;

    /* During consolidation */
    int CurWindOrder;
    int PrimType;
    ACTCVertex *V1;
    ACTCVertex *V2;
    int VerticesSoFar;

    /* Error and state handling */
    int IsInputting;
    int IsOutputting;
    int Error;

    /* actcParam-settable parameters */
    unsigned int MinInputVert;
    unsigned int MaxInputVert;
    int MaxVertShare;
    int MaxEdgeShare;
    int MinFanVerts;
    int MaxPrimVerts;
    int HonorWinding;
};

#if defined(DEBUG) || defined(INFO)

static void dumpTriangles(ACTCEdge *e, FILE *fp)
{
    int i;
    int c;
    char v[12];

    c = fprintf(fp, "      %d triangles: ");
    for(i = 0; i < e->TriangleCount; i++) {
	if(c + 1 + sprintf(v, "%u", e->Triangles[i].FinalVert) > 78) {
	    fputs("\n", fp);
	    c = fprintf(fp, "        ");
	}
	c += fprintf(fp, " %s", v);
    }
    fputs("\n", fp);
}

static void dumpEdges(ACTCVertex *vert, FILE *fp)
{
    int i;
    int c;
    char v[26]; /* two signed ints plus x plus NUL */

    for(i = 0; i < vert->EdgeCount; i++) {
	fprintf(fp, "    %u->%u (%d times)\n", vert->V, vert->Edges[i].V2->V,
	    vert->Edges[i].Count);
	dumpTriangles(&vert->Edges[i], fp);
    }
    fputs("\n", fp);
}

static void dumpVertices(ACTCData *tc, FILE *fp)
{
    int i;
    ACTCVertex *v;

    if(!tc->UsingStaticVerts)
        tableResetIterator(tc->VertexIterator);

    fprintf(fp, "%d vertices in valences list\n", tc->VertexCount);
    if(tc->UsingStaticVerts) {
        for(i = 0; i < tc->VertRange; i++) {
	    v = &tc->StaticVerts[i];
	    if(v->Count > 0) {
		fprintf(fp, "  vertex %u, valence %d, %d edges\n", v->V,
		    v->Count, v->EdgeCount);
		dumpEdges(v, fp);
	    }
	}
    } else {
	for(i = 0; i < tc->VertexCount; i++) {
	    if(tableIterate(tc->Vertices, tc->VertexIterator, NULL,
		(void **)&v) == 0) {
		fprintf(fp, "ACTC::dumpVertices : fewer vertices in the table "
		    "than we expected!\n");
		fprintf(stderr, "ACTC::dumpVertices : fewer vertices in the table "
		    "than we expected!\n");
	    }
	    if(v == NULL) {
		fprintf(fp, "ACTC::dumpVertices : did not expect to get a NULL"
		    "Vertex from the table iterator!\n");
		fprintf(stderr, "ACTC::dumpVertices : did not expect to get a NULL"
		    "Vertex from the table iterator!\n");
	    }
	    fprintf(fp, "  vertex %u, valence %d, %d edges\n", v->V, v->Count,
		v->EdgeCount);
	    dumpEdges(v, fp);
	}
    }
}

static void dumpVertexBins(ACTCData *tc, FILE *fp)
{
    ACTCVertex *cur;
    int i;
    int c;
    char v[26]; /* two signed ints plus x plus NUL */

    fprintf(fp, "vertex bins:\n");
    if(tc->VertexBins == NULL) {
        fprintf(fp, "        empty.\n");
	return;
    }
    for(i = 1; i <= tc->CurMaxVertValence; i++) {
        cur = tc->VertexBins[i];
	c = fprintf(fp, "        bin %d -> ", i);
	while(cur != NULL) {
	    if(c + 1 + sprintf(v, "%ux%d", cur->V, cur->Count) > 78) {
		fputs("\n", fp);
		c = fprintf(fp, "          ");
	    }
	    c += fprintf(fp, " %s", v);
	    cur = cur->Next;
	}
	fputs("\n", fp);
    }
}

void actcDumpState(ACTCData *tc, FILE *fp)
{
    dumpVertices(tc, fp);
    dumpVertexBins(tc, fp);
}

#endif /* DEBUG || INFO */

#if defined(DEBUG)

static int abortWithOptionalDump(ACTCData *tc)
{
    ACTC_INFO(actcDumpState(tc, stderr));
    abort();
}

#endif /* defined(DEBUG) */

int actcGetError(ACTCData *tc)
{
    int error = tc->Error;
    tc->Error = ACTC_NO_ERROR;
    return error;
}

static void *reallocAndAppend(void **ptr, unsigned int *itemCount, size_t itemBytes,
    void *append)
{
    void *t;

    t = realloc(*ptr, itemBytes * (*itemCount + 1));
    if(t == NULL)
	return NULL;
    *ptr = t;

    memcpy((unsigned char *)*ptr + *itemCount * itemBytes, append, itemBytes);
    (*itemCount) += 1;

    return *ptr;
}

/*
 * Call only during input; changes vertices' valences and does not
 * fix the bins that are ordered by vertex valence.  (It's usually cheaper
 * to traverse the vertex list once after all are added, since that's
 * linear in the NUMBER OF UNIQUE VERTEX INDICES, which is almost always
 * going to be less than the number of vertices.)
 */
static int incVertexValence(ACTCData *tc, unsigned int v, ACTCVertex **found)
{
    ACTCVertex *vertex;

    if(tc->UsingStaticVerts) {
        vertex = &tc->StaticVerts[v];
	vertex->Count++;
	if(vertex->Count == 1) {
	    vertex->V = v;
	    tc->VertexCount++;
	}
    } else {
	if(tableRetrieve(v, tc->Vertices, (void **)&vertex) == 1) {
	    if(vertex->V != v) {
		ACTC_DEBUG(
		    fprintf(stderr, "ACTC::incVertexValence : Got vertex %d when "
			"looking for vertex %d?!?\n", vertex->V, v);
		    abortWithOptionalDump(tc);
		)
		return tc->Error = ACTC_DATABASE_CORRUPT;
	    }
	    vertex->Count++;
	} else {
	    chartedSetLabel("new Vertex");
	    vertex = (ACTCVertex *)malloc(sizeof(ACTCVertex));
	    vertex->V = v;
	    vertex->Count = 1;
	    vertex->Edges = NULL;
	    vertex->EdgeCount = 0;
	    if(tableInsert(v, tc->Vertices, vertex) == 0) {
		ACTC_DEBUG(fprintf(stderr, "ACTC::incVertexValence : Failed "
		    "to insert vertex into table\n");)
		return tc->Error = ACTC_ALLOC_FAILED;
	    }
	    tc->VertexCount++;
	}
    }
    if(vertex->Count > tc->CurMaxVertValence)
	tc->CurMaxVertValence = vertex->Count;

    *found = vertex;

    return ACTC_NO_ERROR;
}

static int decVertexValence(ACTCData *tc, ACTCVertex **vptr)
{
    ACTCVertex *v = *vptr;

    v->Count--;
    if(v->Count < 0) {
	ACTC_DEBUG(
	    fprintf(stderr, "ACTC::decVertexValence : Valence went "
		"negative?!?\n");
	    abortWithOptionalDump(tc);
	)
	return tc->Error = ACTC_DATABASE_CORRUPT;
    }

    if(v->PointsToMe != NULL) {
	*v->PointsToMe = v->Next;
	if(v->Next != NULL)
	    v->Next->PointsToMe = v->PointsToMe;
	v->Next = NULL;
    }

    if(v->Count == 0) {
	tc->VertexCount--;
	if(v->Edges != NULL)
	    free(v->Edges);
        if(!tc->UsingStaticVerts) {
	    tableRemove(v->V, tc->Vertices, NULL);
	    free(v);
	}
	*vptr = NULL;
    } else {
	if(tc->VertexBins != NULL) {
	    v->Next = tc->VertexBins[v->Count];
	    v->PointsToMe = &tc->VertexBins[v->Count];
	    if(v->Next != NULL)
		v->Next->PointsToMe = &v->Next;
	    tc->VertexBins[v->Count] = v;
	    if(v->Count < tc->CurMinVertValence)
		tc->CurMinVertValence = v->Count;
	}
    }

    return ACTC_NO_ERROR;
}

static int findNextFanVertex(ACTCData *tc, ACTCVertex **vert)
{
    if(tc->CurMaxVertValence < tc->MinFanVerts) {
	return ACTC_NO_MATCHING_VERT;
    }
    while(tc->VertexBins[tc->CurMaxVertValence] == NULL) {
	tc->CurMaxVertValence--;
	if(tc->CurMaxVertValence < tc->CurMinVertValence) {
	    if(tc->VertexCount > 0) {
		ACTC_DEBUG(fprintf(stderr, "tc::findNextFanVertex : no more "
		    "vertices in bins but VertexCount > 0\n");)
		return tc->Error = ACTC_DATABASE_CORRUPT;
	    }
	    return ACTC_NO_MATCHING_VERT;
	}
    }
    *vert = tc->VertexBins[tc->CurMaxVertValence];
    return ACTC_NO_ERROR;
}

static int findNextStripVertex(ACTCData *tc, ACTCVertex **vert)
{
    while(tc->VertexBins[tc->CurMinVertValence] == NULL) {
	tc->CurMinVertValence++;
	if(tc->CurMinVertValence > tc->CurMaxVertValence) {
	    if(tc->VertexCount > 0) {
		ACTC_DEBUG(fprintf(stderr, "tc::findNextStripVertex : no more "
		    "vertices in bins but VertexCount > 0\n");)
		return tc->Error = ACTC_DATABASE_CORRUPT;
	    }
	    return ACTC_NO_MATCHING_VERT;
	}
    }
    *vert = tc->VertexBins[tc->CurMinVertValence];
    return ACTC_NO_ERROR;
}

int actcGetIsDuringInput(ACTCData *tc) {
    return tc->IsInputting;
}

int actcBeginInput(ACTCData *tc)
{
    if(tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcBeginInput : called within "
	    "BeginOutput/EndOutput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }

    if(tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcBeginInput : called within "
	    "BeginInput/EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }

    tc->IsInputting = 1;
    tc->CurMaxVertValence = 0;

    if(tc->MaxInputVert < MAX_STATIC_VERTS - 1) {
	size_t byteCount;
	tc->UsingStaticVerts = 1;
	tc->VertRange = tc->MaxInputVert + 1;
	byteCount = sizeof(ACTCVertex) * tc->VertRange;
	chartedSetLabel("static verts");
	tc->StaticVerts = (ACTCVertex *)calloc(sizeof(ACTCVertex), tc->VertRange);
	if(tc->StaticVerts == NULL) {
	    ACTC_INFO(printf("Couldn't allocate static %d vert block of %u "
		"bytes\n", tc->VertRange, byteCount);)
	    tc->UsingStaticVerts = 0;
	}
    } else
	tc->UsingStaticVerts = 0;

    return ACTC_NO_ERROR;
}

int actcEndInput(ACTCData *tc)
{
    if(tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcEndInput : called within "
	    "BeginOutput/EndOutput\n");)
	return tc->Error = ACTC_DURING_OUTPUT;
    }

    if(!tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcEndInput : called outside "
	    "BeginInput/EndInput\n");)
	return tc->Error = ACTC_IDLE;
    }

    tc->IsInputting = 0;

    return ACTC_NO_ERROR;
}

int actcGetIsDuringOutput(ACTCData *tc) {
    return tc->IsOutputting;
}

int actcBeginOutput(ACTCData *tc)
{
    ACTCVertex *v;
    int i;

    if(tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcBeginOutput : called within "
	    "BeginInput/EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }

    if(tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcBeginOutput : called within "
	    "BeginOutput/EndOutput\n");)
	return tc->Error = ACTC_DURING_OUTPUT;
    }

    tc->IsOutputting = 1;

    tc->CurMinVertValence = INT_MAX;
    chartedSetLabel("vertex bins");
    tc->VertexBins = (ACTCVertex **)calloc(sizeof(ACTCVertex *), tc->CurMaxVertValence + 1);
    if(tc->VertexBins == NULL) {
	ACTC_DEBUG(fprintf(stderr, "actcBeginOutput : couldn't allocate %d bytes "
	    "for Vertex Bins\n",
	    sizeof(ACTCVertex *) * tc->CurMaxVertValence);)
	return tc->Error = ACTC_ALLOC_FAILED;
    }

    if(tc->UsingStaticVerts) {
        double edgeTotal;
        for(i = 0; i < (int)tc->VertRange; i++) {
	    v = &tc->StaticVerts[i];
	    if(v->Count > 0) {
		v->Next = tc->VertexBins[v->Count];
		v->PointsToMe = &tc->VertexBins[v->Count];
		tc->VertexBins[v->Count] = v;
		if(v->Next != NULL)
		    v->Next->PointsToMe = &v->Next;
		if(v->Count < tc->CurMinVertValence)
		    tc->CurMinVertValence = v->Count;
		edgeTotal += v->EdgeCount;
	    }
	}
    } else {
	tableResetIterator(tc->VertexIterator);
	for(i = 0; i < tc->VertexCount; i++) {
	    if(tableIterate(tc->Vertices, tc->VertexIterator, NULL, (void **)&v)
		== 0) {
		ACTC_DEBUG(fprintf(stderr, "actcBeginOutput : fewer vertices in "
		    "the table than we expected!\n");)
		return tc->Error = ACTC_DATABASE_CORRUPT;
	    }
	    v->Next = tc->VertexBins[v->Count];
	    v->PointsToMe = &tc->VertexBins[v->Count];
	    tc->VertexBins[v->Count] = v;
	    if(v->Next != NULL)
		v->Next->PointsToMe = &v->Next;
	    if(v->Count < tc->CurMinVertValence)
		tc->CurMinVertValence = v->Count;
	}
    }

    return ACTC_NO_ERROR;
}

int actcEndOutput(ACTCData *tc)
{
    if(tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcEndOutput : called within "
	    "BeginInput/EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }

    if(!tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcEndOutput : called outside "
	    "BeginOutput/EndOutput\n");)
	return tc->Error = ACTC_IDLE;
    }

    tc->IsOutputting = 0;

    if(tc->UsingStaticVerts) {
	free(tc->StaticVerts);
	tc->StaticVerts = NULL;
	tc->UsingStaticVerts = 0;
    }

    free(tc->VertexBins);
    tc->VertexBins = NULL;

    return ACTC_NO_ERROR;
}

ACTCData *actcNew(void)
{
    ACTCData *tc;
#if defined(DEBUG) || defined(INFO)
    static int didPrintVersion = 0;

    if(!didPrintVersion) {
	int verMinor, verMajor;
	didPrintVersion = 1;

        actcGetParami(tc, ACTC_MAJOR_VERSION, &verMajor);
        actcGetParami(tc, ACTC_MINOR_VERSION, &verMinor);
	fprintf(stderr, "TC Version %d.%d\n", verMajor, verMinor);
    }
#endif /* defined(DEBUG) || defined(INFO) */

    chartedSetLabel("the tc struct");
    tc = (ACTCData *)calloc(sizeof(*tc), 1);

    if(tc == NULL) {
	ACTC_DEBUG(fprintf(stderr, "actcNew : couldn't allocate %d bytes "
	    "for new ACTCData\n", sizeof(*tc));)
	return NULL;
    }

    tc->Vertices = tableNew();
    tc->VertexIterator = tableNewIterator();

    tc->MinFanVerts = INT_MAX;
    tc->MaxPrimVerts = INT_MAX;
    tc->MaxInputVert = INT_MAX;
    tc->MaxEdgeShare = INT_MAX;
    tc->MaxVertShare = INT_MAX;
    tc->HonorWinding = 1;
    /* seed = 0 handled by calloc */
    /* XXX grantham 20000615 - seed ignored for now */

    return tc;
}

static size_t allocatedForTriangles(ACTCEdge *e)
{
    return sizeof(ACTCTriangle) * e->TriangleCount;
}

static size_t allocatedForEdges(ACTCVertex *vert)
{
    int i;
    size_t size;

    size = sizeof(ACTCEdge) * vert->EdgeCount;
    for(i = 0; i < vert->EdgeCount; i++) {
	size += allocatedForTriangles(&vert->Edges[i]);
    }
    return size;
}

static size_t allocatedForVertices(ACTCData *tc)
{
    int i;
    int size = 1;
    ACTCVertex *v;

    if(!tc->UsingStaticVerts)
        tableResetIterator(tc->VertexIterator);

    if(tc->UsingStaticVerts) {
        size = tc->VertRange * sizeof(ACTCVertex);
        for(i = 0; i < (int)tc->VertRange; i++) {
	    v = &tc->StaticVerts[i];
	    if(v->Count > 0)
	        size += allocatedForEdges(v);
	}
    } else {
	for(i = 0; i < tc->VertexCount; i++) {
	    tableIterate(tc->Vertices, tc->VertexIterator, NULL, (void **)&v);
	    size += allocatedForEdges(v);
	}
    }
    return size;
}

int actcGetMemoryAllocation(ACTCData *tc, size_t *bytesAllocated)
{
    size_t tableBytes;

    tableGetStats(tc->Vertices, NULL, NULL, &tableBytes);
    *bytesAllocated = sizeof(ACTCData);
    *bytesAllocated += tableBytes;
    *bytesAllocated += allocatedForVertices(tc); /* recurses */

    return ACTC_NO_ERROR;
}

static void freeVertex(void *p)
{
    ACTCVertex *v = (ACTCVertex *)p;
    int i;

    for(i = 0; i < v->EdgeCount; i++)
        free(v->Edges[i].Triangles);
    free(v->Edges);
    free(v);
}

int actcMakeEmpty(ACTCData *tc)
{
    tc->VertexCount = 0;
    if(!tc->UsingStaticVerts)
        tableDelete(tc->Vertices, freeVertex);
    if(tc->VertexBins != NULL) {
        free(tc->VertexBins);
	tc->VertexBins = NULL;
    }
    tc->IsOutputting = 0;
    tc->IsInputting = 0;
    return ACTC_NO_ERROR;
}

void actcDelete(ACTCData *tc)
{
    actcMakeEmpty(tc);
    free(tc->VertexIterator);
    free(tc->Vertices);
    free(tc);
}

int actcParami(ACTCData *tc, int param, int value)
{
    if(tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcParami : within BeginInput/"
	    "EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }
    if(tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcParami : within BeginOutput/"
	    "EndOutput\n");)
	return tc->Error = ACTC_DURING_OUTPUT;
    }
    switch(param) {
	case ACTC_OUT_MIN_FAN_VERTS:
	    tc->MinFanVerts = value;
	    break;

	case ACTC_IN_MAX_VERT:
          if(value < (int)tc->MinInputVert) {
		ACTC_DEBUG(fprintf(stderr, "actcParami : tried to set "
		    "MAX_INPUT_VERT to %d, less than MIN_INPUT_VERT (%d)\n",
		    value, tc->MinInputVert);)
		return tc->Error = ACTC_INVALID_VALUE;
	    }
	    tc->MaxInputVert = value;
	    break;

	case ACTC_IN_MIN_VERT:
          if(value > (int)tc->MaxInputVert) {
		ACTC_DEBUG(fprintf(stderr, "actcParami : tried to set "
		    "MIN_INPUT_VERT to %d, greater than MAX_INPUT_VERT (%d)\n",
		    value, tc->MaxInputVert);)
		return tc->Error = ACTC_INVALID_VALUE;
	    }
	    tc->MinInputVert = value;
	    break;

	case ACTC_IN_MAX_EDGE_SHARING:
	    tc->MaxEdgeShare = value;
	    break;

	case ACTC_IN_MAX_VERT_SHARING:
	    tc->MaxVertShare = value;
	    break;

	case ACTC_OUT_HONOR_WINDING:
	    tc->HonorWinding = value;
	    break;

	case ACTC_OUT_MAX_PRIM_VERTS:
	    if(value < 3) {
		ACTC_DEBUG(fprintf(stderr, "actcParami : tried to set "
		    "MAX_PRIM_VERTS to %d (needed to be 3 or more)\n", value);)
		return tc->Error = ACTC_INVALID_VALUE;
	    }
	    tc->MaxPrimVerts = value;
	    break;

    }
    return ACTC_NO_ERROR;
}

int actcParamu(ACTCData *tc, int param, unsigned int value)
{
    /*
     * XXX - yes, this is questionable, but I consulted industry
     * experts and we agreed that most common behavior is to copy the
     * bits directly, which is what I want.
     */
    return actcParami(tc, param, (int)value);
}

int actcGetParami(ACTCData *tc, int param, int *value)
{
    switch(param) {
	case ACTC_MAJOR_VERSION:
	    *value = 1;
	    break;

	case ACTC_MINOR_VERSION:
	    *value = 1;
	    break;

	case ACTC_IN_MAX_VERT:
	    *value = tc->MaxInputVert;
	    break;

	case ACTC_IN_MIN_VERT:
	    *value = tc->MinInputVert;
	    break;

	case ACTC_IN_MAX_EDGE_SHARING:
	    *value = tc->MaxEdgeShare;
	    break;

	case ACTC_IN_MAX_VERT_SHARING:
	    *value = tc->MaxVertShare;
	    break;

	case ACTC_OUT_MIN_FAN_VERTS:
	    *value = tc->MinFanVerts;
	    break;

	case ACTC_OUT_HONOR_WINDING:
	    *value = tc->HonorWinding;
	    break;

	case ACTC_OUT_MAX_PRIM_VERTS:
	    *value = tc->MaxPrimVerts;
	    break;

	default:
	    *value = 0;
	    return tc->Error = ACTC_INVALID_VALUE;
	    /* break; */
    }
    return ACTC_NO_ERROR;
}

int actcGetParamu(ACTCData *tc, int param, unsigned int *value)
{
    return actcGetParami(tc, param, (int *)value);
}

static int mapEdgeTriangle(ACTCData *tc, ACTCEdge *edge, ACTCVertex *v3)
{
    ACTCTriangle tmp;
    void *r;

    tmp.FinalVert = v3;
    chartedSetLabel("triangle list");
    r = reallocAndAppend((void **)&edge->Triangles, (unsigned int*)&edge->TriangleCount,
        sizeof(tmp), &tmp);
    if(r == NULL) {
	ACTC_DEBUG(fprintf(stderr, "ACTC::mapEdgeTriangle : Couldn't allocate "
	    "%d bytes for triangles\n", sizeof(tmp) *
	    (edge->TriangleCount + 1));)
	return tc->Error = ACTC_ALLOC_FAILED;
    }

    return ACTC_NO_ERROR;
}

static int unmapEdgeTriangle(ACTCData *tc, ACTCEdge *edge, ACTCVertex *v3)
{
    int i;

    for(i = 0; i < edge->TriangleCount; i++)
	if(edge->Triangles[i].FinalVert == v3)
	    break;

    if(i == edge->TriangleCount) {
	ACTC_DEBUG(
	    fprintf(stderr, "ACTC::unmapEdgeTriangle : Couldn't find third vertex"
	        " from edge in order to delete it?!?\n");
	    abortWithOptionalDump(tc);
	)
	return tc->Error = ACTC_DATABASE_CORRUPT;
    }

    edge->Triangles[i] = edge->Triangles[edge->TriangleCount - 1];
    edge->TriangleCount --;

    return ACTC_NO_ERROR;
}

static int mapVertexEdge(ACTCData *tc, ACTCVertex *v1, ACTCVertex *v2, ACTCEdge **edge)
{
    int i;
    ACTCEdge tmp;
    void *r;

    for(i = 0; i < v1->EdgeCount; i++)
        if(v1->Edges[i].V2 == v2) {
	    v1->Edges[i].Count++;
	    break;
	}

    if(i == v1->EdgeCount) {

	tmp.V2 = v2;
	tmp.Count = 1;
	tmp.Triangles = NULL;
	tmp.TriangleCount = 0;

	chartedSetLabel("vert-to-edge mapping");
        r = reallocAndAppend((void **)&v1->Edges, (unsigned int*)&v1->EdgeCount,
	    sizeof(tmp), &tmp);
	if(r == NULL) {
	    ACTC_DEBUG(fprintf(stderr, "ACTC::mapVertexEdge : Couldn't reallocate "
	        "to %d bytes for vertex's edge list\n", sizeof(tmp) *
		v1->EdgeCount);)
	    return tc->Error = ACTC_ALLOC_FAILED;
	}
    }
    *edge = &v1->Edges[i];

    return ACTC_NO_ERROR;
}

static int unmapVertexEdge(ACTCData *tc, ACTCVertex *v1, ACTCVertex *v2)
{
    int i;

    for(i = 0; i < v1->EdgeCount; i++)
	if(v1->Edges[i].V2 == v2)
	    break;

    if(i == v1->EdgeCount) {
	ACTC_DEBUG(
	    fprintf(stderr, "ACTC::unmapVertexEdge : Couldn't find edge %d,%d"
	        " from vertex in order to unmap it?!?\n", v1->V, v2->V);
	    abortWithOptionalDump(tc);
	)
	return tc->Error = ACTC_DATABASE_CORRUPT;
    }

    v1->Edges[i].Count --;
    if(v1->Edges[i].Count == 0) {
        if(v1->Edges[i].Triangles != NULL)
	    free(v1->Edges[i].Triangles);
	v1->Edges[i] = v1->Edges[v1->EdgeCount - 1];
	v1->EdgeCount --;
    }

    return ACTC_NO_ERROR;
}

int actcAddTriangle(ACTCData *tc, unsigned int v1, unsigned int v2, unsigned int v3)
{
    ACTCVertex *vertexRec1;
    ACTCVertex *vertexRec2;
    ACTCVertex *vertexRec3;

    ACTCEdge *edge12;
    ACTCEdge *edge23;
    ACTCEdge *edge31;

    if(tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcAddTriangle : inside "
	    "BeginOutput/EndOutput\n");)
	return tc->Error = ACTC_IDLE;
    }
    if(!tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcAddTriangle : outside "
	    "BeginInput/EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }

    if(incVertexValence(tc, v1, &vertexRec1) != ACTC_NO_ERROR) goto returnError1;
    if(incVertexValence(tc, v2, &vertexRec2) != ACTC_NO_ERROR) goto free1;
    if(incVertexValence(tc, v3, &vertexRec3) != ACTC_NO_ERROR) goto free2;

    if(mapVertexEdge(tc, vertexRec1, vertexRec2, &edge12) != ACTC_NO_ERROR)
        goto free3;
    if(mapVertexEdge(tc, vertexRec2, vertexRec3, &edge23) != ACTC_NO_ERROR)
        goto free4;
    if(mapVertexEdge(tc, vertexRec3, vertexRec1, &edge31) != ACTC_NO_ERROR)
        goto free5;

    if(mapEdgeTriangle(tc, edge12, vertexRec3) != ACTC_NO_ERROR) goto free6;
    if(mapEdgeTriangle(tc, edge23, vertexRec1) != ACTC_NO_ERROR) goto free7;
    if(mapEdgeTriangle(tc, edge31, vertexRec2) != ACTC_NO_ERROR) goto free8;

    return ACTC_NO_ERROR;

    /*
     * XXX Unfortunately, while backing out during the following
     * statements, we might encounter errors in the database which
     * will not get returned properly to the caller; I take heart in
     * the fact that if such an error occurs, TC is just a moment from
     * core dumping anyway. XXX grantham 20000615
     */

free8:
    unmapEdgeTriangle(tc, edge23, vertexRec1);
free7:
    unmapEdgeTriangle(tc, edge12, vertexRec3);
free6:
    unmapVertexEdge(tc, vertexRec3, vertexRec1);
free5:
    unmapVertexEdge(tc, vertexRec2, vertexRec3);
free4:
    unmapVertexEdge(tc, vertexRec1, vertexRec2);
free3:
    decVertexValence(tc, &vertexRec3);
free2:
    decVertexValence(tc, &vertexRec2);
free1:
    decVertexValence(tc, &vertexRec1);
returnError1:
    return tc->Error;
}

int actcStartNextPrim(ACTCData *tc, unsigned int *v1Return, unsigned int *v2Return)
{
    ACTCVertex *v1 = NULL;
    ACTCVertex *v2 = NULL;
    int findResult;

    if(tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcStartNextPrim : within "
	    "BeginInput/EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }
    if(!tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcStartNextPrim : outside "
	    "BeginOutput/EndOutput\n");)
	return tc->Error = ACTC_IDLE;
    }

    findResult = findNextFanVertex(tc, &v1);
    if(findResult == ACTC_NO_ERROR)
	tc->PrimType = ACTC_PRIM_FAN;
    else if(findResult != ACTC_NO_MATCHING_VERT) {
	ACTC_DEBUG(fprintf(stderr, "actcStartNextPrim : internal "
	    "error finding next appropriate vertex\n");)
	return tc->Error = findResult;
    } else {
	findResult = findNextStripVertex(tc, &v1);
	if(findResult != ACTC_NO_ERROR && findResult != ACTC_NO_MATCHING_VERT) {
	    ACTC_DEBUG(fprintf(stderr, "actcStartNextPrim : internal "
		"error finding next appropriate vertex\n");)
	    return tc->Error = findResult;
	}
	tc->PrimType = ACTC_PRIM_STRIP;
    }

    if(findResult == ACTC_NO_MATCHING_VERT) {
	*v1Return = -1;
	*v2Return = -1;
	return tc->Error = ACTC_DATABASE_EMPTY;
    }

    v2 = v1->Edges[0].V2;

    tc->CurWindOrder = ACTC_FWD_ORDER;
    tc->VerticesSoFar = 2;

    tc->V1 = v1;
    tc->V2 = v2;

    *v1Return = v1->V;
    *v2Return = v2->V;

    ACTC_INFO(printf("starting with edge %u, %u\n", tc->V1->V, tc->V2->V);)

    return tc->PrimType;
}

static int findEdge(ACTCVertex *v1, ACTCVertex *v2, ACTCEdge **edge)
{
    int i;

    for(i = 0; i < v1->EdgeCount; i++)
        if(v1->Edges[i].V2 == v2) {
	    *edge = &v1->Edges[i];
	    return 1;
	}
    return 0;
}

int unmapEdgeTriangleByVerts(ACTCData *tc, ACTCVertex *v1, ACTCVertex *v2,
    ACTCVertex *v3)
{
    ACTCEdge *e;

    ACTC_CHECK(findEdge(v1, v2, &e));
    unmapEdgeTriangle(tc, e, v3);
    return ACTC_NO_ERROR;
}

int actcGetNextVert(ACTCData *tc, unsigned int *vertReturn)
{
    ACTCEdge *edge;
    int wasEdgeFound = 0;
    ACTCVertex *thirdVertex;
    int wasFoundReversed;

    if(tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcGetNextVert : within BeginInput/"
	    "EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }
    if(!tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcGetNextVert : outside BeginOutput/"
	    "EndOutput\n");)
	return tc->Error = ACTC_IDLE;
    }
    if(tc->PrimType == -1) {
	ACTC_DEBUG(fprintf(stderr, "actcGetNextVert : Asked for next vertex "
	    "without a primitive (got last\n    vertex already?)\n");)
	return tc->Error = ACTC_INVALID_VALUE;
    }

    if(tc->VerticesSoFar >= tc->MaxPrimVerts) {
	tc->PrimType = -1;
	return tc->Error = ACTC_PRIM_COMPLETE;
    }

    if(tc->V1 == NULL || tc->V2 == NULL) {
	tc->PrimType = -1;
	return tc->Error = ACTC_PRIM_COMPLETE;
    }

    ACTC_INFO(printf("looking for edge %u, %u\n", tc->V1->V, tc->V2->V);)

    wasFoundReversed = 0;

    if(findEdge(tc->V1, tc->V2, &edge) != 0) {
	wasEdgeFound = 1;
    } else if(!tc->HonorWinding) {
	wasFoundReversed = 1;
	if(findEdge(tc->V2, tc->V1, &edge) != 0) {
	    wasEdgeFound = 1;
	}
    }

    if(!wasEdgeFound) {
	tc->PrimType = -1;
	return tc->Error = ACTC_PRIM_COMPLETE;
    }

    thirdVertex = edge->Triangles[edge->TriangleCount - 1].FinalVert;

    ACTC_INFO(printf("third vertex = %u\n", thirdVertex->V);)
    *vertReturn = thirdVertex->V;

    if(wasFoundReversed) {
	ACTC_CHECK(unmapEdgeTriangle(tc, edge, thirdVertex));
	ACTC_CHECK(unmapEdgeTriangleByVerts(tc, tc->V1, thirdVertex, tc->V2));
	ACTC_CHECK(unmapEdgeTriangleByVerts(tc, thirdVertex, tc->V2, tc->V1));
	ACTC_CHECK(unmapVertexEdge(tc, tc->V2, tc->V1));
	ACTC_CHECK(unmapVertexEdge(tc, tc->V1, thirdVertex));
	ACTC_CHECK(unmapVertexEdge(tc, thirdVertex, tc->V2));
    } else {
	ACTC_CHECK(unmapEdgeTriangle(tc, edge, thirdVertex));
	ACTC_CHECK(unmapEdgeTriangleByVerts(tc, tc->V2, thirdVertex, tc->V1));
	ACTC_CHECK(unmapEdgeTriangleByVerts(tc, thirdVertex, tc->V1, tc->V2));
	ACTC_CHECK(unmapVertexEdge(tc, tc->V1, tc->V2));
	ACTC_CHECK(unmapVertexEdge(tc, tc->V2, thirdVertex));
	ACTC_CHECK(unmapVertexEdge(tc, thirdVertex, tc->V1));
    }
    ACTC_CHECK(decVertexValence(tc, &tc->V1));
    ACTC_CHECK(decVertexValence(tc, &tc->V2));
    ACTC_CHECK(decVertexValence(tc, &thirdVertex));

    if(tc->PrimType == ACTC_PRIM_FAN) {
        tc->V2 = thirdVertex;
    } else /* PRIM_STRIP */ {
	if(tc->CurWindOrder == ACTC_FWD_ORDER)
	    tc->V1 = thirdVertex;
	else
	    tc->V2 = thirdVertex;
	tc->CurWindOrder = !tc->CurWindOrder;
    }

    tc->VerticesSoFar++;
    return ACTC_NO_ERROR;
}

int actcTrianglesToPrimitives(ACTCData *tc, int triangleCount,
    unsigned int (*triangles)[3], int primTypes[], int primLengths[], unsigned int vertices[],
    int maxBatchSize)
{
    int r;
    int curTriangle;
    int curPrimitive;
    unsigned int curVertex;
    int prim;
    unsigned int v1, v2, v3;
    int lastPrim;
    int passesWithoutPrims;
    int trisSoFar;

    if(tc->IsInputting) {
	ACTC_DEBUG(fprintf(stderr, "actcTrianglesToPrimitives : within BeginInput/"
	    "EndInput\n");)
	return tc->Error = ACTC_DURING_INPUT;
    }
    if(tc->IsOutputting) {
	ACTC_DEBUG(fprintf(stderr, "actcTrianglesToPrimitives : within"
	    "BeginOutput/EndOutput\n");)
	return tc->Error = ACTC_DURING_OUTPUT;
    }
    curTriangle = 0;
    curPrimitive = 0;
    curVertex = 0;
    passesWithoutPrims = 0;

    actcMakeEmpty(tc);

    ACTC_CHECK(actcBeginInput(tc));
    trisSoFar = 0;
    while(curTriangle < triangleCount) {
	r = actcAddTriangle(tc, triangles[curTriangle][0],
	    triangles[curTriangle][1], triangles[curTriangle][2]);
	trisSoFar++;
	curTriangle++;
	if((trisSoFar >= maxBatchSize) ||
	    (r == ACTC_ALLOC_FAILED && curTriangle != triangleCount) ||
	    (r == ACTC_NO_ERROR && curTriangle == triangleCount)) {

	    /* drain what we got */
	    trisSoFar = 0;
	    ACTC_CHECK(actcEndInput(tc));
	    ACTC_CHECK(actcBeginOutput(tc));
	    lastPrim = curPrimitive;
	    while((prim = actcStartNextPrim(tc, &v1, &v2)) != ACTC_DATABASE_EMPTY) {
		ACTC_CHECK(prim);
		primTypes[curPrimitive] = prim;
		primLengths[curPrimitive] = 2;
		vertices[curVertex++] = v1;
		vertices[curVertex++] = v2;
		while((r = actcGetNextVert(tc, &v3)) != ACTC_PRIM_COMPLETE) {
		    ACTC_CHECK(r);
		    vertices[curVertex++] = v3;
		    primLengths[curPrimitive]++;
		}
		curPrimitive++;
	    }
	    ACTC_CHECK(actcEndOutput(tc));
	    if(r == ACTC_ALLOC_FAILED && curPrimitive == lastPrim) {
	        if(passesWithoutPrims == 0) {
		    /* not enough memory to add a triangle and */
		    /* nothing in the database, better free everything */
		    /* and try again */
		    actcMakeEmpty(tc);
		} else {
		    /* cleaned up and STILL couldn't get a triangle in; */
		    /* give up */
		    return tc->Error = ACTC_ALLOC_FAILED;
		}
		passesWithoutPrims++;
	    }
	    ACTC_CHECK(actcBeginInput(tc));
	} else
	    ACTC_CHECK(r);
	if(r == ACTC_ALLOC_FAILED)
	    curTriangle--;
    }
    ACTC_CHECK(actcEndInput(tc));

    actcMakeEmpty(tc);

    return curPrimitive;
}

/* vi:tabstop=8
 */