-- Author: John Maxwell
-- last modified: November 10, 1983 1:49 pm
-- Last Edited by: Maxwell, November 14, 1983 10:39 am

DIRECTORY
	Inline USING [LowHalf], 
	Event USING [Sync], 
	Heuristic USING [MakeChords], 
	MusicDefs, 
	Note USING [Duration, InVoice], 
	Score USING [GetTimeSignature], 
	Selection USING [AddLine, AddNote, Clear, MakeBeam, MakeChord, MakeSync, selection], 
	Voice USING [ClearState, Selected, SetState, State];
 
HeuristicImpl: PROGRAM
  IMPORTS Inline, Event, Heuristic, MusicDefs, Note, Score, Selection, Voice 
  EXPORTS Heuristic = 
BEGIN
OPEN MusicDefs;

-- ***************************************************************************
-- guessing structures 
-- ***************************************************************************

MakeSyncs: PUBLIC PROCEDURE[score: ScorePTR, begin, end: Time] = 
BEGIN
n: NotePTR;
current: Time _ 0;
Selection.Clear[];
FOR i: CARDINAL DECREASING IN [0..score.length) DO
	IF score[i].time < begin THEN EXIT;
	IF score[i].time > end  THEN LOOP;
	IF ABS[current-score[i].time] > 3 THEN
		BEGIN
		IF Selection.selection.length > 1 THEN Selection.MakeSync[];
		Selection.Clear[];
		current _ score[i].time;
		END;
	IF score[i].type # sync THEN LOOP;
	FOR j: CARDINAL IN [0..Event.Sync[score[i]].length) DO
		IF (n _ Event.Sync[score[i]].note[j]) = NIL THEN EXIT;
		IF ~Note.InVoice[n, score.sheet.voice] THEN LOOP;
		Selection.AddNote[score, n];
		ENDLOOP;
	ENDLOOP;
Selection.MakeSync[];
Selection.AddLine[score, begin, end];
END;

MakeChords: PUBLIC PROCEDURE[score: ScorePTR, begin, end: Time] = 
BEGIN
n: NotePTR;
count: CARDINAL;
FOR v: CARDINAL IN [0..score.maxVoice] DO
    IF ~Voice.Selected[score, v] THEN LOOP;
    FOR i: CARDINAL IN [0..score.length) DO
		IF score[i].time < begin THEN LOOP;
		IF score[i].time > end  THEN LOOP;
		IF score[i].type # sync THEN LOOP;
		Selection.Clear[];
		count _ 0;
		FOR j: CARDINAL IN [0..Event.Sync[score[i]].length) DO
			n _ Event.Sync[score[i]].note[j];
			IF n.beam # NIL THEN LOOP;
			IF n.voice # v THEN LOOP;
			Selection.AddNote[score, n];
			count _ count + 1;
			ENDLOOP;
		IF count > 1 THEN Selection.MakeChord[];
		ENDLOOP;
    ENDLOOP;
Selection.AddLine[score, begin, end];
END;

MakeBeams: PUBLIC PROCEDURE[score: ScorePTR, begin, end: Time] = 
BEGIN
n: NotePTR;
vs: Voice.State;
-- ts: TimeSignature;
change, found: BOOLEAN;
sum, sumTS, start, duration: Time _ 0;
count: INTEGER _ 0;
Beam: PROCEDURE = BEGIN IF Selection.selection[1] # NIL THEN Selection.MakeBeam[]; 
	Selection.Clear[]; count _ 0; duration _ 0; start _ sum; change _ FALSE; END;
SetDirty[score, begin, end];
FOR v: CARDINAL IN [0..score.maxVoice] DO
    Voice.ClearState[@vs];
    sum _ 0; change _ FALSE;
    Selection.Clear[];
    IF ~Voice.Selected[score, v] THEN LOOP;
    FOR i: CARDINAL IN [0..score.length) DO
		IF score[i].time < begin THEN LOOP;
		IF score[i].time > end  THEN LOOP;
		IF score[i].type = measure THEN -- IN [measure..repeat2] 
		   BEGIN Voice.ClearState[@vs]; sum _ 0; Beam[]; LOOP; END;
		IF score[i].type # sync THEN LOOP;
		-- determine the sync's logical position
		sum _ Voice.SetState[@vs, score[i]];
		IF NOT vs[v].found THEN LOOP;
		-- decide whether or not to break the current beam
		IF vs[v].duration >= 4096 THEN Beam[];
		FOR j: CARDINAL IN [0..Event.Sync[score[i]].length) DO
			IF (n _ Event.Sync[score[i]].note[j]) = NIL THEN EXIT;
			IF n.voice # v THEN LOOP;
			IF n.beam # NIL THEN Beam[];
			IF n.rest THEN Beam[];
			IF n.value = unknown THEN Beam[];
			ENDLOOP;
		IF change THEN SELECT sum FROM
			4096 => Beam[];
			8192 => Beam[];
			12288 => Beam[];
			16384 => Beam[];
			ENDCASE;
		IF duration # 0 AND vs[v].duration # duration THEN change _ TRUE;
		duration _ vs[v].duration;
		IF count > 3 THEN Beam[];
		IF sum = 4096 AND duration < 2000 THEN Beam[];
		IF sum = 8192 AND duration < 4000 THEN Beam[];
		IF sum = 12288 AND duration < 2000 THEN Beam[];
		IF sum = 16384 AND duration < 4000 THEN Beam[];
		-- select appropriate notes for beaming
		found _ FALSE;
		FOR j: CARDINAL IN [0..Event.Sync[score[i]].length) DO
			IF (n _ Event.Sync[score[i]].note[j]) = NIL THEN EXIT;
			IF n.voice # v THEN LOOP;
			IF n.beam # NIL THEN LOOP;
			IF n.rest THEN LOOP;
			IF n.value = unknown THEN LOOP;
			Selection.AddNote[score, n]; found _ TRUE;
			ENDLOOP;
		IF found THEN count _ count+1;
		ENDLOOP;
	ENDLOOP;
END;

MakeNTuplets: PUBLIC PROCEDURE[score: ScorePTR, nt, a: INTEGER, begin, end: Time] = 
BEGIN
n: NotePTR;
b: BeamPTR;
count: INTEGER _ 0;
found, beamed: BOOLEAN;
value: NoteValue _ unknown;
Beam: PROCEDURE = {
	IF Selection.selection[1] # NIL AND count = nt THEN Selection.MakeBeam[FALSE];
	IF Selection.selection[0] # NIL THEN b _ Selection.selection[0].beam ELSE b _ NIL;
	IF b # NIL THEN BEGIN b.against _ a; b.ntuple _ nt; END;
	IF b # NIL THEN b.beamed _ beamed;  beamed _ TRUE;
	Selection.Clear[]; count _ 0; value _ unknown};
beamed _ TRUE;
SetDirty[score, begin, end];
FOR v: CARDINAL IN [0..score.maxVoice] DO
    IF ~Voice.Selected[score, v] THEN LOOP;
    Selection.Clear[];
    FOR i: CARDINAL IN [0..score.length) DO
		IF score[i].time < begin THEN LOOP;
		IF score[i].time > end  THEN LOOP;
		IF score[i].type = measure THEN BEGIN Beam[]; LOOP; END; -- IN [measure..repeat2]
		IF score[i].type # sync THEN LOOP;
		-- decide whether or not to break the current beam
		FOR j: CARDINAL IN [0..Event.Sync[score[i]].length) DO
			IF (n _ Event.Sync[score[i]].note[j]) = NIL THEN EXIT;
			IF n.voice # v THEN LOOP;
			IF n.beam # NIL THEN Beam[];
			IF n.value = unknown THEN Beam[];
			IF value = unknown THEN value _ n.value;
			IF value # n.value THEN Beam[];
			value _ n.value;
			ENDLOOP;
		IF count = nt THEN Beam[];
		-- select appropriate notes for beaming
		found _ FALSE;
		FOR j: CARDINAL IN [0..Event.Sync[score[i]].length) DO
			IF (n _ Event.Sync[score[i]].note[j]) = NIL THEN EXIT;
			IF n.voice # v THEN LOOP;
			IF n.beam # NIL THEN LOOP;
			IF n.rest THEN beamed _ FALSE;
			IF n.value < eighth THEN beamed _ FALSE;
			IF n.value = unknown THEN LOOP;
			Selection.AddNote[score, n];  found _ TRUE;
			ENDLOOP;
		IF found THEN count _ count+1;
		ENDLOOP;
	ENDLOOP;
Beam[];
END;

-- ****************************************************************************
-- guessing note values
-- ****************************************************************************
    
SetNoteValues: PUBLIC PROCEDURE[score: ScorePTR, begin, end: Time] = 
BEGIN
sumTS: INTEGER;
ts: TimeSignature _ [4, 4];
start, stop: CARDINAL _ 0;
Heuristic.MakeChords[score, begin, end];
FOR i: CARDINAL DECREASING IN [0..score.length) DO
	IF score[i].time < begin THEN EXIT;
	IF score[i].time > end THEN LOOP;
	IF NOT Measure[score[i]] THEN LOOP;
	stop _ start;
	start _ i;
	IF start >= end THEN LOOP;
	ts _ Score.GetTimeSignature[score, score[stop].time];
	sumTS _ (ts.top*256)*(64/ts.bottom);
	GuessMeasure[score, start, stop, sumTS];
	ENDLOOP;
SetDirty[score, begin, end];
END;


GuessMeasure: PROCEDURE[score: ScorePTR, begin, end: CARDINAL, time: INTEGER] = 
BEGIN
n: NotePTR;
sync: SyncPTR;
	firstTime, priorTime, totalTime: Time;
delta, bestComplexity, current: INTEGER;
firstValue, nextValue, priorValue: INTEGER;
maxValue, bestValue, totalValue: INTEGER;
IF begin = end OR time = 0 THEN RETURN; 
-- SUGGESTION: use a note in the prior measure as the beginning rather than the measure line
vs _ ALL[[0]]; 
firstValue _ Inline.LowHalf[time+256];
firstTime _ score[begin].time;
priorValue _ 0;
priorTime _ score[end].time+3;
-- events are processed in DESCENDING order, and score[i].value > score[i+1].value
FOR i: CARDINAL DECREASING IN (begin..end) DO {
	IF score[i].type # sync THEN LOOP;
	sync _ Event.Sync[score[i]];
	-- check for durations already given by the user
	FOR j: CARDINAL IN [0..sync.length) DO
		IF (n _ sync.note[j]) = NIL THEN EXIT;
		IF n.value = unknown THEN LOOP;
		delta _ Inline.LowHalf[Note.Duration[n, 128]];
		bestValue _ delta+vs[n.voice].value;
		GOTO done;
		ENDLOOP;
	totalTime _ priorTime-firstTime;
	totalValue _ firstValue-priorValue; 
		-- obtain the next note sync's value
	nextValue _ firstValue;
	FOR j: CARDINAL DECREASING IN [begin..i) DO 
		IF score[j].type # sync THEN LOOP;
		delta _ Inline.LowHalf[(totalValue*(priorTime-score[j].time))/totalTime];
		nextValue _ priorValue + Quantize[delta, 32];
		EXIT; ENDLOOP;
	-- find the tic within a certain range that has the smallest complexity
	delta _ Inline.LowHalf[(totalValue*(priorTime-score[i].time))/totalTime];
	bestValue _ priorValue+Quantize[delta, 64];
	maxValue _ 32000;
	FOR j: CARDINAL IN [0..score.maxVoice] DO
		maxValue _ MIN[maxValue, (bestValue-vs[j].value)/4];
		ENDLOOP;
	bestComplexity _ Complexity[score, sync, bestValue, @vs];
	current _ bestValue-Quantize[maxValue, 64];
	maxValue _ bestValue+Quantize[maxValue, 64]+256;
	delta _ bestValue;
	WHILE TRUE DO
		current _ current+256;
		IF current <= priorValue THEN LOOP;
		IF current >= maxValue THEN EXIT;
		IF current >= nextValue THEN EXIT;
		IF Complexity[score, sync, current, @vs] > bestComplexity THEN LOOP;
		IF Complexity[score, sync, current, @vs] = bestComplexity AND 
		   ABS[bestValue-delta] <= ABS[current-delta] THEN LOOP;
		bestComplexity _ Complexity[score, sync, current, @vs];
		bestValue _ current;
		ENDLOOP;
	GOTO done;
	EXITS done => {
	-- event done, assign durations
	FOR j: CARDINAL IN [0..sync.length) DO
		IF (n _ sync.note[j]) = NIL THEN EXIT;
		IF n.value # unknown THEN LOOP;
		IF ~Note.InVoice[n, score.sheet.voice] THEN LOOP;
		maxValue _ 64*256;
		delta _ bestValue-vs[n.voice].value;
		FOR nv: NoteValue IN [whole..unknown) DO
			IF delta < maxValue THEN {maxValue _ maxValue/2; LOOP};
			IF delta >= 3*(maxValue/2) THEN n.dotted _ TRUE;
			n.value _ nv; EXIT;
			ENDLOOP;
		IF n.value = unknown THEN n.value _ thirtysecond;
		ENDLOOP;
	SetVoiceSyncs[sync, bestValue, @vs];
	priorTime _ score[i].time;
	priorValue _ bestValue}};
	ENDLOOP;
END;

VoiceSyncs: TYPE = ARRAY [0..10) OF RECORD[value: INTEGER];
vs: VoiceSyncs;


SetVoiceSyncs: PROCEDURE[s: SyncPTR, value: INTEGER, vs: POINTER TO VoiceSyncs] = 
INLINE BEGIN
FOR i: CARDINAL IN [0..s.length) DO 
	IF s.note[i] = NIL THEN EXIT;
	vs[s.note[i].voice].value _ value; 
	ENDLOOP; 
END;

Quantize: PROCEDURE[d: Time, q: INTEGER] RETURNS[INTEGER] = 
BEGIN
delta: Time _ (256*(64/q));
RETURN[Inline.LowHalf[delta*((d+delta/2)/delta)]];
END;

Complexity: PROCEDURE[score: ScorePTR, s: SyncPTR, value: INTEGER, vs: POINTER TO VoiceSyncs] RETURNS[INTEGER] = 
BEGIN
x, d: Time _ 128;
c, y: INTEGER _ 0;
start: CARDINAL;
v: ARRAY [0..10) OF BOOLEAN _ ALL[FALSE];
FOR j: CARDINAL IN [0..s.length) DO
	IF s.note[j] = NIL THEN EXIT;
	IF s.note[j].value # unknown THEN LOOP;
	IF ~Note.InVoice[s.note[j], score.sheet.voice] THEN LOOP;
	IF v[s.note[j].voice] THEN LOOP;
	d _ value-vs[s.note[j].voice].value;
	v[s.note[j].voice] _ TRUE;
	x _ x*256; start _ 10;
	FOR k: CARDINAL IN [0..7] DO
		x _ x/2; IF x > d THEN LOOP;
		d _ d-x; IF start > 7 THEN start _ k;
		IF d # 0 THEN LOOP;
		c _ c+(k-start); EXIT;
		ENDLOOP;
	ENDLOOP;
FOR j: CARDINAL IN [0..10) DO IF v[j] THEN y _ y+1; ENDLOOP;
RETURN[(c*10)/y];
END;

END...

			
GuessLogical: PROCEDURE[begin, end: CARDINAL, time: Time] = 
BEGIN
i, j: CARDINAL;
voice: ARRAY [0..10) OF CARDINAL _ ALL[0];
vs: Voice.State;
max: Time;
Voice.ClearState[@vs];
FOR i: CARDINAL IN [begin..end] DO 
	max _ Voice.SetState[@vs, score[i]];
	FOR j: CARDINAL IN [0..score.maxVoice] DO
		IF NOT vs[j].found THEN LOOP;
		voice[j] _ i;
		ENDLOOP;
	ENDLOOP;
END;

    FOR v: CARDINAL IN [0..score.maxVoice] DO
	duration _ (time*(vs[v]-score[i].time))/measure;
	SELECT TRUE FROM
	   duration IN [15000..19000] => value _ whole;
	   duration IN [7500..9000] => value _ half;
	   duration IN [3500..4500] => value _ quarter;
	   duration IN [1600..2400] => value _ eighth;
	   duration IN [900..1200] => value _ sixteenth;
	   duration IN [200..600] => value _ thirtysecond;
	   ENDCASE => value _ unknown;
	FOR j: CARDINAL IN [0..sync.length) DO
	    IF (n _ sync.note[j]) = NIL THEN EXIT;
	    IF n.voice # v THEN LOOP;
	    vs[v] _ score[i].time;
	    IF n.value # unknown THEN LOOP;
	    n.value _ value;
	    ENDLOOP;
	ENDLOOP;
    ENDLOOP;
END;


PortionOutTime: PROCEDURE[voice, s1, s2: CARDINAL, duration, ratio: INTEGER] = 
BEGIN
-- duration is the logical duration of the interval (64*256 = whole)
-- ratio is the number of tics that a quarter note occupies
beats, units, d: INTEGER;
i, j, r1, r2, count: CARDINAL _ 0; index _ 1;
FOR i: CARDINAL IN (s1..s2) DO
	IF NOT Sync.InVoice[score[i], voice] THEN LOOP;
	list[index] _ [score[i], FALSE]; index _ index + 1;
	IF score[i].value = 0 THEN LOOP;
	PortionOutTime[voice, s1, i, score[i].value-score[s1].value, ratio];  
	PortionOutTime[voice, i, s2, score[s2].value-score[i].value, ratio];
	RETURN;
	ENDLOOP;
IF index = 1 THEN RETURN;
list[0] _ [score[s1], FALSE];
list[index] _ [score[s2], FALSE]; 
index _ index+1;
[beats, units] _ Tranlate[duration];  -- 3/4, 6/8, 3/16, 15/24, etc.
-- look for runs of equally spaced notes 
-- then try successively finer grids
-- all durations must be strictly ordered
d _ list[1].value-list[0].value;
FOR i: CARDINAL IN [0..index) DO list[i].ts.top _ 0; ENDLOOP;
FOR i: CARDINAL IN [2..index) DO
	IF ABS[d-list[i].value-list[i-1].value] < d/5 THEN BEGIN r2 _ i-1; LOOP; END;
	IF r2-r1 > 1 THEN FOR j: CARDINAL IN (r1..r2] DO list[j].ts.top _ 1;
	d _ list[i].value-list[i-1].value; r1 _ i-1;
	ENDLOOP;
FOR i: CARDINAL IN [0..index) DO IF NOT list[i].tuple THEN count _ count+1; ENDLOOP;
WHILE units <= 128 DO
	IF count > beats THEN {units _ units*2; beats _ beats*2; LOOP};
	IF units = 128 THEN RETURN;
	d _ CheckGrid[s1, s2, beats, units, voice];
	IF d < duration/5 THEN EXIT;
	units _ units*2;
	beats _ beats*2;
	ENDLOOP;
AssignGrid[s1, s2, beats, units, voice];
r1 _ 0;
FOR i: CARDINAL IN [0..index) DO
	IF list[i].ts.top = 1 THEN LOOP;
	IF i-r1 < 2 THEN BEGIN r1 _ i; LOOP; END;
	d _ (list[i].value-list[r1].value)/(i-r1-1);
	FOR j: CARDINAL IN (r1..i) DO list[j].value _ list[r1].value+(j-r1)*d; ENDLOOP;
	r1 _ i; ENDLOOP;
END;

CheckGrid[s1, s2: CARDINAL, unit, voice: INTEGER] RETURNS[INTEGER] = 
BEGIN
i: CARDINAL;
d: Time _ 256*(64/unit);
sum: Time _ score[s1].value;
delta: Time _ 0; 
FOR i: CARDINAL IN (s1..s2) DO
	WHILE score[i].value > sum DO sum _ sum+d; ENDLOOP;
	IF NOT Sync.InVoice[score[i], voice] THEN LOOP;
	WHILE score[i].time*ratio-delta/2 > sum DO sum _ sum+d; ENDLOOP;
	delta _ delta+ABS[score[i].time*ratio-sum];
	sum _ sum+d;
	ENDLOOP;
RETURN[Inline.LowHalf[delta]];
END;
	 
AssignGrid[s1, s2: CARDINAL, unit, voice: INTEGER] = 
BEGIN
i: CARDINAL;
d: Time _ 256*(64/unit);
sum: Time _ score[s1].value;
FOR i: CARDINAL IN (s1..s2) DO
	WHILE score[i].value > sum DO sum _ sum+d; ENDLOOP;
	IF NOT Sync.InVoice[score[i], voice] THEN LOOP;
	WHILE score[i].time*ratio-delta/2 > sum DO sum _ sum+d; ENDLOOP;
	score[i].value _ Inline.LowHalf[sum];
	sum _ sum+d;
	ENDLOOP;
END;

Translate: PROCEDURE[duration: INTEGER] RETURNS[INTEGER] = 
BEGIN
units: INTEGER _ 64;
duration _ duration/256;
WHILE (duration MOD 2) = 0 DO 
	duration _ duration/2;
	units _ units/2;
	IF units = 1 THEN EXIT;
	ENDLOOP;
RETURN[duration, units];
END;

index: CARDINAL;
list: ARRAY [0..30) OF RECORD[sync: SyncPTR, tuple: BOOLEAN];
ss: ARRAY [0..10) OF Time;
(0, 4032)(1, 5056)(2, 6080)\542i20I79b10B590b11B545b9B697i37I72i47I680i36I323b12B761i47I318i36I468i20I85b13B785i30I5i55I137i78I76i45I219i1I70i1I4i33I103i2I145i70I121i2I17i2I707i30I2760i123I22i1I254i1I227i146I82i1I

END.
e6(0, 3648)(1, 65535)(2, 65535)