grevych · August 7, 2020 13:24 · Aug 7, 2020
diff --git a/shuffle.js b/shuffle.js
@@ -0,0 +1,145 @@
+class LimitedSet {
+	constructor(size) {
+		this.size = size
+		this.queue = []
+		this.set = new Set()
+	}
+
+	has(key) {
+		return this.set.has(key)
+	}
+
+	add(key, value = true) {
+		if (this.queue.length === this.size) {
+			const last = this.queue.shift()
+			this.set.delete(last)
+		}
+
+		this.queue.push(key)
+		this.set.add(key)
+	}
+}
+
+const createKeyMap = function (posts, selector) {
+	const keyMap = new Map()
+
+	while (posts.length) {
+		const post = posts.shift()
+		const key = selector(post)
+
+		if (!keyMap.has(key)) {
+			keyMap.set(key, [])
+		}
+
+		const list = keyMap.get(key)
+		list.push(post)
+	}
+
+	return keyMap
+}
+
+/*
+ * Shuffle strategy
+ *
+ * Store the elements in a key map grouped by the selector key
+ * Iterate the key map indefinitely in ranges of size equal to the separation
+ * threshold. Add the first element of each key to the result. If the key is
+ * in the limited set, this key is not considered:
+ *
+ *         keyMap
+ *   ------------------  | keyMap:
+ *    A  B  C  D  E  F   |   A: [1, 2, 4],
+ *    -----------------  |   B: [3, 5],
+ *    1  3  6  7  8  10  |   C: [6],
+ *    2  5  -  9  -  -   |   D: [7, 9]
+ *    4  -  -  -  -  -   |   E: [8],
+ *                           F: [10]
+ *
+ *   Keys: A, B, C, D, E, F
+ *   Separation THR: 4
+ *   Expected Result: 1, 3, 6, 7, 8, 2, 5, 10, 9, 4
+ *
+ *   Iteration:     1     2        3           4              5
+ *   Key:           A     B        C           D              E
+ *   Limited Set:   (A)   (A, B)   (A, B, C)   (A, B, C, D)   (B, C, D, E)
+ *   Result:        [1]   [1, 3]   [1, 3, 6]   [1, 3, 6, 7]   [1, 3, 6, 7, 8]
+ *
+ *                                 ^                          ^
+ *                    Keys C and E are removed here since they ran out of elements
+ *
+ *
+ *   Iteration:     6                    7                       8                       9
+ *   Key:           A                    B                       D                       F
+ *   Limited Set:   (C, D, E, A)         (D, E, A, B)            (D, E, A, B)            (E, A, B, F)
+ *   Result:        [1, 3, 6, 7, 8, 2]   [1, 3, 6, 7, 8, 2, 5]   [1, 3, 6, 7, 8, 2, 5]   [1, 3, 6, 7, 8, 2, 5, 10]
+ *
+ *                                                               ^
+ *              Since keys A and D are in cache its element are ommited
+ *                  v
+ *
+ *   Iteration:     10                          11
+ *   Key:           A                           D
+ *   Limited Set:   (E, A, B, F)                (A, B, F, D)
+ *   Result:        [1, 3, 6, 7, 8, 2, 5, 10]   [1, 3, 6, 7, 8, 2, 5, 10, 9]
+ *
+ *
+ *   Remaining elements doesn't guarantee a separation of size of the threshold
+ *   so elements are interspersed from each key
+*/
+const shuffle = function (elements = [], selector = (x => x), separationThreshold = 10) {
+	const result = []
+	const limitedSet = new LimitedSet(separationThreshold)
+	const keyMap = createKeyMap(elements, selector)
+
+	let shuffledElements = null
+
+	while (shuffledElements != result.length) {
+		const generator = keyMap.keys()
+		let index = 0
+		let next = generator.next()
+		shuffledElements  = result.length
+
+		while (index <= separationThreshold && !next.done) {
+			const key = next.value
+
+			if (!limitedSet.has(key)) {
+				const list = keyMap.get(key)
+
+				if (list.length) {
+					result.push(list.shift())
+					limitedSet.add(key)
+
+					if (list.length === 0) {
+						keyMap.delete(key)
+					}
+				}
+
+				index++
+			}
+
+			next = generator.next()
+		}
+	}
+
+  // If the key map is not empty means that is impossible to guarantee a
+  // separation of the given threshold
+	while (keyMap.size) {
+		const generator = keyMap.keys()
+		let next = generator.next()
+
+		while (!next.done) {
+			const key = next.value
+			const list = keyMap.get(key)
+
+			result.push(list.shift())
+
+			if (list.length === 0) {
+				keyMap.delete(key)
+			}
+
+			next = generator.next()
+		}
+	}
+
+	return result
+}