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
|
const std = @import("std");
const Order = std.math.Order;
const Value = @import("value.zig").Value;
const RangeSet = @This();
ranges: std.ArrayList(Range),
pub const Range = struct {
start: Value,
end: Value,
src: usize,
};
pub fn init(allocator: *std.mem.Allocator) RangeSet {
return .{
.ranges = std.ArrayList(Range).init(allocator),
};
}
pub fn deinit(self: *RangeSet) void {
self.ranges.deinit();
}
pub fn add(self: *RangeSet, start: Value, end: Value, src: usize) !?usize {
for (self.ranges.items) |range| {
if ((start.compare(.gte, range.start) and start.compare(.lte, range.end)) or
(end.compare(.gte, range.start) and end.compare(.lte, range.end)))
{
// ranges overlap
return range.src;
}
}
try self.ranges.append(.{
.start = start,
.end = end,
.src = src,
});
return null;
}
/// Assumes a and b do not overlap
fn lessThan(_: void, a: Range, b: Range) bool {
return a.start.compare(.lt, b.start);
}
pub fn spans(self: *RangeSet, start: Value, end: Value) !bool {
std.sort.sort(Range, self.ranges.items, {}, lessThan);
if (!self.ranges.items[0].start.eql(start) or
!self.ranges.items[self.ranges.items.len - 1].end.eql(end))
{
return false;
}
var space: Value.BigIntSpace = undefined;
var counter = try std.math.big.int.Managed.init(self.ranges.allocator);
defer counter.deinit();
// look for gaps
for (self.ranges.items[1..]) |cur, i| {
// i starts counting from the second item.
const prev = self.ranges.items[i];
// prev.end + 1 == cur.start
try counter.copy(prev.end.toBigInt(&space));
try counter.addScalar(counter.toConst(), 1);
const cur_start_int = cur.start.toBigInt(&space);
if (!cur_start_int.eq(counter.toConst())) {
return false;
}
}
return true;
}
|
