%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%       Index handling primitives                                       %
%               reference: Data Structures and Algorithms (5.4)         %
%                               Aho, A.V., Hopcroft, J.E., Ullman, J.D. %
%                               1983, Addison-Wesley                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

/******************************************************************************
            Records of index file has only one field, containing term of the
        following forms.
            First of all, thre must be global information at first record.
                record1         : r(Level,Root,DeleteChain)
                        Level: level of tree
                        Root: record position of root node
                        DeleteChain: head of deleted records chain
            Internal node has either of following forms.
                node            : n(Key1,Child1,Child2)
                                | n(Key1,Key2,Child1,Child2,Chil3)
            Leaf of the tree has the following form.
                leaf            : l(Key,Rec,Link,Last)
                                | l
            The second form is for exceptional leaf placed at leftmost of tree
        to avoid insertion of minimal element.
            Link and Last above points to the record of followinf form.
                overflow        : o(Rec,Next)
******************************************************************************/

:- public ndx_get_rec/3.
:- mode ndx_get_rec(+,+,-).
:- extern ndx_getnode/4.

ndx_get_rec(NDX,Key,Rec) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),
        ndx_search_root(NDX,Key,Level,Root,Leaf),
        ndx_getrecs(NDX,Leaf,Rec).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- mode ndx_search_root(+,+,+,+,-).
:- mode ndx_search_child(+,+,+,+,-).
:- mode ndx_search_node(+,+,+,+,+,+,-).
:- mode ndx_search_leaf(+,+,+,+,+,-).
:- mode ndx_search_node(+,+,+,+,+,+,+,+,-).
:- mode ndx_search_leaf(+,+,+,+,+,+,+,-).

ndx_serach_root(_,_,0,_,_) :- !,fail.
ndx_search_root(NDX,Key,Level,Root,Leaf) :- ndx_getnode(NDX,Level,Root,Node),
        ndx_search_child(NDX,Key,Level,Node,Leaf).

ndx_search_child(NDX,Key,Level,n(Key1,Child1,Child2),Leaf) :- !,
        L is Level-1,
        ndx_search_node(NDX,Key,L,Key1,Child1,Child2,Leaf).
ndx_search_child(NDX,Key,Level,n(Key1,Key2,Child1,Child2,Child3),Leaf) :-
        L is Level-1,
        ndx_search_node(NDX,Key,L,Key1,Key2,Child1,Child2,Child3,Leaf).

ndx_search_node(NDX,Key,0,Key1,Child1,Child2,Leaf) :- !,
        ndx_search_leaf(NDX,Key,Key1,Child1,Child2,Leaf).
ndx_search_node(NDX,Key,Level,Key1,Child1,_,Leaf) :-
        Key @< Key1,!,ndx_getnode(NDX,Level,Child1,Node),
        ndx_search_child(NDX,Key,Level,Node,Leaf).
ndx_search_node(NDX,Key,Level,_,_,Child2,Leaf) :-
        ndx_getnode(NDX,Level,Child2,Node),
        ndx_search_child(NDX,Key,Level,Node,Leaf).

ndx_search_leaf(NDX,Key,Key1,Child1,_,Child1) :- Key @< Key1,!,
        ndx_getnode(NDX,0,Child1,l(Key,Rec,Link,Last)).
ndx_search_leaf(NDX,Key,_,_,Child2,Child2) :-
        ndx_getnode(NDX,0,Child2,l(Key,Rec,Link,Last)).

ndx_search_node(NDX,Key,0,Key1,Key2,Child1,Child2,Child3,Leaf) :- !,
        ndx_search_leaf(NDX,Key,Key1,Key2,Child1,Child2,Child3,Leaf).
ndx_search_node(NDX,Key,Level,Key1,_,Child1,_,_,Leaf) :-
        Key @< Key1,!,ndx_getnode(NDX,Level,Child1,Node),
        ndx_search_child(NDX,Key,Level,Node,Leaf).
ndx_search_node(NDX,Key,Level,_,Key2,_,Child2,_,Leaf) :-
        Key @< Key2,!,ndx_getnode(NDX,Level,Child2,Node),
        ndx_search_child(NDX,Key,Level,Node,Leaf).
ndx_search_node(NDX,Key,Level,_,_,_,_,Child3,Leaf) :-
        ndx_getnode(NDX,Level,Child3,Node),
        ndx_search_child(NDX,Key,Level,Node,Leaf).

ndx_search_leaf(NDX,Key,Key1,_,Child1,_,_,Child1) :- Key @< Key1,!,
        ndx_getnode(NDX,0,Child1,l(Key,Rec,Link,Last)).
ndx_search_leaf(NDX,Key,_,Key2,_,Child2,_,Child2) :- Key @< Key2,!,
        ndx_getnode(NDX,0,Child2,l(Key,Rec,Link,Last)).
ndx_search_leaf(NDX,Key,_,_,_,_,Child3,Child3) :-
        ndx_getnode(NDX,0,Child3,l(Key,Rec,Link,Last)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- mode ndx_getrecs(+,+,-).
:- mode ndx_getovfp(+,+,-).

ndx_getrecs(NDX,Leaf,Rec) :- ndx_getnode(NDX,0,Leaf,l(Key,Rec,Link,Last)).
ndx_getrecs(NDX,Leaf,Rec) :- ndx_getnode(NDX,0,Leaf,l(Key,Rec0,Link,Last)),
        ndx_getovfp(NDX,Link,Rec).

ndx_getovfp(_,0,_) :- !,fail.
ndx_getovfp(NDX,Link,Rec) :- ndx_getnode(NDX,0,Link,o(Rec,Next)).
ndx_getovfp(NDX,Link,Rec) :- ndx_getnode(NDX,0,Link,o(Rec0,Next)),
        ndx_getovfp(NDX,Next,Rec).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- mode ndx_add_root(+,+,+,+,+).
:- mode ndx_newroot(+,+,+,+,+).
:- mode ndx_add_child(+,+,+,+,+,+,+,-,-).
:- mode ndx_add_node(+,+,+,+,+,+,+,+).
:- mode ndx_fillnode1(+,+,+,+,+,+,+,+).
:- mode ndx_fillnode2(+,+,+,+,+,+,+,+).
:- mode ndx_add_leaf(+,+,+,+,+,+,+).
:- mode ndx_addleaf1(+,+,+,+,+,+,+).
:- mode ndx_add_node(+,+,+,+,+,+,+,+,+,+,+,-,-).
:- mode ndx_divnode1(+,+,+,+,+,+,+,+,+,-).
:- mode ndx_divnode2(+,+,+,+,+,+,+,+,+,-).
:- mode ndx_divnode3(+,+,+,+,+,+,+,+,+,-).
:- mode ndx_add_leaf(+,+,+,+,+,+,+,+,+,+,-,-).
:- mode ndx_addleaf1(+,+,+,+,+,+,+,+,+,-).
:- mode ndx_newleaf(+,+,+,-).
:- mode ndx_newovfp(+,+,+).
:- mode ndx_newovfp1(+,+,+,+).


:- public ndx_add/3.
:- mode ndx_add(+,+,+).

ndx_add(NDX,Key,Rec) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),
        ndx_add_root(NDX,Key,Rec,Level,Root).

ndx_add_root(NDX,Key,Rec,0,Leaf) :- !,
        ndx_allocnode(NDX,2),ndx_newleaf(NDX,Key,Rec,NewL),
        ndx_newroot(NDX,Leaf,NewL,Key,0).
ndx_add_root(NDX,Key,Rec,Level,Root) :- ndx_getnode(NDX,Level,Root,Node),
        ndx_add_child(NDX,Key,Rec,Level,Root,Node,1,NewN,NewK),
        ndx_newroot(NDX,Root,NewN,NewK,Level).

ndx_newroot(_,_,0,_,_) :- !.
ndx_newroot(NDX,Old,New,Key,Level) :- L is Level+1,
        ndx_newnode(NDX,NewR),ndx_putnode(NDX,L,NewR,n(Key,Old,New)),
        ndx_getnode(NDX,-1,0,r(Level0,Root,Delete)),
        ndx_putnode(NDX,-1,0,r(L,NewR,Delete)).

ndx_add_child(NDX,Key,Rec,Level,Node,n(Key1,Child1,Child2),_,0,_) :- !,
        L is Level-1,
        ndx_add_node(NDX,Key,Rec,L,Node,Key1,Child1,Child2).
ndx_add_child(NDX,Key,Rec,Level,Node,n(Key1,Key2,Child1,Child2,Child3),More,NewN,NewK) :-
        L is Level-1,M is More+1,
        ndx_add_node(NDX,Key,Rec,L,Node,Key1,Key2,Child1,Child2,Child3,M,NewN,NewK).

ndx_add_node(NDX,Key,Rec,0,Node,Key1,Child1,Child2) :- !,
        ndx_add_leaf(NDX,Key,Rec,Node,Key1,Child1,Child2).
ndx_add_node(NDX,Key,Rec,Level,Node,Key1,Child1,Child2) :-
        Key @< Key1,!,ndx_getnode(NDX,Level,Child1,ChNode),
        ndx_add_child(NDX,Key,Rec,Level,Child1,ChNode,0,NewN,NewK),
        ndx_fillnode1(NDX,Level,Node,Key1,Child1,Child2,NewN,NewK).
ndx_add_node(NDX,Key,Rec,Level,Node,Key1,Child1,Child2) :-
        ndx_getnode(NDX,Level,Child2,ChNode),
        ndx_add_child(NDX,Key,Rec,Level,Child2,ChNode,0,NewN,NewK),
        ndx_fillnode2(NDX,Level,Node,Key1,Child1,Child2,NewN,NewK).

ndx_fillnode1(_,_,_,_,_,_,0,_) :- !.
ndx_fillnode1(NDX,Level,Node,Key1,Child1,Child2,NewN,NewK) :-
        L is Level+1,ndx_putnode(NDX,L,Node,n(NewK,Key1,Child1,NewN,Child2)).

ndx_fillnode2(_,_,_,_,_,_,0,_) :- !.
ndx_fillnode2(NDX,Level,Node,Key1,Child1,Child2,NewN,NewK) :-
        L is Level+1,ndx_putnode(NDX,L,Node,n(Key1,NewK,Child1,Child2,NewN)).

ndx_add_leaf(NDX,Key,Rec,Node,Key1,Child1,Child2) :-
        Key @< Key1,!,ndx_addleaf1(NDX,Key,Rec,Node,Key1,Child1,Child2).
ndx_add_leaf(NDX,Key,Rec,_,Key,_,Child2) :- !,
        ndx_newovfp(NDX,Child2,Rec).
ndx_add_leaf(NDX,Key,Rec,Node,Key1,Child1,Child2) :-
        ndx_allocnode(NDX,1),ndx_newleaf(NDX,Key,Rec,NewL),
        ndx_putnode(NDX,1,Node,n(Key1,Key,Child1,Child2,NewL)).

ndx_addleaf1(NDX,Key,Rec,_,_,Child1,_) :-
        ndx_getnode(NDX,0,Child1,l(Key,Rec0,Link,Last)),!,
        ndx_newovfp(NDX,Child1,Rec).
ndx_addleaf1(NDX,Key,Rec,Node,Key1,Child1,Child2) :-
        ndx_allocnode(NDX,1),ndx_newleaf(NDX,Key,Rec,NewL),
        ndx_putnode(NDX,1,Node,n(Key,Key1,Child1,NewL,Child2)).

ndx_add_node(NDX,Key,Rec,0,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,NewK) :- !,
        ndx_add_leaf(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,NewK).
ndx_add_node(NDX,Key,Rec,Level,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,Key1) :-
        Key @< Key1,!,ndx_getnode(NDX,Level,Child1,ChNode),
        ndx_add_child(NDX,Key,Rec,Level,Child1,ChNode,More,NN,NK),
        ndx_divnode1(NDX,Level,Node,Key2,Child1,Child2,Child3,NN,NK,NewN).
ndx_add_node(NDX,Key,Rec,Level,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,NK) :-
        Key @< Key2,!,ndx_getnode(NDX,Level,Child2,ChNode),
        ndx_add_child(NDX,Key,Rec,Level,Child2,ChNode,More,NN,NK),
        ndx_divnode2(NDX,Level,Node,Key1,Key2,Child1,Child2,Child3,NN,NewN).
ndx_add_node(NDX,Key,Rec,Level,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,Key2) :-
        ndx_getnode(NDX,Level,Child3,ChNode),
        ndx_add_child(NDX,Key,Rec,Level,Child3,ChNode,More,NN,NK),
        ndx_divnode3(NDX,Level,Node,Key1,Child1,Child2,Child3,NN,NK,NewN).

ndx_divnode1(_,_,_,_,_,_,_,0,_,0) :- !.
ndx_divnode1(NDX,Level,Node,Key2,Child1,Child2,Child3,NN,NK,NewN) :-
        L is Level+1,ndx_putnode(NDX,L,Node,n(NK,Child1,NN)),
        ndx_newnode(NDX,NewN),ndx_putnode(NDX,L,NewN,n(Key2,Child2,Child3)).

ndx_divnode2(_,_,_,_,_,_,_,_,0,0) :- !.
ndx_divnode2(NDX,Level,Node,Key1,Key2,Child1,Child2,Child3,NN,NewN) :-
        L is Level+1,ndx_putnode(NDX,L,Node,n(Key1,Child1,Child2)),
        ndx_newnode(NDX,NewN),ndx_putnode(NDX,L,NewN,n(Key2,NN,Child3)).

ndx_divnode3(_,_,_,_,_,_,_,0,_,0) :- !.
ndx_divnode3(NDX,Level,Node,Key1,Child1,Child2,Child3,NN,NK,NewN) :-
        L is Level+1,ndx_putnode(NDX,L,Node,n(Key1,Child1,Child2)),
        ndx_newnode(NDX,NewN),ndx_putnode(NDX,L,NewN,n(NK,Child3,NN)).

ndx_add_leaf(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,Key1) :-
        Key @< Key1,!,ndx_addleaf1(NDX,Key,Rec,Node,Key2,Child1,Child2,Child3,More,NewN).
ndx_add_leaf(NDX,Key,Rec,_,Key,_,_,Child2,_,_,0,_) :- !,
        ndx_newovfp(NDX,Child2,Rec).
ndx_add_leaf(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,Key) :-
        Key @< Key2,!,M is More+1,
        ndx_allocnode(NDX,M),ndx_newleaf(NDX,Key,Rec,NewL),
        ndx_putnode(NDX,1,Node,n(Key1,Child1,Child2)),
        ndx_newnode(NDX,NewN),ndx_putnode(NDX,1,NewN,n(Key2,NewL,Child3)).
ndx_add_leaf(NDX,Key,Rec,_,_,Key,_,_,Child3,_,0,_) :- !,
        ndx_newovfp(NDX,Child3,Rec).
ndx_add_leaf(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,More,NewN,Key2) :-
        M is More+1,ndx_allocnode(NDX,M),ndx_newleaf(NDX,Key,Rec,NewL),
        ndx_putnode(NDX,1,Node,n(Key1,Child1,Child2)),
        ndx_newnode(NDX,NewN),ndx_putnode(NDX,1,NewN,n(Key,Child3,NewL)).

ndx_addleaf1(NDX,Key,Rec,_,_,Child1,_,_,_,0) :-
        ndx_getnode(NDX,0,Child1,l(Key,Rec0,Link,Last)),!,
        ndx_newovfp(NDX,Child1,Rec).
ndx_addleaf1(NDX,Key,Rec,Node,Key2,Child1,Child2,Child3,More,NewN) :-
        M is More+1,ndx_allocnode(NDX,M),ndx_newleaf(NDX,Key,Rec,NewL),
        ndx_putnode(NDX,1,Node,n(Key,Child1,NewL)),
        ndx_newnode(NDX,NewN),ndx_putnode(NDX,1,NewN,n(Key2,Child2,Child3)).

ndx_newleaf(NDX,Key,Rec,Leaf) :-
        ndx_newnode(NDX,Leaf),ndx_putnode(NDX,0,Leaf,l(Key,Rec,0,0)).

ndx_newovfp(NDX,Leaf,Rec) :-
        ndx_getnode(NDX,0,Leaf,L),ndx_newovfp1(NDX,Leaf,L,Rec).

ndx_newovfp1(NDX,Leaf,l(Key,Rec0,0,_),Rec) :- !,
        ndx_allocnode(NDX,1),ndx_newnode(NDX,OV),
        ndx_putnode(NDX,0,Leaf,l(Key,Rec0,OV,OV)),
        ndx_putnode(NDX,0,OV,o(Rec,0)).
ndx_newovfp1(NDX,Leaf,l(Key,Rec0,Link0,Last),Rec) :-
        ndx_allocnode(NDX,1),ndx_newnode(NDX,OV),
        ndx_putnode(NDX,0,Leaf,l(Key,Rec0,Link0,OV)),
        ndx_getnode(NDX,0,Last,o(Rec1,Next)),ndx_putnode(NDX,0,Last,o(Rec1,OV)),        ndx_putnode(NDX,0,OV,o(Rec,0)).




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%  モジュール　%%%  モジュール　%%%  モジュール　%%%  モジュール　%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- module index2.

:- public ndx_delete/3.
:- mode ndx_delete(+,+,+).

ndx_delete(NDX,Key,Rec) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),
        ndx_delete_root(NDX,Key,Rec,Level,Root).



:- mode ndx_delete_root(+,+,+,+,+).
:- mode ndx_freeroot(+,+,+).
:- mode ndx_delete_child(+,+,+,+,+,+,-,+).
:- mode ndx_delete_node(+,+,+,+,+,+,+,+,-,+).
:- mode ndx_delnode1(+,+,+,+,+,+,-).
:- mode ndx_delnode1(+,+,+,+,+,+,+,-).
:- mode ndx_delnode2(+,+,+,+,-).
:- mode ndx_delnode2(+,+,+,+,+,+,+,-).
:- mode ndx_delete_leaf(+,+,+,+,+,+,+,-,+).
:- mode ndx_delleaf1(+,+,+,+,+,+,+,-,+,+).
:- mode ndx_delleaf2(+,+,+,+,+,-,+).
:- mode ndx_trim_node(+,+,+,+,+,+,+,+,+,+,+).
:- mode ndx_trimnode1(+,+,+,+,+,+,+,+).
:- mode ndx_trimnode1(+,+,+,+,+,+,+,+,+).
:- mode ndx_trimnode2(+,+,+,+).
:- mode ndx_trimnode2(+,+,+,+,+,+,+,+,+).
:- mode ndx_trimnode3(+,+,+,+).
:- mode ndx_trimnode3(+,+,+,+,+,+,+,+,+).
:- mode ndx_trim_leaf(+,+,+,+,+,+,+,+,+,+).
:- mode ndx_trimleaf1(+,+,+,+,+,+,+,+,+,+,+).
:- mode ndx_trimleaf2(+,+,+,+,+,+,+,+).
:- mode ndx_trimleaf3(+,+,+,+,+,+,+,+).
:- mode ndx_delovfp(+,+,+,+,+,+,+).
:- mode ndx_delovfp(+,+,+,+,+,+,+,+).
:- mode ndx_delovfp(+,+,+,+,+,+,+,+,+,+,+).
:- mode ndx_changekey(+,+,+).

ndx_delete_root(_,_,_,0,_) :- !,fail.
ndx_delete_root(NDX,Key,Rec,Level,Root) :- ndx_getnode(NDX,Level,Root,Node),
        ndx_delete_child(NDX,Key,Rec,Level,Root,Node,UniN,_),
        ndx_freeroot(NDX,UniN,Level).

ndx_freeroot(_,0,_) :- !.
ndx_freeroot(NDX,Uni,Level) :- L is Level-1,
        ndx_getnode(NDX,-1,0,r(Level0,Root,Delete)),
        ndx_putnode(NDX,-1,0,r(L,Uni,Delete)).

ndx_delete_child(NDX,Key,Rec,Level,Node,n(Key1,Child1,Child2),UniN,UniK) :- !,
        L is Level-1,
        ndx_delete_node(NDX,Key,Rec,L,Node,Key1,Child1,Child2,UniN,UniK).
ndx_delete_child(NDX,Key,Rec,Level,Node,n(Key1,Key2,Child1,Child2,Child3),0,UniK) :-
        L is Level-1,
        ndx_trim_node(NDX,Key,Rec,L,Node,Key1,Key2,Child1,Child2,Child3,UniK).

ndx_delete_node(NDX,Key,Rec,0,Node,Key1,Child1,Child2,UniN,UniK) :- !,
        ndx_delete_leaf(NDX,Key,Rec,Node,Key1,Child1,Child2,UniN,UniK).
ndx_delete_node(NDX,Key,Rec,Level,Node,Key1,Child1,Child2,UniN,UniK) :-
        Key @< Key1,!,ndx_getnode(NDX,Level,Child1,ChNode),
        ndx_delete_child(NDX,Key,Rec,Level,Child1,ChNode,UN,UniK),
        ndx_delnode1(NDX,Level,Node,Key1,Child2,UN,UniN).
ndx_delete_node(NDX,Key,Rec,Level,Node,_,_,Child2,UniN,_) :-
        ndx_getnode(NDX,Level,Child2,ChNode),
        ndx_delete_child(NDX,Key,Rec,Level,Child2,ChNode,UN,Node/Level),
        ndx_delnode2(NDX,Level,Node,UN,UniN).

ndx_delnode1(_,_,_,_,_,0,0) :- !.
ndx_delnode1(NDX,Level,Node,Key1,Child2,UN,UniN) :-
        ndx_getnode(NDX,Level,Child2,SNode),
        ndx_delnode1(NDX,Level,Node,Key1,Child2,SNode,UN,UniN).

ndx_delnode1(NDX,Level,Node,Key1,Child2,n(Sk1,Sc1,Sc2),UN,Child2) :- !,
        ndx_freenode(NDX,Node),
        ndx_putnode(NDX,Level,Child2,n(Key1,Sk1,UN,Sc1,Sc2)).
ndx_delnode1(NDX,Level,Node,Key1,Child2,n(Sk1,Sk2,Sc1,Sc2,Sc3),UN,0) :-
        L is Level+1,ndx_newnode(NDX,UniN),
        ndx_putnode(NDX,L,Node,n(Sk1,UniN,Child2)),
        ndx_putnode(NDX,Level,UniN,n(Key1,UN,Sc1)),
        ndx_putnode(NDX,Level,Child2,n(Sk2,Sc2,Sc3)).

ndx_delnode2(_,_,_,0,0) :- !.
ndx_delnode2(NDX,Level,Node,UN,UniN) :-
        L is Level+1,ndx_getnode(NDX,L,Node,n(Key1,Child1,Child2)),
        ndx_getnode(NDX,Level,Child1,SNode),
        ndx_delnode2(NDX,Level,Node,Key1,Child1,SNode,UN,UniN).

ndx_delnode2(NDX,Level,Node,Key1,Child1,n(Sk1,Sc1,Sc2),UN,Child1) :- !,
        ndx_freenode(NDX,Node),
        ndx_putnode(NDX,Level,Child1,n(Sk1,Key1,Sc1,Sc2,UN)).
ndx_delnode2(NDX,Level,Node,Key1,Child1,n(Sk1,Sk2,Sc1,Sc2,Sc3),UN,0) :-
        L is Level+1,ndx_newnode(NDX,UniN),
        ndx_putnode(NDX,L,Node,n(Sk2,Child1,UniN)),
        ndx_putnode(NDX,Level,Child1,n(Sk1,Sc1,Sc2)),
        ndx_putnode(NDX,Level,UniN,n(Key1,Sc3,UN)).

ndx_delete_leaf(NDX,Key,Rec,Node,Key1,Child1,Child2,UniN,UniK) :-
        Key @< Key1,!,
        ndx_getnode(NDX,0,Child1,Leaf),
        ndx_delleaf1(NDX,Key,Rec,Node,Key1,Child1,Child2,UniN,UniK,Leaf).
ndx_delete_leaf(NDX,Key,Rec,Node,Key,Child1,Child2,UniN,_) :-
        ndx_getnode(NDX,0,Child2,Leaf),
        ndx_delleaf2(NDX,Rec,Node,Child1,Child2,UniN,Leaf).

ndx_delleaf1(NDX,Key,Rec,Node,Key1,Child1,Child2,Child2,UniK,l(Key,Rec,0,_)) :- !,
        ndx_freenode(NDX,Child1),ndx_freenode(NDX,Node),
        ndx_changekey(NDX,UniK,Key1).
ndx_delleaf1(NDX,Key,Rec,_,_,Child1,_,0,_,l(Key,Rec1,Link,Last)) :-
        ndx_delovfp(NDX,Rec,Child1,Key,Rec1,Link,Last).

ndx_delleaf2(NDX,Rec,Node,Child1,Child2,Child1,l(_,Rec,0,_)) :- !,
        ndx_freenode(NDX,Child2),ndx_freenode(NDX,Node).
ndx_delleaf2(NDX,Rec,_,_,Child2,0,l(Key,Rec1,Link,Last)) :-
        ndx_delovfp(NDX,Rec,Child2,Key,Rec1,Link,Last).

ndx_trim_node(NDX,Key,Rec,0,Node,Key1,Key2,Child1,Child2,Child3,UniK) :- !,
        ndx_trim_leaf(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,UniK).
ndx_trim_node(NDX,Key,Rec,Level,Node,Key1,Key2,Child1,Child2,Child3,UniK) :-
        Key @< Key1,!,ndx_getnode(NDX,Level,Child1,ChNode),
        ndx_delete_child(NDX,Key,Rec,Level,Child1,ChNode,UN,UniK),
        ndx_trimnode1(NDX,Level,Node,Key1,Key2,Child2,Child3,UN).
ndx_trim_node(NDX,Key,Rec,Level,Node,_,Key2,_,Child2,_,_) :-
        Key @< Key2,!,ndx_getnode(NDX,Level,Child2,ChNode),
        ndx_delete_child(NDX,Key,Rec,Level,Child2,ChNode,UN,(Node;1)/Level),
        ndx_trimnode2(NDX,Level,Node,UN).
ndx_trim_node(NDX,Key,Rec,Level,Node,_,_,_,_,Child3,_) :-
        ndx_getnode(NDX,Level,Child3,ChNode),
        ndx_delete_child(NDX,Key,Rec,Level,Child3,ChNode,UN,(Node;2)/Level),
        ndx_trimnode3(NDX,Level,Node,UN).

ndx_trimnode1(_,_,_,_,_,_,_,0) :- !.
ndx_trimnode1(NDX,Level,Node,Key1,Key2,Child2,Child3,UN) :-
        ndx_getnode(NDX,Level,Child2,SNode),
        ndx_trimnode1(NDX,Level,Node,Key1,Key2,Child2,Child3,SNode,UN).

ndx_trimnode1(NDX,Level,Node,Key1,Key2,Child2,Child3,n(Sk1,Sc1,Sc2),UN) :- !,
        L is Level+1,
        ndx_putnode(NDX,L,Node,n(Key2,Child2,Child3)),
        ndx_putnode(NDX,Level,Child2,n(Key1,Sk1,UN,Sc1,Sc2)).
ndx_trimnode1(NDX,Level,Node,Key1,Key2,Child2,Child3,n(Sk1,Sk2,Sc1,Sc2,Sc3),UN) :-
        L is Level+1,ndx_newnode(NDX,UniN),
        ndx_putnode(NDX,L,Node,n(Sk1,Key2,UniN,Child2,Child3)),
        ndx_putnode(NDX,Level,UniN,n(Key1,UN,Sc1)),
        ndx_putnode(NDX,Level,Child2,n(Sk2,Sc2,Sc3)).

ndx_trimnode2(_,_,_,0) :- !.
ndx_trimnode2(NDX,Level,Node,UN) :-
        L is Level+1,ndx_getnode(NDX,L,Node,n(Key1,Key2,Child1,Child2,Child3)),
        ndx_getnode(NDX,Level,Child3,SNode),
        ndx_trimnode2(NDX,Level,Node,Key1,Key2,Child1,Child3,SNode,UN).

ndx_trimnode2(NDX,Level,Node,Key1,Key2,Child1,Child3,n(Sk1,Sc1,Sc2),UN) :- !,
        L is Level+1,
        ndx_putnode(NDX,L,Node,n(Key1,Child1,Child3)),
        ndx_putnode(NDX,Level,Child3,n(Key2,Sk1,UN,Sc1,Sc2)).
ndx_trimnode2(NDX,Level,Node,Key1,Key2,Child1,Child3,n(Sk1,Sk2,Sc1,Sc2,Sc3),UN) :-
        L is Level+1,ndx_newnode(NDX,UniN),
        ndx_putnode(NDX,L,Node,n(Key1,Sk1,Child1,UniN,Child3)),
        ndx_putnode(NDX,Level,UniN,n(Key2,UN,Sc1)),
        ndx_putnode(NDX,Level,Child3,n(Sk2,Sc2,Sc3)).

ndx_trimnode3(_,_,_,0) :- !.
ndx_trimnode3(NDX,Level,Node,UN) :-
        L is Level+1,ndx_getnode(NDX,L,Node,n(Key1,Key2,Child1,Child2,Child3)),
        ndx_getnode(NDX,Level,Child2,SNode),
        ndx_trimnode3(NDX,Level,Node,Key1,Key2,Child1,Child2,SNode,UN).

ndx_trimnode3(NDX,Level,Node,Key1,Key2,Child1,Child2,n(Sk1,Sc1,Sc2),UN) :- !,
        L is Level+1,
        ndx_putnode(NDX,L,Node,n(Key1,Child1,Child2)),
        ndx_putnode(NDX,Level,Child2,n(Sk1,Key2,Sc1,Sc2,UN)).
ndx_trimnode3(NDX,Level,Node,Key1,Key2,Child1,Child2,n(Sk1,Sk2,Sc1,Sc2,Sc3),UN) :-
        L is Level+1,ndx_newnode(NDX,UniN),
        ndx_putnode(NDX,L,Node,n(Key1,Sk2,Child1,Child2,UniN)),
        ndx_putnode(NDX,Level,Child2,n(Sk1,Sc1,Sc2)),
        ndx_putnode(NDX,Level,UniN,n(Key2,Sc3,UN)).

ndx_trim_leaf(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,UniK) :-
        Key @< Key1,!,
        ndx_getnode(NDX,0,Child1,Leaf),
        ndx_trimleaf1(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,UniK,Leaf).
ndx_trim_leaf(NDX,Key,Rec,Node,Key,Key2,Child1,Child2,Child3,_) :- !,
        ndx_getnode(NDX,0,Child2,Leaf),
        ndx_trimleaf2(NDX,Rec,Node,Key2,Child1,Child2,Child3,Leaf).
ndx_trim_leaf(NDX,Key,Rec,Node,Key1,Key,Child1,Child2,Child3,_) :-
        ndx_getnode(NDX,0,Child3,Leaf),
        ndx_trimleaf3(NDX,Rec,Node,Key1,Child1,Child2,Child3,Leaf).

ndx_trimleaf1(NDX,Key,Rec,Node,Key1,Key2,Child1,Child2,Child3,UniK,l(Key,Rec,0,_)) :- !,
        ndx_freenode(NDX,Child1),
        ndx_putnode(NDX,1,Node,n(Key2,Child2,Child3)),
        ndx_changekey(NDX,UniK,Key1).
ndx_trimleaf1(NDX,Key,Rec,_,_,_,Child1,_,_,_,l(Key,Rec1,Link,Last)) :-
        ndx_delovfp(NDX,Rec,Child1,Key,Rec1,Link,Last).

ndx_trimleaf2(NDX,Rec,Node,Key2,Child1,Child2,Child3,l(_,Rec,0,_)) :- !,
        ndx_freenode(NDX,Child2),
        ndx_putnode(NDX,1,Node,n(Key2,Child1,Child3)).
ndx_trimleaf2(NDX,Rec,_,_,_,Child2,_,l(Key,Rec1,Link,Last)) :-
        ndx_delovfp(NDX,Rec,Child2,Key,Rec1,Link,Last).

ndx_trimleaf3(NDX,Rec,Node,Key1,Child1,Child2,Child3,l(_,Rec,0,_)) :- !,
        ndx_freenode(NDX,Child3),
        ndx_putnode(NDX,1,Node,n(Key1,Child1,Child2)).
ndx_trimleaf3(NDX,Rec,_,_,_,_,Child3,l(Key,Rec1,Link,Last)) :-
        ndx_delovfp(NDX,Rec,Child3,Key,Rec1,Link,Last).

ndx_delovfp(NDX,Rec,Leaf,Key,Rec,Link,Link) :- !,
        ndx_getnode(NDX,0,Link,o(Rec1,Next)),
        ndx_putnode(NDX,0,Leaf,l(Key,Rec1,0,0)),
        ndx_freenode(NDX,Link).
ndx_delovfp(NDX,Rec,Leaf,Key,Rec,Link,Last) :- !,
        ndx_getnode(NDX,0,Link,o(Rec1,Next)),
        ndx_putnode(NDX,0,Leaf,l(Key,Rec1,Next,Last)),
        ndx_freenode(NDX,Link).
ndx_delovfp(_,_,_,_,_,0,_) :- !,fail.
ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last) :-
        ndx_getnode(NDX,0,Link,OV),
        ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last,OV).

ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Link,o(Rec,_)) :- !,
        ndx_putnode(NDX,0,Leaf,l(Key,Rec1,0,0)),
        ndx_freenode(NDX,Link).
ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last,o(Rec,Next)) :- !,
        ndx_putnode(NDX,0,Leaf,l(Key,Rec1,Next,Last)),
        ndx_freenode(NDX,Link).
ndx_delovfp(_,_,_,_,_,Link,Link,_) :- !,fail.
ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last,o(Rec2,Next)) :-
        ndx_getnode(NDX,0,Next,OV),
        ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last,Link,Rec2,Next,OV).

ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last,Cur,RecC,Last,o(Rec,_)) :- !,
        ndx_putnode(NDX,0,Leaf,l(Key,Rec1,Link,Cur)),
        ndx_putnode(NDX,0,Cur,o(RecC,0)),
        ndx_freenode(NDX,Last).
ndx_delovfp(NDX,Rec,_,_,_,_,_,Cur,RecC,NextC,o(Rec,NextN)) :- !,
        ndx_putnode(NDX,0,Cur,o(RecC,NextN)),
        ndx_freenode(NDX,NextC).
ndx_delovfp(_,_,_,_,_,_,Last,_,_,Last,_) :- !,fail.
ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last,_,_,NextC,o(RecN,NextN)) :-
        ndx_getnode(NDX,0,NextN,OV),
        ndx_delovfp(NDX,Rec,Leaf,Key,Rec1,Link,Last,NextC,RecN,NextN,OV).

ndx_changekey(NDX,Node/Level,NewK) :- !,L is Level+1,
        ndx_getnode(NDX,L,Node,n(Key1,Child1,Child2)),
        ndx_putnode(NDX,L,Node,n(NewK,Child1,Child2)).
ndx_changekey(NDX,(Node;1)/Level,NewK) :- !,L is Level+1,
        ndx_getnode(NDX,L,Node,n(Key1,Key2,Child1,Child2,Child3)),
        ndx_putnode(NDX,L,Node,n(NewK,Key2,Child1,Child2,Child3)).
ndx_changekey(NDX,(Node;2)/Level,NewK) :- L is Level+1,
        ndx_getnode(NDX,L,Node,n(Key1,Key2,Child1,Child2,Child3)),
        ndx_putnode(NDX,L,Node,n(Key1,NewK,Child1,Child2,Child3)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- public ncreate0/3.
:- mode ncreate0(+,+,+).

ncreate0(PDF,Field,NDX) :-
        ndx_make_record1(PDF,Field,NDX),
        ndx_create_body(PDF,Field,NDX).


:- mode ndx_make_record1(+,+,+).
:- mode ndx_create_body(+,+,+).
:- mode ndx_create_body(+,+,+,+).

ndx_make_record1(PDF,Field,NDX) :-
        d_struct(PDF,S),assoc(S,Field,Flen),
        Dlen is Flen*2+40,d_create(NDX,[d,Dlen]),
        d_writeq(NDX,1,[[d,r(0,1,0)]]),d_writeq(NDX,2,[[d,l]]).

%%%% Testing Stub
%ncreate(Flen,NDX) :-
%       Dlen is Flen*2+40,d_create(NDX,[d,Dlen]),
%       d_writeq(NDX,1,[[d,r(0,1,0)]]),d_writeq(NDX,2,[[d,l]]).

ndx_create_body(PDF,Field,NDX) :- d_seek(PDF,_,0),
        repeat(Rec),ndx_create_body(PDF,Field,NDX,Rec),!.

ndx_create_body(PDF,Field,NDX,Rec) :- R is Rec+1,
        d_read(PDF,[Field],[[_,Key]]),!,ndx_add(NDX,Key,R),fail.
ndx_create_body(_,_,_,_).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- public ndx_traverse/3.
:- mode ndx_traverse(+,-,-).
:- mode ndx_traverse_leaf(+,+,+,-,-).
:- mode ndx_traverse_node(+,+,+,-,-).
:- mode ndx_traverse_node(+,+,+,+,-,-).
:- mode ndx_traverse_node(+,+,+,+,+,-,-).
:- mode ndx_traverse_recs(+,+,-).
:- mode ndx_traverse_recs(+,+,+,+,-).

ndx_traverse(NDX,Key,Rec) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),
        ndx_traverse_leaf(NDX,Level,Root,Key,Leaf),
        ndx_traverse_recs(NDX,Leaf,Rec).

ndx_traverse_leaf(NDX,0,Node,Key,Leaf) :- !,
        ndx_getnode(NDX,0,Node,Leaf),Leaf=l(Key,_,_,_).
ndx_traverse_leaf(NDX,Level,Node,Key,Leaf) :-
        ndx_getnode(NDX,Level,Node,N),
        L is Level-1,ndx_traverse_node(NDX,L,N,Key,Leaf).

ndx_traverse_node(NDX,Level,n(_,Child1,Child2),Key,Leaf) :- !,
        ndx_traverse_node(NDX,Level,Child1,Child2,Key,Leaf).
ndx_traverse_node(NDX,Level,n(_,_,Child1,Child2,Child3),Key,Leaf) :-
        ndx_traverse_node(NDX,Level,Child1,Child2,Child3,Key,Leaf).

ndx_traverse_node(NDX,Level,Child,_,Key,Leaf) :-
        ndx_traverse_leaf(NDX,Level,Child,Key,Leaf).
ndx_traverse_node(NDX,Level,_,Child,Key,Leaf) :-
        ndx_traverse_leaf(NDX,Level,Child,Key,Leaf).

ndx_traverse_node(NDX,Level,Child,_,_,Key,Leaf) :-
        ndx_traverse_leaf(NDX,Level,Child,Key,Leaf).
ndx_traverse_node(NDX,Level,_,Child,_,Key,Leaf) :-
        ndx_traverse_leaf(NDX,Level,Child,Key,Leaf).
ndx_traverse_node(NDX,Level,_,_,Child,Key,Leaf) :-
        ndx_traverse_leaf(NDX,Level,Child,Key,Leaf).

ndx_traverse_recs(_,l(_,Rec,0,_),Rec) :- !.
ndx_traverse_recs(_,l(_,Rec,_,_),Rec).
ndx_traverse_recs(NDX,l(_,_,Link,Last),Rec) :-
        ndx_getnode(NDX,0,Link,OV),
        ndx_traverse_recs(NDX,Link,Last,OV,Rec).

ndx_traverse_recs(_,Last,Last,o(Rec,_),Rec) :- !.
ndx_traverse_recs(_,_,_,o(Rec,_),Rec).
ndx_traverse_recs(NDX,_,Last,o(_,Next),Rec) :-
        ndx_getnode(NDX,0,Next,OV),
        ndx_traverse_recs(NDX,Next,Last,OV,Rec).

%%%% Testing Utility
%ndx_dump_tree(NDX) :-
%       ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),
%       ndx_dump_node(NDX,Level,0,Root).
%
%ndx_dump_node(NDX,0,Indent,Node) :- !,
%       ndx_getnode(NDX,0,Node,Leaf),ndx_dump_leaf(NDX,Indent,Leaf).
%ndx_dump_node(NDX,Level,Indent,Node) :-
%       ndx_getnode(NDX,Level,Node,N),L is Level-1,
%       ndx_dumpnode(NDX,L,Indent,N).
%
%ndx_dumpnode(NDX,Level,Indent,n(Key1,Child1,Child2)) :- !,
%       I is Indent+1,
%       ndx_dump_node(NDX,Level,I,Child1),
%       tab(Indent),writeq(Key1),nl,
%       ndx_dump_node(NDX,Level,I,Child2).
%ndx_dumpnode(NDX,Level,Indent,n(Key1,Key2,Child1,Child2,Child3)) :-
%       I is Indent+1,
%       ndx_dump_node(NDX,Level,I,Child1),
%       tab(Indent),writeq(Key1),nl,
%       ndx_dump_node(NDX,Level,I,Child2),
%       tab(Indent),writeq(Key2),nl,
%       ndx_dump_node(NDX,Level,I,Child3).
%
%ndx_dump_leaf(_,Indent,l) :- !,tab(Indent),write('-inf'),nl.
%ndx_dump_leaf(_,Indent,l(Key,Rec,0,_)) :- !,
%       tab(Indent),writeq(Key),nl,
%       tab(Indent+1),write(Rec),nl.
%ndx_dump_leaf(NDX,Indent,l(Key,Rec,Link,Last)) :-
%       tab(Indent),writeq(Key),nl,
%       I is Indent+1,tab(I),write(Rec),nl,
%       ndx_getnode(NDX,0,Link,OV),
%       ndx_dump_ovfp(NDX,I,Link,Last,OV).
%
%ndx_dump_ovfp(_,Indent,Last,Last,o(Rec,_)) :- !,
%       tab(Indent),write(Rec),nl.
%ndx_dump_ovfp(NDX,Indent,_,Last,o(Rec,Next)) :-
%       tab(Indent),write(Rec),nl,
%       ndx_getnode(NDX,0,Next,OV),
%       ndx_dump_ovfp(NDX,Indent,Next,Last,OV).
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- public ndx_getnode/4.

:- mode ndx_getnode(+,+,+,-).
:- mode ndx_putnode(+,+,+,+).
:- mode ndx_allocnode(+,+).
:- mode ndx_allocnode(+,+,+).
:- mode ndx_allocnode1(+,+).
:- mode ndx_allocnode1(+,+,+,-).
:- mode ndx_newnode(+,-).
:- mode ndx_freenode(+,+).

ndx_getnode(NDX,Level,Rec,Data) :- ndx_cache(NDX,Level,Rec,Data),!.
ndx_getnode(NDX,Level,Rec,Data) :-
        (retract(ndx_cache(NDX,Level,_,_));true),!,
        d_seek(NDX,_,Rec),d_read(NDX,[[_,Data]]),
        assert(ndx_cache(NDX,Level,Rec,Data)).

ndx_putnode(NDX,Level,Rec,Data) :-
        (retract(ndx_cache(NDX,Level,_,_));true),!,
        R is Rec+1,d_writeq(NDX,R,[[d,Data]]),
        assert(ndx_cache(NDX,Level,Rec,Data)).

ndx_allocnode(NDX,N) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),ndx_allocnode(NDX,Delete,N).

ndx_allocnode(_,_,0) :- !.
ndx_allocnode(NDX,0,N) :- !,ndx_allocnode1(NDX,N).
ndx_allocnode(NDX,Delete,N) :-
        ndx_getnode(NDX,-2,Delete,Delete1),N1 is N-1,
        ndx_allocnode(NDX,Delete1,N1).

ndx_allocnode1(NDX,N) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),
        ndx_allocnode1(NDX,Delete,N,Delete1),
        ndx_putnode(NDX,-1,0,r(Level,Root,Delete1)).

ndx_allocnode1(NDX,Delete,0,Delete) :- !.
ndx_allocnode1(NDX,Delete,N,Delete1) :-
        d_record(NDX,_,Delete2,_),ndx_putnode(NDX,-2,Delete2,Delete),
        N1 is N-1,ndx_allocnode1(NDX,Delete2,N1,Delete1).

ndx_newnode(NDX,Rec) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Rec)),
        ndx_getnode(NDX,-2,Rec,Delete),
        ndx_putnode(NDX,-1,0,r(Level,Root,Delete)).

ndx_freenode(NDX,Rec) :-
        ndx_getnode(NDX,-1,0,r(Level,Root,Delete)),
        ndx_putnode(NDX,-2,Rec,Delete),
        ndx_putnode(NDX,-1,0,r(Level,Root,Rec)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- mode assoc(+,+,-).

assoc([[E,D]|_],E,D) :- !.
assoc([_|L],E,D) :- assoc(L,E,D).

