36
37:- module(nb_set,
38 [ empty_nb_set/1, 39 add_nb_set/2, 40 add_nb_set/3, 41 size_nb_set/2, 42 nb_set_to_list/2, 43 gen_nb_set/2 44 ]). 45:- use_module(library(debug), [assertion/1]).
64initial_capacity(4).
70empty_nb_set(NbSet) :-
71 initial_capacity(Capacity),
72 Empty = empty(1),
73 '$filled_array'(Buckets, buckets, Capacity, Empty),
74 NbSet = nb_set(Empty, Capacity, 0, Buckets).
84add_nb_set(Key, Set) :-
85 add_nb_set(Key, Set, _).
86add_nb_set(Key, Set, New) :-
87 Set = nb_set(Empty, Capacity, Size, Buckets),
88 key_hash(Key, Hash),
89 index(Hash, Capacity, KIndex),
90 arg(KIndex, Buckets, StoredKey),
91 ( same_term(StoredKey, Empty)
92 -> !,
93 New = true,
94 nb_setarg(KIndex, Buckets, Key),
95 NSize is Size+1,
96 nb_setarg(3, Set, NSize),
97 ( NSize > Capacity//2
98 -> rehash(Set)
99 ; true
100 )
101 ; Key =@= StoredKey
102 -> !,
103 New = false
104 ).
111index(Hash, Capacity, KIndex) :-
112 KIndex0 is (Hash mod Capacity) + 1,
113 next(KIndex0, Capacity, KIndex).
114
115next(KIndex, _, KIndex).
116next(KIndex0, Capacity, KIndex) :-
117 KIndex1 is 1+(KIndex0 mod Capacity),
118 next(KIndex1, Capacity, KIndex).
119
120rehash(Set) :-
121 Set = nb_set(Empty, Capacity, Size, Buckets),
122 NCapacity is Capacity*2,
123 '$filled_array'(NBuckets, buckets, NCapacity, Empty),
124 nb_setarg(2, Set, NCapacity),
125 nb_setarg(3, Set, 0),
126 nb_linkarg(4, Set, NBuckets),
127 forall(between(1, Capacity, I),
128 reinsert(I, Empty, Buckets, Set)),
129 arg(3, Set, NewSize),
130 assertion(NewSize == Size).
131
132:- det(reinsert/4). 133reinsert(KIndex, Empty, Buckets, Set) :-
134 arg(KIndex, Buckets, Key),
135 ( same_term(Key, Empty)
136 -> true
137 ; add_nb_set(Key, Set, true)
138 ).
145key_hash(Key, Hash) :-
146 variant_hash(Key, Hash).
155nb_set_to_list(NBSet, Set),
156 NBSet = nb_set(Empty, Capacity, _Size, Buckets) =>
157 buckets_to_list(1, Empty, Capacity, Buckets, List0),
158 sort(List0, Set).
159
160buckets_to_list(KIndex, Empty, Capacity, Buckets, List) :-
161 ( arg(KIndex, Buckets, Key)
162 -> ( same_term(Empty, Key)
163 -> KIndex1 is KIndex+1,
164 buckets_to_list(KIndex1, Empty, Capacity, Buckets, List)
165 ; List = [Key|List1],
166 KIndex1 is KIndex+1,
167 buckets_to_list(KIndex1, Empty, Capacity, Buckets, List1)
168 )
169 ; List = []
170 ).
176gen_nb_set(nb_set(Empty, Capacity, _Size, Buckets), Key) =>
177 between(1, Capacity, KIndex),
178 arg(KIndex, Buckets, Key),
179 \+ same_term(Empty, Key).
185size_nb_set(nb_set(_Empty, _Capacity, Sz, _Buckets), Size) =>
186 Size = Sz
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. The next iteration used open hash tables, while the current incarnation uses closed hash tables, providing better perfomance and less space usage.