Use set for traitor instead of tracking ownership with dictionary.

2 files changed, 180 insertions, 65 deletions

diff --git a/play.js b/play.js
index 3747df3..c5ef4a0 100644
--- a/play.js
+++ b/play.js
@@ -1,5 +1,21 @@
 "use strict"
 
+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
+}
+
 const CLEOPATRA = "Cleopatra"
 const DEAD = "Dead"
 const LEVY = "Levy"
@@ -123,12 +139,16 @@ function block_description(b) {
 	return block_owner(b)
 }
 
-function block_owner(who) {
-	if (who in view.owner)
-		return view.owner[who]
+function block_original_owner(who) {
 	return BLOCKS[who].owner
 }
 
+function block_owner(who) {
+	if (set_has(view.traitor, who))
+		return enemy(block_original_owner(who))
+	return block_original_owner(who)
+}
+
 function block_name(b) {
 	return BLOCKS[b].name
 }
@@ -471,7 +491,7 @@ function update_map() {
 				let image = " block_" + info.label
 				let known = " known"
 				let jupiter = ""
-				if (block_owner(b) !== BLOCKS[b].owner && view.game_over)
+				if (set_has(view.traitor, b) && view.game_over)
 					jupiter = " jupiter"
 				element.classList = info.color + known + " block" + image + moved + jupiter
 				update_steps(b, element, true)
@@ -479,7 +499,7 @@ function update_map() {
 				let jupiter = ""
 				let mars = ""
 				let neptune = ""
-				if (block_owner(b) !== BLOCKS[b].owner)
+				if (set_has(view.traitor, b))
 					jupiter = " jupiter"
 				if (block_owner(b) === view.mars && space === view.surprise)
 					mars = " mars"
diff --git a/rules.js b/rules.js
index e186641..0d4442d 100644
--- a/rules.js
+++ b/rules.js
@@ -134,56 +134,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 = {}
@@ -265,12 +215,16 @@ function move_to(who, from, to) {
 		game.last_used[e] = game.active
 }
 
-function block_owner(who) {
-	if (who in game.owner)
-		return game.owner[who]
+function block_original_owner(who) {
 	return BLOCKS[who].owner
 }
 
+function block_owner(who) {
+	if (set_has(game.traitor, who))
+		return enemy(block_original_owner(who))
+	return block_original_owner(who)
+}
+
 function block_name(who) {
 	return BLOCKS[who].name
 }
@@ -301,23 +255,22 @@ function is_dead(b) {
 
 function eliminate_block(who) {
 	if (who === CLEOPATRA) {
-		let new_owner = enemy(game.owner[who])
+		set_toggle(game.traitor, who)
 		game.flash = "Cleopatra was captured."
-		log("Cleopatra joined " + new_owner + "!")
-		game.owner[who] = new_owner
+		log("Cleopatra joined " + block_owner(who) + "!")
 	} else {
 		game.flash = block_name(who) + " was eliminated."
 		log(block_name(who) + " was eliminated.")
 		game.location[who] = DEAD
 		game.steps[who] = BLOCKS[who].steps
-		delete game.owner[who]
+		set_delete(game.traitor, who)
 	}
 }
 
 function disband_block(who) {
 	game.location[who] = LEVY
 	game.steps[who] = BLOCKS[who].steps
-	delete game.owner[who]
+	set_delete(game.traitor, who)
 }
 
 function reduce_block(who) {
@@ -2556,7 +2509,7 @@ exports.setup = function (seed, scenario, options) {
 		turn: 0,
 		location: {},
 		steps: {},
-		owner: {},
+		traitor: [],
 		moved: {},
 		limits: {},
 		last_used: {},
@@ -2772,7 +2725,7 @@ exports.view = function(state, current) {
 		hand: (current === CAESAR) ? game.c_hand : (current === POMPEIUS) ? game.p_hand : observer_hand(),
 		who: (game.active === current) ? game.who : null,
 		location: game.location,
-		owner: game.owner,
+		traitor: game.traitor,
 		steps: game.steps,
 		moved: game.moved,
 		battle: null,
@@ -2796,3 +2749,145 @@ 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
+}
+
+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
+			return array_remove(set, m)
+	}
+	return array_insert(set, a, item)
+}
+
+// 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
+}