package de.duehl.basics.text;

/*
 * Copyright 2016 Christian Dühl. All rights reserved.
 *
 * This program is free software. You can redistribute it and/or
 * modify it under the same terms as perl:
 *
 * general:  http://dev.perl.org/licenses/
 * GPL:      http://dev.perl.org/licenses/gpl1.html
 * artistic: http://dev.perl.org/licenses/artistic.html
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Diese Klasse stellt eine Menge von Position eines in einem Text gefundener Strings dar.
 *
 * @version 1.01     2015-11-27
 * @author Christian Dühl
 */

public class TextPositions {

    /** Liste mit allen textpositionen. */
    private final List<TextPosition> positions;

    /** Konstruktor. */
    public TextPositions() {
        positions = new ArrayList<>();
    }

    /** Fügt die übergebene Textposition hinzu. */
    public void add(final TextPosition textPosition) {
        positions.add(textPosition);
    }

    /** Sortiert die Textpositionen. */
    public void sort() {
        Collections.sort(positions);
    }

    /** Liefert die Textposition am angegebene Index (0-basiert) zurück. */
    public TextPosition get(final int index) {
        return positions.get(index);
    }

    /** Diese Methode verschmilzt überlappende Positionen. */
    public void removeOverlapping() {
        sort();
        boolean melting = true;
        while (melting) {
            melting = removeOverlappingOneTime();

            /*
             * Die Positionen sind an dieser Stelle in der Regel unsortiert, da die verschmolzenen
             * Positionen zum einen in sich unsortiert sind und zum anderen ans Ende der Liste
             * angefügt wurden. Daher wird erneut sortiert, wenn verschmolzen wurde:
             */
            if (melting) {
                sort();
            }
        }
    }

    /**
     * Diese Methode verschmilzt überlappende Positionen. Da hierbei mehrere sich wiederum
     * überlappende Positionen erzeugt werden können, muss dies solange geschehen, bis nichts mehr
     * verschmolzen wird.
     *
     * @return Wahrheitswert, true genau dann, wenn etwas verschmolzen wurde.
     */
    private boolean removeOverlappingOneTime() {
        Set<Integer> indicesToRemove = new HashSet<>();
        List<TextPosition> meltedPositionsToAdd = new ArrayList<>();
        boolean melting = findMeltingIndicesAndGenereateMeltedPositions(indicesToRemove,
                meltedPositionsToAdd);

        removeOldPositionsThatWereMelted(indicesToRemove);

        addAllMeltedPositions(meltedPositionsToAdd);

        return melting;
    }

    /**
     * Findet Indizes von zu verschmelzenden Textpositionen und bildet deren verschmolzene
     * Textpositionen.
     *
     * @param indicesToRemove
     *            Hier werden die Indices von Textpositionen abgelegt, die zu neuen Textpositionen
     *            verschmolzen werden.
     * @param meltedPositionsToAdd
     *            Hier werden alle neu erzeugten verschmolzenen Positionen abgelegt.
     * @return Wahrheitswert, true genau dann, wenn etwas verschmolzen wurde.
     */
    private boolean findMeltingIndicesAndGenereateMeltedPositions(
            final Set<Integer> indicesToRemove, final List<TextPosition> meltedPositionsToAdd) {

        for (int i = 0; i < positions.size(); ++i) {
            boolean melting = false;
            TextPosition pos1 = positions.get(i);
            for (int j = i+1; j < positions.size(); ++j) {
                TextPosition pos2 = positions.get(j);
                if (pos1.overlapp(pos2)) {
                    TextPosition meltedPosition = pos1.meltWith(pos2);
                    indicesToRemove.add(i);
                    indicesToRemove.add(j);
                    meltedPositionsToAdd.add(meltedPosition);
                    melting = true;
                }
            }
            if (melting) {
                return true;
                /*
                 * Wenn wir alle Durchgänge machen, dann kann es sein, dass wir genauso viele
                 * verschmolzene neue Objekte erzeugen (etwa wenn wir [0,5), [0,5), [0,5)
                 * reinstecken) und damit in einer Endlosschleife landen.
                 */
            }
        }

        return false;
    }

    /**
     * Entfernt alle Positionen, die zu anderen Positionen verschmolzen wurden.          <br><br><i>
     *
     * Da wir beim Löschen von hinten nach vorne vorgehen wollen, wird die Menge in eine Liste
     * überführt, sortiert und umgedreht, bevor von vorn nach hinten alle Textpositionen am
     * angegebenen Index entfernt werden.                                                       </i>
     *
     * @param indicesToRemove
     *            Menge der zu entfernenden Indices von Textpositionen.
     */
    private void removeOldPositionsThatWereMelted(final Set<Integer> indicesToRemove) {
        List<Integer> sortedIndicesToRemove = new ArrayList<>();
        sortedIndicesToRemove.addAll(indicesToRemove);
        Collections.sort(sortedIndicesToRemove);
        Collections.reverse(sortedIndicesToRemove);
        for (int i : sortedIndicesToRemove) {
            positions.remove(i);
        }
    }

    /** Fügt alle neu erzeugten verschmolzenen Positionen zur Liste aller Positionen hinzu. */
    private void addAllMeltedPositions(final List<TextPosition> positionsToAdd) {
        positions.addAll(positionsToAdd);
    }

    /**
     * Returns the number of elements in this list. If this list contains more than
     * Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
     */
    public int size() {
        return positions.size();
    }

}
