/*************************************************************************/
 /*                                                                       */
 /*                Centre for Speech Technology Research                  */
 /*                     University of Edinburgh, UK                       */
 /*                      Copyright (c) 1995,1996                          */
 /*                        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 :  Paul Taylor                           */
 /*                       Date   :  April 1995                            */
 /* --------------------------------------------------------------------- */
 /*                     Double linked list class                          */
 /*                                                                       */
 /* Modified by RJC, 21/7/97. Now much of the working code is in the      */
 /* UList class, this template class provides a type safe front end to    */
 /* the untyped list.                                                     */
 /*                                                                       */
 /*************************************************************************/

#ifndef __Tlist_H__
#define __Tlist_H__

#include <iostream>

using namespace std;

#include "EST_common.h"
#include "EST_UList.h"
#include "EST_TSortable.h"
#include "EST_TIterator.h"

#include "instantiate/EST_TListI.h"

class EST_String;

template<class T> class EST_TList;

template<class T> class EST_TItem : public EST_UItem {
private:
  static void *operator new(size_t not_used, void *place)
    {(void)not_used; return place;}
  static void *operator new(size_t size)
    {void *p;
    p = (void *)walloc(char,size);
     return p;} 
  static void operator delete(void *p)
    { wfree(p);}

  static EST_TItem *s_free;
  static unsigned int s_nfree;
  static unsigned int s_maxFree;

protected:
  static EST_TItem *make(const T &val);
  static void release(EST_TItem<T> *it);

  friend class EST_TList<T>;
  
public:
    T val;

    EST_TItem(const T &v) : val(v)
	    { init(); };
    EST_TItem() 
	    { init();};
};

// pretty name

typedef EST_UItem EST_Litem;

/** 

A Template doubly linked list class. This class contains doubly linked
lists of a type denoted by {\tt T}. A pointer of type \Ref{EST_Litem}
is used to access items in the list. The class supports a variety of
ways of adding, removing and accessing items in the list. For examples
of how to operate lists, see \Ref{list_example}.

Iteration through the list is performed using a pointer of type
\Ref{EST_Litem}. See \Ref{Iteration} for example code.

*/

template <class T> class EST_TList : public EST_UList 
{
  private:
    void copy_items(const EST_TList<T> &l);
  public:
    void init() { EST_UList::init(); };
    static void free_item(EST_UItem *item);

  /**@name Constructor functions */
  //@{
  /// default constructor
    EST_TList() { };
  /// copy constructor
    EST_TList(const EST_TList<T> &l);
    ~ EST_TList() { clear_and_free(free_item); }
  //@}

  /**@name Access functions for reading and writing items.
    See \Ref{EST_TList_Accessing} for examples.*/

  //@{

  /** return the value associated with the EST_Litem pointer. This
    has the same functionality as the overloaded () operator.
    */
    T &item(const EST_Litem *p)     
	    { return ((EST_TItem<T> *)p) -> val; };
  /** return a const value associated with the EST_Litem pointer.*/
    const T &item(const EST_Litem *p) const	
	    { return ((EST_TItem<T> *)p) -> val; };
    /// return the Nth value
    T &nth(int n)	   
	    { return item(nth_pointer(n)); };
    /// return a const Nth value
    const T &nth(int n) const
	    { return item(nth_pointer(n)); };

  /// return const reference to first item in list
    const T &first() const			
            { return item(head()); };
  /// return const reference to last item in list
    const T &last() const			
	    { return item(tail()); };
  /** return reference to first item in list
    * @see last 
    */
    T &first()					
            { return item(head()); };
  /// return reference to last item in list
    T &last()					
	    { return item(tail()); };

  /// return const reference to item in list pointed to by {\tt ptr}
    const T  &operator () (const EST_Litem *ptr) const
	    { return item(ptr); };
  /// return non-const reference to item in list pointed to by {\tt ptr}
    T  &operator () (const EST_Litem *ptr)
 	    { return item(ptr); };

  //@}

  /**@name Removing items in a list. 
    more.
   */
  //@{
  /** remove item pointed to by {\tt ptr}, return pointer to previous item.
 See \Ref{Removing} for example code.*/
    EST_Litem *remove(EST_Litem *ptr)
	    { return EST_UList::remove(ptr, free_item); };

    /// remove nth item, return pointer to previous item
    EST_Litem *remove_nth(int n)
	    { return EST_UList::remove(n, free_item); };

  //@}


  /**@name Adding items to a list. 
    In all cases, a complete copy of
    the item is made and added to the list. See \Ref{Addition} for examples.
   */
  //@{
  /// add item onto end of list
    void append(const T &item)
	    { EST_UList::append(EST_TItem<T>::make(item)); };
  /// add item onto start of list
    void prepend(const T &item)
	    { EST_UList::prepend(EST_TItem<T>::make(item)); };

  /** add {\tt item} after position given by {\tt ptr}, return pointer
    to added item. */

    EST_Litem *insert_after(EST_Litem *ptr, const T &item)
	    { return EST_UList::insert_after(ptr, EST_TItem<T>::make(item)); };

  /** add {\tt item} before position given by {\tt ptr}, return
      pointer to added item. */

    EST_Litem *insert_before(EST_Litem *ptr, const T &item)
	    { return EST_UList::insert_before(ptr, EST_TItem<T>::make(item)); };

  //@}

  /**@name Exchange */
  //@{
  /// exchange 1
    void exchange(EST_Litem *a, EST_Litem *b)
	    { EST_UList::exchange(a, b); };
  /// exchange 2
    void exchange(int i, int j)
	    { EST_UList::exchange(i,j); };
  /// exchange 3    
   static void exchange_contents(EST_Litem *a, EST_Litem *b);
  //@}

  /**@name General functions */
  //@{
  /// make full copy of list
      EST_TList<T> &operator=(const EST_TList<T> &a); 
  /// Add list onto end of existing list
    EST_TList<T> &operator +=(const EST_TList<T> &a);

  /// print list
    friend ostream& operator << (ostream &st, EST_TList<T> const &list) {
        EST_Litem *ptr; 
        for (ptr = list.head(); ptr != 0; ptr = ptr->next()) 
            st << list.item(ptr) << " "; 
        return st;
    }

  /// remove all items in list
    void clear(void) 
	    { clear_and_free(free_item); };
  //@}

  // Iteration support

protected:
  struct IPointer {  EST_Litem *p; };

  void point_to_first(IPointer &ip) const { ip.p = head(); }
  void move_pointer_forwards(IPointer &ip) const { ip.p = ip.p->next(); }
  bool points_to_something(const IPointer &ip) const { return ip.p != NULL; }
  T &points_at(const IPointer &ip) { return item(ip.p); }

  friend class EST_TIterator< EST_TList<T>, IPointer, T >;
  friend class EST_TRwIterator< EST_TList<T>, IPointer, T >;

public:
  typedef T Entry;
  typedef EST_TIterator< EST_TList<T>, IPointer, T > Entries;
  typedef EST_TRwIterator< EST_TList<T>, IPointer, T > RwEntries;

};


template<class T> 
bool operator==(const EST_TList<T> &a, const EST_TList<T> &b)
{ 
    return EST_UList::operator_eq(a, b, EST_TSortable<T>::items_eq); 
}

template<class T> 
bool operator!=(const EST_TList<T> &a, const EST_TList<T> &b)
{ 
    return !(a==b); 
}

template<class T> 
int index(EST_TList<T> &l, T& val, bool (*eq)(const EST_UItem *, const EST_UItem *) = NULL)
{ 
  EST_TItem<T> item(val);
  return EST_UList::index(l, item, eq?eq:EST_TSortable<T>::items_eq); 
}

template<class T> 
void sort(EST_TList<T> &a, bool (*gt)(const EST_UItem *, const EST_UItem *) = NULL)
{ 
    EST_UList::sort(a, gt?gt:EST_TSortable<T>::items_gt); 
}

template<class T> 
void ptr_sort(EST_TList<T> &a)
{ 
    EST_UList::sort(a, EST_TSortable<T *>::items_gt); 
}

template<class T> 
void qsort(EST_TList<T> &a, bool (*gt)(const EST_UItem *, const EST_UItem *) = NULL)
{ 
    EST_UList::qsort(a, gt?gt:EST_TSortable<T>::items_gt, EST_TList<T>::exchange_contents); 
}

template<class T> 
void ptr_qsort(EST_TList<T> &a)
{ 
    EST_UList::qsort(a, EST_TSortable<T *>::items_gt, EST_TList<T>::exchange_contents); 
}

template<class T> 
void sort_unique(EST_TList<T> &l)
{ 
    EST_UList::sort_unique(l, 
			   EST_TSortable<T>::items_eq, 
			   EST_TSortable<T>::items_gt,
			   EST_TList<T>::free_item); 
}

template<class T> 
void merge_sort_unique(EST_TList<T> &l, EST_TList<T> &m)
{  
    EST_UList::merge_sort_unique(l, m,
				 EST_TSortable<T>::items_eq, 
				 EST_TSortable<T>::items_gt,
				 EST_TList<T>::free_item); 
}

template<class T>
const char *error_name(EST_TList<T> val) { (void)val; return "<<TLIST>>"; }

#endif