var fsm = function () {
    const debugging = false;

    const debug = function (msg) {
	if (debugging) {
	    console.log(msg);
	}
    };

    /**
     * a fsm that tries to match string "abb". see function
     * matchesSubstringAbb.
     */
    const matchAbbMachine = function () {
	const stateWaitForA = "wait for a";
	const stateWaitForFirstB = "wait for 1st b";
	const stateWaitForSecondB = "wait for 2nd b";
	const stateSucceed = "succeed";

	this.currentState = "wait for a";
	this.readch = function (ch) {
	    switch (this.currentState) {
	    case stateWaitForA:
		if (ch === 'a') {
		    this.currentState = stateWaitForFirstB;
		} else {
		    this.currentState = stateWaitForA;
		}
		break;
	    case stateWaitForFirstB:
		if (ch === 'b') {
		    this.currentState = stateWaitForSecondB;
		} else if (ch === 'a') {
		    // do nothing, keep current state.
		} else {
		    this.currentState = stateWaitForA;
		}
		break;
	    case stateWaitForSecondB:
		if (ch === 'b') {
		    this.currentState = stateSucceed;
		} else if (ch === 'a') {
		    this.currentState = stateWaitForFirstB;
		} else {
		    this.currentState = stateWaitForA;
		}
		break;
	    case this.succeed:
		// do nothing, keep current state.
		break;
	    }
	    debug("readch " + ch + ", currentState is " + this.currentState);
	    return this.currentState;
	};
    };

    /**
     * return true if given string has substring "abb" in it.
     * implemented using fsm.
     */
    const matchesSubstringAbb = function (str) {
	const machine = new matchAbbMachine();
	for (i = 0; i < str.length; ++i) {
	    machine.readch(str[i]);
	    if (machine.currentState === "succeed") {
		// console.log("matches");
		return true;
	    }
	}
	return false;
    };

    /**
     * a fsm that implement a RPN calculator. see document in ./operational
     */
    const RPNCalculator = function () {
	// states
    	const stateIdle = "idle";
    	const stateWaitingForNumberOrAction = "waiting for number or action";

	// define constants for key name literals.
	const keyNames = {
	    num0: "num0",
	    num1: "num1",
	    num2: "num2",
	    num3: "num3",
	    num4: "num4",
	    num5: "num5",
	    num6: "num6",
	    num7: "num7",
	    num8: "num8",
	    num9: "num9",
	    dot: "dot",
	    backspace: "backspace",
	    times: "times",
	    divide: "divide",
	    plus: "plus",
	    minus: "minus",
	    sum_all: "sum-all",
	    square_root: "square-root",
	    power: "power",
	    swap: "swap",
	    undo: "undo",
	    "return": "return",
	    change_sign: "change-sign",
	    round: "round",
	};
	// map keyName to short key name.
	const shortKeyNames = {
	    "num0": "0",
	    "num1": "1",
	    "num2": "2",
	    "num3": "3",
	    "num4": "4",
	    "num5": "5",
	    "num6": "6",
	    "num7": "7",
	    "num8": "8",
	    "num9": "9",
	    "dot": ".",
	    "backspace": "bksp",
	    "times": "*",
	    "divide": "/",
	    "plus": "+",
	    "minus": "-",
	    "sum-all": "Σ",
	    "square-root": "sqrt",
	    "power": "pow",
	    "swap": "swap",
	    "undo": "undo",
	    "return": "ret",
	    "change-sign": "chs",
	    round: "rond",
	};
	const msgTooFewElementsOnStack = "Too few elements on stack";
	const trailHistorySize = 100;
	const undoHistorySize = 100;

    	this.currentState = stateIdle;
    	this.numberStack = [];
    	this.currentNumber = "";
	this.lastError = null;
	this.trail = new fifo.BoundedQueue(trailHistorySize);
	this.snapshots = new fifo.BoundedStack(undoHistorySize);

	/**
	 * save current state of this FSM. You can use load to restore the FSM state.
	 */
	this.save = function () {
	    return {
		"currentState": this.currentState,
		"numberStack": this.numberStack.slice(0),
		"currentNumber": this.currentNumber,
		"trail": this.trail.clone(),
	    };
	};
	/**
	 * load saved data back to this FSM. current FSM status will be lost.
	 */
	this.load = function (data) {
	    this.currentState = data.currentState;
	    this.numberStack = data.numberStack.slice(0);
	    this.currentNumber = data.currentNumber;
	    this.trail = data.trail.clone();
	};
	/**
	 * set error msg. only the last error msg can be fetched via this.lastError.
	 */
	this.setErrorMsg = function (msg) {
	    console.log(msg);
	    this.lastError = msg;
	};
	/**
	 * clear error msg.
	 */
	this.clearErrorMsg = function () {
	    this.lastError = null;
	};
	/**
	 * do calculator for an unary operator.
	 * this handles not enough element in stack problem.
	 *
	 * it may modify this.numberStack and this.lastError.
	 *
	 * Return true on success, return false on failure.
	 * You may do early return if this function fails. this.lastError will
	 * be set when false is returned.
	 */
	this.doUnaryOperator = function (keyName, func) {
	    this.snapshots.push(this.save());

	    const num = this.numberStack.pop();
	    if (num === undefined) {
		this.setErrorMsg(msgTooFewElementsOnStack);
		this.snapshots.pop();
		return false;
	    }
	    const result = func(num);
	    if (result === undefined || result === null || result === false) {
		// this does consume the number. Just don't push result
		// to number stack.
		if (this.lastError === null) {
		    this.setErrorMsg("result of this operator is undefined or null");
		}
		return false;
	    }
	    this.numberStack.push(result);

	    this.trail.push([shortKeyName(keyName), result]);
	    return true;
	};
	/**
	 * do calculation for a binary operator.
	 * this handles not enough element in stack problem.
	 *
	 * it may modify this.numberStack and this.lastError.
	 *
	 * Return true on success, return false on failure.
	 * You may do early return if this function fails. this.lastError will
	 * be set when false is returned.
	 */
	this.doBinaryOperator = function (keyName, func) {
	    this.snapshots.push(this.save());

	    const num2 = this.numberStack.pop();
	    if (num2 === undefined) {
		this.setErrorMsg(msgTooFewElementsOnStack);
		this.snapshots.pop();
		return false;
	    }
	    const num1 = this.numberStack.pop();
	    if (num1 === undefined) {
		this.setErrorMsg(msgTooFewElementsOnStack);
		this.numberStack.push(num2);
		this.snapshots.pop();
		return false;
	    }
	    const result = func(num1, num2);
	    if (result === undefined || result === null || result === false) {
		// this does consume the two numbers. Just don't push result
		// to number stack.
		if (this.lastError === null) {
		    this.setErrorMsg("result of this operator is undefined or null");
		}
		return false;
	    }
	    this.numberStack.push(result);

	    this.trail.push([shortKeyName(keyName), result]);
	    return true;
	};

	/**
	 * return true if given keyName is one of number keys.
	 * number keys include num0-9 and dot.
	 */
	const isNumberKey = function (keyName) {
	    return (keyNames[keyName] !== undefined) && (keyName.startsWith("num") || keyName === keyNames.dot);
	};
	/**
	 * operator key names.
	 */
	const operatorKeyList = [
	    keyNames.change_sign,
	    keyNames.plus, keyNames.minus, keyNames.times, keyNames.divide,
	    keyNames.swap, keyNames.undo, keyNames.sum_all, keyNames.square_root,
	    keyNames.power, keyNames.round,
	];
	const isOperator = function (keyName) {
	    return operatorKeyList.indexOf(keyName) !== -1;
	};
	/**
	 * keys that is not a simple operator.
	 */
	const miscKeyList = [keyNames["return"], keyNames.undo, keyNames.backspace];
	const isMiscKey = function (keyName) {
	    return miscKeyList.index(keyName) !== -1;
	};
	/**
	 * convert number key to a number string.
	 */
	const numKeyToNumString = function (keyName) {
	    console.assert(isNumberKey(keyName), "not a number key: " + keyName);
	    if (keyName === keyNames.dot) {
		return ".";
	    } else {
		return keyName.substring(3);
	    }
	};
	/**
	 * press keyName when existing number string is oldNumberString.
	 * return [newNumberString, errMsg]
	 * errMsg will be null if there is no error.
	 */
	const changeNumberString = function (keyName, oldNumberString) {
	    if (oldNumberString === "0" && keyName === keyNames.num0) {
		return [oldNumberString, "more 0s are ignored"];
	    } else if (oldNumberString === "" && keyName === keyNames.dot) {
		return ["0.", null];
	    } else if (keyName === keyNames.dot && oldNumberString.indexOf(".") !== -1) {
		// Note: do not use indexOf(keyNames.dot) in if condition,
		// because the keyName is dot, not ".".
		return [oldNumberString, "more dots are ignored"];
	    } else {
		return [oldNumberString + numKeyToNumString(keyName), null];
	    }
	};
	const testChangeNumberString = function () {
	    var r = changeNumberString(keyNames.dot, "");
	    console.assert(r[0] === "0.");
	    console.assert(r[1] === null);

	    r = changeNumberString(keyNames.num1, "");
	    console.assert(r[0] === "1");
	    console.assert(r[1] === null);

	    r = changeNumberString(keyNames.num1, "2");
	    console.assert(r[0] === "21");
	    console.assert(r[1] === null);

	    r = changeNumberString(keyNames.num0, "0");
	    console.assert(r[0] === "0");
	    console.assert(r[1] !== null);

	    r = changeNumberString(keyNames.num0, "12");
	    console.assert(r[0] === "120");
	    console.assert(r[1] === null);

	    r = changeNumberString(keyNames.dot, "1.2");
	    console.assert(r[0] === "1.2");
	    console.assert(r[1] !== null);
	};
	/**
	 * return short key name for given keyName.
	 * this is used to show operator in shorter form in trails.
	 */
	const shortKeyName = function (keyName) {
	    return shortKeyNames[keyName];
	};
	const printSnapshots = function (snapshots) {
	    debug("printSnapshots()");
	    const data = snapshots.data;
	    const l = data.length;
	    debug("len=" + l);
	    var i;
	    for (i = 0; i < l; ++i) {
		debug("snapshot[" + i + "]: " + data[i].currentState + ", " + data[i].numberStack);
	    }
	};
	const printSnapshot = function (snapshot) {
	    const msg = "snapshot: " + snapshot.currentState + ", " + snapshot.numberStack;
	    debug(msg);
	    return msg;
	};
    	this.sendKey = function (keyName) {
	    var num, num1, num2;
	    var numString, errMsg;
	    var r;

    	    switch (this.currentState) {
    	    case stateIdle:
    		if (isNumberKey(keyName)) {
		    r = changeNumberString(keyName, this.currentNumber);
		    numString = r[0];
		    errMsg = r[1];
		    if (errMsg === null) {
			this.currentNumber = numString;
			// change state
			this.currentState = stateWaitingForNumberOrAction;
		    } else {
			// idle state always succeed on number key input.
			console.assert(false, "this should not happen");
			this.setErrorMsg(errMsg);
			return;
		    }
		} else {
		    switch (keyName) {
		    case keyNames.change_sign:
			if (! this.doUnaryOperator(keyName, (num) => -num)) {
			    return;
			}
		    	break;
		    case keyNames.round:
			if (! this.doUnaryOperator(keyName, (num) => Math.round(num))) {
			    return;
			}
		    	break;
		    case keyNames.square_root:
			if (! this.doUnaryOperator(keyName, (num) => {
			    if (num < 0) {
				// consumes the number and show error to user.
				this.setErrorMsg("square root of negative not supported");
				this.snapshots.pop();
				return;
			    }
			    return Math.pow(num, 0.5);
			})) {
			    return;
			}
		    	break;
		    case keyNames.plus:
			if (! this.doBinaryOperator(keyName, (lhs, rhs) => lhs + rhs)) {
			    return;
			}
		    	break;
		    case keyNames.minus:
			if (! this.doBinaryOperator(keyName, (lhs, rhs) => lhs - rhs)) {
			    return;
			}
		    	break;
		    case keyNames.times:
			if (! this.doBinaryOperator(keyName, (lhs, rhs) => lhs * rhs)) {
			    return;
			}
		    	break;
		    case keyNames.divide:
			if (! this.doBinaryOperator(keyName, (lhs, rhs) => {
			    if (rhs === 0) {
				this.setErrorMsg("Division by 0");
				return null;
			    }
			    return lhs / rhs;
			})) {
			    return;
			}
		    	break;
		    case keyNames.power:
			if (! this.doBinaryOperator(keyName, (lhs, rhs) => Math.pow(lhs, rhs))) {
			    return;
			}
		    	break;
		    case keyNames.swap:
			this.snapshots.push(this.save());
		    	num2 = this.numberStack.pop();
			if (num2 === undefined) {
			    this.setErrorMsg(msgTooFewElementsOnStack);
			    this.snapshots.pop();
			    return;
			}
		    	num1 = this.numberStack.pop();
			if (num1 === undefined) {
			    this.setErrorMsg(msgTooFewElementsOnStack);
			    this.numberStack.push(num2);
			    this.snapshots.pop();
			    return;
			}
		    	this.numberStack.push(num2);
		    	this.numberStack.push(num1);
			// no changes on trail
		    	break;
		    case keyNames['return']:
			// duplicate number
			this.snapshots.push(this.save());
			num = this.numberStack.pop();
			if (num === undefined) {
			    this.setErrorMsg(msgTooFewElementsOnStack);
			    this.snapshots.pop();
			    return;
			}
			this.numberStack.push(num);
			this.numberStack.push(num);
			// no changes on trail.
		    	break;
		    case keyNames.backspace:
			// drop one number on stack
			this.snapshots.push(this.save());
			num = this.numberStack.pop();
			if (num === undefined) {
			    this.setErrorMsg(msgTooFewElementsOnStack);
			    this.snapshots.pop();
			    return;
			}
		    	break;
		    case keyNames.sum_all:
			// sum all numbers of stack
			this.snapshots.push(this.save());
			r = 0;
			num = this.numberStack.pop();
			if (num === undefined) {
			    this.setErrorMsg(msgTooFewElementsOnStack);
			    this.snapshots.pop();
			    return;
			}
			while (num !== undefined) {
			    r += num;
			    num = this.numberStack.pop();
			}
			this.numberStack.push(r);
			this.trail.push([shortKeyName(keyName), r]);
			break;
		    case keyNames.undo:
			printSnapshots(this.snapshots);

			r = this.snapshots.pop();
			if (r === undefined) {
			    this.setErrorMsg("No more undo history!");
			    return;
			} else {
			    console.log("undo: load saved state: " + printSnapshot(r));
			    this.load(r);
			    this.setErrorMsg("Undo!");
			    // this is a success msg, no need to do early return.
			}
			break;
		    default:
		    	console.assert(false, "action not implemented, key is " + keyName);
		    }
		}
    		break;
    	    case stateWaitingForNumberOrAction:
    		if (isNumberKey(keyName)) {
		    r = changeNumberString(keyName, this.currentNumber);
		    numString = r[0];
		    errMsg = r[1];
		    if (errMsg === null) {
			this.currentNumber = numString;
		    } else {
			this.setErrorMsg(errMsg);
			return;
		    }
		    // keep current state
		} else if (keyName === keyNames['return']) {
		    // commit number to stack
		    num = parseFloat(this.currentNumber);
		    this.currentNumber = "";
		    this.currentState = stateIdle;

		    r = this.save();
		    // console.log("save a snapshot: " + r.currentState
		    // 		+ ", " + r.numberStack + ", " + r.currentNumber);
		    this.snapshots.push(r);

		    this.numberStack.push(num);
		    this.trail.push([null, num]);
		} else if (keyName === keyNames.backspace) {
		    if (this.currentNumber.length > 0) {
			this.currentNumber = this.currentNumber.substring(0, this.currentNumber.length - 1);
                        if (this.currentNumber === "") {
                            this.currentNumber = "0";
                        }
		    } else {
			this.setErrorMsg("no digits to delete");
		    }
		} else if (isOperator(keyName)) {
		    // commit number
		    console.log("send return key automatically");
		    this.sendKey(keyNames['return']);
		    console.assert(this.currentState === stateIdle,
				   "auto commit number should set state to idle");
		    // consume and resend this key. notice the early return.
		    console.log("resend key " + keyName);
		    return this.sendKey(keyName);
		} else {
		    switch (keyName) {
		    default:
			console.assert(false, "action not implemented, key is " + keyName);
		    }
		}
    		break;
	    default:
		console.assert(false, "unknown state: " + this.currentState);
    	    }
    	    debug("sendKey " + keyName + ", currentState is " + this.currentState);
	    this.clearErrorMsg();
    	    return this.currentState;
    	};
	this.clearTrail = function () {
	    this.trail.clear();
	};
	this.clearStack = function () {
	    this.numberStack = [];
	};
	this.reset = function () {
	    this.currentState = stateIdle;
    	    this.numberStack = [];
    	    this.currentNumber = "";
	    this.lastError = null;
	    this.trail = new fifo.BoundedQueue(trailHistorySize);
	};

	const runTests = function () {
	    testChangeNumberString();
	};

	// run all tests;
	runTests();
    };

    return {
	matchesSubstringAbb: matchesSubstringAbb,
	RPNCalculator: RPNCalculator,
    };
}();