// **********************************************
// File: FORMAT.CPP
// Musical text formatting functions

#include "muzika.h"
#include <alloc.h>
#include <values.h>

// **********************************************
// FindMinDuration finds the minimum in a list and
// returns its index. This function is used to find
// the minimum duration of the next object among several staves.

int FindMinDuration(int *duration, int multiplicity)
{
  int min = MAXINT, minIndex;
  int *p = duration;

  while (multiplicity--) {
    if (min > *p) {
      min = *p;
      minIndex = p-duration;
    }
    ++p;
  }

  return minIndex;
}

// **********************************************
// FormatMultipleStaff reformats a multiple staff.
// This function is called once for every multiple staff in the part.

void FormatMultipleStaff(int baseStaff)
{
  // Create a few lists for use in the algorithm
  Part &p = *((Part *) &melody.part[displayedPart]);
  int *duration = (int *) malloc(p.multiplicity()*sizeof(int));
  int *index = (int *) malloc(p.multiplicity()*sizeof(int));
  BOOL *atCommon = (int *) malloc(p.multiplicity()*sizeof(BOOL));
  BOOL *staffEnd = (int *) malloc(p.multiplicity()*sizeof(BOOL));
  memset(duration, 0, p.multiplicity()*sizeof(int));
  memset(index, 0, p.multiplicity()*sizeof(int));
  memset(atCommon, 0, p.multiplicity()*sizeof(BOOL));
  memset(staffEnd, 0, p.multiplicity()*sizeof(BOOL));
  int X = 0;
  BOOL multipleEnd, multipleReached = FALSE;

  // Create unions of the continuousObject lists sorted by Xleft and Xright
  IndexedList sortedByLeft, sortedByRight;
  int leftIndex, rightIndex;
  for (int staffIndex = 0; staffIndex < p.multiplicity(); ++staffIndex) {
    Staff &s = *((Staff *) &p.staff[baseStaff+staffIndex]);
    for (int orgIndex = 0; orgIndex < s.continuousObject.number(); ++orgIndex) {
      for (leftIndex = 0;
        leftIndex < sortedByLeft.number() &&
          ((ContinuousObject *) &sortedByLeft[leftIndex])->Xleft() <=
          ((ContinuousObject *) &s.continuousObject[orgIndex])->Xleft();
        ++leftIndex);
      sortedByLeft.insertAt(s.continuousObject[orgIndex], leftIndex);
      for (rightIndex = 0;
        rightIndex < sortedByRight.number() &&
          ((ContinuousObject *) &sortedByRight[rightIndex])->Xright() <=
          ((ContinuousObject *) &s.continuousObject[orgIndex])->Xright();
        ++rightIndex);
      sortedByRight.insertAt(s.continuousObject[orgIndex], rightIndex);
    }
  }

  // Loop as long as the end has not been reached on all staves
  do {
    // Find the staff with the minimum duration of the next object
    int minIndex = FindMinDuration(duration, p.multiplicity());
    int minDuration = duration[minIndex];
    int maxWidth = 0;
    multipleEnd = TRUE;

    // Subtract the minimum duration from all staves;
    // place the next object on the ones which reach 0 as a result
    for (staffIndex = 0; staffIndex < p.multiplicity(); ++staffIndex) {
      Staff &s = *((Staff *) &p.staff[baseStaff+staffIndex]);

      if (atCommon[staffIndex] || !(duration[staffIndex] -= minDuration)) {
        // The next object duration has reached 0:
        // place the next object in the staff
        int currX = ((PointObject *) &s.pointObject[index[staffIndex]])->X();
        while (!(staffEnd[staffIndex] =
          index[staffIndex] == s.pointObject.number())) {
          PointObject &obj =
            *((PointObject *) &s.pointObject[index[staffIndex]]);
          if (obj.X() == currX) {
            if ((obj.location() & ~ONEPERSTAFF) == COMMONMULTIPLE) {
              // The object has a COMMONMULTIPLE location attribute:
              // mark the place and wait for other staves to reach
              // this object too
              atCommon[staffIndex] = !multipleReached;
              duration[staffIndex] = multipleReached ? 0 : MAXINT;
              if (!multipleReached)
                break;
            }

            // Reinitialize the next object duration
            if (duration[staffIndex] < obj.Duration())
              duration[staffIndex] = obj.Duration();

            // Call the object's Format virtual function,
            // in case the object wants to do something during formatting
            obj.Format(X);
            if (maxWidth < obj.Width())
              maxWidth = obj.Width();
            ++index[staffIndex];

            // Adjust the left and right coordinates
            // of any continuous objects that have been reached
            // while reformatting the point objects
            while (leftIndex < sortedByLeft.number() &&
              ((ContinuousObject *)
                &sortedByLeft[leftIndex])->Xleft() <= currX)
              ((ContinuousObject *)
                &sortedByLeft[leftIndex++])->FormatLeft(X);
            while (rightIndex < sortedByRight.number() &&
              ((ContinuousObject *)
                &sortedByRight[rightIndex])->Xright() <= currX)
              ((ContinuousObject *)
                &sortedByRight[rightIndex++])->FormatRight(X);
          }
          else break;
        }
      }

      // See if the end has been reached on all staves
      multipleEnd = multipleEnd && staffEnd[staffIndex];
    }

    // See if an object with a COMMONMULTIPLE location attribute
    // has been reached on all staves
    multipleReached = TRUE;
    for (staffIndex = 0; staffIndex < p.multiplicity(); ++staffIndex)
      multipleReached = multipleReached && atCommon[staffIndex];

    X += maxWidth;
  } while (!multipleEnd);

  // Free the continuous object list copies
  for (int i = sortedByLeft.number()-1; i >= 0; --i) {
    sortedByLeft.detachAt(i);
    sortedByRight.detachAt(i);
  }

  // Free all temporary lists on the heap
  free(staffEnd);
  free(atCommon);
  free(index);
  free(duration);
}

// **********************************************
// FormatEntirePart reformats the displayed part
// by calling FormatMultipleStaff once per every multiple staff
// in the part.

void FormatEntirePart()
{
  Part &p = *((Part *) &melody.part[displayedPart]);

  // Call FormatMultipleStaff for every multiple staff in the part
  for (int index = 0; index < p.staff.number(); index += p.multiplicity())
    FormatMultipleStaff(index);

  // Mark the melody as modified and refresh screen
  melodyModified = TRUE;
  InvalidateRect(hEditWnd, NULL, TRUE);
}