/*
 * Copyright (c) 2004-2005 Chirok Han
 *
 * This file is part of fig2pstricks.
 *
 * Fig2pstricks 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 of the License, or
 * (at your option) any later version.
 * 
 * Fig2pstricks 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 fig2pstricks; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 * 
 * Contact: beanerjo@yahoo.com
 */

#include "fig2pstricks.h"

#ifndef NEXTNODE
#define NEXTNODE(p) ((p)->next)

NODE create_node(int depth, char *ptr)
{
    NODE pn;
    pn = (NODE)malloc(sizeof(struct tagNODE));
    pn->ptr = ptr;
    pn->depth = depth;
    pn->prev = pn;
    pn->next = pn;
    return pn;
}

void delete_node(NODE pn)
{
    NODE qn = pn;
    while (pn->next!=pn) {
	pn = qn;
	qn = pn->next;
	free(pn);
    }
    free(qn);
}

NODE first_node(NODE pn)
{
    while (pn->prev!=pn) pn = pn->prev;
    return pn;
}

NODE last_node(NODE pn)
{
    while (pn->next!=pn) pn = pn->next;
    return pn;
}

void rewind_node(NODE *pn)
{
    *pn = first_node(*pn);
}

void windup_node(NODE *pn)
{
    *pn = last_node(*pn);
}

void append_node(NODE pn, int depth, char *ptr)
{
    NODE qn;
    qn = create_node(depth, ptr);
    pn = last_node(pn);
    pn->next = qn;
    qn->prev = pn;
}

void prepend_node(NODE pn, int depth, char *ptr)
{
    NODE qn;
    qn = create_node(depth, ptr);
    pn = first_node(pn);
    pn->prev = qn;
    qn->next = pn;
}

int sort_by_depth(NODE *pn) /* big to small */
{
    int i, j, ntmp, n;
    int *depths, ndepths, ndepthproper, prevdepth=-1, ndepthchg=0;
    NODE qn=*pn, rn;

    // get the number of depth changes
    while (qn!=qn->next) {
	if (prevdepth!=qn->depth) {
	    ndepthchg++;
	    prevdepth=qn->depth;
	}
	qn=qn->next; 
    }
    if (prevdepth!=qn->depth) ndepthchg++;
    if (ndepthchg==1) return 1;

    ndepthchg++;
    // make the set of depths
    depths = (int*)malloc(ndepthchg*sizeof(int));
    for (i=0; i<ndepthchg; i++) depths[i]=-1;

    ndepths = 0;
    ndepthproper = 0;
    qn = *pn;
    while (1) {
	for (i=0; i<ndepthchg; i++)
	    if (depths[i]<0 || qn->depth==depths[i]) break;
	if (depths[i]<0) {
	    depths[i]=qn->depth;
	    ndepths++;
	    if (qn->depth<INT_MAX) ndepthproper++;
	}
	if (qn==qn->next) break;
	else qn=qn->next;
    }

    // sort depths
    for (i=0; i<ndepths-1; i++) {
	for (j=i+1; j<ndepths; j++) {
	    if (depths[j]>depths[i]) {
		ntmp = depths[j];
		depths[j] = depths[i];
		depths[i] = ntmp;
	    }
	}
    }

    // write - very inefficient
    rn = NULL;
    for (i=0; i<ndepths; i++) {
	n = depths[i];
	qn = *pn;
	while (1) {
	    if (n==qn->depth) {
		if (rn) append_node(rn, n, qn->ptr);
		else rn = create_node(n, qn->ptr);
	    }
	    if (qn==qn->next) break;
	    else qn=qn->next;
	}
    }
    //delete_node(*pn);  // What is happening here?
    *pn = rn;
    return ndepthproper;
}

void print_node(NODE pn)
{
    while (1) {
	printf("*** %4d: %s\n", pn->depth, pn->ptr);
	if (pn==pn->next) break;
	else pn=pn->next;
    }
}

#endif