package eu.bandm.music.haken ; 

import java.util.Collection;
import static java.util.Arrays.asList;
import java.util.List;
import java.util.ArrayList;
import java.util.AbstractList;
import java.util.ListIterator;
import java.util.Map;
import java.util.HashMap;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Set;
import java.util.HashSet;

import java.io.PrintStream ; 

import eu.bandm.tools.annotations.Opt ; 

import eu.bandm.tools.util.Rational ; 

import eu.bandm.tools.message.XMLDocumentIdentifier;
import eu.bandm.tools.message.MessageReceiver ; 
import eu.bandm.tools.message.MessageTee ; 
import eu.bandm.tools.message.MessageCounter ; 
import eu.bandm.tools.message.SimpleMessage;
import eu.bandm.tools.message.SimpleMessage.Sender;

import static eu.bandm.tools.ops.Collections.the  ; 
import eu.bandm.tools.ops.Functions ; 
import eu.bandm.tools.ops.Comparators ; 

import eu.bandm.tscore.model.TimeScape ; 
import eu.bandm.tscore.model.Tp ; 
import eu.bandm.tscore.model.TpTop ; 
import eu.bandm.tscore.model.TDivision ; 
import eu.bandm.tscore.model.Part; 
import eu.bandm.tscore.model.Vox ; 
import eu.bandm.tscore.model.Event ; 

import eu.bandm.tscore.base.Modifiers ; 
import eu.bandm.tscore.base.Util ; 
/*DISLOC*/ import static eu.bandm.tscore.base.Util.Pairwise ; 
import static eu.bandm.tscore.base.Util.range_respectingDomainOrder ; 
import eu.bandm.tscore.base.Translet.Parser ; 

import static eu.bandm.tscore.base.Translet.PRIOR1 ; 
// ??  FIXME   PRIOR1  geht nicht ??
import static eu.bandm.tscore.base.Translet.PRIORn ; 

import static eu.bandm.tscore.base.Translet.STORE ; 
import static eu.bandm.tscore.base.Translet.SEQU ; 
import static eu.bandm.tscore.base.Translet.CONST ; 
import static eu.bandm.tscore.base.Translet.OPT ; 
import static eu.bandm.tscore.base.TransletLib.parseAndPack_integer_nonNeg ; 


/** This class represents the use of tscore models for ml's "hook project" 
 *  ("HKN-Projekt").
 *  <br/>
 *  <b>Usage:</b><br/>
 *  The different classes for different back-ends are derived from this class.
 *  An instance is created with an already raw-parsed {@link TimeScape}, and 
 *  (optionally) a {@link Parameters} collection.
 *  Then {@link #update()} is called, which parses all contained voices.
 *  (TpTops are integer with arbitrary subdivisions, and stand for "K-measure-numbers",
 *  with no relation to front-end timing, but possibly printed in the F-score as comments.)
 *  <p>
 *  Example of a K-Score
 *  <pre>
 *   T         1      !         !                   2
 *   VOX v0    p2               p1        p2
 *   VOX v1    M      O         MU        OMO    
 *   VOX v2    MO 'OM U         MUUM                   
 *  </pre>
 *  Voice "v0" is a voice containing only "additional pauses" to 
 *  support the reception of the intended groupings. (This will be done additionally
 *  to and outside of the Haken expansion process.)
 *  <br>
 *  Voices "v1" and "v2" are a "Haken-Voices" = "K-Voices". They contain 
 *  arbitrary sequences of {@link RelWert}, {@link Haken} and {@link DoppelHaken}.
 *  (= relative values, hooks and double hooks).
 *  They will be selected to control particular parameters when translating to an 
 *  executable V-score.
 *  <p>
 *  First step is to create an {@link Expansion} of a selection of voices.
 *  This is a transformed score where the voices contain RelWert only, at each K-Timepoint 
 *  in the union of the selected voices.
 *  For example, the score above can be expanded to
 *  <pre>
 *   T         1            !         !                  2
 *   VOX v0    p2                     p1     p2
 *   VOX v1    M            O         M O U  O U M U O  
 *   VOX v2    M U O O U M  U         M O O  U U O O M 
 *  </pre>
 *  The rules for this expansion can become complicated and can be further modified
 *  by translation parameters and operators in the source text.
 *  (E.g. the apostrophe in v2 above means: "do not overlap";
 *  contrarily a tilde means "force overlap".)
 *  For the details see 
 *  <a href="http://senzatempo.de/haken/haken01.html">the project documentation (in German).</a>
 *  <p>
 *  All further processing is specific to the interpretation of the K-score,
 *  as realized by the subclasses of this class.
 *  It operates only on {@link Expansion#tps} and {@link Expansion#expanded}, which
 *  run in parallel (plus possibly a dedicated "Pause" voice, which assigns articulation
 *  pauses to a subset of the time points).
 *  <p>
 *  Additionally a voice may contain "pause" events, and the specialized process
 *  may select a particular voice to translate the contained pause events to some
 *  foreground temporal articulation/gap. 
 *  (Pauses are meant to occur BEFORE the sound event at the same K-Timepoint.)
 *  <br/>
 *  FIXME ATTENTION do not mix pause events with haken events !? is currently not checked
 *  by the parser ?!?!?!
 *  <br/>
 */
public class Score_hkn  {

  /** Control parameters for the raw tscore parsing process.*/
  protected static Modifiers modifiers = new Modifiers();

  /** FIXME DOC */
  protected final String name ; 

  /** String value to be used instead of a voice name, iff no voice is selected
   *  for a particular role.
   */
  public static final String noVoiceSelected = "-" ;   

  /** An <em>infinite</em> list delivering {@link RelWert.M} at every position.*/
  public static final List<RelWert> allMedium 
    = new AbstractList<RelWert>(){
    @Override public RelWert get(final int i){
      return RelWert.M;
    }
    @Override public int size(){
      throw new UnsupportedOperationException(); 
    }
  };


  // ---------------------------------------------------------------------

  /** Parameters to control the expansion process.*/
  public static class Parameters {
    /** Whether to emit a warning when the expansion process must create uneven
     *  distributions of RelWert for a Haken or a DoppelHaken.
     *  Default value is true.
     */
    public boolean warnUnevenHakenDistribution = true ; 

    // overlapIsDefault = aggressive overlap
    // overlapDisable
    // strategy for additional Haken segments (middle? extremes?)
    // voicesPerParameter 
    // graphik: ja/nein
    // graphik: größen
    // language/locale
  }


  /** Constructor which will use the default controal {@link Parameters}.
   *  @param ts the already raw-parsed time scape. 
   *   (Normally the parse result of a tscore source file.)
   *  @param msg drain of all messages.
   */
  public Score_hkn (final String name, 
		    final Part tsPart,
		    final MessageReceiver<SimpleMessage<XMLDocumentIdentifier>> msg){
    this(name, tsPart, msg, new Parameters());
  }
  
  /** Constructor which will use an explicit parameter setting.
   *  @param ts the already raw-parsed time scape. 
   *   (Normally the result of parsing a tscore source file.)
   *  @param msg drain of all messages.
   *  @param parameters to control the parsing and expansion process.
   */
  public Score_hkn (final String name, 
		    final Part tsPart, 
		    final MessageReceiver<SimpleMessage<XMLDocumentIdentifier>> msg,
		    final @Opt Parameters parameters){
    this.name = name ; 
    this.tsPart = tsPart ; 
    this.msgr = msg ; 
    this.msg = new SimpleMessage.Sender<>(msgr);
    if (parameters==null)
      this.parameters = new Parameters();
    else
      this.parameters = parameters ; 
  }

  // ---------------------------------------------------------------------

  /** Target of all messages generated by this class.*/
  final MessageReceiver<SimpleMessage<XMLDocumentIdentifier>> msgr;
  /** Target of all messages generated by this class.*/
  final SimpleMessage.Sender<XMLDocumentIdentifier> msg;

  /** The tscore score PART to process. 
   *  Normally the result of parsing a tscore source file.
   */
  final Part tsPart  ; 

  // PRE 202220819
//   /** The time scape tscore score to process. 
//    *  Normally the result of parsing a tscore source file.
//    */
//   final TimeScape timescape  ; 

  /** The control parameters for the expansion process, etc.*/
  final Parameters parameters ; 


  /** Auxiliary functions for sub-classes=specialized formats, to find 
   *  a voice for a particular purpose by name.
   *  If not there, write error or warning to global messagereceiver.
   *  @param s1 name of the voice. If ==null or =={@link #noVoiceSelected}, then return null.
   *  @param errorsNotWarnings whether not finding a name (!=null and != noVoiceSelected)
   *    will raise an error, not only a warning.
   */
  protected @Opt Vox findVoice (final @Opt String s1,
				final boolean errorsNotWarnings
				/*glo in timescape, noVoiceSelected, msg*/){
    if (s1==null)
      return null ; 
    if (s1.equals(noVoiceSelected))
      return null ; 
    return Util.findVoice(tsPart, msgr, errorsNotWarnings, s1);
  }

  /** Value returned by {@link #getPauseIndexByIndex(List,Vox,int,int)} if no 
   *  valid entry is found.
   */
  public static final int noPauseSelected = -1 ; 
  
  /**  Valid pauses are numbered from 0 to maxPause, with increasing significance.
   *   @return  {@link #noPauseSelected} (==-1) for not defined pauses and issue
   *   error message for too large index.
   *   The parser syntax already enyures that pause nubmers are non-negative.
   */
  protected int getPauseIndexByIndex(final List<Tp> tps,
				     final @Opt Vox vpause,
				     final int i,
				     final int maxPause
				     /*glo in event2pause, out msg */){
    if (vpause==null)
      return noPauseSelected ; 
    final Tp tp = tps.get(i);
    final @Opt Event ev = vpause.get_sortedByStart().get(tp);
    if (ev==null) 
      return noPauseSelected ; 
    final @Opt Integer pauseGrade = event2pause.get(ev);
    if (pauseGrade==null)
      return noPauseSelected ; 
    assert pauseGrade>=0;
    if (pauseGrade>maxPause){
      msg.error(ev.get_location(), "invalid pause grade %d", pauseGrade);
      return noPauseSelected ;
    }
    return pauseGrade ; 
  }
  
  /** Map of numeric entries in tne tsore "T" line to their text, as usual in tscore raw parsing.*/
  final Map<TpTop, Integer> tp2barnum = new HashMap<>();

  /** Inverse of {@link #tp2barnum}, as usual in tscore raw parsing.*/
  final SortedMap<Integer, TpTop> barnum2tp 
    = new TreeMap<>(Comparators.<Integer>natural());


  /** Semantic attribute of events. */
  final Map<Event,Haken> event2haken =  new HashMap<>() ; 

  /** Semantic attribute of events. */
  final Map<Event,DoppelHaken> event2doppelHaken =  new HashMap<>() ; 

  /** Semantic attribute of events. */
  final Map<Event,RelWert> event2relwert =  new HashMap<>() ; 

  /** Get Relwert, Haken or DoppelHaken standing with the given event.*/
  protected RelWertFolge getRelWertFolge(final Event ev){
    RelWertFolge r = event2relwert.get(ev);
    if (r!=null) return r ; 
    r = event2haken.get(ev);
    if (r!=null) return r ; 
    r = event2doppelHaken.get(ev);
    return r ; 
  }

  /** Get the first RelWert of the entry with the given event.*/
  // FIXME kann der null sein ?? assert != null scheint besser !?!?
  protected @Opt RelWert getRelWertFolge_first (final Event ev){
    final @Opt RelWertFolge r = getRelWertFolge(ev);
    if (r!=null)
      return r.firstRelWert();
    return null ;
  }



  /** Semantic attribute of events. Pauses are contained in dedicated voices 
   *  and notated as "{@code p0}", "{@code p2}", "{@code p2}", etc., with a
   *  dynamic upper limit and increasing significance.
   */
  final Map<Event,Integer> event2pause =  new HashMap<>() ; 

  /** Semantic attribute of events. Means that the event source text starts with an apostrophe 
   *  "{@code &amp;}", what suppresses any overlap with its predecessor.
   */
  final Map<Event,String> event2noOverlap_start =  new HashMap<>() ; 
  /** Semantic attribute of events. Means that the event source text starts with a tilde 
   *  "{@code ~}", what enforces overlap with its predecessor.
   */
  final Map<Event,String> event2forceOverlap_start = new HashMap<>();
  /** Semantic attribute of events. Means that the event source text ends with an apostrophe 
   *  "{@code '}", what suppresses any overlap with its successor.
   */
  final Map<Event,String> event2noOverlap_end = new HashMap<>(); 
  /** Semantic attribute of events. Means that the event source text ends with a tilde 
   *  "{@code ~}", what enforces overlap with its successor.
   */
  final Map<Event,String> event2forceOverlap_end = new HashMap<>() ; 

  /** Holds all events which start with the same RelWert as their predecssor ends. */
  final Set<Event> eventCanOverlapAtStart = new HashSet<>();

  /** Parser for relwert/haken voices AND pause voices.
   *  Both shall not be mixed.
   */
  // FIXME separate parsers for voice types.
  final Parser<?> parser =
    PRIOR1(SEQU(OPT(PRIOR1(STORE(event2noOverlap_start, CONST("'")),
			   STORE(event2forceOverlap_start, CONST("~")))
		    ),
		// PRIOR1 geht nicht ??FIXME
                // FIXME allow symbolic names for Haken/Doppelhaken ???? switch on/off explictly
		PRIORn(STORE(event2doppelHaken, DoppelHaken.catalog.getParser("de")),
		       STORE(event2haken, Haken.catalog.getParser("de")),
		       STORE(event2relwert, RelWert.catalog.getParser("de"))
		       ),
		OPT(PRIOR1(STORE(event2noOverlap_end, CONST("'")),
			   STORE(event2forceOverlap_end, CONST("~")))
		    )
		),
	   SEQU(CONST("p"), STORE(event2pause, parseAndPack_integer_nonNeg)),
	   CONST("-")
	   );

  /** Translate untyped tscore data into semantically defined values.
   * <ol>
   * <li> Parse all voices into the maps {@link event2relwert}, 
   * {@link event2haken}, {@link event2doppelHaken},
   * and additionally "event2(no/force)overlap_(start/end)".
   * <li> Calculate time instances for ALL tps into two global caches
   *  (forward and backward, {@link tp2rat} and {@link rat2tp}.)
   *  TpTops are integer constants with arbitrary subdivisions, and stand for
   *  "abstract bar numbers", not for any concrete time domain or front-end measures.
   *   All Tps are linked to a Rational.
   */
  // ---------------------------------------------------------------------
  public void update (/*GLO timescape*/){
    // ---------------------------------------------------------------------

    // PRE 20220819
//     final int partcount = timescape.get_parts().size() ;
//     if (partcount!=1){
//       msg.error("currently only files containing exactly one(1) PART are supported");
//       return ; 
//     }
//     final Part firstPart = the(timescape.get_parts().values());

    Util.parseTpTops
      (msgr, 
       modifiers,
       tsPart, // firstPart,
       tp2barnum,
       barnum2tp,
       parseAndPack_integer_nonNeg,  // TpTops are labeled with non-neg integers.
       Util.<Integer>checkIncreasing(), 
       Util.<Integer>checkNotDecreasing()
      ) ;

    for (Vox v : tsPart/*timescape*/.get_voices().values())
      Util.parseParamTrack (msgr, v, Event.main_parameter_name, "", parser, modifiers);
    for (Vox v : tsPart/*timescape*/.get_voices().values())
      for (Event e : v.get_events())
	Util.getRationalValue_lenient
	  (Functions.compose(Functions.get(tp2barnum), 
			     (Integer i) -> Rational.valueOf(i)
	  ),
	   tp2rat, 
	   e.get_when(),
	   rat2tp); 
    for (Vox v : tsPart/*timescape*/.get_voices().values())
      Util.unifyEventTimesByScalarValue(rat2tp,
					Functions.get(tp2rat),
					v);
  }//update

  // ---------------------------------------------------------------------

  /** Maps all time points to rationals, als usual in tscore raw parsing.
   *  (The rational time values of these K-Voices have no significance beyond
   *  their sequential order.)
   */
  final Map<Tp, Rational> tp2rat = new HashMap<Tp, Rational>() ; 
  /** Inverse of {@link #tp2rat}, as usualin tscore raw parsing.*/
  final SortedMap<Rational, Tp> rat2tp = new TreeMap<Rational, Tp>() ; 


  // ---------------------------------------------------------------------

  /** An expansion is a collection of voices which contain only RelWert instead
   *  of Haken and DoppelHaken. It is characterized by a selection of voices,
   *  because the disjunction/union  of all Tps in these voices will be mapped to a
   *  {@link RelWert}.
   *  <p>
   *  ADDITIONAL Tps may be synthesized, if necessary. All Tps are found in {@link #tps}.
   *  The corresponding expanded data is {@link #expanded}.
   *  <p>
   *  For convenience of the calling code, which realizes
   *  the specific interpretation of a bundle of voices for different parameters,
   *  a voice reference==null may be included, which means that no voice has been assigned 
   *  to a particular parameter. This will be excluded before any procesing.
   *  <p>
   *  <b>Usage:</b> Create an instance (giving all voices to take part)
   *  and call {@link #expand()}.
   *  The subsequent application-specific evaluations work exclusively on 
   *  {@link #tps} and {@link #expanded}, which run in parallel.
   */
  public class Expansion { /*GLO IN rat2tp, tp2rat, msg, event2.., .. */

    /** All time points taking part in this Expansion.
     *  The list is a subset of all Tps occuring in the tscore, as given by {@link #tp2rat}.
     *  Synthesized new Tp-s are entered there and here. 
     */
    public final List<Tp> tps = new ArrayList<>();

    /** All voices taking part in this expansion, as given finally on constrcution.
     *  (No null is contained)
     */
    public final Set<Vox> voices ; 

    /** Main result of expansion: a list of expanded RelWert per Vox.
     *  Those lists run all in parallel (same index = same event) and in 
     *  parallel with {@link #tps}.
     */
    public final Map<Vox,List<RelWert>> expanded = new HashMap<>(); // FIXME pause !?!?

    /** Flag that the expanded values are valid.*/
    protected boolean isExpanded = false ; 

    /** Temporary set of Tps <em>before</em> which one additional tp must be synthesized
     *  for the expansion of a Haken.
     */
    Set<Tp> oneMore; 
    /** Temporary set of Tps <em>before</em> which two additional tp-s must be synthesized
     *  for the expansion of a Haken.
     */
    Set<Tp> twoMore ;
    /** Temporary set of Tps <em>before</em> which an additional tp must be synthesized,
     *  <em>or indeterminstically</em> before its successor.
     */
    Set<Tp> oneMoreOrNext ; 
    
    /** Gives the set of voices, the data and time points of which shall be considered.
     *  For convenience of the calle, the set may contain the value null which will be removed.
     */
    public Expansion (final Set<@Opt Vox> voices){
      this.voices=voices ;
      voices.remove(null);
    }
    /** Gives the set of voices, the data and time points of which shall be considered. 
     *  For convenience of the calle, the set may contain the value null which will be removed.
     */
    public Expansion (final @Opt Vox... voices){
      this(new HashSet<Vox>(asList(voices)));
    }

    /** Auxiliary print of all voices and their values, for debugging and demonstration.*/
    public void dump (final PrintStream os){
      os.print("      ");
      os.print("expansion of ");
      final int s = tps.size();
      for (final Vox v : voices)
	os.print (v.get_name()+"  ");
      os.println();
      for (int i=0; i<s; i++){
	os.print (String.format("%20s :", String.valueOf(tps.get(i))));
	for (final Vox v : voices)
	  os.print (expanded.get(v).get(i)+"  ");
	os.println();
      }
    }


    /** Instert <em>additional synthetic</em> time points as needed for the expansion
     *  of a Haken.
     *  The time points are inserted in the network of TDivision, (which is global to the
     *  underlying t-score) and in the local list {@link #tps}.
     *  <br/>
     *  Every new time point gets its rational value (in {@link #tp2rat}, which always
     *  matters only w.r.t. the sequential order.
     *  <p>
     *  ATTENTION: Tps created here are NOT related to Tps in other, parallel K-voices,
     *  even of the same configuration. (This will not do any harm as long as they
     *  will be evaluated K-voice by K-voice, when generating the V-voices.)
     *  @param it is an output parameter used for changing the list {@link #tps}.
     *  It is the {@link ListIterator} contolled by {@link Pairwise} and 
     *  currently (on entering this method) points to the successor of the later item "tp1".
     *  It is used for inserting in to the underlying list of time points by
     *  {@link ListIterator.add(Object)}, but reset to its entering value when returing.
     *  @param tp0 after which the synthetic tp-s shall be entered.
     *  @param tp1 on call time: the successor of tp0 = the node before which the
     *   synthetic tp-s shall be entered.
     *  @param cnt number by which the interval tp1-tp0 shall be divided, 
     *   i.e. one larger than the number of new synthetic nodes.
     */  
    protected void makeTps (final ListIterator<Tp> it,
			    final Tp tp0, final Tp tp1, final int cnt){
      assert cnt>1 ; 
      // Go back to point to tp1, for the calls to "ListIterator.add[before](Object)":
      it.previous();
      final TDivision div = tp0.makeDivision(tp1,cnt, true);
      for (int i = 0; i<cnt; i++){
	final Tp newtp = div.getTp(i);
	Util.getRationalValue (null, tp2rat, newtp, msgr, rat2tp); 
	if (i>0)
	  it.add(newtp);
      }
      // Reconstruct the state when entering the method = point behind tp1:
      it.next();
    }


    /**
     * Translates sybolic input voices (="K-Voices", containing RelWert, Haken and
     * Doppelhaken references as their events) to sequences of RelWert,
     * for a set of K-voices which together define one instrument.
     * (Pauses contained in a voice are ignored.)
     * <ol>
     * <li> First collect all tps appearing in any event in any voice.
     * <li> Then synthesize additional  time points for hook expansion, if necessary.
     *   The final sequence of Tps will be contained in {@link #tps}.
     * <li> Finally expand the haken and doppelhaken in the K-voices into sequences of RelWert,
     *   which will be contained in {@link #expanded}.
     * </ol>
     * This method may only be called once, which is controlled by the flag {@link #isExpanded}.
     * @throws IllegalStateException if called twice.
     */
    protected void expand(){
      if (isExpanded) 
	throw new IllegalStateException("Expansion is already expanded.");
      isExpanded = true ;
      final Set<Tp> tpTemp = new HashSet<>();
      // collect a set of time points which occur in any voice
      for (Vox v : voices){
	assert v!=null;
        collectTps(tpTemp, v);
      }
      // FIXME pointfree Iterator.filter !?!
      // make an ordered list of time points, based on that set.
      for (final Tp tp : range_respectingDomainOrder(rat2tp))
	if (tpTemp.contains(tp))
	  tps.add(tp);

      final Tp lastTp = tps.get(tps.size()-1);
      for (final Vox v : voices){
	if (!event2relwert.containsKey(v.get_sortedByStart().get(lastTp)))
	  msg.error(lastTp.get_location(), // FIXME better: location of LATEST event in voice !?
		    "all voices must end with a RelWert event on the very last time point.");
      }

      oneMore = new HashSet<>(); 
      twoMore = new HashSet<>(); 
      oneMoreOrNext = new HashSet<>();
    
      // copy all "noOverlap_end" to "noOverlap_start", after consistency check.
      // copy all "forceOverlap_start" to "forceOverlap_end", after consistency check.
      for (final Vox v : voices)
	new Pairwise<Event>(Util.voiceEvents(v, tps)){
	  @Override public void pairwise(final Event ev0, final Event ev1){ 
	    if (event2noOverlap_end.containsKey(ev0))
	      if (event2forceOverlap_start.containsKey(ev1))
		msg.error
                  (ev0.get_location(), 
                   "no overlap at end of event conflicts with force overlap at start of successor.");
	      else
		event2noOverlap_start.put(ev1, "INH");
	    final boolean forceOverlap_start = 	event2forceOverlap_start.containsKey(ev1) ; 
	    if (forceOverlap_start)
	      if (event2noOverlap_end.containsKey(ev0))
		msg.error
                  (ev0.get_location(), 
                   "no overlap at end of event conflicts force overlap at start of successor.");
	      else
		event2forceOverlap_end.put(ev0, "INH");
	    final RelWertFolge w0 = getRelWertFolge(ev0);
	    final RelWertFolge w1 = getRelWertFolge(ev1);
	    if (w0!=null && w1!=null){   // FIXME there may be "-" event ? 
	      if (w0.lastRelWert()==w1.firstRelWert())
		eventCanOverlapAtStart.add(ev1);
	      else if (forceOverlap_start || event2forceOverlap_end.containsKey(ev0)){
		event2forceOverlap_end.remove(ev1);
		msg.error(ev0.get_location(), "force overlap conflicts with value difference");
	      }
	    }
	  }}.process();

      for (final Vox v : voices)
	collectAdditionalTpRequirements(v);

      new Pairwise<Tp>(tps.listIterator()){
	/** Insert two or one before the later time point, if this is required by the collected
         *  sets, and remove this and its predecessor from "oneMoreOrNext". So the
         *  deterministic insertion requests remove the non-deterministic they cover.
         *  <p>
         *  ATTENTION: the called makeTps(...) assumes that listIterator 
         *  (controlled by {@link Pairwise}) points currently to the successor of tp1.
         */
	@Override public void pairwise(final Tp tp0, final Tp tp1){ 
	  if (twoMore.contains(tp1)){
	    makeTps (lit, tp0, tp1, 3);
	    oneMore.remove(tp1);
	    oneMoreOrNext.remove(tp1);
	    oneMoreOrNext.remove(tp0);
	  }
	  else if (oneMore.contains(tp1)){
	    makeTps (lit, tp0, tp1, 2);
	    oneMoreOrNext.remove(tp1);
	    oneMoreOrNext.remove(tp0);
	  }
	}
      }.process();

      new Pairwise<Tp>(tps.listIterator()){
	boolean lastSelected = false ; 
	/** Insert one tp AFTER all tps which are still in "oneMoreOrNext" and which
         *  do not get a tp BEFORE them, because their predecessors got one after.
         */
	@Override public void pairwise(final Tp tp0, final Tp tp1){
          // predecessor wants before or after; gets after:
	  if (lastSelected){
	    makeTps (lit, tp0, tp1, 2);
	    lastSelected=false; 
	  }
          // predecessor has NOT got one after, but tp1 wants one before or after; gets after:
	  else if (oneMoreOrNext.contains(tp1))
	    lastSelected=true;
	}
      }.process();

      // calculate the expanded sequence of RelWerts:
      for (Vox v : voices){
	final List<@Opt RelWert> result = new ArrayList<>(tps.size());
	expanded.put(v, result);
	expandHaken(v, result);
      }
    }//expand


    /** Collect all Tps of all events of the given voice into one set.*/
    protected void collectTps (final /*OUT*/Set<Tp> res,
			       final Vox v){
      // use JAVA8 Streams !?!
      for (final Event e:v.get_events())
	res.add(e.get_when());
    }
    
    /** Collect all requirements of additional Tps into global output registers.
     *  (The actual generation of these time points is done after all voices have benn
     *  asked.)
     *  The necessity is calculated by the distance to the preceding Haken, measures in 
     *  (currently exisitng) time points.
     *  Examples of K-tps and K-events for the necessity to synthesize time points:
     *  <pre>
     *       0    1    2    3
     *       M    M    M    M
     *       OM             O   => dist>=3 => nothing required.
     *       OM        M        => dist=2 and overlap =>  nothing required.
     *       OM        O        => dist=2 and no overlap => require 1 additional before pos 1 
     *                                          OR or 1 additional before pos 2, NOT DETERMIN!
     *       OM   M             => dist=1 and overlap =>  require 1 additional before pos 1
     *       OM   O             => dist=1 and no overlap =>  require 2 additional before pos 1 
     *       OM   'MU           => dto., overlap explicitly forbidden.
     *  </pre>
     *  Has only any effect if distance from a Haken to its successor K-event is <=2.
     *  In this case "overlapping" is considered true, if the values permit 
     *  and not forbidden by {@link #event2noOverlap_start}.
     *  <p>
     *  <b>Attention:</b> Currently only Haken, <em>not</em> 
     *  {@link DoppelHaken} do cause additional Timepoints 
     *  to be synthesized. (The degree of freedom with overlapping DoppelHaken can become 
     *  so large that humans cannot control the consequences anymore!-)
     */
    protected void collectAdditionalTpRequirements 
      (final Vox v  
       /*GLO IN tps, event2haken, event2relwert
         event2noOverlap_start, eventCanOverlapAtStart, 
         GLO OUT oneMore, twoMore, oneMoreOrNext*/){
      int lastHakenDist = 1000 ; 
      Haken lastHaken = null ; 
      Tp lasttp = null ; 
      for (final Tp tp : tps){
	lastHakenDist++;
	final Event ev = v.get_sortedByStart().get(tp);
	if (ev==null){
	  lasttp=tp;
	  continue ;  // lastHakenDist has been incremented!
	}
	if (lastHakenDist<=2){ 
          assert lastHaken!=null;
          assert lasttp!=null;
	  final boolean overlap 
	    = (!event2noOverlap_start.containsKey(ev)) && eventCanOverlapAtStart.contains(ev) ; 
	  if (lastHakenDist==2){
	    if (!overlap)
	      oneMoreOrNext.add(lasttp);
	  }
	  else // lastHakenDist==1
	    (overlap?oneMore:twoMore).add(tp);
	}
	final @Opt Haken haken = event2haken.get(ev);
	lastHaken = haken ; 
	lastHakenDist = (haken!=null) ? 0 : 1000 ; 
	lasttp = tp ; 
      }//for
    }
    
    /** Returns a list of {@link RelWert} values by copying these from the K-voice
     *  input and translating all {@link Haken} and {@link DoppelHaken} into these.
     *  Input is a list of {@link Tp} (time points) which are all time points which have
     *  to be filled, i.e. after additionally  required Tps have been synthesized.
     *  The expansion process will generate overlaps iff it is necessary by missing space 
     *  or explicitly requested by {@link event2forceOverlap_end}.
     *  @param v the voice to expand. For convenience of the calling code, which realizes
     *    the specific interpretation of a bundle of voices for different parameters,
     *    a value v==null means that no voice has been assigned to a particular parameter
     *    and a sequence of {@link RelWert#M} of the approriate length is returned.
     */
    protected void expandHaken (/*glo in tps*/
                                final Vox v,
                                final /*out*/ List<RelWert> result){
      RelWert run_wert  = RelWert.M ;
      // Delay the expansion of a haken until the next event with some data is found:
      @Opt Event pending_haken_event = null ; 
      @Opt RelWertFolge pending_haken_cmd = null ; 
      // Numer of time points since the pending haken event:
      int haken_length = 0 ; 

      for (final Tp tp : tps){
	final @Opt Event e = v.get_sortedByStart().get(tp);
	final @Opt RelWert w = (e==null) ? null : event2relwert.get(e);
	final @Opt Haken h =  (e==null) ? null : event2haken.get(e);
	final @Opt DoppelHaken d =  (e==null) ? null : event2doppelHaken.get(e);
	if (pending_haken_event!=null && (w!=null || h!=null || d!=null)){
	  final boolean forceOverlap = event2forceOverlap_end.containsKey(pending_haken_event);
	  if (pending_haken_cmd instanceof DoppelHaken) 
	    flushPendingDoppelHaken(result, haken_length, pending_haken_event, 
				    forceOverlap, eventCanOverlapAtStart.contains(e));
	  else
	    flushPendingHaken(result, haken_length, pending_haken_event, forceOverlap);
	  pending_haken_event = null;
	}
	if (w!=null)
	  run_wert = w ; 
	if (h!=null || d!=null){
	  pending_haken_event = e ; 
	  pending_haken_cmd = (h==null) ? d : h ; 
	  haken_length = 0 ; 
	}
	if (pending_haken_event==null)
	  result.add(run_wert);
	else
	  haken_length++ ; 
      }//for
      if (pending_haken_event!=null)
	if (pending_haken_cmd instanceof Haken)
	  flushPendingHaken(result, haken_length, pending_haken_event, false);
	else
	  flushPendingDoppelHaken(result, haken_length, pending_haken_event, false, false);
    }	

    /** Expand the last recognized {@link Haken} to a sequence of single "O/M/U" 
     *  {@link RelWert} events, 
     *  Fills the time from its start up to "currentPos", because the
     *  next haken/event (or the end of input) is reached in the K-voice (=symbolic input voice).
     *  An overlap is only done when forced by explicit K-Input (reflected in parameter
     *  "forceOverlap") or if space is <3.
     *  @param result the list of RelWert, grown exaxtly to the start point of the Haken to expand.
     *  @param length the number of tp to realize this Haken
     *  @param haken the event which carries this haken info (for getting location and form
     *    of Haken)
     *  @param forceOverlap if overlap requested explicitly by the tscore input.
     */
    protected void flushPendingHaken (final List<RelWert> result,
				      final int length, 
				      final @Opt Event haken,
				      final boolean forceOverlap
				      /*mayoverlap has been checked by tp-synthesis*/ ){
      if (haken==null) // FIXME kann raus !?!  
	return ; 

      final int startMiddle, startLast ; 
      if (forceOverlap){
	startMiddle = length / 2 ; 
	startLast = length ; // = the last segment will not be added by this call.
      }
      else {
	final int min = length / 3 ; 
        final int rest = length % 3 ; 
	
	if ((rest !=0) && length!=2) // = "2" means an overlap, by intention.
	  if (parameters.warnUnevenHakenDistribution)
	    msg.warning(haken.get_location(), 
			"Haken expansion not a multiple of three(3): "+length);
	startMiddle  = min + (rest>1 ? 1 : 0) ;   // first part gets second superfluous
	startLast  = startMiddle + min + (rest>0 ? 1 : 0) ; //middle gets first superfluous
      }
      final Haken h = event2haken.get(haken);
      int i = 0 ; 
      RelWert r = h.getFirst();
      while (i++<startMiddle)  
	result.add(r);
      i--;
      r = h.getMiddle();
      while (i++<startLast)
	result.add(r);
      i--; 
      r = h.getLast();
      while (i++<length)
	result.add(r);
    }//flushPendingHaken


    /** Expand the last recognized {@link DoppelHaken} to a sequence of single "O/M/U" 
     *  {@link RelWert} events, 
     *  Fills the time from its start up to "currentPos", because the
     *  next haken/event (or the end of input) is reached in the K-voice (=symbolic input voice).
     *  <pre>
     *                 0  1  2  3  4  5  6
     *                 MUM         M          overlap
     *                 M  O  U  O  M
     *                 MUM            'M      no overlap
     *                 M  O  U  O  M  M
     *                 MUUM           M       overlap
     *                 M  O  U  U  O  M  
     *                 MUUM              'M   no overlap
     *                 M  O  U  U  O  M  M
     *  </pre>
     *  No additional space has been synthesized (as for Haken), but parallel K-voices must 
     *  provide the required space.
     *  An overlap is forced by explicit notation in the K-voice input 
     *  or can be caused by lack of space (NOT IMPLEMENTED FIXME)
     *  @param result where to put the expansion RelWert
     *  @param length how many Tp-s will be filled by the expansion
     *  @param doppelhaken the Event, for getting Location and form of DoppelHaken
     *  @param forceOverlap whether the K-voice input contains the operator "tilde" for
     *   the end of the DoppelHaken, as in "MOM~".
     *  @param mayOverlap whether the DoppelHaken ends with the same RelWert as its successor
     *   begins.
     */
    protected void flushPendingDoppelHaken (final List<RelWert> result,
					    final int length, 
					    final @Opt Event doppelhaken,
					    final boolean forceOverlap,
					    final boolean mayOverlap){
      if (doppelhaken==null)
	return ; 
      final DoppelHaken h = event2doppelHaken.get(doppelhaken); 
      final boolean internalOverlap = h.doesOverlap();
      final int prefix  =  4 + (internalOverlap ? 0 : 1) ; 
      // = the length of the DoppelHaken without the very last RelWert
      final boolean doOverlap = forceOverlap || ((prefix==length)&&mayOverlap) ; 
      final int segs = prefix + (doOverlap ? 0 : 1);
      if (segs>length){
	msg.error(doppelhaken.get_location(), 
		  "not enough space for DoppelHaken: has %d, needs %d", length, segs);
	for (int i=0;i<length;i++)
	  result.add(RelWert.M);
	return ;
      }
      final int segLength = length / segs ; 
      int rest = length-segs*segLength;
      if (rest>0)
	if (parameters.warnUnevenHakenDistribution)
	  msg.warning(doppelhaken.get_location(), 
		      "DoppelHaken expansion has an unregular rest: "+length);
      int seg0 = segLength, seg1 = segLength, seg2 = segLength, 
	seg3 = internalOverlap ? 0 : segLength, seg4 = segLength,
	seg5 = doOverlap? 0 : segLength ; 
      
      if (rest-->0)  // rest 5 4 3 2 1 
	seg2++; 
      if (rest-->0)  // rest 4 3 2 1 
	seg1++;
      if (rest-->0)  // rest 3 2 1 
	seg4++;
      if (rest-->0)  // rest 2 1 
	seg0++;
      if (rest-->0)  // rest 1  --> all 6 segments do exist!
	seg5++;

      final Haken f = h.getFirst();
      dhPut (result, f.getFirst(), seg0);
      dhPut (result, f.getMiddle(), seg1);
      dhPut (result, f.getLast(), seg2);
      final Haken l = h.getLast();
      dhPut (result, l.getFirst(), seg3);
      dhPut (result, l.getMiddle(), seg4);
      dhPut (result, l.getLast(), seg5);
    }// flushPendingDoppelHaken


    /** Put one segement of a DoppelHaken
     *  @param result where to add.
     *  @param v the value to add.
     *  @param c number of positions to add, maybe == null.
     */
    protected void dhPut (final List<RelWert> result,
			  final RelWert v, 
			  final int c){
      for (int i=0;i<c;i++)
	result.add(v);
    }

  }//class Expansion

}