path: root/rules.js

"use strict"

/*

Special scenario rules implemented:
	zero morale - instant loss

Special card rules implemented:

	place_2_blue
	place_2_red
	remove_after_screen
	suffer_1_less_1_max

*/

// TODO: allow placing dice on full special formations?
// TODO: fizzle when action says to take cards from other dice?

const data = require("./data.js")

// for (let c of data.cards) for (let a of c.actions) console.log(a.type, a.effect)

const P1 = "First"
const P2 = "Second"

var states = {}
var game = null
var view = null

const POOL = -1

const RED = 0
const PINK = 1
const BLUE = 2
const DKBLUE = 3

exports.scenarios = {
	"": [ "Random" ],
}

const scenario_roles = {}

for (let s of data.scenarios) {
	let id = s.number + " - " + s.name
	let x = s.expansion
	if (!(x in exports.scenarios)) {
		exports.scenarios[""].push("Random - " + x)
		exports.scenarios[x] = []
	}
	exports.scenarios[x].push(id)
	scenario_roles[id] = [ s.players[0].name, s.players[1].name ]
}

exports.is_random_scenario = function (scenario) {
	return scenario.startsWith("Random")
}

exports.select_random_scenario = function (scenario, seed) {
	if (scenario === "Random") {
		let info = data.scenarios[seed % data.scenarios.length]
		return info.number + " - " + info.name
	}
	if (scenario.startsWith("Random - ")) {
		let list = exports.scenarios[scenario.replace("Random - ", "")]
		return list[seed % list.length]
	}
	return scenario
}

exports.roles = [ P1, P2 ]

exports.action = function (state, player, action, arg) {
	game = state
	let S = states[game.state]
	if (action in S)
		S[action](arg, player)
	else if (action === "undo" && game.undo && game.undo.length > 0)
		pop_undo()
	else
		throw new Error("Invalid action: " + action)
	return game
}

exports.view = function (state, player) {
	game = state

	view = {
		log: game.log,
		prompt: null,
		scenario: game.scenario,
		dice: game.dice,
		sticks: game.sticks,
		cubes: game.cubes,
		morale: game.morale,
		front: game.front,
		reserve: game.reserve,
		selected: game.selected,
		target: game.target,
		hits: game.hits,
		self: game.self,
	}

	if (game.state === "game_over") {
		view.prompt = game.victory
	} else if (player !== game.active) {
		let inactive = states[game.state].inactive || game.state
		view.prompt = `Waiting for ${player_name()} to ${inactive}.`
	} else {
		view.actions = {}
		states[game.state].prompt()
		if (game.undo && game.undo.length > 0)
			view.actions.undo = 1
		else
			view.actions.undo = 0
	}

	return view
}

exports.resign = function (state, player) {
	game = state
	if (game.state !== 'game_over') {
		if (player === P1)
			return goto_game_over(P2, P1 + " resigned.")
		if (player === P2)
			return goto_game_over(P1, P2 + " resigned.")
	}
}

function goto_game_over(result, victory) {
	game.state = "game_over"
	game.active = "None"
	game.result = result
	game.victory = victory
	log("")
	log(game.victory)
	return false
}

states.game_over = {
	prompt() {
		view.prompt = game.victory
	},
}

// === SETUP ===

exports.setup = function (seed, scenario, options) {
	// TODO: "Random"

	scenario = parseInt(scenario)
	scenario = data.scenarios.findIndex(s => s.number === scenario)
	if (scenario < 0)
		throw Error("cannot find scenario: " + scenario)

	let info = data.scenarios[scenario]

	game = {
		seed: seed,
		scenario: scenario,
		log: [],
		undo: [],

		active: P1,
		state: "roll",

		reacted: 0,

		// dice value and position
		dice: [
			0, POOL, 0, POOL, 0, POOL, 0, POOL, 0, POOL, 0, POOL,
			0, POOL, 0, POOL, 0, POOL, 0, POOL, 0, POOL, 0, POOL,
		],

		// sticks (map normal formation -> count)
		sticks: [],

		// cubes (map special formation -> count)
		cubes: [],

		morale: [ info.players[0].morale, info.players[1].morale ],
		front: [ [], [], ],
		reserve: [ [], [] ],

		// dice value placed on what card
		placed: [],

		// current action
		routed: [ 0, 0 ],
		selected: -1,
		target: -1,
		hits: 0,
		self: 0,
	}

	function setup_formation(front, reserve, c) {
		let card = data.cards[c]
		if (card.reserve)
			set_add(reserve, c)
		else
			set_add(front, c)
		if (card.special)
			add_cubes(c, 1)
		else
			add_sticks(c, card.strength)
	}

	for (let p = 0; p < 2; ++p) {
		for (let c of info.players[p].cards)
			setup_formation(game.front[p], game.reserve[p], c)
	}

	log(".h1 " + info.name)
	log(".h2 " + info.date)
	log("")

	goto_action_phase()

	return game
}

// === GAME STATE ACCESSORS ===

function card_has_rule(c, name) {
	let rules = data.cards[c].rules
	if (rules)
		return rules[name]
	return false
}

function card_number(c) {
	return data.cards[c].number
}

function card_name(c) {
	return data.cards[c].name
}

function player_name() {
	let p = player_index()
	return data.scenarios[game.scenario].players[p].name
}

function set_opponent_active() {
	if (game.active === P1)
		game.active = P2
	else
		game.active = P1
}

function player_index() {
	if (game.active === P1)
		return 0
	return 1
}

function add_cubes(c, n) {
	let limit = data.cards[c].special
	let old = map_get(game.cubes, c, 0)
	map_set(game.cubes, c, Math.min(limit, old + n))
}

function remove_cubes(c, n) {
	let old = map_get(game.cubes, c, 0)
	map_set(game.cubes, c, Math.min(0, old - n))
}

function add_sticks(c, n) {
	let old = map_get(game.sticks, c, 0)
	map_set(game.sticks, c, old + n)
}

function remove_sticks(c, n) {
	let old = map_get(game.sticks, c, 0)
	map_set(game.sticks, c, Math.max(0, old - n))
}

function remove_dice(c) {
	for (let i = 0; i < 12; ++i) {
		if (get_dice_location(i) === c) {
			set_dice_location(i, POOL)
			set_dice_value(i, 0)
		}
	}
}

function eliminate_card(c) {
	remove_dice(c)
	remove_cubes(c, 3)
	set_delete(game.front[0], c)
	set_delete(game.front[1], c)
}

function pay_for_action(c) {
	if (data.cards[c].special)
		remove_cubes(c, 1)
	else
		remove_dice(c)
}

function get_player_dice_value(p, i) {
	return game.dice[p * 12 + i * 2]
}

function get_player_dice_location(p, i) {
	return game.dice[p * 12 + i * 2 + 1]
}

function set_player_dice_value(p, i, v) {
	game.dice[p * 12 + i * 2] = v
}

function set_player_dice_location(p, i, v) {
	game.dice[p * 12 + i * 2 + 1] = v
}

function get_dice_value(d) {
	return game.dice[d * 2]
}

function get_dice_location(i) {
	return game.dice[i * 2 + 1]
}

function set_dice_location(d, v) {
	game.dice[d * 2 + 1] = v
}

function set_dice_value(d, v) {
	game.dice[d * 2] = v
}

// === HOW TO WIN ===

function is_card_in_play(c) {
	return (
		set_has(game.front[0], c) ||
		set_has(game.front[1], c) ||
		set_has(game.reserve[0], c) ||
		set_has(game.reserve[1], c)
	)
}

function is_card_attack_with_target_in_play(c) {
	for (let a of data.cards[c].actions) {
		if (a.type === "Attack") {
			for (let t of a.target_list)
				if (is_card_in_play(t))
					return true
		}
	}
	return false
}

function check_impossible_to_attack_victory() {
	let p = player_index()
	for (let c of game.front[p])
		if (is_card_attack_with_target_in_play(c))
			return false
	for (let c of game.reserve[p])
		if (is_card_attack_with_target_in_play(c))
			return false
	return true
}

// === ROLL PHASE ===

function is_pool_die(i, v) {
	let p = player_index()
	return get_player_dice_location(p, i) < 0 && get_player_dice_value(p, i) === v
}

function is_pool_die_range(i, lo, hi) {
	let p = player_index()
	if (get_player_dice_location(p, i) < 0) {
		let v = get_player_dice_value(p, i)
		return v >= lo && v <= hi
	}
	return false
}

const place_dice_once = {
	"(1)": true,
	"(2)": true,
	"(3)": true,
	"(4)": true,
	"(5)": true,
	"(6)": true,
	"(1)/(2)": true,
	"(1)-(3)": true,
	"(1)-(4)": true,
	"(1)-(5)": true,
	"(2)/(3)": true,
	"(2)-(4)": true,
	"(2)-(5)": true,
	"(2)-(6)": true,
	"(3)/(4)": true,
	"(3)-(5)": true,
	"(3)-(6)": true,
	"(4)/(5)": true,
	"(4)-(6)": true,
	"(5)/(6)": true,
}

const place_dice_check = {
	"Straight 3": check_straight_3,
	"Straight 4": check_straight_4,
	"Doubles": check_doubles,
	"Triples": check_triples,
	"1": (c) => check_single(c, 1),
	"2": (c) => check_single(c, 2),
	"3": (c) => check_single(c, 3),
	"4": (c) => check_single(c, 4),
	"5": (c) => check_single(c, 5),
	"6": (c) => check_single(c, 6),
	"(1)": (c) => check_single(c, 1),
	"(2)": (c) => check_single(c, 2),
	"(3)": (c) => check_single(c, 3),
	"(4)": (c) => check_single(c, 4),
	"(5)": (c) => check_single(c, 5),
	"(6)": (c) => check_single(c, 6),
	"Any": (c) => check_range(c, 1, 6),
	"1/2": (c) => check_range(c, 1, 2),
	"1-3": (c) => check_range(c, 1, 3),
	"1-4": (c) => check_range(c, 1, 4),
	"1-5": (c) => check_range(c, 1, 5),
	"2/3": (c) => check_range(c, 2, 2),
	"2-4": (c) => check_range(c, 2, 4),
	"2-5": (c) => check_range(c, 2, 5),
	"2-6": (c) => check_range(c, 2, 6),
	"3/4": (c) => check_range(c, 3, 4),
	"3-5": (c) => check_range(c, 3, 5),
	"3-6": (c) => check_range(c, 3, 6),
	"4/5": (c) => check_range(c, 4, 5),
	"4-6": (c) => check_range(c, 4, 6),
	"5/6": (c) => check_range(c, 5, 6),
	"(1)/(2)": (c) => check_range(c, 1, 2),
	"(1)-(3)": (c) => check_range(c, 1, 3),
	"(1)-(4)": (c) => check_range(c, 1, 4),
	"(1)-(5)": (c) => check_range(c, 1, 5),
	"(2)/(3)": (c) => check_range(c, 2, 2),
	"(2)-(4)": (c) => check_range(c, 2, 4),
	"(2)-(5)": (c) => check_range(c, 2, 5),
	"(2)-(6)": (c) => check_range(c, 2, 6),
	"(3)/(4)": (c) => check_range(c, 3, 4),
	"(3)-(5)": (c) => check_range(c, 3, 5),
	"(3)-(6)": (c) => check_range(c, 3, 6),
	"(4)/(5)": (c) => check_range(c, 4, 5),
	"(4)-(6)": (c) => check_range(c, 4, 6),
	"(5)/(6)": (c) => check_range(c, 5, 6),
}

const place_dice_gen = {
	"Straight 3": gen_straight_3,
	"Straight 4": gen_straight_4,
	"Doubles": gen_doubles,
	"Triples": gen_triples,
	"1": (c) => gen_single(c, 1),
	"2": (c) => gen_single(c, 2),
	"3": (c) => gen_single(c, 3),
	"4": (c) => gen_single(c, 4),
	"5": (c) => gen_single(c, 5),
	"6": (c) => gen_single(c, 6),
	"(1)": (c) => gen_single(c, 1),
	"(2)": (c) => gen_single(c, 2),
	"(3)": (c) => gen_single(c, 3),
	"(4)": (c) => gen_single(c, 4),
	"(5)": (c) => gen_single(c, 5),
	"(6)": (c) => gen_single(c, 6),
	"Any": (c) => gen_range(c, 1, 6),
	"1/2": (c) => gen_range(c, 1, 2),
	"1-3": (c) => gen_range(c, 1, 3),
	"1-4": (c) => gen_range(c, 1, 4),
	"1-5": (c) => gen_range(c, 1, 5),
	"2/3": (c) => gen_range(c, 2, 2),
	"2-4": (c) => gen_range(c, 2, 4),
	"2-5": (c) => gen_range(c, 2, 5),
	"2-6": (c) => gen_range(c, 2, 6),
	"3/4": (c) => gen_range(c, 3, 4),
	"3-5": (c) => gen_range(c, 3, 5),
	"3-6": (c) => gen_range(c, 3, 6),
	"4/5": (c) => gen_range(c, 4, 5),
	"4-6": (c) => gen_range(c, 4, 6),
	"5/6": (c) => gen_range(c, 5, 6),
	"(1)/(2)": (c) => gen_range(c, 1, 2),
	"(1)-(3)": (c) => gen_range(c, 1, 3),
	"(1)-(4)": (c) => gen_range(c, 1, 4),
	"(1)-(5)": (c) => gen_range(c, 1, 5),
	"(2)/(3)": (c) => gen_range(c, 2, 2),
	"(2)-(4)": (c) => gen_range(c, 2, 4),
	"(2)-(5)": (c) => gen_range(c, 2, 5),
	"(2)-(6)": (c) => gen_range(c, 2, 6),
	"(3)/(4)": (c) => gen_range(c, 3, 4),
	"(3)-(5)": (c) => gen_range(c, 3, 5),
	"(3)-(6)": (c) => gen_range(c, 3, 6),
	"(4)/(5)": (c) => gen_range(c, 4, 5),
	"(4)-(6)": (c) => gen_range(c, 4, 6),
	"(5)/(6)": (c) => gen_range(c, 5, 6),
}

const place_dice_take = {
	"Straight 3": take_straight_3,
	"Straight 4": take_straight_4,
	"Doubles": take_doubles,
	"Triples": take_triples,
	"1": take_single,
	"2": take_single,
	"3": take_single,
	"4": take_single,
	"5": take_single,
	"6": take_single,
	"(1)": take_single,
	"(2)": take_single,
	"(3)": take_single,
	"(4)": take_single,
	"(5)": take_single,
	"(6)": take_single,
	"Any": (c, d) => take_single(c, d),
	"1/2": (c, d) => take_single(c, d),
	"1-3": (c, d) => take_single(c, d),
	"1-4": (c, d) => take_single(c, d),
	"1-5": (c, d) => take_single(c, d),
	"2/3": (c, d) => take_single(c, d),
	"2-4": (c, d) => take_single(c, d),
	"2-5": (c, d) => take_single(c, d),
	"2-6": (c, d) => take_single(c, d),
	"3/4": (c, d) => take_single(c, d),
	"3-5": (c, d) => take_single(c, d),
	"3-6": (c, d) => take_single(c, d),
	"4/5": (c, d) => take_single(c, d),
	"4-6": (c, d) => take_single(c, d),
	"5/6": (c, d) => take_single(c, d),
	"(1)/(2)": (c, d) => take_single(c, d),
	"(1)-(3)": (c, d) => take_single(c, d),
	"(1)-(4)": (c, d) => take_single(c, d),
	"(1)-(5)": (c, d) => take_single(c, d),
	"(2)/(3)": (c, d) => take_single(c, d),
	"(2)-(4)": (c, d) => take_single(c, d),
	"(2)-(5)": (c, d) => take_single(c, d),
	"(2)-(6)": (c, d) => take_single(c, d),
	"(3)/(4)": (c, d) => take_single(c, d),
	"(3)-(5)": (c, d) => take_single(c, d),
	"(3)-(6)": (c, d) => take_single(c, d),
	"(4)/(5)": (c, d) => take_single(c, d),
	"(4)-(6)": (c, d) => take_single(c, d),
	"(5)/(6)": (c, d) => take_single(c, d),
}

function can_place_dice(c) {

	let pattern = data.cards[c].dice
	if (!pattern)
		return false

	let pred = place_dice_check[pattern]
	if (!pred)
		throw Error("bad pattern definition: " + pattern)

	let wing = data.cards[c].wing
	let n_wing = 0
	for (let i = 0; i < game.placed.length; i += 2) {
		let x = game.placed[i]
		if (x !== c) {
			let i_wing = data.cards[x].wing
			if (i_wing === wing)
				n_wing ++
		}
	}
	if (n_wing >= game.place_max[wing])
		return false

	// TODO: 91A Jackson - may only place dice if D.H. Hill has dice

	if (place_dice_once[pattern]) {
		if (map_has(game.placed, c))
			return false
	}

	return pred(c)
}

function can_place_value(c, v) {
	let old_v = map_get(game.placed, c, 0)
	return old_v === 0 || old_v === v
}

function pool_has_single(v) {
	for (let i = 0; i < 6; ++i)
		if (is_pool_die(i, v))
			return true
	return false
}

function check_single_count(c, v, x) {
	if (!can_place_value(c, v))
		return false
	let n = 0
	for (let i = 0; i < 6; ++i)
		if (is_pool_die(i, v) && ++n >= x)
			return true
	return false
}

function check_single(c, v) {
	if (!can_place_value(c, v))
		return false
	for (let i = 0; i < 6; ++i)
		if (is_pool_die(i, v))
			return true
	return false
}

function check_range(c, lo, hi) {
	let old_v = map_get(game.placed, c, 0)
	if (old_v > 0)
		return pool_has_single(old_v)
	for (let i = 0; i < 6; ++i)
		if (is_pool_die_range(i, lo, hi))
			return true
	return false
}

function check_all_3(c, x, y, z) {
	if (!can_place_value(c, x))
		return false
	return pool_has_single(x) && pool_has_single(y) && pool_has_single(z)
}

function check_all_4(c, x, y, z, w) {
	if (!can_place_value(c, x))
		return false
	return pool_has_single(x) && pool_has_single(y) && pool_has_single(z) && pool_has_single(w)
}

function check_straight_3(c) {
	return (
		check_all_3(c, 1, 2, 3) ||
		check_all_3(c, 2, 3, 4) ||
		check_all_3(c, 3, 4, 5) ||
		check_all_3(c, 4, 5, 6)
	)
}

function check_straight_4(c) {
	return (
		check_all_4(c, 1, 2, 3, 4) ||
		check_all_4(c, 2, 3, 4, 5) ||
		check_all_4(c, 3, 4, 5, 6)
	)
}

function check_doubles(c) {
	return (
		check_single_count(c, 1, 2) ||
		check_single_count(c, 2, 2) ||
		check_single_count(c, 3, 2) ||
		check_single_count(c, 4, 2) ||
		check_single_count(c, 5, 2) ||
		check_single_count(c, 6, 2)
	)
}

function check_triples(c) {
	return (
		check_single_count(c, 1, 3) ||
		check_single_count(c, 2, 3) ||
		check_single_count(c, 3, 3) ||
		check_single_count(c, 4, 3) ||
		check_single_count(c, 5, 3) ||
		check_single_count(c, 6, 3)
	)
}

function gen_pool_die(v) {
	let p = player_index()
	for (let i = 0; i < 6; ++i)
		if (get_player_dice_location(p, i) < 0 && get_player_dice_value(p, i) === v)
			gen_action_die(p * 6 + i)
}

function gen_single(c, v) {
	if (!can_place_value(c, v))
		return false
	gen_pool_die(v)
}

function gen_range(c, lo, hi) {
	for (let v = lo; v <= hi; ++v)
		gen_single(c, v)
}

function gen_straight_3(c) {
	if (check_all_3(c, 1, 2, 3))
		gen_pool_die(1)
	if (check_all_3(c, 2, 3, 4))
		gen_pool_die(2)
	if (check_all_3(c, 3, 4, 5))
		gen_pool_die(3)
	if (check_all_3(c, 4, 5, 6))
		gen_pool_die(4)
}

function gen_straight_4(c) {
	if (check_all_4(c, 1, 2, 3, 4))
		gen_pool_die(1)
	if (check_all_4(c, 2, 3, 4, 5))
		gen_pool_die(2)
	if (check_all_4(c, 3, 4, 5, 6))
		gen_pool_die(3)
}

function gen_doubles(c) {
	for (let v = 1; v <= 6; ++v)
		if (check_single_count(c, v, 2))
			gen_pool_die(v)
}

function gen_triples(c) {
	for (let v = 1; v <= 6; ++v)
		if (check_single_count(c, v, 3))
			gen_pool_die(v)
}

function find_and_take_single(c, v) {
	let p = player_index()
	for (let i = 0; i < 6; ++i) {
		if (get_player_dice_location(p, i) < 0 && get_player_dice_value(p, i) === v) {
			set_player_dice_location(p, i, c)
			return
		}
	}
	throw new Error("cannot find die of value " + v)
}

function take_single(c, d) {
	set_dice_location(d, c)
	map_set(game.placed, c, get_dice_value(d))
}

function take_doubles(c, d) {
	let v = get_dice_value(d)
	take_single(c, d)
	find_and_take_single(c, v)
}

function take_triples(c, d) {
	let v = get_dice_value(d)
	take_single(c, d)
	find_and_take_single(c, v)
	find_and_take_single(c, v)
}

function take_straight_3(c, d) {
	let v = get_dice_value(d)
	take_single(c, d)
	find_and_take_single(c, v+1)
	find_and_take_single(c, v+2)
}

function take_straight_4(c, d) {
	let v = get_dice_value(d)
	take_single(c, d)
	find_and_take_single(c, v+1)
	find_and_take_single(c, v+2)
	find_and_take_single(c, v+3)
}

function goto_roll_phase() {
	game.selected = -1
	game.target = -1
	game.action = 0
	game.state = "roll"

	game.place_max = [ 1, 1, 1, 1 ]

	let p = player_index()
	for (let c of game.front[p]) {
		if (card_has_rule(c, "place_2_blue"))
			game.place_max[BLUE] = 2
		if (card_has_rule(c, "place_2_red"))
			game.place_max[RED] = 2
	}
}

states.roll = {
	prompt() {
		view.prompt = "Roll the dice in your pool."
		view.actions.roll = 1
	},
	roll() {
		clear_undo()
		roll_dice_in_pool()
	},
}

function roll_dice_in_pool() {
	let p = player_index()
	for (let i = 0; i < 6; ++i)
		if (get_player_dice_location(p, i) < 0)
			set_player_dice_value(p, i, random(6) + 1)
	game.state = "place"
}

function gen_place_dice_select_card() {
	let p = player_index()
	for (let c of game.front[p]) {
		if (c === game.selected)
			continue
		if (can_place_dice(c))
			gen_action_card(c)
	}
}

states.place = {
	prompt() {
		view.prompt = "Place dice on your formations."
		gen_place_dice_select_card()
		view.actions.end_turn = 1
	},
	card(c) {
		push_undo()
		game.selected = c
		game.state = "place_on_card"
	},
	end_turn() {
		end_roll_phase()
	},
}

states.place_on_card = {
	prompt() {
		let card = data.cards[game.selected]
		view.prompt = "Place dice on " + card.name + "."

		gen_place_dice_select_card()

		place_dice_gen[card.dice](game.selected)

		view.actions.end_turn = 1
	},
	card(c) {
		if (c === game.selected) {
			game.selected = -1
			game.state = "place"
		} else {
			game.selected = c
			game.state = "place_on_card"
		}
	},
	die(d) {
		push_undo()
		place_dice_take[data.cards[game.selected].dice](game.selected, d)
		if (!can_place_dice(game.selected)) {
			game.selected = -1
			game.state = "place"
		}
	},
	end_turn() {
		end_roll_phase()
	},
}

function end_roll_phase() {
	clear_undo()
	map_clear(game.placed)
	game.place_max = null

	// Remove placed dice to add cube on special cards.
	for (let c of game.front[player_index()]) {
		let s = data.cards[c].special
		if (s && has_any_dice_on_card(c)) {
			map_set(game.cubes, c, Math.min(s, map_get(game.cubes, c, 0) + 1))
			remove_dice(c)
		}
	}

	// Blank out unused dice.
	let p = player_index()
	for (let i = 0; i < 6; ++i)
		if (get_player_dice_location(p, i) < 0)
			set_player_dice_value(p, i, 0)

	set_opponent_active()

	goto_action_phase()
}

// === ACTION PHASE ===

function has_any_dice_on_card(c) {
	for (let i = 0; i < 12; ++i)
		if (get_dice_location(i) === c)
			return true
	return false
}

function has_any_cubes_on_card(c) {
	return map_get(game.cubes, c, 0) >= 1
}

function count_dice_on_card(c) {
	let n = 0
	for (let i = 0; i < 12; ++i)
		if (get_dice_location(i) === c)
			++n
	return n
}

function count_dice_on_card_with_value(c, v) {
	let n = 0
	for (let i = 0; i < 12; ++i)
		if (get_dice_location(i) === c && get_dice_value(i) === v)
			++n
	return n
}

function require_pair(c) {
	for (let v = 1; v <= 6; ++v)
		if (count_dice_on_card_with_value(c, v) >= 2)
			return true
	return false
}

function require_triplet(c) {
	for (let v = 1; v <= 6; ++v)
		if (count_dice_on_card_with_value(c, v) >= 3)
			return true
	return false
}

function require_full_house(c) {
	let n3 = 0
	let n2 = 0
	for (let v = 1; v <= 6; ++v) {
		let n = count_dice_on_card_with_value(c, v)
		if (n >= 3)
			++n3
		else if (n >= 2)
			++n2
	}
	return (n3 >= 2) || (n3 >= 1 && n2 >= 1)
}

function require_two_pairs(c) {
	let n = 0
	for (let v = 1; v <= 6; ++v)
		if (count_dice_on_card_with_value(c, v) >= 2)
			++n
	return n >= 2
}

function check_cube_requirement(c, req) {
	switch (req) {
		case "3 cubes":
			return map_get(game.cubes, c, 0) >= 3
		case "Voluntary":
		case undefined:
			return map_get(game.cubes, c, 0) >= 1
		default:
			throw new Error("invalid action requirement: " + req)
	}
}

function check_dice_requirement(c, req) {
	switch (req) {
		case "Full House":
			return require_full_house(c)
		case "Pair":
		case "Pair, Voluntary":
			return require_pair(c)
		case "Triplet":
			return require_triplet(c)
		case "Two Pairs":
			return require_two_pairs(c)
		case "Voluntary":
		case undefined:
			return has_any_dice_on_card(c)
		default:
			throw new Error("invalid action requirement: " + req)
	}
}

function is_action(c, a) {
	return (a.type === "Bombard" || a.type === "Attack" || a.type === "Command")
}

function is_reaction(c, a) {
	return (a.type === "Screen" || a.type === "Counterattack" || a.type === "Absorb")
}

function is_mandatory_reaction(c, a) {
	return (
		a.requirement !== "Voluntary" &&
		a.requirement !== "Pair, Voluntary"
	)
}

function can_take_action(c, a) {
	if (a.type === "Attack" && find_target_of_attack(a) < 0)
		return false
	if (a.type === "Command" && find_target_of_command(a) < 0)
		return false

	// TODO: 38B Clinton (can only attack if other cards have dice)
	// TODO: 91A Jackson - may only attack if D.H. Hill and one other formation have dice

	if (a.type === "Bombard" || a.type === "Attack" || a.type === "Command") {
		if (data.cards[c].special)
			return check_cube_requirement(c, a.requirement)
		else
			return check_dice_requirement(c, a.requirement)
	}
	return false
}

function can_take_any_action() {
	let p = player_index()
	for (let c of game.front[p]) {
		if (has_any_dice_on_card(c))
			return true
		if (has_any_cubes_on_card(c)) // TODO: check requirements!
			return true
	}
	return false
}

function goto_action_phase() {
	if (check_impossible_to_attack_victory()) {
		if (player_index() === 0)
			goto_game_over(P2, P1 + " has no more attacks!")
		else
			goto_game_over(P1, P2 + " has no more attacks!")
		return
	}

	if (game.reacted) {
		game.reacted = 0
		goto_roll_phase()
	} else {
		if (can_take_any_action())
			game.state = "action"
		else
			goto_roll_phase()
	}
}

function end_action_phase() {
	// TODO: 38A: the stanleys -- rout Northumberland
	goto_routing()
}

states.action = {
	prompt() {
		view.prompt = "Take an action."
		view.actions.roll = 1

		let p = player_index()
		for (let c of game.front[p]) {
			let has_dice = has_any_dice_on_card(c)
			let has_cube = has_any_cubes_on_card(c)
			if (has_dice || has_cube) {
				if (data.cards[c].actions.length >= 1) {
					if (is_action(c, data.cards[c].actions[0])) {
						if (can_take_action(c, data.cards[c].actions[0]))
							gen_action_action1(c)
						else if (has_dice)
							gen_action_fizzle1(c)
					}
				}
				if (data.cards[c].actions.length >= 2) {
					if (is_action(c, data.cards[c].actions[1])) {
						if (can_take_action(c, data.cards[c].actions[1]))
							gen_action_action2(c)
						else if (has_dice)
							gen_action_fizzle2(c)
					}
				}
				if (data.cards[c].retire)
					gen_action_retire(c)
			}
		}
	},
	retire(c) {
		push_undo()
		log(card_name(c) + " retired.")
		eliminate_card(c)
		end_action_phase()
	},
	a1(c) {
		push_undo()
		goto_take_action(c, 0)
	},
	a2(c) {
		push_undo()
		goto_take_action(c, 1)
	},
	f1(c) {
		push_undo()
		goto_fizzle(c)
	},
	f2(c) {
		push_undo()
		goto_fizzle(c)
	},
	roll() {
		push_undo()
		goto_roll_phase()
		roll_dice_in_pool()
	},
}

function goto_fizzle(c) {
	log("Fizzled " + card_number(c))
	pay_for_action(c)
	end_action_phase()
}

function goto_take_action(c, ix) {
	let a = data.cards[c].actions[ix]
	game.selected = c
	game.action = ix
	switch (a.type) {
		case "Attack":
			goto_attack()
			break
		case "Bombard":
			game.state = "bombard"
			break
		case "Command":
			game.state = "command"
			break
	}
}

function current_action() {
	return data.cards[game.selected].actions[game.action]
}

function find_target_of_attack(a) {
	for (let c of a.target_list) {
		if (set_has(game.front[0], c))
			return c
		if (set_has(game.front[1], c))
			return c
	}
	return -1
}

function find_target_of_command(a) {
	for (let c of a.target_list) {
		if (set_has(game.reserve[0], c))
			return c
		if (set_has(game.reserve[1], c))
			return c
	}
}

states.bombard = {
	prompt() {
		view.prompt = "Bombard."
		view.actions.bombard = 1
	},
	bombard() {
		log(card_name(game.selected) + " bombarded.")
		let opp = 1 - player_index()
		game.morale[opp] --
		pay_for_action(game.selected)
		end_action_phase()
	},
}

function goto_attack() {
	let a = current_action()

	// TODO: 88B German Infantry - take dice from Saxon Infantry

	game.state = "attack"
	game.target = find_target_of_attack(a)
	game.hits = get_attack_hits(game.selected, a)
	game.self = get_attack_self(game.selected, a)

	// TODO: 17A: rupert's lifeguard (one less hit)

	if (card_has_rule("suffer_1_less_1_max"))
		game.hits = Math.max(0, Math.min(1, game.hits - 1))
}

states.attack = {
	prompt() {
		view.prompt = "Attack " + card_name(game.target) + "."
		gen_action_card(game.target)
		view.actions.attack = 1
	},
	attack() {
		log(card_name(game.selected) + " attacked " + card_name(game.target) + ".")
		if (can_opponent_react()) {
			clear_undo()
			set_opponent_active()
			game.state = "react"
		} else {
			resume_attack()
		}
	},
	card(_) {
		this.attack()
	},
}

function resume_attack() {
	apply_hits(game.hits)
	apply_self(game.self)
	pay_for_action(game.selected)

	game.hits = game.self = 0
	game.selected = -1
	game.target = -1
	end_action_phase()
}

states.command = {
	prompt() {
		let t = find_target_of_command(current_action())
		view.prompt = "Bring " + card_name(t) + " out of reserve."
		gen_action_card(t)
	},
	card(c) {
		log(card_name(game.selected) + " commanded " + card_name(c) + " out of reserve.")
		let p = player_index()
		set_delete(game.reserve[p], c)
		set_add(game.front[p], c)
		pay_for_action(game.selected)
		end_action_phase()
	},
}

// === REACTION ===

function can_opponent_react() {
	let p = 1 - player_index()
	for (let c of game.front[p])
		if (can_card_react(c))
			return true
	return false
}

function can_card_react(c) {
	let has_dice = has_any_dice_on_card(c)
	let has_cube = has_any_cubes_on_card(c)
	if (has_dice || has_cube) {
		if (data.cards[c].actions.length >= 1)
			if (is_reaction(c, data.cards[c].actions[0]))
				if (can_take_reaction(c, data.cards[c].actions[0]))
					return true
		if (data.cards[c].actions.length >= 2)
			if (is_reaction(c, data.cards[c].actions[1]))
				if (can_take_reaction(c, data.cards[c].actions[1]))
					return true
	}
	return false
}

function can_take_reaction(c, a) {
	switch (a.type) {
	default:
		throw new Error("invalid reaction: " + a.type)
	case "Screen":
		// if a friendly formation is attacked by a listed enemy formation
		// ... or a listed formation is attacked (Wheatfield Road Artillery, etc)
		if (!a.target_list.includes(game.selected) && !a.target_list.includes(game.target))
			return false
		break
	case "Counterattack":
		// if this formation is attacked
		if (game.target !== c)
			return false
		// ... by one of the listed targets
		if (!a.target_list.includes(game.selected))
			return false
		break
	case "Absorb":
		// if attack target is listed on absorb action
		if (!a.target_list.includes(game.target))
			return false
		break
	}

	// TODO: 21B The English Fleet (if cubes on card, duan juan jose cannot counterattack)
	// TODO: 21B The English Fleet (if cubes on card, spanish right cav cannot screen)

	if (data.cards[c].special)
		return check_cube_requirement(c, a.requirement)
	else
		return check_dice_requirement(c, a.requirement)
}

states.react = {
	prompt() {
		view.prompt = card_name(game.selected) + " attacks " + card_name(game.target) + "!"

		let voluntary = true
		let p = player_index()
		for (let c of game.front[p]) {
			let has_dice = has_any_dice_on_card(c)
			let has_cube = has_any_cubes_on_card(c)
			if (has_dice || has_cube) {
				if (data.cards[c].actions.length >= 1) {
					if (is_reaction(c, data.cards[c].actions[0])) {
						if (can_take_reaction(c, data.cards[c].actions[0])) {
							if (is_mandatory_reaction(c, data.cards[c].actions[0]))
								voluntary = false
							gen_action_action1(c)
						}
					}
				}
				if (data.cards[c].actions.length >= 2) {
					if (is_reaction(c, data.cards[c].actions[1])) {
						if (can_take_reaction(c, data.cards[c].actions[1])) {
							if (is_mandatory_reaction(c, data.cards[c].actions[1]))
								voluntary = false
							gen_action_action2(c)
						}
					}
				}
			}
		}

		if (voluntary)
			view.actions.pass = 1
	},
	a1(c) {
		push_undo()
		goto_take_reaction(c, 0)
	},
	a2(c) {
		push_undo()
		goto_take_reaction(c, 1)
	},
	pass() {
		set_opponent_active()
		resume_attack()
	},
}

function goto_take_reaction(c, ix) {
	let a = data.cards[c].actions[ix]
	switch (a.type) {
		case "Screen":
			goto_screen(c, a)
			break
		case "Absorb":
			goto_absorb(c, a)
			break
		case "Counterattack":
			goto_counterattack(c, a)
			break
	}
}

function end_reaction() {
	set_opponent_active()
	resume_attack()
}

// === SCREEN ===

function goto_screen(c, a) {
	game.reacted = 1

	game.target = c

	switch (a.effect)
	{
	default:
		throw new Error("invalid screen effect: " + a.effect)
	case undefined:
		game.hits = 0
		game.self = 0
		break
	}

	game.state = "screen"
}

states.screen = {
	prompt() {
		view.prompt = "Screen attack from " + card_name(game.selected) + "."
		view.actions.screen = 1
	},
	screen() {
		log(card_name(game.target) + " screened.")
		pay_for_action(game.target)

		if (card_has_rule(game.target, "remove_after_screen"))
			eliminate_card(game.target)

		end_reaction()
	},
}

// === ABSORB ===

function goto_absorb(c, a) {
	game.reacted = 1

	game.target = c

	switch (a.effect)
	{
	default:
		throw new Error("invalid absorb effect: " + a.effect)
	case "When target suffers Hits, this card suffers them instead.":
		break
	case "When target suffers Hits, this card suffers 1 hit ONLY instead.":
		game.hits = 1
		break
	case "When target suffers Hits, this card suffers 1 less hit per die.":
		game.hits = Math.max(0, game.hits - count_dice_on_card(c))
		break
	}

	game.state = "absorb"
}

states.absorb = {
	prompt() {
		view.prompt = "Absorb attack from " + card_name(game.selected) + "."
		view.actions.absorb = 1
	},
	absorb() {
		log(card_name(game.target) + " absorbed.")
		pay_for_action(game.target)
		end_reaction()
	},
}

// === COUNTERATTACK ===

function goto_counterattack(c, a) {
	game.reacted = 1

	switch (a.effect)
	{
	default:
		throw new Error("invalid counterattack effect: " + a.effect)
	case "1 hit per die.":
		game.self += count_dice_on_card(c)
		break
	case "1 hit.":
		game.self += 1
		break
	case "1 hit. Additionally, this unit only suffers one hit.":
		game.self += 1
		game.hits = 1
		break
	case "1 hit. Additionally, this unit suffers one less hit per die.":
		game.self += 1
		game.hits = Math.max(0, game.hits - count_dice_on_card(c))
		break
	case "1 hit. Additionally, this unit suffers one less hit.":
		game.self += 1
		game.hits -= 1
		break
	case "This unit suffers ONE less hit and never more than one.":
		game.self += 1
		game.hits = Math.max(0, Math.min(1, game.hits - 1))
		break
	case "This unit suffers TWO less hits and never more than one.":
		game.self += 1
		game.hits = Math.max(0, Math.min(1, game.hits - 2))
		break
	}

	game.state = "counterattack"
}

states.counterattack = {
	prompt() {
		view.prompt = "Counterattack " + card_name(game.selected) + "."
		view.actions.counterattack = 1
	},
	counterattack() {
		log(card_name(game.target) + " counterattacked.")
		pay_for_action(game.target)
		end_reaction()
	},
}

// === ATTACK EFFECTS ===

function apply_self(n) {
	remove_sticks(game.selected, n)
}

function apply_hits(n) {
	remove_sticks(game.target, n)
}

function get_attack_hits(c, a) {
	switch (a.effect) {
		default:
			throw new Error("invalid attack effect: " + a.effect)
		case "1 hit.":
		case "1 hit. 1 self per action.":
			return 1
		case "1 hit per die.":
		case "1 hit per die. 1 self per action.":
			return count_dice_on_card(c)
		case "1 hit per pair.":
		case "1 hit per pair. 1 self per action.":
			return count_dice_on_card(c) >> 1
		case "1 hit, PLUS 1 hit per die. 1 self per action.":
			return 1 + count_dice_on_card(c)
	}
}

function get_attack_self(c, a) {
	switch (a.effect) {
		default:
			throw new Error("invalid attack effect: " + a.effect)
		case "1 hit.":
		case "1 hit per die.":
		case "1 hit per pair.":
			return 0
		case "1 hit. 1 self per action.":
		case "1 hit per die. 1 self per action.":
		case "1 hit per pair. 1 self per action.":
		case "1 hit, PLUS 1 hit per die. 1 self per action.":
			return 1
	}
}

// === ROUTING ===

function should_remove_card(c) {
	// TODO: remove after X routs special rules
	return false
}

function should_rout_card(c) {
	// TODO: rout after X routs special rules
	if (!data.cards[c].special)
		if (map_get(game.sticks, c, 0) === 0)
			return true
	return false
}

function goto_routing() {
	game.routed = [ 0, 0 ]

	// TODO: 17A: rupert's lifeguard (cancel rout)

	resume_routing()
}

function resume_routing() {
	game.state = "routing"
	for (let p = 0; p <= 1; ++p)
		for (let c of game.front[p])
			if (should_rout_card(c) || should_remove_card(c))
				return
	end_routing()
}

function end_routing() {
	// Normal morale loss and gain
	if (game.morale[0] > 0 && game.morale[1] > 0) {
		if ((game.routed[0] > 0 && !game.routed[1]) || (game.routed[1] > 0 && !game.routed[0])) {
			if (game.routed[0]) {
				game.routed[0] = Math.min(game.routed[0], game.morale[0])
				game.morale[0] -= game.routed[0]
				// do not gain for special scenarios
				if (game.morale[1] > 0)
					game.morale[1] += game.routed[0]
			} else {
				game.routed[1] = Math.min(game.routed[1], game.morale[1])
				game.morale[1] -= game.routed[1]
				// do not gain for special scenarios
				if (game.morale[0] > 0)
					game.morale[0] += game.routed[1]
			}
		}
		if (game.morale[0] === 0)
			return goto_game_over(P2, P1 + " has run out of morale!")
		if (game.morale[1] === 0)
			return goto_game_over(P1, P2 + " has run out of morale!")
	} else {
		// SPECIAL: S3 - Plains of Abraham
		// SPECIAL: S34 - Tippermuir - Royalists
		// SPECIAL: S35 - Auldearn - Royalists

		// Instant loss if any card routs for side at 0 morale (S3, S34, S35).
		if (game.morale[0] === 0 && game.routed[0])
			return goto_game_over(P2, P1 + " card routed!")
		if (game.morale[1] === 0 && game.routed[1])
			return goto_game_over(P1, P2 + " card routed!")

		// Remove instead of take cubes for side at 0 morale
		if (game.routed[0]) {
			game.morale[0] -= Math.min(game.routed[0], game.morale[0])
			if (game.morale[0] === 0)
				return goto_game_over(P2, P1 + " has run out of morale!")
		}
		if (game.routed[1]) {
			game.morale[1] -= Math.min(game.routed[1], game.morale[1])
			if (game.morale[1] === 0)
				return goto_game_over(P1, P2 + " has run out of morale!")
		}
	}

	game.routed = null

	goto_pursuit()
}

function find_card_owner(c) {
	if (set_has(game.front[0], c) || set_has(game.reserve[0], c))
		return 0
	if (set_has(game.front[1], c) || set_has(game.reserve[1], c))
		return 1
	throw new Error("card not found in any player area")
}

states.routing = {
	prompt() {
		view.prompt = "Rout cards with no remaining sticks!"
		for (let p = 0; p <= 1; ++p)
			for (let c of game.front[p])
				if (should_rout_card(c) || should_remove_card(c))
					gen_action_card(c)
	},
	card(c) {
		if (should_rout_card(c)) {
			log(card_name(c) + " routed.")
			let p = find_card_owner(c)
			if (data.cards[c].star)
				game.routed[p] = 2
			else
				game.routed[p] = 1
		} else {
			log(card_name(c) + " removed.")
		}
		eliminate_card(c)
		resume_routing()
	},
}

// === PURSUIT ===

function should_pursue(c) {
	let pursuit = data.cards[c].pursuit
	if (pursuit !== undefined)
		return !set_has(game.front[0], pursuit) && !set_has(game.front[1], pursuit)
	return false
}

function goto_pursuit() {
	resume_pursuit()
}

function resume_pursuit() {
	game.state = "pursuit"
	for (let p = 0; p <= 1; ++p)
		for (let c of game.front[p])
			if (should_pursue(c))
				return
	end_pursuit()
}

function end_pursuit() {
	goto_reserve()
}

states.pursuit = {
	prompt() {
		view.prompt = "Pursue cards!"
		for (let p = 0; p <= 1; ++p)
			for (let c of game.front[p])
				if (should_pursue(c))
					gen_action_card(c)
	},
	card(c) {
		log(card_name(c) + " pursued.")
		eliminate_card(c)
		resume_pursuit()
	},
}

// === RESERVE ===

function should_enter_reserve(rc) {
	let reserve = data.cards[rc].reserve
	for (let c of reserve)
		if (!set_has(game.front[0], c) && !set_has(game.front[1], c))
			return true
	return false
}

function goto_reserve() {
	resume_reserve()
}

function resume_reserve() {
	game.state = "reserve"
	for (let p = 0; p <= 1; ++p)
		for (let c of game.reserve[p])
			if (should_enter_reserve(c))
				return
	end_reserve()
}

function end_reserve() {
	goto_roll_phase()
}


states.reserve = {
	prompt() {
		view.prompt = "Enter reserves!"
		for (let p = 0; p <= 1; ++p)
			for (let c of game.reserve[p])
				if (should_enter_reserve(c))
					gen_action_card(c)
	},
	card(c) {
		log(card_name(c) + " came out of reserve.")
		let p = find_card_owner(c)
		set_delete(game.reserve[p], c)
		set_add(game.front[p], c)
		resume_reserve()
	},
}

// === COMMON LIBRARY ===

function gen_action(action, argument) {
	if (!(action in view.actions))
		view.actions[action] = [ argument ]
	else
		set_add(view.actions[action], argument)
}

function gen_action_card(c) {
	gen_action("card", c)
}

function gen_action_die(d) {
	gen_action("die", d)
}

function gen_action_action1(c) {
	gen_action("a1", c)
}

function gen_action_action2(c) {
	gen_action("a2", c)
}

function gen_action_fizzle1(c) {
	gen_action("f1", c)
}

function gen_action_fizzle2(c) {
	gen_action("f2", c)
}

function gen_action_retire(c) {
	gen_action("retire", c)
}

function log(msg) {
	game.log.push(msg)
}

function clear_undo() {
	if (game.undo) {
		game.undo.length = 0
	}
}

function push_undo() {
	if (game.undo) {
		let copy = {}
		for (let k in game) {
			let v = game[k]
			if (k === "undo")
				continue
			else if (k === "log")
				v = v.length
			else if (typeof v === "object" && v !== null)
				v = object_copy(v)
			copy[k] = v
		}
		game.undo.push(copy)
	}
}

function pop_undo() {
	if (game.undo) {
		let save_log = game.log
		let save_undo = game.undo
		game = save_undo.pop()
		save_log.length = game.log
		game.log = save_log
		game.undo = save_undo
	}
}

function random(range) {
	// Largest MLCG that will fit its state in a double.
	// Uses BigInt for arithmetic, so is an order of magnitude slower.
	// https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf
	// m = 2**53 - 111
	return (game.seed = Number(BigInt(game.seed) * 5667072534355537n % 9007199254740881n)) % range
}

// Fast deep copy for objects without cycles
function object_copy(original) {
	if (Array.isArray(original)) {
		let n = original.length
		let copy = new Array(n)
		for (let i = 0; i < n; ++i) {
			let v = original[i]
			if (typeof v === "object" && v !== null)
				copy[i] = object_copy(v)
			else
				copy[i] = v
		}
		return copy
	} else {
		let copy = {}
		for (let i in original) {
			let v = original[i]
			if (typeof v === "object" && v !== null)
				copy[i] = object_copy(v)
			else
				copy[i] = v
		}
		return copy
	}
}

// Array remove and insert (faster than splice)

function array_remove(array, index) {
	let n = array.length
	for (let i = index + 1; i < n; ++i)
		array[i - 1] = array[i]
	array.length = n - 1
}

function array_insert(array, index, item) {
	for (let i = array.length; i > index; --i)
		array[i] = array[i - 1]
	array[index] = item
}

function array_insert_pair(array, index, key, value) {
	for (let i = array.length; i > index; i -= 2) {
		array[i] = array[i-2]
		array[i+1] = array[i-1]
	}
	array[index] = key
	array[index+1] = value
}

// Set as plain sorted array

function set_has(set, item) {
	let a = 0
	let b = set.length - 1
	while (a <= b) {
		let m = (a + b) >> 1
		let x = set[m]
		if (item < x)
			b = m - 1
		else if (item > x)
			a = m + 1
		else
			return true
	}
	return false
}

function set_add(set, item) {
	let a = 0
	let b = set.length - 1
	while (a <= b) {
		let m = (a + b) >> 1
		let x = set[m]
		if (item < x)
			b = m - 1
		else if (item > x)
			a = m + 1
		else
			return
	}
	array_insert(set, a, item)
}

function set_delete(set, item) {
	let a = 0
	let b = set.length - 1
	while (a <= b) {
		let m = (a + b) >> 1
		let x = set[m]
		if (item < x)
			b = m - 1
		else if (item > x)
			a = m + 1
		else {
			array_remove(set, m)
			return
		}
	}
}

// Map as plain sorted array of key/value pairs

function map_clear(map) {
	map.length = 0
}

function map_has(map, key) {
	let a = 0
	let b = (map.length >> 1) - 1
	while (a <= b) {
		let m = (a + b) >> 1
		let x = map[m<<1]
		if (key < x)
			b = m - 1
		else if (key > x)
			a = m + 1
		else
			return true
	}
	return false
}

function map_get(map, key, missing) {
	let a = 0
	let b = (map.length >> 1) - 1
	while (a <= b) {
		let m = (a + b) >> 1
		let x = map[m<<1]
		if (key < x)
			b = m - 1
		else if (key > x)
			a = m + 1
		else
			return map[(m<<1)+1]
	}
	return missing
}

function map_set(map, key, value) {
	let a = 0
	let b = (map.length >> 1) - 1
	while (a <= b) {
		let m = (a + b) >> 1
		let x = map[m<<1]
		if (key < x)
			b = m - 1
		else if (key > x)
			a = m + 1
		else {
			map[(m<<1)+1] = value
			return
		}
	}
	array_insert_pair(map, a<<1, key, value)
}