/* $Id$ */

/** @file ai_abstractlist.hpp a linked list which can keep item/value pairs */

#ifndef AI_ABSTRACTLIST_HPP
#define AI_ABSTRACTLIST_HPP

#include "ai_object.hpp"
#include <map>
#include <set>

class AIAbstractListSorter;

/**
 * Class that creates a linked list which can keep item/value pairs.
 */
class AIAbstractList : public AIObject {
public:
	/** Type of sorter */
	enum SorterType {
		SORT_BY_VALUE = 0,
		SORT_BY_ITEM  = 1,
	};

private:
	AIAbstractListSorter *sorter;
	SorterType sorter_type;
	bool sort_ascending;

public:
	typedef std::set<int32> AIItemList;               ///< The list of items inside the bucket
	typedef std::map<int32, AIItemList> AIAbstractListBucket; ///< The bucket list per value
	typedef std::map<int32, int32> AIAbstractListMap;         ///< List per item

	AIAbstractListMap items;           ///< The items in the list
	AIAbstractListBucket buckets;      ///< The items in the list, sorted by value

protected:
	/**
	 * Add a single item to the list.
	 * @param item the item to add. Should be unique, otherwise it is ignored.
	 * @note the value is set to 0 by default.
	 */
	void AddItem(int32 item);

	/**
	 * Remove a single item from the list.
	 * @param item the item to remove. If not existing, it is ignored.
	 */
	void RemoveItem(int32 item);

public:
	/**
	 * The name of the class, needed by several sub-processes.
	 */
	static const char *GetClassName() { return "AIAbstractList"; }

	/**
	 * Constructor of the AIAbstractList.
	 */
	AIAbstractList();

	/**
	 * Destructor of the AIAbstractList.
	 */
	~AIAbstractList();

	/**
	 * Clear the list, making Count() returning 0 and IsEmpty() returning true.
	 */
	void Clear();

	/**
	 * Check if an item is in the list.
	 * @param item the item to check for.
	 * @return true if the item is in the list.
	 */
	bool HasItem(int32 item);

	/**
	 * Go to the beginning of the list.
	 * @return the item value of the first item.
	 */
	int32 Begin();

	/**
	 * Go to the next item in the list.
	 * @return the item value of the next item.
	 * @note returns 0 if beyond end-of-list. Use HasNext() to check for end-of-list.
	 */
	int32 Next();

	/**
	 * Check if a list is empty.
	 * @return true if the list is empty.
	 **/
	bool IsEmpty();

	/**
	 * Check if there is a next element. In other words, if this is true,
	 *   Next() will return a valid item.
	 * @return true if there is a next item.
	 */
	bool HasNext();

	/**
	 * Returns the amount of items in the list.
	 * @return amount of items in the list.
	 */
	int32 Count();

	/**
	 * Get the value that belongs to this item.
	 * @param item the item to get the value from
	 * @return the value that belongs to this item.
	 */
	int32 GetValue(int32 item);

	/**
	 * Set a value of an item directly.
	 * @param item the item to set the value for.
	 * @param value the value to give to the item
	 * @return true if we could set the item to value, false otherwise.
	 */
	bool SetValue(int32 item, int32 value);

	/**
	 * Sort this list by the given sorter and direction.
	 * @param sorter    the type of sorter to use
	 * @param ascending if true, lowest value is on top, else at bottom.
	 * @note the current item stays at the same place.
	 */
	void Sort(SorterType sorter, bool ascending);

	/**
	 * Removes all items with a higher value than 'value'.
	 * @param value the value above which all items are removed.
	 */
	void RemoveAboveValue(int32 value);

	/**
	 * Removes all items with a lower value than 'value'.
	 * @param value the value below which all items are removed.
	 */
	void RemoveBelowValue(int32 value);

	/**
	 * Removes all items with a value above start and below end.
	 * @param start the lower bound of the to be removed values (exclusive).
	 * @param end   the upper bound of the to be removed valuens (exclusive).
	 */
	void RemoveBetweenValue(int32 start, int32 end);

	/**
	 * Remove all items with this value.
	 * @param value the value to remove.
	 */
	void RemoveValue(int32 value);

	/**
	 * Remove the first count items.
	 * @param count the amount of items to remove.
	 */
	void RemoveTop(int32 count);

	/**
	 * Remove the last count items.
	 * @param count the amount of items to remove.
	 */
	void RemoveBottom(int32 count);

	/**
	 * Remove everything that is in the given list from this list (same item index that is).
	 * @param list the list of items to remove.
	 * @pre list != NULL
	 */
	void RemoveList(AIAbstractList *list);

	/**
	 * Keep all items with a higher value than 'value'.
	 * @param value the value above which all items are kept.
	 */
	void KeepAboveValue(int32 value);

	/**
	 * Keep all items with a lower value than 'value'.
	 * @param value the value below which all items are kept.
	 */
	void KeepBelowValue(int32 value);

	/**
	 * Keep all items with a value above start and below end.
	 * @param start the lower bound of the to be kept values (exclusive).
	 * @param end   the upper bound of the to be kept values (exclusive).
	 */
	void KeepBetweenValue(int32 start, int32 end);

	/**
	 * Keep all items with this value.
	 * @param value the value to keep.
	 **/
	void KeepValue(int32 value);

	/**
	 * Keep the first count items, i.e. remove everything except the first count items.
	 * @param count the amount of items to keep.
	 */
	void KeepTop(int32 count);

	/**
	 * Keep the last count items, i.e. remove everything except the last count items.
	 * @param count the amount of items to keep.
	 */
	void KeepBottom(int32 count);

	/**
	 * Keps everything that is in the given list from this list (same item index that is).
	 * @param list the list of items to keep.
	 * @pre list != NULL
	 */
	void KeepList(AIAbstractList *list);

	/**
	 * The definition how valuators should look.
	 */
	class Valuator {
		/* Make this valuator a friend of AIAbstractList, so we can access the private.
		 *  Nobody else should ever call Valuate. */
		friend class AIAbstractList;
	public:
		/**
		 * Virtual destructor, needed to make compilers happy.
		 */
		virtual ~Valuator() {}

	private:
		virtual int32 Valuate(int32 item) const = 0;
	};

	/**
	 * Give all items a value defined by the valuator you give.
	 * @note the valuator should be a valid instance.
	 */
	void Valuate(const AIAbstractList::Valuator &proc);
};

#endif /* AI_LIST_HPP */