Optimize road limit state storage.

1 files changed, 48 insertions, 4 deletions

diff --git a/rules.js b/rules.js
index 7105997..983749d 100644
--- a/rules.js
+++ b/rules.js
@@ -235,11 +235,11 @@ function deal_cards(deck, n) {
 function reset_road_limits() {
 	game.sea_moved = []
 	game.sea_retreated = false
-	game.limits = {}
+	game.limits = []
 }
 
 function road_limit(e) {
-	return game.limits[e]|0
+	return map_get(game.limits, e, 0)
 }
 
 function set_attacker(where, side) {
@@ -264,7 +264,7 @@ function move_to(who, from, to) {
 	let e = edge_id(from, to)
 	game.location[who] = to
 	game.last_from = from
-	game.limits[e] = road_limit(e) + 1
+	map_set(game.limits, e, road_limit(e) + 1)
 	if (is_contested_space(to)) {
 		if (game.active === CAESAR) {
 			set_add(game.c_last_used, e)
@@ -1752,6 +1752,7 @@ function end_player_turn() {
 }
 
 function goto_pick_battle() {
+	reset_road_limits()
 	game.active = game.p1
 	if (have_contested_spaces())
 		game.state = 'pick_battle'
@@ -2626,7 +2627,7 @@ exports.setup = function (seed, scenario, options) {
 		steps: [],
 		traitor: [],
 		moved: [],
-		limits: {},
+		limits: [],
 		c_last_used: [],
 		p_last_used: [],
 		c_attacker: [],
@@ -2888,6 +2889,15 @@ function array_insert(array, index, item) {
 	return array
 }
 
+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
+}
+
 function set_clear(set) {
 	set.length = 0
 }
@@ -2956,6 +2966,40 @@ function set_toggle(set, item) {
 	return array_insert(set, a, item)
 }
 
+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)
+}
+
 // Fast deep copy for objects without cycles
 function object_copy(original) {
 	if (Array.isArray(original)) {