import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;

import javax.xml.parsers.DocumentBuilderFactory;

import org.w3c.dom.*;


/**
 * Program to print sequences as defined by XML files provided.
 *
 * Each command line argument is the name of an XML file. Here's an example:
 *
 * <pre>&lt;?xml version="1.0" encoding="utf-8"?&gt;
 *&lt;limit end="100"&gt;
 *  &lt;combined-sequence&gt;
 *      &lt;base-sequence&gt;
 *          &lt;number-sequence /&gt;
 *      &lt;/base-sequence&gt;
 *      &lt;number-sequence stepSize="3" name="Fizz" /&gt;
 *      &lt;number-sequence stepSize="5" name="Buzz" /&gt;
 *  &lt;/combined-sequence&gt;
 *&lt;/limit&gt;</pre>
 *
 * @author Jeremy
 */
public class PrintSequence {
    /**
     * A generated iterable sequence.
     *
     * IDs are returned in ascending order.
     *
     * Since the sequence is generated, it is immutable--attempts to modify
     * the sequence will throw a runtime exception.
     *
     * @author Jeremy
     */
    private static interface Sequence extends Iterable<Sequence.Entry> {
        /**
         * An id/value pair returned by a Sequence.
         * @author Jeremy
         */
        public static class Entry {
            private final int id;
            private final String name;

            /**
             * Constructs an entry with the given ID.
             * @param id ID of the entry to create
             */
            private Entry(final int id) {
                this.id = id;
                this.name = null;
            }

            /**
             * Constructs an entry with the given ID and name.
             * @param id ID of the entry to create
             * @param name name of the entry to create
             */
            private Entry(final int id, final String name) {
                this.id = id;
                this.name = name;
            }

            /**
             * Returns the ID of this entry.
             * @return ID of this sequence entry
             */
            public int getId() {
                return id;
            }
            /**
             * Returns the name of this entry.
             * @return name associated with this entry
             */
            public String getName() {
                return name == null ? Integer.toString(id) : name;
            }
        }
    }

    /**
     * A sequence of multiples of a specified integer, from a specified start
     * point through a specified end point, and with a specified name.
     *
     * @author Jeremy
     */
    private static class NumberSequence implements Sequence {
        private final int start, end, stepSize;
        private final String name;

        private class EntryIterator implements Iterator<Entry> {
            private int pos = start - 1;

            private EntryIterator() {
                pos = start - 1;
                pos -= pos % stepSize;
            }

            public boolean hasNext() {
                return end < 0 || pos + stepSize <= end;
            }

            public Sequence.Entry next() {
                return hasNext() ? new Entry(pos = pos + stepSize, name) : null;
            }

            public void remove() {
                throw new RuntimeException("No.");
            }
        }

        /**
         * Constructs a sequence of multiples of stepSize beginning at start
         * and running through end. Each entry's name will be set to the value
         * in name.
         * @param start start point for the sequence
         * @param end end point for the sequence
         * @param stepSize difference between IDs of each consecutive sequence entry
         * @param name name given to each sequence entry
         */
        private NumberSequence(final int start, final int end,
                final int stepSize, final String name) {
            this.start = start;
            this.end = end;
            this.stepSize = stepSize;
            this.name = name;
        }

        /**
         * Constructs a sequence of multiples of stepSize beginning at start
         * and running through end. Each entry's name will be the string form
         * of its ID.
         * @param start start point for the sequence
         * @param end end point for the sequence
         * @param stepSize difference between IDs of each consecutive sequence entry
         */
        private NumberSequence(final int start, final int end,
                final int stepSize) {
            this.start = start;
            this.end = end;
            this.stepSize = stepSize;
            this.name = null;
        }

        /**
         * Constructs a sequence of integers beginning at start and running
         * through end. Each entry's name will be the string form of its ID.
         * @param start start point for the sequence
         * @param end end point for the sequence
         */
        private NumberSequence(final int start, final int end) {
            this.start = start;
            this.end = end;
            this.stepSize = 1;
            this.name = null;
        }

        public Iterator<Entry> iterator() {
            return new EntryIterator();
        }
    }

    /**
     * A sequence generated by combining other sequences.
     *
     * This will return elements with IDs generated from a given base
     * sequence. If any entries in the other specified sequences have a
     * matching ID, their names will be concatenated to generate the returned
     * entry's name. Otherwise, the returned entry will use the name given by
     * the base sequence.
     * @author Jeremy
     */
    private static class CombinedSequence implements Sequence {
        private final Sequence baseSequence;
        private final Sequence[] otherSequences;

        private class EntryIterator implements Iterator<Entry> {
            Iterator<Entry> pos = baseSequence.iterator();
            final Iterator<Entry>[] otherPos =
                new Iterator[otherSequences.length];
            final Entry[] otherEntries =
                new Entry[otherSequences.length];

            private EntryIterator() {
                for(int i=0; i<otherPos.length; ++i) {
                    otherPos[i] = otherSequences[i].iterator();
                    otherEntries[i] = otherPos[i].next();
                }
            }

            public boolean hasNext() {
                return pos.hasNext();
            }

            public Entry next() {
                if(pos.hasNext()) {
                    final Entry baseEnt = pos.next();
                    String name = "";
                    for(int i=0; i<otherPos.length; ++i) {
                        while(baseEnt.getId() > otherEntries[i].getId() && otherPos[i].hasNext())
                            otherEntries[i] = otherPos[i].next();
                        if(baseEnt.getId() == otherEntries[i].getId())
                            name += otherEntries[i].getName();
                    }
                    return new Entry(baseEnt.getId(), name.length() == 0 ?
                            baseEnt.getName() : name);
                }
                return null;
            }

            public void remove() {
                throw new RuntimeException("No.");
            }
        }

        /**
         * Constructs a sequence generated by combining baseSequence and
         * otherSequence. The returned instance will use IDs from baseSequence
         * and names from otherSequences, falling back to the name from
         * baseSequence when none of the sequences in otherSequences contain
         * matching IDs.
         * @param baseSequence base sequence
         * @param otherSequences other sequences to use to generate names
         */
        private CombinedSequence(final Sequence baseSequence,
                final Sequence... otherSequences) {
            this.baseSequence = baseSequence;
            this.otherSequences = otherSequences;
        }

        public Iterator<Entry> iterator() {
            return new EntryIterator();
        }
    }

    /**
     * A sequence terminating on or before the specified endpoint.
     *
     * This generates an input sequence as its output, except that this
     * truncates the sequence as specified.
     *
     * @author Jeremy
     */
    private static class LimitedSequence implements Sequence {
        private final Sequence sequence;
        private final int end;

        private class EntryIterator implements Iterator<Entry> {
            private Iterator<Entry> pos = sequence.iterator();
            private Entry lastEntry = pos.next();

            public boolean hasNext() {
                return lastEntry != null && lastEntry.getId() <= end;
            }

            public Entry next() {
                if(hasNext()) {
                    final Entry rv = lastEntry;
                    lastEntry = pos.next();
                    return rv;
                }
                return null;
            }

            public void remove() {
                pos.remove();
            }
        }

        private LimitedSequence(final Sequence sequence, final int end) {
            this.sequence = sequence;
            this.end = end;
        }

        public Iterator<Entry> iterator() {
            return new EntryIterator();
        }
    }

    private static class AttributeList {
        private final NamedNodeMap attributes;

        private AttributeList(final NamedNodeMap attributes) {
            this.attributes = attributes;
        }

        private boolean has(final String key) {
            return attributes.getNamedItem(key) != null;
        }

        private String getString(final String key) {
            try {
                return attributes.getNamedItem(key).getTextContent();
            } catch (Exception e) {
                throw new IllegalArgumentException(String.format(
                        "Required attribute \"%s\" not found.", key), e);
            }
        }

        private int getInteger(final String key) {
            try {
                return Integer.parseInt(getString(key));
            } catch (NumberFormatException e) {
                throw new IllegalArgumentException(String.format(
                        "Attribute \"%s\" must have an integer value.", key), e);
            }
        }
    }

    /**
     * Generates a sequence from the provided XML DOM
     * @param doc XML document from which to generate a sequence
     * @return sequence generated from XML element provided
     */
    private static Sequence loadSequence(final Node element) {
        final AttributeList attributes =
            new AttributeList(element.getAttributes());
        if(element.getNodeName().equals("number-sequence") ||
                element.getNodeName().equals("sequence-of-multiples")) {
            return new NumberSequence(
                    attributes.has("start") ? attributes.getInteger("start") : 1,
                    attributes.has("end") ? attributes.getInteger("end") : -1,
                    attributes.has("stepSize") ? attributes.getInteger("stepSize") : 1,
                    attributes.has("name") ? attributes.getString("name") : null);
        } else if(element.getNodeName().equals("combined-sequence")) {
            Sequence baseSequence = null;
            ArrayList<Sequence> otherSequences = new ArrayList<Sequence>();
            final NodeList children = element.getChildNodes();
            for(int i=0; i < children.getLength(); ++i) {
                final Node child = children.item(i);
                if(child.getNodeName().equals("base-sequence")) {
                    final NodeList baseChildren = child.getChildNodes();
                    for(int j=0; j < baseChildren.getLength(); ++j) {
                        if(baseChildren.item(j).getNodeType() == Node.ELEMENT_NODE)
                            baseSequence = loadSequence(baseChildren.item(i));
                    }
                } else if(child.getNodeType() == Node.ELEMENT_NODE) {
                    otherSequences.add(loadSequence(child));
                }
            }
            if(baseSequence == null)
                throw new IllegalArgumentException("\"combined-sequence\" requires base sequence!");
            final Sequence[] otherArr = new Sequence[otherSequences.size()];
            return new CombinedSequence(baseSequence,
                    otherSequences.toArray(otherArr));
        } else if(element.getNodeName() == "limit") {
            final NodeList children = element.getChildNodes();
            Sequence innerSequence = null;
            for(int i=0; i < children.getLength(); ++i) {
                final Node child = children.item(i);
                if(child.getNodeType() == Node.ELEMENT_NODE)
                    innerSequence = loadSequence(child);
            }
            if(innerSequence == null)
                throw new IllegalArgumentException("\"limit\" requires inner sequence!");
            return new LimitedSequence(innerSequence, attributes.getInteger("end"));
        }
        throw new IllegalArgumentException(String.format("Unknown XML element \"%s\" in config.", element.getNodeName()));
    }

    /**
     * Generates a sequence from the provided XML input stream
     * @param xml XML description of sequence to generate
     * @return sequence generated from XML provided
     */
    private static Sequence loadSequence(final InputStream xml) {
        try {
            return loadSequence(DocumentBuilderFactory.newInstance()
                    .newDocumentBuilder().parse(xml).getDocumentElement());
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    /**
     * Generates a sequence from the provided XML file
     * @param xml XML description of sequence to generate
     * @return sequence generated from XML provided
     */
    private static Sequence loadSequence(final File xml) {
        try {
            return loadSequence(new FileInputStream(xml));
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    /**
     * Writes the provided sequence to System.out
     * @param sequence sequence to print
     */
    private static void printSequence(final Sequence sequence) {
        final StringBuilder buffer = new StringBuilder();
        for(final Sequence.Entry entry: sequence) {
            buffer.append(entry.getName());
            buffer.append('\n');
        }
        System.out.print(buffer);
    }

    public static void main(final String[] args) {
        for(final String arg: args) {
            printSequence(loadSequence(new File(arg)));
        }
    }
}