BoolMap

boolmap.go

package boolmap

// BoolMap is a data structure for storing binary
// states of elements indexed by non-negative
// integer key.
type BoolMap []byte

// New gives new bool map capable of storing state for
// n elements without growing.
func New(n int) BoolMap {
	return make(BoolMap, n/8+1)
}

// Set sets the value of the key to val.
func (p *BoolMap) Set(key int, val bool) {
	n, b := index(key)
	if n >= len(*p) {
		q := make(BoolMap, n+1)
		copy(q, *p)
		*p = q
	}
	if !val {
		(*p)[n] &^= b
	} else {
		(*p)[n] |= b
	}
}

// Get gets the value of the key.
func (p BoolMap) Get(key int) bool {
	n, b := index(key)
	if n >= len(p) {
		return false
	}
	return p[n]&b != 0
}

// String returns string representation of the p.
func (p BoolMap) String() string {
	nbyte := 8
	n := nbyte * len(p)
	if len(p) > 1 {
		nbyte++         // add padding char per each byte
		n += len(p) - 1 // add total padding chars
	}
	s := make([]byte, n)
	for i, b := range p {
		base := (len(p) - i - 1) * nbyte
		if i != 0 {
			s[base+nbyte-1] = 0x20 // add padding char
		}
		for i := 7; i > -1; i, b = i-1, b>>1 {
			s[base+i] = 0x30 + b&0x01
		}
	}
	return string(s)
}

// Neg gives complementary BoolMap to p.
func (p BoolMap) Neg() BoolMap {
	q := make(BoolMap, len(p))
	for i, b := range p {
		q[i] = ^b
	}
	return q
}

// Lower gives the lower bound of the map.
//
// It returns -1 if the map is empty.
func (p BoolMap) Lower() int {
	for n, b := range p {
		if b == 0 {
			continue
		}
		for j := 0; j < 8; j, b = j+1, b>>1 {
			if b&1 != 0 {
				return n*8 + j
			}
		}
	}
	return -1
}

// Upper gives the upper bound of the map.
//
// It returns -1 if the map is empty.
func (p BoolMap) Upper() int {
	for i := len(p) - 1; i > -1; i-- {
		if p[i] == 0 {
			continue
		}
		for j := byte(7); j >= 0; j-- {
			if p[i]&(1<<j) != 0 {
				return i*8 + int(j)
			}
		}
	}
	return -1
}

func index(key int) (int, byte) {
	return key / 8, byte(1 << (uint(key) % 8))
}

boolmap_test.go

package boolmap_test

import (
	"bytes"
	"testing"

	boolmap "gist.github.com/rjeczalik/6eb71c4c0f5058a9a183"
)

func TestBoolMapString(t *testing.T) {
	cases := []struct {
		p []byte
		s string
	}{
		{[]byte{0x01}, "00000001"},
		{[]byte{0x01, 0x01}, "00000001 00000001"},
		{[]byte{0x01, 0x01, 0x01}, "00000001 00000001 00000001"},
		{[]byte{0xAA, 0xAA}, "10101010 10101010"},
		{[]byte{0xAA, 0xAA, 0xAA}, "10101010 10101010 10101010"},
		{[]byte{0xF0}, "11110000"},
		{[]byte{0xF0, 0xAA, 0x01}, "00000001 10101010 11110000"},
	}
	for i, cas := range cases {
		s := (boolmap.BoolMap(cas.p)).String()
		if s != cas.s {
			t.Errorf("want String()=%q; got %q (i=%d)", cas.s, s, i)
		}
	}
}

func TestBoolMap_Edge(t *testing.T) {
	var m boolmap.BoolMap
	m.Set(0, true)
	m.Set(8, true)
	m.Set(15, true)
	m.Set(23, true)
	p := []byte{1, 1 | 1<<7, 1 << 7}
	if bytes.Compare([]byte(m), p) != 0 {
		t.Errorf("want m=%v; got %v", p, []byte(m))
	}
	s := "10000000 10000001 00000001"
	if got := m.String(); got != s {
		t.Errorf("want String()=%q; got %q", s, got)
	}
}

func TestBoolMap(t *testing.T) {
	cases := []struct {
		key int
		val bool
	}{
		{10, true}, {0, true}, {4, true}, {8, true}, {15, true}, {11, true},
		{12, false}, {10, false}, {8, false},
	}
	var m boolmap.BoolMap
	for i, cas := range cases {
		m.Set(cas.key, cas.val)
		val := m.Get(cas.key)
		if val != cas.val {
			t.Fatalf("want Get(%d)=%v; got %v (i=%d)", cas.key, cas.val, val, i)
		}
	}
	rep := []byte{0x11, 0x88}
	if bytes.Compare([]byte(m), rep) != 0 {
		t.Fatalf("want m=%v; got %v", rep, []byte(m))
	}
	want := "10001000 00010001" // 0, 4, 11, 15
	if got := m.String(); got != want {
		t.Fatalf("want String()=%q; got %q", want, got)
	}
	if got := m.Lower(); got != 0 {
		t.Fatalf("want Lower()=0; got %d", got)
	}
	m.Set(0, false)
	if got := m.Lower(); got != 4 {
		t.Fatalf("want Lower()=4; got %d", got)
	}
	if got := m.Upper(); got != 15 {
		t.Fatalf("want Upper()=15; got %d", got)
	}
	want = "01110111 11101111" // ~4, ~11, ~15
	m = m.Neg()
	if got := m.String(); got != want {
		t.Fatalf("want String()=%q; got %q", want, got)
	}
	if got := m.Lower(); got != 0 {
		t.Fatalf("want Lower()=0; got %d", got)
	}
	if got := m.Upper(); got != 14 {
		t.Fatalf("want Upper()=14; got %d", got)
	}
}