-
Notifications
You must be signed in to change notification settings - Fork 0
/
utils.js
99 lines (90 loc) · 3.28 KB
/
utils.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// Merge right into left
export function merge(left, right) {
// If left contains right, return
if (!right.tip) return
if (left.tip && right.tip) {
if (left.tip.chainhash == right.tip.chainhash) return
if (left.contains(right.tip.key)) return
}
let commonChainRight = findCommonChain(left, right)
let commonChainLeft = left.chain.indexOf(right.chain[commonChainRight])
let common = left.blocks[left.chain[commonChainLeft]]
// No common hash found :-(
if (commonChainRight == -1) {
// If left is empty - allow
if (left.length == 0) {
// TODO: Would it not be smarter in this case to
// clone all the properties of right into left instead of recompute?
// Test what is faster.
commonChainRight = -1
commonChainLeft = -1
} else {
throw new Error('Unable to merge. Left side is not empty and has no common commit with right side.')
}
}
// Compute the Right hand blocks
let mergeblocksRight = []
let deltaFromCommonParentRight = 0
for (var i = commonChainRight+1; i < right.length; i++) {
let mhash = right.chain[i]
let mblock = right.blocks[mhash]
deltaFromCommonParentRight += mblock.delta
mblock.deltaFromCommonParent = deltaFromCommonParentRight
mergeblocksRight.push(mblock)
}
// Remove already-merged commits
mergeblocksRight = mergeblocksRight.filter(block => {
return !left.containsCommit(block.commit)
})
// Compute the Left hand blocks
let mergeBlocksLeft = []
let deltaFromCommonParentLeft = 0
for (var i = commonChainLeft+1; i < left.length; i++) {
let mhash = left.chain[i]
let mblock = left.blocks[mhash]
deltaFromCommonParentLeft += mblock.delta
mblock.deltaFromCommonParent = deltaFromCommonParentLeft
mergeBlocksLeft.push(mblock)
}
let mergeBlocks = mergeBlocksLeft.concat(mergeblocksRight)
sortBlocksByDeltaFromCommonParent(mergeBlocks)
// Reset left to common
left.chain.splice(commonChainLeft+1)
left.tip = common
// Recompute chain
let deltaFromCommonParentForPrevNode = 0
mergeBlocks.forEach((block, index) => {
let newDelta = block.deltaFromCommonParent - deltaFromCommonParentForPrevNode
deltaFromCommonParentForPrevNode += newDelta
delete left.blocks[block.chain]
left.push(block.value, newDelta, block.commit)
})
}
function sortBlocksByDeltaFromCommonParent(blocks) {
blocks.sort((a,b) => {
if (a.deltaFromCommonParent < b.deltaFromCommonParent) return -1
if (a.deltaFromCommonParent > b.deltaFromCommonParent) return 1
return 0
})
}
function sortBlocksByDelta(blocks) {
blocks.sort((a,b) => {
let anano = a.delta[0] * 1e9 + a.delta[1]
let bnano = b.delta[0] * 1e9 + b.delta[1]
if (anano < bnano) return -1
if (anano > bnano) return 1
return 0
})
}
function findCommonChain(left, right) {
// TODO: Probably should use binary
// Loop backwards looking for common chainhash
let index = -1;
for (var i=right.chain.length-1; i > -1; i--) {
if (left.contains(right.chain[i])) {
index = i
break
}
}
return index
}