"use strict"

// RULE QUESTIONS: subsidy contract - if major fortress enemy controlled? - ignore contract or waste card?

/* TODO

show who controls which power in player list

set-aside victory marker areas

austria/pragmatic move order on flanders (start with pragmatic)
	only stack if agree (undo/move to previous space)

winter scoring

when are subsidies given?
	example france subsidy to prussia
		at france's stage?
		at prussia's stage?

-- advanced --

silesia home country for prussia

tc subsidies
	minor when major fortress enemy occupied
subsidy contracts

arenberg supply exception
arenberg re-entry exception

victory boxes
politics
imperial election

political changes
	prussia annexes silesia
	france reduces military objectives
	saxony's defection

neutrality

*/

// TODO: austria/pragmatic action stage - 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: TC subsidies
// TODO: subsidy markers?

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

exports.roles = [
	R_MARIA_THERESA,
	R_FREDERICK,
	R_LOUIS_XV
]

exports.scenarios = [ "Advanced" ]

const data = require("./data")

var game
var view
var states = {}

/* DATA (SHARED) */

const deck_name = [ "red", "green", "blue", "yellow" ]
const suit_name = [ "\u2660", "\u2663", "\u2665", "\u2666", "R" ]
const suit_class = [ "spades", "clubs", "hearts", "diamonds", "reserve" ]
const suit_letter = [ "S", "C", "H", "D", "R" ]

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

const power_name = [ "France", "Prussia", "Pragmatic Army", "Austria", "Bavaria", "Saxony" ]
const power_class = [ "france", "prussia", "pragmatic", "austria", "bavaria", "saxony" ]

const F_EMPEROR_FRANCE = 1
const F_EMPEROR_AUSTRIA = 2
const F_ITALY_FRANCE = 4
const F_ITALY_AUSTRIA = 8
const F_SILESIA_ANNEXED = 16
const F_IMPERIAL_ELECTION = 32 // imperial election card revealed!

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 all_powers = [ 0, 1, 2, 3, 4, 5 ]
const all_major_powers = [ 0, 1, 2, 3 ]

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_PRUSSIA, P_PRUSSIA, P_PRUSSIA, P_PRUSSIA,
	P_PRAGMATIC, P_PRAGMATIC, P_PRAGMATIC,
	P_AUSTRIA, P_AUSTRIA, P_AUSTRIA, P_AUSTRIA, P_AUSTRIA, P_AUSTRIA,
	P_BAVARIA,
	P_SAXONY,
	P_FRANCE, P_FRANCE,
	P_PRUSSIA, P_PRUSSIA,
	P_PRAGMATIC,
	P_AUSTRIA, P_AUSTRIA, P_AUSTRIA,
	P_BAVARIA,
	P_SAXONY,
	P_AUSTRIA, P_AUSTRIA
]

const piece_rank = [
	1, 2, 3, 4, 5,
	1, 2, 3, 4,
	1, 2, 3,
	1, 2, 3, 4, 5, 6,
	1,
	1,
]

const piece_abbr = [
	"F1", "F2", "F3", "F4", "F5",
	"P1", "P2", "P3", "P4",
	"PA1", "PA2", "PA3",
	"A1", "A2", "A3", "A4", "A5", "A6",
	"B1",
	"S1",
]

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

const piece_log_name = [
	"Moritz",
	"Belle-Isle",
	"Broglie",
	"Maillebois",
	"Noailles",
	"Friedrich",
	"Schwerin",
	"Leopold",
	"Dessauer",
	"George II",
	"Cumberland",
	"Earl of Stair",
	"Karl",
	"Traun",
	"Khevenhüller",
	"Batthyány",
	"Neipperg",
	"Arenberg",
	"Törring",
	"Rutowski",
	"French ST", "French ST",
	"Prussian ST", "Prussian ST",
	"Pragmatic Army ST",
	"Austrian ST", "Austrian ST", "Austrian ST",
	"Bavarian ST",
	"Saxon ST",
	"Hussars", "Hussars",
]

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
}

/* 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 is_piece_on_map(p) {
	return is_map_space(game.pos[p])
}

function is_piece_eliminated(p) {
	return game.pos[p] === ELIMINATED
}

function is_piece_on_map_or_eliminated(p) {
	let s = game.pos[p]
	return is_map_space(s) || s === ELIMINATED
}

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
}

const TRIER = find_city("Trier")
const MAINZ = find_city("Mainz")
const KOLN = find_city("Köln")
const MANNHEIM = find_city("Mannheim")

const LIEGNITZ = find_city("Liegnitz")
const GLOGAU = find_city("Glogau")
const BRESLAU = find_city("Breslau")
const BRIEG = find_city("Brieg")
const GLATZ = find_city("Glatz")
const NEISSE = find_city("Neisse")
const COSEL = find_city("Cosel")

const MUNCHEN = find_city("München")
const DRESDEN = find_city("Dresden")

const ENGLAND = find_city("England")

const all_pieces = [ ...all_power_generals.flat(), ...all_power_trains.flat() ]
const all_trains = [ ...all_power_trains.flat() ]
const all_generals = [ ...all_power_generals.flat() ]
const all_generals_by_rank = all_generals.slice().sort((a,b)=>piece_rank[a]-piece_rank[b])

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 ]
const all_powers_pragmatic_austria = [ P_PRAGMATIC, P_AUSTRIA ]

const all_powers_none = []
const all_powers_france_bavaria = [ P_FRANCE, P_BAVARIA ]
const all_powers_bavaria = [ P_BAVARIA ]
const all_powers_pragmatic = [ P_PRAGMATIC ]
const all_powers_austria = [ P_AUSTRIA ]
const all_powers_prussia_saxony = [ P_PRUSSIA, P_SAXONY ]
const all_powers_saxony = [ P_SAXONY ]
const all_powers_bavaria_saxony = [ P_BAVARIA, P_SAXONY ]

function coop_major_power(pow) {
	if (pow === P_BAVARIA)
		return P_FRANCE
	if (pow === P_SAXONY)
		return P_PRUSSIA
	return pow
}

function coop_minor_power(pow) {
	if (pow === P_FRANCE)
		return P_BAVARIA
	if (pow === P_PRUSSIA)
		return P_SAXONY
	return pow
}

function all_friendly_minor_powers(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
	case P_PRUSSIA:
	case P_SAXONY:
		return all_powers_bavaria_saxony
	case P_PRAGMATIC:
	case P_AUSTRIA:
		return all_powers_none
	}
}

function all_coop_powers(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
		return all_powers_france_bavaria
	case P_PRUSSIA:
	case P_SAXONY:
		return all_powers_prussia_saxony
	case P_PRAGMATIC:
	case P_AUSTRIA:
		return all_powers_pragmatic_austria
	}
}

function all_controlled_powers(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
		return all_powers_france_bavaria
	case P_PRUSSIA:
	case P_SAXONY:
		return all_powers_prussia_saxony
	case P_PRAGMATIC:
		return all_powers_pragmatic
	case P_AUSTRIA:
		return all_powers_austria
	}
}

function is_hostile_to_austria() {
	switch (game.power) {
	case P_FRANCE:
	case P_BAVARIA:
	case P_PRUSSIA:
	case P_SAXONY:
		return true
	case P_PRAGMATIC:
	case P_AUSTRIA:
		return false
	}
}

function all_enemy_powers(pow) {
	switch (pow) {
	case P_FRANCE:
	case P_BAVARIA:
	case P_PRUSSIA:
	case P_SAXONY:
		return all_powers_pragmatic_austria
	case P_PRAGMATIC:
	case P_AUSTRIA:
		return all_powers_france_bavaria_prussia_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 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_path() {
	if (game.move_path.length > 1)
		log("@" + game.selected + ";" + game.move_path.join(","))
}

/* OBJECTIVES */

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

const all_home_country_fortresses = []

all_home_country_fortresses[P_FRANCE] = set_intersect(all_fortresses, data.country.France)
all_home_country_fortresses[P_PRUSSIA] = set_intersect(all_fortresses, data.country.Prussia)
all_home_country_fortresses[P_PRAGMATIC] = set_intersect(all_fortresses, data.country.Netherlands)
all_home_country_fortresses[P_AUSTRIA] = set_intersect(all_fortresses, data.country.Austria)
all_home_country_fortresses[P_BAVARIA] = set_intersect(all_fortresses, data.country.Bavaria)
all_home_country_fortresses[P_SAXONY] = set_intersect(all_fortresses, data.country.Saxony)

const all_home_country_major_fortresses = []
all_home_country_major_fortresses[P_FRANCE] = set_intersect(data.type.major_fortress, data.country.France)
all_home_country_major_fortresses[P_PRUSSIA] = set_intersect(data.type.major_fortress, data.country.Prussia)
all_home_country_major_fortresses[P_PRAGMATIC] = set_intersect(data.type.major_fortress, data.country.Netherlands)
all_home_country_major_fortresses[P_AUSTRIA] = set_intersect(data.type.major_fortress, data.country.Austria)
all_home_country_major_fortresses[P_BAVARIA] = set_intersect(data.type.major_fortress, data.country.Bavaria)
all_home_country_major_fortresses[P_SAXONY] = set_intersect(data.type.major_fortress, data.country.Saxony)

const all_silesian_fortresses = set_intersect(all_fortresses, data.country.Silesia)

const protect_range = []
for (let s of all_fortresses)
	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_home_country(s) {
	// TODO: Silesia
	switch (game.power) {
	case P_FRANCE: return set_has(data.country.France, s)
	case P_PRUSSIA: return set_has(data.country.Prussia, s)
	case P_PRAGMATIC: return set_has(data.country.Netherlands, s)
	case P_AUSTRIA: return set_has(data.country.Austria, s)
	case P_BAVARIA: return set_has(data.country.Bavaria, s)
	case P_SAXONY: return set_has(data.country.Saxony, s)
	}
}

function is_enemy_home_country(s) {
	for (let other of all_enemy_powers(game.power))
		if (set_has(all_home_country_fortresses[other], s))
			return true
	return false
}

function is_friendly_minor_home_country(s) {
	for (let other of all_friendly_minor_powers(game.power))
		if (set_has(all_home_country_fortresses[other], s))
			return true
	return false
}

function get_home_power(s) {
	for (let pow of all_powers)
		if (set_has(all_home_country_fortresses[pow], s))
			return pow
	return -1
}

function is_enemy_controlled_fortress(s) {
	for (let other of all_enemy_powers(game.power))
		if (is_power_controlled_fortress(other, s))
			return true
	return false
}

function is_friendly_controlled_fortress(s) {
	return !is_enemy_controlled_fortress(s)
}

function is_power_controlled_fortress(pow, s) {
	let owner = map_get(game.elector, s, -1)
	if (owner < 0)
		owner = map_get(game.victory, s, -1)
	if (owner < 0)
		return set_has(all_home_country_fortresses[pow], s)
	return owner === pow
}

function set_control_of_fortress(s, pow) {
	if (s === TRIER || s === MAINZ || s === KOLN || s === MANNHEIM) {
		if (pow === P_AUSTRIA || pow === P_PRAGMATIC)
			map_set(game.elector, s, P_AUSTRIA)
		else
			map_set(game.elector, s, P_FRANCE)
		return
	}

	if (is_enemy_home_country(s) || is_friendly_minor_home_country(s) || set_has(all_silesian_fortresses, s))
		map_set(game.victory, s, pow)
	else
		map_delete(game.victory, s)
}


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

function is_protected_from_conquest(s) {
	let owner = map_get(game.elector, s, -1)
	if (owner < 0)
		owner = map_get(game.victory, s, -1)
	if (owner < 0)
		owner = get_home_power(s)
	for (let p of all_coop_generals(owner))
		if (is_space_protected_by_piece(s, p))
			return true
	return false
}

/* STATE */

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

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

	// TODO: subsidies
	if (game.turn <= 3) {
		if (game.power === P_FRANCE)
			--n
		if (game.power === P_BAVARIA)
			++n
	}

	return n
}

function player_from_power(pow) {
	switch (pow) {
	case P_FRANCE:
		return R_LOUIS_XV
	case P_PRUSSIA:
		return R_FREDERICK
	case P_PRAGMATIC:
		return R_FREDERICK
	case P_AUSTRIA:
		return R_MARIA_THERESA
	case P_SAXONY:
		return R_FREDERICK
	case P_BAVARIA:
		return R_LOUIS_XV
	}
}

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_trains)
		if (game.pos[p] === s)
			return p
	return get_supreme_commander(s)
}

function get_supreme_commander(s) {
	for (let p of all_generals)
		if ((game.supreme & (1<<p)) && game.pos[p] === s)
			return p
	for (let p of all_generals_by_rank)
		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_used_troops() {
	let current = 0
	for (let p of all_power_generals[game.power])
		current += game.troops[p]
	return current
}

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

function has_any_hussar(to) {
	for (let p of all_hussars)
		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_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 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.supreme & (1<<p)) && game.pos[p] === s)
			list.push(p)
	for (let p of all_generals)
		if (!(game.supreme & (1<<p)) && game.pos[p] === s)
			list.push(p)
	return list
}

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

/* SEQUENCE OF PLAY */

const TURN_NAME = [
	"Setup",
	"Turn 1",
	"Turn 2",
	"Turn 3",
	"Winter 1741",
	"Turn 4",
	"Turn 5",
	"Turn 6",
	"Winter 1742",
	"Turn 7",
	"Turn 8",
	"Turn 9",
	"Winter 1743",
	"Turn 10",
	"Turn 11",
	"Turn 12",
	"Winter 1744",
]

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

const title_from_action_stage = [
	"=" + P_FRANCE + "France and Bavaria",
	"=" + P_PRUSSIA + "Prussia and Saxony",
	"=" + P_PRAGMATIC + "Pragmatic Army",
	"=" + P_AUSTRIA + "Austria",
]

function set_active_to_current_action_stage() {
	set_active_to_power(POWER_FROM_ACTION_STAGE[game.stage])
}

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

const title_from_winter_stage = [
	"=" + P_FRANCE,
	"=" + P_BAVARIA,
	"=" + P_PRUSSIA,
	"=" + P_SAXONY,
	"=" + P_PRAGMATIC,
	"=" + P_AUSTRIA,
]

function set_active_to_current_winter_stage() {
	set_active_to_power(POWER_FROM_WINTER_STAGE[game.stage])
}

function goto_end_turn() {
	goto_start_turn()
}

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

	log("# " + TURN_NAME[game.turn])

	game.selected = -1

	if (game.turn % 4 === 0) {
		goto_winter_turn()
	} else {
		goto_politics()
	}
}

function goto_action_stage() {
	set_active_to_current_action_stage()

	clear_undo()

	log(title_from_action_stage[game.stage])

	// TODO: minor powers controlled at the same time

	goto_tactical_cards()
}

function end_action_stage() {
	clear_undo()

	if (check_instant_victory())
		return

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

/* AUSTRIA PLACES ITS HUSSARS */

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

function end_place_hussars() {
	set_clear(game.moved)
	log("=" + P_AUSTRIA + " Hussars")
	for (let p of all_hussars)
		log("Hussar at S" + game.pos[p] + ".")
	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)
		if (!has_any_hussar(ELIMINATED))
			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) && !has_any_hussar(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 in saved political display
	for (let pow of all_major_powers) {
		for (let c of game.saved[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: pause to decide subsidy (france/bavaria)

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

	if (game.power === P_BAVARIA && is_enemy_controlled_fortress(MUNCHEN)) {
		log("S" + MUNCHEN + " is enemy controlled.")
		game.draw = []
	} else if (game.power === P_SAXONY && is_enemy_controlled_fortress(DRESDEN)) {
		log("S" + DRESDEN + " is enemy controlled.")
		game.draw = []
	} else {
		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

	goto_supply()
}

/* PAYMENT */

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_card_value(pool, used, amount) {
	if (game.count > 0) {
		if (amount < game.count) {
			game.count -= amount
			amount = 0
		} else {
			amount -= game.count
			game.count = 0
		}
	}
	while (amount > 0) {
		let c = find_largest_card(pool)
		let v = to_value(c)
		set_delete(pool, c)
		set_add(used, c)
		if (v > amount) {
			game.count = v - amount
			amount = 0
		} else {
			amount -= v
		}
	}
}

/* SUPPLY */

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 search_supply_path_avoid_hussars(who) {
	let from = game.pos[who]
	let trains = all_power_trains[piece_power[who]]

	if (is_home_country(from))
		return 1

	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]) {
			for (let p of trains)
				if (game.pos[p] === next)
					return dist
			if (has_any_hussar(next))
				continue
			if (set_has(seen, next))
				continue
			if (has_enemy_piece(next))
				continue
			set_add(seen, next)
			if (dist < 6)
				queue.push((next << 4) | dist)
		}
	}

	return 0
}

function search_supply_path(who) {
	let from = game.pos[who]
	let trains = all_power_trains[piece_power[who]]

	if (is_home_country(from))
		return 1

	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]) {
			for (let p of trains)
				if (game.pos[p] === next)
					return dist
			if (set_has(seen, next))
				continue
			if (has_enemy_piece(next))
				continue
			set_add(seen, next)
			if (dist < 6)
				queue.push((next << 4) | dist)
		}
	}

	return 0
}

function goto_supply() {
	game.supply = {
		hussars: [],
		restore: [],
		suffer: [],
	}

	for (let p of all_controlled_generals(game.power)) {
		if (!is_piece_on_map(p))
			continue

		if (is_hostile_to_austria()) {
			let d = search_supply_path_avoid_hussars(p)
			if (d > 0) {
				if (is_out_of_supply(p))
					set_add(game.supply.restore, p)
			} else {
				d = search_supply_path(p)
				if (d > 0)
					map_set(game.supply.hussars, p, d)
				else
					set_add(game.supply.suffer, p)
			}
		} else {
			let d = search_supply_path(p)
			if (d > 0) {
				if (is_out_of_supply(p))
					set_add(game.supply.restore, p)
			} else {
				set_add(game.supply.suffer, p)
			}
		}
	}

	if (game.supply.hussars.length + game.supply.restore.length + game.supply.suffer.length === 0)
		end_supply()
	else
		resume_supply()
}

function resume_supply() {
	set_active_to_current_action_stage()
	if (game.supply.hussars.length > 0)
		goto_supply_hussars()
	else if (game.supply.restore.length > 0)
		goto_supply_restore()
	else if (game.supply.suffer.length > 0)
		goto_supply_suffer()
	else
		end_supply()
		// TODO: pause
		// game.state = "supply_done"
}

function goto_supply_hussars() {
	log_br()
	log("Hussars")
	set_active_to_power(piece_power[game.supply.hussars[0]])
	game.state = "supply_hussars"
	game.supply.pool = []
	game.supply.used = []
	game.count = 0
}

function goto_supply_restore() {
	log_br()
	log("In supply")
	game.state = "supply_restore"
}

function goto_supply_suffer() {
	log_br()
	log("Out of supply")
	game.state = "supply_suffer"
}

states.supply_hussars = {
	inactive: "supply",
	prompt() {
		let paid = game.count + sum_card_values(game.supply.pool)

		view.selected = []

		let can_pay = false
		let debt = 0
		map_for_each(game.supply.hussars, (p, d) => {
			if (piece_power[p] === game.power) {
				if (d <= paid) {
					can_pay = true
					gen_action_piece(p)
				} else {
					view.selected.push(p)
				}
				debt += d
			}
		})

		let str
		if (debt > 0)
			str = `Pay ${debt} for tracing supply through hussars`
		else
			str = "Hussar payment done"

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

		if (paid < debt)
			for (let c of game.hand[game.power])
				gen_action_card(c)

		prompt(str)

		view.draw = game.supply.pool

		if (debt === 0 || (!can_pay && game.hand[game.power].length === 0))
			view.actions.next = 1
	},
	piece(p) {
		push_undo()

		let cost = map_get(game.supply.hussars, p)

		spend_card_value(game.supply.pool, game.supply.used, cost)

		map_delete(game.supply.hussars, p)
		if (is_out_of_supply(p))
			set_add(game.supply.restore, p)

		log(">P" + p + " paid " + cost)
	},
	card(c) {
		push_undo()
		set_delete(game.hand[game.power], c)
		set_add(game.supply.pool, c)
	},
	next() {
		push_undo()

		if (game.supply.used.length > 0)
			log(">with " + game.supply.used.map(format_card).join(", "))
		else
			log(">paid nothing")

		// move generals not paid for to out of supply list
		map_for_each(game.supply.hussars, (p, _) => {
			if (piece_power[p] === game.power)
				set_add(game.supply.suffer, p)
		})
		for (let p of game.supply.suffer)
			map_delete(game.supply.hussars, p)

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

		resume_supply()
	},
}

states.supply_restore = {
	inactive: "supply",
	prompt() {
		prompt("Restore supply to generals with a supply path.")
		for (let p of game.supply.restore)
			gen_action_piece(p)
	},
	piece(p) {
		log(`>P${p} at S${game.pos[p]}`)
		set_delete(game.supply.restore, p)
		set_in_supply(p)
		if (game.supply.restore.length === 0)
			resume_supply()
	},
}

states.supply_suffer = {
	inactive: "supply",
	prompt() {
		prompt("Flip and remove troops from generals without a supply path.")
		for (let p of game.supply.suffer)
			gen_action_piece(p)
	},
	piece(p) {
		log(`>P${p} at S${game.pos[p]}`)
		set_delete(game.supply.suffer, p)
		if (is_out_of_supply(p)) {
			//log(`>P${p} at S${game.pos[p]} -2 troops`)
			game.troops[p] -= 2
		} else {
			//log(`>P${p} at S${game.pos[p]} -1 troop`)
			set_out_of_supply(p)
			game.troops[p] -= 1
		}
		if (game.troops[p] <= 0) {
			eliminate_general(p, true)
			lose_vp(coop_major_power(game.power), 1)
		}
		if (game.supply.suffer.length === 0)
			resume_supply()
	},
}

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

function end_supply() {
	delete game.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 goto_movement() {
	set_active_to_current_action_stage()

	game.state = "movement"
	set_clear(game.moved)

	log_br()

	game.move_re_entered = 0
	game.move_conq = []
}

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_piece_on_map(p)) {
				if (can_general_move_anywhere(p)) {
					gen_action_piece(p)
					done_generals = false
				}
			}
		}

		for (let p of all_controlled_trains(game.power)) {
			if ((game.move_re_entered & (1 << piece_power[p])) === 0)
				if (can_train_re_enter(p))
					view.actions.re_enter = 1
			if (!set_has(game.moved, p)) {
				if (is_piece_on_map(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
	},
	re_enter() {
		push_undo()
		goto_re_enter_train()
	},
	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.supreme &= ~(1 << p)
			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)
		delete game.move_conq
		delete game.move_re_entered

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

	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)) {
		if (is_enemy_controlled_fortress(from)) {
			if (is_protected_from_conquest(from)) {
				map_set(game.retro, from, coop_major_power(game.power))
			} else {
				set_add(game.move_conq, from)
				set_control_of_fortress(from, coop_major_power(game.power))
			}
		}
	}

	// 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: stop moving
	for (let p of all_coop_generals(pow)) {
		if (game.pos[p] === to && game.selected !== 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() {
		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

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

		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(3))
		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 < 3 + 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 < 3)
			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() {
		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 === 3 + 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)
		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)
		game.state = "move_general"
	},
}

function end_move_piece() {
	let here = game.pos[game.selected]

	set_add(game.moved, game.selected)

	log_move_path()

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

	delete game.move_path

	// uniting stacks: flag all as moved
	let supreme = false
	if (is_general(game.selected)) {
		for (let p of all_coop_generals(game.power)) {
			if (game.pos[p] === here && p !== game.selected) {
				if (piece_rank[p] === piece_rank[game.selected])
					supreme = true
				set_add(game.moved, p)
			}
		}
	}

	if (supreme) {
		game.state = "move_supreme"
	} else {
		game.selected = -1
		game.state = "movement"
		set_active_to_current_action_stage()
	}
}

states.move_supreme = {
	inactive: "move",
	prompt() {
		prompt("Choose supreme commander for mixed stack.")
		let here = game.pos[game.selected]
		for (let p of all_coop_generals(game.power)) {
			if (game.pos[p] === here) {
				gen_action("supreme", p)
				gen_action_piece(p)
			}
		}
	},
	supreme(p) {
		let here = game.pos[game.selected]
		for (let p of all_coop_generals(game.power))
			if (game.pos[p] === here)
				game.supreme &= ~(1<<p)
		game.supreme |= (1<<p)
		game.selected = -1
		game.state = "movement"
	},
	piece(p) {
		this.supreme(p)
	},
}

/* RE-ENTER SUPPLY TRAIN */

function goto_re_enter_train() {
	if (all_controlled_powers(game.power).length > 1)
		game.state = "re_enter_train_power"
	else
		game.state = "re_enter_train"
	game.recruit = {
		pool: [],
		used: [],
		pieces: [],
	}
	game.count = 0
}

function can_train_re_enter(p) {
	return (
		(is_piece_on_map_or_eliminated(p)) &&
		!set_has(game.moved, p) &&
		has_re_entry_space_for_supply_train(piece_power[p])
	)
}

function has_re_entry_space_for_supply_train(pow) {
	if (coop_minor_power(pow) !== pow)
		return can_re_enter_train_at_power_fortress(pow) || can_re_enter_train_at_power_fortress(coop_minor_power(pow))
	else
		return can_re_enter_train_at_power_fortress(pow)
}

function gen_re_enter_train_at_power_fortress(pow) {
	for (let s of all_home_country_major_fortresses[pow])
		if (is_friendly_controlled_fortress(s) && !has_any_piece(s))
			gen_action_space(s)
}

function can_re_enter_train_at_power_fortress(pow) {
	for (let s of all_home_country_major_fortresses[pow])
		if (is_friendly_controlled_fortress(s) && !has_any_piece(s))
			return true
	return false
}

states.re_enter_train_power = {
	inactive: "move",
	prompt() {
		prompt("Re-enter supply train from which power?")
		view.actions.power = []
		for (let pow of all_controlled_powers(game.power)) {
			if (game.move_re_entered & (1 << pow))
				continue
			for (let p of all_power_trains[pow]) {
				if (can_train_re_enter(p)) {
					view.actions.power.push(pow)
					break
				}
			}
		}
	},
	power(pow) {
		game.move_re_entered |= (1 << pow)
		set_active_to_power(pow)
		game.state = "re_enter_train"
	},
}

states.re_enter_train = {
	inactive: "move",
	prompt() {
		let str

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

		let av_trains = 0
		for (let p of all_power_trains[game.power]) {
			if (can_train_re_enter(p)) {
				if (paid >= 4)
					gen_action_piece(p)
				av_trains += 1
			}
		}

		if (paid / 4 < av_trains) {
			for (let c of game.hand[game.power])
				gen_action_card(c)
		}

		if (game.recruit.used.length > 0)
			view.actions.next = 1

		if (av_trains > 0) {
			str = "Re-enter supply trains for 4 each"
			if (paid > 1)
				str += " \u2014 " + paid + " points."
			else if (paid === 1)
				str += " \u2014 1 point."
			else
				str += "."
		} else {
			str = "Re-enter supply trains done."
		}

		prompt(str)

		view.draw = game.recruit.pool
	},
	piece(p) {
		push_undo()
		spend_card_value(game.recruit.pool, game.recruit.used, 4)
		set_add(game.moved, p)
		map_set(game.recruit.pieces, p, game.pos[p])
		game.state = "re_enter_train_where"
		game.selected = p
	},
	card(c) {
		push_undo()
		set_delete(game.hand[game.power], c)
		set_add(game.recruit.pool, c)
	},
	next() {
		push_undo()
		end_re_enter_train()
	},
}

states.re_enter_train_where = {
	inactive: "move",
	prompt() {
		prompt("Re-enter supply train at a major fortress.")

		view.selected = game.selected
		view.draw = game.recruit.pool

		gen_re_enter_train_at_power_fortress(game.power)
		if (coop_minor_power(game.power) !== game.power)
			gen_re_enter_train_at_power_fortress(coop_minor_power(game.power))
	},
	space(to) {
		game.pos[game.selected] = to
		game.selected = -1
		game.state = "re_enter_train"

		// remove hussars
		for (let p of all_hussars) {
			if (game.pos[p] === to) {
				log("P" + p + " removed.")
				game.pos[p] = ELIMINATED
			}
		}
	},
}

function end_re_enter_train() {
	if (game.recruit.used.length > 0) {
		log_br()
		log(power_name[game.power] + " spent " + game.recruit.used.map(format_card).join(", ") + ".")
		map_for_each(game.recruit.pieces, (p, s) => {
			if (s !== ELIMINATED)
				log("Re-entered P" + p + " from S" + s + " at S" + game.pos[p] + ".")
			else
				log("Re-entered P" + p + " at S" + game.pos[p] + ".")
		})
		log_br()
	}

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

	delete game.recruit

	set_active_to_current_action_stage()
	game.state = "movement"
}

/* WINTER RECRUITMENT */

function goto_winter_turn() {

	// TODO: winter scoring

	goto_winter_stage()
}

function goto_winter_stage() {
	set_active_to_current_winter_stage()

	clear_undo()

	log(title_from_winter_stage[game.stage])

	goto_recruit()
}

function end_winter_stage() {
	clear_undo()

	if (++game.stage === 6)
		goto_end_turn()
	else
		goto_winter_stage()
}

function goto_recruit() {
	game.count = 0

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

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

	game.state = "recruit"
}

function has_re_entry_space_for_general() {
	for (let s of all_home_country_major_fortresses[game.power])
		if (can_re_enter_general_at_city(s))
			return true
	return false
}

function can_re_enter_general_at_city(to) {
	if (is_enemy_controlled_fortress(to))
		return false
	if (has_friendly_supply_train(to))
		return false
	if (has_non_cooperative_general(to))
		return false
	if (count_generals(to) >= 2)
		return false
	return true
}

function can_recruit_anything() {
	for (let p of all_power_generals[game.power]) {
		// can re-enter generals
		if (is_piece_eliminated(p) && has_re_entry_space_for_general())
			return true
		// can recruit troops?
		if (is_piece_on_map(p) && game.troops[p] < 8)
			return true
	}
	return false
}

states.recruit = {
	inactive: "recruit",
	prompt() {
		let av_general = 0
		let av_troops = 0
		for (let p of all_power_generals[game.power]) {
			if (is_piece_on_map(p))
				av_troops += 8 - game.troops[p]
			else if (is_piece_eliminated(p) && has_re_entry_space_for_general()) {
				av_general += 1
				av_troops += 8
			}
		}

		let str
		if (av_general > 0 && av_troops > 0)
			str = `Re-enter generals and recruit up to ${av_troops} troops for 4 each`
		else if (av_troops > 0)
			str = `Recruit up to ${av_troops} troops for 4 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 (av_troops > 0) {
			if (paid / 4 < av_troops) {
				for (let c of game.hand[game.power])
					gen_action_card(c)
			}

			if (paid >= 4) {
				for (let p of all_power_generals[game.power]) {
					if (game.troops[p] > 0 && game.troops[p] < 8)
						gen_action_piece(p)
					else if (is_piece_eliminated(p) && has_re_entry_space_for_general())
						gen_action_piece(p)
				}
			}
		}

		if (paid < 4 || av_troops === 0)
			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_card_value(game.recruit.pool, game.recruit.used, 4)

		if (is_piece_eliminated(p)) {
			game.selected = p
			game.state = "re_enter_general_where"
		} else {
			game.recruit.troops += 1
			game.troops[p] += 1
		}
	},
	end_recruit() {
		push_undo()
		end_recruit()
	},
}

states.re_enter_general_where = {
	inactive: "recruit",
	prompt() {
		prompt("Re-enter " + format_selected() + ".")
		view.selected = game.selected
		for (let s of all_home_country_major_fortresses[game.power])
			if (can_re_enter_general_at_city(s))
				gen_action_space(s)
	},
	space(s) {
		let p = game.selected
		game.pos[p] = s
		set_add(game.recruit.pieces, p)
		if (is_general(p)) {
			game.recruit.troops += 1
			game.troops[p] = 1
		}
		game.selected = -1
		game.state = "recruit"

		// remove hussars
		for (let p of all_hussars) {
			log("P" + p + " removed.")
			game.pos[p] = ELIMINATED
		}

		// remove enemy supply trains
		for (let p of all_enemy_trains(game.power)) {
			log("P" + p + " eliminated.")
			game.pos[p] = ELIMINATED
		}
	},
}

function end_recruit() {
	if (game.recruit) {
		if (game.recruit.used.length > 0) {
			log_br()
			log("Recruited " + game.recruit.troops + " troops with " + game.recruit.used.map(format_card).join(", ") + ".")
			for (let p of game.recruit.pieces)
				log("Re-entered P" + p + " at S" + game.pos[p] + ".")
		} else {
			log("Recruited nothing.")
		}

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

		delete game.recruit
	} else {
		log("Recruited nothing.")
	}

	end_winter_stage()
}

/* COMBAT (CHOOSE TARGETS) */

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

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

	for (let p of all_enemy_generals(game.power))
		if (is_piece_on_map(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_stage()
	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 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()

	// 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.")

	// track VP gained and lost
	if (game.count > 0) {
		game.winner_power = coop_major_power(get_stack_power(game.attacker))
		game.loser_power = coop_major_power(get_stack_power(game.defender))
	} else {
		game.winner_power = coop_major_power(get_stack_power(game.defender))
		game.loser_power = coop_major_power(get_stack_power(game.attacker))
	}
	game.lost_generals = 0
	game.lost_troops = 0
	for (let pow of all_powers)
		game.lost_troops += lost[pow]

	resume_retreat()
}

function resume_retreat() {
	// eliminate generals with no more hits
	for (let p of game.selected) {
		if (game.troops[p] === 0) {
			game.lost_generals += 1
			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
	finish_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) {
			game.lost_generals += 1
			game.lost_troops += game.troops[p]
			eliminate_general(p, false)
		}
		finish_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
}

function is_illegal_cross_map_retreat(from, to) {
	if ((is_flanders_space(from) && is_bohemia_space(to)) || (is_flanders_space(to) && is_bohemia_space(from))) {
		for (let p of game.selected) {
			let pow = piece_power[p]
			if (pow !== P_FRANCE && pow !== P_AUSTRIA)
				return true
		}
	}
	return false
}

// 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 (is_illegal_cross_map_retreat(here, 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() {
		finish_combat()
	},
}

function gain_vp(pow, n) {
	let old_vp = game.vp[pow]
	game.vp[pow] = Math.min(2, game.vp[pow] + n)
	if (game.vp[pow] > old_vp)
		log(`${power_name[pow]} +${game.vp[pow] - old_vp} VP.`)
}

function lose_vp(pow, n) {
	let old_vp = game.vp[pow]
	game.vp[pow] = Math.max(0, game.vp[pow] - n)
	if (game.vp[pow] < old_vp)
		log(`${power_name[pow]} -${old_vp - game.vp[pow]} VP.`)
}

function finish_combat() {
	let n = 0
	if (game.lost_troops >= 6)
		n = 2
	else if (game.lost_troops >= 3)
		n = 1
	else if (game.lost_generals > 0)
		n = 1

	if (n > 0) {
		gain_vp(game.winner_power, n)
		lose_vp(game.loser_power, n)
	}

	delete game.lost_generals
	delete game.lost_troops

	next_combat()
}

/* RETRO-ACTIVE CONQUEST */

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

function goto_retroactive_conquest() {
	delete game.combat

	let conq = []

	map_for_each(game.retro, function (s, pow) {
		if (is_enemy_controlled_fortress(s)) {
			if (!is_protected_from_conquest(s)) {
				set_control_of_fortress(s, pow)
				conq.push(s)
			}
		}
	})

	log_conquest(conq)

	map_clear(game.retro)

	end_action_stage()
}

/* VICTORY */

const power_victory_target = [ 11, 13, 8, 8 ]

function elector_majority() {
	let elector_france = 0
	let elector_pragmatic = 0
	for (let i = 0; i < 8; i += 2) {
		if (view.elector[i+1] === P_FRANCE)
			elector_france ++
		else
			elector_pragmatic ++
	}
	if (elector_france >= 3)
		return P_FRANCE
	if (elector_pragmatic >= 3)
		return P_PRAGMATIC
	return -1
}

function count_vp_markers(pow) {
	let n = game.vp[pow]
	if (pow === P_PRUSSIA) {
		if (game.flags & F_SILESIA_ANNEXED) ++n
	}
	if (pow === P_FRANCE) {
		if (game.flags & F_ITALY_FRANCE) ++n
		if (game.flags & F_EMPEROR_FRANCE) ++n
		if (elector_majority() === P_FRANCE) ++n
	}
	if (pow === P_AUSTRIA) {
		if (game.flags & F_ITALY_AUSTRIA) ++n
		if (game.flags & F_EMPEROR_AUSTRIA) ++n
	}
	if (pow === P_PRAGMATIC) {
		if (elector_majority() === P_PRAGMATIC) ++n
	}
	for (let i = 0; i < game.victory.length; i += 2)
		if (game.victory[i+1] === pow)
			++n
	return n
}

function check_instant_victory() {
	let margin = [
		count_vp_markers(P_FRANCE) - 11,
		count_vp_markers(P_PRUSSIA) - 13,
		count_vp_markers(P_PRAGMATIC) - 8,
		count_vp_markers(P_AUSTRIA) - 8,
	]

	let best = 0
	for (let pow = 1; pow < 4; ++pow)
		if (margin[pow] >= margin[best])
			best = pow

	if (margin[best] >= 0) {
		goto_game_over(player_from_power(best), power_name[best] + " won!")
		return true
	}

	return false
}

/* POLITICS */

const POWER_FROM_POLITICAL_STAGE = [
	P_PRUSSIA,
	P_FRANCE,
	P_PRAGMATIC,
	P_AUSTRIA,
]

function set_active_political_power() {
	set_active_to_power(POWER_FROM_POLITICAL_STAGE[game.stage])
}

function goto_politics() {
	game.political = []
	game.display = [ 0, 0, 0, 0 ]
	game.stage = 0

	while (game.political.length < 2) {
		let pc = game.pol_deck.pop()
		if (pc === IMPERIAL_ELECTION)
			game.flags |= F_IMPERIAL_ELECTION
		else
			game.political.push(pc)
	}

	if (game.winner_power >= 0) {
		set_active_to_power(game.winner_power)
		game.state = "determine_trump_suit"
	} else {
		for (;;) {
			draw_tc(1)
			log("Trump " + format_card(game.draw[0]) + ".")
			if (!is_reserve(game.draw[0])) {
				game.trump = to_suit(game.draw[0])
				break
			}
			delete game.draw
		}
		goto_place_tc_on_display()
	}
}

states.determine_trump_suit = {
	inactive: "determine the political trump suit",
	prompt() {
		prompt("Determine the political trump suit.")
		view.actions.suit = [ 0, 1, 2, 3 ]
	},
	suit(s) {
		game.trump = s
		goto_place_tc_on_display()
	}
}

function goto_place_tc_on_display() {
	set_active_political_power()
	game.state = "place_tc_on_display"
}

states.place_tc_on_display = {
	inactive: "place TC on political display",
	prompt() {
		prompt(`Place TC on political display (${suit_name[game.trump]} is trump).`)
		for (let c of game.hand[game.power])
			gen_action_card(c)
		view.actions.pass = 1
	},
	card(c) {
		push_undo()
		log(power_name[game.power] + " placed a TC.")
		set_delete(game.hand[game.power], c)
		game.display[game.power] = c
		game.state = "place_tc_on_display_done"
	},
	pass() {
		log(power_name[game.power] + " passed.")
		end_place_tc_on_display()
	},
}

states.place_tc_on_display_done = {
	inactive: "place TC on political display",
	prompt() {
		prompt(`Place TC on political display (${suit_name[game.trump]} is trump) done.`)
		view.actions.next = 1
	},
	next() {
		end_place_tc_on_display()
	},
}

function end_place_tc_on_display() {
	if (++game.stage === 4)
		goto_determine_order_of_influence()
	else
		goto_place_tc_on_display()
}

function goto_determine_order_of_influence() {
	// Turn cards face-up and return bluff cards
	for (let pow of all_major_powers) {
		let c = game.display[pow]
		if (c > 0) {
			if (to_suit(c) === game.trump) {
				log(power_name[pow] + " played " + format_card(c) + ".")
				set_add(game.saved[pow], c)
			} else {
				log(power_name[pow] + " bluffed " + format_card(c) + ".")
				set_add(game.hand[pow], c)
			}
		}
	}
	delete game.display

	game.stage = 4
	goto_select_political_cards()
}

function goto_select_political_cards() {
	if (--game.stage < 0)
		end_politics()
	set_active_to_power(most_influence())
	game.state = "select_political_card"
}

states.select_political_card = {
	inactive: "select a political card",
	prompt() {
		prompt(`Select a political card or save your TC.`)
		for (let pc of game.political)
			gen_action_political(pc)
		view.actions.pass = 1
	},
	political(pc) {
		push_undo()
		log(power_name[game.power] + " chose C" + pc + ".")
		throw "TODO"
	},
	pass() {
		log(power_name[game.power] + " saved its TC.")
		goto_select_political_cards()
	},
}

function end_politics() {
	delete game.political
	if (check_instant_victory())
		return
	goto_place_hussars()
}

/* SETUP */

const POWER_FROM_SETUP_STAGE = [
	P_FRANCE,
	P_PRUSSIA,
	P_PRAGMATIC,
	P_AUSTRIA,
]

function set_active_setup_power() {
	set_active_to_power(POWER_FROM_SETUP_STAGE[game.stage])
}

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

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

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

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

const setup_troops = [
	0, 0, 0, 0, 0,
	0, 0, 0, 6,
	0, 0, 0,
	0, 0, 0, 0, 0, 0,
	5,
	5,
]

const setup_piece_position = [
	// - GENERALS -

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

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

	// 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"),

	// B
	find_city("Ergoldsbach"),

	// S
	find_city("Radeberg"),

	// - TRAINS -

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

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

	// PA
	find_city("Tilburg"),

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

	// B
	find_city("Falkenstein"),

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

	// 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
		for (let pow of all_major_powers)
			if (set_has(game.saved[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,
		stage: 0,

		vp: [ 0, 0, 0, 0 ], // battle victory points
		saxony: 2, // political track
		russia: 6, // political track
		italy: 5, // political track
		flags: 0, // emperor vp, italy vp, silesia annexed, etc

		// for tracking VP gains/losses and political trump suit
		winner_power: -1,
		loser_power: -1,
		trump: SPADES,

		pol_deck: null,
		deck: null,
		hand: [ [], [], [], [], [], [] ],
		saved: [ [], [], [], [] ],
		display: [ [], [], [], [] ],

		pos: setup_piece_position.slice(),
		oos: 0,
		supreme: 0,
		troops: setup_troops.slice(),
		victory: [],
		elector: [],

		moved: [],
		retro: [],

		selected: -1,
		count: 0,
	}

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

	shuffle_bigint(game.deck)

	map_set(game.elector, TRIER, P_AUSTRIA)
	map_set(game.elector, MAINZ, P_AUSTRIA)
	map_set(game.elector, KOLN, P_FRANCE)
	map_set(game.elector, MANNHEIM, P_FRANCE)

	map_set(game.victory, LIEGNITZ, P_PRUSSIA)
	map_set(game.victory, GLOGAU, P_PRUSSIA)
	map_set(game.victory, BRESLAU, P_AUSTRIA)
	map_set(game.victory, BRIEG, P_AUSTRIA)
	map_set(game.victory, GLATZ, P_AUSTRIA)
	map_set(game.victory, NEISSE, P_AUSTRIA)
	map_set(game.victory, COSEL, P_AUSTRIA)

	// 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.troops[p] === 0) {
					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()
		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.stage === 4) {
		goto_start_turn()
	} else {
		set_active_setup_power()
	}
}

/* VIEW */

function mask_pol_deck() {
	if (game.pol_deck.length > 0) {
		let top = game.pol_deck[game.pol_deck.length - 1]
		if (top === IMPERIAL_ELECTION)
			return 2
		return 1 + ((top-1) / 6 | 0)
	}
	return 0
}

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 mask_display(player) {
	let view_display = []
	for (let pow of all_major_powers) {
		if (game.display[pow] === 0)
			view_display[pow] = -1
		else if (player_from_power(pow) === player)
			view_display[pow] = game.display[pow]
		else
			view_display[pow] = game.display[pow] & ~127
	}
	return view_display
}

function mask_saved(player) {
	let view_saved = []
	for (let pow of all_major_powers) {
		if (player_from_power(pow) === player)
			view_saved[pow] = game.saved[pow]
		else
			view_saved[pow] = game.saved[pow].map(c => c & ~127)
	}
	return view_saved
}

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,
		vp: game.vp,
		saxony: game.saxony,
		russia: game.russia,
		italy: game.italy,
		flags: game.flags,
		victory: game.victory,
		elector: game.elector,

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

		pol_deck: mask_pol_deck(),
		saved: mask_saved(player),

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

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

	if (game.display)
		view.display = mask_display(player)

	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 gen_action_political(c) {
	gen_action("political", 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_clear(set) {
	set.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, 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 {
			array_remove_pair(map, m<<1)
			return
		}
	}
}

function map_for_each(map, f) {
	for (let i = 0; i < map.length; i += 2)
		f(map[i], map[i+1])
}