import java.io.*;
import java.util.*;

/**
 * Fußnoten-Sortierprogramm mit Ausrichtung auf eine möglichst hohe Effizienz
 * und Skalierbarkeit sowie einem geringen Speicherverbrauch.
 * <p>
 * Zugunsten der Verarbeitungsgeschwindigkeit wurde auf die Nutzung von
 * regulären Ausdrücken (<code>Pattern</code>/<code>Matcher</code>),
 * sowie des <code>PrintWriter</code>s verzichtet.<br>
 * Zugunsten des Speicherverbrauchs arbeitet das Programm Stream-basiert,
 * was jedoch die re-nummerierung der im Text befindlichen Verweise in
 * der Reihenfolge der Verweisziele aus dem Fußnotenabschnitt ohne
 * zweiten Durchlauf unmöglich macht. Des Weiteren wurde auf die Verwendung
 * eines <code>Comparator</code>s verzichtet, der die Vorhaltung aller
 * Verweisziele im Speicher bedingt hätte um die Sortierung durchführen zu
 * können.<br>
 * Nachteil der Optimierungen ist ein deutlich längerer Code - die Klassen
 * <code>FootnoteFinder</code> und <code>Footnotes</code>, sowie die vielen
 * <code>writer.write()</code> würde es ohne diese Optimierungen nicht geben.
 * <p>
 * Die Formatierung des Codes, die Stern-Imports, das fehlende
 * Exception-Handling, sowie die Verwendung innerer Klassen dienen
 * ausschließlich der möglichst kompakten Umsetzung der gestellten Aufgabe
 * und kann nicht als Beispiel guten Codes dienen.
 * <p>
 * Dieser Code wurde mit Eclipse 3.4 / Java 6 unter Kubuntu 8.04 erstellt. :-)
 *
 * @author Oliver Siegmar
 */
public class FootnoteProcessor {

    /** Fußnotenmarkierung **/
    private static final String FOOT_MARKER = "@footnote:";

    /** Zeichensatz der Quelldatei **/
    private static final String CHARSET = "ISO-8859-15";

    /** Betriebssystemspezifisches Zeilenende **/
    private static final String NEWLINE = System.getProperty("line.separator");

    /** Zeichen, mit dem die Fußnoten begonnen werden **/
    private static final char FOOTNOTE_OPEN = '[';

    /** Zeichen, mit dem die Fußnoten geschlossen werden **/
    private static final char FOOTNOTE_CLOSE = ']';

    /**
     * Speicher für die neu nummerierten Fußnoten
     * (Key = alte Nummer, Value = neue Nummer)
     **/
    private final Map<Integer, Integer> noteMap =
        new HashMap<Integer, Integer>();

    /** Writer für die Ausgabe des re-nummerierten Textes **/
    private final Writer writer;

    public static void main(final String[] args) throws IOException {
        if (args.length == 0) {
            System.err.println("No file specified. " +
                "Usage: FootnoteProcessor input.txt > output.txt");
            System.exit(1);
        }
        new FootnoteProcessor().processFile(new File(args[0]));
    }

    private FootnoteProcessor() throws IOException {
        writer = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    /**
     * Einstiegsmethode zur Verarbeitung der Daten.
     *
     * @param file die zu verarbeitende Quelldatei.
     * @throws IOException tritt bei Lese- oder Schreibfehlern auf.
     */
    private void processFile(final File file) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(
            new FileInputStream(file), CHARSET));
        Scanner scanner = new BodyScanner();
        for (String line; (line = br.readLine()) != null;) {
            if (FOOT_MARKER.equals(line)) {
                scanner = new FootScanner();
                writer.write(FOOT_MARKER);
                writer.write(NEWLINE);
            } else {
                scanner.process(line);
            }
        }

        br.close();
        writer.close();
    }

    /**
     * Klasse zur effizienten Ermittlung der Position von Fußnoten
     */
    private class FootnoteFinder {

        /** Zu untersuchende Zeile **/
        private final char[] ca;

        /** Startposition des Fußnotenmarkers ([) **/
        private int start;

        /** Endposition des Fußnotenmarkers (]) **/
        private int end;

        /**
         * Initialisierung.
         *
         * @param line die zu untersuchende Zeile.
         */
        public FootnoteFinder(final String line) {
            ca = line.toCharArray();
        }

        /**
         * Sucht nach der nächsten Fußnote
         *
         * @return Start- und Endposition der Fußnote, oder <code>null</code>,
         *         wenn keine (weitere) Fußnote gefunden wurde.
         */
        private int[] find() {
            boolean open = false;
            int[] ret = null;
            for (int i = end; i < ca.length; i++) {
                if (!open) {
                    if (ca[i] == FOOTNOTE_OPEN) {
                        start = i + 1;
                        open = true;
                    }
                } else {
                    if (ca[i] == FOOTNOTE_CLOSE) {
                        if (i > start) {
                            ret = new int[] { start, i };
                        }
                        end = i + 1;
                        break;
                    } else if (ca[i] < '0' || ca[i] > '9') {
                        break;
                    }
                }
            }

            return ret;
        }
    }

    /** Interface für den zeilenbasierten Fußnotenscanner **/
    private interface Scanner {
        /**
         * Verarbeitet eine Zeile der Quelldatei.
         * @param line eingelesene Zeile der Quelldatei.
         * @throws IOException tritt bei einem Schreibfehler auf.
         */
        void process(String line) throws IOException;
    }

    /** Von den Scannerimplementierungen gemeinsam genutzte Funktionalität **/
    private abstract class AbstractScanner implements Scanner {
        public void process(final String line) throws IOException {
            final FootnoteFinder matcher = new FootnoteFinder(line);
            for (int[] matches; (matches = matcher.find()) != null;) {
                process(line, matches[0], matches[1]);
            }
            postProcess(line);
        }

        /**
         * Diese Methode wird für jeden Treffer einer Fußnote aufgerufen.
         *
         * @param line die zu verarbeitende Zeile.
         * @param start Startposition der Fußnote.
         * @param end Endposition der Fußnote.
         * @throws IOException tritt bei einem Schreibfehler auf.
         */
        abstract void process(String line, int start, int end)
        throws IOException;

        /**
         * Diese Methode wird aufgerufen, sobald alle Treffer für eine
         * Zeile abgearbeitet sind.
         *
         * @param line die zu verarbeitende Zeile.
         * @throws IOException tritt bei einem Schreibfehler auf.
         */
        void postProcess(final String line) throws IOException {}
    }

    /** Scannerimplementierung, welche die Verweise im Text untersucht **/
    private class BodyScanner extends AbstractScanner {
        private int lastNumber = 0;
        private int lastEnd = 0;

        @Override
        public void process(final String line, final int begin, final int end)
        throws IOException {
            final Integer number = new Integer(line.substring(begin, end));

            Integer remap = noteMap.get(number);
            if (remap == null) {
                remap = ++lastNumber;
                noteMap.put(number, remap);
            }

            writer.write(line, lastEnd, (begin - lastEnd));
            writer.write(Integer.toString(remap));

            lastEnd = end;
        }

        @Override
        public void postProcess(final String line) throws IOException {
            writer.write(line, lastEnd, (line.length() - lastEnd));
            writer.write(NEWLINE);
            lastEnd = 0;
        }
    }

    /** Scannerimplementierung, welche die Verweisziele untersucht **/
    private class FootScanner extends AbstractScanner {
        private final Footnotes footnotes = new Footnotes();

        @Override
        public void process(final String line, final int begin, final int end)
        throws IOException {
            final Integer number = new Integer(line.substring(begin, end));
            final String text = line.substring(end + 2);
            final Integer remap = noteMap.get(number);
            footnotes.add(remap, text);
        }
    }

    /** Speicher-, Sortier- und Ausgabelogik für Verweisziele **/
    private class Footnotes {
        /** Zwischenspeicher für Fußnoten, die noch nicht ausgegeben wurden **/
        private final Map<Integer, String> footnotes =
            new HashMap<Integer, String>();

        /** Ziffer der Fußnote, die als nächstes ausgegeben werden muss **/
        private Integer nextNumber = 1;

        /**
         * Fügt dem Zwischenspeicher eine Fußnote hinzu. Prüft anschließend,
         * ob die hinzugefügte Fußnote (sowie evtl. bereits gespeicherte)
         * Fußnoten ausgegeben werden können.
         *
         * @param number Nummer der hinzuzufügenden Fußnote.
         * @param footnote Text der hinzuzufügenden Fußnote.
         * @throws IOException tritt bei einem Schreibfehler auf.
         */
        public void add(final Integer number, final String footnote)
        throws IOException {
            footnotes.put(number, footnote);
            if (number.equals(nextNumber)) {
                printFootnotes();
            }
        }

        /**
         * Gibt alle im Zwischenspeicher befindlichen Fußnoten in
         * sortierter Reihenfolge aus. Bricht ab, wenn der Zwischenspeicher
         * noch keine Fußnote der nächsten Nummer findet.
         *
         * @throws IOException tritt bei einem Schreibfehler auf.
         */
        private void printFootnotes() throws IOException {
            String nextFootnote;
            while ((nextFootnote = footnotes.get(nextNumber)) != null) {
                writer.write(FOOTNOTE_OPEN);
                writer.write(nextNumber.toString());
                writer.write(FOOTNOTE_CLOSE);
                writer.write(" ");
                writer.write(nextFootnote);
                writer.write(NEWLINE);
                nextNumber++;
                footnotes.remove(nextFootnote);
            }
        }
    }

}