Does SWI-Prolog have N+K-trees?

Help! Data Structure
5

It is always a bit of work to get the math correct. After a little playing, I get at:

:- debug(dyn).

dyn_new(Max, Dyn) :-
    Subs is msb(Max)+1,
    functor(Dyn, dyn, Subs).

dyn_access(I, Dyn, Value) :-
    must_be(positive_integer, I),
    I1 is msb(I),
    I11 is I1+1,
    I2 is I-(2**I1-1),
    debug(dyn, 'Located at index ~D in ~D', [I2, I11]),
    arg(I11, Dyn, A2),
    (   var(A2)
    ->  Len is 2**I1,
        debug(dyn, 'Created sub array of length ~D for ~D', [Len, I11]),
        functor(A2, s, Len)
    ;   true
    ),
    arg(I2, A2, Value).

Then we can run some tests and (by induction) conclude we are fine :slight_smile:

% Located at index 1 in 1
% Created sub array of length 1 for 1
X = dyn(s(1), _10312, _10314, _10316, _10318, _10320).

116 ?- dyn_new(32, X), dyn_access(2, X, 1).
% Located at index 1 in 2
% Created sub array of length 2 for 2
X = dyn(_10296, s(1, _10444), _10300, _10302, _10304, _10306).

117 ?- dyn_new(32, X), dyn_access(3, X, 1).
% Located at index 2 in 2
% Created sub array of length 2 for 2
X = dyn(_10296, s(_10442, 1), _10300, _10302, _10304, _10306).

118 ?- dyn_new(32, X), dyn_access(4, X, 1).
% Located at index 1 in 3
% Created sub array of length 4 for 3
X = dyn(_10300, _10302, s(1, _10448, _10450, _10452), _10306, _10308, _10310).
4 Likes