path: root/rules.js

"use strict"

// === CONSTANTS AND DATA ===

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

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

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

const NO_PLACE_GOVERNOR = -1
const OFF_MAP = -1
const AVAILABLE = -1
const UNAVAILABLE = -2

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

const ARMY = [
	[ 100, 101, 102, 103, 104, 105 ],
	[ 200, 201, 202, 203, 204, 205 ],
	[ 300, 301, 302, 303, 304, 305 ],
	[ 400, 401, 402, 403, 404, 405 ]
]

const REGION_NAME = [
	"Italia",
	"Aegyptus",
	"Africa",
	"Asia",
	"Britannia",
	"Galatia",
	"Gallia",
	"Hispania",
	"Macedonia",
	"Pannonia",
	"Syria",
	"Thracia",
	"Alamanni Homeland",
	"Franks Homeland",
	"Goths Homeland",
	"Nomads Homeland",
	"Sassanids Homeland",
]

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

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

const ALAMANNI_UNITS = [ 0, 9 ]
const FRANKS_UNITS = [ 10, 19 ]
const GOTHS_UNITS = [ 20, 29 ]
const NOMADS_UNITS = [ 30, 39 ]
const SASSANIDS_UNITS = [ 40, 49 ]

const LEGION_UNITS = [ 50, 82 ]

const BARBARIAN_UNITS = [
	ALAMANNI_UNITS,
	FRANKS_UNITS,
	GOTHS_UNITS,
	NOMADS_UNITS,
	SASSANIDS_UNITS,
]

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

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

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

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

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

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

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

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

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

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

// ===

var game
var view

const states = {}

exports.scenarios = [ "Standard" ]

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

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

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

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

function setup_barbarians(tribe) {
	for (let i = BARBARIAN_UNITS[tribe][0]; i <= BARBARIAN_UNITS[tribe][1]; ++i)
		game.barbarians[i] = BARBARIAN_HOMELAND[tribe]
}

function remove_barbarians(tribe) {
	for (let i = BARBARIAN_UNITS[tribe][0]; i <= BARBARIAN_UNITS[tribe][1]; ++i)
		game.barbarians[i] = OFF_MAP
}

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

	game = {
		seed: seed,
		log: [],
		undo: [],
		active: 0,
		current: 0,
		state: "setup_province",
		first: 0,
		events: null,
		active_events: [],
		support: new Array(12).fill(1),
		mobs: 0,
		militia: 0,
		quaestor: 0,
		legions: new Array(33).fill(OFF_MAP),
		is_legion_reduced: new Array(33).fill(0),
		barbarians: new Array(50).fill(OFF_MAP),
		is_barbarian_inactive: new Array(50).fill(1),
		barbarian_leaders: [ OFF_MAP, OFF_MAP, OFF_MAP ],
		rival_emperors: [ OFF_MAP, OFF_MAP, OFF_MAP ],
		amphitheater: 0,
		basilica: 0,
		limes: 0,
		dice: [ 0, 0, 0, 0 ], // first two are crisis table dice, second two are barbarian homeland dice
		market: null,
		players: [],
	}

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

	setup_barbarians(ALAMANNI)
	setup_barbarians(FRANKS)
	setup_barbarians(GOTHS)
	setup_barbarians(NOMADS)
	setup_barbarians(SASSANIDS)

	if (player_count === 1) {
		game.solo = 1
		player_count = 4
	}

	for (let pi = 0; pi < player_count; ++pi) {
		game.players[pi] = {
			legacy: 0,
			emperor_turns: 0,
			hand: [],
			draw: setup_player_deck(pi),
			discard: [],
			generals: [ AVAILABLE, UNAVAILABLE, UNAVAILABLE, UNAVAILABLE, UNAVAILABLE, UNAVAILABLE ],
			governors: [ AVAILABLE, UNAVAILABLE, UNAVAILABLE, UNAVAILABLE, UNAVAILABLE, UNAVAILABLE ],
			capital: 0,
			castra: 0,
		}
	}

	if (player_count === 4) {
		game.support[ITALIA] = 8
	}

	if (player_count === 3) {
		game.support[ITALIA] = 6
		game.support[HISPANIA] = NO_PLACE_GOVERNOR
		game.support[AFRICA] = NO_PLACE_GOVERNOR
		game.support[AEGYPTUS] = NO_PLACE_GOVERNOR
		remove_barbarians(NOMADS)
	}

	if (player_count === 2) {
		game.support[ITALIA] = 4
		game.support[BRITANNIA] = NO_PLACE_GOVERNOR
		game.support[HISPANIA] = NO_PLACE_GOVERNOR
		game.support[AFRICA] = NO_PLACE_GOVERNOR
		game.support[AEGYPTUS] = NO_PLACE_GOVERNOR
		game.support[SYRIA] = NO_PLACE_GOVERNOR
		game.support[GALATIA] = NO_PLACE_GOVERNOR
		remove_barbarians(NOMADS)
		remove_barbarians(SASSANIDS)
	}

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

	return save_game()
}

function load_game(state) {
	game = state
}

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

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

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

exports.view = function (state, player_name) {
	let player = PLAYER_INDEX[player_name]

	load_game(state)

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

		militia: game.militia,
		support: game.support,
		quaestor: game.quaestor,
		mobs: game.mobs,
		legions: game.legions,
		is_legion_reduced: game.is_legion_reduced,
		barbarians: game.barbarians,
		is_barbarian_inactive: game.is_barbarian_inactive,
		barbarian_leaders: game.barbarian_leaders,
		rival_emperors: game.rival_emperors,
		amphitheater: game.amphitheater,
		basilica: game.basilica,
		limes: game.limes,
		dice: game.dice,
		market: game.market,
		players: [],
	}

	for (let i = 0; i < game.players.length; ++i) {
		view.players[i] = {
			legacy: game.players[i].legacy,
			emperor_turns: game.players[i].emperor_turns,
			generals: game.players[i].generals,
			governors: game.players[i].governors,
			capital: game.players[i].capital,
			castra: game.players[i].castra,
		}
	}

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

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

	save_game()
	return view
}

// === MISC ===

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

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

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

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

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

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

// === STATES ===

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

function get_governor(r) {
	for (let p = 0; p < game.players.length; ++p) {
		for (let i = 0; i < 6; ++i)
			if (game.players[p].governors[i] === r)
				return p
	}
	return -1
}

function is_neutral_province(r) {
	return (game.support[r] !== NO_PLACE_GOVERNOR) && (get_governor(r) < 0)
}

function find_legion() {
	for (let i = 0; i < 33; ++i)
		if (game.legions[i] < 0)
			return i
	return -1
}

function current_hand() {
	return game.players[game.current].hand
}

function current_draw() {
	return game.players[game.current].draw
}

function add_militia(r) {
	game.militia |= (1 << r)
}

function remove_militia(r) {
	game.militia &= ~(1 << r)
}

function get_support(r) {
	return game.support[r]
}

function set_support(r, level) {
	game.support[r] = level
}

states.setup_province = {
	prompt() {
		view.prompt = "Select a starting Province."
		for (let r = 1; r < 12; ++r)
			if (is_neutral_province(r))
				gen_action("capital", r)
	},
	capital(r) {
		push_undo()
		let p = game.current
		game.players[p].generals[0] = r
		game.players[p].governors[0] = r
		game.players[p].capital = 1
		game.legions[find_legion()] = ARMY[p][0]
		add_militia(r)
		game.state = "setup_hand"
	},
}

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

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

function goto_upkeep() {
	goto_crisis()
}

// === CRISIS ===

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

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

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

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

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

function goto_ira_deorum() {
	logi("Ira Deorum")
	activate_one_barbarian(ALAMANNI)
	activate_one_barbarian(FRANKS)
	activate_one_barbarian(GOTHS)
	activate_one_barbarian(NOMADS)
	activate_one_barbarian(SASSANIDS)
	goto_take_actions()
}

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

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

function is_barbarian_active(i) {
	return !game.is_barbarian_inactive[i]
}

function is_barbarian_inactive(i) {
	return game.is_barbarian_inactive[i]
}

function set_barbarian_active(i) {
	game.is_barbarian_inactive[i] = 0
}

function set_barbarian_inactive(i) {
	game.is_barbarian_inactive[i] = 1
}

function find_active_barbarian(tribe) {
	let home = BARBARIAN_HOMELAND[tribe]
	for (let i = tribe * 10; i < tribe * 10 + 10; ++i)
		if (game.barbarians[i] === home && is_barbarian_active(i))
			return i
	return -1
}

function find_inactive_barbarian(tribe) {
	let home = BARBARIAN_HOMELAND[tribe]
	for (let i = tribe * 10; i < tribe * 10 + 10; ++i)
		if (game.barbarians[i] === home && is_barbarian_inactive(i))
			return i
	return -1
}

function count_active_barbarians_at_home(tribe) {
	let home = BARBARIAN_HOMELAND[tribe]
	let n = 0
	for (let i = tribe * 10; i < tribe * 10 + 10; ++i)
		if (game.barbarians[i] === home && is_barbarian_active(i))
			n += 1
	return n
}

function count_barbarians(tribe, region) {
	// TODO: count leaders
	let n = 0
	for (let i = tribe * 10; i < tribe * 10 + 10; ++i)
		if (game.barbarians[i] === region)
			n += 1
	return n
}

function activate_one_barbarian(tribe) {
	let i = find_inactive_barbarian(tribe)
	if (i >= 0)
		set_barbarian_active(i)
}

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

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

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

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

function invade_with_active_barbarian(tribe, region) {
	// TODO: move leaders first
	let i = find_active_barbarian(tribe)
	if (i >= 0)
		game.barbarians[i] = region
}

function goto_barbarian_invasion(tribe, black, white) {
	logi("Invasion!")

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

	let k = 0
	for (let i = 0; i < black;) {
		let n = count_barbarians(tribe, path[k])
		if (n < 3) {
			invade_with_active_barbarian(tribe, path[k])
			++i
		} else {
			if (++k > path.length)
				break
		}
	}

	goto_take_actions()
}

// === TAKE ACTIONS ===

function goto_take_actions() {
	game.state = "take_actions"
}

states.take_actions = {
	prompt() {
		view.actions.end_actions = 1
	},
	end_actions() {
		goto_expand_pretender_empire()
	},
}

function goto_expand_pretender_empire() {
	goto_gain_legacy()
}

function goto_gain_legacy() {
	goto_buy_trash_cards()
}

function goto_buy_trash_cards() {
	goto_end_of_turn()
}

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

// === COMMON LIBRARY ===

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

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

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

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

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

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

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

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

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

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

// Array remove and insert (faster than splice)

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

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

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

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

// Set as plain sorted array

function set_clear(set) {
	set.length = 0
}

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

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

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

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

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

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

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

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

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

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