/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package compose;

import data.INoteAmount;
import data.MIDIBaseChord;
import data.MIDIBaseChords;
import data.MIDIMelodicInstrument;
import data.MIDIPartData;
import data.MultiBeat;
import data.NoteData;
import database.DatabaseInterface;
import genetic.PolyphonFitnessFunction;
import gui.ComposingStatusDialog;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Random;
import jm.music.data.Note;
import jm.music.data.Part;
import jm.music.data.Phrase;
import jm.music.data.Score;

/**
 *
 * @author Tom
 */
public class PolyphonGeneticComposer {
    /**username*/
    private String user = "";
    /**password*/
    private String pw = "";
    /**DB-Url*/
    private String url = "";
    /**Pulses Per Quarter Note*/
    private static int PPQN = 480;
    /**Array der IDs der zu verwendeten Instrumente (200 entspricht Percussion)*/
    private int[] instruments = null; 
    /**ID der verwendeten/entstehenden Kategorie (Genre)*/
    private int category = -1;
    /**BPM (Beats per Minute)*/
    private int tempo = 120; 
    /**Laenge des MIDI-Tracks in Sekunden*/
    private int tracklength = 10;
    /**Tonart der neuen Komposition*/
    private String key = "C"; 
    /**Dur (major): true, Moll (minor): false*/
    private boolean major = true; 
    /**Anzahl der Motive pro Instrument, die als Grundpopulation dienen sollen*/
    private static int STARTSIZE = 5;
    /**Anzahl der Viertelnoten pro Takt*/
    private int numerator = 4; 
    /**gibt an, welche Instrumente Melodie, Akkord oder zufaellig spielt*/
    private MIDIMelodicInstrument[] mmi = new MIDIMelodicInstrument[16];
    /**die Komposition*/
    private Score score = null;
    /**Halbtonschritte beim Transponieren*/
    private String[] transposeStep = {"C","C#","D","Eb","E","F","F#","G","Ab","A","Bb","B"};
    /**ArrayList mit Begleitungen*/
    private ArrayList<Part> alParts = new ArrayList<>();
    /**Volume of each Part*/
    private int[] volumes = null;
    /** >= dieser Grenze werden die Takte behalten*/
    private double fitness = 0.5; 
    /**Array fuer die Taktuebergaenge (Zeilen-/Spaltenreihenfolge 0-11 : C, C#, D, E, Eb, F, F#, G, Ab, A, Bb, B)*/
    private int[][] beatTransitions = new int[12][12];
    /**gibt an, welche Arten der Taktveraenderung verwendet werden sollen*/
    private boolean Crossover = true, NPointCrossover = true, Mutation = true;
    
    /**
     * Konstruktor des polyphonen genetischen Composers
     * @param category ID der Kategorie (Genre)
     * @param tempo BPM - Tempo des Tracks
     * @param tracklength Laenge des Tracks in Sekunden
     * @param instruments zu verwendende Instrumente
     * @param volumes Lautstaerken der einzelnen Parts
     * @param startPopulation Groesse der Grundpopulation fuer den Algorithmus (Anzahl der verschiedenen zufaellig ausgewaehlten Takte)
     * @param fitness >= diesem Wert werden bewertete Takte behalten
     * @param user DB-User
     * @param pw DB-Passwort
     * @param url DB-Url
     * @param csd Statusdialog (kann auch null sein, wenn keiner angezeigt werden soll)
     * @param Crossover true, wenn OnePointCrossover verwendet werden soll
     * @param NPointCrossover true, wenn NPointCrossover verwendet werden soll
     * @param Mutation true, wenn Mutation verwendet werden soll
     */
    public PolyphonGeneticComposer(int category, int tempo, int tracklength, int[] instruments, int[] volumes, int startPopulation,
            double fitness, String key, String user, String pw, String url, ComposingStatusDialog csd, boolean Crossover, boolean NPointCrossover, boolean Mutation) {
        STARTSIZE = startPopulation;
        this.category = category;
        this.tempo = tempo;
        this.tracklength = tracklength;
        this.instruments = instruments;
        this.volumes = volumes;
        this.fitness = fitness;
        this.user = user;
        this.pw = pw;
        this.url = url;
        this.Crossover = Crossover;
        this.NPointCrossover = NPointCrossover;
        this.Mutation = Mutation;
        this.key = key.substring(0, key.indexOf(" "));
        if (key.substring(key.indexOf(" ")+1).equalsIgnoreCase("major")){
            major = true;
        } else {
            major = false;
        }
        
        initialiseInstruments();
        //Hauptinstrument (fuer Melodie) waehlen
        int chosenInstrument = chooseInstrumentForMelody();
        if (chosenInstrument == -1){
            score = null;
        } else {
            //Taktlaenge zufaellig ermitteln
            numerator = getNumerator();
            //zufaellige Startmotife waehlen
            MIDIPartData mpd = getStartMotifs(chosenInstrument);
            
            if (mpd == null){
                score = null;
            } else {
                //moegliche Fehler korrigieren (zu kurzer Takt)
                mpd = fillUpMotifs(mpd.clone());
            
                //transponiere auf eine Tonart (C-Dur oder A-Moll)
                mpd = transposeMotifsToBaseTonality(mpd.clone());
                
                //transponiere alle Takte auf dieselbe Oktave
                mpd = setMotifsToSameOctave(mpd.clone());
                
                //generiere 'beatcount' Takte, pruefe diese;
                //verwerfe alle, welche als schlecht befunden werden;
                //sind noch nicht genuegend Takte vorhanden, fange von vorne an
                //(behalte dabei die guten Takte)
                mpd = generateBeats(mpd.clone());
                
                //transponiere auf gewuenschte Tonart
                mpd = transposeMotifsToChosenTonality(mpd.clone());
                
                //pruefe, ob alle Pitches in korrekter Tonhoehe (Platz fuer Begleitspuren)
                mpd = checkBeats(mpd.clone());
                if (mpd != null){
                
                    //fuege Takte mit Hilfe von Taktuebergaengen zusammen
                    mpd = connectBeats(mpd.clone());

                    //erzeuge Begleitspuren/-melodien
                    generateCounterParts(mpd, chosenInstrument);

                    //setze alle Parts zusammen
                    score = getPolyphoneScore(mpd);
                    if (csd != null){
                        csd.Finished();
                    }
                } else {
                    score = null;
                }
            }
        }
    }
    
    /**
     * fuer Debuggingzwecke
     * gibt die hoechste und die tiefste Note aus
     * @param mpd alle Takte
     */
    private void printMinMaxPitchOfEachBeat(MIDIPartData mpd){
        for (MultiBeat mb : mpd.getMultiBeats())
        {
            int min = 127, max = 0; 
            NoteData[][] ndArr = mb.getBeat();
            for (int i=0; i<ndArr.length; i++){
                for (int j=0; j<ndArr[i].length; j++){
                    if (ndArr[i][j].getPitch() != Integer.MIN_VALUE){
                        if (min > ndArr[i][j].getPitch()){
                            min = ndArr[i][j].getPitch();
                        }
                        if (max < ndArr[i][j].getPitch()){
                            max = ndArr[i][j].getPitch();
                        }
                    }
                }
            }
            System.out.println("min: " +min +" max: " +max);
        }
    }
    
    /**
     * fuer Debuggingzwecke
     * gibt den Speicherbereich jeder Note aus
     * @param mpd alle Takte
     */
    private void printIdentityHashCode(MIDIPartData mpd){
        for (MultiBeat mb : mpd.getMultiBeats())
        {
            int min = 127, max = 0; 
            NoteData[][] ndArr = mb.getBeat();
            for (int i=0; i<ndArr.length; i++){
                for (int j=0; j<ndArr[i].length; j++){
                    System.out.println(System.identityHashCode(ndArr[i][j]));
                }
            }
            System.out.println("");
        }
    }
    
    /**
     * fuer Debuggingzwecke
     * gibt einen Takt als String aus
     * @param nd NoteDataArray
     */
    private void printNoteDataArray(NoteData[][] nd){
        for (int i=0; i<nd.length; i++){
            for (int j=0; j<nd[i].length; j++){
                System.out.print(nd[i][j].getPitch() +" ");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    
    /**
     * transponiert alle Takte auf die Grundtonart (Tonart ohne Vorzeichen)
     * bei Dur in C-Dur und bei Moll in A-Moll
     * @param mpd alle Takte
     * @return transponierte Takte
     */
    private MIDIPartData transposeMotifsToBaseTonality(MIDIPartData mpd){
        ArrayList<MultiBeat> almbTemp = new ArrayList<>();
        for (MultiBeat mb : mpd.getMultiBeats()){
            if (major){ //transponiere nach C-Dur (Grundtonart)
                almbTemp.add(TransposeBeat(mb, mb.getKey(), "C",200));
            } else { //transponiere nach A-Moll (Grundtonart)
                almbTemp.add(TransposeBeat(mb, mb.getKey(), "A",200));
            }
        }
        mpd.setMultiBeat(almbTemp);
        return mpd;
    }
    
    /**
     * transponiert alle Takte auf die gleiche Oktave
     * @param mpd alle Takte
     * @return transponierte Takte
     */
    private MIDIPartData setMotifsToSameOctave(MIDIPartData mpd){
        ArrayList<MultiBeat> almbTemp = new ArrayList<>();
        int refAvg = 0;
        boolean first = true;
        for (MultiBeat mb : mpd.getMultiBeats()){
            if (first){ //Referenzdurchschnitt berechnen
                refAvg = getAveragePitch(mb);
                almbTemp.add(mb);
                first = false;
            } else { //Takt auf selbe Oktave transponieren
                almbTemp.add(getMultiBeatInCorrectOctave(mb, refAvg));
            }
        }
        mpd.setMultiBeat(almbTemp);
        return mpd;
    }
    
    /**
     * generiert neue Takte mit Hilfe eines genetischen Algorithmus
     * erzeugt so lange Takte, bis die benoetigte Anzahl an Takten (beatcount) erreicht wurde
     * danach werden alle Takte nach verschiedenen Fitnessfunctions bewertet und fuer ungenuegend
     * befundene Takte werden verworfen, alle positiven Takte werden zu den bereits vorhandenen
     * Takten hinzugefuegt.
     * neue Takte entstehen mit Hilfe von
     * - OnePointCrossover
     * - NPointCrossover
     * - Mutation
     * @param mpd alle Takte
     * @return Grundmotive und generierte bewertete Takte
     */
    private MIDIPartData generateBeats(MIDIPartData mpd){
        boolean notEnough = true;
        int beatcount = getBeatCountForTrack(); //Anzahl der maximal benoetigten Takte
        while (notEnough){
            while (mpd.getMultiBeats().size() < beatcount){
                mpd = createNewBeats(mpd.clone());
            }
            mpd = gradeBeats(mpd.clone());
            if (mpd.getMultiBeats().size() >= beatcount){
                notEnough = false;
            }
        }
        return mpd;
    }
    
    /**
     * transponiert alle Takte auf die gewuenschte Tonart
     * @param mpd alle Takte
     * @return transponierte Takte
     */
    private MIDIPartData transposeMotifsToChosenTonality(MIDIPartData mpd){
        int Steps;
        if (major){ //von C-Dur
            Steps = getHalftoneSteps("C", key);
        } else { //von A-Moll
            Steps = getHalftoneSteps("A", key);
        }
        ArrayList<MultiBeat> almbTemp = new ArrayList<>();
        for (MultiBeat mb : mpd.getMultiBeats()){
            if (major){
                almbTemp.add(TransposeBeat(mb, "C", key, Steps));
            } else {
                almbTemp.add(TransposeBeat(mb, "A", key, Steps));
            }
        }
        mpd.setMultiBeat(almbTemp);
        return mpd;
    }
    
    /**
     * prueft, ob alle Pitches noch gueltige Werte besitzen
     * und ob Platz fuer die Begleitspuren bleibt
     * @param mpd alle Takte
     * @return korrigierte Takte
     */
    private MIDIPartData checkBeats(MIDIPartData mpd){
        int min=127, max=0;
        
        //hoechsten und niedrigsten Pitch holen
        for (MultiBeat mb : mpd.getMultiBeats()){
            NoteData[][] ndArr = mb.getBeat();
            for (int i=0; i<ndArr.length; i++){
                for (int j=0; j<ndArr[i].length; j++){
                    if (ndArr[i][j].getPitch() != Integer.MIN_VALUE){
                        if (min > ndArr[i][j].getPitch()){
                            min = ndArr[i][j].getPitch();
                        }
                        if (max < ndArr[i][j].getPitch()){
                            max = ndArr[i][j].getPitch();
                        }
                    }
                }
            }
        }
        
        if (min >= 12 && max <= 115){ //passt alles
            return mpd;
        } else if (min >= 12 && max > 115){ //1 Oktave nach unten transponieren
            for (MultiBeat mb : mpd.getMultiBeats()){
                NoteData[][] ndArr = mb.getBeat();
                for (int i=0; i<ndArr.length; i++){
                    for (int j=0; j<ndArr[i].length; j++){
                        if (!(ndArr[i][j].getPitch() == Integer.MIN_VALUE)){
                            ndArr[i][j].setPitch(ndArr[i][j].getPitch()-12);
                        }
                    }
                }
                mb.setBeat(ndArr);
            }
            return mpd;
        } else if (min < 12 && max <= 115){ //1 Oktave nach oben transponieren
            for (MultiBeat mb : mpd.getMultiBeats()){
            NoteData[][] ndArr = mb.getBeat();
                for (int i=0; i<ndArr.length; i++){
                    for (int j=0; j<ndArr[i].length; j++){
                        if (!(ndArr[i][j].getPitch() == Integer.MIN_VALUE)){
                            ndArr[i][j].setPitch(ndArr[i][j].getPitch()+12);
                        }
                    }
                }
                mb.setBeat(ndArr);
            }
            return mpd;
        } else { //min < 12 && max > 115
            return null;
        }
    }
    
    /**
     * verbindet die Takte mit Hilfe der Taktuebergangstabelle
     * @param mpd alle Takte
     * @return Takte in korrekter Reihenfolge
     */
    private MIDIPartData connectBeats(MIDIPartData mpd){
        int beatcount = getBeatCountForTrack(); //Anzahl der maximal benoetigten Takte
        int min = 0, max = mpd.getMultiBeats().size()-1;
        DatabaseInterface dbi = new DatabaseInterface(user, pw, url);
        beatTransitions = dbi.getBeatTransition(category);
        dbi.closeConnection();
        
        //waehle zufaellig einen Takt aus
        int startID = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
        ArrayList<MultiBeat> almb = new ArrayList<>();
        boolean goOn = true;
        
        while (goOn){
            if (almb.size() < beatcount){
                if (startID != -1){
                    MultiBeat mb = mpd.getMultiBeats().get(startID); //erster Takt zufaellig gewaehlt
                    almb.add(mb);
                    mb = getFollower(mb, mpd);
                    if (mb != null){
                        almb.add(mb);
                        startID = -1;
                    } else { //kein Nachfolger vorhanden => waehle neuen ersten Takt und probiere neu
                        almb = new ArrayList<>();
                        startID = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
                    }
                } else {
                    MultiBeat mb = getFollower(almb.get(almb.size()-1), mpd);
                    if (mb != null){
                        almb.add(mb); //letzter Takt
                    } else { //kein passender Nachfolger vorhanden => entferne letzten Takt und suche neu
                        almb.remove(almb.size()-1);
                    }
                }
            } else {
                goOn = false;
            }
        }
        mpd.setMultiBeat(almb);
        return mpd;
    }
    
    /**
     * generiert Begleittakte, passen zu den Takten der Grundmelodie
     * @param mpd alle Takte
     * @param chosenInstrument Instrument, welches die Grundmelodie spielt
     */
    private void generateCounterParts(MIDIPartData mpd, int chosenInstrument){
        int pos = 1;
        boolean percussions = false;
        for (int i : instruments){
            //Hauptmelodiespur ist schon vorhanden und
            //Percussions muessen extra generiert werden
            //Percussivs werden wie Percussions generiert
            if (i != chosenInstrument && i != 200 && !(i >= 112 && i <= 119)){
                Part pTemp = createCounterParts(mpd, i, pos);
                if (pTemp != null){
                    alParts.add(pTemp);
                }
            } else if(i == 200){ //Percussions
                percussions = true;
            } else if (i >= 112 && i <= 119){ //Percussivs
                alParts.add(createPercussivs(mpd, i, pos));
            }
        }

        //erzeuge Percussions
        if (percussions){
            //Part mit Percussions erzeugen
            if (mpd.getMultiBeats().size() > 0){
                alParts.add(createPercussions(mpd));
            }
        }
    }
    
    /**
     * erzeugt eine Begleitspur passend zu den uebergebenen Takten
     * nach Vorgaben gespeichert in mmi (MIDIMelodicInstrument)
     * @param almb Takte, welche die Grundmelodie darstellen
     * @param instrument Instrument, mit welchem der neue Part gespielt werden soll
     * @param channel der Channel des aktuellen Parts
     * @return begleitender Part
     */
    private Part createCounterParts(MIDIPartData almb, int instrument, int channel){
        for (MIDIMelodicInstrument mi : mmi){
            if (instrument >= mi.getInstrument_from() && instrument <= mi.getInstrument_to()){
                //wenn Instrument Melodie und Akkorde spielen darf
                //entscheide zufaellig, ob die Spur eine Melodie oder Akkordspur wird
                if (mi.isHarmony() && mi.isMelody()){
                    int melharm = 0 + (int)(Math.random() * ((1 - 0) + 1)); //entweder 0 oder 1
                    if (melharm == 1){ //Instrument darf Akkorde begleitend spielen
                        return createHarmonyPart(almb.getMultiBeats(), instrument, channel);
                    } else { //Instrument darf Melodie begleitend spielen
                        return createPolyphoneMelodyPart(almb.getMultiBeats(), instrument, channel, true);
                    }
                } else if (mi.isHarmony()){ //Instrument darf Akkorde begleitend spielen
                    return createHarmonyPart(almb.getMultiBeats(), instrument, channel);
                } else if (mi.isMelody()){ //Instrument darf Melodie begleitend spielen
                    return createPolyphoneMelodyPart(almb.getMultiBeats(), instrument, channel, true);
                } else { //Instrument spielt zufaellige Toene im Verlauf des Lieds
                    return createRandomNoisePart(almb.getMultiBeats(), instrument, channel);
                }
            }
        }
        return null;
    }
    
    /**
     * erstellt Percussions als Begleitung
     * @param mpd Takte, zu denen die Percussions erzeugt werden
     * @return Part mit Percussions
     */
    private Part createPercussions(MIDIPartData mpd){
        Part p = new Part("Part 9", 0, 9);
        Phrase drums = new Phrase(0.0);
        
        for (MultiBeat mb : mpd.getMultiBeats()){
            for (int i=0; i<numerator; i++){
                Note n = new Note(36, PPQN);
                n.setDuration(1.0);
                n.setDynamic(volumes[volumes.length-1]);
                drums.add(n);
            }
        }
        p.add(drums);
        return p;
    }
    
    /**
     * erstellt Percussions als Begleitung
     * @param mpd Takte, zu denen die Percussions erzeugt werden
     * @param instrument Instrument, das den Part spielt
     * @param channel der Channel des Parts
     * @return Part mit Percussions
     */
    private Part createPercussivs(MIDIPartData mpd, int instrument, int channel){
        Part p = new Part("Part " +channel, instrument, channel);
        Phrase phr = new Phrase(0.0);
        
        for (MultiBeat mb : mpd.getMultiBeats()){ //jeden Takt der ArrayList
            NoteData[][] ndarr = mb.getBeat();
            if (ndarr.length > 0 && ndarr[0].length > 0){
                int lowest = getLowestFirstPitch(mb);
                for (int i=0; i<numerator; i++){
                    Note n = new Note(lowest, PPQN);
                    n.setDuration(1.0);
                    n.setDynamic(volumes[channel]);
                    phr.add(n);
                }
            }
        }
        p.add(phr);
        return p;
    }
    
    /**
     * liefert einen Takt, der auf Grund der Taktuebergangstabelle
     * ein moeglicher Nachfolger des uebergebenen Takts ist
     * @param mb Takt, fuer den ein Nachfolger gesucht wird
     * @param mpd alle generierten Takte
     * @return nachfolgender Takt
     */
    private MultiBeat getFollower(MultiBeat mb, MIDIPartData mpd){
        NoteData[][] ndArr = mb.getBeat();
        
        if (ndArr.length > 0){
            int column = ndArr.length-1; //letzte Note vom Takt
            String note;
            while (true){
                note = ndArr[0][column].getNote();
                if (note.equalsIgnoreCase("REST") || note.equalsIgnoreCase("N/A")){
                    column--; //probiere Note davor
                    if (column < 0){
                        return chooseFollower("C", mpd);
                    }
                } else {
                    return chooseFollower(note, mpd);
                }
            }
        }
        return null;
    }
    
    /**
     * waehlt einen Nachfolgertakt fuer mb aus den Takten in mpd,
     * anhand der Taktuebergangstabelle aus
     * @param note Note, fuer die ein Nachfolger gesucht wird
     * @param mpd alle generierten Takte
     * @return nachfolgender Takt
     */
    private MultiBeat chooseFollower(String note, MIDIPartData mpd){
        int row = getIDForNote(note);
        String[] sNotes = {"C","C#","D","Eb","E","F","F#","G","Ab","A","Bb","B"};
        int[] actRow = {0,0,0,0,0,0,0,0,0,0,0,0};
        
        for (int i=0; i<beatTransitions[row].length; i++){
            actRow[i] = beatTransitions[row][i];
        }
        
        //sortiere die Wahrscheinlichkeiten aufsteigen und sortiere dabei auch die Noten
        int tempI;
        String tempS;
        for(int i=1; i<actRow.length; i++) {
            for(int j=0; j<actRow.length-i; j++) {
                if(actRow[j]>actRow[j+1]) {
                    tempI=actRow[j];
                    tempS=sNotes[j];
                    actRow[j]=actRow[j+1];
                    sNotes[j]=sNotes[j+1];
                    actRow[j+1]=tempI;
                    sNotes[j+1]=tempS;
                }
            }
        }
        ArrayList<MultiBeat> almb = new ArrayList<>();
        
        while (almb.isEmpty()){
            int randProb = 1 + (int)(Math.random() * ((99 - 1) + 1)); //zufaelliger Wert zwischen (inkl.) 1 und 99
            String followNote = "C";
            int sum = 0;
            for (int i=0; i < actRow.length-1; i++){
                sum += actRow[i];
                if (sum >= randProb){
                    followNote = sNotes[i];
                    break;
                }
            }

            //hole alle Takte, die mit der Note 'followNote' beginnen
            for (MultiBeat m : mpd.getMultiBeats()){
                NoteData[][] ndArr = m.getBeat();
                for (int i=0; i<ndArr.length; i++){
                    //wenn eine der ersten Noten im Takt gleich 'followNote' ist
                    if (ndArr[i][0].getNote().equalsIgnoreCase(followNote)){
                        almb.add(m);
                        break;
                    }
                }
            }
        }
        
        //waehle zufaellig einen der Takte als Nachfolger aus
        int id = 0 + (int)(Math.random() * ((almb.size() - 1) + 1)); //zufaelliger Wert zwischen (inkl.) 0 und almb.size()-1
        return almb.get(id);
    }
    
    /**
     * liefert zur uebergebenen Note die ID i Taktuebergangsarray
     * @param s Note (zB.: C, C#, D, Eb, ...)
     * @return ID im Array
     */
    private int getIDForNote(String s){
        switch (s){
            case "C":
                return 0;
            case "C#":
                return 1;
            case "D":
                return 2;
            case "Eb":
                return 3;
            case "E":
                return 4;
            case "F":
                return 5;
            case "F#":
                return 6;
            case "G":
                return 7;
            case "Ab":
                return 8;
            case "A":
                return 9;
            case "Bb":
                return 10;
            case "B":
                return 11;
        }
        return -1;
    }
    
    /**
     * liefert den Durchschnittspitch des Takts
     * @param mb der zu analysierende Takt
     * @return Durchschnittspitch
     */
    private int getAveragePitch(MultiBeat mb){
        NoteData[][] ndArr = mb.getBeat();
        int count = 0, sum = 0;
        for (int i=0; i<ndArr.length; i++){
          for (int j=0; j<ndArr[0].length; j++){
              //Pausen ignorieren
              if (ndArr[i][j].getPitch() != Integer.MIN_VALUE){
                  sum += ndArr[i][j].getPitch();
                  count++;
              }
          }
        }
        if (count != 0){
            return sum/count;
        } else {
            return 60; //mittleres C (4. Oktave)
        }
    }
    
    /**
     * liefert einen MultiBeat auf die Oktave transponiert,
     * welche dem Durchschnittspitch (Avg) entspricht
     * @param mb der zu transponierende MultiBeat
     * @param Avg der Referenzdurchschnittspitch
     * @return transponierter MultiBeat
     */
    private MultiBeat getMultiBeatInCorrectOctave(MultiBeat mb, int Avg){
        //Halbtonschritte fuer die Transposition berechnen
        int Steps = getAveragePitch(mb);
        if (Steps > Avg){
            Steps -= Avg;
            Steps *= -1;
        } else {
            Steps = Avg - Steps;
        }
        //keine Aenderung => Korrektur nicht noetig
        if (Steps == 0){
            return mb;
        }
        //transponiere alle Noten
        NoteData[][] ndArr = mb.getBeat();
        for (int i=0; i<ndArr.length; i++){
            for (int j=0; j<ndArr[0].length; j++){
                if (ndArr[i][j].getPitch() != Integer.MIN_VALUE){ //Pausen bleiben Pausen
                    ndArr[i][j].setPitch(ndArr[i][j].getPitch()+Steps);
                }
            }
        }
        MultiBeat mbNew = new MultiBeat(ndArr);
        mbNew.setInstrument(mb.getInstrument());
        mbNew.setKey(mb.getKey());
        mbNew.setMajor(mb.isMajor());
        return mbNew;
    }
    
    /**
     * initialisiert die Instrumentengruppen,
     * ob sie Melodie, Akkorde oder zufaellige Toene spielen sollen/duerfen
     */
    private void initialiseInstruments(){
        mmi[0] = new MIDIMelodicInstrument(0, 7, true, true, false); //Piano
        mmi[1] = new MIDIMelodicInstrument(8, 15, true, true, false); //Chromatic Percussion
        mmi[2] = new MIDIMelodicInstrument(16, 23, false, true, false); //Organ
        mmi[3] = new MIDIMelodicInstrument(24, 31, true, true, false); //Guitar
        mmi[4] = new MIDIMelodicInstrument(32, 39, false, true, false); //Bass
        mmi[5] = new MIDIMelodicInstrument(40, 47, true, false, false); //Strings
        mmi[6] = new MIDIMelodicInstrument(48, 55, false, true, false); //Ensemble
        mmi[7] = new MIDIMelodicInstrument(56, 63, true, true, false); //Brass
        mmi[8] = new MIDIMelodicInstrument(64, 71, true, false, false); //Reed
        mmi[9] = new MIDIMelodicInstrument(72, 79, true, false, false); //Pipe
        mmi[10] = new MIDIMelodicInstrument(80, 87, true, false, false); //Synth Lead
        mmi[11] = new MIDIMelodicInstrument(88, 95, false, true, false); //Synth Pad
        mmi[12] = new MIDIMelodicInstrument(96, 103, false, false, true); //Synth Effects
        mmi[13] = new MIDIMelodicInstrument(104, 111, true, false, false); //Ethnic
        mmi[14] = new MIDIMelodicInstrument(112, 119, false, false, true); //Percussive
        mmi[15] = new MIDIMelodicInstrument(120, 127, false, false, true); //Sound Effects
    }
    
    /**
     * liefert einen polyphonen Score bestehend aus den Phrasen und Noten der uebergebenen Takte
     * @param mpd Instrument und Motife
     * @return MIDI-Score
     */
    private Score getPolyphoneScore(MIDIPartData mpd){
        Score s = new Score("pbmc-composition",tempo);
        s.setPPQN(PPQN); 
        
        //Grundmelodie hinzufuegen
        s.add(createPolyphoneMelodyPart(mpd.getMultiBeats(), mpd.getInstrument(), 0, false));
        
        //Begleitparts und Percussions hinzufuegen
        for (Part p : alParts){
            s.add(p);
        }
        
        //set major, minor
        if (major) {
           s.setKeyQuality(0); //0 = major, 1 = minor
        } else {
           s.setKeyQuality(1); //0 = major, 1 = minor
        }
        return s;
    }
    
    /**
     * liefert die neue Komposition
     * @return die Komposition
     */
    public Score getComposition(){
        return score;
    }
    
    /**
     * liefert einen polyphonen Part bestehend aus den Noten des uebergebenen Takts
     * @param almb ArrayList mit polyphonen Takten
     * @param instrument das zu verwendende Instrument
     * @param part Nummer des Parts (ist auch Channelnummer)
     * @param transpose true, wenn Pitches um 1 Oktave nach unten transponiert werden sollen
     * @return MIDI-Part
     */
    private Part createPolyphoneMelodyPart(ArrayList<MultiBeat> almb, int instrument, int part, boolean transpose){
        //maximale Phrasenanzahl der Takte berechnen
        //(muss bei weniger Phrasen mit leeren Takten ergaenzt werden)
        int phrasecount = getMaxPhraseCount(almb);
        
        Part p = new Part("Part " +part, instrument, part);
        
        for (int phr=0; phr<phrasecount; phr++){ //Phrase eines Takts
            Phrase ph = new Phrase(0.0);
            for (MultiBeat mb : almb){ //jeden Takt der ArrayList
                NoteData[][] ndarr = mb.getBeat();
                if (ndarr.length > phr){ //wenn aktueller Takt genug Phrasen hat
                    //Noten zur Phrase hinzufuegen
                    for (int i=0; i<ndarr[phr].length; i++){
                        int Pitch = Integer.MIN_VALUE;
                        if (ndarr[phr][i].getPitch() != Integer.MIN_VALUE){
                            if (transpose){
                                Pitch = ndarr[phr][i].getPitch() - 12;
                            } else {
                                Pitch = ndarr[phr][i].getPitch();
                            }
                        }
                        Note n = new Note(Pitch, ndarr[phr][i].getQuantizedDuration()*PPQN);
                        n.setDuration(ndarr[phr][i].getQuantizedDuration());
                        n.setDynamic(volumes[part]);
                        ph.add(n);
                    }
                } else { //sonst leere Takt einfuegen (Pause)
                    Note n = new Note(Integer.MIN_VALUE, numerator*PPQN);
                    n.setDuration(numerator);
                    n.setDynamic(volumes[part]);
                    ph.add(n);
                }
            }
            p.addPhrase(ph);
        }
        return p;
    }
    
    /**
     * liefert einen Begleitpart bestehend aus Begleitakkorden
     * @param almb ArrayList mit polyphonen Takten
     * @param instrument das zu verwendende Instrument
     * @param part Nummer des Parts (ist auch Channelnummer)
     * @return MIDI-Part
     */
    private Part createHarmonyPart(ArrayList<MultiBeat> almb, int instrument, int part){
        Part p = new Part("Part " +part, instrument, part);
        Phrase ph1 = new Phrase(0.0);
        Phrase ph2 = new Phrase(0.0);
        Phrase ph3 = new Phrase(0.0);
        
        for (MultiBeat mb : almb){ //jeden Takt der ArrayList
            NoteData[][] ndarr = mb.getBeat();
            //erstelle einen Akkord mit der Dauer eines vollen Takts pro Takt
            if (ndarr.length > 0 && ndarr[0].length > 0){
                int lowest = getLowestFirstPitch(mb);
                String Base = getNoteForInt(lowest); //Grundton des Akkords
                MIDIBaseChord mbc;
                if (major){
                    switch (Base){
                        case "C":
                            mbc = MIDIBaseChords.CMajor;
                            break;
                        case "C#":
                            mbc = MIDIBaseChords.CisMajor;
                            break;
                        case "D":
                            mbc = MIDIBaseChords.DMajor;
                            break;
                        case "Eb":
                            mbc = MIDIBaseChords.EbMajor;
                            break;
                        case "E":
                            mbc = MIDIBaseChords.EMajor;
                            break;
                        case "F":
                            mbc = MIDIBaseChords.FMajor;
                            break;
                        case "F#":
                            mbc = MIDIBaseChords.FisMajor;
                            break;
                        case "G":
                            mbc = MIDIBaseChords.GMajor;
                            break;
                        case "Ab":
                            mbc = MIDIBaseChords.AbMajor;
                            break;
                        case "A":
                            mbc = MIDIBaseChords.AMajor;
                            break;
                        case "Bb":
                            mbc = MIDIBaseChords.BbMajor;
                            break;
                        case "B":
                            mbc = MIDIBaseChords.HMajor;
                            break;
                        case "":
                            mbc = null;
                            break;
                        default:
                            mbc = null;
                            break;
                    }
                } else {
                    switch (Base){
                        case "C":
                            mbc = MIDIBaseChords.CMinor;
                            break;
                        case "C#":
                            mbc = MIDIBaseChords.CisMinor;
                            break;
                        case "D":
                            mbc = MIDIBaseChords.DMinor;
                            break;
                        case "Eb":
                            mbc = MIDIBaseChords.EbMinor;
                            break;
                        case "E":
                            mbc = MIDIBaseChords.EMinor;
                            break;
                        case "F":
                            mbc = MIDIBaseChords.FMinor;
                            break;
                        case "F#":
                            mbc = MIDIBaseChords.FisMinor;
                            break;
                        case "G":
                            mbc = MIDIBaseChords.GMinor;
                            break;
                        case "Ab":
                            mbc = MIDIBaseChords.AbMinor;
                            break;
                        case "A":
                            mbc = MIDIBaseChords.AMinor;
                            break;
                        case "Bb":
                            mbc = MIDIBaseChords.BbMinor;
                            break;
                        case "B":
                            mbc = MIDIBaseChords.HMinor;
                            break;
                        case "":
                            mbc = null;
                            break;
                        default:
                            mbc = null;
                            break;
                    }
                }
                
                if (mbc != null){ //Akkord erstellen
                    int diff = mbc.getFirst() - lowest;
                    if (numerator == 2 || numerator == 3){ //auf 1
                        Note n1 = new Note(lowest, numerator*PPQN);
                        n1.setDuration(numerator);
                        n1.setDynamic(volumes[part]);
                        ph1.add(n1);
                        n1.setPitch(mbc.getSecond()-diff);
                        ph2.add(n1);
                        n1.setPitch(mbc.getThird()-diff);
                        ph3.add(n1);
                    } else if (numerator == 4){ //auf 1 und 3
                        Note n1 = new Note(lowest, numerator/2*PPQN);
                        n1.setDuration(numerator/2);
                        n1.setDynamic(volumes[part]);
                        ph1.add(n1);
                        ph1.add(n1);
                        n1.setPitch(mbc.getSecond()-diff);
                        ph2.add(n1);
                        ph2.add(n1);
                        n1.setPitch(mbc.getThird()-diff);
                        ph3.add(n1);
                        ph3.add(n1);
                    } else {
                        Note n = getEmptyBeat();
                        ph1.add(n);
                        ph2.add(n);
                        ph3.add(n);
                    }
                } else { //sonst leere Takt einfuegen (Pause)
                    Note n = getEmptyBeat();
                    ph1.add(n);
                    ph2.add(n);
                    ph3.add(n);
                }
            } else { //sonst leere Takt einfuegen (Pause)
                Note n = getEmptyBeat();
                ph1.add(n);
                ph2.add(n);
                ph3.add(n);
            }
        }
        
        p.addPhrase(ph1);
        p.addPhrase(ph2);
        p.addPhrase(ph3);
        return p;
    }
    
    private Note getEmptyBeat(){
        Note n = new Note(Integer.MIN_VALUE, numerator*PPQN);
        n.setDuration(numerator);
        n.setDynamic(100);
        return n;
    }
    
    /**
     * liefert zu einem Pitch die Note als String
     * @param pitch Pitch als Integer
     * @return die Note als String
     */
    private String getNoteForInt(int pitch){
        pitch = pitch % 12;
        
        switch (pitch){
            case 0:
                return "C";
            case 1:
                return "C#";
            case 2:
                return "D";
            case 3:
                return "Eb";
            case 4:
                return "E";
            case 5:
                return "F";
            case 6:
                return "F#";
            case 7:
                return "G";
            case 8:
                return "Ab";
            case 9:
                return "A";
            case 10:
                return "Bb";
            case 11:
                return "B";
            default:
                return "";
        }
    }
    
    /**
     * liefert den tiefsten Pitch der ersten (auftretenden) Note
     * @param mb MultiBeat 
     * @return niedrigster Pitch der ersten Note
     */
    private int getLowestFirstPitch(MultiBeat mb){
        NoteData[][] ndarr = mb.getBeat();
        boolean onlyRest = true;
        int lowest = 200;
        int pos = 0;
        while (onlyRest){
            for (int i=0; i<ndarr.length; i++){
                if (ndarr[i][pos].getPitch() < lowest){
                    lowest = ndarr[i][pos].getPitch();
                    onlyRest = false;
                }
            }
            pos++;
        }
        return lowest;
    }
    
    /**
     * liefert einen Begleitpart bestehend aus zufaelligen Geraeuschen
     * @param almb ArrayList mit polyphonen Takten
     * @param instrument das zu verwendende Instrument
     * @param part Nummer des Parts (ist auch Channelnummer)
     * @return MIDI-Part
     */
    private Part createRandomNoisePart(ArrayList<MultiBeat> almb, int instrument, int part){
        int min = 0, max = numerator;
        int noiseCount; //Anzahl der Geraeusche im Takt
        
        Part p = new Part("Part " +part, instrument, part);
        Phrase ph = new Phrase(0.0);
        for (MultiBeat mb : almb){ //jeden Takt der ArrayList
            NoteData[][] ndarr = mb.getBeat();
            //erstelle zufaellige Toene innerhalb des Takts
            if (ndarr.length > 0 && ndarr[0].length > 0){
                noiseCount = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
                
                //Positionen der Geraeusche im Takt bestimmten
                boolean[] bArr = new boolean[numerator];
                boolean bSet = false;
                if (noiseCount == numerator){ //wenn alle Viertelnoten Geraeusche sind, kann man gleich alle auf true setzen
                    bSet = true;
                }
                for (int i=0; i<numerator; i++){
                    bArr[i] = bSet;
                }
                if (!bSet){
                    for (int i=0; i<noiseCount; i++){
                        boolean next = true;
                        while (next){
                            int pos = min + (int)(Math.random() * ((max - 1 - min) + 1)); //Position des Geraeusches im Takt
                            if (!bArr[pos]){
                                bArr[pos] = true;
                                next = false;
                            }
                        }
                    }
                }
                for (int i=0; i<bArr.length; i++){
                    if (bArr[i]){
                        int pitch = Integer.MIN_VALUE;
                        int shift = 0;
                        while (pitch == Integer.MIN_VALUE){
                            pitch = ndarr[0][shift].getPitch();
                            shift++;
                        }
                        Note n = new Note(pitch, PPQN);
                        n.setDuration(1.0);
                        n.setDynamic(volumes[part]);
                        ph.add(n);
                    } else { //Viertelpause einfuegen
                        Note n = new Note(Integer.MIN_VALUE, PPQN);
                        n.setDuration(1.0);
                        n.setDynamic(volumes[part]);
                        ph.add(n);
                    }
                }
            } else { //sonst leere Takt einfuegen (Pause)
                Note n = new Note(Integer.MIN_VALUE, numerator*PPQN);
                n.setDuration(numerator);
                n.setDynamic(volumes[part]);
                ph.add(n);
            }
        }
        p.addPhrase(ph);
        return p;
    }
    
    /**
     * liefert die Anzahl der maximalen Phrasen aller Takte
     * @param almb ArrayList mit polyphonen Takten
     * @return maximale Anzahl der Phrasen
     */
    private int getMaxPhraseCount(ArrayList<MultiBeat> almb){
        int max = 0;
        for (MultiBeat mb : almb){
            if (max < mb.getBeat().length){
                max = mb.getBeat().length;
            }
        }
        return max;
    }
    
    /**
     * waehlt aus den zu verwendenden Instrumenten ein passendes fuer die Melodie aus
     * gibt es kein passendes, wird das erste Instrument zugewiesen
     * @return Instrument, welches die Hauptmelodie spielen soll
     */
    private int chooseInstrumentForMelody(){
        for (int i : instruments){
            if (InstrumentPlaysMelody(i)){
                return i;
            }
        }
        //kein Instrument sollte die Melodie spielen => nimm das erste Instrument fuer die Melodie
        if (instruments.length > 0){
            return instruments[0];
        } else {
            return -1;
        }
    }
    
    /**
     * gibt an, ob das uebergebene Instrument eine Melodie spielen kann/soll
     * @param instrument ID des Instruments
     * @return true, wenn Instrument Melodie spielen kann
     */
    private boolean InstrumentPlaysMelody(int instrument){
        for (MIDIMelodicInstrument mm : mmi){
            if (instrument >= mm.getInstrument_from() && instrument <= mm.getInstrument_to() && mm.isMelody()){
                return true;
            }
        }
        return false;
    }
    
    /**
     * liefert den zufaellig ausgewaehlten Numerator einer Kategorie
     * @return Numerator
     */
    private int getNumerator(){
        DatabaseInterface dbi = new DatabaseInterface(user, pw, url);
        int[] iArr = dbi.getCategoryNumeratorAndDenominator(category);
        dbi.closeConnection();
        int num = iArr[0];
        int den = iArr[1];
        double d = num/den;
        if (Double.compare(d, 1.0) == 0){ // 4/4, 8/8, ...
            return 4;
        } else if (Double.compare(d, 0.5) == 0){ // 2/4, 4/8, ...
            return 2;
        } else if (Double.compare(d, 0.75) == 0){ // 3/4, 6/8, ...
            return 3;
        } else {
            return 4;
        }
    }
    
    /**
     * sucht nach einem Startmotif fuer ein Instrument aus der Kategorie,
     * welches eine Melodie spielt
     * @param chosenInstrument Instrument, welches die Hauptmelodie spielen soll
     * @return Instrument (Part) und dessen Takte
     */
    private MIDIPartData getStartMotifs(int chosenInstrument){
        ArrayList<MultiBeat> mb = new ArrayList<>();
        DatabaseInterface dbi = new DatabaseInterface(user, pw, url);
        
        int[] motifIDs = dbi.getRandomMotifForCategoryAndInstrument(category, chosenInstrument,STARTSIZE,1, major, numerator);
        //pruefen, ob Motife gefunden wurden
        boolean allNegOne = true;
        for (int i=0; i<motifIDs.length; i++){
            if (motifIDs[i] != -1){
                allNegOne = false;
                break;
            }
        }
        //keine Motife des Instruments gefunden/vorhanden
        //andere Motife aus der Instrumentengruppe
        if (allNegOne){
            int[] iArr = getInstrumentGroupBorder(chosenInstrument);
            motifIDs = dbi.getRandomMotifForCategoryAndInstrumentGroup(category, iArr[0], iArr[1],STARTSIZE,1, major, numerator);
        }
        //pruefen, ob Motife gefunden wurden
        allNegOne = true;
        for (int i=0; i<motifIDs.length; i++){
            if (motifIDs[i] != -1){
                allNegOne = false;
                break;
            }
        }
        //keine Motife fuer das Instrument vorhanden
        if (allNegOne){
            return null;
        }
        //erstelle MultiBeat des Motifs
        for (int j=0; j<motifIDs.length; j++){
            MultiBeat m = dbi.getPolyphonMotif(motifIDs[j]);
            if (m != null){
                mb.add(m);
            }
        }
        
        MIDIPartData mpd = new MIDIPartData(chosenInstrument, mb);
        dbi.closeConnection();
        return mpd;
    }
    
    /**
     * ueberprueft, ob alle Takte genau der Taktlaenge entsprechen
     * und fuellt sie gegebenenefalls mit Pausen auf
     * @param mpd die Takte
     * @return korregierte Takte
     */
    private MIDIPartData fillUpMotifs(MIDIPartData mpd){
        ArrayList<Integer> toFillUp = new ArrayList<>();
        int beatIndex = 0;
        for (MultiBeat mb : mpd.getMultiBeats()){
            NoteData[][] nd = mb.getBeat();
            for (int i=0; i<nd.length; i++){
                double beatlength = 0;
                for (int j=0; j<nd[i].length; j++){
                    beatlength += nd[i][j].getDuration();
                }
                if (beatlength < numerator){
                    if (!toFillUp.contains(beatIndex)){
                        toFillUp.add(beatIndex);
                    }
                }
            }
            beatIndex++;
        }
        //Takte mit Pausen auffuellen
        for (int i : toFillUp){
            MultiBeat mbNew = correctMultiBeat(mpd.getMultiBeats().get(i));
            mpd.getMultiBeats().set(i, mbNew);
        }
        return mpd;
    }
    
    /**
     * ergaenzt den Takt mit Pausen, um die korrekte Taktlaenge zu erreichen
     * @param mb der zu korrigierende Takt
     * @return der korrigierte Takt
     */
    private MultiBeat correctMultiBeat(MultiBeat mb){
        NoteData[][] nd = mb.getBeat();
        NoteData[][] ndNew = new NoteData[nd.length][nd[0].length+1];
        
        for (int i=0; i<nd.length; i++){
            double beatlength = 0;
            for (int j=0; j<nd[i].length; j++){
                ndNew[i][j] = nd[i][j];
                beatlength += nd[i][j].getDuration();
            }
            //Rest des Takts mit Pause auffuellen
            NoteData temp = new NoteData(0.0, numerator - beatlength, Integer.MIN_VALUE);
            temp.setQuantizedDuration(temp.getDuration());
            ndNew[i][nd[i].length] = temp;
            
        }
        return new MultiBeat(ndNew);
    }
    
    /**
     * liefert die untere und obere Grenze der Instrumentengruppe
     * des uebergebenen Instruments
     * @param instrument Instrumenten-ID (MIDI-Standard)
     * @return Array mit unterer und oberer Grenze (ID 0: unten, ID 1: oben)
     */
    private int[] getInstrumentGroupBorder(int instrument){
        int i[] = {0,0};
        if (instrument >= 0 && instrument <= 7){ //Piano
            i[0] = 0;
            i[1] = 7;
        } else if (instrument >= 8 && instrument <= 15){ //Chromatic Percussion
            i[0] = 8;
            i[1] = 15;
        } else if (instrument >= 16 && instrument <= 23){ //Organ
            i[0] = 16;
            i[1] = 23;
        } else if (instrument >= 24 && instrument <= 31){ //Guitar
            i[0] = 24;
            i[1] = 31;
        } else if (instrument >= 32 && instrument <= 39){ //Bass
            i[0] = 32;
            i[1] = 39;
        } else if (instrument >= 40 && instrument <= 47){ //Strings
            i[0] = 40;
            i[1] = 47;
        } else if (instrument >= 48 && instrument <= 55){ //Ensemble
            i[0] = 48;
            i[1] = 55;
        } else if (instrument >= 56 && instrument <= 63){ //Brass
            i[0] = 56;
            i[1] = 63;
        } else if (instrument >= 64 && instrument <= 71){ //Reed
            i[0] = 64;
            i[1] = 71;
        } else if (instrument >= 72 && instrument <= 79){ //Pipe
            i[0] = 72;
            i[1] = 79;
        } else if (instrument >= 80 && instrument <= 87){ //Synth Lead
            i[0] = 80;
            i[1] = 87;
        } else if (instrument >= 88 && instrument <= 95){ //Synth Pad
            i[0] = 88;
            i[1] = 95;
        } else if (instrument >= 96 && instrument <= 103){ //Synth Effects
            i[0] = 96;
            i[1] = 103;
        } else if (instrument >= 104 && instrument <= 111){ //Ethnic
            i[0] = 104;
            i[1] = 111;
        } else if (instrument >= 112 && instrument <= 119){ //Percussive
            i[0] = 112;
            i[1] = 119;
        } else { //120-127 Sound Effects
            i[0] = 120;
            i[1] = 127;
        }
        return i;
    }
    
    /**
     * bewertet die Takte, entfernt unpassende/falsche Takte
     * @param mpd die bisherigen Takte
     * @return passende Takte
     */
    private MIDIPartData gradeBeats(MIDIPartData mpd){
        ArrayList<MultiBeat> almb = new ArrayList<>();
        
        DatabaseInterface dbi = new DatabaseInterface(user, pw, url);
        ArrayList<INoteAmount> alina = dbi.getNoteAmountsGroupByNote(category);
        dbi.closeConnection();
        
        PolyphonFitnessFunction pff = new PolyphonFitnessFunction(alina);
        
        for (MultiBeat mb : mpd.getMultiBeats()){ //jeden Takt
            double fit = pff.getFitnessValue(mb);
            if (fit >= fitness){
                almb.add(mb);
            }
        }
        
        MIDIPartData mpdNew = new MIDIPartData(mpd.getInstrument(), null);
        //alle Takte wurden fuer ungenuegend befunden,
        //fange mit den Startmotiven neu an
        if (almb.isEmpty()){
            System.out.println("empty");
            for (int i=0; i<STARTSIZE; i++){
                almb.add(mpd.getMultiBeats().get(i));
            }
        }
        
        mpdNew.setMultiBeat(almb);
        return mpdNew;
    }
    
    /**
     * waehlt zufaellig eine Art aus, wie neue Takte entstehen sollen
     * @param mpd die bisherigen Takte
     * @return alte und neue Takte
     */
    private MIDIPartData createNewBeats(MIDIPartData mpd){
        int min = 0, max = 2;
        int type = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
        max = mpd.getMultiBeats().size()-1;
        int beatID = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
        int beatID2 = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
        while (beatID2 == beatID){
            beatID2 = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
        }
        
        if (type == 0){
            if (Crossover){
                if (mpd.getMultiBeats().size() > 1){
                    MultiBeat[] mpArr = Crossover(mpd.getMultiBeats().get(beatID).clone(), mpd.getMultiBeats().get(beatID2).clone(), false);
                    if (mpArr != null){
                        mpd.addMultiBeat(mpArr[0].clone());
                        mpd.addMultiBeat(mpArr[1].clone());
                    }
                }
            }
        } else if (type == 1){
            if (NPointCrossover){
                if (mpd.getMultiBeats().size() > 1){
                    MultiBeat[] mpArr = CrossoverNPoint(mpd.getMultiBeats().get(beatID).clone(), mpd.getMultiBeats().get(beatID2).clone());
                    if (mpArr != null){
                        mpd.addMultiBeat(mpArr[0].clone());
                        mpd.addMultiBeat(mpArr[1].clone());
                    }
                }
            }
        } else {
            if (Mutation){
                mpd.addMultiBeat(Mutation(mpd.getMultiBeats().get(beatID).clone()));
            }
        }
        //verwende nur Takte aus Grundmotiven
        if (!Crossover && !NPointCrossover && !Mutation){
            mpd.addMultiBeat(mpd.getMultiBeats().get(beatID).clone());
            mpd.addMultiBeat(mpd.getMultiBeats().get(beatID2).clone());
        }
        return mpd;
    }
    
    /**
     * one-point crossover zweier Takte
     * zwei Genome werden jeweils an einer Stelle gebrochen und die
     * entstehenden Teilstücke ausgetauscht
     * (AA, BB => AB, BA)
     * es koennen nur Takte, bei denen beide eine gerade bzw. ungerade Notenanzahl haben, gekreuzt werden
     * @param mb erster urspruenglicher Takt
     * @param mb2 zweiter urspruenglicher Takt
     * @param NPoint true wenn NPointCrossover, false wenn OnePointCrossover
     * @return neue Takte
     */
    private MultiBeat[] Crossover(MultiBeat mb, MultiBeat mb2, boolean NPoint){
        NoteData[][] ndArr = mb.getBeat();
        NoteData[][] ndArr2 = mb2.getBeat();
        NoteData[][] ndFirst, ndSecond;
        int maxPhrases, maxNoteCount, maxNoteCount2;
        MultiBeat[] mbNew = new MultiBeat[2];
        boolean samesamebutdifferent = false;
        
        //maximale Anzahl der Phrasen (Zeilen) bestimmen
        if (ndArr.length > ndArr2.length){
            maxPhrases = ndArr.length;
        } else if (ndArr.length < ndArr2.length) {
            maxPhrases = ndArr2.length;
        } else { // gleiche Anzahl
            samesamebutdifferent = true;
            maxPhrases = ndArr.length;
        }
        
        //maximale Anzahl der Noten pro Phrase bestimmen
        maxNoteCount = ndArr[0].length;
        maxNoteCount2 = ndArr2[0].length;
        
        //pruefen, ob Takt gerade oder ungerade Anzahl an Noten besitzt
        boolean allEven = true, allEven2 = true;
        if (maxNoteCount%2 != 0){
            allEven = false;
        }
        if (maxNoteCount2%2 != 0){
            allEven2 = false;
        }
        
         if ((allEven && !allEven2) || (!allEven && allEven2)){ //ein Takt hat eine gerade Notenanzahl
             return null;
         }
        
        int border1 = -1 /*Grenze der ersten Haelfte im ersten Array, bei gerader Anzahl an Noten*/, 
            border2 = -1 /*Grenze der ersten Haelfte im zweiten Array, bei gerader Anzahl an Noten*/, 
            odd1 = -1 /*Grenze der ersten Haelfte im ersten Array, bei ungerader Anzahl an Noten*/,
            odd2 = -1; /*Grenze der ersten Haelfte im zweiten Array, bei ungerader Anzahl an Noten*/
        
        if (!NPoint){ //Takteilung in Mitte
            border1 = maxNoteCount/2;
            border2 = maxNoteCount2/2;
            odd1 = ((maxNoteCount+1)/2)-1;
            odd2 = ((maxNoteCount2+1)/2)-1;
            
        } else { //Taktteilung zufaellig im Takt
            if (allEven && allEven2){ //beide Takte haben eine gerade Notenanzahl
                if (maxNoteCount > maxNoteCount2){
                    border2 = 1 + (int)(Math.random() * ((maxNoteCount2 -1 - 1) + 1)); //zufaelliger Wert zwischen min und max
                    border1 = border2 + ((maxNoteCount - maxNoteCount2)/2);
                } else if (maxNoteCount < maxNoteCount2){
                    border1 = 1 + (int)(Math.random() * ((maxNoteCount -1 - 1) + 1)); //zufaelliger Wert zwischen min und max
                    border2 = border1 + ((maxNoteCount2 - maxNoteCount)/2);
                } else { //beide gleich lang => teile an selber Stelle
                    border1 = 1 + (int)(Math.random() * ((maxNoteCount -1 - 1) + 1)); //zufaelliger Wert zwischen min und max
                    border2 = border1;
                }
                              
            } else { //beide Takte haben eine ungerade Notenanzahl
                if (maxNoteCount > maxNoteCount2){
                    odd2 = 1 + (int)(Math.random() * ((maxNoteCount2 -1 - 1) + 1)); //zufaelliger Wert zwischen min und max
                    odd1 = odd2 + maxNoteCount - ((maxNoteCount + maxNoteCount2)/2);
                } else if (maxNoteCount < maxNoteCount2){
                    odd1 = 1 + (int)(Math.random() * ((maxNoteCount -1 - 1) + 1)); //zufaelliger Wert zwischen min und max
                    odd2 = odd1 + maxNoteCount2 - ((maxNoteCount + maxNoteCount2)/2);
                } else { //beide gleich lang => teile an selber Stelle
                    odd1 = 1 + (int)(Math.random() * ((maxNoteCount -1 - 1) + 1)); //zufaelliger Wert zwischen min und max
                    odd2 = odd1;
                }
            }            
        }
        
        if (allEven && allEven2){ //beide Takte bestehen nur aus gerader Anzahl von Noten
            int noteCount = (maxNoteCount + maxNoteCount2)/2;
            ndFirst = new NoteData[maxPhrases][noteCount];
            ndSecond = new NoteData[maxPhrases][noteCount];
            
            //erste Haelfte von 1 kopieren
            for (int i=0; i<ndArr.length; i++){
                for (int j=0; j<border1; j++){
                    ndFirst[i][j] = ndArr[i][j].clone();
                }
            }
            //erste Haelfte von 2 kopieren
            for (int i=0; i<ndArr2.length; i++){
                for (int j=0; j<border2; j++){
                    ndSecond[i][j] = ndArr2[i][j].clone();
                }
            }
            //zweite Haelfte von 1 kopieren
            int otherj;
            for (int i=0; i<ndArr.length; i++){
                otherj = border2;
                for (int j=border1; j<ndArr[i].length; j++){
                    ndSecond[i][otherj] = ndArr[i][j].clone();
                    otherj++;
                }
            }
            //zweite Haelfte von 2 kopieren
            for (int i=0; i<ndArr2.length; i++){
                otherj = border1;
                for (int j=border2; j<ndArr2[i].length; j++){
                    ndFirst[i][otherj] = ndArr2[i][j].clone();
                    otherj++;
                }
            }

        } else { //beide Takte bestehen aus ungerader Anzahl von Noten
            int noteCount = (maxNoteCount + maxNoteCount2)/2;
            ndFirst = new NoteData[maxPhrases][noteCount];
            ndSecond = new NoteData[maxPhrases][noteCount];
            
            //erste Haelfte von 1 kopieren
            for (int i=0; i<ndArr.length; i++){
                for (int j=0; j<odd1; j++){
                    ndFirst[i][j] = ndArr[i][j].clone();
                }
            }
            //erste Haelfte von 2 kopieren
            for (int i=0; i<ndArr2.length; i++){
                for (int j=0; j<odd2; j++){
                    ndSecond[i][j] = ndArr2[i][j].clone();
                }
            }
            //zweite Haelfte von 1 kopieren
            int otherj;
            for (int i=0; i<ndArr.length; i++){
                otherj = odd2;
                for (int j=odd1; j<ndArr[i].length; j++){
                    ndSecond[i][otherj] = ndArr[i][j].clone();
                    otherj++;
                }
            }
            //zweite Haelfte von 2 kopieren
            for (int i=0; i<ndArr2.length; i++){
                otherj = odd1;
                for (int j=odd2; j<ndArr2[i].length; j++){
                    ndFirst[i][otherj] = ndArr2[i][j].clone();
                    otherj++;
                }
            }
        }
        
        //alle null-Werte mit Pausen ersetzen
        if (!samesamebutdifferent){
            for (int i=0; i<ndFirst.length; i++){
                for (int j=0; j<ndFirst[i].length; j++){
                    if (ndFirst[i][j] == null){
                        ndFirst[i][j] = new NoteData(0.0, 0.0, Integer.MIN_VALUE);
                    }
                    if (ndSecond[i][j] == null){
                        ndSecond[i][j] = new NoteData(0.0, 0.0, Integer.MIN_VALUE);
                    }
                }
            }
        }
        
        //pruefen, ob Takt noch korrekte Taktlaenge besitzt
        //wenn zu kurz => ok, wenn zu lang => verwerfen
        boolean tooLong = false;
        for (int i=0; i<ndFirst.length; i++){
            int sum = 0;
            for (int j=0; j<ndFirst[i].length; j++){
                sum += ndFirst[i][j].getDuration();
            }
            if (sum > numerator){
                tooLong = true;
                break;
            }
        }
        if (tooLong){
            return null;
        }
        for (int i=0; i<ndSecond.length; i++){
            int sum = 0;
            for (int j=0; j<ndSecond[i].length; j++){
                sum += ndSecond[i][j].getDuration();
            }
            if (sum > numerator){
                tooLong = true;
                break;
            }
        }
        if (tooLong){
            return null;
        }

        mbNew[0] = correctMultiBeat(new MultiBeat(ndFirst));
        mbNew[1] = correctMultiBeat(new MultiBeat(ndSecond));
        mbNew[0].setInstrument(mb.getInstrument());
        mbNew[1].setInstrument(mb2.getInstrument());
        mbNew[0].setKey(mb.getKey());
        mbNew[1].setKey(mb2.getKey());
        mbNew[0].setMajor(mb.isMajor());
        mbNew[1].setMajor(mb2.isMajor());
        
        return mbNew;
    }
    
    /**
     * n-point crossover zweier Takte
     * zwei Genome werden jeweils an mehreren Stelle gebrochen und die
     * entstehenden Teilstücke ausgetauscht
     * (AAAA, BBBB => AB, BA, ABAB, BABA, ABBB, BAAA, AABA, ...)
     * es koennen nur Takte, bei denen beide eine gerade bzw. ungerade Notenanzahl haben, gekreuzt werden
     * @param mb erster urspruenglicher Takt
     * @param mb2 zweiter urspruenglicher Takt
     * @return neue Takte
     */
    private MultiBeat[] CrossoverNPoint(MultiBeat mb, MultiBeat mb2){
        NoteData[][] ndArr1 = mb.getBeat();
        MultiBeat[] mbArr;
        //erster Takt soll der gerade sein, wenn einer gerade und einer ungerade ist
        if (ndArr1[0].length%2 == 0){
            mbArr = Crossover(mb, mb2, true);
        } else {
            mbArr = Crossover(mb2, mb, true);
        }
        return mbArr;
    }
    
    /**
     * Mutation eines Takts
     * - transponieren (um -6 bis 6)
     * - vertauschen der Pitches
     * - nach Pitches aufsteigend sortieren
     * - nach Pitches absteigend sortieren
     * - umdrehen (Reversion/Krebs)
     * - Intervallrichtungsaenderung (Inversion/Spiegel)
     * @param mb urspruenglicher Takt
     * @return neue Takt
     */
    private MultiBeat Mutation(MultiBeat mb){
        //TODO: Mutation
        int min = 1, max = 6;
        int numberOfChanges = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
        MultiBeat m = mb.clone();
        for (int i=0; i<numberOfChanges; i++){
            int type = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
            switch (type){
                case 1: //transponieren (um -6 bis 6)
                    m = transposeBeat(m.clone());
                    break;
                case 2: //vertauschen der Pitches
                    m = shuffleBeat(m.clone());
                    break;
                case 3: //nach Pitches aufsteigend sortieren
                    m = sortBeatAscOrDesc(m.clone(), true);
                    break;
                case 4: //nach Pitches absteigend sortieren
                    m = sortBeatAscOrDesc(m.clone(), false);
                    break;
                case 5: //umdrehen (Reversion/Krebs)
                    m = revertBeat(m.clone());
                    break;
                case 6: //Intervallrichtungsaenderung (Inversion/Spiegel)
                    m = invertBeat(m.clone());
            }
        }
        return m;
    }
    
    /**
     * transponiert den Takt zufaellig um -6 bis +6 Halbtonschritte
     * @param mb ein Takt
     * @return transponierter Takt
     */
    private MultiBeat transposeBeat(MultiBeat mb){
        NoteData[][] nd = mb.getBeat();
        int min = 1, max = 12;
        int Steps = min + (int)(Math.random() * ((max - min) + 1)); //zufaelliger Wert zwischen min und max
        Steps -= max;
        
        for (int i=0; i<nd.length; i++){
            for (int j=0; j<nd[i].length; j++){
                if (nd[i][j].getPitch() != Integer.MIN_VALUE){
                    nd[i][j].setPitch(nd[i][j].getPitch()+Steps);
                }
            }
        }
        mb.setBeat(nd);
        return mb;
    }
    
    /**
     * vertauscht zufaellig die Reihenfolge der Noten im Takt
     * @param mb ein Takt
     * @return Takt mit durchgemischten Noten
     */
    private MultiBeat shuffleBeat(MultiBeat mb){
        NoteData[][] nd = mb.getBeat();
        int[] iArr = new int[nd[0].length];
        for (int i=0; i<iArr.length; i++){
            iArr[i] = i;
        }
        // Implementing Fisher–Yates Shuffle
        Random rnd = new Random();
        for (int i = iArr.length - 1; i > 0; i--)
        {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            int a = iArr[index];
            iArr[index] = iArr[i];
            iArr[i] = a;
        }
        
        NoteData[][] shuffled = new NoteData[nd.length][nd[0].length];
        for (int i=0; i<iArr.length; i++){
            for (int j=0; j<nd.length; j++){
                shuffled[j][i] = nd[j][iArr[i]].clone();
            }
        }
        mb.setBeat(shuffled);
        return mb;
    }
    
    /**
     * sortiert die Noten aufsteigend bzw. absteigend
     * @param mb ein Takt
     * @param Asc true wenn aufsteigend, false wenn absteigend
     * @return Takt aufsteigend bzw. absteigend sortiert
     */
    private MultiBeat sortBeatAscOrDesc(MultiBeat mb, boolean Asc){
        NoteData[][] nd = mb.getBeat();
        
        int len = nd[0].length;
        int j;
        NoteData tmp;
        
        for(int i=0; i < len; i++){
            j = i;
            for(int k = i; k < len; k++){
                if (Asc){
                    if(nd[0][i].getPitch() > nd[0][k].getPitch()){
                        j = k;
                    }
                } else {
                    if(nd[0][i].getPitch() < nd[0][k].getPitch()){
                        j = k;
                    }
                }
            }
            for (int x=0; x<nd.length;x++){
                tmp = nd[x][i].clone();
                nd[x][i] = nd[x][j].clone();
                nd[x][j] = tmp.clone();
            }
        }
        
        mb.setBeat(nd);
        return mb;
    }

    /**
     * dreht den Takt um (Krebs)
     * @param mb ein Takt
     * @return umgedrehter Takt
     */
    private MultiBeat revertBeat(MultiBeat mb){
        NoteData[][] nd = mb.getBeat();
        NoteData[][] rev = new NoteData[nd.length][nd[0].length];
        
        for (int i=0; i<nd.length; i++){
            int x = 0;
            for (int j=nd[i].length-1; j>=0; j--){
                rev[i][x] = nd[i][j].clone();
                x++;
            }
        }
        
        mb.setBeat(rev);
        return mb;
    }
    
    /**
     * invertiert den Tankt (Spiegel)
     * @param mb ein Takt
     * @return invertierter Takt
     */
    private MultiBeat invertBeat(MultiBeat mb){
        NoteData[][] nd = mb.getBeat();
        
        for (int i=0; i<nd.length; i++){
            //Intervalle merken
            int[] intervalle = new int[nd[i].length-1];           
            for (int j=1; j<nd[i].length; j++){
                if (nd[i][j].getPitch() != Integer.MIN_VALUE && nd[i][j-1].getPitch() != Integer.MIN_VALUE){
                    int intervall = (nd[i][j].getPitch() - nd[i][j-1].getPitch())* -1;
                    intervalle[j-1] = intervall;
                }else{
                    intervalle[j-1] = 0; //keine Aenderung bei Pause
                }
            }
            //Intervalle anwenden
            for (int j=1; j<nd[i].length; j++){
                if (intervalle[j-1] != 0){
                    nd[i][j].setPitch(nd[i][j-1].getPitch()+intervalle[j-1]);
                }
            }
        }
        
        mb.setBeat(nd);
        return mb;
    }
    
    /**
     * liefert die Anzahl der Takte, die der MIDI-Track benoetigt,
     * um die gewuenschte Laenge zu erreichen
     * @return Anzahl der Takte
     */
    private int getBeatCountForTrack(){
        //Laenge des Tracks in Sekunden / 60 (auf Minuten) * BPM (Viertel pro Minute) / Viertelnoten pro Takt
        double b = (tracklength / 60.0 * tempo / numerator);
        String sd = DecimalFormat.getNumberInstance().format(b);
        if (sd.indexOf(",") == -1){
            return (int)b;
        } else {
            return (int)b+1;
        }
    }
    
    /**
    * transponiert den polyphonen Takt in eine andere Tonart
    * @param mb polyphoner Takt
    * @param oldKey bisherige Tonart (nur Grundton, zB. bei C-Dur nur "C")
    * @param newKey neue Tonart (nur Grundton, zB. bei G-Dur nur "G")
    * @param Steps Anzahl der Halbtonschritte der Aenderung, wenn Steps = 200 => berechne die Halbtonschritte intern
    * @return der transponierte MultiBeat
    */
    private MultiBeat TransposeBeat(MultiBeat mb, String oldKey, String newKey, int Steps) {
        if (Steps == 200){
            Steps = getHalftoneSteps(oldKey, newKey);
        }
      
        //alle Pitches um die Halbtonschritte erhoehen bzw. verringern
        NoteData[][] ndArr = mb.getBeat();
        for (int i=0; i<ndArr.length; i++){
            for (int j=0; j<ndArr[0].length; j++){
                if (ndArr[i][j].getPitch() != Integer.MIN_VALUE){ //Pausen bleiben Pausen
                  ndArr[i][j].setPitch(ndArr[i][j].getPitch()+Steps);
                }
            }
        }
        MultiBeat mbNew = new MultiBeat(ndArr);
        mbNew.setInstrument(mb.getInstrument());
        mbNew.setKey(newKey);
        mbNew.setMajor(major);
        return mbNew;
    }

    /**
    * gibt die Anzahl der Halbtoene zurueck um von der Ursprungstonart in die Zieltonart zu gelangen
    * der geringere Unterschied wird verwendet (man kann auf beide Seiten transponieren, nur die Oktave aendert sich)
    * @param From Ursprungstonart
    * @param To Zieltonart
    * @return Verschiebung in Halbtoenen
    */
    private int getHalftoneSteps(String From, String To) {
        int StepOld = 0;
        int StepNew = 0;
        int x1, x2;

        From = FormatKeys(From);
        To = FormatKeys(To);

        for (int i=0; i<transposeStep.length; i++) {
           if (transposeStep[i].equalsIgnoreCase(From)) {
              StepOld = i;
           }
           if (transposeStep[i].equalsIgnoreCase(To)) {
              StepNew = i;
           }
        }
        x1 = (StepOld - StepNew);
        x2 = (StepNew - StepOld);

        if (x1 < 0){
           x1 += 12;
        }else{
           x1 *= -1;
        }
        if (x2 < 0){
           x2 += 12;
        }else{
           x1 *= -1;
        }
        if (Math.abs(x1) < Math.abs(x2)) {
           return x1;
        }else{
           return x2;
        }
    }

    /**
    * replace key by MIDI-key-name
    * @param s key to check
    * @return the correspondent key or the key passed through
    */
    private String FormatKeys(String s) {
        //{"C","C#","D","Eb","E","F","F#","G","Ab","A","Bb","B"};
        switch (s) {
           case "A#":
              s = "Bb";
              break;
           case "D#":
              s = "Eb";
              break;
           case "G#":
              s = "Ab";
              break;
        }
        return s;
    }
}