One of the things I needed in my Boggle solver was a bitmap. The average Boggle! board is 4x4, or 16 squares, and one of the rules is that you may not use the same letter twice. I needed a data structure that would handle the "Have I seen this before?"
Now, for a 4x4 board, a 16-bit integer will work just fine. And, in fact, the Ledger structure in the solver is, by default, a 64-bit integer, capable of handling boards as big as 8x8. In those case, the "mark" and "check" operations are just indices. Since this is a two-dimensional structure, we need a way to convert two-dimensional constructs into a one-dimensional number.
We want to move forward through the bitmap, using the width of the bitmap to find which row we're in, and then the position on that row as the final offset.
These functions use the Rust bitmap operators. << means "shift left", and for a lot of programming operations these are used to mean "multiply by two." An accompanying function >> means "shift right", and can mean "divide by two"; in assembly language, both of these functions have an associated register that will tell you if a zero or one "fell off", and there are are similar instructions that will actually "shift around"; if a '1' falls off at the 0th position of a 64-bit register, a '1' will be inserted into the 63rd position, and vice-versa.
For our purposes, though, we just care about "the bit at a given position," and we use the shift operator to shift that bit into that position. In this case, we just create a new u64 bitmap with that one bit set:
<code class="sourceCode rust"><span class="kw">pub</span> <span class="kw">struct</span> Ledger(<span class="dt">isize</span>, <span class="dt">isize</span>, <span class="dt">u64</span>);
<span class="kw">impl</span> Ledger <span class="op">{</span>
<span class="kw">fn</span> point(&<span class="kw">self</span>, x: <span class="dt">isize</span>, y: <span class="dt">isize</span>) -> <span class="dt">u64</span> <span class="op">{</span>
<span class="dv">1</span> << (<span class="kw">self</span>.<span class="dv">1</span> * x + y)
<span class="op">}</span>
<span class="op">}</span></code>
And then marking the bitmap consists of 'or'ing it against the representative bitmap.
<code class="sourceCode rust"> <span class="kw">fn</span> mark(&<span class="kw">self</span>, x: <span class="dt">isize</span>, y: <span class="dt">isize</span>) <span class="op">{</span>
<span class="kw">self</span>.<span class="dv">2</span> |= <span class="kw">self</span>.point(x, y);
<span class="op">}</span></code>
And checking the bitmap is to 'and' the pointed bitmap against the internal bitmap and checking that the result is not zero (a very fast operation in assembly language).
<code class="sourceCode rust"> <span class="kw">fn</span> check(&<span class="kw">self</span>, x: <span class="dt">isize</span>, y: <span class="dt">isize</span>) -> <span class="dt">bool</span> <span class="op">{</span>
<span class="kw">self</span>.<span class="dv">2</span> &= <span class="kw">self</span>.point(x, y) != <span class="dv">0</span>
<span class="op">}</span></code>
As trivial as that is, what if the board is bigger than 8x8? At that point, we're beyond the largest integer provided by mainstream CPUs, so we have to move to something simple: a map of maps. We'll use a Vec<u8>, and kinda do what point() does up above, only in reverse: turn a single coordinate into a coordinate pair indicating which index in the vector to target, and then which bit in that u8 we want to set or change.
The only challenge here is that we need to know how big the vector will be ahead of time, and we need to ensure that the vector is pre-populated and that the entire bitmap starts out set to zero. In the event that our size isn't evenly divisible by eight, we need one more block of bits for the overflow:
<code class="sourceCode rust"><span class="kw">pub</span> <span class="kw">struct</span> Bitmap(<span class="dt">Vec</span><<span class="dt">u8</span>>, <span class="dt">usize</span>);
<span class="kw">impl</span> Bitmap<span class="op">{</span>
<span class="kw">pub</span> <span class="kw">fn</span> new(b: <span class="dt">usize</span>) -> FSBitmap <span class="op">{</span>
<span class="kw">let</span> s = b / <span class="dv">8</span> + <span class="op">{</span> <span class="kw">if</span> (b % <span class="dv">8</span>) == <span class="dv">0</span> <span class="op">{</span> <span class="dv">0</span> <span class="op">}</span> <span class="kw">else</span> <span class="op">{</span> <span class="dv">1</span> <span class="op">}</span> <span class="op">}</span>;
FSBitmap((<span class="dv">0.</span>.s).map(|_| <span class="dv">0</span> <span class="kw">as</span> <span class="dt">u8</span>).collect::<<span class="dt">Vec</span><<span class="dt">u8</span>>>(), b)
<span class="op">}</span>
<span class="op">}</span></code>
The index of a point is then two numbers: which byte we want to examine, and then an offset into that byte. In many ways, it's exactly what the Ledger does, only backward. The Ledger doesn't care about machine sizes, just the board. The bitmap, though, cares about machine sizes.
<code class="sourceCode rust"> <span class="kw">fn</span> index(&<span class="kw">self</span>, p: <span class="dt">usize</span>) -> (<span class="dt">usize</span>, <span class="dt">usize</span>) <span class="op">{</span>
(p / <span class="dv">8</span>, p % <span class="dv">8</span>)
<span class="op">}</span></code>
This format isn't usable as a number, but as a way of tracking "in a modestly large atomic space, which units are in a which binary state?" it's perfect. Marking a bit uses this pair:
<code> pub fn mark(&mut self, p: usize) {
let (cell, byte) = self.index(p);
self.0[cell] |= 1 << byte;
}</code>
As does checking it. In this particular case, any bit referenced outside the size of the requested original size is assumed to be zero:
<code class="sourceCode rust"> <span class="kw">pub</span> <span class="kw">fn</span> check(&<span class="kw">self</span>, p: <span class="dt">usize</span>) -> <span class="dt">bool</span> <span class="op">{</span>
<span class="kw">if</span> p >= <span class="kw">self</span>.<span class="dv">1</span> <span class="op">{</span> <span class="kw">return</span> <span class="cn">false</span>; <span class="op">}</span>
<span class="kw">let</span> (cell, byte) = <span class="kw">self</span>.index(p);
<span class="kw">self</span>.<span class="dv">0</span><span class="op">[</span>cell<span class="op">]</span> & (<span class="dv">1</span> << byte) != <span class="dv">0</span>
<span class="op">}</span></code>
Other operations such as flip and unmark can be written with just these operators.
Bitmaps aren't the most thrilling data structures in the world, although there are some significant uses for very large, sparse bitmaps that have to be stored in something more esoteric than just a Vec<u8>. But for the purposes of Boggle! this was straightforward and not too difficult.