1/*  Part of SWI-Prolog
    2
    3    Author:        R.A.O'Keefe, L.Damas, V.S.Costa, Glenn Burgess,
    4                   Jiri Spitz and Jan Wielemaker
    5    E-mail:        J.Wielemaker@vu.nl
    6    WWW:           http://www.swi-prolog.org
    7    Copyright (c)  2004-2018, various people and institutions
    8    All rights reserved.
    9
   10    Redistribution and use in source and binary forms, with or without
   11    modification, are permitted provided that the following conditions
   12    are met:
   13
   14    1. Redistributions of source code must retain the above copyright
   15       notice, this list of conditions and the following disclaimer.
   16
   17    2. Redistributions in binary form must reproduce the above copyright
   18       notice, this list of conditions and the following disclaimer in
   19       the documentation and/or other materials provided with the
   20       distribution.
   21
   22    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   23    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   24    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   25    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   26    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   27    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   28    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   29    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   30    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   31    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   32    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   33    POSSIBILITY OF SUCH DAMAGE.
   34*/
   35
   36:- module(assoc,
   37          [ empty_assoc/1,              % -Assoc
   38            is_assoc/1,                 % +Assoc
   39            assoc_to_list/2,            % +Assoc, -Pairs
   40            assoc_to_keys/2,            % +Assoc, -List
   41            assoc_to_values/2,          % +Assoc, -List
   42            gen_assoc/3,                % ?Key, +Assoc, ?Value
   43            get_assoc/3,                % +Key, +Assoc, ?Value
   44            get_assoc/5,                % +Key, +Assoc0, ?Val0, ?Assoc, ?Val
   45            list_to_assoc/2,            % +List, ?Assoc
   46            map_assoc/2,                % :Goal, +Assoc
   47            map_assoc/3,                % :Goal, +Assoc0, ?Assoc
   48            max_assoc/3,                % +Assoc, ?Key, ?Value
   49            min_assoc/3,                % +Assoc, ?Key, ?Value
   50            ord_list_to_assoc/2,        % +List, ?Assoc
   51            put_assoc/4,                % +Key, +Assoc0, +Value, ?Assoc
   52            del_assoc/4,                % +Key, +Assoc0, ?Value, ?Assoc
   53            del_min_assoc/4,            % +Assoc0, ?Key, ?Value, ?Assoc
   54            del_max_assoc/4             % +Assoc0, ?Key, ?Value, ?Assoc
   55          ]).   56:- autoload(library(error),[must_be/2,domain_error/2]).   57
   58
   59/** <module> Binary associations
   60
   61Assocs are Key-Value associations implemented as  a balanced binary tree
   62(AVL tree).
   63
   64__Warning: instantiation of keys__
   65
   66AVL  trees  depend  on    the   Prolog   _standard  order  of  terms_ to
   67organize the keys as a (balanced)  binary   tree.  This implies that any
   68term may be used as a key. The   tree may produce wrong results, such as
   69not being able to find a key, if  the ordering of keys changes after the
   70key has been inserted into the tree.   The user is responsible to ensure
   71that variables used as keys or appearing in  a term used as key that may
   72affect ordering are not  unified,  with   the  exception  of unification
   73against new fresh variables. For this   reason,  _ground_ terms are safe
   74keys. When using non-ground terms, either make sure the variables appear
   75in places that do not affect the   standard order relative to other keys
   76in the tree or make sure to not unify against these variables as long as
   77the tree is being used.
   78
   79@see            library(pairs), library(rbtrees)
   80@author         R.A.O'Keefe, L.Damas, V.S.Costa and Jan Wielemaker
   81*/
   82
   83:- meta_predicate
   84    map_assoc(1, ?),
   85    map_assoc(2, ?, ?).   86
   87%!  empty_assoc(?Assoc) is semidet.
   88%
   89%   Is true if Assoc is the empty association list.
   90
   91empty_assoc(t).
   92
   93%!  assoc_to_list(+Assoc, -Pairs) is det.
   94%
   95%   Translate Assoc to a list Pairs  of   Key-Value  pairs.  The keys in
   96%   Pairs are sorted in ascending order.
   97
   98assoc_to_list(Assoc, List) :-
   99    assoc_to_list(Assoc, List, []).
  100
  101assoc_to_list(t(Key,Val,_,L,R), List, Rest) :-
  102    assoc_to_list(L, List, [Key-Val|More]),
  103    assoc_to_list(R, More, Rest).
  104assoc_to_list(t, List, List).
  105
  106
  107%!  assoc_to_keys(+Assoc, -Keys) is det.
  108%
  109%   True if Keys is the list of keys   in  Assoc. The keys are sorted in
  110%   ascending order.
  111
  112assoc_to_keys(Assoc, List) :-
  113    assoc_to_keys(Assoc, List, []).
  114
  115assoc_to_keys(t(Key,_,_,L,R), List, Rest) :-
  116    assoc_to_keys(L, List, [Key|More]),
  117    assoc_to_keys(R, More, Rest).
  118assoc_to_keys(t, List, List).
  119
  120
  121%!  assoc_to_values(+Assoc, -Values) is det.
  122%
  123%   True if Values is the list of values in Assoc. Values are ordered in
  124%   ascending order of the key to which they were associated. Values may
  125%   contain duplicates.
  126
  127assoc_to_values(Assoc, List) :-
  128    assoc_to_values(Assoc, List, []).
  129
  130assoc_to_values(t(_,Value,_,L,R), List, Rest) :-
  131    assoc_to_values(L, List, [Value|More]),
  132    assoc_to_values(R, More, Rest).
  133assoc_to_values(t, List, List).
  134
  135%!  is_assoc(+Assoc) is semidet.
  136%
  137%   True if Assoc is an association list. This predicate checks that the
  138%   structure is valid, elements are in order,   and tree is balanced to
  139%   the extent guaranteed by AVL trees.   I.e., branches of each subtree
  140%   differ in depth by at most  1.   Does  _not_  validate that keys are
  141%   sufficiently instantiated to ensure the tree  remains valid if a key
  142%   is further instantiated.
  143
  144is_assoc(Assoc) :-
  145    nonvar(Assoc),
  146    is_assoc(Assoc, _Min, _Max, _Depth).
  147
  148is_assoc(t,X,X,0) :- !.
  149is_assoc(t(K,_,-,t,t),K,K,1) :- !.
  150is_assoc(t(K,_,>,t,t(RK,_,-,t,t)),K,RK,2) :-
  151    !, K @< RK.
  152is_assoc(t(K,_,<,t(LK,_,-,t,t),t),LK,K,2) :-
  153    !, LK @< K.
  154is_assoc(t(K,_,B,L,R),Min,Max,Depth) :-
  155    is_assoc(L,Min,LMax,LDepth),
  156    is_assoc(R,RMin,Max,RDepth),
  157    % Ensure Balance matches depth
  158    compare(Rel,RDepth,LDepth),
  159    balance(Rel,B),
  160    % Ensure ordering
  161    LMax @< K,
  162    K @< RMin,
  163    Depth is max(LDepth, RDepth)+1.
  164
  165balance(=,-).
  166balance(<,<).
  167balance(>,>).
  168
  169
  170%!  gen_assoc(?Key, +Assoc, ?Value) is nondet.
  171%
  172%   True if Key-Value is an  association   in  Assoc. Enumerates keys in
  173%   ascending order on backtracking.
  174%
  175%   @see get_assoc/3.
  176
  177gen_assoc(Key, Assoc, Value) :-
  178    (   ground(Key)
  179    ->  get_assoc(Key, Assoc, Value)
  180    ;   gen_assoc_(Key, Assoc, Value)
  181    ).
  182
  183gen_assoc_(Key, t(Key0,Val0,_,L,R), Val) =>
  184    gen_assoc_(Key, Key0,Val0,L,R, Val).
  185gen_assoc_(_Key, t, _Val) =>
  186    fail.
  187
  188gen_assoc_(Key, _,_,L,_, Val) :-
  189    gen_assoc_(Key, L, Val).
  190gen_assoc_(Key, Key,Val0,_,_, Val) :-
  191    Val = Val0.
  192gen_assoc_(Key, _,_,_,R, Val) :-
  193    gen_assoc_(Key, R, Val).
  194
  195
  196%!  get_assoc(+Key, +Assoc, -Value) is semidet.
  197%
  198%   True if Key-Value is an association in Assoc.
  199
  200:- if(current_predicate('$btree_find_node'/5)).  201get_assoc(Key, Tree, Val) :-
  202    Tree \== t,
  203    '$btree_find_node'(Key, Tree, 0x010405, Node, =),
  204    arg(2, Node, Val).
  205:- else.  206get_assoc(Key, t(K,V,_,L,R), Val) =>
  207    compare(Rel, Key, K),
  208    get_assoc(Rel, Key, V, L, R, Val).
  209get_assoc(_, t, _) =>
  210    fail.
  211
  212get_assoc(=, _, Val, _, _, Val).
  213get_assoc(<, Key, _, Tree, _, Val) :-
  214    get_assoc(Key, Tree, Val).
  215get_assoc(>, Key, _, _, Tree, Val) :-
  216    get_assoc(Key, Tree, Val).
  217:- endif.  218
  219
  220%!  get_assoc(+Key, +Assoc0, ?Val0, ?Assoc, ?Val) is semidet.
  221%
  222%   True if Key-Val0 is in Assoc0 and Key-Val is in Assoc.
  223
  224get_assoc(Key, t(K,V,B,L,R), Val, Assoc, NVal) =>
  225    Assoc = t(K,NV,B,NL,NR),
  226    compare(Rel, Key, K),
  227    get_assoc(Rel, Key, V, L, R, Val, NV, NL, NR, NVal).
  228get_assoc(_Key, t, _Val, _, _) =>
  229    fail.
  230
  231get_assoc(=, _, Val, L, R, Val, NVal, L, R, NVal).
  232get_assoc(<, Key, V, L, R, Val, V, NL, R, NVal) :-
  233    get_assoc(Key, L, Val, NL, NVal).
  234get_assoc(>, Key, V, L, R, Val, V, L, NR, NVal) :-
  235    get_assoc(Key, R, Val, NR, NVal).
  236
  237
  238%!  list_to_assoc(+Pairs, -Assoc) is det.
  239%
  240%   Create an association from a  list   Pairs  of Key-Value pairs. List
  241%   must not contain duplicate keys.
  242%
  243%   @error domain_error(unique_key_pairs, List) if List contains duplicate keys
  244
  245list_to_assoc(List, Assoc) :-
  246    (   List == []
  247    ->  Assoc = t
  248    ;   keysort(List, Sorted),
  249        (  ord_pairs(Sorted)
  250        -> length(Sorted, N),
  251           list_to_assoc(N, Sorted, [], _, Assoc)
  252        ;  domain_error(unique_key_pairs, List)
  253        )
  254    ).
  255
  256list_to_assoc(1, [K-V|More], More, 1, t(K,V,-,t,t)) :- !.
  257list_to_assoc(2, [K1-V1,K2-V2|More], More, 2, t(K2,V2,<,t(K1,V1,-,t,t),t)) :- !.
  258list_to_assoc(N, List, More, Depth, t(K,V,Balance,L,R)) :-
  259    N0 is N - 1,
  260    RN is N0 div 2,
  261    Rem is N0 mod 2,
  262    LN is RN + Rem,
  263    list_to_assoc(LN, List, [K-V|Upper], LDepth, L),
  264    list_to_assoc(RN, Upper, More, RDepth, R),
  265    Depth is LDepth + 1,
  266    compare(B, RDepth, LDepth), balance(B, Balance).
  267
  268%!  ord_list_to_assoc(+Pairs, -Assoc) is det.
  269%
  270%   Assoc is created from an ordered list  Pairs of Key-Value pairs. The
  271%   pairs must occur in strictly ascending order of their keys.
  272%
  273%   @error domain_error(key_ordered_pairs, List) if pairs are not ordered.
  274
  275ord_list_to_assoc(Sorted, Assoc) :-
  276    (   Sorted == []
  277    ->  Assoc = t
  278    ;   (  ord_pairs(Sorted)
  279        -> length(Sorted, N),
  280           list_to_assoc(N, Sorted, [], _, Assoc)
  281        ;  domain_error(key_ordered_pairs, Sorted)
  282        )
  283    ).
  284
  285%!  ord_pairs(+Pairs) is semidet
  286%
  287%   True if Pairs is a list of Key-Val pairs strictly ordered by key.
  288
  289ord_pairs([K-_V|Rest]) :-
  290    ord_pairs(Rest, K).
  291ord_pairs([], _K).
  292ord_pairs([K-_V|Rest], K0) :-
  293    K0 @< K,
  294    ord_pairs(Rest, K).
  295
  296%!  map_assoc(:Pred, +Assoc) is semidet.
  297%
  298%   True if Pred(Value) is true for all values in Assoc.
  299
  300map_assoc(Pred, T) :-
  301    map_assoc_(T, Pred).
  302
  303map_assoc_(t, _) =>
  304    true.
  305map_assoc_(t(_,Val,_,L,R), Pred) =>
  306    map_assoc_(L, Pred),
  307    call(Pred, Val),
  308    map_assoc_(R, Pred).
  309
  310%!  map_assoc(:Pred, +Assoc0, ?Assoc) is semidet.
  311%
  312%   Map corresponding values. True if Assoc  is Assoc0 with Pred applied
  313%   to all corresponding pairs of of values.
  314
  315map_assoc(Pred, T0, T) :-
  316    map_assoc_(T0, Pred, T).
  317
  318map_assoc_(t, _, Assoc) =>
  319    Assoc = t.
  320map_assoc_(t(Key,Val,B,L0,R0), Pred, Assoc) =>
  321    Assoc = t(Key,Ans,B,L1,R1),
  322    map_assoc_(L0, Pred, L1),
  323    call(Pred, Val, Ans),
  324    map_assoc_(R0, Pred, R1).
  325
  326
  327%!  max_assoc(+Assoc, -Key, -Value) is semidet.
  328%
  329%   True if Key-Value is in Assoc and Key is the largest key.
  330
  331max_assoc(t(K,V,_,_,R), Key, Val) =>
  332    max_assoc(R, K, V, Key, Val).
  333max_assoc(t, _, _) =>
  334    fail.
  335
  336max_assoc(t, K, V, K, V).
  337max_assoc(t(K,V,_,_,R), _, _, Key, Val) :-
  338    max_assoc(R, K, V, Key, Val).
  339
  340
  341%!  min_assoc(+Assoc, -Key, -Value) is semidet.
  342%
  343%   True if Key-Value is in assoc and Key is the smallest key.
  344
  345min_assoc(t(K,V,_,L,_), Key, Val) =>
  346    min_assoc(L, K, V, Key, Val).
  347min_assoc(t, _, _) =>
  348    fail.
  349
  350min_assoc(t, K, V, K, V).
  351min_assoc(t(K,V,_,L,_), _, _, Key, Val) :-
  352    min_assoc(L, K, V, Key, Val).
  353
  354
  355%!  put_assoc(+Key, +Assoc0, +Value, -Assoc) is det.
  356%
  357%   Assoc is Assoc0, except that Key is  associated with Value. This can
  358%   be used to insert and change associations.
  359
  360put_assoc(Key, A0, Value, A) :-
  361    insert(A0, Key, Value, A, _).
  362
  363insert(t, Key, Val, Assoc, Changed) =>
  364    Assoc = t(Key,Val,-,t,t),
  365    Changed = yes.
  366insert(t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) =>
  367    compare(Rel, K, Key),
  368    insert(Rel, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged).
  369
  370insert(=, t(Key,_,B,L,R), _, V, t(Key,V,B,L,R), no).
  371insert(<, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  372    insert(L, K, V, NewL, LeftHasChanged),
  373    adjust(LeftHasChanged, t(Key,Val,B,NewL,R), left, NewTree, WhatHasChanged).
  374insert(>, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  375    insert(R, K, V, NewR, RightHasChanged),
  376    adjust(RightHasChanged, t(Key,Val,B,L,NewR), right, NewTree, WhatHasChanged).
  377
  378adjust(no, Oldree, _, Oldree, no).
  379adjust(yes, t(Key,Val,B0,L,R), LoR, NewTree, WhatHasChanged) :-
  380    table(B0, LoR, B1, WhatHasChanged, ToBeRebalanced),
  381    rebalance(ToBeRebalanced, t(Key,Val,B0,L,R), B1, NewTree, _, _).
  382
  383%     balance  where     balance  whole tree  to be
  384%     before   inserted  after    increased   rebalanced
  385table(-      , left    , <      , yes       , no    ) :- !.
  386table(-      , right   , >      , yes       , no    ) :- !.
  387table(<      , left    , -      , no        , yes   ) :- !.
  388table(<      , right   , -      , no        , no    ) :- !.
  389table(>      , left    , -      , no        , no    ) :- !.
  390table(>      , right   , -      , no        , yes   ) :- !.
  391
  392%!  del_min_assoc(+Assoc0, ?Key, ?Val, -Assoc) is semidet.
  393%
  394%   True if Key-Value is in Assoc0 and Key is the smallest key. Assoc is
  395%   Assoc0 with Key-Value removed. Warning: This  will succeed with _no_
  396%   bindings for Key or Val if Assoc0 is empty.
  397
  398del_min_assoc(Tree, Key, Val, NewTree) :-
  399    del_min_assoc(Tree, Key, Val, NewTree, _DepthChanged).
  400
  401del_min_assoc(t(Key,Val,_B,t,R), Key, Val, R, yes) :- !.
  402del_min_assoc(t(K,V,B,L,R), Key, Val, NewTree, Changed) :-
  403    del_min_assoc(L, Key, Val, NewL, LeftChanged),
  404    deladjust(LeftChanged, t(K,V,B,NewL,R), left, NewTree, Changed).
  405
  406%!  del_max_assoc(+Assoc0, ?Key, ?Val, -Assoc) is semidet.
  407%
  408%   True if Key-Value is in Assoc0 and Key is the greatest key. Assoc is
  409%   Assoc0 with Key-Value removed. Warning: This  will succeed with _no_
  410%   bindings for Key or Val if Assoc0 is empty.
  411
  412del_max_assoc(Tree, Key, Val, NewTree) :-
  413    del_max_assoc(Tree, Key, Val, NewTree, _DepthChanged).
  414
  415del_max_assoc(t(Key,Val,_B,L,t), Key, Val, L, yes) :- !.
  416del_max_assoc(t(K,V,B,L,R), Key, Val, NewTree, Changed) :-
  417    del_max_assoc(R, Key, Val, NewR, RightChanged),
  418    deladjust(RightChanged, t(K,V,B,L,NewR), right, NewTree, Changed).
  419
  420%!  del_assoc(+Key, +Assoc0, ?Value, -Assoc) is semidet.
  421%
  422%   True if Key-Value is  in  Assoc0.   Assoc  is  Assoc0 with
  423%   Key-Value removed.
  424
  425del_assoc(Key, A0, Value, A) :-
  426    delete(A0, Key, Value, A, _).
  427
  428% delete(+Subtree, +SearchedKey, ?SearchedValue, ?SubtreeOut, ?WhatHasChanged)
  429delete(t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) =>
  430    compare(Rel, K, Key),
  431    delete(Rel, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged).
  432delete(t, _, _, _, _) =>
  433    fail.
  434
  435% delete(+KeySide, +Subtree, +SearchedKey, ?SearchedValue, ?SubtreeOut, ?WhatHasChanged)
  436% KeySide is an operator {<,=,>} indicating which branch should be searched for the key.
  437% WhatHasChanged {yes,no} indicates whether the NewTree has changed in depth.
  438delete(=, t(Key,Val,_B,t,R), Key, Val, R, yes) :- !.
  439delete(=, t(Key,Val,_B,L,t), Key, Val, L, yes) :- !.
  440delete(=, t(Key,Val,>,L,R), Key, Val, NewTree, WhatHasChanged) :-
  441    % Rh tree is deeper, so rotate from R to L
  442    del_min_assoc(R, K, V, NewR, RightHasChanged),
  443    deladjust(RightHasChanged, t(K,V,>,L,NewR), right, NewTree, WhatHasChanged),
  444    !.
  445delete(=, t(Key,Val,B,L,R), Key, Val, NewTree, WhatHasChanged) :-
  446    % Rh tree is not deeper, so rotate from L to R
  447    del_max_assoc(L, K, V, NewL, LeftHasChanged),
  448    deladjust(LeftHasChanged, t(K,V,B,NewL,R), left, NewTree, WhatHasChanged),
  449    !.
  450
  451delete(<, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  452    delete(L, K, V, NewL, LeftHasChanged),
  453    deladjust(LeftHasChanged, t(Key,Val,B,NewL,R), left, NewTree, WhatHasChanged).
  454delete(>, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  455    delete(R, K, V, NewR, RightHasChanged),
  456    deladjust(RightHasChanged, t(Key,Val,B,L,NewR), right, NewTree, WhatHasChanged).
  457
  458deladjust(no, OldTree, _, OldTree, no).
  459deladjust(yes, t(Key,Val,B0,L,R), LoR, NewTree, RealChange) :-
  460    deltable(B0, LoR, B1, WhatHasChanged, ToBeRebalanced),
  461    rebalance(ToBeRebalanced, t(Key,Val,B0,L,R), B1, NewTree, WhatHasChanged, RealChange).
  462
  463%     balance  where     balance  whole tree  to be
  464%     before   deleted   after    changed   rebalanced
  465deltable(-      , right   , <      , no        , no    ) :- !.
  466deltable(-      , left    , >      , no        , no    ) :- !.
  467deltable(<      , right   , -      , yes       , yes   ) :- !.
  468deltable(<      , left    , -      , yes       , no    ) :- !.
  469deltable(>      , right   , -      , yes       , no    ) :- !.
  470deltable(>      , left    , -      , yes       , yes   ) :- !.
  471% It depends on the tree pattern in avl_geq whether it really decreases.
  472
  473% Single and double tree rotations - these are common for insert and delete.
  474/* The patterns (>)-(>), (>)-( <), ( <)-( <) and ( <)-(>) on the LHS
  475   always change the tree height and these are the only patterns which can
  476   happen after an insertion. That's the reason why we can use a table only to
  477   decide the needed changes.
  478
  479   The patterns (>)-( -) and ( <)-( -) do not change the tree height. After a
  480   deletion any pattern can occur and so we return yes or no as a flag of a
  481   height change.  */
  482
  483
  484rebalance(no, t(K,V,_,L,R), B, t(K,V,B,L,R), Changed, Changed).
  485rebalance(yes, OldTree, _, NewTree, _, RealChange) :-
  486    avl_geq(OldTree, NewTree, RealChange).
  487
  488avl_geq(t(A,VA,>,Alpha,t(B,VB,>,Beta,Gamma)),
  489        t(B,VB,-,t(A,VA,-,Alpha,Beta),Gamma), yes) :- !.
  490avl_geq(t(A,VA,>,Alpha,t(B,VB,-,Beta,Gamma)),
  491        t(B,VB,<,t(A,VA,>,Alpha,Beta),Gamma), no) :- !.
  492avl_geq(t(B,VB,<,t(A,VA,<,Alpha,Beta),Gamma),
  493        t(A,VA,-,Alpha,t(B,VB,-,Beta,Gamma)), yes) :- !.
  494avl_geq(t(B,VB,<,t(A,VA,-,Alpha,Beta),Gamma),
  495        t(A,VA,>,Alpha,t(B,VB,<,Beta,Gamma)), no) :- !.
  496avl_geq(t(A,VA,>,Alpha,t(B,VB,<,t(X,VX,B1,Beta,Gamma),Delta)),
  497        t(X,VX,-,t(A,VA,B2,Alpha,Beta),t(B,VB,B3,Gamma,Delta)), yes) :-
  498    !,
  499    table2(B1, B2, B3).
  500avl_geq(t(B,VB,<,t(A,VA,>,Alpha,t(X,VX,B1,Beta,Gamma)),Delta),
  501        t(X,VX,-,t(A,VA,B2,Alpha,Beta),t(B,VB,B3,Gamma,Delta)), yes) :-
  502    !,
  503    table2(B1, B2, B3).
  504
  505table2(< ,- ,> ).
  506table2(> ,< ,- ).
  507table2(- ,- ,- ).
  508
  509
  510                 /*******************************
  511                 *            ERRORS            *
  512                 *******************************/
  513
  514:- multifile
  515    error:has_type/2.  516
  517error:has_type(assoc, X) :-
  518    (   X == t
  519    ->  true
  520    ;   compound(X),
  521        compound_name_arity(X, t, 5)
  522    )