gistfile1.java

package com.example.ojacobson;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.regex.Pattern;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.ListMultimap;

/**
 * Generates random strings from a suite of rules. Each rule has a name, and a
 * collection of templates. Templates consist of runs of plain text and rule
 * substitutions. When generation encounters a rule substitution, it expands a
 * random template from the rule named by the substitution. Multiple templates
 * may share the same rule.
 * <p>
 * The algorithm this generator uses will happily consume infinite time and
 * space when asked to generate recursive rules. This is unlikely to be fixed;
 * design your rulesets to have probable termination in some reasonable amount
 * of time and space. The algorithm is also recursive, so sufficiently deep
 * trees of templates will blow your stack.
 */
public class StringGenerator {

	private static interface Segment {
		/**
		 * Expand this segment to produce a string.
		 * 
		 * @param random
		 *            the RNG to use when selecting alternate expansions.
		 * @return the resulting string.
		 */
		public String expand(Random random);
	}

	private static class Literal implements Segment {
		private final String body;

		/**
		 * Creates a literal segment which {@link #expand(Random) expands} to
		 * <var>body</var>.
		 * 
		 * @param body
		 *            the body of the literal.
		 */
		public Literal(String body) {
			this.body = body;
		}

		/**
		 * @see com.unreasonent.ds.strings.StringGenerator.Segment#expand(java.util.Random)
		 */
		@Override
		public String expand(Random random) {
			return body;
		}
	}

	private class Substitution implements Segment {
		private final String name;

		public Substitution(String name) {
			this.name = name;
		}

		@Override
		public String expand(Random random) {
			Template template = selectTemplate(name, random);
			return template.expand(random);
		}
	}

	private static class Template {
		private final List<Segment> segments;

		/**
		 * Wires up a template to expand a given list of segments.
		 * 
		 * @param segments
		 *            the template's segments.
		 */
		public Template(List<Segment> segments) {
			this.segments = new ArrayList<>(segments);
		}

		/**
		 * Generate a String from this template by expanding each of its
		 * segments.
		 * 
		 * @param random
		 *            the RNG to use when selecting alternate expansions.
		 * @return the resulting expansion.
		 */
		public String expand(Random random) {
			StringBuilder result = new StringBuilder();

			for (Segment segment : segments)
				result.append(segment.expand(random));

			return result.toString();
		}
	}

	private final ListMultimap<String, Template> templates = ArrayListMultimap
			.create();

	/**
	 * Adds a named rule to the generator. The rule will be available in
	 * subsequent calls to {@link #generate(String, Random)}.
	 * <p>
	 * Templates can consist of arbitrary text, and may contain "substitutions"
	 * consisting of a rule name enclosed in {curly braces}. To include a
	 * literal curly brace in a rule, define a rule whose only pattern is a
	 * single curly brace (of either variety) and reference it as a substitution
	 * target.
	 * <p>
	 * Substitution targets do not need to refer to existing rules during
	 * {@link #addTemplate(String, String)}. However, undefined rules will cause
	 * {@link #generate(String, Random)} to throw an exception when it attempts
	 * to expand them.
	 * 
	 * @param name
	 *            the name to add a rule for.
	 * @param template
	 *            the template to add as an alternative for the named rule.
	 */
	public void addTemplate(String name, String template) {
		templates.put(name, parse(template));
	}

	private static final char SUBST_START = '{';
	private static final char SUBST_END = '}';

	private enum ParserState {
		LITERAL() {
			@Override
			public ParserState consider(char c, StringGenerator generator,
					List<Segment> segments, StringBuilder segment) {
				if (c == SUBST_START) { // Skipped in output.
					segments.add(new Literal(segment.toString()));
					segment.setLength(0);
					return SUBST;
				}

				segment.append(c);
				return LITERAL;
			}

			@Override
			public void remainder(List<Segment> segments, StringBuilder segment) {
				segments.add(new Literal(segment.toString()));
			}
		},
		SUBST() {
			@Override
			public ParserState consider(char c, StringGenerator generator,
					List<Segment> segments, StringBuilder segment) {
				if (c == SUBST_END) { // Skipped in output.
					segments.add(generator.new Substitution(segment.toString()));
					segment.setLength(0);
					return LITERAL;
				}

				segment.append(c);
				return SUBST;
			}

			@Override
			public void remainder(List<Segment> segments, StringBuilder segment) {
				// If we're in this state at the end of the string, we saw (and
				// discarded) a '{' that needs to be re-prepended.
				segments.add(new Literal(SUBST_START + segment.toString()));
			}
		};

		public abstract ParserState consider(char c, StringGenerator generator,
				List<Segment> segments, StringBuilder segment);

		public abstract void remainder(List<Segment> segments,
				StringBuilder segment);
	}

	private Template parse(String pattern) {
		List<Segment> segments = new ArrayList<>();
		StringBuilder segment = new StringBuilder();
		ParserState state = ParserState.LITERAL;
		for (char c : pattern.toCharArray())
			state = state.consider(c, this, segments, segment);
		state.remainder(segments, segment);
		return new Template(segments);
	}

	/**
	 * Generates a random string from the rules in this generator. The passed
	 * {@link Random} will be used to select patterns.
	 * 
	 * @param name
	 *            the name of the rule to start from.
	 * @param random
	 *            the random number generator controlling rule selection.
	 * @return the generated string.
	 * @throws IllegalStateException
	 *             if the requested rule does not exist, or if expansion of
	 *             rules encounters a substitution that refers to an undefined
	 *             rule.
	 */
	public String generate(String name, Random random) {
		Template pattern = selectTemplate(name, random);

		return pattern.expand(random);
	}

	private Template selectTemplate(String name, Random random) {
		List<Template> patterns = requireTemplate(name);
		Template pattern = selectRandom(patterns, random);
		return pattern;
	}

	private <T> T selectRandom(List<T> elements, Random random) {
		int index = random.nextInt(elements.size());
		return elements.get(index);
	}

	private List<Template> requireTemplate(String name) {
		if (templates.containsKey(name))
			return templates.get(name);
		throw new IllegalStateException(String.format(
				"Rule '%s' has no templates.", name));
	}
}