77 lines
1.9 KiB
Zig
77 lines
1.9 KiB
Zig
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;
|
|
}
|