35
36:- module(nb_set,
37 [ empty_nb_set/1, 38 add_nb_set/2, 39 add_nb_set/3, 40 gen_nb_set/2, 41 size_nb_set/2, 42 nb_set_to_list/2 43 ]). 44:- autoload(library(lists),[member/2,append/2]). 45:- autoload(library(terms),[term_factorized/3]).
63initial_size(32).
69empty_nb_set(nb_set(Buckets, 0)) :-
70 initial_size(Size),
71 '$filled_array'(Buckets, buckets, Size, []).
86add_nb_set(Key, Set) :-
87 add_nb_set(Key, Set, _).
88add_nb_set(Key, Set, New) :-
89 arg(1, Set, Buckets),
90 compound_name_arity(Buckets, _, BCount),
91 hash_key(Key, BCount, Hash),
92 arg(Hash, Buckets, Bucket),
93 ( member(X, Bucket),
94 Key =@= X
95 -> New = false
96 ; New = true,
97 duplicate_term(Key, Copy),
98 nb_linkarg(Hash, Buckets, [Copy|Bucket]),
99 arg(2, Set, Size0),
100 Size is Size0+1,
101 nb_setarg(2, Set, Size),
102 ( Size > BCount
103 -> rehash(Set)
104 ; true
105 )
106 ).
115:- if(catch((A = f(A), variant_hash(A,_)), _, fail)). 116hash_key(Term, BCount, Key) :-
117 variant_hash(Term, IntHash),
118 Key is (IntHash mod BCount)+1.
119:- else. 120hash_key(Term, BCount, Key) :-
121 acyclic_term(Key),
122 !,
123 variant_hash(Term, IntHash),
124 Key is (IntHash mod BCount)+1.
125hash_key(Term, BCount, Key) :-
126 term_factorized(Term, Skeleton, Substiution),
127 variant_hash(Skeleton+Substiution, IntHash),
128 Key is (IntHash mod BCount)+1.
129:- endif. 130
131rehash(Set) :-
132 arg(1, Set, Buckets0),
133 compound_name_arity(Buckets0, Name, Arity0),
134 Arity is Arity0*2,
135 '$filled_array'(Buckets, Name, Arity, []),
136 nb_setarg(1, Set, Buckets),
137 nb_setarg(2, Set, 0),
138 ( arg(_, Buckets0, Chain),
139 member(Key, Chain),
140 add_nb_set(Key, Set, _),
141 fail
142 ; true
143 ).
150nb_set_to_list(nb_set(Buckets, _Size), OrdSet) :-
151 compound_name_arguments(Buckets, _, Args),
152 append(Args, List),
153 sort(List, OrdSet).
159gen_nb_set(Set, Key) :-
160 nb_set_to_list(Set, OrdSet),
161 member(Key, OrdSet).
167size_nb_set(nb_set(_, Size), Size)
Non-backtrackable sets
This library provides a non-backtrackabe set of terms that are variants of each other. It is primarily intended to implement distinct/1 from
library(solution_sequences)
. The set is implemented as a hash table that is built using non-backtrackable primitives, notably nb_setarg/3.The original version of this library used binary trees which provides immediate ordering. As the trees were not balanced, performance could get really poor. The complexity of balancing trees using non-backtrackable primitives is too high.