-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathordered_list.ts
96 lines (86 loc) · 2.22 KB
/
ordered_list.ts
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
/**
* This implementation combines the OrderedList and the CircularList from
* the original haskell library.
*/
export interface Entry<T> {
data: T | null; // only base should have null data
stamp: number;
next: Entry<T>;
prev: Entry<T>;
deleted: boolean;
}
/**
* Implementation of the OrderedList interface from Sleator and
* Dietz paper https://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf
*/
export class OrderedList<T> {
M = 1 << 29;
// 'as any' needed to break cyclic construction,
// after the constructor the lie disappears.
base: Entry<T> = {
data: null,
stamp: 0,
next: undefined as any,
prev: undefined as any,
deleted: false,
};
constructor() {
// At this point 'base' actually has 'undefined' for prev and next.
// A bit or manual patching gets it to be trully cyclical.
this.base.prev = this.base;
this.base.next = this.base;
}
relabel(start: Entry<T>) {
let j = 0;
let end = start;
while (end.stamp - start.stamp <= j * j && end !== this.base) {
end = end.next;
j += 1;
}
const w = end.stamp - start.stamp;
let k = 0;
let cur = start;
while (k !== j) {
cur.stamp = Math.floor((w * k) / j) + start.stamp;
cur = cur.next;
k += 1;
}
}
insertEntryAfter(data: T, after: Entry<T>) {
// no spot left, we need to relabel.
if (after.stamp + 1 === after.next.stamp) {
this.relabel(after);
}
const nextStamp = after.next === this.base ? this.M : after.next.stamp;
const stamp = Math.floor((after.stamp + nextStamp) / 2);
const entry = {
data,
stamp,
next: after.next,
prev: after,
deleted: false,
};
after.next = entry;
return entry;
}
order(x: Entry<T>, y: Entry<T>): -1 | 0 | 1 {
return x.stamp < y.stamp ? 1 : x.stamp === y.stamp ? 0 : -1;
}
delete(x: Entry<T>) {
if (x === this.base) {
throw new Error(`Cannot delete the base entry.`);
}
x.deleted = true;
x.prev.next = x.next;
}
deleted(x: Entry<T>) {
return x.deleted;
}
spliceOut(x: Entry<T>, y: Entry<T>) {
let c = x.next;
while (c != this.base && this.order(c, y) != -1) {
this.delete(c);
c = c.next;
}
}
}