/*********************************************************************
 * This file is part of the PRAPI library.
 *
 * 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.15 $
 *********************************************************************/

#ifndef _QUANTIZER_H
#define _QUANTIZER_H

#include "Distribution.h"
#include <Matrix.h>
#include <Exception.h>
#include <List.h>
#include <LinkedList.h>
#include <iostream>

using namespace util;

namespace prapi
{
	/**
	 * An exception for quantization errors. (Values out of quantization
	 * range etc.)
	 **/
	class QuantizationException : public Exception
	{
	public:
		QuantizationException(char* msg) : Exception(msg) {}
	};
	
	/**
	 * Quantizer is an interface specification for different types of
	 * quantization schemes.
	 **/
	class Quantizer
	{
	public:
		/**
		 * Create a quantizer with the given number of quantization levels.
		 **/
		Quantizer(int l=1) { setLevels(l); }
		virtual ~Quantizer() {}

		/**
		 * Get the number of quantization levels.
		 **/
		virtual int getLevels(void) const { return _iLevels; }
		/**
		 * Set the number of quantization levels. The output values
		 * produced by getBinIndex will range from 0 to l-1.
		 **/
		virtual void setLevels(int l) { _iLevels = l; }

		/**
		 * Get the bin index for the given value, i.e. <i>quantize</i> the
		 * value.
		 * @return the quantized value
		 **/
		virtual int getBinIndex(double value) throw (QuantizationException&) = 0;
		
	protected:
		int _iLevels;
	};

	/**
	 * UniformQuantizer implements an uniform quantization scheme. It
	 * divides the feature space into equally spaced bins.
	 **/
	class UniformQuantizer : public Quantizer
	{
	public:
		/**
		 * Create a new UniformQuantizer instance.
		 *
		 * Example:
		 * <pre>
		 * UniformQuantizer q(64,256); //drop two lsb's of 8-bit feature values
		 * </pre>
		 *
		 * @param lev the number of quantization levels
		 * @param origMax the original maximum value of the data. Add a small
		 *                value (one quantization step in the original feature
		 *                space) to this to prevent the quantizer from producing
		 *                bin index <i>lev</i>. Typically, one is added when
		 *                quantizing integer spaces.
		 * @param origMin the original minimum value. Use the exact value.
		 **/
		UniformQuantizer(int lev, double origMax, double origMin=0.0) : Quantizer(lev) { originalMax = origMax; originalMin = origMin; }

		void setMin(double min) { originalMin = min; }
		void setMax(double max) { originalMax = max; }
		double getMin(void) const { return originalMin; }
		double getMax(void) const { return originalMax; }
		
		int getBinIndex(double value) throw (QuantizationException&) { return int((value-originalMin)*_iLevels/(originalMax-originalMin)); }

	private:
		double originalMin, originalMax;
	};


	/**
	 * EqualAreaQuantizer derives the quantization from a distribution.
	 * The distribution is split into pieces whose areas are as close to
	 * equal as possible. This ensures maximum resolution where feature
	 * density is highest.
	 **/
	class EqualAreaQuantizer : public Quantizer
	{
	public:
		/**
		 * Create a EqualAreaQuantizer with the given number of
		 * quantization levels.
		 **/
		EqualAreaQuantizer(int levels = 1) : Quantizer(levels) {}

		/**
		 * Extract the quantization from a sorted list of values. This
		 * method does not assume any prior quantization. That is, the
		 * given list is just an ordered set of values.
		 *
		 * @param lst the values in ascending order
		 **/
		template <class T> void extractFrom(const List<T>& lst);

		/**
		 * Extract the quantization from a sorted linked list of values.
		 * This method does not assume any prior quantization. That is,
		 * the given list is just an ordered set of values.
		 *
		 * @param lst the values in ascending order
		 * @deprecated use extractFrom(const List<T>&) instead
		 **/
		template <class T> void extractFrom(const LinkedList<T>* lst);
		
		/**
		 * Create a list of values from a matrix. The list will contain
		 * the matrix' items in scanning order. If a sorted list is used,
		 * the result is suitable for an extractFrom(List&)
		 * call.<p>
		 *
		 * Example:<br>
		 * <pre>
		 * Matrix<double> mat(...);
		 * SortedDoubleList lst;
		 * EqualAreaQuantizer::createList(img,lst);
		 * EqualAreaQuantizer q(8);
		 * q.extractFrom(lst);
		 * </pre>
		 *
		 * Note that using a SortedList for a large number of entries is
		 * extremely inefficient as each insertion into the list may
		 * involve massive memory transfers. A better solution is to use
		 * an ordinary list and sort it afterwards or to use the
		 * createList(Matrix&,SortedLinkedList*&) method.
		 * 
		 * @param mat any matrix
		 * @param lst the list to which values are to be added
		 * @param n the number of samples to take from the matrix. 0 means
		 * all. If n is less than the size of the image, every (size/n)th
		 * sample is selected.
		 **/
		template <class T> static void createList(const Matrix<T>& mat, List<T>& lst, int n=0);
		/**
		 * Create a linked list of values from a matrix. The list will
		 * contain the matrix' items in ascending order, and the result is
		 * suitable for an extractFrom(SortedLinkedList*) call.<p>
		 *
		 * Example:<br>
		 * <pre>
		 * Matrix<double> mat(...);
		 * SortedLinkedList<double>* lst = NULL;
		 * EqualAreaQuantizer::createList(img,lst);
		 * EqualAreaQuantizer q(8);
		 * q.extractFrom(lst);
		 * </pre>
		 *
		 * @param mat any matrix
		 * @param lst the list to which values are to be added
		 * @param n the number of samples to take from the matrix. 0 means
		 * all. If n is less than the size of the image, every (size/n)th
		 * sample is selected.
		 *
		 * @deprecated use createList(const Matrix<T>& mat, List<T>& lst, int n=0) instead
		 **/
		template <class T> static void createList(const Matrix<T>& mat, SortedLinkedList<T>*& lst, int n=0);

		int getBinIndex(double value) throw (QuantizationException&);
		void setLevels(int l);

		/**
		 * Get the list of cut values used by this quantizer.
		 **/
		List<double> getCutvalues() const { return _lstCutvalues; }
		/**
		 * Get the list of cut values used by this quantizer.
		 **/
		const List<double>& cutvalues() const { return _lstCutvalues; }
		/**
		 * Get the list of cut values used by this quantizer.
		 **/
		List<double>& cutvalues() { return _lstCutvalues; }

		/**
		 * Write to a stream.
		 **/
		friend std::ostream& operator<< (std::ostream& sout,const EqualAreaQuantizer& quantizer);
		/**
		 * Read from a stream.
		 **/
		friend std::istream& operator>> (std::istream& sin, EqualAreaQuantizer& quantizer);

	private:
		List<double> _lstCutvalues;
	};

	template <class T> void EqualAreaQuantizer::extractFrom(const List<T>& lst)
	{
		int items = lst.getLength();
		double percentile = double(items)/double(_iLevels);
		_lstCutvalues.clear();
		for (int i=1;i<_iLevels;i++)
			_lstCutvalues += (double)lst[(int)(i*percentile)];
	}

	template <class T> void EqualAreaQuantizer::extractFrom(const LinkedList<T>* lst)
	{
		int items = lst->getLength();
		double percentile = double(items)/double(_iLevels);
		_lstCutvalues.clear();
		const LinkedList<T>* next = lst;
		int index = 0,i=1;
		while (next && i<_iLevels)
			{
				if (index == (int)(i*percentile))
					{
						i++;
						_lstCutvalues += (double)next->getData();
					}
				next = next->getNext();
				index++;
			}
	}

	template <class T> void EqualAreaQuantizer::createList(const Matrix<T>& mat, List<T>& lst, int n)
	{
		const T *data = mat.getData();
		int size = mat.getRows()*mat.getColumns();
		if (n <=0 || n >= size)
			{
				for (int i=size;i--;data++)
					lst += *data;
			}
		else
			{
				double step = (double)size / (double)n;
				double pos = 0;
				int index = 0;
				do
					{
						lst += data[index];
						pos += step;
						index = int(pos+0.5);
					} while (index < size - 1);
			}
	}

	template <class T> void EqualAreaQuantizer::createList(const Matrix<T>& mat, SortedLinkedList<T>*& lst, int n)
	{
		const T *data = mat.getData();
		int size = mat.getRows()*mat.getColumns();
		SortedLinkedList<T>* oldNode = NULL;
		if (n <=0 || n >= size)
			{
				for (int i=size;i--;data++)
					{
						SortedLinkedList<T>* previous = NULL;
						SortedLinkedList<T>* newNode = new SortedLinkedList<T>(*data);
						if (lst)
							{
								if (oldNode && oldNode->data() < newNode->data())
									previous = oldNode->addNode(newNode);
								else									
									previous = lst->addNode(newNode);
							}
						if (!previous)
							lst = newNode;

						oldNode = newNode;
					}
			}
		else
			{
				double step = (double)size / (double)n;
				double pos = 0;
				int index = 0;
				do
					{
						SortedLinkedList<T>* previous = NULL;
						SortedLinkedList<T>* newNode = new SortedLinkedList<T>(data[index]);
						if (lst)
							{
								//We stored the last node.
								//If the old data is smaller than the current one,
								//we can seek the list from this point on.
								//By using '<' we ensure that the new node is never
								//added before the old one, and we need not worry
								//about splitting the sequence.
								if (oldNode && oldNode->data() < newNode->data())
									previous = oldNode->addNode(newNode);
								//Otherwise we must run from the beginning.
								else									
									previous = lst->addNode(newNode);
							}
						if (!previous)
							lst = newNode;

						oldNode = newNode;
						
						pos += step;
						index = int(pos+0.5);
					} while (index < size - 1);
			}
	}
}


#endif