From 26de64be138e6d53212ec1b362796d890dd42c7b Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Mon, 21 Sep 2020 22:47:10 -0700 Subject: adding a function to update the priority of an element --- lib/std/priority_queue.zig | 88 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 88 insertions(+) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index b9be9b70bf..c91af77dfe 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -190,6 +190,31 @@ pub fn PriorityQueue(comptime T: type) type { self.len = new_len; } + fn binarySearch(items: []const T, target: T) usize { + var left: usize = 0; + var right: usize = items.len-1; + + while(left <= right) { + const mid = left + (right - left) / 2; + if (items[mid] == target) { + return mid; + } else if (items[mid] < target) { + left= mid+1; + } else { + right= mid-1; + } + } + + return 0; + } + + pub fn update(self: *Self, elem: T, new_elem: T) !void { + var update_index: usize = binarySearch(self.items, elem); + assert (update_index >= 0 and update_index < self.items.len); + _ = self.removeIndex(update_index); + try self.add(new_elem); + } + pub const Iterator = struct { queue: *PriorityQueue(T), count: usize, @@ -437,3 +462,66 @@ test "std.PriorityQueue: iterator while empty" { expectEqual(it.next(), null); } + +test "std.PriorityQueue: update min heap" { + var queue = PQ.init(testing.allocator, lessThan); + defer queue.deinit(); + + try queue.add(55); + try queue.add(44); + try queue.add(11); + try queue.update(55, 5); + try queue.update(44, 4); + try queue.update(11, 1); + expectEqual(@as(u32, 1), queue.remove()); + expectEqual(@as(u32, 4), queue.remove()); + expectEqual(@as(u32, 5), queue.remove()); +} + + +test "std.PriorityQueue: update same min heap" { + var queue = PQ.init(testing.allocator, lessThan); + defer queue.deinit(); + + try queue.add(1); + try queue.add(1); + try queue.add(2); + try queue.add(2); + try queue.update(1, 5); + try queue.update(2, 4); + expectEqual(@as(u32, 1), queue.remove()); + expectEqual(@as(u32, 2), queue.remove()); + expectEqual(@as(u32, 4), queue.remove()); + expectEqual(@as(u32, 5), queue.remove()); +} + +test "std.PriorityQueue: update max heap" { + var queue = PQ.init(testing.allocator, greaterThan); + defer queue.deinit(); + + try queue.add(55); + try queue.add(44); + try queue.add(11); + try queue.update(55, 5); + try queue.update(44, 1); + try queue.update(11, 4); + expectEqual(@as(u32, 5), queue.remove()); + expectEqual(@as(u32, 4), queue.remove()); + expectEqual(@as(u32, 1), queue.remove()); +} + +test "std.PriorityQueue: update same max heap" { + var queue = PQ.init(testing.allocator, greaterThan); + defer queue.deinit(); + + try queue.add(1); + try queue.add(1); + try queue.add(2); + try queue.add(2); + try queue.update(1, 5); + try queue.update(2, 4); + expectEqual(@as(u32, 5), queue.remove()); + expectEqual(@as(u32, 4), queue.remove()); + expectEqual(@as(u32, 2), queue.remove()); + expectEqual(@as(u32, 1), queue.remove()); +} \ No newline at end of file -- cgit v1.2.3 From f083ea88d8a9fcfdc0e344b122207f6c7fe0be36 Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Tue, 22 Sep 2020 01:05:33 -0700 Subject: using binary search function from std.sort --- lib/std/priority_queue.zig | 20 +++----------------- 1 file changed, 3 insertions(+), 17 deletions(-) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index c91af77dfe..a074fbec19 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -190,26 +190,12 @@ pub fn PriorityQueue(comptime T: type) type { self.len = new_len; } - fn binarySearch(items: []const T, target: T) usize { - var left: usize = 0; - var right: usize = items.len-1; - - while(left <= right) { - const mid = left + (right - left) / 2; - if (items[mid] == target) { - return mid; - } else if (items[mid] < target) { - left= mid+1; - } else { - right= mid-1; - } - } - - return 0; + fn orderFn(lhs: T, rhs: T) std.math.Order { + return std.math.order(lhs, rhs); } pub fn update(self: *Self, elem: T, new_elem: T) !void { - var update_index: usize = binarySearch(self.items, elem); + var update_index: usize = std.sort.binarySearch(T, elem, self.items, orderFn) orelse 0; assert (update_index >= 0 and update_index < self.items.len); _ = self.removeIndex(update_index); try self.add(new_elem); -- cgit v1.2.3 From 69f0fc513a1926e6214733c678f785b724da0340 Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Tue, 22 Sep 2020 01:36:41 -0700 Subject: sorry, local compiler using different version of zig --- lib/std/priority_queue.zig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index a074fbec19..345d5db584 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -195,7 +195,7 @@ pub fn PriorityQueue(comptime T: type) type { } pub fn update(self: *Self, elem: T, new_elem: T) !void { - var update_index: usize = std.sort.binarySearch(T, elem, self.items, orderFn) orelse 0; + var update_index: usize = std.sort.binarySearch(T, elem, self.items, {}, orderFn) orelse 0; assert (update_index >= 0 and update_index < self.items.len); _ = self.removeIndex(update_index); try self.add(new_elem); -- cgit v1.2.3 From 1345f87f4efb7444516fceb76b1d60ec18ddebc1 Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Tue, 22 Sep 2020 01:50:22 -0700 Subject: items are not sorted, using linear search --- lib/std/priority_queue.zig | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index 345d5db584..6e0e47dd05 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -190,12 +190,19 @@ pub fn PriorityQueue(comptime T: type) type { self.len = new_len; } - fn orderFn(lhs: T, rhs: T) std.math.Order { - return std.math.order(lhs, rhs); + fn linearSearch(elem: T, items: []const T) usize { + var found: usize = 0; + for (items) |item, i| { + if (item == elem) { + found = i; + break; + } + } + return found; } pub fn update(self: *Self, elem: T, new_elem: T) !void { - var update_index: usize = std.sort.binarySearch(T, elem, self.items, {}, orderFn) orelse 0; + var update_index: usize = linearSearch(elem, self.items); assert (update_index >= 0 and update_index < self.items.len); _ = self.removeIndex(update_index); try self.add(new_elem); -- cgit v1.2.3 From a5140cc9020f4e3649ccc14ca4317829ea289306 Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Tue, 22 Sep 2020 02:12:35 -0700 Subject: implemented efficient heapreplace --- lib/std/priority_queue.zig | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index 6e0e47dd05..9c6545c4e1 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -204,8 +204,13 @@ pub fn PriorityQueue(comptime T: type) type { pub fn update(self: *Self, elem: T, new_elem: T) !void { var update_index: usize = linearSearch(elem, self.items); assert (update_index >= 0 and update_index < self.items.len); - _ = self.removeIndex(update_index); - try self.add(new_elem); + // Heapreplace: + // replace the item: self.items[update_index]= new_elem; + // swap the new item to the top of the heap: std.mem.swap(heap[0], heap[update_index]); + // sift up or down: which has been generically implemented as sift down: siftDown(self, 0) + self.items[update_index] = new_elem; + std.mem.swap(T, &self.items[0], &self.items[update_index]); + siftDown(self, 0); } pub const Iterator = struct { -- cgit v1.2.3 From 983830a4ae9955f95b46a4fb64d3914468226ccb Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Tue, 22 Sep 2020 03:46:13 -0700 Subject: replace linearSearch with mem.indexOfScalar, return not found error, factor out siftUp from addUnchecked, use compareFn to decide siftUp/siftDown --- lib/std/priority_queue.zig | 33 +++++++++++++-------------------- 1 file changed, 13 insertions(+), 20 deletions(-) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index 9c6545c4e1..02188b5564 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -49,7 +49,12 @@ pub fn PriorityQueue(comptime T: type) type { fn addUnchecked(self: *Self, elem: T) void { self.items[self.len] = elem; - var child_index = self.len; + siftUp(self, self.len); + self.len += 1; + } + + fn siftUp(self: *Self, start_index: usize) void { + var child_index = start_index; while (child_index > 0) { var parent_index = ((child_index - 1) >> 1); const child = self.items[child_index]; @@ -61,7 +66,6 @@ pub fn PriorityQueue(comptime T: type) type { self.items[child_index] = parent; child_index = parent_index; } - self.len += 1; } /// Add each element in `items` to the queue. @@ -190,27 +194,16 @@ pub fn PriorityQueue(comptime T: type) type { self.len = new_len; } - fn linearSearch(elem: T, items: []const T) usize { - var found: usize = 0; - for (items) |item, i| { - if (item == elem) { - found = i; - break; - } - } - return found; - } - pub fn update(self: *Self, elem: T, new_elem: T) !void { - var update_index: usize = linearSearch(elem, self.items); + var update_index: usize = std.mem.indexOfScalar(T, self.items, elem) catch |error| return error.ElementNotFound; assert (update_index >= 0 and update_index < self.items.len); - // Heapreplace: - // replace the item: self.items[update_index]= new_elem; - // swap the new item to the top of the heap: std.mem.swap(heap[0], heap[update_index]); - // sift up or down: which has been generically implemented as sift down: siftDown(self, 0) + const old_elem: T = self.items[update_index]; self.items[update_index] = new_elem; - std.mem.swap(T, &self.items[0], &self.items[update_index]); - siftDown(self, 0); + if (self.compareFn(new_elem, old_elem)) { + siftUp(self, update_index); + } else { + siftDown(self, update_index); + } } pub const Iterator = struct { -- cgit v1.2.3 From 778bb4b324f4764386f55781d70e8167f1dd1abc Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Tue, 22 Sep 2020 03:50:28 -0700 Subject: return not found error correctly --- lib/std/priority_queue.zig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index 02188b5564..2769e7aa02 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -195,7 +195,7 @@ pub fn PriorityQueue(comptime T: type) type { } pub fn update(self: *Self, elem: T, new_elem: T) !void { - var update_index: usize = std.mem.indexOfScalar(T, self.items, elem) catch |error| return error.ElementNotFound; + var update_index: usize = std.mem.indexOfScalar(T, self.items, elem) orelse return error.ElementNotFound; assert (update_index >= 0 and update_index < self.items.len); const old_elem: T = self.items[update_index]; self.items[update_index] = new_elem; -- cgit v1.2.3 From 84406d98e4fd8032b544eba7b5f9d3ed78e67e6c Mon Sep 17 00:00:00 2001 From: Bhargav Srinivasan Date: Tue, 22 Sep 2020 05:12:21 -0700 Subject: removing redundant assert --- lib/std/priority_queue.zig | 1 - 1 file changed, 1 deletion(-) (limited to 'lib/std') diff --git a/lib/std/priority_queue.zig b/lib/std/priority_queue.zig index 2769e7aa02..f5ff4800e8 100644 --- a/lib/std/priority_queue.zig +++ b/lib/std/priority_queue.zig @@ -196,7 +196,6 @@ pub fn PriorityQueue(comptime T: type) type { pub fn update(self: *Self, elem: T, new_elem: T) !void { var update_index: usize = std.mem.indexOfScalar(T, self.items, elem) orelse return error.ElementNotFound; - assert (update_index >= 0 and update_index < self.items.len); const old_elem: T = self.items[update_index]; self.items[update_index] = new_elem; if (self.compareFn(new_elem, old_elem)) { -- cgit v1.2.3