/*********************************************************************
 * This file is part of the PRAPI library.
 *
 * Copyright (C) 2001-2002 Topi Mäenpää
 * Copyright (C) 2001 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.13 $
 *********************************************************************/

#ifndef _FEATURESELECTOR_H
#define _FEATURESELECTOR_H

#include <Event.h>

namespace prapi
{
	/**
	 * An optimization event is fired for each completed iteration of an
	 * optimization method.
	 **/
	class SelectionEvent
	{
	public:
		/**
		 * Create a new optimization event.
		 *
		 * @param i the index of the current iteration
		 * @param s the best score (goodness) obtained during this iteration
		 * @param the indices of the features with which the best result was obtained
		 **/
		SelectionEvent(int i, double s, const util::List<int>& bestFeatures) :
			iterationIndex(i), goodness(s), features(bestFeatures) {}

		/**
		 * The index of the current generation (optimization level).
		 **/
		int iterationIndex;
		/**
		 * The goodness of the best features.
		 **/
		double goodness;
		/**
		 * The features with which the best result was obtained.
		 **/
		util::List<int> features;
	};

	/**
	 * A common base class for methods searching for sub-optimal subsets
	 * (of features, for example).
	 **/
	class SubSetSelector : virtual public util::Object, public util::EventSource<SelectionEvent>
	{
	public:
		class GoodnessMeasure;

		/**
		 * Create a new SubSetSelector with the given goodness measure. 
		 * The goodness measure is consulted whenever a set of features
		 * needs to be evaluated.
		 **/
		SubSetSelector(GoodnessMeasure& measure) : _bStopped(false), _measure(measure), _dGoodnessThreshold(0) {}
									 
		/**
		 * Find a sub-optimal subset of items. The implementation of this
		 * method is method-dependent. By convention, each implementation
		 * should fire a SelectionEvent every time an optimization round
		 * is finished.
		 *
		 * @param totalCount the total number of items out of which the
		 * subset is to be selected.
		 *
		 * @param the desired number of enabled items after optimization. 
		 * If this value is set to a non-positive value, optimization is
		 * stopped only after the goodness threshold is exceeded.
		 **/
		virtual util::List<int> optimize(int totalCount, int desiredCount=-1) = 0;

		/**
		 * Stop the optimization. This method is useful with fancy
		 * stopping criteria. If the optimization is not to be stopped
		 * after a certain number of iterations but according to some
		 * other rule, this method can be called from the
		 * measureGoodness() method of the GoodnessMeasure. This method
		 * sets the _bStopped flag to true.
		 **/
		void stop() { _bStopped = true; }
		
		/**
		 * Measure the goodness of a subset (of features). This methods
		 * consults the internal goodness measure to perform the actual
		 * measurement.
		 **/
		double measureGoodness(const util::List<int>& enabledIndices);

		/**
		 * Set the goodness value after which optimization is stopped. To
		 * disable the threshold, set it to a non-positive number.
		 **/
		void setGoodnessThreshold(double threshold) { _dGoodnessThreshold = threshold; }

		/**
		 * Get the goodness value after which optimization is stopped.
		 **/
		double getGoodnessThreshold() const { return _dGoodnessThreshold; }

	protected:
		/**
		 * A flag indicating whether the optimization should be continued.
		 **/
		bool _bStopped;
		
		/**
		 * The goodness measure.
		 **/
		GoodnessMeasure& _measure;

		/**
		 * The goodness threshold.
		 **/
		double _dGoodnessThreshold;
	};

	/**
	 * An interface for methods for evaluating the goodness of a subset
	 * (of features).
	 **/
	class SubSetSelector::GoodnessMeasure : virtual public util::Object
	{
	public:
		/**
		 * Measure the goodness of a subset (of features). Subclasses must
		 * override this method and find out a method of evaluating the
		 * goodness of the given subset. A typical way of evaluating the
		 * subset is to perform a classification experiment with the
		 * indicated items (features) enabled. 
		 *
		 * @param selector a reference to the SubSetSelector instance that
		 * called this method. One may use this to stop the optimization.
		 * @param enabledIndices the indices of enabled items (features). 
		 * @return the goodness of the enabled items. Larger is better,
		 * and negative values are not acceptable.
		 **/
		virtual double measureGoodness(SubSetSelector& selector,
																	 const util::List<int>& enabledIndices) = 0;
	};
	
	/**
	 * Methods for sequential feature selection. This class is capable
	 * of performing (feature) subset selection with the SFS, SFFS, SBS,
	 * and SBFS methods. In fact, due to the abstraction of performance
	 * evaluation, this class serves just as an algorithm that can be
	 * used in selecting a sub-optimal subset from just about anything. 
	 * A common example is finding a sub-optimal subset of model samples
	 * from a large number of candidates.
	 **/
	class SequentialSelector : public SubSetSelector
	{
	public:
		/**
		 * Create a new (feature) selector. The different types of
		 * selection schemes can be achieved with the following parameter
		 * combinations:		 
		 * <pre>
		 * Method | forward floating
		 * -------+-----------------
		 * SBS    | false   false
		 * SBFS   | false   true
		 * SFS    | true    false
		 * SFFS   | true    true
		 * </pre>
		 *
		 * @param forward if true, selection is started with an empty item
		 * set. At each iteration, all remaining items are added to
		 * "enabled" items in turn, the resulting sets are evaluated, and
		 * the best one is selected. If false, the search goes backward. 
		 * That is, selection is started with all items enabled. Each item
		 * is dropped out in turn, and the item whose removal resulted in
		 * the best score is discarded.
		 *
		 * @param floating if true, the search goes both back and forth,
		 * alternating each phase.
		 **/
		SequentialSelector(GoodnessMeasure& measure, bool forward=true, bool floating=true) :
			SubSetSelector(measure),
			_bForward(forward), _bFloating(floating) {}

		/**
		 * Set search parameters.
		 **/
		void setParams(bool forward, bool floating)
		{
			_bForward = forward;
			_bFloating = floating;
		}

		/**
		 * See if the search is of "floating" type.
		 **/
		bool isFloating() const { return _bFloating; }

		/**
		 * See if the search goes forward.
		 **/
		bool isForward() const { return _bForward; }

		util::List<int> optimize(int totalCount, int desiredCount=-1);

	private:
		bool _bForward;
		bool _bFloating;
	};

	/**
	 * BeamSelector implements the beam search optimization algorithm.
	 **/
	class BeamSelector : public SubSetSelector
	{
	public:
		/**
		 * Create an instance of the BeamSelector with the given goodness
		 * measure and beam width.
		 **/
		BeamSelector(GoodnessMeasure& measure, int beamWidth=3) :
			SubSetSelector(measure), _iWidth(beamWidth) {}

		util::List<int> optimize(int totalCount, int desiredCount=-1);
	private:
		int _iWidth;
	};
}
#endif