"use strict"

// TODO: barbarian leaders -> barbarian list

/*
TODO
----

[x] crisis ira deorum
[x] crisis barbarians
[ ] crisis pax deorum

[x] tribute
[ ] foederati
[ ] mobs

[ ] disperse mob

[ ] combat victory
[ ] combat retreat out of capital
[ ] combat retreat barbarians to homeland
[ ] combat advance into capital
[ ] combat flanking maneuver

[x] quaestor
	[x] place
	[x] remove at start
	[x] remove when replaced

[ ] castra
	[x] place
	[x] remove at start
	[x] remove when move/attack
	[ ] take hits in battle

[ ] support check

[ ] gain legacy
	[ ] emperor
	[ ] provinces
	[ ] improvements

[ ] end turn
	[ ] grow mobs
	[ ] flip barbarians

[ ] praetorian guard
[ ] damnatio memoriae

[ ] pretender
	[ ] place
	[ ] expand
	[ ] scoring effects
	[ ] occupation effects

[ ] game end

[ ] rival emperors
	[ ] emperor turns
	[ ] combat
	[ ] support check
	[ ] combat bonus
	[ ] buy/trash bonus

[ ] barbarian leaders
	[ ] invasion
	[ ] combat bonus
	[ ] combat effect
	[ ] buy/trash bonus

[ ] other events

*/

var game
var view
const states = {}

const P1 = "Red"
const P2 = "Blue"
const P3 = "Yellow"
const P4 = "Green"

exports.scenarios = [ "Standard" ]

exports.roles = function (scenario, options) {
	if (options.players == 1)
		return [ "Solo" ]
	if (options.players == 2)
		return [ P1, P2 ]
	if (options.players == 3)
		return [ P1, P2, P3 ]
	return [ P1, P2, P3, P4 ]
}

// === CONSTANTS ===

const PLAYER_NAMES = [ P1, P2, P3, P4 ]

const PLAYER_INDEX = {
	[P1]: 0,
	[P2]: 1,
	[P3]: 2,
	[P4]: 3,
	"Solo": 4,
	"Observer": -1,
}

const MILITARY = 0
const SENATE = 1
const POPULACE = 2

const LEGION_COUNT = 33

// REGIONS

const ITALIA = 0
const ASIA = 1
const GALLIA = 2
const MACEDONIA = 3
const PANNONIA = 4
const THRACIA = 5
const AEGYPTUS = 6
const AFRICA = 7
const HISPANIA = 8
const BRITANNIA = 9
const GALATIA = 10
const SYRIA = 11
const ALAMANNI_HOMELAND = 12
const FRANKS_HOMELAND = 13
const GOTHS_HOMELAND = 14
const NOMADS_HOMELAND = 15
const SASSANIDS_HOMELAND = 16
const MARE_OCCIDENTALE = 17
const MARE_ORIENTALE = 18
const OCEANUS_ATLANTICUS = 19
const PONTUS_EUXINUS = 20
const AVAILABLE = 21
const UNAVAILABLE = 22
const ARMY = 23

const REGION_NAME = [
	"Italia",
	"Asia",
	"Gallia",
	"Macedonia",
	"Pannonia",
	"Thracia",
	"Aegyptus",
	"Africa",
	"Hispania",
	"Britannia",
	"Galatia",
	"Syria",
	"Alamanni Homeland",
	"Franks Homeland",
	"Goths Homeland",
	"Nomads Homeland",
	"Sassanids Homeland",
	"Mare Occidentale",
	"Mare Orientale",
	"Oceanus Atlanticus",
	"Pontus Euxinus",
	"Available",
	"Unavailable",
]

const ADJACENT = [
	/* ITALIA */ [ GALLIA, PANNONIA, MARE_OCCIDENTALE ],
	/* ASIA */ [ THRACIA, GALATIA, MARE_ORIENTALE, PONTUS_EUXINUS ],
	/* GALLIA */ [ ITALIA, PANNONIA, HISPANIA, FRANKS_HOMELAND, MARE_OCCIDENTALE, OCEANUS_ATLANTICUS ],
	/* MACEDONIA */ [ PANNONIA, THRACIA, MARE_OCCIDENTALE, MARE_ORIENTALE ],
	/* PANNONIA */ [ ITALIA, GALLIA, MACEDONIA, THRACIA, ALAMANNI_HOMELAND, FRANKS_HOMELAND, MARE_OCCIDENTALE ],
	/* THRACIA */ [ ASIA, MACEDONIA, PANNONIA, ALAMANNI_HOMELAND, GOTHS_HOMELAND, MARE_ORIENTALE, PONTUS_EUXINUS ],
	/* AEGYPTUS */ [ AFRICA, SYRIA, NOMADS_HOMELAND, MARE_ORIENTALE ],
	/* AFRICA */ [ AEGYPTUS, HISPANIA, NOMADS_HOMELAND, MARE_OCCIDENTALE, MARE_ORIENTALE, OCEANUS_ATLANTICUS ],
	/* HISPANIA */ [ GALLIA, AFRICA, MARE_OCCIDENTALE, OCEANUS_ATLANTICUS ],
	/* BRITANNIA */ [ OCEANUS_ATLANTICUS ],
	/* GALATIA */ [ ASIA, SYRIA, SASSANIDS_HOMELAND, MARE_ORIENTALE, PONTUS_EUXINUS ],
	/* SYRIA */ [ AEGYPTUS, GALATIA, SASSANIDS_HOMELAND, MARE_ORIENTALE ],
	/* ALAMANNI_HOMELAND */ [ PANNONIA, THRACIA, FRANKS_HOMELAND, GOTHS_HOMELAND ],
	/* FRANKS_HOMELAND */ [ GALLIA, PANNONIA, ALAMANNI_HOMELAND ],
	/* GOTHS_HOMELAND */ [ THRACIA, ALAMANNI_HOMELAND, PONTUS_EUXINUS ],
	/* NOMADS_HOMELAND */ [ AEGYPTUS, AFRICA, OCEANUS_ATLANTICUS ],
	/* SASSANIDS_HOMELAND */ [ GALATIA, SYRIA, PONTUS_EUXINUS ],
	/* MARE_OCCIDENTALE */ [ ITALIA, GALLIA, MACEDONIA, PANNONIA, AFRICA, HISPANIA, MARE_ORIENTALE, OCEANUS_ATLANTICUS ],
	/* MARE_ORIENTALE */ [ ASIA, MACEDONIA, THRACIA, AEGYPTUS, AFRICA, GALATIA, SYRIA, MARE_OCCIDENTALE ],
	/* OCEANUS_ATLANTICUS */ [ GALLIA, AFRICA, HISPANIA, BRITANNIA, NOMADS_HOMELAND, MARE_OCCIDENTALE ],
	/* PONTUS_EUXINUS */ [ ASIA, THRACIA, GALATIA, GOTHS_HOMELAND, SASSANIDS_HOMELAND ],
]

// BARBARIANS

const ALAMANNI = 0
const FRANKS = 1
const GOTHS = 2
const NOMADS = 3
const SASSANIDS = 4

const BARBARIAN_COUNT = [ 0, 50, 30, 40, 50 ]
const first_barbarian = [ 0, 10, 20, 30, 40 ]
const last_barbarian = [ 9, 19, 29, 39, 49 ]

const GENERAL_NAME = [
	"Red 0", "Red 1", "Red 2", "Red 3", "Red 4", "Red 5",
	"Blue 0", "Blue 1", "Blue 2", "Blue 3", "Blue 4", "Blue 5",
	"Yellow 0", "Yellow 1", "Yellow 2", "Yellow 3", "Yellow 4", "Yellow 5",
	"Green 0", "Green 1", "Green 2", "Green 3", "Green 4", "Green 5",
]

const BARBARIAN_NAME = [
	"Alamanni",
	"Franks",
	"Goths",
	"Nomads",
	"Sassanids",
]

const BARBARIAN_HOMELAND = [
	ALAMANNI_HOMELAND,
	FRANKS_HOMELAND,
	GOTHS_HOMELAND,
	NOMADS_HOMELAND,
	SASSANIDS_HOMELAND,
]

const BARBARIAN_INVASION = [
	// Alamanni
	[
		[ 1, 3, [ PANNONIA, ITALIA ] ],
		[ 4, 6, [ THRACIA, MACEDONIA ] ],
	],
	// Franks
	[
		[ 1, 2, [ BRITANNIA, GALLIA ] ],
		[ 3, 4, [ GALLIA, HISPANIA ] ],
		[ 5, 6, [ PANNONIA, ITALIA ] ],
	],
	// Goths
	[
		[ 1, 2, [ THRACIA, MACEDONIA ] ],
		[ 3, 4, [ ASIA, MACEDONIA ] ],
		[ 5, 6, [ GALATIA, SYRIA ] ],
	],
	// Nomads
	[
		[ 1, 3, [ AFRICA, HISPANIA ] ],
		[ 4, 6, [ AEGYPTUS, SYRIA ] ],
	],
	// Sassanids
	[
		[ 1, 3, [ GALATIA, ASIA ] ],
		[ 4, 6, [ SYRIA, AEGYPTUS ] ],
	],
]

const CRISIS_TABLE_4P = [
	0,
	SASSANIDS,
	FRANKS,
	SASSANIDS,
	GOTHS,
	0,
	ALAMANNI,
	NOMADS,
	FRANKS,
	NOMADS,
	0,
]

const CRISIS_TABLE_3P = [
	0,
	FRANKS,
	SASSANIDS,
	SASSANIDS,
	FRANKS,
	0,
	ALAMANNI,
	GOTHS,
	GOTHS,
	ALAMANNI,
	0,
]

const CRISIS_TABLE_2P = [
	0,
	FRANKS,
	ALAMANNI,
	FRANKS,
	GOTHS,
	0,
	GOTHS,
	FRANKS,
	ALAMANNI,
	ALAMANNI,
	0,
]

// CARDS

const EVENT_PLAGUE_OF_CYPRIAN = 1
const EVENT_ARDASHIR = 2
const EVENT_PRIEST_KING = 3
const EVENT_PALMYRA_ALLIES = 4
const EVENT_SHAPUR_I = 5
const EVENT_POSTUMUS = 6
const EVENT_LUDI_SAECULARES = 7
const EVENT_CNIVA = 8
const EVENT_ZENOBIA = 9
const EVENT_BAD_AUGURIES = 10
const EVENT_RAIDING_PARTIES = 11
const EVENT_PREPARING_FOR_WAR = 12
const EVENT_INFLATION = 13
const EVENT_GOOD_AUGURIES = 14
const EVENT_DIOCLETIAN = 15

// 12x
const CARD_M1 = [ 1, 12 ]
const CARD_S1 = [ 13, 24 ]
const CARD_P1 = [ 25, 36 ]

// 9x
const CARD_M2 = [ 37, 45 ]
const CARD_S2 = [ 46, 54 ]
const CARD_P2 = [ 55, 63 ]

// 8x
const CARD_M3 = [ 64, 71 ]
const CARD_S3 = [ 72, 79 ]
const CARD_P3 = [ 80, 87 ]

// 6x
const CARD_M4 = [ 88, 93 ]
const CARD_S4 = [ 94, 99 ]
const CARD_P4 = [ 100, 105 ]

function card_name(c) {
	if (c >= CARD_M1[0] && c <= CARD_M1[1]) return "M1"
	if (c >= CARD_M2[0] && c <= CARD_M2[1]) return "M2"
	if (c >= CARD_M3[0] && c <= CARD_M3[1]) return "M3"
	if (c >= CARD_M4[0] && c <= CARD_M4[1]) return "M4"
	if (c >= CARD_S1[0] && c <= CARD_S1[1]) return "S1"
	if (c >= CARD_S2[0] && c <= CARD_S2[1]) return "S2"
	if (c >= CARD_S3[0] && c <= CARD_S3[1]) return "S3"
	if (c >= CARD_S4[0] && c <= CARD_S4[1]) return "S4"
	if (c >= CARD_P1[0] && c <= CARD_P1[1]) return "P1"
	if (c >= CARD_P2[0] && c <= CARD_P2[1]) return "P2"
	if (c >= CARD_P3[0] && c <= CARD_P3[1]) return "P3"
	if (c >= CARD_P4[0] && c <= CARD_P4[1]) return "P4"
	return "??"
}

function card_cost(c) {
	if (c >= CARD_M1[0] && c <= CARD_M1[1]) return 1
	if (c >= CARD_M2[0] && c <= CARD_M2[1]) return 2
	if (c >= CARD_M3[0] && c <= CARD_M3[1]) return 3
	if (c >= CARD_M4[0] && c <= CARD_M4[1]) return 4
	if (c >= CARD_S1[0] && c <= CARD_S1[1]) return 1
	if (c >= CARD_S2[0] && c <= CARD_S2[1]) return 2
	if (c >= CARD_S3[0] && c <= CARD_S3[1]) return 3
	if (c >= CARD_S4[0] && c <= CARD_S4[1]) return 4
	if (c >= CARD_P1[0] && c <= CARD_P1[1]) return 1
	if (c >= CARD_P2[0] && c <= CARD_P2[1]) return 2
	if (c >= CARD_P3[0] && c <= CARD_P3[1]) return 3
	if (c >= CARD_P4[0] && c <= CARD_P4[1]) return 4
	return "??"
}

function card_event_name(c) {
	if (c >= CARD_M1[0] && c <= CARD_M1[1]) return "None"
	if (c >= CARD_M2[0] && c <= CARD_M2[1]) return "Castra"
	if (c >= CARD_M3[0] && c <= CARD_M3[1]) return "Flanking Maneuver"
	if (c >= CARD_M4[0] && c <= CARD_M4[1]) return "Praetorian Guard"
	if (c >= CARD_S1[0] && c <= CARD_S1[1]) return "None"
	if (c >= CARD_S2[0] && c <= CARD_S2[1]) return "Tribute"
	if (c >= CARD_S3[0] && c <= CARD_S3[1]) return "Foederati"
	if (c >= CARD_S4[0] && c <= CARD_S4[1]) return "Damnatio Memoriae"
	if (c >= CARD_P1[0] && c <= CARD_P1[1]) return "None"
	if (c >= CARD_P2[0] && c <= CARD_P2[1]) return "Quaestor"
	if (c >= CARD_P3[0] && c <= CARD_P3[1]) return "Mob"
	if (c >= CARD_P4[0] && c <= CARD_P4[1]) return "Pretender"
	return "None"
}

function can_play_card_event(c) {
	if (c >= CARD_M1[0] && c <= CARD_M1[1]) return false
	if (c >= CARD_M2[0] && c <= CARD_M2[1]) return can_play_castra()
	if (c >= CARD_M3[0] && c <= CARD_M3[1]) return false // "Flanking Maneuver"
	if (c >= CARD_M4[0] && c <= CARD_M4[1]) return can_play_praetorian_guard()
	if (c >= CARD_S1[0] && c <= CARD_S1[1]) return false
	if (c >= CARD_S2[0] && c <= CARD_S2[1]) return can_play_tribute()
	if (c >= CARD_S3[0] && c <= CARD_S3[1]) return can_play_foederati()
	if (c >= CARD_S4[0] && c <= CARD_S4[1]) return false // "Damnatio Memoriae"
	if (c >= CARD_P1[0] && c <= CARD_P1[1]) return false
	if (c >= CARD_P2[0] && c <= CARD_P2[1]) return can_play_quaestor()
	if (c >= CARD_P3[0] && c <= CARD_P3[1]) return can_play_mob()
	if (c >= CARD_P4[0] && c <= CARD_P4[1]) return false // "Pretender"
	return false
}

function play_card_event(c) {
	if (c >= CARD_M2[0] && c <= CARD_M2[1]) play_castra()
	if (c >= CARD_M3[0] && c <= CARD_M3[1]) play_flanking_maneuver()
	if (c >= CARD_M4[0] && c <= CARD_M4[1]) play_praetorian_guard()
	if (c >= CARD_S2[0] && c <= CARD_S2[1]) play_tribute()
	if (c >= CARD_S3[0] && c <= CARD_S3[1]) play_foederati()
	if (c >= CARD_S4[0] && c <= CARD_S4[1]) play_damnatio_memoriae()
	if (c >= CARD_P2[0] && c <= CARD_P2[1]) play_quaestor()
	if (c >= CARD_P3[0] && c <= CARD_P3[1]) play_mob()
	if (c >= CARD_P4[0] && c <= CARD_P4[1]) play_pretender()
}

function add_card_ip(c) {
	if (c >= CARD_M1[0] && c <= CARD_M1[1]) return game.ip[MILITARY] += 1
	if (c >= CARD_M2[0] && c <= CARD_M2[1]) return game.ip[MILITARY] += 2
	if (c >= CARD_M3[0] && c <= CARD_M3[1]) return game.ip[MILITARY] += 3
	if (c >= CARD_M4[0] && c <= CARD_M4[1]) return game.ip[MILITARY] += 4
	if (c >= CARD_S1[0] && c <= CARD_S1[1]) return game.ip[SENATE] += 1
	if (c >= CARD_S2[0] && c <= CARD_S2[1]) return game.ip[SENATE] += 2
	if (c >= CARD_S3[0] && c <= CARD_S3[1]) return game.ip[SENATE] += 3
	if (c >= CARD_S4[0] && c <= CARD_S4[1]) return game.ip[SENATE] += 4
	if (c >= CARD_P1[0] && c <= CARD_P1[1]) return game.ip[POPULACE] += 1
	if (c >= CARD_P2[0] && c <= CARD_P2[1]) return game.ip[POPULACE] += 2
	if (c >= CARD_P3[0] && c <= CARD_P3[1]) return game.ip[POPULACE] += 3
	if (c >= CARD_P4[0] && c <= CARD_P4[1]) return game.ip[POPULACE] += 4
}

function is_region(where) {
	return where < AVAILABLE
}

function is_province(where) {
	return where < 12
}

function is_sea(where) {
	return where >= MARE_OCCIDENTALE && where <= PONTUS_EUXINUS
}

function current_hand() { return game.hand[game.current] }
function current_draw() { return game.draw[game.current] }
function current_discard() { return game.discard[game.current] }

function get_barbarian_tribe(id) {
	for (let tribe = 0; tribe < 5; ++tribe)
		if (id >= first_barbarian[tribe] && id <= last_barbarian[tribe])
			return tribe
	return -1
}

// === BOARD STATE ===

function is_no_place_governor(where) {
	return where >= game.support.length
}

function get_support(province) { return game.support[province] }
function set_support(province, level) { game.support[province] = level }

function get_barbarian_location(id) { return game.barbarians[id] & 63 }
function set_barbarian_location(id, loc) { game.barbarians[id] = loc }
function is_barbarian_inactive(id) { return game.barbarians[id] & 64 }
function is_barbarian_active(id) { return !is_barbarian_inactive(id) }
function set_barbarian_inactive(id) { game.barbarians[id] |= 64 }
function set_barbarian_active(id) { game.barbarians[id] &= 63 }

function get_legion_location(ix) { return game.legions[ix] & 63 }
function set_legion_location(ix, loc) { game.legions[ix] = loc }
function is_legion_reduced(ix) { return game.legions[ix] & 64 }
function set_legion_reduced(ix) { game.legions[ix] |= 64 }
function set_legion_full_strength(ix) { game.legions[ix] &= 63 }

function is_legion_unused(ix) {
	return game.legions[ix] === AVAILABLE
}

function get_governor_location(id, loc) { return game.governors[id] & 63 }
function set_governor_location(id, loc) { game.governors[id] = loc }
function get_general_location(id) { return game.generals[id] & 63 }

function set_general_location(id, loc) { game.generals[id] = loc }
function is_general_inside_capital(id) { return game.generals[id] & 64 }
function set_general_inside_capital(id) { game.generals[id] |= 64 }
function set_general_outside_capital(id) { game.generals[id] &= 63 }

function has_general_castra(id) { return game.castra & (1 << id) }
function add_general_castra(id) { game.castra |= (1 << id) }
function remove_general_castra(id) { game.castra &= ~(1 << id) }

function has_militia_castra(province) { return game.mcastra & (1 << province) }
function add_militia_castra(province) { game.mcastra |= (1 << province) }
function remove_militia_castra(province) { game.mcastra &= ~(1 << province) }

function has_quaestor(province) { return game.quaestor & (1 << province) }
function add_quaestor(province) { game.quaestor |= (1 << province) }
function remove_quaestor(province) { game.quaestor &= ~(1 << province) }

function has_militia(province) { return game.militia & (1 << province) }
function add_militia(province) { game.militia |= (1 << province) }
function remove_militia(province) { game.militia &= ~(1 << province) }

function has_mob(province) { return game.mobs[province] > 0 }
function count_mobs(province) { return game.mobs[province] }
function add_one_mob(province) { game.mobs[province] ++ }
function remove_one_mob(province) { game.mobs[province] -- }
function remove_all_mobs(province) { game.mobs[province] = 0 }

function has_amphitheater(province) { return game.amphitheater & (1 << province) }
function has_basilica(province) { return game.basilica & (1 << province) }
function has_limes(province) { return game.limes & (1 << province) }
function add_amphitheater(province) { game.amphitheater |= (1 << province) }
function add_basilica(province) { game.basilica |= (1 << province) }
function add_limes(province) { game.limes |= (1 << province) }

function is_breakaway(province) { return game.breakaway & (1 << province) }
function add_breakaway(province) { game.breakaway |= (1 << province) }
function remove_breakaway(province) { game.breakaway &= ~(1 << province) }

function is_seat_of_power(province) { return game.seat_of_power & (1 << province) }
function add_seat_of_power(province) { game.seat_of_power |= (1 << province) }
function remove_seat_of_power(province) { game.seat_of_power &= ~(1 << province) }

// === TRANSIENT STATE ===

function has_placed_governor(province) { return game.placed & (1 << province) }
function set_placed_governor(province) { game.placed |= (1 << province) }

function has_general_battled(id) { return game.battled & (1 << id) }
function set_general_battled(id) { game.battled |= (1 << id) }

function has_militia_battled(province) { return game.mbattled & (1 << province) }
function set_militia_battled(province) { game.mbattled |= (1 << province) }

// === COMPOUND STATE ===

function get_selected_region() {
	if (game.selected_governor >= 0)
		return get_governor_location(game.selected_governor)
	if (game.selected_general >= 0)
		return get_governor_location(game.selected_general)
	return UNAVAILABLE
}

function for_each_current_general(f) {
	let a = game.current * 6
	for (let id = a; id < a + 6; ++id)
		f(id, get_general_location(id), is_general_inside_capital(id))
}

function for_each_current_governor(f) {
	let a = game.current * 6
	for (let id = a; id < a + 6; ++id)
		f(id, get_governor_location(id))
}

function for_each_general(f) {
	let n = game.legacy.length * 6
	for (let id = 0; id < n; ++id)
		f(id, get_general_location(id), is_general_inside_capital(id))
}

function for_each_governor(f) {
	let n = game.legacy.length * 6
	for (let id = 0; id < n; ++id)
		f(id, get_governor_location(id))
}

function find_general(f) {
	let n = game.legacy.length * 6
	for (let id = 0; id < n; ++id)
		if (f(id, get_general_location(id), is_general_inside_capital(id)))
			return id
	return -1
}

function find_governor(f) {
	let n = game.legacy.length * 6
	for (let id = 0; id < n; ++id)
		if (f(id, get_governor_location(id)))
			return id
	return -1
}

function for_each_barbarian(f) {
	let n = game.barbarians.length
	for (let id = 0; id < n; ++id)
		f(id, get_barbarian_location(id), is_barbarian_inactive(id))
}

function find_barbarian(f) {
	let n = game.barbarians.length
	for (let id = 0; id < n; ++id)
		if (f(id, get_barbarian_location(id), is_barbarian_active(id)))
			return id
	return -1
}

function some_governor(f) {
	return find_governor(f) >= 0
}

function some_general(f) {
	return find_general(f) >= 0
}

function some_barbarian(f) {
	return find_barbarian(f) >= 0
}

function next_player() {
	return (game.current + 1) % game.legacy.length
}

function find_unused_legion() {
	for (let ix = 0; ix < LEGION_COUNT; ++ix)
		if (get_legion_location(ix) === AVAILABLE)
			return ix
	return -1
}

function can_build_improvement(province) {
	if (has_mob(province))
		return false
	if (has_active_barbarians(province))
		return false
	if (has_rival_emperor(province))
		return false
	if (has_enemy_general_in_capital(province))
		return false
	return true
}

function update_neutral_italia() {
	if (is_neutral_province(ITALIA)) {
		let n = 1
		for (let s = 1; s < 12; ++s)
			if (is_neutral_province(s))
				++n
		if (n > 8)
			n = 8
		set_support(ITALIA, n)
	}
}

function get_player_count() {
	return game.legacy.length
}

function get_tribe_count() {
	return game.legacy.length + 1
}

function can_enter_capital(where) {
	// No Capital
	if (is_no_place_governor(where))
		return false

	// Occupied by General
	if (some_general((id, loc, cap) => loc === where && cap))
		return false

	// Occupied by opponent Militia
	if (has_militia(where)) {
		if (!is_own_province(where))
			return false
	}

	return true
}

function is_own_general(id) {
	let a = game.current * 6
	return id >= a && id < a + 6
}

function is_enemy_general(id) {
	return id >= 0 && !is_own_general(id)
}

function is_own_governor(id) {
	let a = game.current * 6
	return id >= a && id < a + 6
}

function is_enemy_governor(id) {
	return id >= 0 && !is_own_governor(id)
}

function is_capital_free_of_enemy(where) {
	return !is_enemy_general(get_capital_general(where))
}

function get_province_governor(where) {
	return find_governor((id, loc) => loc === where)
}

function get_capital_general(where) {
	return find_general((id, loc, cap) => loc === where && cap)
}

function is_neutral_province(where) {
	if (is_no_place_governor(where))
		return false
	return get_province_governor(where) < 0
}

function has_active_barbarians(where) {
	if (has_barbarian_leader(where))
		return true
	return some_barbarian((id, loc, active) => loc === where && active)
}

function find_active_barbarian_of_tribe(where, tribe) {
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
		if (get_barbarian_location(id) === where && is_barbarian_active(id))
			return id
	return -1
}

function has_barbarian_leader(where) {
	for (let i = 0; i < 3; ++i)
		if (game.barbarian_leaders[i] === where)
			return true
	return false
}

function has_rival_emperor(where) {
	for (let i = 0; i < 3; ++i)
		if (game.rival_emperors[i] === where)
			return true
	return false
}

function is_enemy_province(where) {
	return is_enemy_governor(get_province_governor(where))
}

function is_own_province(where) {
	return is_own_governor(get_province_governor(where))
}

function is_emperor(governor) {
	let emperor = get_province_governor(ITALIA)
	if (emperor >= 0 && governor >= 0)
		return (emperor / 6 | 0) === (governor / 6 | 0)
	return false
}

function has_enemy_general_in_capital(where) {
	return is_enemy_general(get_capital_general(where))
}

function has_enemy_army_in_province(where) {
	if (some_general((id, loc) => loc === where && is_enemy_general(id)))
		return true
	if (is_province(where) && some_barbarian((id, loc) => loc === where))
		return true
	if (!is_province(where) && some_barbarian((id, loc, active) => loc === where && active))
		return true
	return false
}

function spend_ip(type, n) {
	game.ip[type] -= n
}

function can_place_governor(where) {
	if (is_no_place_governor(where))
		return false
	if (is_own_province(where))
		return false
	// Recalled or already attempted to place.
	if (has_placed_governor(where))
		return false
	// Cannot Place in breakaway provinces
	if (is_breakaway(where) || is_seat_of_power(where))
		return false
	return true
}

function find_active_barbarian_at_home(tribe) {
	let home = BARBARIAN_HOMELAND[tribe]
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
		if (get_barbarian_location(id) === home && is_barbarian_active(id))
			return id
	return -1
}

function count_active_barbarians_at_home(tribe) {
	let home = BARBARIAN_HOMELAND[tribe]
	let n = 0
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
		if (get_barbarian_location(id) === home && is_barbarian_active(id))
			n += 1
	return n
}

function find_inactive_barbarian_at_home(tribe) {
	let home = BARBARIAN_HOMELAND[tribe]
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
		if (get_barbarian_location(id) === home && is_barbarian_inactive(id))
			return id
	return -1
}

function count_barbarians_in_province(tribe, where) {
	let n = 0
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
		if (get_barbarian_location(id) === where)
			n += 1
	return n
}

function count_legions_in_army(id) {
	let n = 0
	for (let i = 0; i < LEGION_COUNT; ++i)
		if (get_legion_location(i) === ARMY + id)
			++n
	return n
}

function find_reduced_legion_in_army(id) {
	for (let i = 0; i < LEGION_COUNT; ++i)
		if (get_legion_location(i) === ARMY + id && is_legion_reduced(i))
			return i
	return -1
}

function has_reduced_legions_in_army(id) {
	return find_reduced_legion_in_army(id) >= 0
}

function has_lone_militia(where) {
	return has_militia(where) && get_capital_general(where) < 0
}

function count_units_in_army(id) {
	let n = 0
	for (let i = 0; i < LEGION_COUNT; ++i)
		if (get_legion_location(i) === ARMY + id)
			++n
	for (let loc of game.barbarians)
		if (loc === ARMY + id)
			++n
	return n
}

function count_own_provinces() {
	let n = 0
	for (let where = 0; where < 12; ++where)
		if (is_own_province(where))
			++n
	return n
}

function count_own_basilicas() {
	let n = 0
	for (let where = 0; where < 12; ++where)
		if (is_own_province(where) && has_basilica(where))
			++n
	return n
}

function roll_dice(count, target) {
	let hits = 0
	console.log("roll_dice", count, target)
	while (count > 0) {
		let summary = []
		let sixes = 0
		for (let i = 0; i < count; ++i) {
			let die = roll_die()
			if (die === 6)
				sixes += 1
			if (die >= target) {
				summary.push("B" + die)
				hits += 1
			} else {
				summary.push("W" + die)
			}
		}
		log("Rolled " + summary.join(" "))
		count = sixes
	}
	return hits
}

function eliminate_barbarian(id) {
	let tribe = get_barbarian_tribe(id)
	set_barbarian_location(id, BARBARIAN_HOMELAND[tribe])
	set_barbarian_inactive(id)
}

function flip_discard_to_available() {
	game.draw[game.current] = game.discard[game.current]
	game.discard[game.current] = []
}

// === SETUP ===

states.setup_province = {
	prompt() {
		view.prompt = "Select a starting Province."
		for (let where = 2; where <= 12; ++where)
			if (is_neutral_province(where) && !is_no_place_governor(where))
				gen_action("capital", where)
	},
	capital(where) {
		push_undo()

		set_governor_location(game.current * 6 + 0, where)

		add_militia(where)

		set_general_location(game.current * 6 + 0, where)
		set_general_inside_capital(game.current * 6 + 0)
		set_legion_location(find_unused_legion(), ARMY + game.current * 6 + 0)

		game.state = "setup_hand"
	},
}

states.setup_hand = {
	prompt() {
		view.prompt = "Draw your initial hand."
		let hand = current_hand()
		if (hand.length < 5) {
			for (let c of current_draw())
				gen_action_card(c)
		} else {
			view.actions.done = 1
		}
	},
	card(c) {
		push_undo()
		set_delete(current_draw(), c)
		set_add(current_hand(), c)
	},
	done() {
		clear_undo()
		game.state = "setup_province"
		game.current = next_player()
		if (game.current === game.first)
			goto_start_turn()
	},
}

// === UPKEEP ===

function goto_start_turn() {
	log_h2(PLAYER_NAMES[game.current])

	game.battled = 0
	game.mbattled = 0
	game.placed = 0

	goto_upkeep()
}

function goto_upkeep() {
	// TODO: manually remove Quaestor and Castra?
	for (let i = 0; i < 6; ++i) {
		let id = game.current * 6 + i
		let where = get_governor_location(id)
		if (is_province(where) && has_quaestor(where)) {
			log("Removed Quaestor from S" + where)
			remove_quaestor(where)
		}
		if (has_militia_castra(where)) {
			log("Removed Castra from S" + where)
			remove_militia_castra(where)
		}
		if (has_general_castra(id)) {
			log("Removed Castra from S" + get_general_location(id))
			remove_general_castra(id)
		}
	}

	goto_crisis()
}

// === CRISIS ===

// TODO: manual barbarian invasions!

function goto_crisis() {
	game.dice[0] = roll_die()
	game.dice[1] = roll_die()

	log(`Crisis B${game.dice[0]} W${game.dice[1]}`)

	let sum = game.dice[0] + game.dice[1]

	if (sum === 2)
		return goto_ira_deorum()
	if (sum === 12)
		return goto_pax_deorum()
	if (sum === 7)
		return goto_event()

	if (game.legacy.length === 2)
		return goto_barbarian_crisis(CRISIS_TABLE_2P[sum - 2])
	if (game.legacy.length === 3)
		return goto_barbarian_crisis(CRISIS_TABLE_3P[sum - 2])
	return goto_barbarian_crisis(CRISIS_TABLE_4P[sum - 2])
}

function goto_ira_deorum() {
	logi("Ira Deorum")

	game.count = 0
	let tribe_count = get_tribe_count()
	for (let tribe = 0; tribe < tribe_count; ++tribe)
		if (find_inactive_barbarian_at_home(tribe) >= 0)
			game.count |= (1 << tribe)

	game.state = "ira_deorum"
	if (game.count === 0)
		goto_take_actions()
}

states.ira_deorum = {
	prompt() {
		prompt("Ira Deorum: Activate one Barbarian in each tribe's homeland.")
		let tribe_count = get_tribe_count()
		for (let tribe = 0; tribe < tribe_count; ++tribe)
			if (game.count & (1 << tribe))
				gen_action_barbarian(find_inactive_barbarian_at_home(tribe))
	},
	barbarian(id) {
		let tribe = get_barbarian_tribe(id)
		game.count &= ~(1 << tribe)

		log("Activated " + BARBARIAN_NAME[tribe])
		set_barbarian_active(id)

		if (game.count === 0)
			goto_take_actions()
	},
}

function goto_pax_deorum() {
	logi("Pax Deorum")
	logi("TODO")
	goto_take_actions()
}

function goto_event() {
	logi("Event")
	logi("TODO")
	goto_take_actions()
}

function goto_barbarian_crisis(tribe) {
	logi(BARBARIAN_NAME[tribe])

	game.crisis = tribe

	if (find_inactive_barbarian_at_home(tribe) >= 0)
		game.state = "barbarian_crisis"
	else
		roll_barbarian_crisis()
}

states.barbarian_crisis = {
	prompt() {
		let tribe = game.crisis
		prompt(BARBARIAN_NAME[tribe] + " Crisis!")
		gen_action_barbarian(find_inactive_barbarian_at_home(tribe))
	},
	barbarian(id) {
		let tribe = game.crisis
		log("Activated " + BARBARIAN_NAME[tribe])
		set_barbarian_active(id)
		roll_barbarian_crisis()
	},
}

function roll_barbarian_crisis() {
	let tribe = game.crisis

	let black = game.dice[2] = roll_die()
	let white = game.dice[3] = roll_die()

	logi(`B${black} W${white}`)

	if (black <= count_active_barbarians_at_home(tribe))
		goto_barbarian_invasion()
	else
		goto_take_actions()
}

function goto_barbarian_invasion(tribe, black, white) {
	logi("Invasion!")
	game.count = game.dice[2]
	game.state = "barbarian_invasion"
}

states.barbarian_invasion = {
	prompt() {
		let tribe = game.crisis
		prompt(BARBARIAN_NAME[tribe] + " Invasion!")
		gen_action_barbarian(find_active_barbarian_at_home(tribe))
	},
	barbarian(id) {
		if (invade_with_barbarian(id) || --game.count === 0)
			goto_take_actions()
	},
}

function invade_with_barbarian(id) {
	let tribe = game.crisis
	let white = game.dice[3]

	let path = null
	for (let list of BARBARIAN_INVASION[tribe])
		if (white >= list[0] && white <= list[1])
			path = list[2]

	for (let i = 0; i < path.length; ++i) {
		let n = count_barbarians_in_province(tribe, path[i])
		if (n < 3) {
			invade_with_barbarian_counter(id, path, path[i])
			return false
		}
	}

	return true
}

function invade_with_barbarian_counter(id, path, where) {
	set_barbarian_location(id, where)
	for (let loc of path) {
		if (has_limes(loc))
			set_barbarian_inactive(id)
		if (loc === where)
			break
	}
}

// === TAKE ACTIONS ===

function goto_take_actions() {
	game.state = "take_actions"
	game.ip = [ 0, 0, 0 ]
	game.played = []
	game.used = []
	game.placed = 0 // only place governor once (and no place if recalled)
}

states.take_actions = {
	prompt() {
		let [ mip, sip, pip ] = game.ip

		prompt(`Take Actions: ${mip} Military, ${sip} Senate, ${pip} Populace.`)

		let where = UNAVAILABLE

		view.actions.end_actions = 1

		// Play cards for IP
		for (let c of current_hand())
			gen_action_card(c)

		// Use events on played cards
		for (let c of game.played)
			if (!set_has(game.used, c) && can_play_card_event(c))
				gen_action_card(c)

		if (game.selected_governor >= 0) {
			view.selected_governor = game.selected_governor
			where = get_governor_location(game.selected_governor)
		}

		if (game.selected_general >= 0) {
			view.selected_general = game.selected_general
			where = get_general_location(game.selected_general)
		}

		// Select Governor
		for (let i = 0; i < 6; ++i) {
			let id = game.current * 6 + i
			if (id !== game.selected_governor) {
				switch (get_governor_location(id)) {
				case UNAVAILABLE:
					if (sip >= i)
						gen_action_governor(id)
					break
				case AVAILABLE:
					if (sip >= 1)
						gen_action_governor(id)
					break
				default:
					gen_action_governor(id)
					break
				}
			}
		}

		// Select General
		for (let i = 0; i < 6; ++i) {
			let id = game.current * 6 + i
			if (id !== game.selected_general) {
				switch (get_general_location(id)) {
				case UNAVAILABLE:
					if (mip >= i)
						gen_action_general(id)
					break
				case AVAILABLE:
					if (mip >= 1)
						gen_action_general(id)
					break
				default:
					gen_action_general(id)
					break
				}
			}
		}

		// Recruit Governor
		if (game.selected_governor >= 0 && where === UNAVAILABLE) {
			view.actions.recruit_governor = 0
			if (sip >= game.selected_governor % 6)
				view.actions.recruit_governor = 1
		}

		// Recruit General
		if (game.selected_general >= 0 && where === UNAVAILABLE) {
			view.actions.recruit_general = 0
			if (mip >= game.selected_general % 6)
				view.actions.recruit_general = 1
		}

		// Place Governor
		if (game.selected_governor >= 0 && where === AVAILABLE) {
			gen_place_governor()
		}

		// Create Army
		if (game.selected_general >= 0 && where === AVAILABLE) {
			if (mip >= 1 && find_unused_legion() >= 0)
				gen_create_army()
		}

		// Governor Actions
		if (game.selected_governor >= 0 && is_province(where)) {
			view.actions.place_militia = 0
			view.actions.amphitheater = 0
			view.actions.basilica = 0
			view.actions.limes = 0

			// Recall Governor
			if (sip >= 2)
				gen_action_recall(where)

			// Increase Support Level
			let support = game.support[where]
			if (where !== ITALIA && support < 4) {
				if (pip > support)
					gen_action_support(where, support + 1)
			}

			// Place Militia
			if (!has_militia(where) && is_capital_free_of_enemy(where)) {
				if (pip >= 2)
					view.actions.place_militia = 1
			}

			// Hold Games
			if (has_mob(where)) {
				view.actions.disperse_mob = 0
				view.actions.hold_games = 0
				if (has_lone_militia(where) && mip >= 1)
					view.actions.disperse_mob = 1
				if (pip >= 2)
					view.actions.hold_games = 1
			}

			// Build an Improvement
			if (can_build_improvement(where)) {
				if (pip >= 3) {
					if (!has_amphitheater(where))
						view.actions.amphitheater = 1
					if (!has_basilica(where))
						view.actions.basilica = 1
					if (!has_limes(where))
						view.actions.limes = 1
				}
			}

			// Initiate Battle with Militia not stacked with General
			if (!has_militia_battled(where)) {
				if (has_lone_militia(where))
					gen_initiate_battle(where)
			}
		}

		// General Actions
		if (game.selected_general >= 0 && is_region(where)) {
			view.actions.disperse_mob = 0
			view.actions.train_legions = 0
			view.actions.add_legion_to_army = 0

			// Disperse Mob
			if (has_mob(where)) {
				if (mip >= 1)
					view.actions.disperse_mob = 1
			}

			// Train Legions
			if (has_reduced_legions_in_army(game.selected_general)) {
				if (mip >= 1)
					view.actions.train_legions = 1
			}

			// Add Legion to Army
			if (is_own_province(where)) {
				let cost = count_legions_in_army(game.selected_general) + 1
				if (mip >= cost)
					view.actions.add_legion_to_army = 1
			}

			if (!has_general_battled(game.selected_general)) {
				// Move Army
				gen_move_army()

				// Initiate Battle
				gen_initiate_battle(where)

				// Free Action: Enter/Leave Capital
				if (is_province(where)) {
					if (is_general_inside_capital(game.selected_general)) {
						view.actions.leave = 1
					} else if (can_enter_capital(where)) {
						view.actions.enter = 1
						gen_action_capital(where)
					}
				}
			}
		}

	},

	end_actions() {
		push_undo()
		goto_support_check()
	},

	card(c) {
		push_undo()
		let hand = current_hand()
		if (set_has(hand, c)) {
			set_delete(hand, c)
			set_add(game.played, c)
			add_card_ip(c)
		} else if (set_has(game.played, c)) {
			set_add(game.used, c)
			play_card_event(c)
		}
	},

	governor(id) {
		game.selected_governor = id
		game.selected_general = -1
	},

	general(id) {
		if (is_own_general(id)) {
			game.selected_governor = -1
			game.selected_general = id
		} else {
			goto_battle_vs_general(get_general_location(game.selected_general), game.selected_general, id)
		}
	},

	recruit_governor() {
		push_undo()
		log("Recruited Governor " + (game.selected_governor % 6) + ".")
		spend_ip(SENATE, game.selected_governor % 6)
		set_governor_location(game.selected_governor, AVAILABLE)
	},

	recruit_general() {
		push_undo()
		log("Recruited General " + (game.selected_general % 6) + ".")
		spend_ip(MILITARY, game.selected_general % 6)
		set_general_location(game.selected_general, AVAILABLE)
	},

	recall() {
		push_undo()
		recall_governor()
	},

	support() {
		push_undo()
		improve_support()
	},

	place_militia() {
		push_undo()
		let where = get_governor_location(game.selected_governor)
		spend_ip(POPULACE, 2)
		add_militia(where)
	},

	hold_games() {
		push_undo()
		let where = get_governor_location(game.selected_governor)
		log("Held Games in S" + where + ".")
		spend_ip(POPULACE, 3)
		remove_one_mob(where)
	},

	amphitheater() {
		push_undo()
		spend_ip(POPULACE, 3)
		let where = get_governor_location(game.selected_governor)
		add_amphitheater(where)
		log("Built Amphitheater in S" + where + ".")
	},

	basilica() {
		push_undo()
		spend_ip(POPULACE, 3)
		let where = get_governor_location(game.selected_governor)
		add_basilica(where)
		log("Built Basilica in S" + where + ".")
	},

	limes() {
		push_undo()
		spend_ip(POPULACE, 3)
		let where = get_governor_location(game.selected_governor)
		add_limes(where)
		log("Built Limes in S" + where + ".")
	},

	add_legion_to_army() {
		push_undo()
		log("Added Legion to Army.")
		let cost = count_legions_in_army(game.selected_general) + 1
		spend_ip(MILITARY, cost)
		set_legion_location(find_unused_legion(), ARMY + game.selected_general)
	},

	train_legions() {
		push_undo()
		log("Trained Legions.")
		spend_ip(MILITARY, 1)
		set_legion_full_strength(find_reduced_legion_in_army(game.selected_general))
	},

	capital(where) {
		push_undo()
		set_general_inside_capital(game.selected_general)
	},

	enter() {
		push_undo()
		set_general_inside_capital(game.selected_general)
	},

	leave() {
		push_undo()
		set_general_outside_capital(game.selected_general)
	},

	region(where) {
		push_undo()
		if (game.selected_governor >= 0) {
			spend_ip(SENATE, 1)
			game.misc = { spend: 1, where: where }
			game.state = "place_governor"
		}
		if (game.selected_general >= 0) {
			if (get_general_location(game.selected_general) === AVAILABLE)
				create_army(where)
			else
				move_army_to(game.selected_general, where, true)
		}
	},

	barbarian(id) {
		push_undo()
		goto_battle_vs_barbarian(get_general_location(game.selected_general), game.selected_general, id)
	},

	rival_emperor(id) {
		push_undo()
		goto_battle_vs_rival_emperor(get_general_location(game.selected_general), game.selected_general, id)
	},

	militia(where) {
		push_undo()
		goto_battle_vs_militia(get_general_location(game.selected_general), game.selected_general)
	},
}

// ACTION: IMPROVE SUPPORT

function improve_support() {
	let where = get_governor_location(game.selected_governor)
	let support = game.support[where]
	log("Built Support in S" + where + ".")
	spend_ip(POPULACE, support + 1)
	game.support[where] = support + 1
}

// ACTION: RECALL GOVERNOR

function recall_governor() {
	let where = get_governor_location(game.selected_governor)
	log("Recalled Governor from S" + where + ".")
	spend_ip(SENATE, 2)
	set_placed_governor(where)
	remove_governor(where)
	update_neutral_italia()
}

// ACTION: PLACE GOVERNOR

function gen_place_governor() {
	let sip = game.ip[SENATE]
	if (sip >= 1) {
		for (let where = 0; where < 12; ++where)
			if (can_place_governor(where))
				gen_action_region(where)
	}
}

function reduce_support(where) {
	if (game.support[where] === 1)
		remove_governor(where)
	else
		game.support[where] -= 1
}

function increase_support(where) {
	game.support[where] += 1
}

function remove_governor(where) {
	log("Removed Governor from S" + where)

	remove_all_mobs(where)
	remove_militia(where)
	remove_militia_castra(where)
	remove_quaestor(where)

	let old_governor = get_province_governor(where)
	if (old_governor >= 0) {
		set_governor_location(old_governor, AVAILABLE)
		if (where !== ITALIA && is_emperor(old_governor))
			reduce_support(ITALIA)
	}

	if (where !== ITALIA)
		game.support[where] = 1

	update_neutral_italia()
}

function place_governor(where, new_governor) {
	remove_all_mobs(where)
	remove_militia(where)
	remove_militia_castra(where)

	let old_governor = get_province_governor(where)
	if (old_governor >= 0) {
		set_governor_location(old_governor, AVAILABLE)
		if (where !== ITALIA && is_emperor(old_governor))
			reduce_support(ITALIA)
	}

	set_governor_location(new_governor, where)
	if (where === ITALIA)
		game.support[where] = count_own_provinces()
	else
		game.support[where] = Math.max(1, game.support[where] - 1)

	if (where !== ITALIA && is_emperor(new_governor))
		increase_support(ITALIA)

	update_neutral_italia()
}

function calc_needed_votes(where) {
	let n = get_support(where) * 2 // base number of votes
	let old_governor = get_province_governor(where)
	let old_player = (old_governor < 0) ? -1 : (old_governor / 6 | 0)
	let army_general = get_capital_general(where)
	if (army_general >= 0) {
		let army_player = army_general / 6 | 0
		let army_size = count_units_in_army(army_general)
		console.log("VOTES", old_player, army_player, game.current)
		if (army_player === old_player)
			n += army_size
		else if (army_player === game.current)
			n -= army_size
	}
	if (has_militia(where))
		n += 1
	console.log("votes needed", where, n)
	return Math.max(1, n)
}

states.place_governor = {
	prompt() {
		let [ mip, sip, pip ] = game.ip
		let need = calc_needed_votes(game.misc.where)
		let votes = game.misc.spend
		if (game.misc.where === ITALIA)
			votes += count_own_basilicas()
		view.selected_governor = game.selected_governor
		view.selected_region = game.misc.where

		prompt(`Place Governor: ${sip} Senate. Rolling ${votes} dice. ${need} votes needed.`)

		view.actions.spend_senate = (sip >= 1)

		view.actions.roll = 1
	},
	spend_senate() {
		push_undo()
		spend_ip(SENATE, 1)
		game.misc.spend += 1
	},
	roll() {
		let need = calc_needed_votes(game.misc.where)
		let have = 0

		set_placed_governor(game.misc.where)

		if (game.misc.where === ITALIA)
			game.misc.spend += count_own_basilicas()

		log("Place Governor in S" + game.misc.where)
		if (is_neutral_province(game.misc.where))
			have = roll_dice(game.misc.spend, 1)
		else if (has_quaestor(game.misc.where))
			have = roll_dice(game.misc.spend, 3)
		else
			have = roll_dice(game.misc.spend, 2)

		if (have >= need) {
			logi("Success!")
			place_governor(game.misc.where, game.selected_governor)
		} else {
			logi("Failed!")
		}

		game.misc = null
		game.state = "take_actions"
	},
}

// ACTION: CREATE ARMY

function gen_create_army() {
	for (let i = 0; i < 6; ++i) {
		let where = get_governor_location(game.current * 6 + i)
		if (is_province(where))
			gen_action_region(where)
	}
}

function create_army(where) {
	spend_ip(MILITARY, 1)
	log("Created Army in S" + where + ".")
	set_general_location(game.selected_general, where)
	if (can_enter_capital(where))
		set_general_inside_capital(game.selected_general)
	set_legion_location(find_unused_legion(), ARMY + game.selected_general)
	game.state = "take_actions"
}

// ACTION: MOVE ARMY

function gen_move_army() {
	let mip = game.ip[MILITARY]
	let from = get_general_location(game.selected_general)
	if (mip >= 1) {
		for (let to of ADJACENT[from]) {
			if (!is_sea(to))
				gen_action_region(to)
			else if (mip >= 2)
				gen_action_region(to)
		}
	}
}

states.move_army_at_sea = {
	prompt() {
		let [ mip, sip, pip ] = game.ip
		prompt("Move Army.")
		view.selected_general = game.selected_general
		gen_move_army()
	},
	region(to) {
		push_undo()
		move_army_to(game.selected_general, to, true)
	},
	capital(to) {
		push_undo()
		move_army_to(game.selected_general, to, true)
	},
}

function move_army_to(who, to, go_inside) {
	log("Moved Army to S" + to + ".")

	remove_general_castra(who)

	spend_ip(MILITARY, 1)
	set_general_location(who, to)
	if (can_enter_capital(to) && go_inside)
		set_general_inside_capital(who)

	if (is_sea(to))
		game.state = "move_army_at_sea"
	else
		game.state = "take_actions"
}

// CARD: CASTRA

function can_play_castra() {
	let where = get_selected_region()
	if (game.selected_governor >= 0 && is_province(where))
		return has_lone_militia(where) && !has_militia_castra(where)
	if (game.selected_general >= 0 && is_province(where))
		return !has_general_castra(where)
	return false
}

function play_castra() {
	let where = get_selected_region()
	if (game.selected_governor >= 0 && is_province(where))
		add_militia_castra(where)
	if (game.selected_general >= 0)
		add_general_castra(game.selected_general)
}

function can_play_quaestor() {
	let where = get_selected_region()
	if (game.selected_governor >= 0 && is_province(where))
		return !has_quaestor(where)
	return false
}

function play_quastor() {
	let where = get_selected_region()
	add_quaestor(where)
}

function can_play_tribute() {
	for (let where = 0; where < 12; ++where)
		if (has_active_barbarians(where))
			return true
	return false
}

function play_tribute() {
	game.state = "tribute"
}

states.tribute = {
	prompt() {
		prompt("Tribute: Flip a single tribe to their inactive side in any province.")
		let tribe_count = get_tribe_count()
		for (let where = 0; where < 12; ++where) {
			for (let tribe = 0; tribe < tribe_count; ++tribe) {
				let id = find_active_barbarian_of_tribe(where, tribe)
				if (id >= 0)
					gen_action_barbarian(id)
			}
		}
	},
	barbarian(target) {
		let where = get_barbarian_location(target)
		let tribe = get_barbarian_tribe(target)
		log("Tribute " + BARBARIAN_NAME[tribe] + " in S" + where)
		for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
			if (get_barbarian_location(id) === where && is_barbarian_active(id))
				set_barbarian_inactive(id)
		game.state = "take_actions"
	},
}

// === COMBAT ===

function goto_battle_vs_general(where, attacker, target) {
	log("Initiate Battle vs " + GENERAL_NAME[target] + " in S" + where)
	goto_battle("general", where, attacker, target)
}

function goto_battle_vs_barbarian(where, attacker, target) {
	log("Initiate Battle vs " + BARBARIAN_NAME[target] + " in S" + where)
	goto_battle("barbarians", where, attacker, get_barbarian_tribe(target))
}

function goto_battle_vs_rival_emperor(where, attacker, target) {
	log("Initiate Battle vs Rival Emperor in S" + where)
	goto_battle("rival_emperor", where, attacker, target)
}

function goto_battle_vs_militia(where, attacker) {
	log("Initiate Battle vs Militia in S" + where)
	goto_battle("militia", where, attacker, -1)
}

function goto_battle(type, where, attacker, target) {
	spend_ip(MILITARY, 1)
	game.misc = { type, where, attacker, target }
	game.state = "battle"
	if (attacker >= 0) {
		remove_general_castra(who)
		set_general_battled(attacker)
	} else {
		set_militia_battled(where)
	}
}

function gen_initiate_battle(where) {
	if (game.ip[MILITARY] >= 1) {
		for_each_general((id, loc) => {
			if (loc === where && is_enemy_general(id))
				gen_action_general(id)
		})
		for_each_barbarian((id, loc) => {
			if (loc === where)
				gen_action_barbarian(id)
		})
		if (is_enemy_province(where)) {
			if (has_lone_militia(where))
				gen_action_militia(where)
		}
	}
}

states.battle = {
	prompt() {
		prompt("Battle!")
		// TODO: play "Flanking Maneuver"
		view.actions.roll = 1
	},
	roll() {
		// clear_undo()

		game.misc.dhits = roll_attacker_dice()
		game.misc.dtaken = 0

		game.misc.ahits = roll_defender_dice()
		game.misc.ataken = 0

		// TODO: castra

		if (game.misc.ahits > 0)
			game.state = "assign_hits_on_attacker"
		else if (game.misc.dhits > 0)
			game.state = "assign_hits_on_defender"
		else
			end_battle()
	},
}

function roll_general_dice(general) {
	let army = ARMY + general
	let n = 0

	log(GENERAL_NAME[general])

	if (is_general_inside_capital(general) && has_militia(game.misc.where)) {
		log("Militia")
		n += roll_dice(1, 5)
	}

	let full_strength = 0
	let reduced = 0
	for (let id = 0; id < 33; ++id) {
		if (get_legion_location(id) === army) {
			if (is_legion_reduced(id))
				reduced += 1
			else
				full_strength += 1
		}
	}
	if (full_strength > 0) {
		log("Legions")
		n += roll_dice(full_strength, 3)
	}
	if (reduced > 0) {
		log("Reduced Legions")
		n += roll_dice(reduced, 5)
	}

	let barbarians = 0
	for (let id = 0; id < game.barbarians.length; ++id)
		if (get_barbarian_location(id) === army)
			barbarians += 1
	if (barbarians > 0) {
		log("Barbarians")
		n += roll_dice(barbarians, 4)
	}

	return n
}

function roll_militia_dice() {
	log("Militia")
	return roll_dice(1, 5)
}

function roll_rival_emperor_dice(rival_emperor) {
	log("Rival Emperor")
	return roll_dice(3, 4)
}

function roll_barbarian_dice(tribe) {
	log(BARBARIAN_NAME[tribe])
	let prov = is_province(game.misc.where)
	let n = 0
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
		if (get_barbarian_location(id) === game.misc.where)
			if (prov || is_barbarian_active(id))
				n += 1
	return roll_dice(n, 4)
}

function roll_attacker_dice() {
	log_h3("ATTACKER")
	if (game.misc.attacker < 0)
		return roll_militia_dice()
	else
		return roll_general_dice(game.misc.attacker)
}

function roll_defender_dice() {
	log_h3("DEFENDER")
	switch (game.misc.type) {
		case "militia":
			return roll_militia_dice()
		case "rival_emperor":
			return roll_rival_emperor_dice(game.misc.target)
		case "barbarians":
			return roll_barbarian_dice(game.misc.target)
		case "general":
			return roll_general_dice(game.misc.target)
	}
	return 0
}

function gen_hits_militia() {
	if (has_militia(game.misc.where)) {
		gen_action_militia(game.misc.where)
		return false
	}
	return true
}

function gen_hits_barbarians(tribe) {
	let prov = is_province(game.misc.where)
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id)
		if (get_barbarian_location(id) === game.misc.where)
			if (prov || is_barbarian_active(id))
				gen_action_barbarian(id)
}

// TODO: auto-end if all possible hits assigned

function gen_hits_general(general) {
	let army = ARMY + general

	// TODO: castra

	if (is_general_inside_capital(general) && has_militia(game.misc.where)) {
		gen_action_militia(game.misc.where)
		return false
	}

	for (let id = 0; id < game.barbarians.length; ++id) {
		if (get_barbarian_location(id) === army) {
			gen_action_barbarian(id)
			return false
		}
	}

	// NOTE: reduce all legions before eliminating any
	for (let id = 0; id < 33; ++id) {
		if (get_legion_location(id) === army && !is_legion_reduced(id)) {
			gen_action_legion(id)
			return false
		}
	}

	for (let id = 0; id < 33; ++id) {
		if (get_legion_location(id) === army && is_legion_reduced(id)) {
			gen_action_legion(id)
			return false
		}
	}

	return true
}

states.assign_hits_on_attacker = {
	prompt() {
		prompt("Assign " + (game.misc.ahits - game.misc.ataken) + " hits!")

		let done = true

		if (game.misc.ataken < game.misc.ahits) {
			if (game.misc.attacker < 0)
				done = gen_hits_militia()
			else
				done = gen_hits_general(game.misc.attacker)
		}

		if (done)
			view.actions.done = 1
	},
	done() {
		if (game.misc.dhits > 0)
			game.state = "assign_hits_on_defender"
		else
			end_battle()
	},
	militia(where) {
		game.misc.ataken += 1
		remove_militia(where)
	},
	legion(id) {
		game.misc.ataken += 1
		if (is_legion_reduced(id))
			set_legion_location(id, AVAILABLE)
		else
			set_legion_reduced(id)
	},
	barbarian(id) {
		game.misc.ataken += 1
		eliminate_barbarian(id)
	},
}

states.assign_hits_on_defender = {
	prompt() {
		prompt("Assign " + (game.misc.dhits - game.misc.dtaken) + " hits!")

		let done = true

		if (game.misc.dtaken < game.misc.dhits) {
			switch (game.misc.type) {
				case "militia":
					done = gen_hits_militia()
					break
				case "rival_emperor":
					done = gen_hits_rival_emperor(game.misc.target)
					break
				case "barbarians":
					done = gen_hits_barbarians(game.misc.target)
					break
				case "general":
					done = gen_hits_general(game.misc.target)
					break
			}
		}

		if (done)
			view.actions.done = 1
	},
	done() {
		end_battle()
	},
	militia(where) {
		game.misc.dtaken += 1
		remove_militia(where)
	},
	legion(id) {
		game.misc.dtaken += 1
		if (is_legion_reduced(id))
			set_legion_location(id, AVAILABLE)
		else
			set_legion_reduced(id)
	},
	barbarian(id) {
		game.misc.dtaken += 1
		eliminate_barbarian(id)
	},
}

function end_battle() {
	// TODO: retreat / advance into capital
	game.state = "take_actions"
}

// === SUPPORT CHECK ===

function goto_support_check() {
	goto_expand_pretender_empire()
}

// === EXPAND PRETENDER EMPIRE ===

function goto_expand_pretender_empire() {
	goto_gain_legacy()
}

// === GAIN LEGACY ===

function goto_gain_legacy() {
	goto_buy_trash_cards()
}

// === BUY / TRASH CARDS ===

function count_political_points() {
	let pp = 0
	for (let where = 0; where < 12; ++where) {
		if (is_own_province(where)) {
			pp += game.support[where]
			pp -= game.mobs[where]
		}
	}
	return pp
}

function goto_buy_trash_cards() {
	let discard = current_discard()
	for (let c of game.played)
		set_add(discard, c)
	game.played.length = 0
	game.misc = {
		count: 0,
		pp: count_political_points(),
	}
	if (current_hand().length > 0)
		game.state = "buy_trash_discard"
	else
		game.state = "buy_trash"
}

states.buy_trash_discard = {
	prompt() {
		prompt("You may discard any number of cards.")
		for (let c of current_hand())
			gen_action_card(c)
		view.actions.done = 1
	},
	card(c) {
		push_undo()
		set_delete(current_hand(), c)
		set_add(current_discard(), c)
	},
	done() {
		push_undo()
		game.state = "buy_trash"
	},
}

function find_market_with_card(c) {
	for (let m of game.market)
		if (set_has(m, c))
			return m
	return null
}

states.buy_trash = {
	prompt() {
		prompt("Buy/Trash cards: " + game.misc.pp + "PP left.")
		let nprov = count_own_provinces()
		if (game.misc.pp >= 3) {
			for (let c of current_discard())
				gen_action_card(c)
		}
		for (let m of game.market) {
			if (m.length > 0) {
				let c = m[0]
				let cost = card_cost(c)
				if (cost > nprov)
					cost *= 2
				cost += game.misc.count
				if (game.misc.pp >= cost)
					gen_action_card(c)
			}
		}
		view.actions.done = 1
	},
	card(c) {
		push_undo()
		if (set_has(current_discard(), c)) {
			log("Trashed " + card_name(c))
			set_delete(current_discard(), c)
			game.misc.pp -= 3
		} else {
			log("Bought " + card_name(c))
			set_add(current_discard(), c)
			set_delete(find_market_with_card(c), c)
			let cost = card_cost(c)
			if (cost > count_own_provinces())
				cost *= 2
			cost += game.misc.count
			game.misc.pp -= cost
			game.misc.count += 1
		}
	},
	done() {
		push_undo()
		goto_end_of_turn()
	},
}

// === END OF TURN ===

function goto_end_of_turn() {
	// TODO: add mobs
	// TODO: flip inactive barbarians
	goto_refill_hand()
}

function goto_refill_hand() {
	if (current_draw().length === 0)
		flip_discard_to_available()
	game.state = "refill_hand"
}

states.refill_hand = {
	prompt() {
		view.prompt = "Refill your hand."
		let hand = current_hand()
		let draw = current_draw()
		if (hand.length < 5 && draw.length > 0) {
			for (let c of draw)
				gen_action_card(c)
		} else {
			view.actions.done = 1
		}
	},
	card(c) {
		push_undo()
		let hand = current_hand()
		let draw = current_draw()
		set_delete(draw, c)
		set_add(hand, c)
		if (draw.length === 0)
			flip_discard_to_available()
	},
	done() {
		clear_undo()
		end_refill_hand()
	}
}

function end_refill_hand() {
	game.current = next_player()
	goto_start_turn()
}

// === SETUP ===

function setup_player_deck(player) {
	return [
		CARD_M1[0] + (player * 3) + 0,
		CARD_M1[0] + (player * 3) + 1,
		CARD_M1[0] + (player * 3) + 2,
		CARD_S1[0] + (player * 3) + 0,
		CARD_S1[0] + (player * 3) + 1,
		CARD_S1[0] + (player * 3) + 2,
		CARD_P1[0] + (player * 3) + 0,
		CARD_P1[0] + (player * 3) + 1,
		CARD_P1[0] + (player * 3) + 2,
	]
}

function setup_events() {
	let deck = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ]
	shuffle(deck)
	// Shuffle Diocletian with last 3 cards
	array_insert(deck, 11 + random(4), 15)
	return deck
}

function setup_market_pile(cards) {
	let pile = []
	for (let c = cards[0]; c <= cards[1]; ++c)
		pile.push(c)
	return pile
}

function setup_barbarians(tribe, home) {
	for (let id = first_barbarian[tribe]; id <= last_barbarian[tribe]; ++id) {
		set_barbarian_location(id, home)
		set_barbarian_inactive(id)
	}
}

exports.setup = function (seed, scenario, options) {
	let real_player_count = options.players || 4
	let player_count = real_player_count
	if (player_count === 1)
		player_count = 4

	game = {
		seed: seed,
		log: [],
		undo: [],
		active: 0,
		current: 0,
		state: "setup_province",
		first: 0,
		events: null,
		active_events: [],

		ip: [],
		selected_governor: -1,
		selected_general: -1,
		played: [],
		used: [],
		placed: 0,
		battled: 0,

		// grab bag of temporary data for the current procedure
		misc: null,

		support: new Array(player_count * 3).fill(1),
		mobs: new Array(player_count * 3).fill(0),
		militia: 0,
		quaestor: 0,
		castra: 0,
		mcastra: 0,
		amphitheater: 0,
		basilica: 0,
		limes: 0,
		breakaway: 0,
		seat_of_power: 0,

		governors: new Array(6 * player_count).fill(UNAVAILABLE),
		generals: new Array(6 * player_count).fill(UNAVAILABLE),
		legions: new Array(LEGION_COUNT).fill(AVAILABLE),
		barbarians: new Array(BARBARIAN_COUNT[player_count]).fill(AVAILABLE),
		rival_emperors: [ UNAVAILABLE, UNAVAILABLE, UNAVAILABLE ],
		barbarian_leaders: [ UNAVAILABLE, UNAVAILABLE, UNAVAILABLE ],

		dice: [ 0, 0, 0, 0 ], // first two are crisis table dice, second two are barbarian homeland dice
		market: null,

		// per-player data
		legacy: new Array(player_count).fill(0),
		emperor_turns: new Array(player_count).fill(0),
		hand: [],
		draw: [],
		discard: [],
	}

	if (real_player_count === 1)
		game.solo = 1

	game.events = setup_events()

	/*
	game.market = [
		setup_market_pile(CARD_M2),
		setup_market_pile(CARD_S2),
		setup_market_pile(CARD_P2),
		setup_market_pile(CARD_M3),
		setup_market_pile(CARD_S3),
		setup_market_pile(CARD_P3),
		setup_market_pile(CARD_M4),
		setup_market_pile(CARD_S4),
		setup_market_pile(CARD_P4),
	]
	 */
	game.market = [
		setup_market_pile(CARD_M2),
		setup_market_pile(CARD_M3),
		setup_market_pile(CARD_M4),
		setup_market_pile(CARD_S2),
		setup_market_pile(CARD_S3),
		setup_market_pile(CARD_S4),
		setup_market_pile(CARD_P2),
		setup_market_pile(CARD_P3),
		setup_market_pile(CARD_P4),
	]

	setup_barbarians(ALAMANNI, ALAMANNI_HOMELAND)
	setup_barbarians(FRANKS, FRANKS_HOMELAND)
	setup_barbarians(GOTHS, GOTHS_HOMELAND)
	if (player_count >= 3)
		setup_barbarians(NOMADS, NOMADS_HOMELAND)
	if (player_count >= 4)
		setup_barbarians(SASSANIDS, SASSANIDS_HOMELAND)

	for (let player = 0; player < player_count; ++player) {
		game.hand[player] = []
		game.draw[player] = setup_player_deck(player)
		game.discard[player] = []
	}

	update_neutral_italia()

	game.first = game.current = random(player_count)
	log("First Player is " + PLAYER_NAMES[game.first] + "!")

	return save_game()
}

function load_game(state) {
	game = state
}

function save_game() {
	if (game.solo)
		game.active = "Solo"
	else
		game.active = PLAYER_NAMES[game.current]
	return game
}

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

function is_current_player(player) {
	if (player === 4)
		return true
	return game.current === player
}

exports.view = function (state, player_name) {
	load_game(state)

	let player = PLAYER_INDEX[player_name]
	if (game.solo)
		player = game.current
	let player_count = game.legacy.length

	view = {
		log: game.log,
		current: game.current,
		prompt: null,

		support: game.support,
		mobs: game.mobs,
		militia: game.militia,
		quaestor: game.quaestor,
		castra: game.castra,
		amphitheater: game.amphitheater,
		basilica: game.basilica,
		limes: game.limes,

		governors: game.governors,
		generals: game.generals,
		legions: game.legions,
		barbarians: game.barbarians,
		rival_emperors: game.rival_emperors,
		barbarian_leaders: game.barbarian_leaders,

		dice: game.dice,
		events: game.active_events,
		played: game.played,
		used: game.used,
		market: game.market.map(m => m[0] | 0),

		legacy: game.legacy,
		emperor_turns: game.emperor_turns,
	}

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

	if (player >= 0 && player < player_count) {
		view.hand = game.hand[player]
		view.draw = game.draw[player]
		view.discard = game.discard[player]
	}

	save_game()
	return view
}

// === MISC ===

function prompt(s) {
	view.prompt = s
}

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

function log_br() {
	if (game.log.length > 0 && game.log[game.log.length - 1] !== "")
		game.log.push("")
}

function log_h1(msg) {
	log_br()
	log(".h1 " + msg)
	log_br()
}

function log_h2(msg) {
	log_br()
	log(".h2 " + msg)
	log_br()
}

function log_h3(msg) {
	log_br()
	log(".h3 " + msg)
}

function logi(msg) {
	game.log.push(">" + msg)
}

function logii(msg) {
	game.log.push(">>" + msg)
}

// === COMMON LIBRARY ===

function roll_die() {
	return random(6) + 1
}

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

function gen_action_general(id) {
	gen_action("general", id)
}

function gen_action_governor(id) {
	gen_action("governor", id)
}

function gen_action_legion(id) {
	gen_action("legion", id)
}

function gen_action_barbarian(id) {
	gen_action("barbarian", id)
}

function gen_action_militia(where) {
	gen_action("militia", where)
}

function gen_action_region(where) {
	gen_action("region", where)
}

function gen_action_capital(where) {
	gen_action("capital", where)
}

function gen_action_recall(where) {
	gen_action("recall", where)
}

function gen_action_support(where, level) {
	gen_action("support", where << 3 | level)
}

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

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

function push_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() {
	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) {
	// An MLCG using integer arithmetic with doubles.
	// https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf
	// m = 2**35 − 31
	return (game.seed = game.seed * 200105 % 34359738337) % range
}

function random_bigint(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
}

function shuffle(list) {
	// Fisher-Yates shuffle
	for (let i = list.length - 1; i > 0; --i) {
		let j = random(i + 1)
		let tmp = list[j]
		list[j] = list[i]
		list[i] = tmp
	}
}

function shuffle_bigint(list) {
	// Fisher-Yates shuffle
	for (let i = list.length - 1; i > 0; --i) {
		let j = random_bigint(i + 1)
		let tmp = list[j]
		list[j] = list[i]
		list[i] = tmp
	}
}

// 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_remove_pair(array, index) {
	let n = array.length
	for (let i = index + 2; i < n; ++i)
		array[i - 2] = array[i]
	array.length = n - 2
}

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_clear(set) {
	set.length = 0
}

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
		}
	}
}

function set_toggle(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
		}
	}
	array_insert(set, a, item)
}

// 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)
}

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