Swap to bitwise hasSet()

Using bitwise operations yields over a 2x speedup.

The iteration order of hasSet was reversed which causes it to be within
60% of the performance of hasSetWithLast, instead of 6x slower. It was
also rewritten to use hasSetWithLast for better code reuse.

1 files changed, 68 insertions, 15 deletions

diff --git a/capset_test.go b/capset_test.go
index 29a77da..a807b3b 100644
--- a/capset_test.go
+++ b/capset_test.go
@@ -3,7 +3,6 @@ package main
 import (
 	"bufio"
 	"fmt"
-	"log"
 	"os"
 	"reflect"
 	"testing"
@@ -11,22 +10,68 @@ import (
 
 var deck = NewDeck(4)
 
+var hassettests = []struct {
+	tableau    []string
+	hasSet     bool
+	hasSetLast bool
+}{
+	{[]string{"0000"}, false, false},
+	{[]string{"0000", "0001"}, false, false},
+	{[]string{"0000", "0001", "0002"}, true, true},
+	{[]string{"0000", "0001", "0011"}, false, false},
+	{[]string{"0000", "1111", "2222"}, true, true},
+	{[]string{"0000", "1111", "2222", "0100"}, true, false},
+	{[]string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
+		"1000", "1001", "1012"}, false, false},
+	{[]string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
+		"1000", "1001", "1012", "1022", "1102", "1202", "2012", "2102", "2110",
+		"2111", "2122", "2212"}, false, false},
+}
+
+func TestHasSet(t *testing.T) {
+	for _, tt := range hassettests {
+		tableau, err := deck.FindCards(tt.tableau)
+		if err != nil {
+			t.Error(err)
+			continue
+		}
+		found := deck.hasSet(tableau)
+		if tt.hasSet != found {
+			t.Error("HasSet: For", tableau, "found", found, "but expected", tt.hasSet)
+		}
+		found = deck.hasSetWithLast(tableau)
+		if tt.hasSetLast != found {
+			t.Error("HasSetLast: For", tableau, "found", found, "but expected", tt.hasSet)
+		}
+	}
+}
+
 var capsettests = []struct {
 	maxim         int
-	start, finish []Card
+	start, finish []string
 }{
-	{20, []Card{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
+	{20, []string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
 		"1000", "1001", "1012"},
-		[]Card{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
+		[]string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
 			"1000", "1001", "1012", "1022", "1102", "1202", "2012", "2102", "2110",
 			"2111", "2122", "2212"}},
 }
 
 func TestFindNextCapset(t *testing.T) {
 	for _, tt := range capsettests {
-		cs := Capset{tableau: tt.start, maxim: tt.maxim, d: deck}
+		start, err := deck.FindCards(tt.start)
+		if err != nil {
+			t.Error(err)
+			continue
+		}
+		finish, err := deck.FindCards(tt.finish)
+		if err != nil {
+			t.Error(err)
+			continue
+		}
+		cs := Capset{tableau: start, maxim: tt.maxim, d: deck}
 		cs.FindNextCapset()
-		expected := Capset{tableau: tt.finish, maxim: len(tt.finish), d: deck}
+		expected := Capset{tableau: finish, maxim: len(tt.finish), d: deck}
 		if !reflect.DeepEqual(cs, expected) {
 			t.Fatalf("Got \n%v but expected \n%v", cs, expected)
 		}
@@ -35,17 +80,17 @@ func TestFindNextCapset(t *testing.T) {
 
 var scantests = []struct {
 	in  string
-	out []Card
+	out []string
 	err bool
 }{
 	{"", nil, true},
-	{"[]", []Card{}, false},
-	{"[0000]", []Card{"0000"}, false},
-	{"[0000 2222]", []Card{"0000", "2222"}, false},
+	{"[]", []string{}, false},
+	{"[0000]", []string{"0000"}, false},
+	{"[0000 2222]", []string{"0000", "2222"}, false},
 	{"[2]", nil, true},
 	{"not it", nil, true},
 	{"[0000", nil, true},
-	{"[  0000   2222  ]", []Card{"0000", "2222"}, false},
+	{"[  0000   2222  ]", []string{"0000", "2222"}, false},
 }
 
 func TestScan(t *testing.T) {
@@ -63,7 +108,12 @@ func TestScan(t *testing.T) {
 			if err != nil {
 				t.Errorf("Sscanln(%v). Unexpected error %v", tt.in, err)
 			} else {
-				if !reflect.DeepEqual(cs.tableau, tt.out) {
+				out, err := deck.FindCards(tt.out)
+				if err != nil {
+					t.Error("For input", tt.in, "got unexpected error:", err)
+					continue
+				}
+				if !reflect.DeepEqual(cs.tableau, out) {
 					t.Errorf("Sscanln(%v) => %v, want %v", tt.in, cs.tableau, tt.out)
 				}
 			}
@@ -85,7 +135,7 @@ func TestDim3(t *testing.T) {
 
 	cmpfile, err := os.Open("./capset3.out")
 	if err != nil {
-		log.Fatal(err)
+		t.Fatal(err)
 	}
 	defer cmpfile.Close()
 	scanner := bufio.NewScanner(cmpfile)
@@ -98,6 +148,9 @@ func TestDim3(t *testing.T) {
 				newline, scanner.Text())
 		}
 	}
+	if scanner.Scan() {
+		t.Error("Did not find items starting with", scanner.Text())
+	}
 }
 
 func BenchmarkIncrement(b *testing.B) {
@@ -111,7 +164,7 @@ func BenchmarkIncrementHasSet(b *testing.B) {
 	cs := NewCapset(deck, -1)
 	for i := 0; i < b.N; i++ {
 		cs.incrementTableau()
-		cs.hasSet = hasSet(cs.tableau)
+		cs.hasSet = deck.hasSet(cs.tableau)
 	}
 }
 
@@ -119,6 +172,6 @@ func BenchmarkIncrementHasSetWithLast(b *testing.B) {
 	cs := NewCapset(deck, -1)
 	for i := 0; i < b.N; i++ {
 		cs.incrementTableau()
-		cs.hasSet = hasSetWithLast(cs.tableau)
+		cs.hasSet = deck.hasSetWithLast(cs.tableau)
 	}
 }