/*
 * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *        notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *        notice, this list of conditions and the following disclaimer in the
 *        documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the author nor the names of any co-contributors
 *        may be used to endorse or promote products derived from this software
 *        without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

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

#include "tmalloc.h"
#include "psort.h"

/*
 * this defines only for faster code
 */
#define insert_full(val)  do {                                             \
	tmp = sobj->last;                                                  \
        if ( sobj->free )                                                  \
                (*(sobj->free))( tmp->value );                             \
        sobj->last = sobj->last->prev; /* current last */                  \
        tmp->value = (val);                                                \
	curitem = sobj->last;                                              \
	curitem->next = tmp->prev = tmp->next = NULL;                      \
	                                                                   \
        do {                                                               \
                if ( (*(sobj->cmpr))( curitem->value, (val) ) <= 0 ) {     \
			tmp->next = curitem->next;                         \
			tmp->prev = curitem;                               \
			                                                   \
			if ( curitem->next ) /* not last */                \
				curitem->next->prev = tmp;                 \
			else                                               \
				sobj->last = tmp;                          \
			curitem->next = tmp;                               \
                        break;                                             \
                }                                                          \
                curitem = curitem->prev;                                   \
        } while ( curitem );                                               \
	/* insert to first position */                                     \
        if ( !tmp->prev ) {                                                \
		sobj->first->prev = tmp;                                   \
		tmp->next = sobj->first;                                   \
		sobj->first = tmp;	                                   \
        }                                                                  \
} while(0)

#define insert_notfull( val ) do {                                         \
	tmp = &(sobj->buf[sobj->curlen]);                                  \
	tmp->value = (val);                                                \
	previtem = NULL;                                                   \
	curitem = sobj->first;                                             \
	do {                                                               \
		if ( (*(sobj->cmpr))( curitem->value, tmp->value ) > 0 ) { \
			tmp->next = curitem;                               \
			curitem->prev = tmp;                               \
			tmp->prev = previtem;                              \
			if ( previtem )                                    \
				previtem->next = tmp;                      \
			else {                                             \
				sobj->first->prev = tmp;                   \
				sobj->first = tmp;                         \
			}                                                  \
			break;                                             \
		}                                                          \
		previtem = curitem;                                        \
		curitem = curitem->next;                                   \
	} while( curitem );                                                \
	if ( ! tmp->next ) { /*not inserted*/                              \
		sobj->last->next = tmp;                                    \
		tmp->prev = sobj->last;                                    \
		sobj->last = tmp;                                          \
	}                                                                  \
} while(0) 



/*
 * Initialization
 * If input options are invalid, return -1
 * if no memory return 1
 * If success return 0
 */
int 
PS_init( SORT* sobj, int buflen, compare_sort func, ffree ffunc ) {
	if ( ! sobj ) return -1;
	if ( ! func ) return -1;
	if ( buflen <= 0 ) return -1;

	sobj->buf = (SORTITEM*)t0malloc( sizeof(SORTITEM)*buflen );

	sobj->buflen = buflen;
	sobj->cmpr   = func;
	sobj->free  = ffunc;
	sobj->curlen = 0;

	sobj->first = sobj->last = sobj->buf; 
	sobj->curitem = NULL; 

	return 0;
}

/*
 * finish...
 * clear memory
 */
void  
PS_clear( SORT* sobj ) {
	if ( sobj->free ) {
		int i;
		for(i=0; i<sobj->curlen; i++ )
			(*(sobj->free))( sobj->buf[i].value );
	}
	if ( sobj->buf ) 
		tfree( sobj->buf );
	memset( (void*)sobj, 0, sizeof(SORT) );
}

/*
 * Reset sort object..
 */
void 
PS_reset( SORT* sobj ) {
	int i;

	if ( sobj->free ) {
		for(i=0; i<sobj->curlen; i++ )
			(*(sobj->free))( sobj->buf[i].value );
	}
	memset( (void*)sobj->buf, 0, sizeof(SORTITEM)*sobj->buflen );
	sobj->curlen = 0;
	sobj->first = sobj->last = sobj->buf; 
	sobj->curitem = NULL; 
}

/*
 * Insert
 */
int 
PS_insert( SORT* sobj, void* nobj ) {
	SORTITEM *curitem, *previtem, *tmp;

	/* first insertion */
	if ( ! sobj->curlen  ) { 
		sobj->first->value = nobj;
		sobj->curlen++;
		return 1;
	}

	if ( sobj->curlen == sobj->buflen ) {
		if ( (*(sobj->cmpr))( sobj->last->value, nobj ) > 0 ) {
			if ( sobj->buflen == 1 ) {
				if ( sobj->free ) 
					(*(sobj->free))( sobj->last->value );
				sobj->last->value = nobj;
			} else 
				insert_full( nobj );
			return 1;
		}
	} else {
		insert_notfull( nobj );
		sobj->curlen++;
		return 1;
	}

	return 0;
}

static compare_sort compareobject;
static int highlevelcompare( const void *a, const void *b ) {
	return (*compareobject)(  *(void**)a, *(void**)b );	
} 

/*
 * Insert array, if defined free function, 
 * unused item will be freeed
 */

#define RECOMMEND_M(N)	( ((N)<8000) ? ( 23.0+1.5*pow((N),0.6) ) : pow(( 8.05 * log((N)) - 53.53 ),2.0) )
void
PS_bulkinsert( SORT* sobj, void** nobjs, int len ) {
	register SORTITEM *curitem, *tmp;
	register void** ptr = nobjs;

	if ( !sobj->curlen ) {
		int initlen = len;
		if ( len > sobj->buflen ) {
			if ( sobj->buflen < RECOMMEND_M( len ) )
				initlen = sobj->buflen;
		}
		curitem = sobj->first;
		compareobject = sobj->cmpr;
		if ( initlen > 1 )
			qsort( nobjs, initlen, sizeof(void*), highlevelcompare );
		ptr = nobjs; 
		while( ptr - nobjs < initlen &&  sobj->curlen != sobj->buflen ) {
			curitem->value = *ptr;
			if ( sobj->curlen ) {
				curitem->prev = curitem - 1;
				curitem->prev->next = curitem;
			}
			curitem++;
			sobj->curlen++;
			ptr++;
		}
		sobj->last = curitem-1;

		if ( sobj->free && initlen != sobj->buflen ) {
			while( ptr - nobjs < len ) { 
				(*(sobj->free))( *ptr ); 
				ptr++;
			}
			return;
		} 
	} else {
		while( ptr - nobjs < len &&  sobj->curlen != sobj->buflen ) {
			PS_insert( sobj, *ptr ); /* buflen is very small, so we can use function call */ 
			ptr++;
		}
	}

	if ( sobj->free ) {
		while( ptr - nobjs < len ) {
			if ( (*(sobj->cmpr))( sobj->last->value, *ptr ) > 0 ) {
				if ( sobj->buflen == 1 ) {
					(*(sobj->free))( sobj->last->value );
					sobj->last->value = *ptr;
				} else 
					insert_full( *ptr );
			} else
				(*(sobj->free))( *ptr );  
			ptr++;
		}
	} else {
		while( ptr - nobjs < len ) {
			if ( (*(sobj->cmpr))( sobj->last->value, *ptr ) > 0 ) {
				if ( sobj->buflen == 1 )
					sobj->last->value = *ptr;
				else 
					insert_full( *ptr );
			}
			ptr++;
		}
	}
} 

/*
 * insert a-la qsort, require sobj->free = NULL
 */
int 
PS_bulkplain( SORT* sobj, void* nobjs, int size, int len ) {
	register SORTITEM *curitem, *tmp;
	register char* ptr = (char*)nobjs;

	if ( sobj->free )
		return 1;

	if ( !sobj->curlen ) {
		int initlen = len;
		if ( len > sobj->buflen ) {
			if ( sobj->buflen < RECOMMEND_M( len ) )
				initlen = sobj->buflen;
		}
		curitem = sobj->first;
		if ( initlen > 1 )
			qsort( nobjs, initlen, size, sobj->cmpr );
		ptr = (char*)nobjs; 
		initlen *= size;
		while( ptr - (char*)nobjs < initlen &&  sobj->curlen != sobj->buflen ) {
			curitem->value = (void*)ptr;
			if ( sobj->curlen ) {
				curitem->prev = curitem - 1;
				curitem->prev->next = curitem;
			}
			curitem++;
			sobj->curlen++;
			ptr += size;
		}
		sobj->last = curitem-1;

	} else {
		while( ( ptr - (char*)nobjs )/size < len &&  sobj->curlen != sobj->buflen ) {
			PS_insert( sobj, (void*)ptr ); /* buflen is very small, so we can use function call */ 
			ptr += size;
		}
	}

	len *= size;
	while( ptr - (char*)nobjs < len ) {
		if ( (*(sobj->cmpr))( sobj->last->value, (void*)ptr ) > 0 ) {
			if ( sobj->buflen == 1 )
				sobj->last->value = (void*)ptr;
			else 
				insert_full( (void*)ptr );
		}
		ptr += size;
	}

	return 0;
}

/*
 * init_iterator, return 0 if success
 */
int 
PS_init_iterator( SORT* sobj, int start ) {
	if ( sobj->curlen <= 0 || start<0 || start >= sobj->curlen )
		return 1;
	sobj->curitem = sobj->first;
	while ( start ) {
		sobj->curitem = sobj->curitem->next;
		start--;
	}
	return 0;
} 

/*
 * return next sorted value or NULL
 */
void* 
PS_getnext( SORT* sobj ) {
	void *value = NULL;
	if ( sobj->curitem ) 
		value = sobj->curitem->value;
	else 
		return NULL;

	sobj->curitem =  ( sobj->curitem->next == NULL || sobj->curitem->next == sobj->first ) ? NULL : sobj->curitem->next; 

	return value;
}

int
PS_number( SORT* sobj ) {
	return sobj->curlen;
}