Struct
IpuzCharsetVec
Description [src]
struct IpuzCharsetVec {
guint8 count[63];
}
A transient histogram that stores a count indexed by the ordinals
within an IpuzCharset.
The IpuzCharsetVec is a supplementary data structure. It
is generally not useful on its own. The index has no meaning
outside the charset, so a vector is only ever interpreted alongside
the charset it was built from. Two vectors may be only meaningfully
compared or combined when they share the same source charset.
Fundamentally, this structure is an IpuzCharset with
three major distinctions:
- It is indexed by the position of a character within an
IpuzCharsetrather than by the character itself. Think array instead of a hashtable. - It can be mutated. Values indexed by ordinal can be added or
removed from it.
IpuzCharsets are immutable once created. - It can be allocated on the stack when used from C.
The primary reason this structure exists is for
performance. IpuzCharset and IpuzCharsetBuilder
were designed to collate and store data, and make access
fast. IpuzCharsetVec is designed to do repeated
operations on that charset. It is particularly useful for
grid-filling algorithms that may add/remove viable letters from a
solution set in a tight inner loop.
Bindings can use ipuz_charset_vec_new() and
ipuz_charset_vec_copy() to allocate one dynamically and so
that GValue has a way to hold one. However, it loses it’s
performance value when used this way, so alternatives should be
considered if needed in other languages.
This structure carries a valid bit alongside its counts, and
zeroed memory is invalid by default. It must be initialised with
ipuz_charset_vec_init() or
ipuz_charset_vec_init_from_string() before it can be used.
Note
A vector is constrained in two ways: 1) it holds at most
IPUZ_CHARSET_VEC_LEN ordinals, and 2) no single count
may rise above 255 or fall below 0. In practice, most alphabets
and puzzles will easily fit within these constraints. If an
operation breaks a constraint it will return FALSE and marks
the vector invalid. Subsequent calls to an invalid vector will fail.
Examples:
Asking whether a word can be spelled from a pool of letters, and what remains once it has been:
IpuzCharsetBuilder *builder;
g_autoptr (IpuzCharset) charset = NULL;
IpuzCharsetVec pool = {0, };
IpuzCharsetVec word = {0, };
builder = ipuz_charset_builder_new_for_language ("en");
charset = ipuz_charset_builder_build (builder);
ipuz_charset_vec_init_from_string (&pool, charset, "APPLEBEES");
ipuz_charset_vec_init_from_string (&word, charset, "PLEA");
// PLEA can be spelled from the letters in APPLEBEES
g_assert_true (ipuz_charset_vec_subset (&pool, &word));
// Once taken out, there aren't the letters for a second PLEA
ipuz_charset_vec_subtract (&pool, &word);
g_assert_false (ipuz_charset_vec_subset (&pool, &word));
Structure members
count:guint8The number of times each ordinal occurs.
Constructors
ipuz_charset_vec_new
Allocates a new IpuzCharsetVec on the heap, initialised
to a valid, empty histogram.
Instance methods
ipuz_charset_vec_free
Frees an IpuzCharsetVec allocated by
ipuz_charset_vec_new() or ipuz_charset_vec_copy().
ipuz_charset_vec_init_from_string
Initialises vec to a histogram of the characters in str, indexed
by their ordinal within charset.
ipuz_charset_vec_mask
Returns a bitmask of which ordinals occur in vec, with bit n set
when the count at ordinal n is non-zero.
ipuz_charset_vec_subset
Returns TRUE if subset is a subset of vec. That is to say, all
the characters in subset exist in vec, and of a count less than
or equal to the count in self.