<commit_before>/*
 * Copyright <NAME> 2009-2012, All rights reserved.
 *
 * This code is licensed under a standard 3-clause BSD license:
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice, 
 *    this list of conditions and the following disclaimer.
 * 
 *  * Redistributions in binary form must reproduce the above copyright notice, 
 *    this list of conditions and the following disclaimer in the documentation 
 *    and/or other materials provided with the distribution.
 * 
 *  * The names of its contributors may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */

package net.domesdaybook.automata.regex;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import net.domesdaybook.automata.Automata;
import net.domesdaybook.automata.State;
import net.domesdaybook.automata.StateFactory;
import net.domesdaybook.automata.Transition;
import net.domesdaybook.automata.TransitionFactory;
import net.domesdaybook.automata.base.BaseAutomata;
import net.domesdaybook.automata.base.BaseStateFactory;

/**
 * This class helps to build an automata as it is invoked for each node of a regular 
 * expression parse-tree. It builds a particular kind of automata as it goes,
 * called a Glushkov automata.  
 * <p>
 * A Glushkov Non-deterministic Finite-state Automata (NFA) is an automata which
 * is constructed to have one initial state, and additionally, a state for each
 * position in the regular expression that defines a byte or set of bytes.
 * <p>
 * Each position has transitions to every other reachable position,
 * on the bytes which need to match to get to those positions.
 * <p>
 * Being Non-Deterministic means that from any given state,
 * there can be transitions to several states on the same byte value.
 * (by contrast, Deterministic Finite-state Automata (DFAs) have at most one
 * state they can transition to on a given byte value.)
 * <p>
 * Unlike the classic Thompson construction (the most common regular expression NFA)
 * Glushkov automata have no "empty" transitions - that is, transitions to another
 * state without reading a byte. The Thompson NFA uses empty transitions as a sort of 
 * permanent scaffolding to simplify constructing the automata, by wiring up states 
 * together as the need arises during construction.  
 * <p>
 * Having no empty transitions makes the automata smaller, and easier to transform
 * it further (e.g. building a DFA from it) but makes constructing it a little more
 * difficult in the first place.
 * <p>
 * The method of constructing a Glushkov automata used in this class is due to 
 * Champarnaud.  Details of the construction can be found in the paper:
 * <p>
 *   "A reexamination of the Glushkov and Thompson Constructions"
 *    by <NAME>, <NAME>, <NAME>, 1998.
 *
 * @param <T> The type of the object associated with a State in the NFA.
 * @param <S> The type of object used to build a transition from.
 * 
 * @author <NAME>
 */
public final class GlushkovRegexBuilder<T, S> implements RegexBuilder<T, S> {

	private final TransitionFactory<T, S>	transitionFactory;
	private final StateFactory<T>		stateFactory;

	/**
	 * Constructs a GlushkovRegexBuilder using the default {@link net.domesdaybook.automata.StateFactory},
	 * {@link net.domesdaybook.automata.base.BaseStateFactory}, and the supplied 
	 * default {@link net.domesdaybook.automata.TransitionFactory}.
	 * 
	 * @param transitionFactory The TransitionFactory to use when creating the NFA.
	 * @throws IllegalArgumentException if the transition factory passed in is null.
	 */
	public GlushkovRegexBuilder(final TransitionFactory<T, S> transitionFactory) {
		this(transitionFactory, null);
	}

	/**
	 * Constructs a GlushkovRegexBuilder using the supplied
	 * {@link net.domesdaybook.automata.StateFactory},
	 * and the supplied 
	 * default {@link net.domesdaybook.automata.TransitionFactory}.
	 * 
	 * @param transitionFactory The TransitionFactory to use when creating the NFA.
	 * @param stateFactory The StateFactory to use when creating the NFA.
	 * @throws IllegalArgumentException if the transition factory passed in is null.
	 */
	public GlushkovRegexBuilder(final TransitionFactory<T, S> transitionFactory,
			final StateFactory<T> stateFactory) {
		if (transitionFactory == null) {
			throw new IllegalArgumentException("Transition factory cannot be null.");
		} else {
			this.transitionFactory = transitionFactory;
		}
		if (stateFactory == null) {
			this.stateFactory = new BaseStateFactory<T>();
		} else {
			this.stateFactory = stateFactory;
		}
	}

	/**
	 * Builds an (initial) state and a [final] state,<commit_msg>minor refactoring removing unnecessary else clause.<commit_after>/*
 * Copyright <NAME> 2009-2012, All rights reserved.
 *
 * This code is licensed under a standard 3-clause BSD license:
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice, 
 *    this list of conditions and the following disclaimer.
 * 
 *  * Redistributions in binary form must reproduce the above copyright notice, 
 *    this list of conditions and the following disclaimer in the documentation 
 *    and/or other materials provided with the distribution.
 * 
 *  * The names of its contributors may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */

package net.domesdaybook.automata.regex;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import net.domesdaybook.automata.Automata;
import net.domesdaybook.automata.State;
import net.domesdaybook.automata.StateFactory;
import net.domesdaybook.automata.Transition;
import net.domesdaybook.automata.TransitionFactory;
import net.domesdaybook.automata.base.BaseAutomata;
import net.domesdaybook.automata.base.BaseStateFactory;

/**
 * This class helps to build an automata as it is invoked for each node of a regular 
 * expression parse-tree. It builds a particular kind of automata as it goes,
 * called a Glushkov automata.  
 * <p>
 * A Glushkov Non-deterministic Finite-state Automata (NFA) is an automata which
 * is constructed to have one initial state, and additionally, a state for each
 * position in the regular expression that defines a byte or set of bytes.
 * <p>
 * Each position has transitions to every other reachable position,
 * on the bytes which need to match to get to those positions.
 * <p>
 * Being Non-Deterministic means that from any given state,
 * there can be transitions to several states on the same byte value.
 * (by contrast, Deterministic Finite-state Automata (DFAs) have at most one
 * state they can transition to on a given byte value.)
 * <p>
 * Unlike the classic Thompson construction (the most common regular expression NFA)
 * Glushkov automata have no "empty" transitions - that is, transitions to another
 * state without reading a byte. The Thompson NFA uses empty transitions as a sort of 
 * permanent scaffolding to simplify constructing the automata, by wiring up states 
 * together as the need arises during construction.  
 * <p>
 * Having no empty transitions makes the automata smaller, and easier to transform
 * it further (e.g. building a DFA from it) but makes constructing it a little more
 * difficult in the first place.
 * <p>
 * The method of constructing a Glushkov automata used in this class is due to 
 * Champarnaud.  Details of the construction can be found in the paper:
 * <p>
 *   "A reexamination of the Glushkov and Thompson Constructions"
 *    by <NAME>, <NAME>, <NAME>, 1998.
 *
 * @param <T> The type of the object associated with a State in the NFA.
 * @param <S> The type of object used to build a transition from.
 * 
 * @author <NAME>
 */
public final class GlushkovRegexBuilder<T, S> implements RegexBuilder<T, S> {

	private final TransitionFactory<T, S>	transitionFactory;
	private final StateFactory<T>		stateFactory;

	/**
	 * Constructs a GlushkovRegexBuilder using the default {@link net.domesdaybook.automata.StateFactory},
	 * {@link net.domesdaybook.automata.base.BaseStateFactory}, and the supplied 
	 * default {@link net.domesdaybook.automata.TransitionFactory}.
	 * 
	 * @param transitionFactory The TransitionFactory to use when creating the NFA.
	 * @throws IllegalArgumentException if the transition factory passed in is null.
	 */
	public GlushkovRegexBuilder(final TransitionFactory<T, S> transitionFactory) {
		this(transitionFactory, null);
	}

	/**
	 * Constructs a GlushkovRegexBuilder using the supplied
	 * {@link net.domesdaybook.automata.StateFactory},
	 * and the supplied 
	 * default {@link net.domesdaybook.automata.TransitionFactory}.
	 * 
	 * @param transitionFactory The TransitionFactory to use when creating the NFA.
	 * @param stateFactory The StateFactory to use when creating the NFA.
	 * @throws IllegalArgumentException if the transition factory passed in is null.
	 */
	public GlushkovRegexBuilder(final TransitionFactory<T, S> transitionFactory,
			final StateFactory<T> stateFactory) {
		if (transitionFactory == null) {
			throw new IllegalArgumentException("Transition factory cannot be null.");
		}
		this.transitionFactory = transitionFactory;
		if (stateFactory == null) {
			this.stateFactory = new BaseStateFactory<T>();
		} else {
			this.stateFactory = stateFactory;
		}
	}

	/**
	 * Builds an (initial) state and a [final] state,
{'fraction_non_alphanumeric': 0.06875551632833186, 'fraction_numerical': 0.002294792586054722, 'mean_word_length': 4.253129346314325, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 47, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4668640', 'n_tokens_mistral': 3160, 'n_tokens_neox': 2888, 'n_words': 1359}