このディレクトリの索引

#  @ideoneさん 2012/03/12 のtwitterより
#  
#  test:-disp(6,[12,15,4,10,2,18,7,14,21,5],[7,8,10,5,-1,1,-1,6,-1,-1],[3,-1,-1,9,-1,4,-1,2,-1,-1],[]).
#   
#  disp(Index,Key,Left,Right,Stack):-
#      find(Key,Index,K),
#      write(K),write(' '),
#      find(Right,Index,R),
#      stackin(Stack,R,Stacktmp),
#      find(Left,Index,L),
#      stackin(Stacktmp,L,Newstack),
#      cal(Key,Left,Right,Newstack).
#   
#  cal(Key,Left,Right,[]).
#  cal(Key,Left,Right,[X|Z]):-
#      disp(X,Key,Left,Right,Z).
#   
#  stackin(Stack,-1,Stack).
#  stackin(Stack,V,Newstack):-push(Stack,V,Newstack).
#   
#  find([X|A],1,X).
#  find([X|A],V,Z):-W is V-1, find(A,W,Z).
#   
#  push(A,X,[X|A]).
#   
#  pop([X|A],X,A).
#  

test :-
        disp(6,[12,15,4,10,2,18,7,14,21,5],[7,8,10,5,-1,1,-1,6,-1,-1],[3,-1,-1,9,-1,4,-1,2,-1,-1],[]).
 
disp(Index,Key,Left,Right,Stack) :-
        disp([Index|Stack],Key,Left,Right).

disp([],_,_,_).
disp([Index|Stack_1],Key,Left,Right):-
        disp_Key(Index,Key),
        stackin(Index,Left,Right,Stack_1,Stack_2),
        disp(Stack_2,Key,Left,Right).

disp_Key(Index,Key) :-
        nth1(Index,Key,K),
        writef('%t ',[K]).

stackin(Index,Left,Right,Stack_1,Stack_2) :-
        find(Left,Index,V_1),
        stackin(Stack_1,V_1,Stack_3),
        find(Right,Index,V_2),
        stackin(Stack_3,V_2,Stack_2).

stackin(Stack,-1,Stack).
stackin(Stack,V,Newstack) :-
        push(Stack,V,Newstack).
 
find([X|A],1,X) :- !.
find([X|A],V,Z) :-
        W is V-1,
        find(A,W,Z).
find([],_,-1).

push(A,X,[X|A]).