https://graffiti.quest/scripts/DataSet.js

1class DataSet {
2  constructor(
3    elements,
4    id_func = (element) => element.id,
5    id_set_func = (element, new_id) => {
6      element.id = new_id;
7    }
8  ) {
9    this.elements = [...elements];
10    this.id_func = id_func;
11    this.id_set_func = id_set_func;
12
13    this.elements.sort((a, b) => id_func(a) - id_func(b));
14  }
15
16  get(id) {
17    const index = binarySearch(this.elements, id, this.id_func);
18    if (index < 0) {
19      return null;
20    }
21
22    return this.elements[index];
23  }
24
25  add(element) {
26    const elementId = this.id_func(element);
27    const insertionIndex = binarySearch(this.elements, elementId, this.id_func);
28    if (insertionIndex >= 0) {
29      throw new Error(
30        `Element with the given id is already in the array. Inserted element: ${element}`
31      );
32    }
33
34    this.elements.splice(~insertionIndex, 0, element);
35  }
36
37  remove(id) {
38    const deletionIndex = binarySearch(this.elements, id, this.id_func);
39    if (deletionIndex < 0) {
40      throw new Error(
41        `Element with the given id is not in the array. id: ${id}`
42      );
43    }
44
45    this.elements.splice(deletionIndex, 1);
46  }
47
48  updateOnly(updates) {
49    for (const update of updates) {
50      const updateId = this.id_func(update);
51      const updateIndex = binarySearch(this.elements, updateId, this.id_func);
52      if (updateIndex < 0) {
53        throw new Error(`Update for element with invalid id: ${update}`);
54      }
55      const originalElement = this.elements[updateIndex];
56      this.elements[updateIndex] = { ...originalElement, ...update };
57    }
58  }
59
60  clear() {
61    this.elements = [];
62  }
63
64  swap(id1, id2) {
65    const firstIndex = binarySearch(this.elements, id1, this.id_func);
66    const secondIndex = binarySearch(this.elements, id2, this.id_func);
67
68    if (firstIndex < 0 || secondIndex < 0) {
69      throw new Error(
70        `Failed to swap, as one of those ids are not in the dataset: ${id1}, ${id2}`
71      );
72    }
73
74    const firstElement = this.elements[firstIndex];
75    const secondElement = this.elements[secondIndex];
76
77    this.id_set_func(firstElement, id2);
78    this.id_set_func(secondElement, id1);
79
80    this.elements[firstIndex] = secondElement;
81    this.elements[secondIndex] = firstElement;
82  }
83
84  asReadOnly() {
85    return this.elements;
86  }
87
88  map(mapping) {
89    return this.elements.map(mapping);
90  }
91
92  filter(filter) {
93    return this.elements.filter(filter);
94  }
95
96  forEach(func) {
97    this.elements.forEach(func);
98  }
99
100  size() {
101    return this.elements.length;
102  }
103}
104
105function binarySearch(arr, id, id_func) {
106  let m = 0;
107  let n = arr.length - 1;
108  while (m <= n) {
109    let k = (n + m) >> 1;
110    let cmp = id - id_func(arr[k]);
111    if (cmp > 0) {
112      m = k + 1;
113    } else if (cmp < 0) {
114      n = k - 1;
115    } else {
116      return k;
117    }
118  }
119  return ~m;
120}