This is the clustered-intset Reference Manual, version 0.0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed Mar 15 05:40:12 2023 GMT+0.
The main system appears first, followed by any subsystem dependency.
clustered-intsetImplements a non-negative keyed set of integers favoring clustered keys.
Dave Tenny
MIT
0.0.1
alexandria (system).
package.lisp (file).
clustered-intset.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
clustered-intset/clustered-intset.asdclustered-intset/package.lispclustered-intset/clustered-intset.lispclustered-intset/clustered-intset.asdclustered-intset (system).
clustered-intset/clustered-intset.lisppackage.lisp (file).
clustered-intset (system).
add (function).
advance (function).
containsp (function).
count (function).
delete (function).
first (function).
intset->list (function).
intset->vector (function).
iterator (function).
iterator (structure).
make-intset (function).
map-intset (function).
map-sorted-intset (function).
next (function).
seq->intset (function).
%make-intset (function).
+fixnum-bits+ (constant).
copy-intset (function).
copy-iterator (function).
first-value (function).
fix-mod-type (type).
ht-key-filter (function).
initiate-new-ht-key (function).
intset (structure).
intset-count (reader).
(setf intset-count) (writer).
intset-ht (reader).
intset-p (function).
iterator-current-bit-position (reader).
(setf iterator-current-bit-position) (writer).
iterator-current-ht-key (reader).
(setf iterator-current-ht-key) (writer).
iterator-current-ht-value (reader).
(setf iterator-current-ht-value) (writer).
iterator-descending (reader).
(setf iterator-descending) (writer).
iterator-ending-with (reader).
(setf iterator-ending-with) (writer).
iterator-ht (reader).
(setf iterator-ht) (writer).
iterator-intset (reader).
(setf iterator-intset) (writer).
iterator-next-bit-value (function).
iterator-next-key-value (function).
iterator-p (function).
iterator-remaining-ht-keys (reader).
(setf iterator-remaining-ht-keys) (writer).
iterator-starting-with (reader).
(setf iterator-starting-with) (writer).
iterator-state (reader).
(setf iterator-state) (writer).
iterator-value-qualifies-fn (reader).
(setf iterator-value-qualifies-fn) (writer).
key-type (type).
make-iterator (function).
next-ascending-key (function).
next-value (function).
next-value-for-ht-key (function).
some-ht-val (function).
value-predicate (function).
value-type (type).
with-hash-kv (macro).
Packages are listed by definition order.
clustered-intsetHash based int-set that is slightly more efficient for clustered keys
such as a set of integer primary key values from a database.
All keys must be non-negative integers.
common-lisp.
add (function).
advance (function).
containsp (function).
count (function).
delete (function).
first (function).
intset->list (function).
intset->vector (function).
iterator (function).
iterator (structure).
make-intset (function).
map-intset (function).
map-sorted-intset (function).
next (function).
seq->intset (function).
%make-intset (function).
+fixnum-bits+ (constant).
copy-intset (function).
copy-iterator (function).
first-value (function).
fix-mod-type (type).
ht-key-filter (function).
initiate-new-ht-key (function).
intset (structure).
intset-count (reader).
(setf intset-count) (writer).
intset-ht (reader).
intset-p (function).
iterator-current-bit-position (reader).
(setf iterator-current-bit-position) (writer).
iterator-current-ht-key (reader).
(setf iterator-current-ht-key) (writer).
iterator-current-ht-value (reader).
(setf iterator-current-ht-value) (writer).
iterator-descending (reader).
(setf iterator-descending) (writer).
iterator-ending-with (reader).
(setf iterator-ending-with) (writer).
iterator-ht (reader).
(setf iterator-ht) (writer).
iterator-intset (reader).
(setf iterator-intset) (writer).
iterator-next-bit-value (function).
iterator-next-key-value (function).
iterator-p (function).
iterator-remaining-ht-keys (reader).
(setf iterator-remaining-ht-keys) (writer).
iterator-starting-with (reader).
(setf iterator-starting-with) (writer).
iterator-state (reader).
(setf iterator-state) (writer).
iterator-value-qualifies-fn (reader).
(setf iterator-value-qualifies-fn) (writer).
key-type (type).
make-iterator (function).
next-ascending-key (function).
next-value (function).
next-value-for-ht-key (function).
some-ht-val (function).
value-predicate (function).
value-type (type).
with-hash-kv (macro).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Add non-negative integer ’k’ to the the intset previously created with ‘make-intset‘. Return true if ’k’ was added, nil if ’k’ was already present.
Advance an iterator returned by ‘iterator‘. Return the next integer value in the iteration, or nil if there are no more values.
Return T if the non-negative integer ’k’ is a member of the specified intset, NIL otherwise.
Return the count of integers held by the intset. Named for sequence-like compatibiltiy.
Remove non-negative integer ’k’ from the intset previously created with ‘make-intset‘. Return true if ’k’ was removed, nil if ’k’ was already absent.
Return the smallest valued integer in the intset, or NIL if there are no members. This is not an efficient implementation, it is O(n).
Accumulate all members of the intset into a list and return it.
DIRECTION may be one of:
:UNORDERED (the default), which produces unordered results as efficiently as possible.
:ASCENDING, which produces intset members in ascending order.
:DESCENDING, which produces intset members in descending order.
Accumulate all members of the intset into a vector and return it.
VECTOR may be one of:
- nil, in which case a SIMPLE-VECTOR will be allocated, filled, and returned.
- a SIMPLE-VECTOR (i.e. ‘simple-vector-p‘ is true for the vector)
in which case elements are added from slots zero to N-1
where N is the number of elements in the intset. It is an error to specify an array
of insufficient size in this case.
- a non-adjustable vector with a fill-pointer, in which case elements are added as by
‘vector-push‘. Note that vector-push does not yield errors if the array would overflow,
it does nothing.
- a adjustable vector with a fill pointer, in which case elements are added as by
‘vector-push-extend‘.
Note that you can determine the size of the array to preallocate in full by allocating
‘(count intset)‘ elements.
DIRECTION may be one of:
:UNORDERED (the default), which produces unordered results as efficiently as possible.
:ASCENDING, which produces intset members in ascending order.
:DESCENDING, which produces intset members in descending order.
Creates and returns an unidirectional iterator for ordered traversal of the intset.
The iterator is called with ‘(advance <iterator>)‘ until it returns nil.
E.g. (loop with iterator = (iterator intset)
as value = (advance iterator)
while value
do ... something with value ...)
Values returned by ADVANCE will be ascending or descending according to the value of
DESCENDING. By default, iteration proceeds with all intset values in ascending order.
If DESCENDING is true, iterataion proceeds in descending order. As explained below,
DESCENDING affects comparison of STARTING-WITH and ENDING-WITH values.
A single iterator is always unidirectional
STARTING-WITH, if specified, is an inclusive value limiting the iteration to
start to the first value equal to or (> if DESCENDING, < if not DESCENDING) the value.
ENDING-WITH, is specified, is an exclusive value limiting the iteration
range end to the first value (> if DESCENDING, < if not DESCENDING) the value.
If both STARTING-WITH and ENDING-WITH are supplied and overlap in semantically incompatible
ways an error will be signalled, e.g.
‘(iterator intset :starting-with 1 :ending-with 1)‘ => ERROR
The intset from which the iterator was created may be updated while iterating.
It is undefined whether newly added values will be produced by new calls to ADVANCE.
If a member k is deleted from the intset undergoing iteration after the iterator
is created, it will not appear in any ADVANCE calls after deletion.
Create an empty int-set.
If you’d like to create an intset with an input sequence see SEQ->INTSET.
:size - a non-negative integer hint as to how many keys (or key clusters) will
be in the underlying hashtable. Remember that if you have good clustering,
you might have (/ N +FIXNUM-BITS+) keys, so be careful not to overallocate.
You are NOT declaring an equivalent number of keys as you would with a hash-table.
:rehash-size - indicates how to expand the table when it fills up.
If an integer, add
space for that many elements. If a floating point number (which must be
greater than 1.0), multiply the size by that amount.
Call ‘f‘, a function of one argument, with each member of the intset.
The order of element traversal is undefined. If you wanted ascending or descending
traversal, see ‘map-sorted-inset‘.
Behavior is undefined if the function modifies the intset, or if concurrent updates are
made from another thread.
Returns nil.
Call ‘f‘, a function of one argument, with each member of the inset in the ascending
or descending order according to the value of ‘direction‘, which must be :ascending or
:descending.
Note that this function is less efficient than unordered traversals of ‘map-intset‘
as it requires a sort on the intset’s hash table keys (and only those keys).
However the behavior is equally efficient to the unordered traversal within the
range of up to clustered-intset:+fixnum-bits+ values that might be associated with a
hash table key.
Behavior is undefined if the function modifies the intset, or if concurrent updates are
made from another thread.
Returns nil.
For a given non-negative integer k, which does not have to be a member of the intset,
find the next larger member of the intset. Return NIL if there is no appropriate member.
This is not an efficient implementation, this is O(n) and is a misguided convenience function.
Consider using the ITERATOR capability instead if that’s what you’re attempting to do,
or one of the mapping functions.
Create and return an intset populated from the specified sequence (vector or list). Makes a rough guess about the number of hash table keys you need (HT capacity) based on the range, or quantity, of sequence elements.
An object representation iteration state over an INTSET
structure-object.
hash-table
clustered-intset::intset
function
(or null vector)
keyword
clustered-intset::key-type
0
clustered-intset::value-type
0
clustered-intset::fix-mod-type
0
Given an intset and a non-negative integer member k in the intset, bind vars in the list vars
as follows:
first var - the hashtable key, effectively (/ k +fixnum-bits+).
second var - the hashtable value for the hashtable key, or zero if it doesn’t exist.
third var - the modulus of (/ k +fixnum-bits+) which is the bit position for k in hash-value.
and execute ’body’ with those bindings.
An an iterator hasn’t been activated yet, activate it and begin looking for keys.
Return the next value, if any, or nil if there isn’t any. Update iterator state accordingly.
Return a function which acts as a filter for hash table keys
to see if they quality for iteration according to ‘iterator‘ semantics below.
We’re setting up for the first HT key in iteration, or moving to a new HT key.
Set the iterator state to reflect this HT key, and find the first bit position
with a relevant value. Assuming the iterator initialization filtered any keys without
any applicable values, we’ll always return a value for a new HT key here.
Does not maintain the remaining-ht-keys slot of the iterator.
Does update the ’current’ values iterator.
Returns the intset element value for the first value associated with the HT key, which should not be nil.
ht.
For an active iterator, if there’s another value to be retrieved for the current hash-table key, advance the iterator to that bit and return the value. Otherwise return nil.
For an active iterator, if there’s another hash key to process, advance to that key and return the value. Otherwise mark the iterator inactive and return nil.
Given a hash-table HT, and a key which may or may not be that hash-table,
return the next key (with multiple values) in the hashtable with a value greater than ‘ht-key‘,
or nil if there is no such key.
HT-KEY may be -1, which is not usually accepted in this module, for a a ’first’ like
behavior that will find the lowest valued key in the intset, there are any keys.
Returns (values nil nil) or (values next-key value-for-key).
Advance an in-progress iterator if we can, returning the next value and updating iterator state. If there are no more values, deactivate the iterator and return nil.
Given a hash-table key, the value from the hash table, and the bit position of some set member
stored in that key/value pair, return the next ascending value available for the
ht key/value pair or NIL if there is no next value.
HT-VALUE may be zero, in which case we assume there are no valid keys for the value and you just
happened to have obtained it via ‘with-hash-kv‘.
BIT-POSITION may be nil if this is the first search for a value in HT-VALUE
otherwise it is deemed to be the position or an intset member for which we want to find
a successor value, i.e. the search starts at (1+ bit-position).
For some intset member K, check to see if there is some value in the hashtable value bits
associated with the hashtable key for K ‘(floor k fixnum-bits)‘, for which
pred is true. For example:
(some-ht-val ht 43 #’<)
For 62 fixnum bits, would check ht key 0 for any ht value bits indicating quantities < 43.
Similarly:
(some-ht-val ht 143 #’<=)
For 62 fixnum bits would check for values associated with that key from (* 2 62) to
(* 3 62) that were <= 143.
If we find a PRED-qualified value, return true, otherwise return nil.
Similar to ‘ht-key-filter‘, only in thise case we’re looking at intset members values
with the optional iteration controls (starting-with, ending-with, descending). Return a
predicate which accepts an intset member value and returns true if an intset member qualifies,
w.r.t. the optional range value, nil if it does not.
structure-object.
integer
0
Type of value resulting from ‘(mod k +fixnum-bits+)‘.
Generally used to specify the position of a bit in fixnum used as a bitvector.
Type of keys stored in the hashtable.
Type of values stored in the hashtable.
| Jump to: | %
(
A C D F H I M N S V W |
|---|
| Jump to: | %
(
A C D F H I M N S V W |
|---|
| Jump to: | +
C D E H I R S V |
|---|
| Jump to: | +
C D E H I R S V |
|---|
| Jump to: | C F I K P S T V |
|---|
| Jump to: | C F I K P S T V |
|---|