From 03270fc88a894680796c5992ac4aa66ce848237a Mon Sep 17 00:00:00 2001
From: Tor Andersson <tor@ccxvii.net>
Date: Mon, 29 Aug 2022 14:17:13 +0200
Subject: Use sets for reduced status and fortifications.

---
 rules.js | 227 ++++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 145 insertions(+), 82 deletions(-)

diff --git a/rules.js b/rules.js
index 6d1efa0..bd11bf9 100644
--- a/rules.js
+++ b/rules.js
@@ -262,6 +262,69 @@ function clamp(x, min, max) {
 	return Math.min(Math.max(x, min), max)
 }
 
+// Sorted array treated as Set (for JSON)
+function set_index(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 m
+	}
+	return -1
+}
+
+function validate_set(set) {
+	for (let i = 1; i < set.length; ++i)
+		if (set[i] < set[i-1])
+			throw new Error("unsorted set: " + set)
+}
+
+function set_has(set, item) {
+	validate_set(set)
+	return set_index(set, item) >= 0
+}
+
+function set_add(set, item) {
+	validate_set(set)
+	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.splice(a, 0, item)
+}
+
+function set_delete(set, item) {
+	validate_set(set)
+	let i = set_index(set, item)
+	if (i >= 0)
+		set.splice(i, 1)
+}
+
+function set_clear(set) {
+	set.length = 0
+}
+
+function set_toggle(set, item) {
+	if (set_has(set, item))
+		set_delete(set, item)
+	else
+		set_add(set, item)
+}
+
 function remove_from_array(array, item) {
 	let i = array.indexOf(item)
 	if (i >= 0)
@@ -538,6 +601,7 @@ const originally_french_fortresses = [
 	MONTREAL,
 	QUEBEC,
 ]
+originally_french_fortresses.sort((a,b)=>a-b)
 
 const originally_british_fortresses = [
 	ALBANY,
@@ -549,6 +613,7 @@ const originally_british_fortresses = [
 	NEW_YORK,
 	PHILADELPHIA,
 ]
+originally_british_fortresses.sort((a,b)=>a-b)
 
 const originally_british_fortresses_and_all_ports = [
 	ALBANY,
@@ -582,10 +647,8 @@ function define_indian(color, space, tribe) {
 		indians.pieces_from_color[color] = []
 	if (!indians.spaces_from_color[color])
 		indians.spaces_from_color[color] = []
-	if (space) {
-		if (!indians.spaces_from_color[color].includes(space))
-			indians.spaces_from_color[color].push(space)
-	}
+	if (space)
+		set_add(indians.spaces_from_color[color], space)
 	if (!indians.pieces_from_space[space])
 		indians.pieces_from_space[space] = []
 	if (space === PAYS_D_EN_HAUT)
@@ -594,8 +657,8 @@ function define_indian(color, space, tribe) {
 		indians.tribe_from_space[space] = tribe
 	for (let p = 1; p <= last_piece; ++p) {
 		if (is_indian(p) && pieces[p].name === tribe) {
-			indians.pieces_from_color[color].push(p)
-			indians.pieces_from_space[space].push(p)
+			set_add(indians.pieces_from_color[color], p)
+			set_add(indians.pieces_from_space[space], p)
 			indians.space_from_piece[p] = space
 		}
 	}
@@ -626,11 +689,11 @@ define_indian("gray", SHAWIANGTO, "Tuscarora")
 
 const within_two_of_canajoharie = [ CANAJOHARIE ]
 for_each_exit(CANAJOHARIE, one => {
-	if (!within_two_of_canajoharie.includes(one)) {
-		within_two_of_canajoharie.push(one)
+	if (!set_has(within_two_of_canajoharie, one)) {
+		set_add(within_two_of_canajoharie, one)
 		for_each_exit(one, two => {
-			if (!within_two_of_canajoharie.includes(two)) {
-				within_two_of_canajoharie.push(two)
+			if (!set_has(within_two_of_canajoharie, two)) {
+				set_add(within_two_of_canajoharie, two)
 			}
 		})
 	}
@@ -638,15 +701,15 @@ for_each_exit(CANAJOHARIE, one => {
 
 const within_two_of_gray_settlement = []
 indians.spaces_from_color.gray.forEach(zero => {
-	within_two_of_gray_settlement.push(zero)
+	set_add(within_two_of_gray_settlement, zero)
 })
 indians.spaces_from_color.gray.forEach(zero => {
 	for_each_exit(zero, one => {
-		if (!within_two_of_gray_settlement.includes(one)) {
-			within_two_of_gray_settlement.push(one)
+		if (!set_has(within_two_of_gray_settlement, one)) {
+			set_add(within_two_of_gray_settlement, one)
 			for_each_exit(one, two => {
-				if (!within_two_of_gray_settlement.includes(two)) {
-					within_two_of_gray_settlement.push(two)
+				if (!set_has(within_two_of_gray_settlement, two)) {
+					set_add(within_two_of_gray_settlement, two)
 				}
 			})
 		}
@@ -655,7 +718,7 @@ indians.spaces_from_color.gray.forEach(zero => {
 
 const in_or_adjacent_to_ohio_forks = [ OHIO_FORKS ]
 for_each_exit(OHIO_FORKS, one => {
-	in_or_adjacent_to_ohio_forks.push(one)
+	set_add(in_or_adjacent_to_ohio_forks, one)
 })
 
 // CARD DECK
@@ -1062,15 +1125,14 @@ function unit_strength(p) {
 }
 
 function is_unit_reduced(p) {
-	return game.reduced.includes(p)
+	return set_has(game.reduced, p)
 }
 
 function set_unit_reduced(p, v) {
 	if (v) {
-		if (!game.reduced.includes(p))
-			game.reduced.push(p)
+		set_add(game.reduced, p)
 	} else {
-		remove_from_array(game.reduced, p)
+		set_delete(game.reduced, p)
 	}
 }
 
@@ -1127,45 +1189,45 @@ function is_piece_besieged_in_space(p, s) {
 }
 
 function has_amphib(s) {
-	return game.amphib.includes(s)
+	return set_has(game.amphib, s)
 }
 
 function has_friendly_amphib(s) {
-	return game.active === BRITAIN && game.amphib.includes(s)
+	return game.active === BRITAIN && set_has(game.amphib, s)
 }
 
 function has_enemy_amphib(s) {
-	return game.active === FRANCE && game.amphib.includes(s)
+	return game.active === FRANCE && set_has(game.amphib, s)
 }
 
 function has_fieldworks(s) {
-	return game.fieldworks.includes(s)
+	return set_has(game.fieldworks, s)
 }
 
 function place_fieldworks(s) {
 	log(`Placed fieldworks at ${space_name(s)}.`)
-	game.fieldworks.push(s)
+	set_add(game.fieldworks, s)
 }
 
 function remove_fieldworks(s) {
-	if (game.fieldworks.includes(s)) {
+	if (set_has(game.fieldworks, s)) {
 		// log(`Fieldworks (${space_name(s)}) removed.`)
 		log(`Removed fieldworks at ${space_name(s)}.`)
-		remove_from_array(game.fieldworks, s)
+		set_delete(game.fieldworks, s)
 	}
 }
 
 function place_friendly_raided_marker(s) {
 	log(`Placed raided marker at ${space_name(s)}.`)
-	player.raids.push(s)
+	set_add(player.raids, s)
 }
 
 function has_friendly_raided_marker(s) {
-	return player.raids.includes(s)
+	return set_has(player.raids, s)
 }
 
 function has_enemy_raided_marker(s) {
-	return enemy_player.raids.includes(s)
+	return set_has(enemy_player.raids, s)
 }
 
 function is_space_besieged(s) {
@@ -1177,43 +1239,43 @@ function is_space_unbesieged(s) {
 }
 
 function has_enemy_allied_settlement(s) {
-	return enemy_player.allied.includes(s)
+	return set_has(enemy_player.allied, s)
 }
 
 function has_friendly_allied_settlement(s) {
-	return player.allied.includes(s)
+	return set_has(player.allied, s)
 }
 
 function has_enemy_stockade(s) {
-	return enemy_player.stockades.includes(s)
+	return set_has(enemy_player.stockades, s)
 }
 
 function has_friendly_stockade(s) {
-	return player.stockades.includes(s)
+	return set_has(player.stockades, s)
 }
 
 function has_enemy_fortress(s) {
-	return enemy_player.fortresses.includes(s)
+	return set_has(enemy_player.fortresses, s)
 }
 
 function has_friendly_fortress(s) {
-	return player.fortresses.includes(s)
+	return set_has(player.fortresses, s)
 }
 
 function has_enemy_fort(s) {
-	return enemy_player.forts.includes(s)
+	return set_has(enemy_player.forts, s)
 }
 
 function has_friendly_fort(s) {
-	return player.forts.includes(s)
+	return set_has(player.forts, s)
 }
 
 function has_enemy_fort_uc(s) {
-	return enemy_player.forts_uc.includes(s)
+	return set_has(enemy_player.forts_uc, s)
 }
 
 function has_friendly_fort_uc(s) {
-	return player.forts_uc.includes(s)
+	return set_has(player.forts_uc, s)
 }
 
 function has_enemy_fort_or_fortress(s) {
@@ -1298,27 +1360,27 @@ function is_french_controlled_space(s) {
 }
 
 function has_french_stockade(s) {
-	return game.french.stockades.includes(s)
+	return set_has(game.french.stockades, s)
 }
 
 function has_british_stockade(s) {
-	return game.british.stockades.includes(s)
+	return set_has(game.british.stockades, s)
 }
 
 function has_french_fort(s) {
-	return game.french.forts.includes(s)
+	return set_has(game.french.forts, s)
 }
 
 function has_british_fort(s) {
-	return game.british.forts.includes(s)
+	return set_has(game.british.forts, s)
 }
 
 function is_french_fortress(s) {
-	return game.french.fortresses.includes(s)
+	return set_has(game.french.fortresses, s)
 }
 
 function is_british_fortress(s) {
-	return game.british.fortresses.includes(s)
+	return set_has(game.british.fortresses, s)
 }
 
 function has_french_fortifications(s) {
@@ -1719,29 +1781,29 @@ function award_british_vp(n) {
 }
 
 function remove_friendly_stockade(s) {
-	remove_from_array(player.stockades, s)
+	set_delete(player.stockades, s)
 }
 
 function remove_friendly_fort_uc(s) {
-	remove_from_array(player.forts_uc, s)
+	set_delete(player.forts_uc, s)
 }
 
 function remove_friendly_fort(s) {
-	remove_from_array(player.forts, s)
+	set_delete(player.forts, s)
 }
 
 function remove_enemy_fort_uc(s) {
-	remove_from_array(enemy_player.forts_uc, s)
+	set_delete(enemy_player.forts_uc, s)
 }
 
 function place_friendly_fort(s) {
 	remove_friendly_stockade(s)
 	remove_friendly_fort_uc(s)
-	player.forts.push(s)
+	set_add(player.forts, s)
 }
 
 function place_friendly_fort_uc(s) {
-	player.forts_uc.push(s)
+	set_add(player.forts_uc, s)
 }
 
 // Isolate piece from any forces it may be involved in.
@@ -1804,9 +1866,9 @@ function eliminate_piece(p, verbose=true) {
 			if (is_indian_tribe_eliminated(home)) {
 				log(`Removed ${indians.tribe_from_space[home]} allied marker.`)
 				if (is_british_indian(p))
-					remove_from_array(game.british.allied, home)
+					set_delete(game.british.allied, home)
 				else
-					remove_from_array(game.french.allied, home)
+					set_delete(game.french.allied, home)
 			}
 		}
 	}
@@ -1856,14 +1918,14 @@ function place_piece(who, to) {
 		let home = indians.space_from_piece[who]
 		if (home) {
 			if (is_british_indian(who)) {
-				if (!game.british.allied.includes(home)) {
+				if (!set_has(game.british.allied, home)) {
 					log(`Placed ${indians.tribe_from_space[home]} allied marker.`)
-					game.british.allied.push(home)
+					set_add(game.british.allied, home)
 				}
 			} else {
-				if (!game.french.allied.includes(home)) {
+				if (!set_has(game.french.allied, home)) {
 					log(`Placed ${indians.tribe_from_space[home]} allied marker.`)
-					game.french.allied.push(home)
+					set_add(game.french.allied, home)
 				}
 			}
 		}
@@ -1872,55 +1934,55 @@ function place_piece(who, to) {
 
 function capture_enemy_fortress(s) {
 	log(`Captured fortress at ${space_name(s)}.`)
-	remove_from_array(enemy_player.fortresses, s)
-	player.fortresses.push(s)
+	set_delete(enemy_player.fortresses, s)
+	set_add(player.fortresses, s)
 	award_vp(3)
 }
 
 function recapture_french_fortress(s) {
 	log(`France recaptured fortress at ${space_name(s)}.`)
-	remove_from_array(game.british.fortresses, s)
-	game.french.fortresses.push(s)
+	set_delete(game.british.fortresses, s)
+	set_add(game.french.fortresses, s)
 	award_french_vp(3)
 }
 
 function recapture_british_fortress(s) {
 	log(`Britain recaptured fortress at ${space_name(s)}.`)
-	remove_from_array(game.french.fortresses, s)
-	game.british.fortresses.push(s)
+	set_delete(game.french.fortresses, s)
+	set_add(game.british.fortresses, s)
 	award_british_vp(3)
 }
 
 function capture_enemy_fort_intact(s) {
 	log(`Captured intact fort at ${space_name(s)}.`)
-	remove_from_array(enemy_player.forts, s)
-	player.forts.push(s)
+	set_delete(enemy_player.forts, s)
+	set_add(player.forts, s)
 	award_vp(2)
 }
 
 function capture_enemy_fort(s) {
 	log(`Captured fort at ${space_name(s)}.`)
-	remove_from_array(enemy_player.forts, s)
-	player.forts_uc.push(s)
+	set_delete(enemy_player.forts, s)
+	set_add(player.forts_uc, s)
 	award_vp(2)
 }
 
 function capture_enemy_stockade(s) {
 	log(`Captured stockade at ${space_name(s)}.`)
-	remove_from_array(enemy_player.stockades, s)
-	player.stockades.push(s)
+	set_delete(enemy_player.stockades, s)
+	set_add(player.stockades, s)
 	award_vp(1)
 }
 
 function destroy_enemy_stockade_after_battle(s) {
 	log(`Destroyed stockade at ${space_name(s)}.`)
-	remove_from_array(enemy_player.stockades, s)
+	set_delete(enemy_player.stockades, s)
 	award_vp(1)
 }
 
 function destroy_enemy_stockade_in_raid(s) {
 	log(`Destroyed stockade at ${space_name(s)}.`)
-	remove_from_array(enemy_player.stockades, s)
+	set_delete(enemy_player.stockades, s)
 }
 
 function add_raid(who) {
@@ -1961,10 +2023,10 @@ function lift_sieges_and_amphib() {
 
 	// Recapture abandoned enemy fortresses.
 	for (let s of originally_french_fortresses)
-		if (game.british.fortresses.includes(s) && is_french_controlled_space(s))
+		if (set_has(game.british.fortresses, s) && is_french_controlled_space(s))
 			recapture_french_fortress(s)
 	for (let s of originally_british_fortresses)
-		if (game.french.fortresses.includes(s) && is_british_controlled_space(s))
+		if (set_has(game.french.fortresses, s) && is_british_controlled_space(s))
 			recapture_british_fortress(s)
 
 	// Remove forts u/c if solely occupied by enemy drilled troops
@@ -2976,7 +3038,7 @@ function gen_naval_move() {
 				gen_action_space(to)
 		})
 		ports.forEach(to => {
-			if (to !== from && !game.amphib.includes(to))
+			if (to !== from && !set_has(game.amphib, to))
 				if (is_friendly_controlled_space(to))
 					gen_action_space(to)
 		})
@@ -3587,7 +3649,7 @@ states.amphibious_landing = {
 	},
 	space(to) {
 		push_undo()
-		game.amphib.push(to)
+		set_add(game.amphib, to)
 		apply_move(to)
 		goto_intercept()
 	},
@@ -6886,7 +6948,7 @@ states.construct_stockades = {
 		log(`Stockade at ${space_name(s)}.`)
 		// log(`Constructed stockade at ${space_name(s)}.`)
 		// log(`Stockade at ${space_name(s)} constructed.`)
-		player.stockades.push(s)
+		set_add(player.stockades, s)
 		game.count --
 	},
 	pass() {
@@ -7220,7 +7282,7 @@ events.iroquois_alliance = {
 			has_enemy_fortifications(ONEIDA_CARRY_EAST)
 		if (ff && !ef) {
 			if (game.active === BRITAIN)
-				return within_two_of_gray_settlement.includes(piece_space(JOHNSON))
+				return set_has(within_two_of_gray_settlement, piece_space(JOHNSON))
 			return true
 		}
 		return false
@@ -7357,7 +7419,7 @@ states.restore_units = {
 events.mohawks = {
 	can_play() {
 		let s = piece_space(JOHNSON)
-		if (within_two_of_canajoharie.includes(s))
+		if (set_has(within_two_of_canajoharie, s))
 			if (is_piece_unbesieged(JOHNSON))
 				return can_place_or_restore_indians(first_mohawk, last_mohawk)
 		return false
@@ -7801,7 +7863,7 @@ events.british_ministerial_crisis = {
 		let n = 0
 		for (let i = 0; i < enemy_player.hand.length; ++i) {
 			let c = enemy_player.hand[i]
-			if (british_ministerial_crisis_cards.includes(c))
+			if (set_has(british_ministerial_crisis_cards, c))
 				++n
 		}
 		if (n > 0) {
@@ -7821,7 +7883,7 @@ states.british_ministerial_crisis = {
 			view.prompt = "British Ministerial Crisis: Discard a British Regulars, Highlanders, Light Infantry, Transports, or Victories card."
 			for (let i = 0; i < player.hand.length; ++i) {
 				let c = player.hand[i]
-				if (british_ministerial_crisis_cards.includes(c))
+				if (set_has(british_ministerial_crisis_cards, c))
 					gen_action_discard(c)
 			}
 		} else {
@@ -9049,7 +9111,8 @@ exports.roles = [
 ]
 
 function setup_markers(m, list) {
-	list.forEach(name => m.push(find_space(name)))
+	for (let name of list)
+		set_add(m, find_space(name))
 }
 
 function setup_leader(where, who) {
-- 
cgit v1.2.3