/*************************************************************************/
/*                                                                       */
/*                Centre for Speech Technology Research                  */
/*                     University of Edinburgh, UK                       */
/*                      Copyright (c) 1997,1998                          */
/*                        All Rights Reserved.                           */
/*  Permission is hereby granted, free of charge, to use and distribute  */
/*  this software and its documentation without restriction, including   */
/*  without limitation the rights to use, copy, modify, merge, publish,  */
/*  distribute, sublicense, and/or sell copies of this work, and to      */
/*  permit persons to whom this work is furnished to do so, subject to   */
/*  the following conditions:                                            */
/*   1. The code must retain the above copyright notice, this list of    */
/*      conditions and the following disclaimer.                         */
/*   2. Any modifications must be clearly marked as such.                */
/*   3. Original authors' names are not deleted.                         */
/*   4. The authors' names are not used to endorse or promote products   */
/*      derived from this software without specific prior written        */
/*      permission.                                                      */
/*  THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK        */
/*  DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING      */
/*  ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT   */
/*  SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE     */
/*  FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES    */
/*  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN   */
/*  AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,          */
/*  ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF       */
/*  THIS SOFTWARE.                                                       */
/*                                                                       */
/*************************************************************************/
/*                                                                       */
/*                 Author: Richard Caley (rjc@cstr.ed.ac.uk)             */
/*                   Date: Mon Jul 21 1997                               */
/* --------------------------------------------------------------------  */
/* Untyped list used as the basis of the TList class                     */
/*                                                                       */
/*************************************************************************/
#include <EST_UList.h>

void EST_UList::clear_and_free(void (*item_free)(EST_UItem *p))
{
    EST_UItem *q, *np;

    for (q=head(); q != 0; q = np)
    {
	np=q->next();
	if (item_free)
	    item_free(q);
	else
	    delete q;
    }
    h = t = 0;
}

int EST_UList::length() const
{
    EST_UItem *ptr;
    int n = 0;

    for (ptr = head(); ptr != 0; ptr = ptr->next())
	++n;
    return n;
}

int EST_UList::index(EST_UItem *item) const
{
    EST_UItem *ptr;
    int n = 0;
    
    for (ptr = head(); ptr != 0; ptr = ptr->next(), ++n)
	if (item == ptr)
	    return n;

    return -1;
}

EST_UItem *EST_UList::nth_pointer(int n) const
{
    EST_UItem *ptr;
    int i;
    
    for (i = 0, ptr = head(); ptr != 0; ptr = ptr->next(), ++i)
      if (i == n)
	return ptr;

    cerr << "Requested item #" << n << " off end of list" << endl;
    return head();
}

EST_UItem * EST_UList::remove(EST_UItem *item,
			      void (*free_item)(EST_UItem *item))
{
    if (item == 0)
	return 0;

    EST_UItem *prev = item->p;
    if (item->p == 0)  // at start
	h = item->n;
    else
	item->p->n = item->n;
    if (item->n == 0)  // at end
	t = item->p;
    else
	item->n->p = item->p;
	
    if (free_item)
	free_item(item);
    else
	delete item;
    
    return prev;
}

EST_UItem * EST_UList::remove(int n,
			      void (*item_free)(EST_UItem *item))
{
    return remove(nth_pointer(n), item_free);
}

// This should check if the incoming prev_item actually is in the list

EST_UItem *EST_UList::insert_after(EST_UItem *prev_item, EST_UItem *new_item)
{
    if (new_item == 0)
	return new_item;
    if (prev_item == 0)	// insert it at start of list
    {
	new_item->n = h;
	h = new_item;
    }
    else
    {
	new_item->n = prev_item->n;
	prev_item->n = new_item;
    }
    new_item->p = prev_item;
    if (new_item->n == 0)
	t = new_item;
    else
	new_item->n->p = new_item;
    
    return new_item;
}

EST_UItem *EST_UList::insert_before(EST_UItem *next_item, EST_UItem *new_item)
{
    if (new_item == 0)
	return new_item;
    if (next_item == 0)	// put it on the end of the list
    {
	new_item->p = t;
	t = new_item;
    }
    else
    {
	new_item->p = next_item->p;
	next_item->p = new_item;
    }
    new_item->n = next_item;
    if (new_item->p == 0)
	h = new_item;
    else
	new_item->p->n = new_item;
    
    return next_item;
}

void EST_UList::exchange(EST_UItem *a, EST_UItem *b)
{

    if (a==b)
	return;
    
    if ((a==0) || (b==0))
    {
	cerr << "EST_UList:exchange: can't exchange NULL items" << endl;
	return;
    }

    // I know this isn't very readable but there are eight pointers
    // that need to be changed, and half of them are trivial back pointers
    // care need only be taken when b and a are adjacent, this actual
    // sets p and n twice if they are adjacent but still gets the right answer
    EST_UItem *ap=a->p,*an=a->n,*bn=b->n,*bp=b->p;

    a->n = bn == a ? b : bn;
    if (a->n)
      a->n->p = a;
    a->p = bp == a ? b : bp;
    if (a->p)
      a->p->n = a;

    b->n = an == b ? a : an;
    if (b->n)
      b->n->p = b;
    b->p = ap == b ? a : ap;
    if (b->p)
      b->p->n = b;

    // Fix t and h 
    if (a == h)
	h = b;
    else if (b == h)
	h = a;
    else if (a == t)
	t = b;
    else if (b == t)
	t = a;
	     
}

void EST_UList::exchange(int i, int j)
{
    
    EST_UItem *p;
    EST_UItem *a=0,*b=0;
    int k;
    
    for (k=0,p = head(); p != 0; p = p->next(),k++)
    {
	if(i==k)
	    a = p;
	if(j==k)
	    b = p;
    }
    
    if ((a==0) || (b==0))
    {
	cerr << "EST_UList:exchange: can't exchange items " << i << 
	    " and " << j << " (off end of list)" << endl;
	return;
    }
    
    exchange(a,b);
}

void EST_UList::reverse()
{
    EST_UItem *p,*q;

    for (p=head(); p != 0; p=q)
    {
	q = p->n;
	p->n = p->p;
	p->p = q;
    }
    q = h;
    h = t;
    t = q;
}

void EST_UList::append(EST_UItem *new_item)
{

    if (new_item == 0) return;

    new_item->n = 0;
    new_item->p = t;
    if (t == 0)
	h = new_item;
    else
	t->n = new_item;
    t = new_item;
}

void EST_UList::prepend(EST_UItem *new_item)
{
    if (new_item == 0) return;

    new_item->p = 0;
    new_item->n = h;
    if (h == 0)
	t = new_item;
    else
	h->p = new_item;
    h = new_item;
}

bool EST_UList::operator_eq(const EST_UList &a, 
			    const EST_UList &b, 
			    bool (*eq)(const EST_UItem *item1, const EST_UItem *item2))
{
    EST_UItem *p,*q;
    q=b.head();
    for (p = a.head(); p != NULL; p = p->next()){
	if(q == NULL)
	    return false;
	if(eq(q, p))
	    q=q->next();
	else
	    return false;
    }
    
    if(q == NULL)
	return true;
    else
	return false;
}

int EST_UList::index(const EST_UList &l, 
		     const EST_UItem &val, 
		     bool (*eq)(const EST_UItem *item1, const EST_UItem *item2))
{
    
    EST_UItem *ptr;
    int n = 0;
    
    for (ptr = l.head(); ptr != 0; ptr = ptr->next(), ++n)
	if (eq(&val,ptr))
	    return n;
    
    return -1;
}

void EST_UList::sort(EST_UList &l,
		     bool (*gt)(const EST_UItem *item1, 
				const EST_UItem *item2))
{
    
    // just bubble sort for now
    // use EST_String::operator > for comparisons
    
    EST_UItem *l_ptr,*m_ptr;
    bool sorted=false;
    
    while(!sorted){
	sorted=true;
	
	for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
	    
	    m_ptr=l_ptr->next();
	    if(m_ptr != 0)
		if(gt(l_ptr, m_ptr)){
		    l.exchange(l_ptr,m_ptr);
		    sorted=false;
		}
	}
    }
    
}

// quicksort from 'Algorithms'
// by Cormen, Leiserson & Rivest

static EST_UItem *partition(EST_UItem *p, EST_UItem *r,
			    bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
			    void (*exchange)(EST_UItem *item1, EST_UItem *item2))
{
    // this can be tidied up / sped up
    
    EST_UItem *i,*j,*i2,*j2;
    EST_UItem *x = p;
    
    i = p;
    j = r;
    
    while(true){
	
	while(gt(j, x) )
	    j = j->prev();
	
	while(gt(x, i))
	    i = i->next();
	
	if((i != j) && (i->prev() != j)){
	    i2=i;
	    j2=j;
	    i=i->next();
	    j=j->prev();
	    exchange(i2,j2);
	    
	}else
	    return j;
	
    }
    return NULL;
}


static void qsort_sub(EST_UList &l, EST_UItem *p, EST_UItem *r,
		      bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
		      void (*exchange)(EST_UItem *item1, EST_UItem *item2))
{
    EST_UItem *q;
    if(p != r){
	q = partition(p,r, gt, exchange);
	qsort_sub(l,p,q, gt, exchange);
	qsort_sub(l,q->next(),r, gt, exchange);
    }
}

void EST_UList::qsort(EST_UList &l,
		      bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
		      void (*exchange)(EST_UItem *item1, EST_UItem *item2))
{
    qsort_sub(l,l.head(),l.tail(), gt, exchange);
}


void EST_UList::sort_unique(EST_UList &l,
			    bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
			    bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
			    void (*item_free)(EST_UItem *item))
{
    // as sort(..) but delete any repeated items
    
    EST_UItem *l_ptr,*m_ptr;
    bool sorted=false;
    
    while(!sorted){
	sorted=true;
	
	for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
	    
	    m_ptr=l_ptr->next();
	    if(m_ptr != 0)
            {
		if(gt(l_ptr, m_ptr)){
		    l.exchange(l_ptr,m_ptr);
		    sorted=false;
		} else if(eq(l_ptr,  m_ptr)){
		    l.remove(m_ptr, item_free);
		    sorted=false;
		}
            }
	}
    }
}

void EST_UList::merge_sort_unique(EST_UList &l, EST_UList &m,
				  bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
				  bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
				  void (*item_free)(EST_UItem *item))
{
    // keep all unique items in l, and add any new items from m to l
    
    EST_UItem *l_ptr,*m_ptr;
    bool flag;
    
    // make sure
    sort_unique(l, eq, gt, item_free);
    
    for(m_ptr=m.head(); m_ptr != 0; m_ptr=m_ptr->next()){
	
	// try and put item from m in list 
	flag=false;
	for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
	    if( gt(l_ptr, m_ptr) ){
		l.insert_before(l_ptr, m_ptr);
		flag=true;
		break;
	    }else if( eq(m_ptr, l_ptr) ){
		flag=true;
		break;
	    }
	}
	// or try and append it
	if(!flag && ( gt(m_ptr, l.tail()) ) )
	    l.append(m_ptr);
    }
}