Regrettably, the standard data types in JavaScript, particularly Map, do not offer much support for this specific task due to their lack of relevant methods.
Typically, the majority of entries will belong to consecutive ranges with identical values.
Nevertheless, we can take advantage of this pattern and utilize a binary search approach on sorted arrays, assuming that the transition tables will remain relatively static.
To encode continuous input ranges leading to the same state, store the lowest value of each range in a sorted array. Then, keep the corresponding states at the matching indices in a separate array:
let inputs = [0, 5, 10]; // Input ranges [0,4], [5,9], [10,∞)
let states = [0, 1, 0 ]; // Inputs [0,4] lead to state 0, [5,9] to 1, [10,∞) to 0
When given an input, conduct a binary search on the inputs array similar to Java's floorEntry(k):
// Retrieves the index of the largest element less than or equal to
// the specified element, or returns undefined if none exists:
function floorIndex(sorted, element) {
let low = 0;
let high = sorted.length - 1;
while (low <= high) {
let mid = low + high >> 1;
if (sorted[mid] > element) {
high = mid - 1;
} else if (sorted[mid] < element) {
low = mid + 1;
} else {
return mid
}
}
return low - 1;
}
// Example: Transition to 1 for emoticons in range 1F600 - 1F64F:
let transitions = {
inputs: [0x00000, 0x1F600, 0x1F650],
states: [0, 1, 0 ]
};
let input = 0x1F60B; // 😋
let next = transitions.states[floorIndex(transitions.inputs, input)];
console.log(`transition to ${next}`);
This search operation requires O(log n) steps where n is the count of contiguous input ranges. Consequently, a single state's transition table demands space proportional to O(n). This method remains effective for both sparse and dense transition tables as long as our initial assumption remains valid - the number of successive input ranges resulting in the same state is limited.