"use strict"

// TODO: game.selected - singleton instead of array

// TODO: re-entering supply trains during movement (10.2)

// TODO: austria/pragmatic action step - show both sides cards and interleave movement on flanders map
// PLAN: move all austria on bohemia first, then alternate pragmatic and austria activations on flanders map
// TODO: confirm mixed stack creation on flanders map (force "undo" to previous location if denied?)

// TODO: supreme commander in mixed stacks
// TODO: TC subsidies
// TODO: subsidy markers?

const R_LOUIS_XV = "Louis XV"
const R_FREDERICK = "Frederick"
const R_MARIA_THERESA = "Maria Theresa"

exports.roles = [ R_LOUIS_XV, R_FREDERICK, R_MARIA_THERESA ]

exports.scenarios = [ "Advanced" ]

/* DATA */

var game
var view
var states = {}

const data = require("./data")

function is_bohemia_space(s) {
	return s >= 0 && s <= 401
}

function is_flanders_space(s) {
	return s >= 402 && s <= 618
}

function is_map_space(s) {
	return s >= 0 && s <= 618
}

function find_city(city) {
	let n = data.cities.name.length
	let x = -1
	for (let c = 0; c < n; ++c) {
		if (data.cities.name[c] === city) {
			if (x < 0)
				x = c
			else
				throw "TWO CITIES: " + city
		}
	}
	if (x < 0)
		throw "CITY NOT FOUND: " + city
	return x
}

function find_city_list(names) {
	let list = []
	for (let n of names)
		set_add(list, find_city(n))
	return list
}

const deck_name = [ "red", "green", "blue", "yellow" ]
const suit_name = [ "\u2660", "\u2663", "\u2665", "\u2666", "R" ]

const P_FRANCE = 0
const P_BAVARIA = 1
const P_PRUSSIA = 2
const P_SAXONY = 3
const P_PRAGMATIC = 4
const P_AUSTRIA = 5

const POWER_NAME = [ "France", "Bavaria", "Prussia", "Saxony", "Pragmatic Army", "Austria" ]

const SPADES = 0
const CLUBS = 1
const HEARTS = 2
const DIAMONDS = 3
const RESERVE = 4

const IMPERIAL_ELECTION = 25

const ELIMINATED = data.cities.name.length
const REMOVED = ELIMINATED + 1

const max_power_troops = [ 5*8, 1*8, 4*8, 1*8, 3*8, 6*8 ]

const all_powers = [ 0, 1, 2, 3, 4, 5 ]

const all_home_or_depot_cities = [
]

const all_power_depots = [
]

const all_power_re_entry_cities = [
]

const all_power_generals = [
	[ 0, 1, 2, 3, 4 ],
	[ 5 ],
	[ 6, 7, 8, 9 ],
	[ 10 ],
	[ 11, 12, 13 ],
	[ 14, 15, 16, 17, 18, 19 ],
]

const all_power_trains = [
	[ 20, 21 ],
	[ 22 ],
	[ 23, 24 ],
	[ 25 ],
	[ 26 ],
	[ 27, 28, 29 ],
]

const last_piece = 29

const all_hussars = [ 30, 31 ]

const piece_power = [
	P_FRANCE, P_FRANCE, P_FRANCE, P_FRANCE, P_FRANCE,
	P_BAVARIA,
	P_PRUSSIA, P_PRUSSIA, P_PRUSSIA, P_PRUSSIA,
	P_SAXONY,
	P_PRAGMATIC, P_PRAGMATIC, P_PRAGMATIC,
	P_AUSTRIA, P_AUSTRIA, P_AUSTRIA, P_AUSTRIA, P_AUSTRIA, P_AUSTRIA,
	P_FRANCE, P_FRANCE,
	P_BAVARIA,
	P_PRUSSIA, P_PRUSSIA,
	P_SAXONY,
	P_PRAGMATIC,
	P_AUSTRIA, P_AUSTRIA, P_AUSTRIA,
	P_AUSTRIA, P_AUSTRIA
]

const piece_name = [
	"Moritz",
	"Belle-Isle",
	"Broglie",
	"Maillebois",
	"Noailles",
	"Törring",
	"Friedrich",
	"Schwerin",
	"Leopold",
	"Dessauer",
	"Rutowski",
	"George II",
	"Cumberland",
	"Earl of Stair",
	"Karl",
	"Traun",
	"Khevenhüller",
	"Batthyány",
	"Neipperg",
	"Arenberg",
	"supply train", "supply train",
	"supply train",
	"supply train", "supply train",
	"supply train",
	"supply train",
	"supply train", "supply train", "supply train",
	"hussar", "hussar",
]

const all_power_generals_rev = all_power_generals.map(list => list.slice().reverse())

const all_pieces = [ ...all_power_generals.flat(), ...all_power_trains.flat() ]
const all_generals = [ ...all_power_generals.flat() ]

const all_france_bavaria_generals = [
	...all_power_generals[P_FRANCE],
	...all_power_generals[P_BAVARIA],
]

const all_prussia_saxony_generals = [
	...all_power_generals[P_PRUSSIA],
	...all_power_generals[P_SAXONY],
]

const all_austria_pragmatic_generals = [
	...all_power_generals[P_AUSTRIA],
	...all_power_generals[P_PRAGMATIC],
]

const all_france_bavaria_trains = [
	...all_power_trains[P_FRANCE],
	...all_power_trains[P_BAVARIA],
]

const all_prussia_saxony_trains = [
	...all_power_trains[P_PRUSSIA],
	...all_power_trains[P_SAXONY],
]

const all_austria_pragmatic_trains = [
	...all_power_trains[P_AUSTRIA],
	...all_power_trains[P_PRAGMATIC],
]

const all_france_allied_trains = [
	...all_power_trains[P_FRANCE],
	...all_power_trains[P_BAVARIA],
	...all_power_trains[P_PRUSSIA],
	...all_power_trains[P_SAXONY],
]

const all_austria_allied_trains = [
	...all_power_trains[P_AUSTRIA],
	...all_power_trains[P_PRAGMATIC],
]

const all_austria_allied_generals = [
	...all_power_generals[P_AUSTRIA],
	...all_power_generals[P_PRAGMATIC],
]

const all_france_allied_generals = [
	...all_power_generals[P_FRANCE],
	...all_power_generals[P_BAVARIA],
	...all_power_generals[P_PRUSSIA],
	...all_power_generals[P_SAXONY],
]

const all_powers_prussia_saxony_pragmatic_austria = [ P_PRUSSIA, P_SAXONY, P_PRAGMATIC, P_AUSTRIA ]
const all_powers_france_bavaria_pragmatic_austria = [ P_FRANCE, P_BAVARIA, P_PRAGMATIC, P_AUSTRIA ]
const all_powers_france_bavaria_prussia_saxony = [ P_FRANCE, P_BAVARIA, P_PRUSSIA, P_SAXONY ]

function all_non_coop_powers(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
		return all_powers_prussia_saxony_pragmatic_austria
	case P_PRUSSIA:
	case P_SAXONY:
		return all_powers_france_bavaria_pragmatic_austria
	case P_PRAGMATIC:
	case P_AUSTRIA:
		return all_powers_france_bavaria_prussia_saxony
	}
}

function all_coop_generals(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
		return all_france_bavaria_generals
	case P_PRUSSIA:
	case P_SAXONY:
		return all_prussia_saxony_generals
	case P_PRAGMATIC:
	case P_AUSTRIA:
		return all_austria_pragmatic_generals
	}
}

function all_controlled_generals(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
		return all_france_bavaria_generals
	case P_PRUSSIA:
	case P_SAXONY:
		return all_prussia_saxony_generals
	case P_PRAGMATIC:
		return all_power_generals[P_PRAGMATIC]
	case P_AUSTRIA:
		return all_power_generals[P_AUSTRIA]
	}
}

function all_controlled_trains(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
		return all_france_bavaria_trains
	case P_PRUSSIA:
	case P_SAXONY:
		return all_prussia_saxony_trains
	case P_PRAGMATIC:
		return all_power_trains[P_PRAGMATIC]
	case P_AUSTRIA:
		return all_power_trains[P_AUSTRIA]
	}
}

function all_allied_trains(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
	case P_PRUSSIA:
	case P_SAXONY:
		return all_france_allied_trains
	case P_AUSTRIA:
	case P_PRAGMATIC:
		return all_austria_allied_trains
	}
}

function all_enemy_trains(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
	case P_PRUSSIA:
	case P_SAXONY:
		return all_austria_allied_trains
	case P_AUSTRIA:
	case P_PRAGMATIC:
		return all_france_allied_trains
	}
}

function all_enemy_generals(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
	case P_PRUSSIA:
	case P_SAXONY:
		return all_austria_allied_generals
	case P_AUSTRIA:
	case P_PRAGMATIC:
		return all_france_allied_generals
	}
}

function is_general(p) {
	return p < 20
}

function is_supply_train(p) {
	return p >= 20 && p < 30
}

function is_hussar(p) {
	return p >= 30 && p < 32
}

function to_deck(c) {
	return c >> 7
}

function to_suit(c) {
	return (c >> 4) & 7
}

function to_value(c) {
	if (to_suit(c) === RESERVE)
		return 8
	return c & 15
}

function format_card_prompt(c) {
	if (is_reserve(c))
		return "8R"
	return to_value(c) + suit_name[to_suit(c)]
}

function format_card(c) {
	return (to_deck(c)+1) + "^" + format_card_prompt(c)
}

function format_reserve(c, v) {
	return (to_deck(c)+1) + "^" + v + "R"
}

function is_reserve(c) {
	return to_suit(c) === RESERVE
}

function format_card_list_prompt(list) {
	if (list.length > 0)
		return list.map(format_card_prompt).join(", ")
	return "nothing"
}

function format_selected() {
	if (Array.isArray(game.selected)) {
		if (game.selected.length === 0)
			return "nobody"
		return game.selected.map(p => piece_name[p]).join(" and ")
	} else {
		if (game.selected < 0)
			return "nobody"
		return piece_name[game.selected]
	}
}

function log_move_to(to) {
	let from = game.pos[game.selected]
	log("@" + game.selected + ";" + from + "," + to)
}

function log_move_path() {
	if (game.move_path.length > 1)
		log("@" + game.selected + ";" + game.move_path.join(","))
}

/* OBJECTIVES */

const all_objectives = []
set_add_all(all_objectives, data.type.major_fortress)
set_add_all(all_objectives, data.type.minor_fortress)

const protect_range = []
for (let s of all_objectives)
	make_protect_range(protect_range[s] = [], s, s, 3)

function make_protect_range(result, start, here, range) {
	for (let next of data.cities.adjacent[here]) {
		if (next !== start)
			set_add(result, next)
		if (range > 1)
			make_protect_range(result, start, next, range - 1)
	}
}

function is_enemy_controlled_fortress(s) {
	// TODO
	return false
}

function is_conquest_space(_pow, s) {
	// TODO
	return set_has(all_objectives, s)
}

function is_reconquest_space(_pow, s) {
	// TODO
	return set_has(all_objectives, s)
}

function is_space_protected_by_piece(s, p) {
	return set_has(protect_range[s], game.pos[p])
}

function is_protected_from_conquest(s) {
	for (let pow of all_powers) {
		for (let p of all_power_generals[pow])
			if (is_space_protected_by_piece(s, p))
				return true
	}
	return false
}

function is_protected_from_reconquest(s) {
	for (let pow of all_powers) {
		for (let p of all_power_generals[pow])
			if (is_space_protected_by_piece(s, p))
				return true
	}
	return false
}

/* STATE */

const tc_per_turn_table = [ 5, 1, 3, 1, 3, 5 ]

function tc_per_turn() {
	let n = tc_per_turn_table[game.power]

	// TODO: subsidies

	return n
}

const player_from_power_table = [
	R_LOUIS_XV,
	R_LOUIS_XV,
	R_FREDERICK,
	R_FREDERICK,
	R_FREDERICK,
	R_MARIA_THERESA,
]

function player_from_power(pow) {
	// TOOD: saxony allies with austria
	return player_from_power_table[pow]
}

function set_active_to_power(power) {
	game.power = power
	game.active = current_player()
}

function current_player() {
	return player_from_power(game.power)
}

function get_top_piece(s) {
	for (let p of all_pieces)
		if (game.pos[p] === s)
			return p
	return -1
}

function get_supreme_commander(s) {
	// TODO: promoted minor power (check who is actually on top!)
	for (let p of all_generals)
		if (game.pos[p] === s)
			return p
	return -1
}

function get_stack_power(s) {
	return piece_power[get_supreme_commander(s)]
}

function is_space_suit(s, ranges) {
	for (let [a, b] of ranges)
		if (s >= a && s <= b)
			return true
	return false
}

function get_space_suit(s) {
	if (s >= ELIMINATED)
		return SPADES
	if (is_space_suit(s, data.suit.spades))
		return SPADES
	if (is_space_suit(s, data.suit.clubs))
		return CLUBS
	if (is_space_suit(s, data.suit.hearts))
		return HEARTS
	if (is_space_suit(s, data.suit.diamonds))
		return DIAMONDS
	throw "IMPOSSIBLE"
}

function count_eliminated_trains() {
	let n = 0
	for (let p of all_power_trains[game.power])
		if (game.pos[p] === ELIMINATED)
			++n
	return n
}

function count_eliminated_generals() {
	let n = 0
	for (let p of all_power_generals[game.power])
		if (game.pos[p] === ELIMINATED)
			++n
	return n
}

function count_used_troops() {
	let current = 0
	for (let p of all_power_generals[game.power])
		current += game.troops[p]
	return current
}

function count_unused_troops_on_map() {
	let n = 0
	for (let p of all_power_generals[game.power])
		if (is_map_space(game.pos[p]))
			n += 8 - game.troops[p]
	return n
}

function has_any_piece(to) {
	for (let p = 0; p <= last_piece; ++p)
		if (game.pos[p] === to)
			return true
	return false
}

function has_friendly_supply_train(to) {
	for (let p of all_allied_trains(game.power))
		if (game.pos[p] === to)
			return true
	return false
}

function has_enemy_supply_train(to) {
	for (let p of all_enemy_trains(game.power))
		if (game.pos[p] === to)
			return true
	return false
}

function has_enemy_general(to) {
	for (let p of all_enemy_generals(game.power))
		if (game.pos[p] === to)
			return true
	return false
}

function has_enemy_piece(to) {
	for (let p of all_enemy_generals(game.power))
		if (game.pos[p] === to)
			return true
	for (let p of all_enemy_trains(game.power))
		if (game.pos[p] === to)
			return true
	return false
}

function has_non_cooperative_general(to) {
	for (let other of all_non_coop_powers(game.power))
		for (let p of all_controlled_generals(other))
			if (game.pos[p] === to)
				return true
	return false
}

function has_own_general(to) {
	for (let p of all_power_generals[game.power])
		if (game.pos[p] === to)
			return true
	return false
}

function count_generals(to) {
	let n = 0
	for (let p of all_generals)
		if (game.pos[p] === to)
			++n
	return n
}

function select_stack(s) {
	let list = []
	for (let p of all_generals)
		if (game.pos[p] === s)
			list.push(p)
	return list
}

function add_one_troop(p) {
	for (let x of all_power_generals[game.power]) {
		if (game.pos[x] === game.pos[p] && game.troops[x] < 8) {
			game.troops[x] ++
			break
		}
	}
}

function remove_one_troop(p) {
	for (let x of all_power_generals_rev[game.power]) {
		if (game.pos[x] === game.pos[p] && game.troops[x] > 1) {
			game.troops[x] --
			break
		}
	}
}

function retire_general(p) {
	// save troops if possible
	let s = game.pos[p]
	let n = game.troops[p]
	game.pos[p] = REMOVED
	game.troops[p] = 0
	set_in_supply(p)

	if (is_map_space(s)) {
		for (let p of all_power_generals[game.power]) {
			if (game.pos[p] === s) {
				let x = Math.min(n, 8 - game.troops[p])
				game.troops[p] += x
				n -= x
			}
		}
		if (n > 1)
			log("P" + p + " retired with " + n + " troops.")
		else if (n === 1)
			log("P" + p + " retired with 1 troop.")
		else
			log("P" + p + " retired.")
	} else {
		log("P" + p + " retired.")
	}
}

function eliminate_general(p, indent) {
	if (indent)
		log(">P" + p + " eliminated")
	else
		log("P" + p + " eliminated.")
	game.pos[p] = ELIMINATED
	game.troops[p] = 0
	set_in_supply(p)
}

/* SEQUENCE OF PLAY */

const POWER_FROM_ACTION_STEP = [
	P_FRANCE, // and bavaria
	P_PRUSSIA, // and saxony
	P_AUSTRIA, // and pragmatic army -- interleave with pragmatic moves on flanders map
	P_PRAGMATIC, // interleave with austria moves on flanders map
]

function set_active_to_current_action_step() {
	set_active_to_power(POWER_FROM_ACTION_STEP[game.step])
}

function goto_end_turn() {
	// TODO: winter
	goto_start_turn()
}

function goto_start_turn() {
	game.turn += 1
	game.step = 0

	log("# Turn " + game.turn)

	game.selected = -1
	delete game.ia_lost

	// MARIA: politics
	// MARIA: hussars

	goto_place_hussars()
}

function goto_action_stage() {
	set_active_to_current_action_step()

	clear_undo()

	log("=" + game.power)

	// TODO: minor powers controlled at the same time

	goto_tactical_cards()
}

function end_action_stage() {
	clear_undo()

	if (++game.step === 4)
		goto_end_turn()
	else
		goto_action_stage()
}

/* VICTORY */

function check_victory() {
	// TODO
	return false
}

/* HUSSARS */

function goto_place_hussars() {
	set_active_to_power(P_AUSTRIA)
	game.state = "place_hussars"
}

function end_place_hussars() {
	set_clear(game.moved)
	goto_action_stage()
}

states.place_hussars = {
	inactive: "place Hussars",
	prompt() {
		prompt("Place the Hussars.")
		for (let p of all_hussars)
			if (!set_has(game.moved, p))
				gen_action_piece(p)
		view.actions.next = 1
	},
	piece(p) {
		push_undo()
		set_add(game.moved, p)
		game.selected = p
		game.state = "place_hussars_where"
	},
	next() {
		end_place_hussars()
	},
}

states.place_hussars_where = {
	inactive: "place Hussars",
	prompt() {
		prompt("Place the Hussar in a city.")
		view.selected = game.selected

		// bohemia
		// within 4 of an austrian general
		// not occupied by any piece
		for (let p of all_power_generals[P_AUSTRIA]) {
			let s = game.pos[p]
			if (is_bohemia_space(s))
				for (let x of search_hussar_bfs(s))
					gen_action_space(x)
		}
	},
	space(to) {
		game.state = "place_hussars"
		game.pos[game.selected] = to
		game.selected = -1
	},
}

function search_hussar_bfs(from) {
	let seen = [ from ]
	let queue = [ from << 4 ]
	while (queue.length > 0) {
		let item = queue.shift()
		let here = item >> 4
		let dist = (item & 15) + 1
		for (let next of data.cities.adjacent[here]) {
			if (set_has(seen, next))
				continue
			if (!is_bohemia_space(next))
				continue
			if (!has_any_piece(next))
				set_add(seen, next)
			if (dist < 4)
				queue.push((next << 4) | dist)
		}
	}
	set_delete(seen, from)
	return seen
}

/* TACTICAL CARDS */

function find_largest_discard(u) {
	for (let i = 0; i < 4; ++i)
		if (u[i] <= u[0] && u[i] <= u[1] && u[i] <= u[2] && u[i] <= u[3])
			return i
	throw "OUT OF CARDS"
}

function count_used_cards() {
	let held = [ 0, 0, 0, 0 ]

	// count cards in hands
	for (let pow of all_powers) {
		for (let c of game.hand[pow])
			held[to_deck(c)]++
	}

	// count cards currently being held
	if (game.draw)
		for (let c of game.draw)
			held[to_deck(c)]++

	// count cards remaining in deck
	for (let c of game.deck)
		held[to_deck(c)]++

	return held
}

function next_tactics_deck() {
	let held = count_used_cards()

	// find next unused deck
	for (let i = 1; i < 5; ++i) {
		if (held[i] === 0) {
			game.deck = make_tactics_deck(i)
			shuffle_bigint(game.deck)
			log("Shuffled " + deck_name[i] + ".")
			return
		}
	}

	// find two largest discard piles
	let a = find_largest_discard(held)
	if (held[a] === 38)
		return
	held[a] = 100

	let b = find_largest_discard(held)
	if (held[b] === 38)
		return

	log("Shuffled " + deck_name[a] + " and " + deck_name[b] + ".")

	game.deck = [
		make_tactics_discard(a),
		make_tactics_discard(b)
	].flat()

	shuffle_bigint(game.deck)
}

function total_discard_list() {
	let discard = count_used_cards()
	for (let i = 0; i < 4; ++i)
		discard[i] = Math.ceil((38 - discard[i]) / 5)
	return discard
}

function draw_tc(n) {
	game.draw = []

	let k = 0
	while (n > 0) {
		if (game.deck.length === 0) {
			if (k > 0)
				log(POWER_NAME[game.power] + " " + k + " TC.")
			k = 0
			next_tactics_deck()
			if (game.deck.length === 0) {
				log("The cards ran out!")
				break
			}
		}
		set_add(game.draw, game.deck.pop())
		++k
		--n
	}

	if (k > 0)
		log(POWER_NAME[game.power] + " " + k + " TC.")
}

function goto_tactical_cards() {

	// TODO: no TC (even subsidy) if major fortress is enemy controlled

	draw_tc(tc_per_turn())

	game.state = "tactical_cards_show"
}

states.tactical_cards_show = {
	inactive: "draw tactical cards",
	prompt() {
		view.draw = game.draw
		prompt("Draw " + format_card_list_prompt(game.draw) + ".")
		view.actions.end_cards = 1
	},
	end_cards() {
		end_tactical_cards()
	},
}

function end_tactical_cards() {
	for (let c of game.draw)
		set_add(game.hand[game.power], c)
	delete game.draw

	// MARIA: supply is before movement

	if (game.power === P_FRANCE) {
		set_active_to_power(P_BAVARIA)
		goto_tactical_cards()
		return
	}
	if (game.power === P_BAVARIA)
		set_active_to_power(P_FRANCE)

	if (game.power === P_PRUSSIA) {
		set_active_to_power(P_SAXONY)
		goto_tactical_cards()
		return
	}
	if (game.power === P_SAXONY)
		set_active_to_power(P_PRUSSIA)

	// TODO: draw pragmatic cards before austria moves

	// MARIA TODO: supply!

	goto_movement()
}

/* TRANSFER TROOPS */

function find_unstacked_general() {
	let here = game.pos[game.selected]
	for (let p of all_power_generals[game.power])
		if (game.pos[p] === here && game.selected !== p)
			return p
	return -1
}

function count_stacked_take() {
	return 8 - game.troops[game.selected]
}

function count_unstacked_take() {
	let p = find_unstacked_general()
	if (p < 0)
		return 0
	return 8 - game.troops[p]
}

function count_stacked_give() {
	return game.troops[game.selected] - 1
}

function count_unstacked_give() {
	let p = find_unstacked_general()
	if (p < 0)
		return 0
	return game.troops[p] - 1
}

function take_troops(total) {
	game.troops[game.selected] += total
	game.troops[find_unstacked_general()] -= total
}

function give_troops(total) {
	game.troops[game.selected] -= total
	game.troops[find_unstacked_general()] += total
}

/* MOVEMENT */

function movement_range() {
	return 3
}

function goto_movement() {
	game.state = "movement"
	set_clear(game.moved)

	log_br()

	game.move_conq = []
	game.move_reconq = []
}

function can_train_move_anywhere(p) {
	let from = game.pos[p]
	for (let to of data.cities.adjacent[from])
		if (can_move_train_to(to))
			return true
	return false
}

function can_general_move_anywhere(p) {
	let from = game.pos[p]
	for (let to of data.cities.adjacent[from])
		if (can_move_general_to(from, to))
			return true
	return false
}

states.movement = {
	inactive: "move",
	prompt() {
		let done_generals = true
		let done_trains = true

		for (let p of all_controlled_generals(game.power)) {
			if (!set_has(game.moved, p) && is_map_space(game.pos[p])) {
				if (can_general_move_anywhere(p)) {
					gen_action_piece(p)
					done_generals = false
				}
			}
		}

		for (let p of all_controlled_trains(game.power)) {
			if (!set_has(game.moved, p) && is_map_space(game.pos[p])) {
				if (can_train_move_anywhere(p)) {
					gen_action_piece(p)
					done_trains = false
				}
			}
		}

		if (done_trains && done_generals)
			prompt("Movement done.")
		else if (done_generals && !done_trains)
			prompt("Move your supply trains.")
		else if (!done_generals && done_trains)
			prompt("Move your generals.")
		else
			prompt("Move your generals and supply trains.")

		if (game.moved.length === 0)
			view.actions.confirm_end_movement = 1
		else
			view.actions.end_movement = 1
	},
	piece(p) {
		push_undo()

		let here = game.pos[p]

		set_active_to_power(piece_power[p])

		game.selected = p

		game.count = 0

		if (data.cities.main_roads[here].length > 0)
			game.main = 1
		else
			game.main = 0

		game.move_path = [ here ]
		if (is_supply_train(p))
			game.state = "move_supply_train"
		else
			game.state = "move_general"
	},
	confirm_end_movement() {
		this.end_movement()
	},
	end_movement() {
		push_undo()

		if (game.moved.length === 0)
			log("Nothing moved.")

		set_clear(game.moved)

		log_conquest(game.move_conq, game.move_reconq)
		delete game.move_conq
		delete game.move_reconq

		// MARIA: recruit during winter goto_recruit()
		goto_combat()
	},
}

function format_move(max) {
	let n = max - game.count
	if (game.main)
		return ` up to ${n} cities (${n+1} on main roads).`
	return ` up to ${n} cities.`
}

function can_move_train_to(to) {
	return !has_any_piece(to)
}

function is_illegal_cross_map_move(from, to) {
	return (
		game.power !== P_FRANCE && game.power !== P_AUSTRIA && (
			(is_flanders_space(from) && is_bohemia_space(to)) ||
			(is_flanders_space(to) && is_bohemia_space(from))
		)
	)
}

function can_move_general_to(from, to) {
	if (is_illegal_cross_map_move(from, to))
		return false
	if (has_friendly_supply_train(to))
		return false
	if (has_non_cooperative_general(to))
		return false
	if (has_enemy_supply_train(to))
		return false
	if (count_generals(to) >= 2)
		return false
	return true
}

function move_general_to(to, is_force_march) {
	let pow = game.power
	let who = game.selected
	let from = game.pos[who]
	let stop = false

	set_add(game.moved, game.selected)
	game.pos[game.selected] = to

	// Cannot conquer if force marching.
	// Cannot conquer if out of supply.
	if (!is_force_march && !is_out_of_supply(who)) {

		// conquer space
		if (is_conquest_space(pow, from) && !set_has(game.conquest, from)) {
			if (is_protected_from_conquest(from)) {
				set_add(game.retro, from)
			} else {
				set_add(game.move_conq, from)
				set_add(game.conquest, from)
			}
		}

		// re-conquer space
		if (is_reconquest_space(pow, from) && set_has(game.conquest, from)) {
			if (is_protected_from_reconquest(from)) {
				set_add(game.retro, from)
			} else {
				set_add(game.move_reconq, from)
				set_delete(game.conquest, from)
			}
		}

	}

	// eliminate supply train
	for (let p of all_enemy_trains(pow)) {
		if (game.pos[p] === to) {
			if (!game.move_elim)
				game.move_elim = []
			set_add(game.move_elim, p)
			game.pos[p] = ELIMINATED
			// NOTE: eliminating a supply train does not stop movement!
		}
	}

	// uniting stacks: flag all as moved and stop moving
	for (let p of all_coop_generals(pow)) {
		if (game.pos[p] === to && game.selected !== p) {
			set_add(game.moved, p)
			stop = true
		}
	}

	// remove hussars
	for (let p of all_hussars) {
		if (game.pos[p] === to) {
			if (!game.move_elim)
				game.move_elim = []
			set_add(game.move_elim, p)
			game.pos[p] = ELIMINATED
		}
	}

	return stop
}

states.move_supply_train = {
	inactive: "move",
	prompt() {
		prompt("Move supply train" + format_move(2))
		view.selected = game.selected

		let who = game.selected
		let here = game.pos[who]

		if (game.count < 2 + game.main)
			for (let next of data.cities.main_roads[here])
				if (!has_any_piece(next))
					gen_action_space(next)
		if (game.count < 2)
			for (let next of data.cities.roads[here])
				if (!has_any_piece(next))
					gen_action_space(next)

		if (game.count > 0)
			gen_action_piece(who)
		view.actions.stop = 1
	},
	piece(_) {
		this.stop()
	},
	stop() {
		let who = game.selected
		set_add(game.moved, who)
		end_move_piece()
	},
	space(to) {
		let who = game.selected
		let from = game.pos[who]

		game.move_path.push(to)

		if (!set_has(data.cities.main_roads[from], to))
			game.main = 0

		set_add(game.moved, who)
		game.pos[who] = to

		if (++game.count === 2 + game.main)
			end_move_piece()
	},
}

states.move_general = {
	inactive: "move",
	prompt() {
		prompt("Move " + format_selected() + format_move(movement_range()))
		view.selected = game.selected

		let who = game.selected
		let here = game.pos[who]

		if (game.count === 0) {
			if (data.cities.main_roads[here].length > 0)
				view.actions.force_march = 1

			let s_take = count_stacked_take()
			let s_give = count_stacked_give()
			let u_take = count_unstacked_take()
			let u_give = count_unstacked_give()

			if (s_take > 0 && u_give > 0)
				view.actions.take = 1
			if (s_give > 0 && u_take > 0)
				view.actions.give = 1

			view.actions.stop = 1
		} else {
			gen_action_piece(who)
			view.actions.stop = 1
		}

		if (game.count < movement_range() + game.main)
			for (let next of data.cities.main_roads[here])
				if (can_move_general_to(here, next))
					gen_action_space_or_piece(next)

		if (game.count < movement_range())
			for (let next of data.cities.roads[here])
				if (can_move_general_to(here, next))
					gen_action_space_or_piece(next)
	},
	take() {
		game.state = "move_take"
	},
	give() {
		game.state = "move_give"
	},
	piece(p) {
		if (game.count === 0) {
			this.space(game.pos[p])
		} else {
			if (p === game.selected)
				this.stop()
			else
				this.space(game.pos[p])
		}
	},
	stop() {
		set_add(game.moved, game.selected)
		end_move_piece()
	},
	space(to) {
		let who = game.selected
		let from = game.pos[who]

		game.move_path.push(to)

		if (!set_has(data.cities.main_roads[from], to))
			game.main = 0

		if (move_general_to(to, false) || ++game.count === movement_range() + game.main)
			end_move_piece()
	},
	force_march() {
		game.state = "force_march"
	}
}

function is_adjacent_to_enemy_piece(here) {
	for (let next of data.cities.adjacent[here])
		if (has_enemy_piece(next))
			return true
	return false
}

function search_force_march(came_from, start) {
	let seen = [ start ]
	let queue = [ start << 4 ]
	while (queue.length > 0) {
		let item = queue.shift()
		let here = item >> 4
		let dist = (item & 15) + 1
		for (let next of data.cities.main_roads[here]) {
			if (set_has(seen, next))
				continue
			if (is_enemy_controlled_fortress(next))
				continue
			if (has_enemy_piece(next))
				continue
			if (is_adjacent_to_enemy_piece(next))
				continue
			if (!can_move_general_to(here, next))
				continue
			if (came_from)
				map_set(came_from, next, here)
			set_add(seen, next)
			if (dist < 8)
				queue.push((next << 4) | dist)
		}
	}
	set_delete(seen, start)
	return seen
}

// TODO: choose not-shortest path to capture hussars during force march?
states.force_march = {
	inactive: "move",
	prompt() {
		prompt("Force March " + format_selected() + ".")
		view.selected = game.selected

		let here = game.pos[game.selected]
		for (let s of search_force_march(null, here))
			gen_action_space(s)
	},
	space(to) {
		let here = game.pos[game.selected]
		let came_from = []

		search_force_march(came_from, here)

		let path = []
		while (to !== here) {
			path.unshift(to)
			to = map_get(came_from, to)
		}

		for (let s of path) {
			game.move_path.push(s)
			move_general_to(s, true)
		}

		end_move_piece()
	},
}

states.move_take = {
	inactive: "move",
	prompt() {
		prompt("Transfer troops to " + format_selected() + ".")
		view.selected = game.selected
		let take = count_stacked_take()
		let give = count_unstacked_give()
		let n = Math.min(take, give)
		view.actions.value = []
		for (let i = 1; i <= n; ++i)
			view.actions.value.push(i)
	},
	value(v) {
		take_troops(v)
		if (game.state === "laudon_take")
			game.state = "austria_may_move_laudon_by_one_city_immediately"
		else
			game.state = "move_general"
	},
}

states.move_give = {
	inactive: "move",
	prompt() {
		prompt("Transfer troops from " + format_selected() + ".")
		view.selected = game.selected
		let take = count_unstacked_take()
		let give = count_stacked_give()
		let n = Math.min(take, give)
		view.actions.value = []
		for (let i = 1; i <= n; ++i)
			view.actions.value.push(i)
	},
	value(v) {
		give_troops(v)
		if (game.state === "laudon_give")
			game.state = "austria_may_move_laudon_by_one_city_immediately"
		else
			game.state = "move_general"
	},
}

function end_move_piece() {
	log_move_path()

	if (game.move_elim) {
		for (let p of game.move_elim)
			log("P" + p + " eliminated.")
		delete game.move_elim
	}

	delete game.move_path
	game.selected = -1
	game.state = "movement"

	set_active_to_current_action_step()
}

/* RECRUITMENT */

function troop_cost() {
	if (is_map_space(game.recruit.re_enter))
		return 8
	return 6
}

function sum_card_values(list) {
	let n = 0
	for (let c of list)
		n += to_value(c)
	return n
}

function find_largest_card(list) {
	for (let v = 10; v >= 2; --v) {
		for (let c of list)
			if (to_value(c) === v)
				return c
	}
	throw "NO CARDS FOUND IN LIST"
}

function spend_recruit_cost() {
	let spend = troop_cost()
	if (game.count > 0) {
		if (spend < game.count) {
			game.count -= spend
			spend = 0
		} else {
			spend -= game.count
			game.count = 0
		}
	}
	while (spend > 0) {
		let c = find_largest_card(game.recruit.pool)
		let v = to_value(c)
		set_delete(game.recruit.pool, c)
		set_add(game.recruit.used, c)
		if (v > spend) {
			game.count = v - spend
			spend = 0
		} else {
			spend -= v
		}
	}
}

function has_available_depot() {
	for (let s of all_power_depots[game.power])
		// TODO: also allied other player's pieces?
		if (!has_enemy_piece(s))
			return true
	return false
}

function can_re_enter_general(to) {
	if (has_friendly_supply_train(to))
		return false
	if (has_non_cooperative_general(to))
		return false
	if (1 + count_generals(to) > 3)
		return false
	return true
}

function can_re_enter_supply_train(s) {
	return !has_any_piece(s)
}

function goto_recruit() {
	game.count = 0

	if (!can_recruit_anything_in_theory()) {
		end_recruit()
		return
	}

	game.recruit = {
		pool: [],
		used: [],
		pieces: [],
		re_enter: ELIMINATED,
		troops: 0,
	}

	// if all depots have enemy pieces, choose ONE city in given sector and COST is 8
	if (has_available_depot())
		game.state = "recruit"
	else
		game.state = "re_enter_choose_city"
}

states.re_enter_choose_city = {
	inactive: "recruit",
	prompt() {
		prompt("Choose city to re-enter troops.")
		for (let s of all_power_re_entry_cities[game.power])
			if (!has_enemy_piece(s))
				gen_action_space(s)
	},
	space(s) {
		push_undo()
		game.recruit.re_enter = s
		game.state = "recruit"
	},
}

function has_re_entry_space(p) {
	let can_re_enter_at = is_general(p) ? can_re_enter_general : can_re_enter_supply_train
	if (is_map_space(game.recruit.re_enter))
		return can_re_enter_at(game.recruit.re_enter)
	for (let s of all_power_depots[game.power])
		if (can_re_enter_at(s))
			return true
	return false
}

function is_attack_position(s) {
	for (let p of all_enemy_generals(game.power))
		if (set_has(data.cities.adjacent[s], game.pos[p]))
			return true
	return false
}

function can_recruit_anything_in_theory() {
	let unused_everywhere = max_power_troops(game.power) - count_used_troops()
	return unused_everywhere > 0 || count_eliminated_trains() > 0
}

function can_recruit_anything() {
	let unused_everywhere = max_power_troops(game.power) - count_used_troops()
	let elim_trains = count_eliminated_trains()
	let elim_generals = count_eliminated_generals()
	let unused_on_map = count_unused_troops_on_map()
	// can reinforce on-map generals
	if (unused_everywhere > 0 && unused_on_map > 0)
		return true
	// can re-enter eliminated generals
	if (unused_everywhere > 0 && elim_generals > 0 && has_re_entry_space())
		return true
	// can re-enter eliminated supply trains
	if (elim_trains > 0 && has_re_entry_space())
		return true
	return false
}

states.recruit = {
	inactive: "recruit",
	prompt() {
		let cost = troop_cost()
		let n_troops = count_used_troops()
		let av_troops = max_power_troops(game.power) - n_troops
		let av_trains = count_eliminated_trains()
		let possible = can_recruit_anything()

		let str
		if (av_trains > 0 && av_troops > 0)
			str = `Recruit supply trains and up to ${av_troops} troops for ${cost} each`
		else if (av_troops > 0)
			str = `Recruit up to ${av_troops} troops for ${cost} each`
		else if (av_trains > 0)
			str = `Recruit supply trains for ${cost} each`
		else
			str = "Nothing to recruit"

		let paid = game.count + sum_card_values(game.recruit.pool)

		if (paid > 1)
			str += " \u2014 " + paid + " points."
		else if (paid === 1)
			str += " \u2014 1 point."
		else
			str += "."

		prompt(str)

		view.draw = game.recruit.pool

		if (possible && paid / cost < av_troops + av_trains) {
			for (let c of game.hand[game.power])
				gen_action_card(c)
		}

		if (paid >= cost) {
			if (av_troops > 0) {
				for (let p of all_power_generals[game.power]) {
					if (game.troops[p] > 0 && game.troops[p] < 8) {
						let s = game.pos[p]
						gen_action_piece(s)
					}
					else if (game.pos[p] === ELIMINATED && has_re_entry_space(p))
						gen_action_piece(p)
				}
			}
			if (av_trains > 0) {
				for (let p of all_power_trains[game.power]) {
					if (game.pos[p] === ELIMINATED && has_re_entry_space(p))
						gen_action_piece(p)
				}
			}
		}

		if (paid < cost || !possible)
			view.actions.end_recruit = 1
	},
	card(c) {
		push_undo()
		set_delete(game.hand[game.power], c)
		set_add(game.recruit.pool, c)
	},
	piece(p) {
		push_undo()

		spend_recruit_cost()

		if (game.pos[p] === ELIMINATED) {
			game.selected = p
			game.state = "re_enter"
		} else {
			game.recruit.troops += 1
			add_one_troop(p)
		}
	},
	end_recruit() {
		push_undo()
		end_recruit()
	},
}

function end_recruit() {
	if (game.recruit) {
		if (game.recruit.used.length > 0) {
			log_br()
			if (game.recruit.troops > 0)
				log("Recruited " + game.recruit.troops + " troops with " + game.recruit.used.map(format_card).join(", ") + ".")
			else
				log("Recruited with " + game.recruit.used.map(format_card).join(", ") + ".")
			map_for_each(game.recruit.pieces, (p,s) => {
				log("Re-entered P" + p + " at S" + s + ".")
			})
			if (game.recruit.troops)
				log(">" + game.recruit.troops + " troops")
		}

		// put back into hand unused cards
		for (let c of game.recruit.pool)
			set_add(game.hand[game.power], c)

		delete game.recruit
	}

	// MARIA: NOT goto_combat()
	// goto_combat()
}

states.re_enter = {
	inactive: "recruit",
	prompt() {
		prompt("Re-enter " + format_selected() + ".")
		view.selected = game.selected

		let p = game.selected
		let can_re_enter_at = is_general(p) ? can_re_enter_general : can_re_enter_supply_train

		if (is_map_space(game.recruit.re_enter)) {
			if (can_re_enter_at(game.recruit.re_enter))
				gen_action_space(game.recruit.re_enter)
		} else {
			for (let s of all_power_depots[game.power])
				if (can_re_enter_at(s))
					gen_action_space(s)
		}
	},
	space(s) {
		let p = game.selected
		game.pos[p] = s
		map_set(game.recruit.pieces, p, s)
		if (is_general(p)) {
			game.recruit.troops += 1
			game.troops[p] = 1
		}
		game.selected = -1
		game.state = "recruit"
	},
}

/* COMBAT (CHOOSE TARGETS) */

function goto_combat() {
	let from = []
	let to = []

	for (let p of all_controlled_generals(game.power))
		if (is_map_space(game.pos[p]))
			set_add(from, game.pos[p])

	for (let p of all_enemy_generals(game.power))
		if (is_map_space(game.pos[p]))
			set_add(to, game.pos[p])

	game.combat = []
	for (let a of from) {
		for (let b of to) {
			if (set_has(data.cities.adjacent[a], b)) {
				game.combat.push(a)
				game.combat.push(b)
			}
		}
	}

	if (game.combat.length > 0)
		game.state = "combat"
	else
		goto_retroactive_conquest()
}

function next_combat() {
	clear_undo()
	set_active_to_current_action_step()
	game.count = 0
	delete game.attacker
	delete game.defender
	if (game.combat.length > 0)
		game.state = "combat"
	else
		// TODO: a bit abrupt, but saves time if
		// game.state = "combat_done"
		goto_retroactive_conquest()
}


states.combat = {
	inactive: "attack",
	prompt() {
		prompt("Resolve your attacks.")
		for (let i = 0; i < game.combat.length; i += 2)
			gen_action_supreme_commander(game.combat[i])
	},
	piece(p) {
		push_undo()
		game.attacker = game.pos[p]
		game.state = "combat_target"
	},
}

// TODO: unused for now
states.combat_done = {
	inactive: "attack",
	prompt() {
		prompt("Combat done.")
		view.actions.end_combat = 1
	},
	end_combat() {
		goto_retroactive_conquest()
	},
}

states.combat_target = {
	inactive: "attack",
	prompt() {
		prompt("Choose enemy stack to attack.")
		for (let i = 0; i < game.combat.length; i += 2)
			if (game.combat[i] === game.attacker)
				gen_action_supreme_commander(game.combat[i+1])
	},
	piece(p) {
		clear_undo()

		game.defender = game.pos[p]

		for (let i = 0; i < game.combat.length; i += 2) {
			if (game.combat[i] === game.attacker && game.combat[i+1] === game.defender) {
				array_remove_pair(game.combat, i)
				break
			}
		}

		goto_resolve_combat()
	},
}

function goto_resolve_combat() {
	let a_troops = 0
	let d_troops = 0

	for (let p of all_generals) {
		if (game.pos[p] === game.attacker)
			a_troops += game.troops[p]
		if (game.pos[p] === game.defender)
			d_troops += game.troops[p]
	}

	log_br()

	game.count = a_troops - d_troops

	let a = get_supreme_commander(game.attacker)
	let d = get_supreme_commander(game.defender)
	log("!")
	log(`>P${a} at S${game.attacker}`)
	log(`>P${d} at S${game.defender}`)
	log(`>Troops ${a_troops} - ${d_troops} = ${game.count}`)

	if (game.count <= 0) {
		set_active_attacker()
		game.state = "combat_attack"
	} else {
		set_active_defender()
		game.state = "combat_defend"
	}
}

function end_resolve_combat() {
	if (game.count === 0) {
		log(">Tied")
		next_combat()
	} else if (game.count > 0) {
		game.selected = select_stack(game.defender)
		goto_retreat()
	} else {
		game.selected = select_stack(game.attacker)
		goto_retreat()
	}
}

/* COMBAT (CARD PLAY) */

function format_combat_stack(s) {
	let p = get_supreme_commander(s)
	return suit_name[get_space_suit(s)] + " " + piece_name[p]
}

function signed_number(v) {
	if (v > 0)
		return "+" + v
	if (v < 0)
		return "\u2212" + (-v)
	return "0"
}

function format_combat(value) {
	let a = format_combat_stack(game.attacker)
	let d = format_combat_stack(game.defender)
	let s = signed_number(value)
	let p = POWER_NAME[game.power]
	return `${a} vs ${d}. ${p} is at ${s}.`
}

function inactive_attack() {
	return "Waiting for " + format_combat(game.count)
}

function inactive_defend() {
	return "Waiting for " + format_combat(-game.count)
}

function prompt_combat(value, extra = null) {
	let text = format_combat(value)
	if (extra)
		text += " " + extra
	view.prompt = text
}

function set_active_attacker() {
	set_active_to_power(get_stack_power(game.attacker))
}

function set_active_defender() {
	set_active_to_power(get_stack_power(game.defender))
}

function resume_combat_attack() {
	if (game.count === 0)
		game.state = "combat_attack_swap"
	else if (game.count > 0)
		game.state = "combat_attack_swap"
	else
		game.state = "combat_attack"
}

function resume_combat_defend() {
	if (game.count === 0)
		game.state = "combat_defend_swap"
	else if (game.count < 0)
		game.state = "combat_defend_swap"
	else
		game.state = "combat_defend"
}

function gen_play_card(suit) {
	let score = Math.abs(game.count)
	let has_suit = false

	for (let c of game.hand[game.power]) {
		let c_suit = to_suit(c)
		if (c_suit === suit) {
			has_suit = true
			gen_action_card(c)
		} else if (c_suit === RESERVE) {
			gen_action_card(c)
		}
	}

	// cannot pass if at 0 (and can play)
	if (score === 0 && has_suit)
		view.actions.pass = 0
	else
		view.actions.pass = 1
}

function gen_play_reserve() {
	view.draw = [ game.reserve ]
	view.actions.value = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
}

function play_card(c, sign) {
	let prefix = (sign < 0 ? ">>" : ">") + POWER_NAME[game.power]
	if (sign < 0)
		game.count -= to_value(c)
	else
		game.count += to_value(c)
	let score = signed_number(sign * game.count)
	log(`${prefix} ${format_card(c)} = ${score}`)
}

function play_reserve(v, sign) {
	let c = game.reserve
	delete game.reserve
	let prefix = (sign < 0 ? ">>" : ">") + POWER_NAME[game.power]
	if (sign < 0)
		game.count -= v
	else
		game.count += v
	let score = signed_number(sign * game.count)
	log(`${prefix} ${format_reserve(c, v)} = ${score}`)
}

function play_combat_card(c, sign, resume, next_state) {
	push_undo()
	array_remove_item(game.hand[game.power], c)
	if (is_reserve(c)) {
		game.state = next_state
		game.reserve = c
	} else {
		play_card(c, sign)
		resume()
	}
}

states.combat_attack = {
	inactive: inactive_attack,
	prompt() {
		prompt_combat(game.count)
		gen_play_card(get_space_suit(game.attacker))
	},
	card(c) {
		play_combat_card(c, +1, resume_combat_attack, "combat_attack_reserve")
	},
	pass() {
		clear_undo()
		end_resolve_combat()
	},
}

states.combat_defend = {
	inactive: inactive_defend,
	prompt() {
		prompt_combat(-game.count)
		gen_play_card(get_space_suit(game.defender))
	},
	card(c) {
		play_combat_card(c, -1, resume_combat_defend, "combat_defend_reserve")
	},
	pass() {
		clear_undo()
		end_resolve_combat()
	},
}

states.combat_attack_reserve = {
	inactive: inactive_attack,
	prompt() {
		prompt_combat(game.count, "Choose value.")
		view.draw = [ game.reserve ]
		gen_play_reserve()
	},
	value(v) {
		play_reserve(v, +1)
		resume_combat_attack()
	},
}

states.combat_defend_reserve = {
	inactive: inactive_defend,
	prompt() {
		prompt_combat(-game.count, "Choose value.")
		view.draw = [ game.reserve ]
		gen_play_reserve()
	},
	value(v) {
		play_reserve(v, -1)
		resume_combat_defend()
	},
}

states.combat_attack_swap = {
	inactive: inactive_attack,
	prompt() {
		prompt_combat(game.count)
		view.actions.next = 1
	},
	next() {
		clear_undo()
		set_active_defender()
		game.state = "combat_defend"
	},
}

states.combat_defend_swap = {
	inactive: inactive_defend,
	prompt() {
		prompt_combat(-game.count)
		view.actions.next = 1
	},
	next() {
		clear_undo()
		set_active_attacker()
		game.state = "combat_attack"
	},
}

/* RETREAT */

function get_winner() {
	return game.count > 0 ? game.attacker : game.defender
}

function get_loser() {
	return game.count < 0 ? game.attacker : game.defender
}

function set_active_winner() {
	if (game.count > 0)
		set_active_attacker()
	else
		set_active_defender()
}

function set_active_loser() {
	if (game.count > 0)
		set_active_defender()
	else
		set_active_attacker()
}

function remove_stack_from_combat(s) {
	for (let i = game.combat.length - 2; i >= 0; i -= 2)
		if (game.combat[i] === s || game.combat[i + 1] === s)
			array_remove_pair(game.combat, i)
}

function goto_retreat() {
	let hits = Math.abs(game.count)
	let lost = [ 0, 0, 0, 0, 0, 0 ] // per power!

	let loser = get_loser()
	let loser_power = get_stack_power(loser)
	let winner_power = get_stack_power(get_winner())

	// no more fighting for the loser
	remove_stack_from_combat(loser)

	// apply hits
	for (let i = game.selected.length - 1; i >= 0 && hits > 0; --i) {
		let p = game.selected[i]
		while (game.troops[p] > 1 && hits > 0) {
			lost[piece_power[p]]++
			--game.troops[p]
			--hits
		}
	}

	for (let i = game.selected.length - 1; i >= 0 && hits > 0; --i) {
		let p = game.selected[i]
		while (game.troops[p] > 0 && hits > 0) {
			lost[piece_power[p]]++
			--game.troops[p]
			--hits
		}
	}

	for (let pow of all_powers)
		if (lost[pow] > 0)
			log(POWER_NAME[pow] + " lost " + (lost[pow]) + " troops.")

	resume_retreat()
}

function resume_retreat() {
	// eliminate generals with no more hits
	for (let p of game.selected) {
		if (game.troops[p] === 0) {
			game.state = "retreat_eliminate_hits"
			return
		}
	}

	// retreat remaining generals
	if (game.selected.length > 0) {
		game.retreat = search_retreat(get_loser(), get_winner(), Math.abs(game.count))
		if (game.retreat.length > 0) {
			// victor chooses retreat destination
			set_active_winner()
			game.state = "retreat"
		} else {
			// eliminate if there are no retreat possibilities
			delete game.retreat
			game.state = "retreat_eliminate_trapped"
		}
		return
	}

	// no retreat if generals wiped out
	next_combat()
}

states.retreat_eliminate_hits = {
	inactive: "retreat",
	prompt() {
		prompt("Eliminate generals without troops.")
		// remove eliminated generals
		for (let p of game.selected)
			if (game.troops[p] === 0)
				gen_action_piece(p)
	},
	piece(p) {
		eliminate_general(p, false)
		set_delete(game.selected, p)
		resume_retreat()
	},
}

states.retreat_eliminate_trapped = {
	inactive: "retreat",
	prompt() {
		prompt("Eliminate " + format_selected() + " without a retreat path.")
		for (let p of game.selected)
			gen_action_piece(p)
	},
	piece(_) {
		log("Trapped.")
		for (let p of game.selected)
			eliminate_general(p, false)
		next_combat()
	},
}

// search distances from winner within retreat range
function search_retreat_distance(from, range) {
	let seen = [ from, 0 ]
	let queue = [ from << 4 ]
	while (queue.length > 0) {
		let item = queue.shift()
		let here = item >> 4
		let dist = (item & 15) + 1
		for (let next of data.cities.adjacent[here]) {
			if (map_has(seen, next))
				continue
			if (dist <= range) {
				map_set(seen, next, dist)
				queue.push((next << 4) | dist)
			}
		}
	}
	return seen
}

// search all possible retreat paths of given length
function search_retreat_possible_dfs(result, seen, here, range) {
	for (let next of data.cities.adjacent[here]) {
		if (seen.includes(next))
			continue
		if (has_any_piece(next))
			continue
		if (range === 1) {
			set_add(result, next)
		} else {
			seen.push(next)
			search_retreat_possible_dfs(result, seen, next, range - 1)
			seen.pop()
		}
	}
}

function search_retreat_possible(from, range) {
	let result = []
	search_retreat_possible_dfs(result, [from], from, range)
	return result
}

function search_retreat(loser, winner, range) {
	let distance = search_retreat_distance(winner, range + 1)
	let possible = search_retreat_possible(loser, range)

	let max = 0
	for (let s of possible) {
		let d = map_get(distance, s, -1)
		if (d > max)
			max = d
	}

	let result = []
	for (let s of possible)
		if (map_get(distance, s, -1) === max)
			result.push(s)
	return result
}

// TODO: remove hussars when retreating across them
states.retreat = {
	inactive: "retreat defeated general",
	prompt() {
		prompt("Retreat " + format_selected() + " " + Math.abs(game.count) + " cities.")
		view.selected = game.selected
		for (let s of game.retreat)
			gen_action_space(s)
	},
	space(to) {
		push_undo()
		log("Retreated to S" + to + ".")
		for (let p of game.selected)
			game.pos[p] = to
		delete game.retreat
		game.state = "retreat_done"
	},
}

states.retreat_done = {
	inactive: "retreat defeated general",
	prompt() {
		prompt("Retreat done.")
		view.actions.next = 1
	},
	next() {
		next_combat()
	},
}

/* RETRO-ACTIVE CONQUEST */

function log_conquest(conq, reconq) {
	if (conq.length > 0 || reconq.length > 0) {
		log_br()
		if (conq.length > 0) {
			log("Conquered")
			for (let s of conq)
				log(">S" + s)
		}
		if (reconq.length > 0) {
			log("Reconquered")
			for (let s of reconq)
				log(">S" + s)
		}
	}
}

function goto_retroactive_conquest() {
	delete game.combat

	let conq = []
	let reconq = []

	for (let s of game.retro) {
		if (is_conquest_space(game.power, s)) {
			if (!is_protected_from_conquest(s)) {
				set_add(game.conquest, s)
				conq.push(s)
			}
		}
		if (is_reconquest_space(game.power, s)) {
			if (!is_protected_from_reconquest(s)) {
				set_delete(game.conquest, s)
				reconq.push(s)
			}
		}
	}

	log_conquest(conq, reconq)

	set_clear(game.retro)

	end_action_stage()
}

/* SUPPLY */

function search_supply_bfs(from, range) {
	let seen = [ from ]
	let queue = [ from << 4 ]
	while (queue.length > 0) {
		let item = queue.shift()
		let here = item >> 4
		let dist = (item & 15) + 1
		for (let next of data.cities.adjacent[here]) {
			if (set_has(seen, next))
				continue
			if (has_enemy_piece(next))
				continue
			set_add(seen, next)
			if (dist < range)
				queue.push((next << 4) | dist)
		}
	}
	return seen
}

function search_supply(range) {
	for (let p of all_power_trains[game.power]) {
		let here = game.pos[p]
		if (here >= ELIMINATED)
			continue
		if (!game.supply)
			game.supply = search_supply_bfs(here, range)
		else
			set_add_all(game.supply, search_supply_bfs(here, range))
	}
}

function is_out_of_supply(p) {
	return (game.oos & (1 << p)) !== 0
}

function set_out_of_supply(p) {
	return game.oos |= (1 << p)
}

function set_in_supply(p) {
	return game.oos &= ~(1 << p)
}

function has_supply_line(p) {
	let s = game.pos[p]
	if (set_has(all_home_or_depot_cities[game.power], s))
		return true
	if (game.supply && set_has(game.supply, s))
		return true
	return false
}

function should_supply_restore() {
	for (let p of all_power_generals[game.power]) {
		if (game.pos[p] >= ELIMINATED)
			continue
		if (is_out_of_supply(p) && has_supply_line(p))
			return true
	}
	return false
}

function should_supply_eliminate() {
	for (let p of all_power_generals[game.power]) {
		if (game.pos[p] >= ELIMINATED)
			continue
		if (is_out_of_supply(p) && !has_supply_line(p))
			return true
	}
	return false
}

function should_supply_flip() {
	for (let p of all_power_generals[game.power]) {
		if (game.pos[p] >= ELIMINATED)
			continue
		if (!is_out_of_supply(p) && !has_supply_line(p))
			return true
	}
	return false
}

function goto_supply() {
	set_clear(game.moved)
	search_supply(6)

	if (should_supply_restore())
		goto_supply_restore()
	else if (should_supply_eliminate())
		goto_supply_eliminate()
	else if (should_supply_flip())
		goto_supply_flip()
	else
		end_supply()
}

function goto_supply_restore() {
	log_br()
	log("In supply")
	resume_supply_restore()
}

function goto_supply_eliminate() {
	log_br()
	log("Out of supply")
	resume_supply_eliminate()
}

function goto_supply_flip() {
	log_br()
	log("Out of supply")
	resume_supply_flip()
}

function resume_supply_restore() {
	if (should_supply_restore())
		game.state = "supply_restore"
	else if (should_supply_eliminate())
		goto_supply_eliminate()
	else if (should_supply_flip())
		goto_supply_flip()
	else
		game.state = "supply_done"
}

function resume_supply_eliminate() {
	if (should_supply_eliminate())
		game.state = "supply_eliminate"
	else if (should_supply_flip())
		goto_supply_flip()
	else
		game.state = "supply_done"
}

function resume_supply_flip() {
	if (should_supply_flip())
		game.state = "supply_flip"
	else
		game.state = "supply_done"
}

states.supply_restore = {
	inactive: "supply",
	prompt() {
		prompt("Restore supply to generals with a supply line.")
		for (let p of all_power_generals[game.power]) {
			if (game.pos[p] >= ELIMINATED)
				continue
			if (is_out_of_supply(p) && has_supply_line(p))
				gen_action_piece(game.pos[p])
		}
	},
	piece(x) {
		let s = game.pos[x]
		for (let p of all_power_generals[game.power]) {
			if (game.pos[p] === s) {
				set_add(game.moved, p)
				set_in_supply(p)
				log(">P" + p + " at S" + s)
			}
		}
		resume_supply_restore()
	},
}

states.supply_eliminate = {
	inactive: "supply",
	prompt() {
		prompt("Eliminate out of supply generals with no supply line.")
		for (let p of all_power_generals[game.power]) {
			if (game.pos[p] >= ELIMINATED)
				continue
			if (is_out_of_supply(p) && !has_supply_line(p))
				gen_action_piece(game.pos[p])
		}
	},
	piece(x) {
		let s = game.pos[x]
		for (let p of all_power_generals[game.power])
			if (game.pos[p] === s)
				eliminate_general(p, true)

		resume_supply_eliminate()
	},
}

states.supply_flip = {
	inactive: "supply",
	prompt() {
		prompt("Flip generals with no supply line.")
		for (let p of all_power_generals[game.power]) {
			if (game.pos[p] >= ELIMINATED)
				continue
			if (!is_out_of_supply(p) && !has_supply_line(p))
				gen_action_piece(game.pos[p])
		}
	},
	piece(x) {
		let s = game.pos[x]
		for (let p of all_power_generals[game.power]) {
			if (game.pos[p] === s) {
				log(">P" + p + " at S" + s)
				set_out_of_supply(p)
			}
		}
		resume_supply_flip()
	},
}

states.supply_done = {
	inactive: "supply",
	prompt() {
		prompt("Supply done.")
		view.actions.end_supply = 1
	},
	end_supply() {
		end_supply()
	},
}

function end_supply() {
	delete game.supply

	end_action_stage()
}

/* SETUP */

const POWER_FROM_SETUP_STEP = [
	P_FRANCE,
	P_BAVARIA,
	P_PRUSSIA,
	P_SAXONY,
	P_PRAGMATIC,
	P_AUSTRIA,
]

function set_active_setup_power() {
	game.power = POWER_FROM_SETUP_STEP[game.step]
	game.active = current_player()
}

const setup_initial_tcs = [ 2, 5, 9, 3, 3, 5 ]

const setup_total_troops = [ 26, 5, 16+6, 5, 14, 28 ]

const setup_min_troops = [
	1, 1, 1, 1, 1,
	5,
	1, 1, 4, 6,
	5,
	1, 1, 1,
	1, 1, 6, 2, 1, 4,
]

const setup_max_troops = [
	8, 8, 8, 8, 8,
	5,
	8, 8, 8, 6,
	8,
	8, 8, 8,
	8, 8, 8, 8, 8, 8,
]

const setup_piece_position = [
	// - GENERALS -

	// F
	find_city("Beaune"),
	find_city("Schwandorf"),
	find_city("Ergoldsbach"),
	find_city("Créspy-en-V."),
	find_city("Sarreguemines"),

	// B
	find_city("Ergoldsbach"),

	// P
	find_city("Steinau"),
	find_city("Steinau"),
	find_city("Sprottau"),
	find_city("East Prussia"),

	// S
	find_city("Radeberg"),

	// PA
	find_city("Delfzijl"),
	find_city("Delfzijl"),
	find_city("Dordrecht"),

	// A
	find_city("Austerlitz"),
	find_city("Steinamanger"),
	find_city("Stuhlweißenburg"),
	find_city("Stuhlweißenburg"),
	find_city("Trübau"),
	find_city("Malmedy"),

	// - TRAINS -

	// F
	find_city("Bar-le-Duc"),
	find_city("Regensburg"),

	// B
	find_city("Falkenstein"),

	// P
	find_city("Grünberg"),
	find_city("Silesia Victory"),

	// S
	find_city("Meißen"),

	// PA
	find_city("Tilburg"),

	// A
	find_city("Hlinsko"),
	find_city("Bruck"),
	find_city("Geel"),

	// Hussars
	ELIMINATED,
	ELIMINATED
]

function make_political_deck() {
	let deck41 = [ 1, 2, 3, 4, 5, 6 ]
	let deck42 = [ 7, 8, 9, 10, 11, 12, 25 ]
	let deck43 = [ 13, 14, 15, 16, 17, 18 ]
	let deck44 = [ 19, 20, 21, 22, 23, 24 ]
	shuffle_bigint(deck41)
	shuffle_bigint(deck42)
	shuffle_bigint(deck43)
	shuffle_bigint(deck44)
	return [ deck44, deck43, deck42, deck41 ].flat()
}

function make_tactics_deck(n) {
	let deck = []
	for (let suit = 0; suit <= 3; ++suit)
		for (let value = 2; value <= 10; ++value)
			deck.push((n << 7) | (suit << 4) | value)
	deck.push((n << 7) | (RESERVE << 4) | 2)
	deck.push((n << 7) | (RESERVE << 4) | 3)
	return deck
}

function make_tactics_discard(n) {
	return make_tactics_deck(n).filter(c => {
		if (game.draw && set_has(game.draw, c))
			return false
		for (let pow of all_powers)
			if (set_has(game.hand[pow], c))
				return false
		return true
	})
}

exports.setup = function (seed, _scenario, _options) {
	game = {
		seed: seed,
		undo: [],
		log: [],

		state: "setup",
		active: R_LOUIS_XV,
		power: P_FRANCE,

		turn: 0,
		step: 0,
		pol_deck: null,
		deck: null,
		hand: [ [], [], [], [], [], [] ],

		pos: setup_piece_position.slice(),
		oos: 0,
		troops: setup_min_troops.map(n => 0),
		conquest: [],

		moved: [],
		retro: [],

		selected: -1,
		count: 0,
	}

	game.pol_deck = make_political_deck()
	game.deck = make_tactics_deck(0)

	shuffle_bigint(game.deck)

	// Deal initial cards
	for (let pow of all_powers)
		for (let i = 0; i < setup_initial_tcs[pow]; ++i)
			set_add(game.hand[pow], game.deck.pop())

	log("# 1741")

	return game
}

states.setup = {
	inactive: "setup troops",
	prompt() {
		let n_troops = setup_total_troops[game.power] - count_used_troops()
		if (n_troops === 0) {
			prompt("Setup done.")
			view.actions.end_setup = 1
		} else {
			let n_stacks = 0
			for (let p of all_power_generals[game.power]) {
				if (game.pos[p] !== ELIMINATED && !set_has(game.moved, p)) {
					gen_action_piece(p)
					n_stacks ++
				}
			}
			if (n_stacks > 1)
				prompt("Add " + n_troops + " troops to " + n_stacks + " generals.")
			else if (n_troops > 1)
				prompt("Add " + n_troops + " troops to last general.")
			else
				prompt("Add 1 troop to last general.")
		}
	},
	piece(p) {
		push_undo()
		set_add(game.moved, p)
		game.selected = p
		game.state = "setup_general"
	},
	end_setup() {
		clear_undo()
		end_setup()
	},
}

function count_unsetup_min() {
	let n = 0
	for (let p of all_power_generals[game.power])
		if (game.troops[p] === 0)
			n += setup_min_troops[p]
	return n
}

function count_unsetup_max() {
	let n = 0
	for (let p of all_power_generals[game.power])
		if (game.troops[p] === 0)
			n += setup_max_troops[p]
	return n
}

states.setup_general = {
	inactive: "setup troops",
	prompt() {
		prompt("Add troops to " + format_selected() + ".")
		view.selected = game.selected

		let who = game.selected

		let n_self_min = setup_min_troops[who]
		let n_self_max = setup_max_troops[who]
		let n_other_min = count_unsetup_min() - n_self_min
		let n_other_max = count_unsetup_max() - n_self_max
		let n_troops = setup_total_troops[game.power] - count_used_troops()

		// leave at least 1 for each remaining general
		let take_max = Math.min(n_self_max, n_troops - n_other_min)

		// leave no more than 8 for each remaining general
		let take_min = Math.max(n_self_min, n_troops - n_other_max)

		view.actions.value = []
		for (let i = take_min; i <= take_max; ++i)
			view.actions.value.push(i)
	},
	value(v) {
		game.troops[game.selected] += v
		game.selected = -1
		game.state = "setup"
	},
}

function end_setup() {
	if (++game.step === 6) {
		goto_start_turn()
	} else {
		set_active_setup_power()
	}
}

/* VIEW */

function mask_troops(player) {
	let view_troops = []
	for (let pow of all_powers) {
		if (player_from_power(pow) === player) {
			for (let p of all_power_generals[pow])
				view_troops.push(game.troops[p])
		} else {
			for (let p of all_power_generals[pow]) {
				let s = game.pos[p]
				if (game.attacker === s || game.defender === s)
					view_troops.push(game.troops[p])
				else
					view_troops.push(0)
			}
		}
	}
	return view_troops
}

function mask_hand(player) {
	let view_hand = []
	for (let pow of all_powers) {
		if (player_from_power(pow) === player)
			view_hand[pow] = game.hand[pow]
		else
			view_hand[pow] = game.hand[pow].map(c => c & ~127)
			//view_hand[pow] = game.hand[pow].length
			//view_hand[pow] = Math.ceil(game.hand[pow].length / 3) * 3
			//view_hand[pow] = Math.ceil(game.hand[pow].length / 5)
	}
	return view_hand
}

function total_troops_list() {
	let list = []
	for (let pow of all_powers) {
		let n = 0
		for (let p of all_power_generals[pow])
			n += game.troops[p]
		list[pow] = n
	}
	return list
}

exports.view = function (state, player) {
	game = state
	view = {
		prompt: null,
		actions: null,
		log: game.log,

		turn: game.turn,
		pos: game.pos,
		oos: game.oos,
		conquest: game.conquest,
		troops: mask_troops(player),
		hand: mask_hand(player),
		pt: total_troops_list(),
		discard: total_discard_list(),

		power: game.power,
		retro: game.retro,
	}

	if (game.attacker !== undefined && game.defender !== undefined) {
		view.attacker = game.attacker
		view.defender = game.defender
	}

	if (game.state === "game_over") {
		view.prompt = game.victory
		view.troops = game.troops
		view.hand = game.hand
	} else if (game.active !== player) {
		let inactive = states[game.state].inactive || game.state
		if (typeof inactive === "function")
			view.prompt = inactive()
		else
			view.prompt = `Waiting for ${POWER_NAME[game.power]} to ${inactive}.`
	} else {
		view.actions = {}
		if (states[game.state])
			states[game.state].prompt()
		else
			view.prompt = "Unknown state: " + game.state
		if (view.actions.undo === undefined) {
			if (game.undo && game.undo.length > 0)
				view.actions.undo = 1
			else
				view.actions.undo = 0
		}
	}

	return view
}

/* COMMON FRAMEWORK */

function goto_game_over(result, victory) {
	log("# The End")
	game.active = "None"
	game.state = "game_over"
	game.result = result
	game.victory = victory
	log(game.victory)
	return true
}

function prompt(str) {
	view.prompt = POWER_NAME[game.power] + ": " + str
}

exports.action = function (state, _player, action, arg) {
	game = state
	let S = states[game.state]
	if (S && 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 game
}

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

function gen_action_piece(p) {
	gen_action("piece", p)
}

function gen_action_space(s) {
	gen_action("space", s)
}

function gen_action_supreme_commander(s) {
	let p = get_supreme_commander(s)
	if (p >= 0)
		gen_action_piece(p)
}

function gen_action_space_or_piece(s) {
	let p = get_top_piece(s)
	if (p >= 0)
		gen_action_piece(p)
	else
		gen_action_space(s)
}

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

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

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

/* COMMON LIBRARY */

function clear_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_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_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_remove_item(array, item) {
	let n = array.length
	for (let i = 0; i < n; ++i)
		if (array[i] === item)
			return array_remove(array, i)
}

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_add_all(set, other) {
	for (let item of other)
		set_add(set, item)
}

function set_union(one, two) {
	let set = []
	for (let item of one)
		set_add(set, item)
	for (let item of two)
		set_add(set, item)
	return set
}

function set_intersect(one, two) {
	let set = []
	for (let item of one)
		if (set_has(two, item))
			set_add(set, item)
	return set
}

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

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_for_each(map, f) {
	for (let i = 0; i < map.length; i += 2)
		f(map[i], map[i+1])
}