const std = @import( "std" );
const Allocator = std.mem.Allocator;
const print = std.debug.print;
const Stack = std.ArrayList( u8 );

pub fn main() !void {
    // std.debug.print( "hello world\n", .{} );
    
    var gpa = std.heap.GeneralPurposeAllocator( .{} ) {};
    defer { _ = gpa.deinit(); }
    const all = gpa.allocator();
    
    var out = std.ArrayList( u8 ) {};
    defer { out.deinit( all ); }
    var ow = out.writer( all );
    defer {
        std.fs.File.stdout().writeAll( out.items ) catch |e| {
            print( "error {s}\n", .{ @errorName( e ) } );
        };
    }
    
    // {
    //     print( "alpha\n", .{} );
    //     var la = Stack {};
    //     var lb = Stack {};
    //     var lc = Stack {};
    //     const towers = [3]*Stack { &la, &lb, &lc };
    //     try towers[0].append( all, 'a' );
    //     defer {
    //         for( towers ) |tower| { tower.deinit( all ); }
    //     }
    //     print( " before: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
    //     try hanoi( all, &towers );
    //     print( "  after: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
    // }
    // {
    //     print( "beta\n", .{} );
    //     var la = Stack {};
    //     var lb = Stack {};
    //     var lc = Stack {};
    //     const towers = [3]*Stack { &la, &lb, &lc };
    //     try towers[0].append( all, 'a' );
    //     try towers[0].append( all, 'b' );
    //     defer {
    //         for( towers ) |tower| { tower.deinit( all ); }
    //     }
    //     print( " before: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
    //     try hanoi( all, &towers );
    //     print( "  after: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
    // }
    {
        try ow.print( "omega no interface\n", .{} );
        var la = Stack {};
        var lb = Stack {};
        var lc = Stack {};
        const towers = [3]*Stack { &la, &lb, &lc };
        for( 'a'..'f'+1 ) |c| {
            try towers[0].append( all, @intCast( c ) );
        }
        defer {
            for( towers ) |tower| { tower.deinit( all ); }
        }
        try ow.print( " before: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
        try hanoi( all, &towers );
        try ow.print( "  after: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
    }
    {
        try ow.print( "omega implicit interface\n", .{} );
        var la = Stack {};
        var lb = Stack {};
        var lc = Stack {};
        const towers = [3]*Stack { &la, &lb, &lc };
        for( 'a'..'f'+1 ) |c| {
            try towers[0].append( all, @intCast( c ) );
        }
        defer {
            for( towers ) |tower| { tower.deinit( all ); }
        }
        try ow.print( " before: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
        try hanoi2( all, &towers );
        try ow.print( "  after: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
    }
    {
        try ow.print( "omega explicit interface\n", .{} );
        var la = Stack {};
        var lb = Stack {};
        var lc = Stack {};
        const towers = [3]*Stack { &la, &lb, &lc };
        for( 'a'..'f'+1 ) |c| {
            try towers[0].append( all, @intCast( c ) );
        }
        defer {
            for( towers ) |tower| { tower.deinit( all ); }
        }
        try ow.print( " before: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
        const trait = StackTrait( Stack ) {
            .push  = simplePush ,
            .pop   = simplePop  ,
            .size  = simpleSize ,
        };
        try hanoi3( all, &towers, trait );
        try ow.print( "  after: {}{}{}\n", .{ towers[0], towers[1], towers[2] } );
    }
}



// simple hanoi example

fn hanoi( all :Allocator, towers :*const [3]*Stack ) !void {
    try hanoi_helper( all, towers, towers[0].items.len );
}
// transfer `i` values from `towers[0]` to `towers[2]`
fn hanoi_helper( all :Allocator, towers :*const [3]*Stack, i :usize ) !void {
    if( i == 0 ) { return; }
    // print( "(", .{} );
    try hanoi_helper( all, &.{ towers[0], towers[2], towers[1] }, i-1 );
    // print( "<", .{} );
    try towers[2].append( all, towers[0].pop() orelse @panic( "empty list" ) );
    // print( ">", .{} );
    try hanoi_helper( all, &.{ towers[1], towers[0], towers[2] }, i-1 );
    // print( ")", .{} );
}



// defacto zig "interface"

fn hanoi2( all :Allocator, towers :anytype ) !void {
    try hanoi2_helper( all, towers, towers[0].items.len );
}
fn hanoi2_helper( all :Allocator, towers :anytype, i :usize ) !void {
    if( i == 0 ) { return; }
    try hanoi2_helper( all, &.{ towers[0], towers[2], towers[1] }, i-1 );
    const val = towers[0].pop() orelse @panic( "empty list" );
    try towers[2].append( all, val );
    try hanoi2_helper( all, &.{ towers[1], towers[0], towers[2] }, i-1 );
}



// proper zig interface

fn StackTrait( StackT :type ) type { // TODO parameterize StackT Element (u8)
    return struct {
        size  :*const fn( *const StackT ) usize,
        push  :*const fn( *StackT, Allocator, u8 ) anyerror!void, // TODO parameterized error
        pop   :*const fn( *StackT ) u8,
    };
}

fn hanoi3( all :Allocator, towers :anytype, comptime trait :StackTrait( @TypeOf( towers.*[0].* ) ) ) !void {
    const size = trait.size( towers.*[0] );
    try hanoi3_helper( all, towers, trait, size );
}
fn hanoi3_helper( all :Allocator, towers :anytype, comptime trait :StackTrait( @TypeOf( towers.*[0].* ) ), i :usize ) !void {
    if( i == 0 ) { return; }
    var towersA = .{ towers[0], towers[2], towers[1] };
    try hanoi3_helper( all, &towersA, trait, i-1 );
    const val = trait.pop( towers.*[0] );
    try trait.push( towers[2], all, val );
    var towersB = .{ towers[1], towers[0], towers[2] };
    try hanoi3_helper( all, &towersB, trait, i-1 );
}

const simplePush = Stack.append;
fn simplePop( stack :*Stack ) u8 {
    return stack.pop() orelse @panic( "empty stack" );
}
fn simpleSize( stack :*const Stack ) usize {
    return stack.items.len;
}



// pan interface

// var hanoi3 = fn<Stack>(
//     all :Allocator,
//     towers :*[3]*mut Stack,
//     #trait :StackTrait( Stack ),
// ) :!void {
//     var size = trait.size( towers.*[0] );
//     try hanoi3_helper( all, towers, trait, size );
// };
// var hanoi3_helper = fn<Stack>(
//     all :Allocator,
//     towers :*[3]*mut Stack,
//     #trait :StackTrait( Stack ),
//     i :usize,
// ) :!void {
//     if( i == 0 ) { return; }
//     var towersA = .{ towers[0], towers[2], towers[1] };
//     try hanoi3_helper( all, &towersA, trait, i-1 );
//     try trait.push( towers[2], all, trait.pop( towers[0] ) );
//     var towersB = .{ towers[1], towers[0], towers[2] };
//     try hanoi3_helper( all, &towersB, trait, i-1 );
// };