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

#include "FeatureSelector.h"
#include <SortedList.h>
#include <Pair.h>
#include <functional>

using namespace util;

namespace prapi
{
	double SubSetSelector::measureGoodness(const util::List<int>& enabledIndices)
	{
		return _measure.measureGoodness(*this, enabledIndices);
	}
	
	List<int> SequentialSelector::optimize(int totalFeatureCount, int featureCount)
	{
		List<int> enabledFeatures, disabledFeatures;
		if (_bForward)
			{
				for (int i=0; i<totalFeatureCount; i++)
					disabledFeatures += i;
			}
		else
			{
				for (int i=0; i<totalFeatureCount; i++)
					enabledFeatures += i;
			}

		bool forward = _bForward;
		double previousScore = -MAXDOUBLE;
		int previousFeature = -1;
		_bStopped = false;

		if (featureCount <= 0 && _dGoodnessThreshold <= 0)
			return enabledFeatures;

		int index = 0;
		while (!_bStopped && enabledFeatures.getLength() != featureCount)
			{
				double maxScore = -MAXDOUBLE;
				int maxIndex = -1;

				//Forward selection goes through all disabled features, adds
				//one at time to enabled features, and takes the best one.
				if (forward)
					{
						for (int i=0; i<disabledFeatures.getLength(); i++)
							{
								if (disabledFeatures[i] == previousFeature)
									continue;
								double score = measureGoodness(enabledFeatures + disabledFeatures[i]);
								if (score > maxScore)
									{
										maxScore = score;
										maxIndex = i;
									}
							}
						if (!_bFloating || maxScore > previousScore)
							{
								enabledFeatures += disabledFeatures[maxIndex];
								previousFeature = disabledFeatures.removeElementAt(maxIndex);
								previousScore = maxScore;
								fireEvent(SelectionEvent(index++, maxScore, enabledFeatures));
							}
						else if (_bForward)
							break;

						//If this is a floating search, change direction
						if (_bFloating && enabledFeatures.getLength() > 2)
							forward = false;
					}
				//Backward selection removes one enabled feature at time, and
				//discards the one whose removal resulted in the best result.
				else
					{
						for (int i=0; i<enabledFeatures.getLength(); i++)
							{
								if (enabledFeatures[i] == previousFeature)
									continue;
								double score = measureGoodness(enabledFeatures - enabledFeatures[i]);
								if (score > maxScore)
									{
										maxScore = score;
										maxIndex = i;
									}
							}
						if (!_bFloating || maxScore > previousScore)
							{
								disabledFeatures += enabledFeatures[maxIndex];
								previousFeature = enabledFeatures.removeElementAt(maxIndex);
								previousScore = maxScore;
								fireEvent(SelectionEvent(index++, maxScore, enabledFeatures));
							}
						else if (!_bForward)
							break;

						if (_bFloating && disabledFeatures.getLength() > 2)
							forward = true;
					}
				if (_dGoodnessThreshold > 0 && maxScore > _dGoodnessThreshold)
					break;
			}
		return enabledFeatures;
	}

	List<int> BeamSelector::optimize(int totalFeatureCount, int featureCount)
	{
		List<List<int> > sets(_iWidth);
		sets.setLength(1); //Add an empty feature set
		typedef Pair<double,int> Score;

		_bStopped = false;
		
		if (featureCount <= 0 && _dGoodnessThreshold <= 0)
			return sets[0];

		//Loop to the given depth
		for (int i=0; i<featureCount && !_bStopped; i++)
			{
				SortedList<Score, std::less<Score> > scores(_iWidth);
				scores.setMaximumSize(_iWidth);
				
				//Store all feature sets tested on this round to avoid
				//multiple evaluations
				List<List<int> > testedSets(totalFeatureCount*_iWidth);

				//Loop through all feature sets on the previous level
				for (int j=0; j<sets.getLength(); j++)
					{
						//Add each feature in turn to the current set
						for (int k=0; k<totalFeatureCount; k++)
							{
								if (sets[j].contains(k))
									continue;
								//Create a new feature set (sort order is maintained
								//to make list comparison easy)
								SortedList<int> tmp(i+1);
								tmp += sets[j];
								tmp += k;
								//Check that it isn't evaluated yet
								if (testedSets.contains(tmp))
									continue;
								//Store score and feature set index
								scores += Score(measureGoodness(tmp), testedSets.getLength());
								testedSets += tmp;
							}
					}

				//Store N best sets
				sets.clear();
				for (int j=0; j<scores.getLength(); j++)
					sets += testedSets[scores[j].second()];

				fireEvent(SelectionEvent(i, scores[0].first(), sets[0]));
			}
		//Return the best set on the last round
		return sets[0];
	}
}