#include "importmidi_chord.h"
#include "importmidi_inner.h"
#include "importmidi_chord.h"
#include "importmidi_clef.h"
#include "importmidi_operations.h"
#include "importmidi_quant.h"
#include "libmscore/mscore.h"
#include "libmscore/sig.h"
#include "mscore/preferences.h"

#include <set>


namespace Ms {
namespace MChord {

bool isGrandStaffProgram(int program)
      {
      const static std::set<int> grandStaffPrograms = {
                  // Piano
              0, 1, 2, 3, 4, 5, 6, 7
                  // Chromatic Percussion
            , 8, 10, 11, 12, 13, 15
                  // Organ
            , 16, 17, 18, 19, 20, 21, 23
                  // Strings
            , 46
                  // Ensemble
            , 50, 51, 54
                  // Brass
            , 62, 63
                  // Synth Lead
            , 80, 81, 82, 83, 84, 85, 86, 87
                  // Synth Pad
            , 88, 89, 90, 91, 92, 93, 94, 95
                  // Synth Effects
            , 96, 97, 98, 99, 100, 101, 102, 103
            };

      return grandStaffPrograms.find(program) != grandStaffPrograms.end();
      }

std::multimap<ReducedFraction, MidiChord>::iterator
findFirstChordInRange(std::multimap<ReducedFraction, MidiChord> &chords,
                      const ReducedFraction &startRangeTick,
                      const ReducedFraction &endRangeTick)
      {
      auto iter = chords.lower_bound(startRangeTick);
      if (iter != chords.end() && iter->first >= endRangeTick)
            iter = chords.end();
      return iter;
      }

std::multimap<ReducedFraction, MidiChord>::const_iterator
findFirstChordInRange(const std::multimap<ReducedFraction, MidiChord> &chords,
                      const ReducedFraction &startRangeTick,
                      const ReducedFraction &endRangeTick)
      {
      auto iter = chords.lower_bound(startRangeTick);
      if (iter != chords.end() && iter->first >= endRangeTick)
            iter = chords.end();
      return iter;
      }

const ReducedFraction& minAllowedDuration()
      {
      const static auto minDuration = ReducedFraction::fromTicks(MScore::division) / 32;
      return minDuration;
      }

ReducedFraction minNoteOffTime(const QList<MidiNote> &notes)
      {
      if (notes.isEmpty())
            return {0, 1};
      auto it = notes.begin();
      ReducedFraction minOffTime = it->offTime;
      for (++it; it != notes.end(); ++it) {
            if (it->offTime < minOffTime)
                  minOffTime = it->offTime;
            }
      return minOffTime;
      }

ReducedFraction maxNoteOffTime(const QList<MidiNote> &notes)
      {
      ReducedFraction maxOffTime(0, 1);
      for (const auto &note: notes) {
            if (note.offTime > maxOffTime)
                  maxOffTime = note.offTime;
            }
      return maxOffTime;
      }

ReducedFraction minNoteLen(const std::pair<const ReducedFraction, MidiChord> &chord)
      {
      const auto minOffTime = minNoteOffTime(chord.second.notes);
      return minOffTime - chord.first;
      }

ReducedFraction maxNoteLen(const std::pair<const ReducedFraction, MidiChord> &chord)
      {
      const auto maxOffTime = maxNoteOffTime(chord.second.notes);
      return maxOffTime - chord.first;
      }

void removeOverlappingNotes(QList<MidiNote> &notes)
      {
      QLinkedList<MidiNote> tempNotes;
      for (const auto &note: notes)
            tempNotes.append(note);

      for (auto noteIt1 = tempNotes.begin(); noteIt1 != tempNotes.end(); ++noteIt1) {
            for (auto noteIt2 = std::next(noteIt1); noteIt2 != tempNotes.end(); ) {
                  if (noteIt2->pitch == noteIt1->pitch) {
                                    // overlapping notes found
                        if (noteIt2->offTime > noteIt1->offTime)      // set max len before erase
                              noteIt1->offTime = noteIt2->offTime;
                        noteIt2 = tempNotes.erase(noteIt2);
                        qDebug("Midi import: removeOverlappingNotes: note was removed");
                        continue;
                        }
                  ++noteIt2;
                  }
            }
      notes.clear();
      for (const auto &note: tempNotes)
            notes.append(note);
      }

// remove overlapping notes with the same pitch

void removeOverlappingNotes(std::multimap<int, MTrack> &tracks)
      {
      for (auto &track: tracks) {
            auto &chords = track.second.chords;
            if (chords.empty())
                  continue;

            Q_ASSERT_X(MidiTuplet::areTupletRangesOk(chords, track.second.tuplets),
                       "MChord::removeOverlappingNotes", "Tuplet chord/note is outside tuplet "
                        "or non-tuplet chord/note is inside tuplet before overlaps remove");

            for (auto i1 = chords.begin(); i1 != chords.end(); ) {
                  const auto &onTime1 = i1->first;
                  auto &chord1 = i1->second;
                  removeOverlappingNotes(chord1.notes);

                  for (auto note1It = chord1.notes.begin(); note1It != chord1.notes.end(); ) {
                        auto &note1 = *note1It;

                        for (auto i2 = std::next(i1); i2 != chords.end(); ++i2) {
                              const auto &onTime2 = i2->first;
                              if (onTime2 >= note1.offTime)
                                    break;
                              auto &chord2 = i2->second;
                              if (chord1.voice != chord2.voice)
                                    continue;
                              for (auto &note2: chord2.notes) {
                                    if (note2.pitch != note1.pitch)
                                          continue;
                                                // overlapping notes found
                                    note1.offTime = onTime2;
                                    if (!note1.isInTuplet && chord2.isInTuplet) {
                                          if (note1.offTime > chord2.tuplet->second.onTime) {
                                                note1.isInTuplet = true;
                                                note1.tuplet = chord2.tuplet;
                                                }
                                          }
                                    else if (note1.isInTuplet && !chord2.isInTuplet) {
                                          note1.isInTuplet = false;
                                          }

                                    i2 = std::prev(chords.end());
                                    break;
                                    }
                              }
                        if (note1.offTime - onTime1 < MChord::minAllowedDuration()) {
                              note1It = chord1.notes.erase(note1It);
                              qDebug("Midi import: removeOverlappingNotes: note was removed");
                              continue;
                              }
                        ++note1It;
                        }
                  if (chord1.notes.isEmpty()) {
                        i1 = chords.erase(i1);
                        continue;
                        }
                  ++i1;
                  }

            MidiTuplet::removeEmptyTuplets(track.second);

            Q_ASSERT_X(MidiTuplet::areTupletRangesOk(chords, track.second.tuplets),
                       "MChord::removeOverlappingNotes", "Tuplet chord/note is outside tuplet "
                        "or non-tuplet chord/note is inside tuplet after overlaps remove");
            }
      }


#ifdef IMPORTMIDI_DEBUG

// check for equal on time values with the same voice that is invalid
bool areOnTimeValuesDifferent(const std::multimap<ReducedFraction, MidiChord> &chords)
      {
      std::map<ReducedFraction, int> onTimeVoices;
      for (const auto &chordEvent: chords) {
            const auto it = onTimeVoices.find(chordEvent.first);
            if (it == onTimeVoices.end())
                  onTimeVoices.insert({chordEvent.first, chordEvent.second.voice});
            else if (chordEvent.second.voice == it->second)
                  return false;
            }
      return true;
      }

bool areNotesLongEnough(const std::multimap<ReducedFraction, MidiChord> &chords)
      {
      for (const auto &chord: chords) {
            if (minNoteLen(chord) < minAllowedDuration())
                  return false;
            }
      return true;
      }

bool areBarIndexesSuccessive(const std::multimap<ReducedFraction, MidiChord> &chords)
      {
      int barIndex = 0;
      for (const auto &chord: chords) {
            const MidiChord &c = chord.second;
            if (c.barIndex < 0)
                  return false;
            if (c.barIndex < barIndex)
                  return false;
            barIndex = c.barIndex;
            }
      return true;
      }

bool isLastTickValid(const ReducedFraction &lastTick,
                     const std::multimap<ReducedFraction, MidiChord> &chords)
      {
      for (const auto &chord: chords) {
            if (maxNoteOffTime(chord.second.notes) > lastTick)
                  return false;
            }
      return true;
      }

bool isLastTickValid(const ReducedFraction &lastTick,
                     const std::multimap<int, MTrack> &tracks)
      {
      for (const auto &track: tracks) {
            if (!(isLastTickValid(lastTick, track.second.chords)))
                  return false;
            }
      return true;
      }

bool areBarIndexesSet(const std::multimap<ReducedFraction, MidiChord> &chords)
      {
      for (const auto &chord: chords) {
            if (chord.second.barIndex == -1)
                  return false;
            }
      return true;
      }

#endif

void setToNegative(ReducedFraction &v1, ReducedFraction &v2, ReducedFraction &v3)
      {
      v1 = ReducedFraction(-1, 1);
      v2 = ReducedFraction(-1, 1);
      v3 = ReducedFraction(-1, 1);
      }

bool hasNotesWithEqualPitch(const MidiChord &chord1, const MidiChord &chord2)
      {
      std::set<int> notes1;
      for (const auto &note: chord1.notes)
            notes1.insert(note.pitch);
      for (const auto &note: chord2.notes) {
            if (notes1.find(note.pitch) != notes1.end())
                  return true;
            }
      return false;
      }

void collectChords(
            std::multimap<int, MTrack> &tracks,
            const ReducedFraction &humanTolCoeff,
            const ReducedFraction &nonHumanTolCoeff)
      {
      for (auto &track: tracks)
            collectChords(track.second, humanTolCoeff, nonHumanTolCoeff);
      }

// based on quickthresh algorithm
//
// http://www.cycling74.com/docs/max5/refpages/max-ref/quickthresh.html
// (link date 9 July 2013)
//
// here are default values for audio, in milliseconds
// for midi there will be another values, in ticks

// all notes received in the left inlet within this time period are collected into a chord
// threshTime = 40 ms

// if there are any incoming values within this amount of time
// at the end of the base thresh time,
// the threshold is extended to allow more notes to be added to the chord
// fudgeTime = 10 ms

// this is an extension value of the base thresh time, which is used if notes arrive
// in the object's inlet in the "fudge" time zone
// threshExtTime = 20 ms

//     chord                             |<--fudge time-->|
// ------x-------------------------------|----------------|---------------------|------
//       |<-----------------thresh time------------------>|<--thresh ext time-->|
//
void collectChords(
            MTrack &track,
            const ReducedFraction &humanTolCoeff,
            const ReducedFraction &nonHumanTolCoeff)
      {
      auto &chords = track.chords;
      if (chords.empty())
            return;

      Q_ASSERT_X(areNotesLongEnough(chords),
                 "MChord::collectChords", "There are too short notes");

      const auto &opers = midiImportOperations.data()->trackOpers;
      const auto minAllowedDur = minAllowedDuration();

      const auto threshTime = (opers.isHumanPerformance.value())
                                    ? minAllowedDur * humanTolCoeff
                                    : minAllowedDur * nonHumanTolCoeff;
      const auto fudgeTime = threshTime / 4;
      const auto threshExtTime = threshTime / 2;

      ReducedFraction currentChordStart;
      ReducedFraction curThreshTime;
                  // if note onTime goes after max chord offTime
                  // then this is not a chord but arpeggio
      ReducedFraction maxOffTime;

      setToNegative(currentChordStart, curThreshTime, maxOffTime); // invalidate

      for (auto it = chords.begin(); it != chords.end(); ) {
            if (it->second.isInTuplet) {
                  setToNegative(currentChordStart, curThreshTime, maxOffTime);
                  ++it;
                  continue;
                  }

            const auto maxNoteOffTime = MChord::maxNoteOffTime(it->second.notes);
            if (it->first < currentChordStart + curThreshTime) {

                  // this branch should not be executed when it == chords.begin()
                  Q_ASSERT_X(it != chords.begin(),
                             "MChord: collectChords", "it == chords.begin()");

                  if (it->first <= maxOffTime - minAllowedDur) {
                                    // add current note to the previous chord
                        auto chordAddTo = std::prev(it);
                        if (it->second.voice != chordAddTo->second.voice) {
                              setToNegative(currentChordStart, curThreshTime, maxOffTime);
                              ++it;
                              continue;
                              }

                        if (!hasNotesWithEqualPitch(chordAddTo->second, it->second)) {
                              for (const auto &note: it->second.notes)
                                    chordAddTo->second.notes.push_back(note);
                              if (maxNoteOffTime > maxOffTime)
                                    maxOffTime = maxNoteOffTime;
                              }
                        if (it->first >= currentChordStart + curThreshTime - fudgeTime
                                    && curThreshTime == threshTime) {
                              curThreshTime += threshExtTime;
                              }

                        it = chords.erase(it);
                        continue;
                        }
                  }

            currentChordStart = it->first;
            maxOffTime = maxNoteOffTime;
            curThreshTime = threshTime;
            ++it;
            }

      Q_ASSERT_X(areOnTimeValuesDifferent(chords),
                 "MChord: collectChords",
                 "onTime values of chords are equal but should be different");
      }

void sortNotesByPitch(std::multimap<ReducedFraction, MidiChord> &chords)
      {
      struct {
            bool operator()(const MidiNote &note1, const MidiNote &note2)
                  {
                  return note1.pitch < note2.pitch;
                  }
            } pitchSort;

      for (auto &chordEvent: chords) {
                        // in each chord sort notes by pitches
            auto &notes = chordEvent.second.notes;
            qSort(notes.begin(), notes.end(), pitchSort);
            }
      }

void sortNotesByLength(std::multimap<ReducedFraction, MidiChord> &chords)
      {
      struct {
            bool operator()(const MidiNote &note1, const MidiNote &note2)
                  {
                  return note1.offTime < note2.offTime;
                  }
            } lenSort;

      for (auto &chordEvent: chords) {
                        // in each chord sort notes by lengths
            auto &notes = chordEvent.second.notes;
            qSort(notes.begin(), notes.end(), lenSort);
            }
      }

// find notes of each chord that have different durations
// and separate them into different chords
// so all notes inside every chord will have equal lengths

void splitUnequalChords(std::multimap<int, MTrack> &tracks)
      {
      for (auto &track: tracks) {
            std::vector<std::pair<ReducedFraction, MidiChord>> newChordEvents;
            auto &chords = track.second.chords;
            if (chords.empty())
                  continue;
            sortNotesByLength(chords);
            for (auto &chordEvent: chords) {
                  auto &chord = chordEvent.second;
                  auto &notes = chord.notes;
                  ReducedFraction offTime;
                  for (auto it = notes.begin(); it != notes.end(); ) {
                        if (it == notes.begin())
                              offTime = it->offTime;
                        else {
                              ReducedFraction newOffTime = it->offTime;
                              if (newOffTime != offTime) {
                                    MidiChord newChord(chord);
                                    newChord.notes.clear();
                                    for (int j = it - notes.begin(); j > 0; --j)
                                          newChord.notes.push_back(notes[j - 1]);
                                    newChordEvents.push_back({chordEvent.first, newChord});
                                    it = notes.erase(notes.begin(), it);
                                    continue;
                                    }
                              }
                        ++it;
                        }
                  }
            for (const auto &event: newChordEvents)
                  chords.insert(event);
            }
      }

ReducedFraction findMinDuration(const ReducedFraction &onTime,
                                const QList<MidiChord> &midiChords,
                                const ReducedFraction &length)
      {
      ReducedFraction len = length;
      for (const auto &chord: midiChords) {
            for (const auto &note: chord.notes) {
                  if ((note.offTime - onTime < len)
                              && (note.offTime - onTime != ReducedFraction(0, 1)))
                        len = note.offTime - onTime;
                  }
            }
      return len;
      }

void mergeChordsWithEqualOnTimeAndVoice(std::multimap<int, MTrack> &tracks)
      {
      for (auto &track: tracks) {
            auto &chords = track.second.chords;
            if (chords.empty())
                  continue;
                        // the key is pair<onTime, voice>
            std::map<std::pair<ReducedFraction, int>,
                     std::multimap<ReducedFraction, MidiChord>::iterator> onTimes;

            for (auto it = chords.begin(); it != chords.end(); ) {
                  const auto &onTime = it->first;
                  const int voice = it->second.voice;
                  auto fit = onTimes.find({onTime, voice});
                  if (fit == onTimes.end()) {
                        onTimes.insert({{onTime, voice}, it});
                        }
                  else {
                        auto &oldNotes = fit->second->second.notes;
                        auto &newNotes = it->second.notes;
                        oldNotes.append(newNotes);
                        it = chords.erase(it);
                        continue;
                        }
                  ++it;
                  }
            }
      }

int chordAveragePitch(const QList<MidiNote> &notes, int beg, int end)
      {
      Q_ASSERT_X(!notes.isEmpty(), "MChord::chordAveragePitch", "Empty notes");
      Q_ASSERT_X(end > 0 && beg >= 0 && end > beg,
                 "MChord::chordAveragePitch", "Invalid note indexes");

      int sum = 0;
      for (int i = beg; i != end; ++i)
            sum += notes[i].pitch;
      return qRound(sum * 1.0 / (end - beg));
      }

int chordAveragePitch(const QList<MidiNote> &notes)
      {
      Q_ASSERT_X(!notes.isEmpty(), "MChord::chordAveragePitch", "Empty notes");

      return chordAveragePitch(notes, 0, notes.size());
      }

// it's an optimization function: we can don't check chords
// with (on time + max chord len) < given time moment
// because chord cannot be longer than found max length

ReducedFraction findMaxChordLength(const std::multimap<ReducedFraction, MidiChord> &chords)
      {
      ReducedFraction maxChordLength;

      for (const auto &chord: chords) {
            const auto offTime = maxNoteOffTime(chord.second.notes);
            if (offTime - chord.first > maxChordLength)
                  maxChordLength = offTime - chord.first;
            }
      return maxChordLength;
      }

std::vector<std::multimap<ReducedFraction, MidiChord>::const_iterator>
findChordsForTimeRange(
            int voice,
            const ReducedFraction &onTime,
            const ReducedFraction &offTime,
            const std::multimap<ReducedFraction, MidiChord> &chords,
            const ReducedFraction &maxChordLength)
      {
      std::vector<std::multimap<ReducedFraction, MidiChord>::const_iterator> result;

      if (chords.empty())
            return result;

      auto it = chords.lower_bound(offTime);
      if (it == chords.begin())
            return result;
      --it;

      while (it->first + maxChordLength > onTime) {
            const MidiChord &chord = it->second;
            if (chord.voice == voice) {
                  const auto chordInterval = std::make_pair(it->first, maxNoteOffTime(chord.notes));
                  const auto durationInterval = std::make_pair(onTime, offTime);

                  if (MidiTuplet::haveIntersection(chordInterval, durationInterval))
                        result.push_back(it);
                  }
            if (it == chords.begin())
                  break;
            --it;
            }

      return result;
      }

void setBarIndexes(
            std::multimap<ReducedFraction, MidiChord> &chords,
            const ReducedFraction &basicQuant,
            const ReducedFraction &lastTick,
            const TimeSigMap *sigmap)
      {
      if (chords.empty())
            return;
      auto it = chords.begin();
      for (int barIndex = 0;; ++barIndex) {       // iterate over all measures by indexes
            const auto endBarTick = ReducedFraction::fromTicks(sigmap->bar2tick(barIndex + 1, 0));
            if (endBarTick <= it->first)
                  continue;
            for (; it != chords.end(); ++it) {
                  const auto onTime = Quantize::findQuantizedChordOnTime(*it, basicQuant);
#ifdef IMPORTMIDI_DEBUG
                  const auto barStart = ReducedFraction::fromTicks(sigmap->bar2tick(barIndex, 0));
                  Q_ASSERT_X(!(it->first >= barStart && onTime < barStart),
                             "MChord::setBarIndexes", "quantized on time cannot be in previous bar");
#endif
                  if (onTime < endBarTick) {
                        it->second.barIndex = barIndex;
                        continue;
                        }
                  break;
                  }
            if (it == chords.end() || endBarTick > lastTick)
                  break;
            }

      Q_ASSERT_X(areBarIndexesSet(chords),
                 "MChord::setBarIndexes", "Not all bar indexes were set");
      Q_ASSERT_X(areBarIndexesSuccessive(chords),
                 "MChord::setBarIndexes", "Bar indexes are not successive");
      }

} // namespace MChord
} // namespace Ms