%?- gtrace, bitrev([a,b], L).

%?- bitrev(Ls, Ps).

%?- bitrev([a,b], L).
%@ L = [a, b] ;
%@ No

%?- bitrev([a,b,c,d], L).
%@ L = [a, c, b, d] ;
%@ No

%?- bitrev(L, [1,2,3,4,5,6,7,8]).
%@ L = [1, 5, 3, 7, 2, 6, 4, 8] ;
%@ No

%?- bitrev([a], Out).


length_power_two([_], bin(zero,nil)).
length_power_two(Ls, bin(zero,Bin)) :-
        Ls = [_|_],
        length(Ls, _),
        append(Front, Back, Ls),
        same_length(Front, Back),
        length_power_two(Front, Bin).

same_length([], []).
same_length([_|Rs1], [_|Rs2]) :- same_length(Rs1, Rs2).

%?- length_power_two(Ls, L).

bitrev([], []).  % ? (according to example queries)
bitrev(Ls, Ps) :-
        same_length(Ls, Ps),
        length_power_two(Ls, Bs),
        bitrev_check(Ls, Bs, Bs, Ps).

bitrev_check([], _, _, _).
bitrev_check([L|Ls], Pos0, Bs, Ps) :-
        Pos0 = bin(_,Pos00),
        bitrev_reverse(Pos00, RPos0),
        Bs = bin(_,Bs0),
        position_in_list_is(Bs0, RPos0, Ps, L),
        bitrev_succ(Pos0, Pos1),
        bitrev_check(Ls, Pos1, Bs, Ps).

position_in_list_is(Pos, Pos, [L|_], L).
position_in_list_is(Pos0, Pos, [_|Ls], L) :-
        dif(Pos0, Pos),
        bitrev_succ(Pos0, Pos1),
        position_in_list_is(Pos1, Pos, Ls, L).

bitrev_reverse(B, R) :- bitrev_reverse(B, nil, R).

bitrev_reverse(nil, Acc, Acc).
bitrev_reverse(bin(Elem,Bin), Acc0, Rev) :-
        bitrev_reverse(Bin, bin(Elem,Acc0), Rev).

bitrev_succ(B, S) :-
        bitrev_reverse(B, R),
        bitrev_succ_(R, SR),
        bitrev_reverse(SR, S).

bitrev_succ_(bin(B0,Bin0), bin(B,Bin)) :-
        switch_on_carry(B0, Bin0, B, Bin).

switch_on_carry(zero, Bin0, one, Bin0).
switch_on_carry(one, Bin0, zero, Bin) :- bitrev_succ_(Bin0, Bin).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Testing:

%?- loop(N).

% first_position_binary(Ls, Bs) :- first_position_binary(Ls, nil, Bs).

% first_position_binary([], Bs, Bs).
% first_position_binary([_|Rest], Bs0, Bs) :-
%         Bs1 = bin(zero,Bs0),
%         first_position_binary(Rest, Bs1, Bs).

% loop(N) :-
%         length(Ls, N),
%         first_position_binary(Ls, Bs),
%         format("binary: ~w\n", [Bs]),
%         ignore(all_successors(Bs)).

% all_successors(Bs) :-
%         bitrev_succ(Bs, Succ),
%         format("  successor: ~w\n", [Succ]),
%         all_successors(Succ).

%?- length(Ls, _), first_position_binary(Ls, zero, Bs).

%?- length(Ls, _).

%?- first_position_binary([a,a,a], nil, Bs).