diff options
author | theia | 2022-08-08 13:08:31 -0400 |
---|---|---|
committer | theia | 2022-08-08 13:08:31 -0400 |
commit | a38ede6126ebcb667f92d68be3442bb438b7e31b (patch) | |
tree | dc5670706205b8c720202852f6f81aaf90a814e0 | |
parent | 5784d506595758277e7b09691aafe4252d1a5763 (diff) |
added logoot crdt for ordered lists
-rw-r--r-- | logoot.js | 134 |
1 files changed, 134 insertions, 0 deletions
diff --git a/logoot.js b/logoot.js new file mode 100644 index 0000000..f183cbe --- /dev/null +++ b/logoot.js @@ -0,0 +1,134 @@ +export default { + + maxInt: 9007199254740992, + + begin() { + return [] + }, + + end() { + return [this.maxInt] + }, + + lengthWithoutZeros(a) { + let length = a.length + while (length > 0 && a[length - 1] == 0) { + length-- + } + return length + }, + + between(a, b) { + // Strip zeros and find common length + const aLength = this.lengthWithoutZeros(a) + const bLength = this.lengthWithoutZeros(b) + const minLength = Math.min(aLength, bLength) + + // Initialize output + const out = [] + + // Find the break point where a[i] != b[i] + let i = 0 + while (i < minLength && a[i] == b[i]) { + out.push(a[i]) + i++ + } + + // Initialize upper and lower bounds for + // sampling the last digit + let lowerBound = 1 + let upperBound = this.maxInt + + if (i < minLength) { + // If the break happened before we hit + // the end of one of the arrays + + if (Math.abs(a[i] - b[i]) > 1) { + // If a[i] and b[i] are more than one + // away from each other, just sample + // between them + lowerBound = Math.min(a[i], b[i]) + 1 + upperBound = Math.max(a[i], b[i]) - 1 + } else { + // If they are one away no integers + // will fit in between, so add new layer + const lesser = (a[i] < b[i])? a : b + out.push(lesser[i]) + i++ + + while (i < lesser.length && lesser[i] >= this.maxInt) { + // If the lesser is at it's limit, + // we will need to add even more layers + out.push(lesser[i]) + i++ + } + + if (i < lesser.length) { + // Sample something greater than + // the lesser digit + lowerBound = lesser[i] + 1 + } + } + } else { + // The break happened because we hit + // the end of one of the arrays. + + if (aLength == bLength) { + // If they are entirely equal, + // there is nothing in between + // just return what we have + return out + } + + const longerLength = Math.max(aLength, bLength) + const longer = (a.length == longerLength)? a : b + while (i < longerLength && longer[i] == 0) { + // Skip past the zeros because we can't sample + // for digits less than zero + out.push(0) + i++ + } + + if (i < longerLength) { + if (longer[i] == 1) { + // If longer is at it's limit, + // we still need to add another layer + out.push(0) + } else { + upperBound = longer[i] - 1 + } + } + } + + // Finally, sample between the upper and + // lower bounds + out.push(Math.floor(Math.random() * (upperBound + 1 - lowerBound)) + lowerBound) + return out + }, + + compare(a, b) { + // Strip zeros and find common length + const aLength = this.lengthWithoutZeros(a) + const bLength = this.lengthWithoutZeros(b) + const minLength = Math.min(aLength, bLength) + + // See if there are any differences + for (let i = 0; i < minLength; i++) { + if (a[i] > b[i]) { + return 1 + } else if (a[i] < b[i]) { + return -1 + } + } + + // If they are all the same up til now, + // the longer one is bigger + if (aLength > bLength) { + return 1 + } else if (aLength < bLength) { + return -1 + } else { + return 0 + } + }, +} |