Shuffle an array of objects by a given selector key

shuffle.js

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
}