1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2005-2015, VU University Amsterdam 7 All rights reserved. 8 9 Redistribution and use in source and binary forms, with or without 10 modification, are permitted provided that the following conditions 11 are met: 12 13 1. Redistributions of source code must retain the above copyright 14 notice, this list of conditions and the following disclaimer. 15 16 2. Redistributions in binary form must reproduce the above copyright 17 notice, this list of conditions and the following disclaimer in 18 the documentation and/or other materials provided with the 19 distribution. 20 21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 29 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 31 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 32 POSSIBILITY OF SUCH DAMAGE. 33*/ 34 35:- module(nb_set, 36 [ empty_nb_set/1, % -EmptySet 37 add_nb_set/2, % +Key, !Set 38 add_nb_set/3, % +Key, !Set, ?New 39 gen_nb_set/2, % +Set, -Key 40 size_nb_set/2, % +Set, -Size 41 nb_set_to_list/2 % +Set, -List 42 ]). 43:- use_module(library(lists)). 44:- use_module(library(terms)). 45:- use_module(library(apply_macros), []). 46 47/** <module> Non-backtrackable sets 48 49This library provides a non-backtrackabe _set_ of terms that are 50variants of each other. It is primarily intended to implement distinct/1 51from library(solution_sequences). The set is implemented as a hash table 52that is built using non-backtrackable primitives, notably nb_setarg/3. 53 54The original version of this library used binary trees which provides 55immediate ordering. As the trees were not balanced, performance could 56get really poor. The complexity of balancing trees using 57non-backtrackable primitives is too high. 58 59@author Jan Wielemaker 60*/ 61 62initial_size(32). % initial hash-table size 63 64%! empty_nb_set(-Set) 65% 66% Create an empty non-backtrackable set. 67 68empty_nb_set(nb_set(Buckets, 0)) :- 69 initial_size(Size), 70 '$filled_array'(Buckets, buckets, Size, []). 71 72%! add_nb_set(+Key, !Set) is det. 73%! add_nb_set(+Key, !Set, ?New) is semidet. 74%! add_nb_set(+Key, !Set, ?New) is semidet. 75% 76% Insert Key into the set. If a variant (see =@=/2) of Key is 77% already in the set, the set is unchanged and New is unified with 78% `false`. Otherwise, New is unified with `true` and a _copy of_ 79% Key is added to the set. 80% 81% @tbd Computing the hash for cyclic terms is performed with 82% the help of term_factorized/3, which performs rather 83% poorly. 84 85add_nb_set(Key, Set) :- 86 add_nb_set(Key, Set, _). 87add_nb_set(Key, Set, New) :- 88 arg(1, Set, Buckets), 89 compound_name_arity(Buckets, _, BCount), 90 hash_key(Key, BCount, Hash), 91 arg(Hash, Buckets, Bucket), 92 ( member(X, Bucket), 93 Key =@= X 94 -> New = false 95 ; New = true, 96 duplicate_term(Key, Copy), 97 nb_linkarg(Hash, Buckets, [Copy|Bucket]), 98 arg(2, Set, Size0), 99 Size is Size0+1, 100 nb_setarg(2, Set, Size), 101 ( Size > BCount 102 -> rehash(Set) 103 ; true 104 ) 105 ). 106 107%! hash_key(+Term, +BucketCount, -Key) is det. 108% 109% Compute a hash for Term. Note that variant_hash/2 currently does 110% not handle cyclic terms, so use term_factorized/3 to get rid of 111% the cycles. This means that this library is rather slow when 112% cyclic terms are involved. 113 114:- if(catch((A = f(A), variant_hash(A,_)), error(type_error(_,_),_), fail)). 115hash_key(Term, BCount, Key) :- 116 variant_hash(Term, IntHash), 117 Key is (IntHash mod BCount)+1. 118:- else. 119hash_key(Term, BCount, Key) :- 120 acyclic_term(Key), 121 !, 122 variant_hash(Term, IntHash), 123 Key is (IntHash mod BCount)+1. 124hash_key(Term, BCount, Key) :- 125 term_factorized(Term, Skeleton, Substiution), 126 variant_hash(Skeleton+Substiution, IntHash), 127 Key is (IntHash mod BCount)+1. 128:- endif. 129 130rehash(Set) :- 131 arg(1, Set, Buckets0), 132 compound_name_arity(Buckets0, Name, Arity0), 133 Arity is Arity0*2, 134 '$filled_array'(Buckets, Name, Arity, []), 135 nb_setarg(1, Set, Buckets), 136 nb_setarg(2, Set, 0), 137 forall(( arg(_, Buckets0, Chain), 138 member(Key, Chain) 139 ), 140 add_nb_set(Key, Set, _)). 141 142%! nb_set_to_list(+Set, -List) 143% 144% Get the elements of a an nb_set. List is sorted to the standard 145% order of terms. 146 147nb_set_to_list(nb_set(Buckets, _Size), OrdSet) :- 148 compound_name_arguments(Buckets, _, Args), 149 append(Args, List), 150 sort(List, OrdSet). 151 152%! gen_nb_set(+Set, -Key) 153% 154% Enumerate the members of a set in the standard order of terms. 155 156gen_nb_set(Set, Key) :- 157 nb_set_to_list(Set, OrdSet), 158 member(Key, OrdSet). 159 160%! size_nb_set(+Set, -Size) 161% 162% Unify Size with the number of elements in the set 163 164size_nb_set(nb_set(_, Size), Size).