ant/org.eclipse.ant.ui/Ant Editor/org/eclipse/ant/internal/ui/dtd/schema/Nfm.java

/*******************************************************************************
 * Copyright (c) 2002, 2005 Object Factory Inc.
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 * 
 * Contributors:
 *		Object Factory Inc. - Initial implementation
 *******************************************************************************/
package org.eclipse.ant.internal.ui.dtd.schema;

import org.eclipse.ant.internal.ui.dtd.IAtom;
import org.eclipse.ant.internal.ui.dtd.util.Factory;
import org.eclipse.ant.internal.ui.dtd.util.FactoryObject;


/**
 * Non-deterministic finite state machine.
 * @author Bob Foster
 */
public class Nfm implements FactoryObject {
	private NfmNode start;
	private NfmNode stop;
	
	public NfmNode getStart() {
		return start;
	}
	
	public NfmNode getStop() {
		return stop;
	}
	
	/**
	 * Construct an nfm such that:
	 * <pre>
	 * start  stop
	 *   |      |
	 * +---+  +---+
	 * | s |->|   |
	 * +---+  +---+
	 * </pre>
	 * In all pictures, boxes are NfmNodes.
	 */
	private static Nfm nfm(IAtom s) {
		Nfm nfm = free();
		nfm.stop = NfmNode.nfmNode();
		nfm.start = NfmNode.nfmNode(s, nfm.stop);
		return nfm;
	}
	
	/**
	 * Construct an nfm that "wraps" an existing nfm x such that:
	 * <pre>
	 * start                            stop
	 *   |                                |
	 * +---+  +---------+  +---------+  +---+
	 * |   |->| x start |  | x stop  |->|   |
	 * +---+  +---------+  +---------+  +---+
	 * </pre>
	 */
	private static Nfm nfm(Nfm x) {
		Nfm nfm = free();
		nfm.start = NfmNode.nfmNode(x.start);
		nfm.stop = NfmNode.nfmNode();
		x.stop.next1 = nfm.stop;
		return nfm;
	}
	
	private static Nfm nfm() {
		Nfm nfm = free();
		nfm.start = NfmNode.nfmNode();
		nfm.stop = NfmNode.nfmNode();
		return nfm;
	}

	public static Nfm getNfm(IAtom s) {
		return nfm(s);
	}
	
	/**
	 * "Star" an existing nfm x.
	 * <pre>
	 * start                            stop
	 *   |                                |
	 * +---+  +---------+  +---------+  +---+
	 * |   |->| x start |  | x stop  |->|   |
	 * +---+  +---------+  +---------+  +---+
	 *   |         |            |         |
	 *   |         +-----<------+         |
	 *   +------>-------------------------+
	 * </pre>
	 * Frees x.
	 */
	public static Nfm getStar(Nfm x) {
		// Make the back link
		x.stop.next2 = x.start;
		Nfm tmp = nfm(x);
		// Make the forward link
		tmp.start.next2 = tmp.stop;
		free(x);
		return tmp;
	}
	
	/**
	 * "Question" an existing nfm x: x => x?
	 * <pre>
	 * start                            stop
	 *   |                                |
	 * +---+  +---------+  +---------+  +---+
	 * |   |->| x start |  | x stop  |->|   |
	 * +---+  +---------+  +---------+  +---+
	 *   |                                |
	 *   +---------------->---------------+
	 * </pre>
	 * Frees x.
	 */
	public static Nfm getQuestion(Nfm x) {
		Nfm tmp = nfm(x);
		// Make the forward link
		tmp.start.next2 = tmp.stop;
		free(x);
		return tmp;
	}

	/**
	 * "Plus" an existing nfm x -> x+
	 * <pre>
	 * start                            stop
	 *   |                                |
	 * +---+  +---------+  +---------+  +---+
	 * |   |->| x start |  | x stop  |->|   |
	 * +---+  +---------+  +---------+  +---+
	 *             |            |
	 *             +-----<------+
	 * </pre>
	 * Frees x.
	 */
	public static Nfm getPlus(Nfm x) {
		// Make the back link
		x.stop.next2 = x.start;
		Nfm tmp = nfm(x);
		free(x);
		return tmp;
	}
	
	/**
	 * "Or" two existing nfms x,y -> x|y
	 * <pre>
	 * start                            stop
	 *   |                                |
	 * +---+  +---------+  +---------+  +---+
	 * |   |->| x start |  | x stop  |->|   |
	 * +---+  +---------+  +---------+  +---+
	 *   |                                |
	 *   |    +---------+  +---------+    |
	 *   +--->| y start |  | y stop  |-->-+
	 *        +---------+  +---------+
	 * </pre>
	 * Frees x and y.
	 */
	public static Nfm getOr(Nfm x, Nfm y) {
		Nfm tmp = nfm();
		tmp.start.next1 = x.start;
		tmp.start.next2 = y.start;
		x.stop.next1 = tmp.stop;
		y.stop.next1 = tmp.stop;
		free(x);
		free(y);
		return tmp;
	}
	
	/**
	 * "Comma" two existing nfms x,y -> x,y
	 * 
	 * <p>Re-uses x so that x.stop is first
	 * transformed to y.start and then
	 * x.stop is reset to y.stop.
	 * This is as efficient as possible.
	 * <pre>
	 * x start      former x stop   x stop
	 *     |               |           |
	 * +---------+  +----------+  +--------+
	 * | x start |  | y start  |->| y stop |
	 * +---------+  +----------+  +--------+
	 * </pre>
	 * Frees y, returns x modified.
	 */
	public static Nfm getComma(Nfm x, Nfm y) {
		x.stop.next1 = y.start.next1;
		x.stop.next2 = y.start.next2;
		x.stop.symbol = y.start.symbol;
		x.stop = y.stop;
		free(y);
		return x;
	}
	
	/**
	 * "{min,*}" an existing nfm x -> x[0],x[1],...,x[min-1],x[min]*
	 * Frees x.
	 */
	public static Nfm getUnbounded(Nfm x, int min) {
		if (min == 0)
			return getStar(x);
		if (min == 1)
			return getPlus(x);
		Nfm last1 = nfm(x), last2 = nfm(x);
		for (int i = 2; i < min; i++) {
			last1 = getComma(last1, last2);
			free(last2);
			last2 = nfm(x);
		}
		free(x);
		return getComma(last1, getStar(last2));
	}
	
	/**
	 * "{min,max}" an existing nfm x -> x[0],x[1],...,x[min-1],x[min]?,...,x[max-1]?
	 * Frees or returns x.
	 */
	public static Nfm getMinMax(Nfm x, int min, int max) {
		if (max == Integer.MAX_VALUE)
			return getUnbounded(x, min);
		if (max == 0) {
			free(x);
			return nfm((IAtom)null);
		}
		if (max == 1) {
			if (min == 0)
				return getQuestion(x);
			return x;
		}
		Nfm last = null;
		int i = 0;
		for (; i < min; i++) {
			if (last == null)
				last = nfm(x);
			else {
				Nfm tmp = nfm(x);
				last = getComma(last, tmp);
				free(tmp);
			}
		}
		for (; i < max; i++) {
			if (last == null)
				last = getQuestion(x);
			else {
				Nfm tmp = getQuestion(x);
				last = getComma(last, tmp);
				free(tmp);
				//??? this is inefficient since the first failure
				//    in a sequence of x?,x?,...,x? can skip to
				//    the end rather than keep trying to match x
			}
		}
		free(x);
		return last;
	}
	
	// Below here is factory stuff
	
	/* (non-Javadoc)
	 * @see org.eclipse.ant.internal.ui.dtd.util.FactoryObject#next()
	 */
	public FactoryObject next() {
		return fNext;
	}
	
	/* (non-Javadoc)
	 * @see org.eclipse.ant.internal.ui.dtd.util.FactoryObject#next(org.eclipse.ant.internal.ui.dtd.util.FactoryObject)
	 */
	public void next(FactoryObject obj) {
		fNext = (Nfm) obj;
	}
	private Nfm fNext;
	private static Factory fFactory = new Factory();
	private static Nfm free() {
		Nfm nfm = (Nfm) fFactory.getFree();
		if (nfm == null)
			return new Nfm();
		return nfm;
	}
	public static void free(Nfm nfm) {
		nfm.start = nfm.stop = null;
		fFactory.setFree(nfm);
	}
	private Nfm() {
	}
}