Simple trie implementation

Brainstorming
,
1

Hi.

I’ve implemented very simple semi-generic trie.
It can hold arbitrary data, but alphabet size is fixed (256), hence semi-generic.
Currently I have only insert and search, deletion is not implemented yet.
Also there is some (almost useless) traversal over the entire trie.

Here it is

trie.zig 
const std = @import("std");
const Allocator = std.mem.Allocator;

pub fn Trie(comptime T: type) type {

    return struct {

        pub const Edge = struct {
            sym: u8,
            kid: *Node,
        };

        pub const Node = struct {
            data: T,
            edge: []Edge,
        };

        const Self = @This();
        root: Node,
        allo: Allocator,

        pub fn getNode(self: *Self, key: []const u8) ?*Node {
            var n: *Node = &self.root;
            for (key) |s| {
                const i = __edgeIndex(n, s) orelse return null;
                n = n.edge[i].kid;
            }
            return n;
        }

        pub fn addNode(self: *Self, key: []const u8) !*Node {
            var n = &self.root;
            for (key) |s| {
                var i: ?u8 = null;
                i = __edgeIndex(n, s);
                if (i == null) {
                    var new_node = try self.allo.create(Node);
                    new_node.edge.len = 0;
                    new_node.data = undefined;
                    i = @intCast(n.edge.len);
                    n.edge = try self.allo.realloc(n.edge, n.edge.len + 1);
                    n.edge[i.?] = .{.sym = s, .kid = new_node};
                }
                n = n.edge[i.?].kid;
            }
            return n;
        }

        pub fn walkOver(self: *Self, node: *Node) void {

            // depth first traversal
            std.debug.print(" at {*} ... {} kids\n", .{node, node.edge.len});

            for (node.edge) |e| {
                walkOver(self, e.kid);
            }

            // breadth first traversal (?)
            // std.debug.print(" at {*} ... {} kids\n", .{node, node.edge.len});
        }

        fn __edgeIndex(node: *Node, s: u8) ?u8 {
            var index: ?u8 = null;
            for (node.edge, 0..) |e, i| {
                if (e.sym == s) {
                    index = @intCast(i);
                    break;
                }
            }
            return index;
        }
    };
}
main.zig 
const std = @import("std");
const Allocator = std.mem.Allocator;

const Data = struct {
    a: u32,
    b: u32,
};

const SomeTrie = @import("trie.zig").Trie(Data);

pub fn main() !void {

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();

    const d: Data = .{.a = 5, .b = 7};
    var t: SomeTrie = .{
        .root = .{
            .data = d,
            .edge = undefined,
        },
        .allo = allocator,
    };

    std.debug.print("root {*} a = {} b = {}\n", .{&t.root, t.root.data.a, t.root.data.b});

    var n = t.getNode("123");
    std.debug.print("{*}\n", .{n});

    n = try t.addNode("123");
    n.?.data = d;

    n = t.getNode("1");
    std.debug.print("{*} a = {X} b = {X}\n", .{n, n.?.data.a, n.?.data.b});

    n = t.getNode("12");
    std.debug.print("{*}\n", .{n});

    n = t.getNode("123");
    std.debug.print("{*} a = {} b = {}\n", .{n, n.?.data.a, n.?.data.b});

    n = t.getNode("1234");
    std.debug.print("{*}\n", .{n});

    n = try t.addNode("124");
    n.?.data = .{.a = 333, .b = 444};
    n = t.getNode("124");
    std.debug.print("{*} a = {} b = {}\n", .{n, n.?.data.a, n.?.data.b});

    _ = try t.addNode("abc");
    n = t.getNode("a");
    std.debug.print("{*}\n", .{n});
    n = t.getNode("ab");
    std.debug.print("{*}\n", .{n});
    n = t.getNode("abc");
    std.debug.print("{*}\n", .{n});
    n = t.getNode("abcd");
    std.debug.print("{*}\n", .{n});

    n = try t.addNode(&[_]u8{0,1,2});
    n.?.data.a = 11;
    n.?.data.b = 22;
    n = t.getNode(&[_]u8{0,1,2});
    std.debug.print("{*} a = {} b = {}\n", .{n, n.?.data.a, n.?.data.b});

    t.walkOver(&t.root);
}

It works as expected, but I would like some comments on the code.
What is done good?
What is done bad/ugly?
Is it “ziggy” enough?

Thanks.

2

If you want to get better at Zig, next implement an iterator type over it, and add successor/predecessor queries (the second is more because it will force you to use pointers).

if you want to make the trie implementation better, implement level (merge multiple levels into a single level, it basically makes your branch table size at each level dynamic) and/or path compression (a path with multiple levels where just a single value is stored instead get stored a string of values in a single transition). Knuth called them Patricia trees, and there are a hundred permutations and options in the research.

If you want to take your data structure knowledge to the next level with something very similar but better performance, go look up van Emde Boas trees they are similar but have log( log( U )) operations where U is hte size of the universe of values.