lib::list.zig (7180B)
1 const std = @import("std"); 2 3 const utils = @import("lib::utils.zig"); 4 5 pub fn List(T: type) type { 6 return struct { 7 const Self = @This(); 8 9 pub const Error = error{ OutOfMemory, IndexOutOfBounds, Empty }; 10 pub const Value = T; 11 12 const Element = struct { 13 val: Value, 14 next: *@This(), 15 prev: *@This(), 16 17 fn jmp(self: *Element, idx: isize) *Element { 18 var ret = self; 19 20 for (0..@abs(idx)) |_| { 21 ret = if (idx > 0) ret.next else ret.prev; 22 } 23 24 return ret; 25 } 26 27 pub fn del(self: *Element, gpa: std.mem.Allocator) void { 28 self.next.prev = self.prev; 29 self.prev.next = self.next; 30 31 gpa.destroy(self); 32 } 33 34 fn init(gpa: std.mem.Allocator, prv: ?*Element, nxt: ?*Element, val: Value) !*Element { 35 const ret = try gpa.create(Element); 36 ret.* = Element{ 37 .prev = prv orelse ret, 38 .next = nxt orelse ret, 39 .val = val, 40 }; 41 return ret; 42 } 43 44 pub fn add_prev(self: *Element, gpa: std.mem.Allocator, val: Value) !*Element { 45 self.prev.next = try Element.init(gpa, self.prev, self, val); 46 self.prev = self.prev.next; 47 if (self.next == self) self.next = self.prev; 48 return self.prev; 49 } 50 51 pub fn add_next(self: *Element, gpa: std.mem.Allocator, val: Value) !*Element { 52 self.next.prev = try Element.init(gpa, self, self.next, val); 53 self.next = self.next.prev; 54 if (self.prev == self) self.prev = self.next; 55 return self.next; 56 } 57 58 pub fn new(gpa: std.mem.Allocator, val: Value) !*Element { 59 return try Element.init(gpa, null, null, val); 60 } 61 }; 62 63 pub fn Iterator(@"const": bool) type { 64 return struct { 65 const Super = utils.mod_ptr_t(*Self, "const", @"const"); 66 const This = utils.mod_ptr_t(*Element, "const", @"const"); 67 68 super: Super, 69 this: ?This, 70 71 pub fn new(sup: Super) @This() { 72 return .{ 73 .super = sup, 74 .this = sup.tip, 75 }; 76 } 77 78 pub fn next(self: *@This()) ?Value { 79 if (self.this) |el| { 80 self.this = if (el.next == self.super.tip) null else el.next; 81 return el.val; 82 } else { 83 return null; 84 } 85 } 86 87 pub fn pop(self: *@This()) void { 88 if (@"const") @compileError("Cannot call pop() on a const Iterator"); 89 90 const el = if (self.this) |el| el.prev else self.super.tip orelse return; 91 92 if (self.this == el) self.this = null; 93 94 self.super.del(el); 95 } 96 97 pub fn push(self: *@This(), val: Value) !void { 98 if (@"const") @compileError("Cannot call push() on a const Iterator"); 99 100 if (self.this) |el| { 101 self.super.retip(el, try self.super.insert(.prev, el, val)); 102 } else if (self.super.tip) |el| { 103 _ = try self.super.insert(.prev, el, val); 104 } else { 105 try self.super.begin(val); 106 } 107 } 108 }; 109 } 110 111 _len: isize, 112 tip: ?*Element, 113 114 gpa: std.mem.Allocator, 115 116 pub fn iter(self: anytype) Iterator(utils.is_const(@TypeOf(self))) { 117 return Iterator(utils.is_const(@TypeOf(self))).new(self); 118 } 119 120 pub fn init(gpa: std.mem.Allocator) Self { 121 return Self{ 122 ._len = 0, 123 .tip = null, 124 .gpa = gpa, 125 }; 126 } 127 128 pub fn len(self: *const Self) usize { 129 return @intCast(self._len); 130 } 131 132 pub fn eql(self: *const Self, other: *const Self, eql_fn: fn (Value, Value) bool) bool { 133 if (self._len != other._len) return false; 134 135 var iter1 = self.iter(); 136 var iter2 = other.iter(); 137 138 while (iter1.next()) |val1| { 139 if (!eql_fn(val1, iter2.next().?)) return false; 140 } 141 142 return true; 143 } 144 145 pub fn deinit(self: *Self) void { 146 while (true) { 147 _ = self.pop(-1) catch break; 148 } 149 } 150 151 fn _at(self: *Self, idx: isize) Error!*Element { 152 if (self.tip) |tip| { 153 const haf: isize = utils.sign(idx) * @divTrunc(self._len, 2); 154 return tip.jmp(@rem(idx + haf, self._len) - haf); 155 } else { 156 return Error.Empty; 157 } 158 } 159 160 fn at(self: *Self, idx: isize) Error!*Element { 161 return if (-self._len <= idx and idx < self._len) 162 try self._at(idx) 163 else 164 Error.IndexOutOfBounds; 165 } 166 167 pub fn set(self: *Self, idx: isize, val: Value) Error!void { 168 (try self.at(idx)).val = val; 169 } 170 171 pub fn get(self: *Self, idx: isize) Error!Value { 172 return (try self.at(idx)).val; 173 } 174 175 fn del(self: *Self, el: *Element) void { 176 self._len -= 1; 177 178 if (self.tip == el) { 179 self.tip = if (el.next == el) null else el.next; 180 } 181 182 el.del(self.gpa); 183 } 184 185 pub fn pop(self: *Self, idx: isize) Error!Value { 186 const el = try self.at(idx); 187 const ret = el.val; 188 189 self.del(el); 190 191 return ret; 192 } 193 194 fn begin(self: *Self, val: Value) !void { 195 if (self.tip) |_| @panic("This function can only be called on an empty list"); 196 197 self.tip = try Element.new(self.gpa, val); 198 self._len = 1; 199 } 200 201 fn insert(self: *Self, dir: enum { next, prev }, anchor: *Element, val: Value) !*Element { 202 const new = if (dir == .next) 203 try anchor.add_next(self.gpa, val) 204 else 205 try anchor.add_prev(self.gpa, val); 206 207 self._len += 1; 208 209 return new; 210 } 211 212 fn retip(self: *Self, old: ?*Element, new: *Element) void { 213 if (self.tip == old) self.tip = new; 214 } 215 216 pub fn push(self: *Self, idx: isize, val: Value) Error!void { 217 const len1 = self._len + 1; 218 219 if (-len1 <= idx and idx < len1) { 220 const el = self._at(idx) catch return self.begin(val); 221 222 const new = try self.insert(if (idx < 0) .next else .prev, el, val); 223 224 if (idx == -len1 or idx == 0) { 225 self.tip = new; 226 } 227 } else { 228 return Error.IndexOutOfBounds; 229 } 230 } 231 }; 232 }