/*********************************************************************
 * 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.8 $
 *********************************************************************/

#ifndef _LISTUTILS_H
#define _LISTUTILS_H

#include "Util.h"
#include "List.h"
#include <time.h>
#include <stdlib.h>

namespace util
{
	/**
	 * Here you can find functions for handling lists.
	 **/
	class ListUtils
	{
	public:
		/**
		 * Reverse the order of elements in a list (in-place).
		 **/
		template <class T> static void reverse(List<T>& lst);
		/**
		 * Finds the first element form the list which is not same as
		 * given value.
		 *
		 * @return the index of value found.
		 *         if different values is not found will be returned -1.
		 **/
		template <class T> static int findFirstNotOf(const List<T>& lst,const T& value) throw (InvalidArgumentException&);
		/**
		 * Randomly select <i>n</i> items from a list.
		 **/
		template <class T> static List<T> selectRandomly(const List<T>& lst, int n) throw (InvalidArgumentException&);
		/**
		 * Randomly split <i>lst</i> into two pieces containing <i>n</i>
		 * and <i>size-n</i> items, respectively.
		 **/
		template <class T> static List<List<T> > splitRandomly(const List<T>& lst, int n) throw (InvalidArgumentException&);
		/**
		 * Finds the index of maximum value of the list.
		 **/
		template <class T> static int maxIndex(const List<T>& lst) throw (InvalidArgumentException&);
		/**
		 * Finds the index of minimum value of the list.
		 **/
		template <class T> static int minIndex(const List<T>& lst) throw (InvalidArgumentException&);

		/**
		 * Create a list of strings out of an array of char pointers. This
		 * method is useful for example in parsing command-line arguments.
		 *
		 * @param argc the number of items in argv
		 * @param argv an array of strings (char pointers)
		 **/
		static List<std::string> createList(int argc, char* const *argv);

	private:
		template <class T> static void randomSelect(const List<T>& lst,
																								List<T>* selected,
																								List<T>* notSelected,
																								int n) throw (InvalidArgumentException&);
	};

	template <class T> void ListUtils::reverse(List<T>& lst)
	{
		int len = lst.getLength();
		T tmp;
		for (int i=0;i<len>>1;i++)
			{
				tmp = lst[len-i-1];
				lst[len-i-1] = lst[i];
				lst[i] = tmp;
			}
	}

	template <class T> int ListUtils::findFirstNotOf(const List<T>& lst,const T& value) throw (InvalidArgumentException&)
	{
		int len = lst.getLength();
		if (len > 0)
			{
				for(int i=0;i<len;i++)
					if(lst[i] !=  value)return i;
			}
		else
			throw InvalidArgumentException("ListUtils::findFirstNotOf(const List<T>&): Cannot find anything in an empty list.");
		
		return -1;
	}
	

	template <class T> List<T> ListUtils::selectRandomly(const List<T>& lst, int n)
		throw (InvalidArgumentException&)
	{
		List<T> result(n);
		randomSelect<T>(lst,&result,NULL,n);
		return result;
	}
	
	template <class T> List<List<T> > ListUtils::splitRandomly(const List<T>& lst, int n)
		throw (InvalidArgumentException&)
	{
		List<List<T> > result(2);
		result.setLength(2);
		result[0].setCapacity(n);
		result[1].setCapacity(lst.getLength()-n);
		randomSelect<T>(lst,&result[0],&result[1],n);
		return result;
	}

	template <class T> void ListUtils::randomSelect(const List<T>& lst,
																									List<T>* selected,
																									List<T>* notSelected,
																									int n)
		throw (InvalidArgumentException&)
	{
		int size = lst.getLength();
		if (n > size)
			throw InvalidArgumentException("ListUtils::randomSelect(const List<T>&,List<T>*,List<T>*,int): There are too few items in the list.");

		srand48(time(NULL));
		char* buffer = new char[size];
		memset(buffer,0,size);

		char selectMark = -1;
		//If the user wants to select more than half of the items, then
		//turn the selection process around, i.e. select items that are
		//not to be included in the result set.
		if (n > size/2)
			{
				n = size - n;
				selectMark = 0;
			}
			
		while (n)
			{
				int rnumber = int(drand48()*size);
				if (!buffer[rnumber])
					{
						n--;
						buffer[rnumber] = -1;
					}
			}

		for (int i=size;i--;)
			{
				if (buffer[i] == selectMark)
					selected->addElement(lst[i]);
				else if (notSelected)
					notSelected->addElement(lst[i]);
			}

		delete[] buffer;
	}

	template <class T> int ListUtils::maxIndex(const List<T>& lst) throw (InvalidArgumentException&)
	{
		int len = lst.getLength();
		if (len > 0)
			{
				T max = lst[0];
				int index = 0;
				for(int i=1;i<len;i++)
					if(max < lst[i])
						{
							max = lst[i];
							index = i;
						}
				return index;
			}
		else
			throw InvalidArgumentException("ListUtils::maxIndex(const List<T>&): Cannot calculate maximum index for an empty list.");
	}
		
	template <class T> int ListUtils::minIndex(const List<T>& lst) throw (InvalidArgumentException&)
	{
		int len = lst.getLength();
		if (len > 0)
			{
				T min = lst[0];
				int index = 0;
				for(int i=1;i<len;i++)
					if(lst[i] < min)
						{
							min = lst[i];
							index = i;
						}
				return index;
			}
		else
			throw InvalidArgumentException("ListUtils::minIndex(const List<T>&): Cannot calculate minium index for an empty list.");
	}
	
}
#endif