@@ 0,0 1,331 @@
+//! This module contains iterators for use in while loops. Some
+//! iterators accept other iterators. Any struct that exposes a "next"
+//! method can be used with most of those, though some also require
+//! "reset".
+//!
+//! To use any iterator in this module, follow this pattern:
+//! var specialized = IterType(args).init();
+//! var iter = &specialized.iterator;
+//! while (iter.next()) |v| {
+//! // Do things with v.
+//! }
+//!
+//! Note that these iterators' next methods all change the state of the
+//! iterators themselves. They can't be const and they shouldn't be
+//! shared across threads.
+const std = @import("std");
+
+pub fn Iterator(comptime T: type) type {
+ return struct {
+ const Self = @This();
+ nextFn: fn (self: *Self) ?T,
+ resetFn: fn (self: *Self) void,
+ pub fn next(self: *Self) ?T {
+ return self.nextFn(self);
+ }
+ pub fn reset(self: *Self) void {
+ return self.resetFn(self);
+ }
+ };
+}
+
+/// Half-open range type. Call next() on it to get values out. Example
+/// usage:
+///
+/// var range = try Range(u32, 1).init(0, 10);
+/// var iter = &range.iterator;
+/// while (iter.next()) |n| {
+/// std.debug.warn("{}\n", .{n});
+/// }
+pub fn Range(comptime T: type, step: T) type {
+ // Some profiling results, as run on an i5-9600KF: This is
+ // consistently a good deal slower than
+ // u32 i = 0; while (i < limit) : (i += 1) {}
+ // debug: 2.27 times the run time
+ // release-fast, release-safe: 5 times the run time
+ // release-small: 6 times the run time
+ //
+ // This is mostly due to the iterator construct. When calling
+ // Range's next directly, the comparison becomes much more
+ // favorable with all release modes running slightly faster
+ // (around 0.1%) than the idiomatic while loop and Debug taking
+ // about 7/4 as long.
+ //
+ // Note: when this was written (June 2020), passing
+ // --single-threaded to a release-fast build slowed idiomatic
+ // loops down by about a factor of 2. These benchmarks should
+ // probably be re-run when the compiler is more stable.
+ return struct {
+ iterator: Iterator(T),
+ next_val: T,
+ start: T,
+ end: T,
+ const Self = @This();
+
+ /// Return the next element in the range, or null if the range
+ /// has been exhausted.
+ pub fn next(iterator: *Iterator(T)) ?T {
+ const self = @fieldParentPtr(Self, "iterator", iterator);
+ const rv = self.next_val;
+ if (step < 0) {
+ if (rv <= self.end) {
+ return null;
+ }
+ } else {
+ if (rv >= self.end) {
+ return null;
+ }
+ }
+
+ self.next_val += step;
+ return rv;
+ }
+
+ /// Reset the range back to its start.
+ pub fn reset(iterator: *Iterator(T)) void {
+ const self = @fieldParentPtr(Self, "iterator", iterator);
+ self.next_val = self.start;
+ }
+
+ /// Initialize. Returns error if step size is invalid.
+ pub fn init(start: T, end: T) !Self {
+ if (step == 0) {
+ return error.ZeroStepSize;
+ }
+ return Self{
+ .next_val = start,
+ .start = start,
+ .end = end,
+ .iterator = Iterator(T){
+ .nextFn = next,
+ .resetFn = reset,
+ },
+ };
+ }
+ };
+}
+
+/// Reverse a slice. Example usage:
+///
+/// const word: []const u8 = "Word";
+/// var drow = Reversed(u8).init(word);
+/// var iter = &drow.iterator;
+/// while (drow.next()) |c| {
+/// std.debug.warn("{}", .{c});
+/// std.debug.warn("\n", .{});
+pub fn Reversed(comptime T: type) type {
+ return struct {
+ const Self = @This();
+ idx: ?usize,
+ slice: []const T,
+
+ /// Initialize with slice to be reversed.
+ pub fn init(slice: []const T) Self {
+ return Self{ .idx = slice.len - 1, .slice = slice };
+ }
+
+ /// Reset the iterator state to what it was when initialized.
+ pub fn reset(self: *Self) void {
+ self.idx = self.slice.len - 1;
+ }
+
+ /// Return the previous element in the slice, or null if the whole
+ /// slice has been consumed.
+ pub fn next(self: *Self) ?T {
+ var rv: T = undefined;
+ if (self.idx) |i| {
+ if (i == 0) {
+ defer self.idx = null;
+ } else {
+ defer self.idx = self.idx.? - 1;
+ }
+ return self.slice[i];
+ } else {
+ return null;
+ }
+ }
+ };
+}
+
+/// Convert a slice of T to an iterator that can be used with the
+/// other iterators in this module.
+pub fn SliceIter(comptime T: type) type {
+ return struct {
+ const Self = @This();
+ idx = ?usize,
+ slice: []const T,
+
+ /// Initialize with a slice.
+ pub fn init(slice: []const T) Self {
+ return Self{ .idx = 0, .slice = slice };
+ }
+
+ /// Reset the iterator to the start.
+ pub fn reset(self: *Self) void {
+ self.idx = 0;
+ }
+
+ /// Return the next element in the slice, or null if the whole
+ /// slice has been consumed.
+ pub fn next(self: *Self) ?T {
+ if (idx) |i| {
+ if (i < self.slice.len) {
+ defer self.idx += 1;
+ } else {
+ defer self.idx = null;
+ }
+ return self.slice[i];
+ } else {
+ return null;
+ }
+ }
+ };
+}
+
+pub fn Product(comptime T: type) type {
+ return struct {
+ const Self = @This();
+ // This would be better as a tuple. Note for when we get tuple
+ // types.
+ const Result = struct { a: T, b: T };
+
+ iterator: Iterator(Result),
+ a: *Iterator(T),
+ b: *Iterator(T),
+ next_a: T,
+ next_b: T,
+ done: bool = false,
+
+ pub fn next(iterator: *Iterator(Result)) ?Result {
+ const self = @fieldParentPtr(Self, "iterator", iterator);
+ if (self.done)
+ return null;
+ const prev_a = self.next_a;
+ const prev_b = self.next_b;
+ if (self.a.next()) |aa| {
+ self.next_a = aa;
+ } else {
+ self.a.reset();
+ if (self.a.next()) |aa| {
+ self.next_a = aa;
+ } else {
+ // a iterator is empty.
+ return null;
+ }
+ if (self.b.next()) |bb| {
+ self.next_b = bb;
+ } else {
+ // b iterator has been exhausted; all done
+ self.done = true;
+ }
+ }
+ return Result{ .a = prev_a, .b = prev_b };
+ }
+
+ pub fn reset(iterator: *Iterator(Result)) void {
+ const self = @fieldParentPtr(Self, "iterator", iterator);
+ self.a.reset();
+ self.b.reset();
+ }
+
+ pub fn init(a: *Iterator(T), b: *Iterator(T)) Self {
+ const prev_a = a.next().?;
+ const prev_b = b.next().?;
+ return Self{
+ .a = a,
+ .b = b,
+ .next_a = prev_a,
+ .next_b = prev_b,
+ .iterator = Iterator(Result){
+ .nextFn = next,
+ .resetFn = reset,
+ },
+ };
+ }
+ };
+}
+
+const testing = std.testing;
+test "range ascend" {
+ var range = try Range(u32, 1).init(0, 10);
+ var iter = &range.iterator;
+ var correct: u32 = 0;
+ while (iter.next()) |n| {
+ testing.expectEqual(correct, n);
+ correct += 1;
+ }
+ testing.expectEqual(correct, 10);
+ testing.expectEqual(iter.next(), null);
+}
+
+test "range descend" {
+ var range = try Range(i32, -1).init(10, 0);
+ var iter = &range.iterator;
+ var correct: i32 = 10;
+ while (iter.next()) |n| {
+ testing.expectEqual(correct, n);
+ correct -= 1;
+ }
+ testing.expectEqual(correct, 0);
+ testing.expectEqual(iter.next(), null);
+}
+
+test "range skip" {
+ var range = try Range(u32, 2).init(0, 10);
+ var iter = &range.iterator;
+ var correct: u32 = 0;
+ while (iter.next()) |n| {
+ testing.expectEqual(correct, n);
+ correct += 2;
+ }
+ testing.expectEqual(correct, 10);
+ testing.expectEqual(iter.next(), null);
+}
+
+test "range runtime" {
+ var start: u32 = 0;
+ while (start < 10) : (start += 1) {
+ var range = try Range(u32, 1).init(start, 10);
+ var iter = &range.iterator;
+ var correct: u32 = start;
+ while (iter.next()) |n| {
+ testing.expectEqual(correct, n);
+ correct += 1;
+ }
+ testing.expectEqual(correct, 10);
+ testing.expectEqual(iter.next(), null);
+ }
+}
+
+test "reverse" {
+ const word: []const u8 = "This is some text.";
+ var backwards = Reversed(u8).init(word);
+ var idx: isize = word.len - 1;
+ while (backwards.next()) |letter| {
+ testing.expectEqual(word[@intCast(usize, idx)], letter);
+ idx -= 1;
+ }
+ testing.expectEqual(idx, -1);
+}
+
+test "product" {
+ const R = Range(u32, 1);
+ var a = try R.init(0, 10);
+ var b = try R.init(10, 20);
+ var product = Product(u32).init(&a.iterator, &b.iterator);
+ var pi = &product.iterator;
+
+ var correct_a: u32 = 0;
+ var correct_b: u32 = 10;
+ while (pi.next()) |ab| {
+ testing.expectEqual(ab.a, correct_a);
+ testing.expectEqual(ab.b, correct_b);
+ correct_a += 1;
+ if (correct_a == 10) {
+ correct_a = 0;
+ correct_b += 1;
+ }
+ }
+ testing.expectEqual(correct_b, 20);
+ testing.expectEqual(pi.next(), null);
+}
@@ 0,0 1,74 @@
+const std = @import("std");
+const iterators = @import("iterators.zig");
+
+const test_loops = 100_000;
+
+fn standardLoop() void {
+ var n: u64 = 0;
+
+ while (n < test_loops) : (n += 1) {
+ asm volatile (""
+ :
+ :
+ : "memory"
+ );
+ }
+}
+
+fn iterLoop() !void {
+ var range = try iterators.Range(u64, 1).init(0, test_loops);
+ var iter = &range.iterator;
+ while (iter.next()) |_| {
+ asm volatile (""
+ :
+ :
+ : "memory"
+ );
+ }
+}
+
+fn hackyFastLoop() !void {
+ const Range = iterators.Range(u64, 1);
+ var range = try Range.init(0, test_loops);
+ var iter = &range.iterator;
+ while (Range.next(iter)) |_| {
+ asm volatile (""
+ :
+ :
+ : "memory"
+ );
+ }
+}
+
+pub fn main() anyerror!void {
+ // Range comparison
+ var n: u64 = 0;
+ const start = std.time.nanoTimestamp();
+ while (n < test_loops) : (n += 1) {
+ standardLoop();
+ }
+ const end = std.time.nanoTimestamp();
+ const stdout = std.io.getStdOut().writer();
+ try stdout.print("Normal Zig-style: {}ns\n", .{(end - start)});
+
+ n = 0;
+ const iterstart = std.time.nanoTimestamp();
+ var range = try iterators.Range(u64, 1).init(0, test_loops);
+ var iter = &range.iterator;
+ while (iter.next()) |_| {
+ try iterLoop();
+ }
+ const iterend = std.time.nanoTimestamp();
+ try stdout.print("Iterator-style: {}ns\n", .{(iterend - iterstart)});
+
+ n = 0;
+ const hackystart = std.time.nanoTimestamp();
+ const Range = iterators.Range(u64, 1);
+ range = try Range.init(0, test_loops);
+ iter = &range.iterator;
+ while (Range.next(iter)) |_| {
+ try hackyFastLoop();
+ }
+ const hackyend = std.time.nanoTimestamp();
+ try stdout.print("Hacky fast-style: {}ns\n", .{(hackyend - hackystart)});
+}