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@see            library(pairs), library(rbtrees)
   65@author         R.A.O'Keefe, L.Damas, V.S.Costa and Jan Wielemaker
   66*/
   67
   68:- meta_predicate
   69    map_assoc(1, ?),
   70    map_assoc(2, ?, ?).   71
   72%!  empty_assoc(?Assoc) is semidet.
   73%
   74%   Is true if Assoc is the empty association list.
   75
   76empty_assoc(t).
   77
   78%!  assoc_to_list(+Assoc, -Pairs) is det.
   79%
   80%   Translate Assoc to a list Pairs of Key-Value pairs.  The keys
   81%   in Pairs are sorted in ascending order.
   82
   83assoc_to_list(Assoc, List) :-
   84    assoc_to_list(Assoc, List, []).
   85
   86assoc_to_list(t(Key,Val,_,L,R), List, Rest) :-
   87    assoc_to_list(L, List, [Key-Val|More]),
   88    assoc_to_list(R, More, Rest).
   89assoc_to_list(t, List, List).
   90
   91
   92%!  assoc_to_keys(+Assoc, -Keys) is det.
   93%
   94%   True if Keys is the list of keys   in Assoc. The keys are sorted
   95%   in ascending order.
   96
   97assoc_to_keys(Assoc, List) :-
   98    assoc_to_keys(Assoc, List, []).
   99
  100assoc_to_keys(t(Key,_,_,L,R), List, Rest) :-
  101    assoc_to_keys(L, List, [Key|More]),
  102    assoc_to_keys(R, More, Rest).
  103assoc_to_keys(t, List, List).
  104
  105
  106%!  assoc_to_values(+Assoc, -Values) is det.
  107%
  108%   True if Values is the  list  of   values  in  Assoc.  Values are
  109%   ordered in ascending  order  of  the   key  to  which  they were
  110%   associated.  Values may contain duplicates.
  111
  112assoc_to_values(Assoc, List) :-
  113    assoc_to_values(Assoc, List, []).
  114
  115assoc_to_values(t(_,Value,_,L,R), List, Rest) :-
  116    assoc_to_values(L, List, [Value|More]),
  117    assoc_to_values(R, More, Rest).
  118assoc_to_values(t, List, List).
  119
  120%!  is_assoc(+Assoc) is semidet.
  121%
  122%   True if Assoc is an association list. This predicate checks
  123%   that the structure is valid, elements are in order, and tree
  124%   is balanced to the extent guaranteed by AVL trees.  I.e.,
  125%   branches of each subtree differ in depth by at most 1.
  126
  127is_assoc(Assoc) :-
  128    is_assoc(Assoc, _Min, _Max, _Depth).
  129
  130is_assoc(t,X,X,0) :- !.
  131is_assoc(t(K,_,-,t,t),K,K,1) :- !, ground(K).
  132is_assoc(t(K,_,>,t,t(RK,_,-,t,t)),K,RK,2) :-
  133    % Ensure right side Key is 'greater' than K
  134    !, ground((K,RK)), K @< RK.
  135
  136is_assoc(t(K,_,<,t(LK,_,-,t,t),t),LK,K,2) :-
  137    % Ensure left side Key is 'less' than K
  138    !, ground((LK,K)), LK @< K.
  139
  140is_assoc(t(K,_,B,L,R),Min,Max,Depth) :-
  141    is_assoc(L,Min,LMax,LDepth),
  142    is_assoc(R,RMin,Max,RDepth),
  143    % Ensure Balance matches depth
  144    compare(Rel,RDepth,LDepth),
  145    balance(Rel,B),
  146    % Ensure ordering
  147    ground((LMax,K,RMin)),
  148    LMax @< K,
  149    K @< RMin,
  150    Depth is max(LDepth, RDepth)+1.
  151
  152% Private lookup table matching comparison operators to Balance operators used in tree
  153balance(=,-).
  154balance(<,<).
  155balance(>,>).
  156
  157
  158%!  gen_assoc(?Key, +Assoc, ?Value) is nondet.
  159%
  160%   True if Key-Value is an association in Assoc. Enumerates keys in
  161%   ascending order on backtracking.
  162%
  163%   @see get_assoc/3.
  164
  165gen_assoc(Key, Assoc, Value) :-
  166    (   ground(Key)
  167    ->  get_assoc(Key, Assoc, Value)
  168    ;   gen_assoc_(Key, Assoc, Value)
  169    ).
  170
  171gen_assoc_(Key, t(_,_,_,L,_), Val) :-
  172    gen_assoc_(Key, L, Val).
  173gen_assoc_(Key, t(Key,Val,_,_,_), Val).
  174gen_assoc_(Key, t(_,_,_,_,R), Val) :-
  175    gen_assoc_(Key, R, Val).
  176
  177
  178%!  get_assoc(+Key, +Assoc, -Value) is semidet.
  179%
  180%   True if Key-Value is an association in Assoc.
  181%
  182%   @error type_error(assoc, Assoc) if Assoc is not an association list.
  183
  184get_assoc(Key, Assoc, Val) :-
  185    must_be(assoc, Assoc),
  186    get_assoc_(Key, Assoc, Val).
  187
  188:- if(current_predicate('$btree_find_node'/5)).  189get_assoc_(Key, Tree, Val) :-
  190    Tree \== t,
  191    '$btree_find_node'(Key, Tree, 0x010405, Node, =),
  192    arg(2, Node, Val).
  193:- else.  194get_assoc_(Key, t(K,V,_,L,R), Val) :-
  195    compare(Rel, Key, K),
  196    get_assoc(Rel, Key, V, L, R, Val).
  197
  198get_assoc(=, _, Val, _, _, Val).
  199get_assoc(<, Key, _, Tree, _, Val) :-
  200    get_assoc(Key, Tree, Val).
  201get_assoc(>, Key, _, _, Tree, Val) :-
  202    get_assoc(Key, Tree, Val).
  203:- endif.  204
  205
  206%!  get_assoc(+Key, +Assoc0, ?Val0, ?Assoc, ?Val) is semidet.
  207%
  208%   True if Key-Val0 is in Assoc0 and Key-Val is in Assoc.
  209
  210get_assoc(Key, t(K,V,B,L,R), Val, t(K,NV,B,NL,NR), NVal) :-
  211    compare(Rel, Key, K),
  212    get_assoc(Rel, Key, V, L, R, Val, NV, NL, NR, NVal).
  213
  214get_assoc(=, _, Val, L, R, Val, NVal, L, R, NVal).
  215get_assoc(<, Key, V, L, R, Val, V, NL, R, NVal) :-
  216    get_assoc(Key, L, Val, NL, NVal).
  217get_assoc(>, Key, V, L, R, Val, V, L, NR, NVal) :-
  218    get_assoc(Key, R, Val, NR, NVal).
  219
  220
  221%!  list_to_assoc(+Pairs, -Assoc) is det.
  222%
  223%   Create an association from a list Pairs of Key-Value pairs. List
  224%   must not contain duplicate keys.
  225%
  226%   @error domain_error(unique_key_pairs, List) if List contains duplicate keys
  227
  228list_to_assoc(List, Assoc) :-
  229    (  List = [] -> Assoc = t
  230    ;  keysort(List, Sorted),
  231           (  ord_pairs(Sorted)
  232           -> length(Sorted, N),
  233              list_to_assoc(N, Sorted, [], _, Assoc)
  234           ;  domain_error(unique_key_pairs, List)
  235           )
  236    ).
  237
  238list_to_assoc(1, [K-V|More], More, 1, t(K,V,-,t,t)) :- !.
  239list_to_assoc(2, [K1-V1,K2-V2|More], More, 2, t(K2,V2,<,t(K1,V1,-,t,t),t)) :- !.
  240list_to_assoc(N, List, More, Depth, t(K,V,Balance,L,R)) :-
  241    N0 is N - 1,
  242    RN is N0 div 2,
  243    Rem is N0 mod 2,
  244    LN is RN + Rem,
  245    list_to_assoc(LN, List, [K-V|Upper], LDepth, L),
  246    list_to_assoc(RN, Upper, More, RDepth, R),
  247    Depth is LDepth + 1,
  248    compare(B, RDepth, LDepth), balance(B, Balance).
  249
  250%!  ord_list_to_assoc(+Pairs, -Assoc) is det.
  251%
  252%   Assoc is created from an ordered list Pairs of Key-Value
  253%   pairs. The pairs must occur in strictly ascending order of
  254%   their keys.
  255%
  256%   @error domain_error(key_ordered_pairs, List) if pairs are not ordered.
  257
  258ord_list_to_assoc(Sorted, Assoc) :-
  259    (  Sorted = [] -> Assoc = t
  260    ;  (  ord_pairs(Sorted)
  261           -> length(Sorted, N),
  262              list_to_assoc(N, Sorted, [], _, Assoc)
  263           ;  domain_error(key_ordered_pairs, Sorted)
  264           )
  265    ).
  266
  267%!  ord_pairs(+Pairs) is semidet
  268%
  269%   True if Pairs is a list of Key-Val pairs strictly ordered by key.
  270
  271ord_pairs([K-_V|Rest]) :-
  272    ord_pairs(Rest, K).
  273ord_pairs([], _K).
  274ord_pairs([K-_V|Rest], K0) :-
  275    K0 @< K,
  276    ord_pairs(Rest, K).
  277
  278%!  map_assoc(:Pred, +Assoc) is semidet.
  279%
  280%   True if Pred(Value) is true for all values in Assoc.
  281
  282map_assoc(Pred, T) :-
  283    map_assoc_(T, Pred).
  284
  285map_assoc_(t, _).
  286map_assoc_(t(_,Val,_,L,R), Pred) :-
  287    map_assoc_(L, Pred),
  288    call(Pred, Val),
  289    map_assoc_(R, Pred).
  290
  291%!  map_assoc(:Pred, +Assoc0, ?Assoc) is semidet.
  292%
  293%   Map corresponding values. True if Assoc is Assoc0 with Pred
  294%   applied to all corresponding pairs of of values.
  295
  296map_assoc(Pred, T0, T) :-
  297    map_assoc_(T0, Pred, T).
  298
  299map_assoc_(t, _, t).
  300map_assoc_(t(Key,Val,B,L0,R0), Pred, t(Key,Ans,B,L1,R1)) :-
  301    map_assoc_(L0, Pred, L1),
  302    call(Pred, Val, Ans),
  303    map_assoc_(R0, Pred, R1).
  304
  305
  306%!  max_assoc(+Assoc, -Key, -Value) is semidet.
  307%
  308%   True if Key-Value is in Assoc and Key is the largest key.
  309
  310max_assoc(t(K,V,_,_,R), Key, Val) :-
  311    max_assoc(R, K, V, Key, Val).
  312
  313max_assoc(t, K, V, K, V).
  314max_assoc(t(K,V,_,_,R), _, _, Key, Val) :-
  315    max_assoc(R, K, V, Key, Val).
  316
  317
  318%!  min_assoc(+Assoc, -Key, -Value) is semidet.
  319%
  320%   True if Key-Value is in assoc and Key is the smallest key.
  321
  322min_assoc(t(K,V,_,L,_), Key, Val) :-
  323    min_assoc(L, K, V, Key, Val).
  324
  325min_assoc(t, K, V, K, V).
  326min_assoc(t(K,V,_,L,_), _, _, Key, Val) :-
  327    min_assoc(L, K, V, Key, Val).
  328
  329
  330%!  put_assoc(+Key, +Assoc0, +Value, -Assoc) is det.
  331%
  332%   Assoc is Assoc0, except that Key is associated with
  333%   Value. This can be used to insert and change associations.
  334
  335put_assoc(Key, A0, Value, A) :-
  336    insert(A0, Key, Value, A, _).
  337
  338insert(t, Key, Val, t(Key,Val,-,t,t), yes).
  339insert(t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  340    compare(Rel, K, Key),
  341    insert(Rel, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged).
  342
  343insert(=, t(Key,_,B,L,R), _, V, t(Key,V,B,L,R), no).
  344insert(<, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  345    insert(L, K, V, NewL, LeftHasChanged),
  346    adjust(LeftHasChanged, t(Key,Val,B,NewL,R), left, NewTree, WhatHasChanged).
  347insert(>, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  348    insert(R, K, V, NewR, RightHasChanged),
  349    adjust(RightHasChanged, t(Key,Val,B,L,NewR), right, NewTree, WhatHasChanged).
  350
  351adjust(no, Oldree, _, Oldree, no).
  352adjust(yes, t(Key,Val,B0,L,R), LoR, NewTree, WhatHasChanged) :-
  353    table(B0, LoR, B1, WhatHasChanged, ToBeRebalanced),
  354    rebalance(ToBeRebalanced, t(Key,Val,B0,L,R), B1, NewTree, _, _).
  355
  356%     balance  where     balance  whole tree  to be
  357%     before   inserted  after    increased   rebalanced
  358table(-      , left    , <      , yes       , no    ) :- !.
  359table(-      , right   , >      , yes       , no    ) :- !.
  360table(<      , left    , -      , no        , yes   ) :- !.
  361table(<      , right   , -      , no        , no    ) :- !.
  362table(>      , left    , -      , no        , no    ) :- !.
  363table(>      , right   , -      , no        , yes   ) :- !.
  364
  365%!  del_min_assoc(+Assoc0, ?Key, ?Val, -Assoc) is semidet.
  366%
  367%   True if Key-Value  is  in  Assoc0   and  Key  is  the smallest key.
  368%   Assoc is Assoc0 with Key-Value   removed. Warning: This will
  369%   succeed with _no_ bindings for Key or Val if Assoc0 is empty.
  370
  371del_min_assoc(Tree, Key, Val, NewTree) :-
  372    del_min_assoc(Tree, Key, Val, NewTree, _DepthChanged).
  373
  374del_min_assoc(t(Key,Val,_B,t,R), Key, Val, R, yes) :- !.
  375del_min_assoc(t(K,V,B,L,R), Key, Val, NewTree, Changed) :-
  376    del_min_assoc(L, Key, Val, NewL, LeftChanged),
  377    deladjust(LeftChanged, t(K,V,B,NewL,R), left, NewTree, Changed).
  378
  379%!  del_max_assoc(+Assoc0, ?Key, ?Val, -Assoc) is semidet.
  380%
  381%   True if Key-Value  is  in  Assoc0   and  Key  is  the greatest key.
  382%   Assoc is Assoc0 with Key-Value   removed. Warning: This will
  383%   succeed with _no_ bindings for Key or Val if Assoc0 is empty.
  384
  385del_max_assoc(Tree, Key, Val, NewTree) :-
  386    del_max_assoc(Tree, Key, Val, NewTree, _DepthChanged).
  387
  388del_max_assoc(t(Key,Val,_B,L,t), Key, Val, L, yes) :- !.
  389del_max_assoc(t(K,V,B,L,R), Key, Val, NewTree, Changed) :-
  390    del_max_assoc(R, Key, Val, NewR, RightChanged),
  391    deladjust(RightChanged, t(K,V,B,L,NewR), right, NewTree, Changed).
  392
  393%!  del_assoc(+Key, +Assoc0, ?Value, -Assoc) is semidet.
  394%
  395%   True if Key-Value is  in  Assoc0.   Assoc  is  Assoc0 with
  396%   Key-Value removed.
  397
  398del_assoc(Key, A0, Value, A) :-
  399    delete(A0, Key, Value, A, _).
  400
  401% delete(+Subtree, +SearchedKey, ?SearchedValue, ?SubtreeOut, ?WhatHasChanged)
  402delete(t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  403    compare(Rel, K, Key),
  404    delete(Rel, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged).
  405
  406% delete(+KeySide, +Subtree, +SearchedKey, ?SearchedValue, ?SubtreeOut, ?WhatHasChanged)
  407% KeySide is an operator {<,=,>} indicating which branch should be searched for the key.
  408% WhatHasChanged {yes,no} indicates whether the NewTree has changed in depth.
  409delete(=, t(Key,Val,_B,t,R), Key, Val, R, yes) :- !.
  410delete(=, t(Key,Val,_B,L,t), Key, Val, L, yes) :- !.
  411delete(=, t(Key,Val,>,L,R), Key, Val, NewTree, WhatHasChanged) :-
  412    % Rh tree is deeper, so rotate from R to L
  413    del_min_assoc(R, K, V, NewR, RightHasChanged),
  414    deladjust(RightHasChanged, t(K,V,>,L,NewR), right, NewTree, WhatHasChanged),
  415    !.
  416delete(=, t(Key,Val,B,L,R), Key, Val, NewTree, WhatHasChanged) :-
  417    % Rh tree is not deeper, so rotate from L to R
  418    del_max_assoc(L, K, V, NewL, LeftHasChanged),
  419    deladjust(LeftHasChanged, t(K,V,B,NewL,R), left, NewTree, WhatHasChanged),
  420    !.
  421
  422delete(<, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  423    delete(L, K, V, NewL, LeftHasChanged),
  424    deladjust(LeftHasChanged, t(Key,Val,B,NewL,R), left, NewTree, WhatHasChanged).
  425delete(>, t(Key,Val,B,L,R), K, V, NewTree, WhatHasChanged) :-
  426    delete(R, K, V, NewR, RightHasChanged),
  427    deladjust(RightHasChanged, t(Key,Val,B,L,NewR), right, NewTree, WhatHasChanged).
  428
  429deladjust(no, OldTree, _, OldTree, no).
  430deladjust(yes, t(Key,Val,B0,L,R), LoR, NewTree, RealChange) :-
  431    deltable(B0, LoR, B1, WhatHasChanged, ToBeRebalanced),
  432    rebalance(ToBeRebalanced, t(Key,Val,B0,L,R), B1, NewTree, WhatHasChanged, RealChange).
  433
  434%     balance  where     balance  whole tree  to be
  435%     before   deleted   after    changed   rebalanced
  436deltable(-      , right   , <      , no        , no    ) :- !.
  437deltable(-      , left    , >      , no        , no    ) :- !.
  438deltable(<      , right   , -      , yes       , yes   ) :- !.
  439deltable(<      , left    , -      , yes       , no    ) :- !.
  440deltable(>      , right   , -      , yes       , no    ) :- !.
  441deltable(>      , left    , -      , yes       , yes   ) :- !.
  442% It depends on the tree pattern in avl_geq whether it really decreases.
  443
  444% Single and double tree rotations - these are common for insert and delete.
  445/* The patterns (>)-(>), (>)-( <), ( <)-( <) and ( <)-(>) on the LHS
  446   always change the tree height and these are the only patterns which can
  447   happen after an insertion. That's the reason why we can use a table only to
  448   decide the needed changes.
  449
  450   The patterns (>)-( -) and ( <)-( -) do not change the tree height. After a
  451   deletion any pattern can occur and so we return yes or no as a flag of a
  452   height change.  */
  453
  454
  455rebalance(no, t(K,V,_,L,R), B, t(K,V,B,L,R), Changed, Changed).
  456rebalance(yes, OldTree, _, NewTree, _, RealChange) :-
  457    avl_geq(OldTree, NewTree, RealChange).
  458
  459avl_geq(t(A,VA,>,Alpha,t(B,VB,>,Beta,Gamma)),
  460        t(B,VB,-,t(A,VA,-,Alpha,Beta),Gamma), yes) :- !.
  461avl_geq(t(A,VA,>,Alpha,t(B,VB,-,Beta,Gamma)),
  462        t(B,VB,<,t(A,VA,>,Alpha,Beta),Gamma), no) :- !.
  463avl_geq(t(B,VB,<,t(A,VA,<,Alpha,Beta),Gamma),
  464        t(A,VA,-,Alpha,t(B,VB,-,Beta,Gamma)), yes) :- !.
  465avl_geq(t(B,VB,<,t(A,VA,-,Alpha,Beta),Gamma),
  466        t(A,VA,>,Alpha,t(B,VB,<,Beta,Gamma)), no) :- !.
  467avl_geq(t(A,VA,>,Alpha,t(B,VB,<,t(X,VX,B1,Beta,Gamma),Delta)),
  468        t(X,VX,-,t(A,VA,B2,Alpha,Beta),t(B,VB,B3,Gamma,Delta)), yes) :-
  469    !,
  470    table2(B1, B2, B3).
  471avl_geq(t(B,VB,<,t(A,VA,>,Alpha,t(X,VX,B1,Beta,Gamma)),Delta),
  472        t(X,VX,-,t(A,VA,B2,Alpha,Beta),t(B,VB,B3,Gamma,Delta)), yes) :-
  473    !,
  474    table2(B1, B2, B3).
  475
  476table2(< ,- ,> ).
  477table2(> ,< ,- ).
  478table2(- ,- ,- ).
  479
  480
  481                 /*******************************
  482                 *            ERRORS            *
  483                 *******************************/
  484
  485:- multifile
  486    error:has_type/2.  487
  488error:has_type(assoc, X) :-
  489    (   X == t
  490    ->  true
  491    ;   compound(X),
  492        functor(X, t, 5)
  493    )