/*
 * Copyright 2009-2010  Stefan Gehn <stefan@srcbox.net>
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of 
 * the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "Decoder.hpp"
#include "settings.hpp"

#include <cmath>
#include <qdebug.h>


namespace IrTouch
{


Decoder::Decoder()
{
  qDebug() << "Decoder::Decoder()";
	qDebug() << "Delta values:";
	deltaMergeX = Settings::self()->deltaMergeX();
	deltaMergeY = Settings::self()->deltaMergeY();
	qDebug() << "  Merge: " << deltaMergeX << ";" << deltaMergeY;
	deltaMoveX = Settings::self()->deltaMoveX();
	deltaMoveY = Settings::self()->deltaMoveY();
	qDebug() << "  Move : " << deltaMoveX << ";" << deltaMoveY;
}

/**
 Liefert die nächsten beiden RawValues, die zu @p val "passen" könnten.
 @param rvIdx Index des naheliegendsten Nachfolgewerts für @p val
 @param rvDiff Abweichung vom RawValue an @p rvIdx zum Wert @p val
 @param rvAltIdx Index des zweiten naheliegendsten Nachfolgewerts
 **/
static void getNearest(const RawValueList &rawValues, const Value &val, const int delta, int &rvIdx, int &rvDiff, int &rvAltIdx)
{
	rvAltIdx = -1;
	rvIdx = -1;
	rvDiff = INT_MAX;

	for (int rvi = 0; rvi < rawValues.count(); rvi++)
	{
		const RawValue &rv = rawValues.at(rvi);

		// Finde zugehörigen Wert in letzten Touchdaten.
		// Es wird nach einem minimalen Unterschied gesucht, es wird also nicht
		// der erste RawValue genutzt, der auf den zu identifizierenden
		// Wert passt, sondern der Wert mit minimalstem Abstand zum vorigen Wert.
		int ccDiff = qAbs(rv.center() - val.center());
		if ( (ccDiff < delta) && (ccDiff < rvDiff) )
		{
			rvAltIdx = rvIdx; // zweitbesten wert merken
			rvIdx = rvi; // besten wert merken
			rvDiff = ccDiff;
		}
	}
}

static void identify(RawValueList &rawValues, ValueList &values, const int delta)
{
	for (int o = 0; o < values.size(); ++o)
	{
		Value &oldV = values[o];
		// Nur alte Einzelwerte betrachten
		if (oldV.mIsMerge || oldV.mHandled)
			continue;
		//qDebug() << "BEGIN identify() on " << oldV ;

		int rvIdx = -1;
		int rvDiff = INT_MAX;
		int altRvIdx = -1;
		getNearest(rawValues, oldV, delta, rvIdx, rvDiff, altRvIdx);
		if (rvIdx == -1)
		{
			qDebug() << "NO matching RawValue found for" << oldV;
			continue;
		}
		//qDebug() << "rvIdx" << rvIdx << "; altRvIdx:" << altRvIdx;

		// Prüfen, ob der gefundene RawValue evtl. auf den nächsten Wert besser passt!
		if (o + 1 < values.size())
		{
			const Value &nextValue = values.at(o + 1);
			int nextRvIdx = -1;
			int nextRvDiff = INT_MAX;
			int nextAltRvIdx = -1; // hier ungenutzt
			// Besten RawValue für den nächsten Wert raussuchen
			getNearest(rawValues, nextValue, delta, nextRvIdx, nextRvDiff, nextAltRvIdx);
			if ((nextRvIdx == rvIdx) && (nextRvDiff < rvDiff))
			{ // RawValue passt besser auf nachfolgenden Wert
				//qDebug() << "OOPS; rawvalue fits better to" << nextValue << "than" << oldV;
				rvIdx = altRvIdx;
				// Spezialfall: RawValue passt auf nachfolgenden Wert aber
				// "unser" RawValue ist garnicht nicht mehr existent
				if (rvIdx == -1)
				{
					qDebug() << "NO matching RawValue found for" << oldV;
					continue;
				}
			}
		}

		const RawValue &rv = rawValues.at(rvIdx);
		//qDebug() << "Updating" << oldV << "with (" << rv.value() << "->" << rv.extent() << ")";
		oldV.update(rv.value(), rv.extent());
		oldV.mIsMerge = false;
		oldV.mHandled = true;
		rawValues.removeAt(rvIdx);

		//qDebug() << "END identify() on " << oldV ;
	} // for()


	// Alle verbliebenden RawValues "passen" zu keinem Value, neue Value-Instanzen erzeugen
	RawValueListIterator it = rawValues.begin();
	while (it != rawValues.end())
	{
		RawValue &rv = *it;

		// Neuen Wert (mit neuer ID) erzeugen
		Value newV(rv.value(), rv.extent());
		newV.mIsMerge = false;
		newV.mHandled = true;
		values.append(newV);

		it = rawValues.erase(it);
	}
}

/**
 * Suche nach zusammenliegenden Werten, die im neuen Paket als ein
 * einzelner (Merge-)Wert auftreten.
 **/
static QList<QList<Value *> > getMerges(ValueList &values)
{
  int mergeEnd = -1;
  QList<QList<Value *> > ret;
  QList<Value *> oldMerges;

  // suche nach zusammenfallenden Values (d.h. ohne platz dazwischen)
  for (int oi = 0; oi < values.size(); ++oi)
  {
    Value *oldVal = &values[oi];

    // entweder ist der aktuelle wert kein merge (mehr) oder
    // es gibt eine spalte zwischen dem letzten Merge und dem jetzt gefundenen.
    // Letzteres bedeutet, dass wir einen neuen Merge gefunden haben
    if (!oldVal->mIsMerge || (oldVal->mIsMerge && (mergeEnd > 0) && (oldVal->start() > mergeEnd + 1)))
    {
      //qDebug() << "Resetting oldMerges";
      if (!oldMerges.isEmpty())
      {
        ret.append(oldMerges);
        oldMerges.clear();
      }
      mergeEnd = -1;
    }
    else if (oldVal->mIsMerge)
    {
      //qDebug() << "====== Adding" << *oldVal << "to oldMerges";
      // wert in liste zusammenfallender merges merken
      oldMerges.append(oldVal);
      // startposition merken
      if (mergeEnd == -1)
        mergeEnd = oldVal->value();
      // ausdehnung aufaddieren
      mergeEnd += oldVal->extent();
    }
  }

  if (!oldMerges.isEmpty())
    ret.append(oldMerges);

  return ret;
}

void getMergeMinMax(const QList<Value *> &merges, int &min, int &max)
{
  min = INT_MAX;
  max = 0;

  for (int o = 0; o < merges.size(); ++o)
  {
    Value *v = merges.at(o);
    min = qMin(min, v->start());
    max = qMax(max, v->end());
  }
}

// Sucht die in "oldMerges" übergebene Liste zusammenhängender Values in "rawValues"
static void assignSinglePreviousMerge(const QList<Value *> &oldMerge, RawValueList &rawValues, const int delta)
{
  // Start- Endposition des bisherigen Merges holen
  int mergeStart, mergeEnd;
  getMergeMinMax(oldMerge, mergeStart, mergeEnd);

	qDebug() << "assignSinglePreviousMerge();" << "start" << mergeStart << "; end" << mergeEnd;

  // den durch mergeStart und mergeEnd definierten Merge als
  // Einzelwert in den Rawdaten suchen...

	RawValueListIterator it = rawValues.begin();
	while (it != rawValues.end())
	{
		RawValue &rv = *it;

    // Abweichung von Start- und Endposition berechnen
    int startDiff = rv.start() - mergeStart;
    int endDiff = rv.end() - mergeEnd;

		qDebug() << "raw: " << rv.start() << "->" << rv.extent() << "|" << rv.end();
		qDebug() << "start diff:" << startDiff << "; end diff:" << endDiff;

    // Abstand zwischen den beiden Werten prüfen
		if (qAbs(startDiff + endDiff) > delta)
		{
			it++;
      continue;
		}

		// Erwartete Startposition des ersten Wertes
    int curPos = rv.start();

    for (int no = 0; no < oldMerge.size(); ++no)
    {
      Value *val = oldMerge[no];
			qDebug() << "Vorher   " << *val;

      int vStart = val->start();
      int vExt = val->extent();
      int gap = 0;
			qDebug() << "vStart:" << vStart << " ;  curPos:" << curPos;

      if (vStart != curPos)
      {
        // Aktueller Wert ist nicht an der erwarteten Position =>
        // korrigiere Startpos. des Werts
        vStart = curPos;

        // Abstand zum bisherigen Nachfolgewert berechnen
        if (no + 1 < oldMerge.size())
          gap = oldMerge[no + 1]->start() - (vStart + vExt);

        // Prüfen, ob der Wert einen nachfolgenden Wert berührt/überlappt
        if (gap > 0)
        {
					qDebug() << "KORRIGIERE Spalt mit Breite" << gap;
          // Keine Berührung/Überlappung mehr => Spalt zwischen den beiden aufteilen
          // Wert wird aufgerundet um keinen Spalt entstehen zu lassen
          vExt += (gap / 2) + 1;
          // Nächsten "erwarteten" Wert an die Endposition des aktuellen Wertes
          // verschieben um den entstandenen Spalt zu kompensieren
          gap = 0;
        }
				else if (gap < 0)
				{
					qDebug() << "Negative gap to following value:" << gap << "; vExt is" << vExt;
					if (vStart > oldMerge[no + 1]->start())
					{
						qDebug() << "ALERT: moving value below following value, slightly adjusting gap!";
						//FIXME: Benötigt Logik die Reihenfolgeerhaltend wirkt, da nur die
						//       nachfolgende Swap-Logik eine Reihenfolgeänderung
						//       durchführen sollte
						gap = (int)(((double)gap) * 0.8);
					}
				}
      }

      // Abstand zum Ende des RawValues bestimmen, falls der Abstand negativ ist,
      // so ragt der aktuelle Wert aus dem RawValue aus und muss korrigiert werden
      int endOverlap = rv.end() - (vStart + vExt);
      if (endOverlap < 0)
      {
        //TODO: Benötigt bessere Logik um festzustellen ob vStart oder vExt korrigiert werden sollte

				int prevValueStart = (no > 0) ? (oldMerge[no - 1]->start()) : 0;

        // Letzter Wert im Merge, nicht kürzen sondern nach oben schieben
				if (
						(no == (oldMerge.size() - 1)) &&
						(vStart + endOverlap > prevValueStart) &&
						(vStart + endOverlap > rv.start())
					)
        {
					qDebug() << "Letzter Wert ragt am Ende raus, korrigiere vStart um endOverlap:" << endOverlap;
          vStart += endOverlap;
          gap = 0; // egal
          //TODO: abschließende Prüfung ob der Wert nun oben rausragt!
        }
        else
        {
					qDebug() << "End of val" << val->id() << "below RawValue end," <<
							" fixing vExt by endOverlap:" << endOverlap;
          vExt += endOverlap;
					if (no + 1 < oldMerge.size())
          {
						qDebug() << "old gap:" << gap;
            gap = oldMerge[no + 1]->start() - (vStart + vExt);
						qDebug() << "new gap:" << gap;
          }
        }
      }

      val->update(vStart, vExt);
      val->mHandled = true;
			qDebug() << "Nachher   " << *val;

      curPos = vStart + vExt + gap;
			qDebug() << "Erwarte nachfolgenden Wert bei" << curPos << "; gap war" << gap;
    }

    for (int no = 0; no < oldMerge.size() - 1; ++no)
    {
      Value *val1 = oldMerge[no];
      Value *val2 = oldMerge[no + 1];

			// High- und Low-Watermark bei denen ein Swap vorgemerkt und durchgeführt wird
      int minSwapOverlap = (int)((double)qMin(val1->extent(), val2->extent()) * 0.70);
      int maxDoSwapOverlap = (int)((double)qMin(val1->extent(), val2->extent()) * 0.50);

      int currOverlap = /*qAbs*/(val1->end() - val2->start());
      Q_ASSERT(currOverlap > -1);

      val1->mMaxMergeOverlap = qMax(val1->mMaxMergeOverlap, currOverlap);

      // aktuelle überdeckung ist einiges kleiner als die maximale überdeckung
      if (currOverlap < maxDoSwapOverlap)
      {
        // maximale überdeckung war groß genug für einen swap
        if (val1->mMaxMergeOverlap > minSwapOverlap)
        {
					qDebug() << "==========";
          qDebug() << " START SWAP:" << *val1 << "/" << *val2;
          qDebug() << "  " << val1->mMaxMergeOverlap << "(MaxMergeOverlap)   >" <<
            minSwapOverlap << "(minSwapOverlap)";
          qDebug() << "  " << currOverlap << "(currOverlap)   <" <<
						maxDoSwapOverlap << "(maxDoSwapOverlap)";

          val1->swapValues(*val2);
          val1->mMaxMergeOverlap = 0;
          val2->mMaxMergeOverlap = 0;

					qDebug() << " END SWAP :" << *val1 << "/" << *val2;
					qDebug() << "==========";
        }
/*
        else
        {
          qDebug() << "Ignoriere moeglichen Swap," <<
            val1->mMaxMergeOverlap << "(MaxMergeOverlap)   <" <<
            minSwapOverlap << "(minSwapOverlap)";
				}
*/
        // Maximalwert vergessen, da die Überlappung zu gering geworden ist
        val1->mMaxMergeOverlap = 0;
        if (val2->mMaxMergeOverlap > 0)
          qDebug() << "OOPS, Zweiter Wert hat MaxMergeOverlap:" <<  val2->mMaxMergeOverlap;

        ++no; // skip the second value
      }

    }

		// merge value wurde in raw-values gefunden und bearbeitet
		it = rawValues.erase(it);
    break;
  }

	qDebug() << "assignSinglePreviousMerge(); END ===";
}

// suche nach zusammenliegenden werten, die im neuen paket als ein
// einzelner (merge-)wert sichtbar sind
static void assignPreviousMerges(RawValueList &rawValues, ValueList &values, const int delta)
{
  QList<QList<Value *> > oldMerges = getMerges(values);

  for (int i = 0; i < oldMerges.size(); ++i)
  {
		assignSinglePreviousMerge(oldMerges.at(i), rawValues, delta);
  }
}

//! Neuen Einzelwert aus "rawValues" zwei alten, nahe zusammenliegenden werten zuordnen
static void assignNewMerges(RawValueList &rawValues, ValueList &values, const int delta)
{
  for (int o = 0; o < values.size() - 1; ++o)
  {
    // TODO: prüfen, welcher der werte die kleinere startposition besitzt,
    // es sollte eigentlich immer oldV1 sein
    Value &oldV1 = values[o];
    Value &oldV2 = values[o + 1];

    // Prüfen ob es "Einzelwerte" sind, alte Merges werden hier ignoriert
    if (oldV1.mIsMerge || oldV2.mIsMerge)
      continue;

    //TODO: Merge von einem Einzelwert mit einem vorherigen Merge ermöglichen?
    //qDebug() << "assignNewMerges() zwischen" << oldV1 << " / " << oldV2;

    // Abstand zwischen den beiden Werten prüfen
		if (qAbs(oldV2.start() - oldV1.end()) > delta)
      continue;

    //qDebug() << "Suche RawValue der vergleichbar mit" << oldV1 << "und" << oldV2 << "ist.";
    // Einzelnen RawWert suchen der ähnlich zu oldV1 + oldV2 ist
		RawValueListIterator it = rawValues.begin();
		while (it != rawValues.end())
		{
			RawValue &rv = *it;

      //qDebug() << "(" << rv.value << "->" << rv.extent << ")  <= ??? => " << oldV1 << " / " << oldV2;
      int valDiff = qAbs(rv.start() - oldV1.start());
			int extDiff = qAbs(rv.end() - oldV2.end());
			// Abstand zwischen neuem Wert und altem Wert prüfen
			if ( (valDiff > delta) || (extDiff > delta))
			{
				it++;
				continue;
			}

      //qDebug() << "(" << rv.value << "->" << rv.extent << ")  ~~ " << oldV1 << " / " << oldV2;

      qreal extSum = (oldV1.extent() + oldV2.extent());
			qreal extSumDiff = rv.extent() - extSum;
      //qDebug() << "extSumDiff" << extSumDiff;

      qreal v1ExtFactor = oldV1.extent() / extSum;
      qreal v2ExtFactor = oldV2.extent() / extSum;

      int newV1Ext = oldV1.extent() + (int)(v1ExtFactor * extSumDiff);
      int newV2Ext = oldV2.extent() + (int)(v2ExtFactor * extSumDiff);

      //qDebug() << "V1 old extent:" << oldV1.extent() << "; new extent" << newV1Ext;
      //qDebug() << "V2 old extent:" << oldV2.extent() << "; new extent" << newV2Ext;
      //qDebug() << rv.start() + newV1Ext + newV2Ext << " == " << rv.end() << "?";

      oldV1.update(rv.start(), newV1Ext /* rv.extent / 2*/);
      oldV1.mHandled = true;
      oldV1.mIsMerge = true;
      oldV1.mMaxMergeOverlap = 0;

      oldV2.update(rv.start() + newV1Ext, newV2Ext /*rv.extent / 2*/);
      oldV2.mHandled = true;
      oldV2.mIsMerge = true;
      oldV2.mMaxMergeOverlap = 0;

			it = rawValues.erase(it);
      break;
		} // while
  }
}

static void splitPreviousMerge(const QList<Value *> &oldMerge, QList<RawValue> &rawValues, const int delta)
{
  int mergeStart;
  int mergeEnd;
  getMergeMinMax(oldMerge, mergeStart, mergeEnd);

	qDebug() << "splitPreviousMerge();" << "start" << mergeStart << "; end" << mergeEnd;

	// Find two adjacent raw values that have a similar size/pos compared to a previous merge

	qDebug() << "splitPreviousMerge();" << "rawValues count:" << rawValues.count();
	RawValueListIterator it = rawValues.begin();
	while ((it != rawValues.end()) && ((it + 1) != rawValues.end()))
	{
		RawValue &newV1 = *it;
		RawValue &newV2 = *(it + 1);

    int startDiff = newV1.start() - mergeStart;
    int endDiff = newV2.end() - mergeEnd;

#if 1
		//if (qAbs(startDiff) < (delta * 2.5) || qAbs(endDiff) < (delta * 2.5))
    {
			qDebug() << "splitPreviousMerge(); raw1: " << newV1.start() << "|-> " << newV1.extent() << " <-|" << newV1.end();
			qDebug() << "splitPreviousMerge(); raw2: " << newV2.start() << "|-> " << newV2.extent() << " <-|" << newV2.end();
			qDebug() << "splitPreviousMerge(); start diff:" << startDiff << "; end diff:" << endDiff;
    }
#endif

    // Startposition und Breite von neuen Werten und altem Wert prüfen
		if (qAbs(startDiff) > delta || qAbs(endDiff) > delta)
		{
			it++;
      continue;
		}

		qDebug() << "splitPreviousMerge(); SPLITTING with start diff:" << startDiff << "; end diff:" << endDiff;
    if (oldMerge.size() > 2)
    {
			 qWarning() << "splitPreviousMerge(); Splitting of multiple values not implemented!";
    }
    else
    {
      Value *oldV1 = oldMerge[0];
			oldV1->update(newV1.start(), newV1.extent());
      oldV1->mIsMerge = false;
      oldV1->mMaxMergeOverlap = 0;
      oldV1->mHandled = true;

      Value *oldV2 = oldMerge[1];
			oldV2->update(newV2.start(), newV2.extent());
      oldV2->mIsMerge = false;
      oldV2->mMaxMergeOverlap = 0;
      oldV2->mHandled = true;
    }

		it = rawValues.erase(it);
		Q_ASSERT(it != rawValues.end()); // there should be two values before reaching end()
		it = rawValues.erase(it);
		break;
  }
}

//! Zwei (nahe beieinander liegende) Werte "rawValues" einem alten Mergewert zuordnen
static void assignSplitMerges(RawValueList &rawValues, ValueList &values, const int delta)
{
  /* Ablauf
   * - nahe beieinander liegende Werte in rawValues finden
   * - prüfen ob deren Position mit (virtuellen) Mergewerten aus values übereinstimmt
   * - values entsprechend aktualisieren und Mergeflag löschen
   */
  QList<QList<Value *> > oldMerges = getMerges(values);
  for (int i = 0; i < oldMerges.size(); ++i)
  {
		splitPreviousMerge(oldMerges[i], rawValues, delta);
  }
}


void Decoder::removeUnhandledValues(ValueList &vl)
{
  for (int i = vl.size() - 1; i > -1; --i)
  {
    const Value &val = vl.at(i);
    if (val.mHandled == false)
    {
      //qDebug() << "Removing outdated value" << val;
      vl.removeAt(i);
    }
  }
}




void Decoder::decodePacket(const IrTouch::Packet &packet)
{
	//qDebug() << "Decoder::decodePacket() IN:" << packet.rawXValues().size() << packet.rawYValues().size();

	// Copy raw-values temporarily in order to (re)set the used flags on them
	RawValueList rawX = packet.rawXValues();
	RawValueList rawY = packet.rawYValues();

  for (int xo = 0; xo < mData.mXValues.size(); ++xo)
    mData.mXValues[xo].mHandled = false;

  for (int yo = 0; yo < mData.mYValues.size(); ++yo)
    mData.mYValues[yo].mHandled = false;

	/*
	 * Bisherige Merges die sich aufgetrennt haben in neuen Daten suchen
	 *   - alt: ein wert mit höhe h
	 *   - neu: zwei werte mit höhe h1 und höhe h2 wobei h1+h2 ~ h
	 */
	assignSplitMerges(rawX, mData.mXValues, deltaMergeX);
	assignSplitMerges(rawY, mData.mYValues, deltaMergeY);

	/*
   * Bisherige Merges in aktuellen Daten wiederfinden
   */
	assignPreviousMerges(rawX, mData.mXValues, deltaMergeX);
	assignPreviousMerges(rawY, mData.mYValues, deltaMergeY);

  /*
   * Neue Merges suchen, die zuvor getrennt waren
   *   - alt: zwei werte mit höhe h1 und h2
   *   - neu: ein wert mit höhe h, wobei h < h1+h2 && h > min(h1, h2)
   */
	assignNewMerges(rawX, mData.mXValues, deltaMergeX);
	assignNewMerges(rawY, mData.mYValues, deltaMergeY);

  /*
   * Verbliebene neue Daten mit IDs der verbliebenen alten Daten
   * identifizieren oder neue IDs vergeben
   */
	identify(rawX, mData.mXValues, deltaMoveX);
	identify(rawY, mData.mYValues, deltaMoveY);

  // Alle Werte die nicht (wieder) identifiziert werden konnten entfernen
	removeUnhandledValues(mData.mXValues);
  removeUnhandledValues(mData.mYValues);

  // Sortierung der Values nach Startposition wiederherstellen
  qSort(mData.mXValues);
  qSort(mData.mYValues);

  /*
   * Rectangles aus den nun mit Ids versehenen Values erstellen oder aktualisieren
   */
  mData.updateRects();
  mData.updateObjectType();

	/*
	 * 1:1-Kopie der Rawwerte erstellen
	 */
	mData.mRawXValues = packet.rawXValues();
	mData.mRawYValues = packet.rawYValues();

  //qDebug() << "Decoder::dataReceived() OUT:" << mData.xValues().size() << mData.yValues().size();
}

} // namespace IrTouch

#include "moc_Decoder.cpp"