/*********************************************************************
 * This file is part of the cpplibs suite.
 *
 * Copyright (C) 2001 Topi Mäenpää and Jaakko Viertola
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.30 $
 *********************************************************************/

#ifndef _LISTCLASS_H
#define _LISTCLASS_H

#include "Iterator.h"
#include "Util.h"
#include "Boolean.h"
#include "io/IO.h"

#include <iostream>
#include <string>

#include <stdarg.h>
#include <values.h>

/**
 * Loop through all list items from index 0 to length-1.
 **/
#define AllListItems(i,lst) for (i=0;i<lst.getLength();i++)

namespace util
{
	template <class T> class List;
	template <class U> std::ostream& operator<< (std::ostream& sout, const List<U>& lst);
	template <class U> std::istream& operator>> (std::istream& sin, List<U>& lst);

	/**
	 * List is the default implementation of a growing list that allocates
	 * new memory as needed. The method implementations provide direct
	 * access to the internal array of the list.
	 **/
	template <class T> class List : public Iterator<T>
	{
	public:
		/**
		 * Constructs a new list with the given initial capacity
		 * and block size.
		 * @param initialSlots the number of items that can the list can
		 *        initially hold without expanding
		 * @param blockSize the number of slots the list will expand each
		 *        time its capacity is exceeded
		 **/
		List(int initialSlots = 16, int blockSize = 16);
		/**
		 * Create a copy of a list.
		 **/
		List(const List& other);
		/**
		 * Create a typecasted copy of a list. The iterator of the
		 * typecasted copy is reset to 0.
		 **/
		template <class U> List(const List<U>& other);

		/**
		 * Initialize a list with the given data. If the <i>release</i>
		 * flag is true, the memory pointed by <i>data</i> is used as the
		 * internal storage and deleted upon the destruction of the list.
		 * If the release flag is true, one cannot rely on the data
		 * pointer any more as it might change when adding new elements to
		 * the list. If the release flag is false, the data is copied.
		 *
		 * @param data a pointer to the data to be used as an internal
		 *        array or to be copied.
		 * @param len the number of entries in data
		 * @param release if true, list will take the ownership of the pointer.
		 **/
		List(T* data, int len, bool release=false);
		
		/**
		 * Release all resources.
		 **/
		virtual ~List();

		/**
		 * Add an element to the end of the list.
		 * @param element the element to be added
		 **/
		virtual void addElement(const T& element);
		/**
		 * Remove the given element from the list. This method calls the
		 * indexOf(element) method to obtain the element's index in the
		 * list and then removes it by calling removeElementAt(index).
		 * @param element the element to be removed
		 **/
		virtual void removeElement(const T& element);
		/**
		 * Add all elements in a list to this list. This method goes
		 * through the list and calls addElement(element) for each list
		 * item.
		 * @param other a list of elements to be added to this list
		 **/
		virtual void addElements(const List& other);

		/**
		 * Add a variable number of elements into the list at once. An
		 * example:<br>
		 * <pre>
		 * List<int> lst;
		 * lst.addElements(5,1,2,3,4,5);
		 * </pre>
		 *
		 * This method calls addElement(const T&) for each element
		 * encountered. If the count or the type of the elements is not
		 * correct, the behavior is undefined.<p>
		 *
		 * Note that only elementary types can be used with this method.
		 * Complex types (except for strings) cause a compile-time error.
		 * For strings, there is a template specialization that takes
		 * <i>const char*</i> parameters.
		 *
		 * <b>Warning!</b> Take extreme care to ensure that the elements
		 * you give in the parameter list are of correct type. Make sure
		 * that the compiler understands what you mean. Examples:
		 *
		 * <pre>
		 * List&lt;float&gt; lst;
		 * lst.addElements(3,1,2,3);          //WRONG! values are passed as ints
		 * lst.addElements(3,1.0,2.0,3.0);    //WRONG! values are passed as doubles
		 * lst.addElements(3,1.0f,2.0f,3.0f); //correct
		 * </pre>
		 *
		 * @param count the number of elements to add
		 * @param ... the elements to add, all of type T
		 **/
		void addElements(int count, ...);
		/**
		 * Remove all elements in a list from this list. This method goes
		 * through the list and calls removeElement(element) for each list
		 * item.
		 * @param other a list of elements to be removed from this list
		 **/
		virtual void removeElements(const List& other);
		/**
		 * Find the index of the given element.
		 * @param element the element to be found
		 * @return the index of the element, or -1 if it was not found
		 **/
		virtual int indexOf(const T& element) const;
		/**
		 * Returns indexOf(element) != -1.
		 **/
		virtual bool contains(const T& element) const { return indexOf(element) != -1; }

		/**
		 * Insert an element in the middle of the list. All elements at or
		 * after the given index are shifted to right.
		 * @param element the element to be inserted
		 * @param index the index of the element
		 **/
		virtual void insertElementAt(const T& element, int index);
		/**
		 * Remove an element at the given index. The elements following
		 * the removed one are shifted to left.
		 * @param index the element's index
		 * @return the removed element
		 **/
		virtual T removeElementAt(int index);
		/**
		 * Get a reference to the object at the given index.
		 **/
		virtual T& elementAt(int index) { return _internalArray[index]; }
		/**
		 * Get a reference to the object at the given index.
		 **/
		virtual const T& elementAt(int index) const { return _internalArray[index]; }
		/**
		 * Get the object at the given index.
		 **/
		virtual T getElementAt(int index) const { return _internalArray[index]; }
		/**
		 * Set the element at a given index.
		 **/
		void setElementAt(const T& element, int index) { _internalArray[index] = element; }
		/**
		 * Make the list empty and resize the internal array to its original size.
		 **/
		void clear(void);
		/**
		 * Get the current number of stored entries in the list.
		 **/
		int getLength(void) const { return _iCurrentItems; }

		/**
		 * Get a pointer to the first item of the internal data array.
		 **/
		const T* getData(void) const { return _internalArray; }

		/**
		 * Get a pointer to the first item of the internal data array.
		 **/
		T* getData(void) { return _internalArray; }

		/**
		 * Take the ownership of the internal element array. When calling
		 * this method, the length of the list will be set to zero, and
		 * the pointer to the internal data to NULL. A pointer to the
		 * internal data array is returned, and it must be deleted by the
		 * caller (with delete[]).
		 **/
		T* releaseData(void)
		{
			_iSize = _iCurrentItems = 0;
			T* tmp = _internalArray;
			_internalArray = NULL;
			return tmp;
		}
		
		/**
		 * Set the length of this vector to 'length'. If the new length is
		 * smaller than the current one, the list will be truncated. If
		 * the new length is larger than the current one, the list will
		 * grow, but the new entries will be in undefined state. For class
		 * types the state will be that defined by its default constructor.
		 * @param length the new length
		 **/
		void setLength(int length);

		/**
		 * Set the length of this vector to <i>length</i>. Fill newly
		 * allocated entries (if any) with <i>value</i>.
		 *
		 * @param length the new length
		 * @param value value for new entries
		 **/
		void setLength(int length, T value);

		/**
		 * Set the maximum number of items this list will be able to hold
		 * without allocating new memory. If 'size' is smaller than the
		 * current length of the list, the capacity will be set to the
		 * current length.		 
		 * @param size the new capacity.
		 **/
		void setCapacity(int size);

		/**
		 * Set the capacity of this list to the current number of etries
		 * so that no unnecessary memory is allocated.
		 **/
		void fix(void) { setCapacity(_iCurrentItems); }

		/**
		 * Get the number of items this list expands each time its
		 * internal array becomes full.
		 **/
		int getBlockSize(void) const { return _iBlockSize; }
		/**
		 * Get the number of items this list will hold without expanding.
		 **/
		int getCapacity(void) const { return _iSize; }
		/**
		 * Get the size this list was initialized with.
		 **/
		int getInitialSize(void) const { return _iInitialSize; }

		/**
		 * Add the values in <i>other</i> to the corresponding values in
		 * this list. List lengths must be equal to each other. Operator +=
		 * must be defined for the content type.
		 * @param other the list whose contents are to be added to the
		 *        corresponding items in this list
		 **/
		void add(const List& other);
		/**
		 * Subtract the values in <i>other</i> from the corresponding values in
		 * this list. List lengths must be equal to each other. Operator -=
		 * must be defined for the content type.
		 * @param other the list whose contents are to be subtracted from the
		 *        corresponding items in this list
		 **/
		void subtract(const List& other);
		/**
		 * Multiply the values in <i>other</i> from the corresponding values in
		 * this list. List lengths must be equal to each other. Operator *=
		 * must be defined for the content type.
		 * @param other the list whose contents are to be multiplyed from the
		 *        corresponding items in this list
		 **/
		void multiply(const List& other);
		/**
		 * Divide the values in <i>other</i> from the corresponding values in
		 * this list. List lengths must be equal to each other. Operator /=
		 * must be defined for the content type.
		 * @param other the list whose contents are to be divided from the
		 *        corresponding items in this list
		 **/
		void divide(const List& other);
		
		/**
		 * Get a sub-list from this list. The returned list will include
		 * <i>length</i> (or as many as possible) items from this list
		 * starting at <i>startIndex</i>. If <i>startIndex</i> is
		 * negative, it is treated relative to the end of the list. Thus,
		 * -1 refers to the last list item. If <i>length</i> is negative,
		 * it is treated as a negative offset from the end of the list.
		 * Therefore, getSublist(-3,-2) will return the two items next to
		 * the last one.
		 *
		 * @param startIndex the start of the sub-list
		 * @param length the length of the sub-list
		 **/
		List getSublist(int startIndex, int length=MAXINT) const;

		/**
		 * Create a copy of a list.
		 **/
		List& operator= (const List& other);
		/**
		 * Create a typecasted copy of a list. The iterator of the
		 * typecasted copy is reset to 0.
		 **/
		template <class U> List& operator= (const List<U>& other);
		/**
		 * Make all entries in a list equal to <i>value</i>.
		 **/
		List& operator= (const T& value);

		/**
		 * Multiply each value in the list by <i>value</i>.
		 **/
		void operator*= (const T& value) { for (int i=0;i<_iCurrentItems;i++) _internalArray[i] *= value; }
		/**
		 * Divide each value in the list by <i>value</i>.
		 **/
		void operator/= (const T& value) { for (int i=0;i<_iCurrentItems;i++) _internalArray[i] /= value; }

		/**
		 * Add an element to the list. Calls addElement(element).
		 **/
		void operator+= (const T& element) { addElement(element); }
		/**
		 * Remove an element from the list. Calls removeElement(element).
		 **/
		void operator-= (const T& element) { removeElement(element); }
		/**
		 * Add elements to the list. Calls addElements(element).
		 **/
		void operator+= (const List& other) { addElements(other); }
		/**
		 * Remove elements from the list. Calls removeElements(element).
		 **/
		void operator-= (const List& other) { removeElements(other); }
		/**
		 * Get a sub-list. Calls getSublist(startIndex,length).
		 * @param startIndex the starting index of the sub-list, inclusive
		 * @param length the number of items to copy
		 **/
		List operator() (int startIndex, int length=MAXINT) const { return getSublist(startIndex,length); }

		/**
		 * Compare two lists.
		 **/
		template <class U> friend bool operator== (const List<U>& lst1, const List<U>& lst2);

		/**
		 * Return a list with all elements cast to a new type.
		 **/
		template <class U> operator List<U>();
		
		/**
		 * Return the list element at the given index. Note that no bound
		 * checking is performed. One must ensure that the list is large
		 * enough so that memory outside the internal buffer is not
		 * referenced.
		 * @see #setLength(int)
		 * @see #getElementAt(int)
		 **/
		const T& operator[] (int index) const { return _internalArray[index]; }
		/**
		 * Return the list element at the given index. Note that no bound
		 * checking is performed. One must ensure that the list is large
		 * enough so that memory outside the internal buffer is not
		 * referenced.
		 * @see #setLength(int)
		 * @see #getElementAt(int)
		 **/
		T& operator[] (int index) { return _internalArray[index]; }

		/**
		 * Write a list into a stream in XML format.
		 **/
		template <class U> friend std::ostream& operator<< (std::ostream& sout, const List<U>& lst);
		/**
		 * Read an XML-formatted list from an input stream.
		 *
		 * @exception IOException& on an input error
		 * @exception XMLException& on an XML format error
		 **/
		template <class U> friend std::istream& operator>> (std::istream& sin, List<U>& lst);

		/**
		 * Reset the internal iterator. After reset(), the next call to
		 * next() returns a pointer to the first item in the list.
		 **/
		void reset(void) { _iInternalCounter = 0; }
		/**
		 * Get the next item in the array. Successive calls to next return
		 * the contents of the list from index zero up to the length of
		 * the array.
		 * @return a pointer to the next data in the list
		 **/
		T* next(void) { return (hasNext())? &_internalArray[_iInternalCounter++] : NULL; }
		/**
		 * Check if the list has more data to be fetched.
		 * @return true iff there is still some data to be read
		 **/
		bool hasNext(void) const { return _iInternalCounter < _iCurrentItems; }

		/**
		 * Convert a list to a string.
		 **/
		std::string toString() const;
		/**
		 * Clone a list.
		 **/
		Object* clone() const throw (NotCloneableException&) { return new List(*this); }

	protected:
		template <class U> void copy(const List<U>& other);

		/**
		 * Enlarge the internal array by blockSize.
		 **/
		void enlargeArray(void) { enlargeArray(_iSize+_iBlockSize); }
		/**
		 * Define a new size for the internal array. Depending on the new
		 * value, memory will be either released or allocated.
		 **/
		void enlargeArray(int newSize);

		/**
		 * The contents of the list.
		 **/
		T * _internalArray;
		int _iSize, _iInitialSize, _iBlockSize;
		int _iCurrentItems;

	private:
		int _iInternalCounter;
	};

	typedef List<unsigned char> UnsignedCharList;
	typedef List<char> CharList;
	typedef List<int> IntegerList;
	typedef List<unsigned> UnsignedIntegerList;
	typedef List<long> LongList;
	typedef List<float> FloatList;
	typedef List<double> DoubleList;

#if __GNUC__ > 2 || (__GNUC__ ==  2 && __GNUC_MINOR__ >= 96)
	/**
	 * A template specialization for string lists. Actually, this method
	 * does not allow one to add multiple strings at once because it is
	 * impossible to pass complex types through stdarg. Instead, const
	 * char pointers are excepted. An example:<br>
	 * <pre>
	 * List<string> lst;
	 * string value("D");
	 * lst.addElements(3,"A","B","C"); //correct
	 * lst.addElements(1,value); //wrong!
	 * </pre>
	 *
	 * @param count the number of items to add
	 * @param ... the items as const char pointers
	 **/
	template <> void List<std::string>::addElements(int count, ...);
#endif
	
	template <class T> List<T>::List(T* data, int len, bool release) :
		_internalArray(data), _iSize(len), _iInitialSize(len), _iBlockSize(16),
		_iCurrentItems(len), _iInternalCounter(0)
	{
		if (!release)
			{
				_internalArray = new T[len];
				for (int i=0;i<len;i++)
					_internalArray[i] = data[i];
			}
	}

	template <class T> List<T> operator* (const List<T>& lst, const T& value)
	{
		List<T> result(lst);
		result *= value;
		return result;
	}
	
	template <class T> List<T> operator/ (const List<T>& lst, const T& value)
	{
		List<T> result(lst);
		result /= value;
		return result;
	}

	template <class T> inline List<T> operator+ (const List<T>& lst, const T& element)
	{ List<T> result(lst); result.addElement(element); return result; }
	template <class T> inline List<T> operator- (const List<T>& lst, const T& element)
	{ List<T> result(lst); result.removeElement(element); return result; }
	template <class T> inline List<T> operator+ (const List<T>& lst, const List<T>& other)
	{ List<T> result(lst); result.addElements(other); return result; }
	template <class T> inline List<T> operator- (const List<T>& lst, const List<T>& other)
	{ List<T> result(lst); result.removeElements(other); return result; }

	template <class T> bool operator== (const List<T>& lst1, const List<T>& lst2)
	{
		if (lst1._iCurrentItems != lst2._iCurrentItems)
			return false;
		for (int i=0;i<lst1._iCurrentItems;i++)
			if (! (lst1[i] == lst2[i]))
				return false;
		return true;
	}
	
	template <class T> List<T>::List(int initialSlots, int block) :
		_iSize(initialSlots), _iInitialSize(initialSlots), _iBlockSize(block), _iCurrentItems(0), _iInternalCounter(0)
	{
		_internalArray = new T[_iSize];
	}

	template <class T> List<T>::List(const List<T>& other) : _internalArray(NULL)
	{
		copy(other);
		_iInternalCounter = other._iInternalCounter;
	}

	template <class T>
	template <class U> List<T>::List(const List<U>& other) : _internalArray(NULL)
	{
		copy(other);
	}
	
	template <class T> List<T>& List<T>::operator= (const List<T>& other)
	{
		copy(other);
		_iInternalCounter = other._iInternalCounter;
		return *this;
	}

	template <class T>
	template <class U> List<T>& List<T>::operator= (const List<U>& other)
	{
		copy(other);
		return *this;
	}

	template <class T> List<T>& List<T>::operator= (const T& value)
	{
		for (int i=0;i<_iCurrentItems;i++)
			_internalArray[i] = value;
		return *this;
	}

	template <class T>
	template <class U> List<T>::operator List<U>()
	{
		List<U> result(*this);
		return result;
	}

	template <class T> List<T>::~List()
	{
		delete[] _internalArray;
	}

	template <class T> void List<T>::setCapacity(int newSize)
	{
		if (newSize < _iCurrentItems)
			enlargeArray(_iCurrentItems);
		else if (newSize != _iSize)
			enlargeArray(newSize);
	}

	template <class T> void List<T>::setLength(int newLength)
	{
		if (newLength > _iSize)			
			enlargeArray(newLength);
		_iCurrentItems = newLength;
	}

	template <class T> void List<T>::setLength(int newLength, T value)
	{
		if (newLength > _iSize)
			enlargeArray(newLength);
		for (int i=_iCurrentItems;i<newLength;i++)
			_internalArray[i] = value;
		_iCurrentItems = newLength;
	}

	template <class T> void List<T>::add(const List& other)
	{
		int minLength = minimum(_iCurrentItems, other._iCurrentItems);
		for (int i=0;i<minLength;i++)
			_internalArray[i] += other._internalArray[i];

		for (int i=minLength;i<other._iCurrentItems;i++)
			addElement(other._internalArray[i]);
	}

	template <class T> void List<T>::subtract(const List& other)
	{
		int minLength = minimum(_iCurrentItems, other._iCurrentItems);
		for (int i=0;i<minLength;i++)
			_internalArray[i] -= other._internalArray[i];

		for (int i=minLength;i<other._iCurrentItems;i++)
			addElement(-other._internalArray[i]);
	}

	template <class T> void List<T>::multiply(const List& other)
	{
		int minLength = minimum(_iCurrentItems, other._iCurrentItems);
		for (int i=0;i<minLength;i++)
			_internalArray[i] *= other._internalArray[i];
	}

	template <class T> void List<T>::divide(const List& other)
	{
		int minLength = minimum(_iCurrentItems, other._iCurrentItems);
		for (int i=0;i<minLength;i++)
			_internalArray[i] /= other._internalArray[i];
	}

	
	template <class T> void List<T>::addElement(const T& element)
	{
		if (_iCurrentItems >= _iSize)
			enlargeArray();
		_internalArray[_iCurrentItems++] = element;
	}

	template <class T> void List<T>::enlargeArray(int newSize)
	{
		T * newArray = new T[newSize];
		//memcpy((void*)newArray,(void*)_internalArray,size*sizeof(T));
		int minSize = _iSize < newSize ? _iSize : newSize;
		for (int i=0;i<minSize;i++)
			newArray[i] = _internalArray[i];
		delete [] _internalArray;
		_internalArray = newArray;
		_iSize = newSize;
		if (_iCurrentItems > _iSize)
			_iCurrentItems = _iSize;
	}

	template <class T> List<T> List<T>::getSublist(int startIndex, int length) const
	{
		if (startIndex < 0)
			startIndex += _iCurrentItems;
		if (length < 0)
			length += _iCurrentItems-startIndex+1;
		if (length < 0)
			length = 0;
		else if (length > _iCurrentItems || startIndex+length > _iCurrentItems)
			length = _iCurrentItems-startIndex;
		List<T> result(length);
		for (int i=startIndex;i<startIndex+length;i++)
			result += _internalArray[i];
		return result;
	}

	template <class T> void List<T>::removeElement(const T& element)
	{
		int index = indexOf(element);
		if (index != -1)
			removeElementAt(index);
	}

	template <class T> void List<T>::insertElementAt(const T& element, int index)
	{
		if (index <= _iCurrentItems)
			{
				if (_iCurrentItems >= _iSize)
					enlargeArray();
				for (int i=_iCurrentItems;i>index;i--)
					_internalArray[i] = _internalArray[i-1];
				_internalArray[index] = element;
				_iCurrentItems++;
			}
	}
	
	template <class T> T List<T>::removeElementAt(int index)
	{
		T removed = _internalArray[index];
		for (int i=index;i<_iCurrentItems && i<_iSize-1;i++)
			_internalArray[i] = _internalArray[i+1];
		_iCurrentItems--;
		return removed;
	}

	template <class T> void List<T>::addElements(const List<T>& other)
	{
		int i;
		AllListItems(i,other)
			addElement(other[i]);
	}
	
	template <class T> void List<T>::addElements(int count,...)
	{
		if (_iCurrentItems + count > _iSize)
			{
				int size = _iSize;
				while (_iCurrentItems + count > size) size += _iBlockSize;
				enlargeArray(size);
			}
		va_list argp;
		// initalize var ptr
		va_start(argp, count); 

		// repeat for each arg
		while (count--)
			addElement(va_arg(argp,T));

		// done with args
		va_end(argp);
	}
	
	template <class T> void List<T>::removeElements(const List<T>& other)
	{
		int i;
		AllListItems(i,other)
			removeElement(other[i]);
	}
	
	template <class T> int List<T>::indexOf(const T& element) const
	{
		for (int i=0;i<_iCurrentItems;i++)
			if (_internalArray[i] == element)
				return i;
		return -1;
	}

	template <class T> void List<T>::clear(void)
	{
		delete[] _internalArray;
		_internalArray = new T[_iInitialSize];
		_iCurrentItems = 0;
	}

	template <class T>
	template <class U> void List<T>::copy(const List<U>& other)
	{
		_iSize = other.getCapacity();
		T* tmp = new T[_iSize];
		_iCurrentItems = other.getLength();
		_iBlockSize = other.getBlockSize();
		_iInitialSize = other.getInitialSize();
 		for (int i=0;i<_iCurrentItems;i++)
			tmp[i] = T(other[i]);

		delete[] _internalArray;
		_internalArray = tmp;
		_iInternalCounter = 0;
	}

	template <class T> std::string List<T>::toString() const
	{
		return getClassName();
	}
}


#if !defined(_LIST_INCLUDED_FROM_XMLPARSER_H) && !defined(_LIST_INCLUDED_FROM_STREAMTOKENIZER_H) && !defined(_LIST_INCLUDED_FROM_PAIR_H)
#include "StreamTokenizer.h"
#include "xml/XMLParser.h"
#include "String.h"

namespace util
{
	template <class T> std::ostream& operator<< (std::ostream& sout, const List<T>& lst)
	{
		sout << "<list size='" << lst._iCurrentItems << '\'';
		if (lst._iSize != lst._iCurrentItems)
			sout << " capacity='" << lst._iSize << '\'';
		if (lst._iInitialSize != lst._iCurrentItems)
			sout << " initialSize='" << lst._iInitialSize << '\'';
		if (lst._iBlockSize != 16)
			sout << " blockSize='" << lst._iBlockSize << '\'';
		sout << '>' << std::endl;
		for (int i=0;i<lst._iCurrentItems;i++)
			{
				Util::writeXMLItem(sout,lst._internalArray[i]);
				sout << std::endl;
			}
		sout << "</list>";
		return sout;
	}

#define getInt(variable,name) \
	child = element->getChildNode(std::string("list.") + name); \
	if (child && child->getNodeType() == Node::ATTRIBUTE_NODE) \
		variable = String::parseInt(((Attr*)child)->value);

	template <class T> std::istream& operator>> (std::istream& sin, List<T>& lst)
	{
		using namespace util::xml;
		
		XMLParser parser;
		sin >> std::ws;
		
		SmartPtr<Node> node(parser.getNextNode(sin));
		if (node.get() && node->getNodeType() == Node::ELEMENT_NODE)
			{
				Element* element = (Element*)node.get();
				if (element->tagType != Element::TAG_OPENING || element->tagName != "list")
					throw io::IOException("operator>> (istream&, List<T>&): Expecting <list>.");
				const Node* child;
				lst._iCurrentItems = -1;
				getInt(lst._iCurrentItems,"size");
				if (lst._iCurrentItems < 0)
					throw io::IOException("operator>> (istream&, List<T>&): The size of a list must be specified, and it must be non-negative.");
				lst._iSize = lst._iCurrentItems;
				getInt(lst._iSize,"capacity");
				lst._iInitialSize = lst._iCurrentItems;
				getInt(lst._iInitialSize,"initialSize");
				lst._iBlockSize = 16;
				getInt(lst._iBlockSize,"blockSize");

				sin >> std::ws;

				delete[] lst._internalArray;
				lst._internalArray = new T[lst._iSize];
				for (int i=0;i<lst._iCurrentItems;i++)
					{
						Util::readXMLItem(sin,lst._internalArray[i]);
						//cerr << "Read item " << i << endl;
						if (!sin)
							throw io::IOException("operator>> (istream&, List<T>&): Premature end of input after element " + String::toString(i) + ".");
					}

				sin >> std::ws;
				SmartPtr<Node> closing(parser.getNextNode(sin));
				if (!closing.get() || closing->getNodeType() != Node::ELEMENT_NODE ||
						closing->getName() != "list" ||
						((Element*)closing.get())->tagType != Element::TAG_CLOSING)
					throw io::IOException("operator>> (istream&, List<T>&): Expecting </list>.");
			}
		else
			throw io::IOException("operator>> (istream&, List<T>&): Input stream does not contain a list.");

		return sin;
	}

#undef getInt

}
#endif //_LIST_INCLUDED_FROM_X_H

// Move this declaration anywhere else, and it won't compile. Don't
// ask me why.
#if __GNUC__ == 2 && __GNUC_MINOR__ < 96
namespace util
{
	template <> void List<std::string>::addElements(int count, ...);
}
#endif

#endif