From 46cb8d83adfa4db5433d5f201c7b69f085cdc4a1 Mon Sep 17 00:00:00 2001
From: Tor Andersson <tor@ccxvii.net>
Date: Sun, 2 Oct 2022 21:06:57 +0200
Subject: Use sets.

---
 rules.js | 297 ++++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 190 insertions(+), 107 deletions(-)

diff --git a/rules.js b/rules.js
index 12d9630..0a71e3a 100644
--- a/rules.js
+++ b/rules.js
@@ -133,56 +133,6 @@ function remove_from_array(array, item) {
 		array.splice(i, 1)
 }
 
-function deep_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] = deep_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] = deep_copy(v)
-			else
-				copy[i] = v
-		}
-		return copy
-	}
-}
-
-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 = deep_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 clear_undo() {
-	game.undo = []
-}
-
 function gen_action_undo(view) {
 	if (!view.actions)
 		view.actions = {}
@@ -569,7 +519,7 @@ function block_max_steps(who) {
 }
 
 function can_activate(who) {
-	return block_owner(who) === game.active && !game.moved[who] && !game.dead[who]
+	return block_owner(who) === game.active && !set_has(game.moved, who) && !set_has(game.dead, who)
 }
 
 function is_area_on_map(location) {
@@ -581,7 +531,7 @@ function is_block_on_map(b) {
 }
 
 function is_block_alive(b) {
-	return is_area_on_map(game.location[b]) && !game.dead[b]
+	return is_area_on_map(game.location[b]) && !set_has(game.dead, b)
 }
 
 function border_id(a, b) {
@@ -612,7 +562,7 @@ function count_friendly(where) {
 	let p = game.active
 	let count = 0
 	for (let b of BLOCKLIST)
-		if (game.location[b] === where && block_owner(b) === p && !game.dead[b])
+		if (game.location[b] === where && block_owner(b) === p && !set_has(game.dead, b))
 			++count
 	return count
 }
@@ -621,7 +571,7 @@ function count_enemy(where) {
 	let p = ENEMY[game.active]
 	let count = 0
 	for (let b of BLOCKLIST)
-		if (game.location[b] === where && block_owner(b) === p && !game.dead[b])
+		if (game.location[b] === where && block_owner(b) === p && !set_has(game.dead, b))
 			++count
 	return count
 }
@@ -631,7 +581,7 @@ function count_enemy_excluding_reserves(where) {
 	let count = 0
 	for (let b of BLOCKLIST)
 		if (game.location[b] === where && block_owner(b) === p)
-			if (!game.reserves.includes(b))
+			if (!set_has(game.reserves, b))
 				++count
 	return count
 }
@@ -746,7 +696,7 @@ function count_pinned(where) {
 	let count = 0
 	for (let b of BLOCKLIST)
 		if (game.location[b] === where && block_owner(b) === game.active)
-			if (!game.reserves.includes(b))
+			if (!set_has(game.reserves, b))
 				++count
 	return count
 }
@@ -940,18 +890,18 @@ function can_muster_to(muster) {
 }
 
 function is_battle_reserve(who) {
-	return game.reserves.includes(who)
+	return set_has(game.reserves, who)
 }
 
 function is_attacker(who) {
-	if (game.location[who] === game.where && block_owner(who) === game.attacker[game.where] && !game.dead[who])
-		return !game.reserves.includes(who)
+	if (game.location[who] === game.where && block_owner(who) === game.attacker[game.where] && !set_has(game.dead, who))
+		return !set_has(game.reserves, who)
 	return false
 }
 
 function is_defender(who) {
-	if (game.location[who] === game.where && block_owner(who) !== game.attacker[game.where] && !game.dead[who])
-		return !game.reserves.includes(who)
+	if (game.location[who] === game.where && block_owner(who) !== game.attacker[game.where] && !set_has(game.dead, who))
+		return !set_has(game.reserves, who)
 	return false
 }
 
@@ -1018,12 +968,12 @@ function eliminate_block(who) {
 		case "French Mercenary": game.location[who] = "France"; break
 		}
 		game.steps[who] = block_max_steps(who)
-		game.dead[who] = true
+		set_add(game.dead, who)
 		return
 	}
 	game.location[who] = POOL
 	game.steps[who] = block_max_steps(who)
-	game.dead[who] = true
+	set_add(game.dead, who)
 }
 
 function reduce_block(who) {
@@ -1289,7 +1239,7 @@ function setup_kingmaker() {
 	deploy_lancaster("Canterbury (church)", "Enemy")
 
 	// Prisoner!
-	game.dead["Henry VI"] = true
+	set_add(game.dead, "Henry VI")
 }
 
 function setup_richard_iii() {
@@ -1345,11 +1295,11 @@ function setup_richard_iii() {
 
 // Kingmaker scenario special rule
 function free_henry_vi() {
-	if (game.dead["Henry VI"]) {
+	if (set_has(game.dead, "Henry VI")) {
 		if ((game.active === LANCASTER && is_friendly_area("Middlesex")) ||
 			(game.active === YORK && is_enemy_area("Middlesex"))) {
 			log("Henry VI rescued!")
-			delete game.dead["Henry VI"]
+			set_delete(game.dead, "Henry VI")
 		}
 	}
 }
@@ -1380,8 +1330,8 @@ function start_game_turn() {
 	reset_border_limits()
 	game.last_used = {}
 	game.attacker = {}
-	game.reserves = []
-	game.moved = {}
+	set_clear(game.reserves)
+	set_clear(game.moved)
 
 	goto_card_phase()
 }
@@ -1679,7 +1629,7 @@ states.muster_move_1 = {
 		move_block(game.who, from, to)
 		if (to === game.where) {
 			log_move_end()
-			game.moved[game.who] = true
+			set_add(game.moved, game.who)
 			game.who = null
 			game.state = 'muster_who'
 		} else {
@@ -1702,7 +1652,7 @@ states.muster_move_2 = {
 		log_move_continue(to)
 		log_move_end()
 		move_block(game.who, game.location[game.who], to)
-		game.moved[game.who] = true
+		set_add(game.moved, game.who)
 		game.who = null
 		game.state = 'muster_who'
 	},
@@ -1726,7 +1676,7 @@ function move_block(who, from, to) {
 			game.main_border[to] = from
 		} else {
 			if (game.attacker[to] !== game.active || game.main_border[to] !== from) {
-				game.reserves.push(who)
+				set_add(game.reserves, who)
 				return RESERVE_MARK
 			}
 		}
@@ -1845,7 +1795,7 @@ states.recruit_where = {
 		game.recruit_log.push([to])
 		--game.moves
 		game.location[game.who] = to
-		game.moved[game.who] = true
+		set_add(game.moved, game.who)
 		end_action()
 	},
 	block: pop_undo,
@@ -1943,7 +1893,7 @@ states.sea_move_to = {
 	},
 	area: function (to) {
 		game.location[game.who] = to
-		game.moved[game.who] = true
+		set_add(game.moved, game.who)
 
 		if (game.active === game.piracy && is_contested_area(to)) {
 			// Can attack with piracy, but no port-to-port bonus.
@@ -1980,7 +1930,7 @@ function end_move() {
 			game.activated.push(game.origin)
 			game.moves --
 		}
-		game.moved[game.who] = true
+		set_add(game.moved, game.who)
 	}
 	game.last_from = null
 	end_action()
@@ -2052,7 +2002,7 @@ function end_battle() {
 	game.flash = ""
 	game.battle_round = 0
 	reset_border_limits()
-	game.moved = {}
+	set_clear(game.moved)
 	game.defected = {}
 	game.treachery = {}
 	goto_regroup()
@@ -2100,8 +2050,11 @@ states.treason_event = {
 function bring_on_reserves(owner, moved) {
 	for (let b of BLOCKLIST) {
 		if (block_owner(b) === owner && game.location[b] === game.where) {
-			remove_from_array(game.reserves, b)
-			game.moved[b] = moved
+			set_delete(game.reserves, b)
+			if (moved)
+				set_add(game.moved, b)
+			else
+				set_delete(game.moved, b)
 		}
 	}
 }
@@ -2115,7 +2068,7 @@ function start_battle_round() {
 		log("~ Battle Round " + game.battle_round + " ~")
 
 		reset_border_limits()
-		game.moved = {}
+		set_clear(game.moved)
 
 		if (game.battle_round > 1) {
 			bring_on_reserves(LANCASTER, false)
@@ -2152,7 +2105,7 @@ function pump_battle_round() {
 	function filter_battle_blocks(ci, is_candidate) {
 		let output = null
 		for (let b of BLOCKLIST) {
-			if (is_candidate(b) && !game.moved[b] && !game.dead[b]) {
+			if (is_candidate(b) && !set_has(game.moved, b) && !set_has(game.dead, b)) {
 				if (block_initiative(b) === ci) {
 					if (!output)
 						output = []
@@ -2190,7 +2143,7 @@ function pump_battle_round() {
 function pass_with_block(b) {
 	game.flash = block_name(b) + " passed."
 	log_battle(game.flash)
-	game.moved[b] = true
+	set_add(game.moved, b)
 	resume_battle()
 }
 
@@ -2257,7 +2210,7 @@ function roll_attack(active, b, verb) {
 }
 
 function fire_with_block(b) {
-	game.moved[b] = true
+	set_add(game.moved, b)
 	roll_attack(game.active, b, "fired")
 	if (game.hits > 0) {
 		game.active = ENEMY[game.active]
@@ -2271,7 +2224,7 @@ function attempt_treachery(source, target) {
 	if (source) {
 		let once = treachery_tag(source)
 		game.treachery[once] = true
-		game.moved[source] = true
+		set_add(game.moved, source)
 	}
 	let n = block_loyalty(source, target)
 	let rolls = []
@@ -2293,7 +2246,7 @@ function attempt_treachery(source, target) {
 		game.flash += " converted " + block_name(target) + "!"
 		target = swap_blocks(target)
 		game.defected[target] = true
-		game.reserves.push(target)
+		set_add(game.reserves, target)
 	} else {
 		game.flash += " failed to convert " + block_name(target) + "."
 	}
@@ -2302,7 +2255,7 @@ function attempt_treachery(source, target) {
 
 function charge_with_block(heir, target) {
 	let n
-	game.moved[heir] = true
+	set_add(game.moved, heir)
 	roll_attack(game.active, heir, "charged " + block_name(target))
 	n = Math.min(game.hits, game.steps[target])
 	if (n === game.steps[target]) {
@@ -2375,7 +2328,7 @@ function is_senior_royal_heir_in(who, where) {
 
 function can_heir_charge() {
 	let heir = find_senior_heir_in_area(game.active, game.where)
-	if (heir && !game.moved[heir]) {
+	if (heir && !set_has(game.moved, heir)) {
 		if (is_attacker(heir))
 			return game.battle_round < 4 ? heir : null
 		if (is_defender(heir))
@@ -2766,7 +2719,7 @@ states.sea_regroup_to = {
 // SUPPLY PHASE
 
 function goto_supply_phase() {
-	game.moved = {}
+	set_clear(game.moved)
 
 	if (!game.location[game.king]) {
 		game.king = find_next_king(block_owner(game.king))
@@ -3118,7 +3071,7 @@ states.pretender_goes_home = {
 		gen_action_undo(view)
 		let done = true
 		for (let b of BLOCKLIST) {
-			if (block_owner(b) === game.active && is_block_on_map(b) && !game.moved[b]) {
+			if (block_owner(b) === game.active && is_block_on_map(b) && !set_has(game.moved, b)) {
 				if (!is_in_exile(b)) {
 					if (is_heir(b)) {
 						done = false
@@ -3135,7 +3088,7 @@ states.pretender_goes_home = {
 		if (done) {
 			view.prompt = "Pretender Goes Home: You may move nobles to another home."
 			for (let b of BLOCKLIST) {
-				if (block_owner(b) === game.active && is_block_on_map(b) && !game.moved[b]) {
+				if (block_owner(b) === game.active && is_block_on_map(b) && !set_has(game.moved, b)) {
 					if (!is_in_exile(b)) {
 						if (is_at_home(b)) {
 							let n = count_available_homes(b)
@@ -3188,7 +3141,7 @@ states.pretender_goes_home_to = {
 			game.turn_log.push([block_name(game.who), to]) // TODO: "Exile"?
 		else
 			game.turn_log.push([block_name(game.who), to]) // TODO: "Home"?
-		game.moved[game.who] = true
+		set_add(game.moved, game.who)
 		game.location[game.who] = to
 		game.who = null
 		game.state = 'pretender_goes_home'
@@ -3198,7 +3151,7 @@ states.pretender_goes_home_to = {
 }
 
 function goto_exile_limits_pretender() {
-	game.moved = {}
+	set_clear(game.moved)
 	game.active = block_owner(game.pretender)
 	if (check_exile_limits()) {
 		game.state = 'exile_limits_pretender'
@@ -3258,7 +3211,7 @@ states.king_goes_home = {
 		gen_action_undo(view)
 		let done = true
 		for (let b of BLOCKLIST) {
-			if (block_owner(b) === game.active && is_block_on_map(b) && !game.moved[b]) {
+			if (block_owner(b) === game.active && is_block_on_map(b) && !set_has(game.moved, b)) {
 				if (!is_in_exile(b)) {
 					if (!is_at_home(b)) {
 						done = false
@@ -3272,7 +3225,7 @@ states.king_goes_home = {
 		if (done) {
 			view.prompt = "King Goes Home: You may move nobles and heirs to another home."
 			for (let b of BLOCKLIST) {
-				if (block_owner(b) === game.active && is_block_on_map(b) && !game.moved[b]) {
+				if (block_owner(b) === game.active && is_block_on_map(b) && !set_has(game.moved, b)) {
 					if (!is_in_exile(b)) {
 						if (is_at_home(b)) {
 							let n = count_available_homes(b)
@@ -3313,7 +3266,7 @@ states.king_goes_home_to = {
 	},
 	area: function (to) {
 		game.turn_log.push([block_name(game.who), to]) // TODO: "Home"?
-		game.moved[game.who] = true
+		set_add(game.moved, game.who)
 		game.location[game.who] = to
 		game.who = null
 		game.state = 'king_goes_home'
@@ -3323,7 +3276,7 @@ states.king_goes_home_to = {
 }
 
 function goto_exile_limits_king() {
-	game.moved = {}
+	set_clear(game.moved)
 	game.active = block_owner(game.king)
 	if (check_exile_limits()) {
 		game.state = 'exile_limits_king'
@@ -3359,7 +3312,7 @@ states.exile_limits_king = {
 
 function end_political_turn() {
 	// Campaign reset
-	game.dead = {}
+	set_clear(game.dead)
 	for (let b of BLOCKLIST)
 		game.steps[b] = block_max_steps(b)
 
@@ -3399,7 +3352,7 @@ function make_battle_view() {
 
 	function fill_cell(cell, owner, fn) {
 		for (let b of BLOCKLIST)
-			if (game.location[b] === game.where & block_owner(b) === owner && !game.dead[b] && fn(b))
+			if (game.location[b] === game.where & block_owner(b) === owner && !set_has(game.dead, b) && fn(b))
 				cell.push(b)
 	}
 
@@ -3416,21 +3369,25 @@ exports.setup = function (seed, scenario, options) {
 		seed: seed,
 		log: [],
 		undo: [],
-		attacker: {},
-		border_limit: {},
-		last_used: {},
-		location: {},
-		main_border: {},
-		moved: {},
-		dead: {},
+
+		active: null,
 		moves: 0,
-		prompt: null,
-		reserves: [],
-		show_cards: false,
-		steps: {},
 		who: null,
 		where: null,
+
+		show_cards: false,
 		killed_heirs: { Lancaster: 0, York: 0 },
+
+		location: {},
+		steps: {},
+		moved: [],
+		dead: [],
+		reserves: [],
+
+		attacker: {},
+		border_limit: {},
+		last_used: {},
+		main_border: {},
 	}
 
 	// Old RNG for ancient replays
@@ -3512,3 +3469,129 @@ exports.view = function(state, current) {
 
 	return view
 }
+
+// === COMMON LIBRARY ===
+
+// remove item at index (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
+	return array
+}
+
+// insert item at index (faster than splice)
+function array_insert(array, index, item) {
+	for (let i = array.length; i > index; --i)
+		array[i] = array[i - 1]
+	array[index] = item
+	return 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 set
+	}
+	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
+			return array_remove(set, m)
+	}
+	return set
+}
+
+// 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
+	}
+}
+
+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
+}
-- 
cgit v1.2.3