Added generic big to 256 method. Implemented new iterator

5 files changed, 129 insertions, 105 deletions

diff --git a/ethtrie/encoding.go b/ethtrie/encoding.go
index c9c391110..bcf2c5669 100644
--- a/ethtrie/encoding.go
+++ b/ethtrie/encoding.go
@@ -6,7 +6,7 @@ import (
 	"strings"
 )
 
-func CompactEncode(hexSlice []int) string {
+func CompactEncode(hexSlice []byte) string {
 	terminator := 0
 	if hexSlice[len(hexSlice)-1] == 16 {
 		terminator = 1
@@ -17,11 +17,11 @@ func CompactEncode(hexSlice []int) string {
 	}
 
 	oddlen := len(hexSlice) % 2
-	flags := 2*terminator + oddlen
+	flags := byte(2*terminator + oddlen)
 	if oddlen != 0 {
-		hexSlice = append([]int{flags}, hexSlice...)
+		hexSlice = append([]byte{flags}, hexSlice...)
 	} else {
-		hexSlice = append([]int{flags, 0}, hexSlice...)
+		hexSlice = append([]byte{flags, 0}, hexSlice...)
 	}
 
 	var buff bytes.Buffer
@@ -32,7 +32,7 @@ func CompactEncode(hexSlice []int) string {
 	return buff.String()
 }
 
-func CompactDecode(str string) []int {
+func CompactDecode(str string) []byte {
 	base := CompactHexDecode(str)
 	base = base[:len(base)-1]
 	if base[0] >= 2 {
@@ -47,20 +47,20 @@ func CompactDecode(str string) []int {
 	return base
 }
 
-func CompactHexDecode(str string) []int {
+func CompactHexDecode(str string) []byte {
 	base := "0123456789abcdef"
-	hexSlice := make([]int, 0)
+	hexSlice := make([]byte, 0)
 
 	enc := hex.EncodeToString([]byte(str))
 	for _, v := range enc {
-		hexSlice = append(hexSlice, strings.IndexByte(base, byte(v)))
+		hexSlice = append(hexSlice, byte(strings.IndexByte(base, byte(v))))
 	}
 	hexSlice = append(hexSlice, 16)
 
 	return hexSlice
 }
 
-func DecodeCompact(key []int) string {
+func DecodeCompact(key []byte) string {
 	base := "0123456789abcdef"
 	var str string
 
diff --git a/ethtrie/encoding_test.go b/ethtrie/encoding_test.go
index 7a4849678..0cceef792 100644
--- a/ethtrie/encoding_test.go
+++ b/ethtrie/encoding_test.go
@@ -1,67 +1,68 @@
 package ethtrie
 
 import (
+	"bytes"
 	"fmt"
 	"testing"
 )
 
 func TestCompactEncode(t *testing.T) {
-	test1 := []int{1, 2, 3, 4, 5}
+	test1 := []byte{1, 2, 3, 4, 5}
 	if res := CompactEncode(test1); res != "\x11\x23\x45" {
 		t.Error(fmt.Sprintf("even compact encode failed. Got: %q", res))
 	}
 
-	test2 := []int{0, 1, 2, 3, 4, 5}
+	test2 := []byte{0, 1, 2, 3, 4, 5}
 	if res := CompactEncode(test2); res != "\x00\x01\x23\x45" {
 		t.Error(fmt.Sprintf("odd compact encode failed. Got: %q", res))
 	}
 
-	test3 := []int{0, 15, 1, 12, 11, 8 /*term*/, 16}
+	test3 := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
 	if res := CompactEncode(test3); res != "\x20\x0f\x1c\xb8" {
 		t.Error(fmt.Sprintf("odd terminated compact encode failed. Got: %q", res))
 	}
 
-	test4 := []int{15, 1, 12, 11, 8 /*term*/, 16}
+	test4 := []byte{15, 1, 12, 11, 8 /*term*/, 16}
 	if res := CompactEncode(test4); res != "\x3f\x1c\xb8" {
 		t.Error(fmt.Sprintf("even terminated compact encode failed. Got: %q", res))
 	}
 }
 
 func TestCompactHexDecode(t *testing.T) {
-	exp := []int{7, 6, 6, 5, 7, 2, 6, 2, 16}
+	exp := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16}
 	res := CompactHexDecode("verb")
 
-	if !CompareIntSlice(res, exp) {
+	if !bytes.Equal(res, exp) {
 		t.Error("Error compact hex decode. Expected", exp, "got", res)
 	}
 }
 
 func TestCompactDecode(t *testing.T) {
-	exp := []int{1, 2, 3, 4, 5}
+	exp := []byte{1, 2, 3, 4, 5}
 	res := CompactDecode("\x11\x23\x45")
 
-	if !CompareIntSlice(res, exp) {
+	if !bytes.Equal(res, exp) {
 		t.Error("odd compact decode. Expected", exp, "got", res)
 	}
 
-	exp = []int{0, 1, 2, 3, 4, 5}
+	exp = []byte{0, 1, 2, 3, 4, 5}
 	res = CompactDecode("\x00\x01\x23\x45")
 
-	if !CompareIntSlice(res, exp) {
+	if !bytes.Equal(res, exp) {
 		t.Error("even compact decode. Expected", exp, "got", res)
 	}
 
-	exp = []int{0, 15, 1, 12, 11, 8 /*term*/, 16}
+	exp = []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
 	res = CompactDecode("\x20\x0f\x1c\xb8")
 
-	if !CompareIntSlice(res, exp) {
+	if !bytes.Equal(res, exp) {
 		t.Error("even terminated compact decode. Expected", exp, "got", res)
 	}
 
-	exp = []int{15, 1, 12, 11, 8 /*term*/, 16}
+	exp = []byte{15, 1, 12, 11, 8 /*term*/, 16}
 	res = CompactDecode("\x3f\x1c\xb8")
 
-	if !CompareIntSlice(res, exp) {
+	if !bytes.Equal(res, exp) {
 		t.Error("even terminated compact decode. Expected", exp, "got", res)
 	}
 }
diff --git a/ethtrie/slice.go b/ethtrie/slice.go
index cf4e8df7a..f0edc9532 100644
--- a/ethtrie/slice.go
+++ b/ethtrie/slice.go
@@ -1,6 +1,9 @@
 package ethtrie
 
-import "math"
+import (
+	"bytes"
+	"math"
+)
 
 // Helper function for comparing slices
 func CompareIntSlice(a, b []int) bool {
@@ -16,7 +19,7 @@ func CompareIntSlice(a, b []int) bool {
 }
 
 // Returns the amount of nibbles that match each other from 0 ...
-func MatchingNibbleLength(a, b []int) int {
+func MatchingNibbleLength(a, b []byte) int {
 	var i, length = 0, int(math.Min(float64(len(a)), float64(len(b))))
 
 	for i < length {
@@ -28,3 +31,23 @@ func MatchingNibbleLength(a, b []int) int {
 
 	return i
 }
+
+func HasTerm(s []byte) bool {
+	return s[len(s)-1] == 16
+}
+
+func RemTerm(s []byte) []byte {
+	if HasTerm(s) {
+		return s[:len(s)-1]
+	}
+
+	return s
+}
+
+func BeginsWith(a, b []byte) bool {
+	if len(b) > len(a) {
+		return false
+	}
+
+	return bytes.Equal(a[:len(b)], b)
+}
diff --git a/ethtrie/trie.go b/ethtrie/trie.go
index 24f6a1f08..0d0c13456 100644
--- a/ethtrie/trie.go
+++ b/ethtrie/trie.go
@@ -252,7 +252,7 @@ func (t *Trie) Cache() *Cache {
 	return t.cache
 }
 
-func (t *Trie) getState(node interface{}, key []int) interface{} {
+func (t *Trie) getState(node interface{}, key []byte) interface{} {
 	n := ethutil.NewValue(node)
 	// Return the node if key is empty (= found)
 	if len(key) == 0 || n.IsNil() || n.Len() == 0 {
@@ -269,13 +269,13 @@ func (t *Trie) getState(node interface{}, key []int) interface{} {
 		k := CompactDecode(currentNode.Get(0).Str())
 		v := currentNode.Get(1).Raw()
 
-		if len(key) >= len(k) && CompareIntSlice(k, key[:len(k)]) {
+		if len(key) >= len(k) && bytes.Equal(k, key[:len(k)]) { //CompareIntSlice(k, key[:len(k)]) {
 			return t.getState(v, key[len(k):])
 		} else {
 			return ""
 		}
 	} else if length == 17 {
-		return t.getState(currentNode.Get(key[0]).Raw(), key[1:])
+		return t.getState(currentNode.Get(int(key[0])).Raw(), key[1:])
 	}
 
 	// It shouldn't come this far
@@ -301,20 +301,11 @@ func (t *Trie) getNode(node interface{}) *ethutil.Value {
 	return data
 }
 
-func (t *Trie) UpdateState(node interface{}, key []int, value string) interface{} {
+func (t *Trie) UpdateState(node interface{}, key []byte, value string) interface{} {
 	return t.InsertState(node, key, value)
 }
 
 func (t *Trie) Put(node interface{}) interface{} {
-	/*
-		TODO?
-			c := Conv(t.Root)
-			fmt.Println(c.Type(), c.Length())
-			if c.Type() == reflect.String && c.AsString() == "" {
-				return enc
-			}
-	*/
-
 	return t.cache.Put(node)
 
 }
@@ -327,7 +318,7 @@ func EmptyStringSlice(l int) []interface{} {
 	return slice
 }
 
-func (t *Trie) InsertState(node interface{}, key []int, value interface{}) interface{} {
+func (t *Trie) InsertState(node interface{}, key []byte, value interface{}) interface{} {
 	if len(key) == 0 {
 		return value
 	}
@@ -335,7 +326,6 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter
 	// New node
 	n := ethutil.NewValue(node)
 	if node == nil || n.Len() == 0 {
-		//if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 {
 		newNode := []interface{}{CompactEncode(key), value}
 
 		return t.Put(newNode)
@@ -350,7 +340,7 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter
 		v := currentNode.Get(1).Raw()
 
 		// Matching key pair (ie. there's already an object with this key)
-		if CompareIntSlice(k, key) {
+		if bytes.Equal(k, key) { //CompareIntSlice(k, key) {
 			newNode := []interface{}{CompactEncode(key), value}
 			return t.Put(newNode)
 		}
@@ -392,7 +382,7 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter
 			}
 		}
 
-		newNode[key[0]] = t.InsertState(currentNode.Get(key[0]).Raw(), key[1:], value)
+		newNode[key[0]] = t.InsertState(currentNode.Get(int(key[0])).Raw(), key[1:], value)
 
 		return t.Put(newNode)
 	}
@@ -400,9 +390,8 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter
 	panic("unexpected end")
 }
 
-func (t *Trie) deleteState(node interface{}, key []int) interface{} {
+func (t *Trie) deleteState(node interface{}, key []byte) interface{} {
 	if len(key) == 0 {
-		println("<empty ret>")
 		return ""
 	}
 
@@ -424,18 +413,13 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} {
 		v := currentNode.Get(1).Raw()
 
 		// Matching key pair (ie. there's already an object with this key)
-		if CompareIntSlice(k, key) {
+		if bytes.Equal(k, key) { //CompareIntSlice(k, key) {
 			//fmt.Printf("<delete ret> %x\n", v)
 
 			return ""
-		} else if CompareIntSlice(key[:len(k)], k) {
+		} else if bytes.Equal(key[:len(k)], k) { //CompareIntSlice(key[:len(k)], k) {
 			hash := t.deleteState(v, key[len(k):])
 			child := t.getNode(hash)
-			/*
-				if child.IsNil() {
-					return node
-				}
-			*/
 
 			var newNode []interface{}
 			if child.Len() == 2 {
@@ -475,13 +459,13 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} {
 			}
 		}
 		if amount == 16 {
-			newNode = []interface{}{CompactEncode([]int{16}), n[amount]}
+			newNode = []interface{}{CompactEncode([]byte{16}), n[amount]}
 		} else if amount >= 0 {
 			child := t.getNode(n[amount])
 			if child.Len() == 17 {
-				newNode = []interface{}{CompactEncode([]int{amount}), n[amount]}
+				newNode = []interface{}{CompactEncode([]byte{byte(amount)}), n[amount]}
 			} else if child.Len() == 2 {
-				key := append([]int{amount}, CompactDecode(child.Get(0).Str())...)
+				key := append([]byte{byte(amount)}, CompactDecode(child.Get(0).Str())...)
 				newNode = []interface{}{CompactEncode(key), child.Get(1).Str()}
 			}
 
@@ -511,6 +495,10 @@ func (t *Trie) NewIterator() *TrieIterator {
 	return &TrieIterator{trie: t}
 }
 
+func (self *Trie) Iterator() *Iterator {
+	return NewIterator(self)
+}
+
 // Some time in the near future this will need refactoring :-)
 // XXX Note to self, IsSlice == inline node. Str == sha3 to node
 func (it *TrieIterator) workNode(currentNode *ethutil.Value) {
@@ -583,11 +571,11 @@ func (it *TrieIterator) Each(cb EachCallback) {
 	it.fetchNode(nil, ethutil.NewValue(it.trie.Root).Bytes(), cb)
 }
 
-func (it *TrieIterator) fetchNode(key []int, node []byte, cb EachCallback) {
+func (it *TrieIterator) fetchNode(key []byte, node []byte, cb EachCallback) {
 	it.iterateNode(key, it.trie.cache.Get(node), cb)
 }
 
-func (it *TrieIterator) iterateNode(key []int, currentNode *ethutil.Value, cb EachCallback) {
+func (it *TrieIterator) iterateNode(key []byte, currentNode *ethutil.Value, cb EachCallback) {
 	if currentNode.Len() == 2 {
 		k := CompactDecode(currentNode.Get(0).Str())
 
@@ -595,7 +583,6 @@ func (it *TrieIterator) iterateNode(key []int, currentNode *ethutil.Value, cb Ea
 		if currentNode.Get(1).Len() != 0 && currentNode.Get(1).Str() == "" {
 			it.iterateNode(pk, currentNode.Get(1), cb)
 		} else {
-
 			if k[len(k)-1] == 16 {
 				cb(DecodeCompact(pk), currentNode.Get(1))
 			} else {
@@ -604,7 +591,7 @@ func (it *TrieIterator) iterateNode(key []int, currentNode *ethutil.Value, cb Ea
 		}
 	} else {
 		for i := 0; i < currentNode.Len(); i++ {
-			pk := append(key, i)
+			pk := append(key, byte(i))
 			if i == 16 && currentNode.Get(i).Len() != 0 {
 				cb(DecodeCompact(pk), currentNode.Get(i))
 			} else {
diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go
index 2661f8f25..11c20f8fb 100644
--- a/ethtrie/trie_test.go
+++ b/ethtrie/trie_test.go
@@ -1,16 +1,16 @@
 package ethtrie
 
 import (
-	_ "bytes"
-	_ "encoding/hex"
-	_ "encoding/json"
+	"bytes"
+	"encoding/hex"
+	"encoding/json"
 	"fmt"
-	_ "io/ioutil"
-	_ "math/rand"
-	_ "net/http"
-	_ "reflect"
+	"io/ioutil"
+	"math/rand"
+	"net/http"
+	"reflect"
 	"testing"
-	_ "time"
+	"time"
 
 	"github.com/ethereum/eth-go/ethutil"
 )
@@ -44,7 +44,6 @@ func NewTrie() (*MemDatabase, *Trie) {
 	return db, New(db, "")
 }
 
-/*
 func TestTrieSync(t *testing.T) {
 	db, trie := NewTrie()
 
@@ -247,41 +246,6 @@ func CreateTests(uri string, cb func(Test)) map[string]Test {
 	return tests
 }
 
-func TestRemote(t *testing.T) {
-	CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) {
-		_, trie := NewTrie()
-		for key, value := range test.In {
-			trie.Update(get(key), get(value))
-		}
-
-		a := ethutil.NewValue(h(test.Root)).Bytes()
-		b := ethutil.NewValue(trie.Root).Bytes()
-		if bytes.Compare(a, b) != 0 {
-			t.Errorf("%-10s: %x %x", test.Name, a, b)
-		}
-	})
-}
-
-func TestTrieReplay(t *testing.T) {
-	CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) {
-		_, trie := NewTrie()
-		for key, value := range test.In {
-			trie.Update(get(key), get(value))
-		}
-
-		_, trie2 := NewTrie()
-		trie.NewIterator().Each(func(key string, v *ethutil.Value) {
-			trie2.Update(key, v.Str())
-		})
-
-		a := ethutil.NewValue(trie.Root).Bytes()
-		b := ethutil.NewValue(trie2.Root).Bytes()
-		if bytes.Compare(a, b) != 0 {
-			t.Errorf("%s %x %x\n", test.Name, trie.Root, trie2.Root)
-		}
-	})
-}
-
 func RandomData() [][]string {
 	data := [][]string{
 		{"0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1", "0x4e616d6552656700000000000000000000000000000000000000000000000000"},
@@ -352,7 +316,6 @@ func TestDelete(t *testing.T) {
 	trie.Delete("a")
 	trie.Update("aaaa", "testmegood")
 
-	fmt.Println("aa =>", trie.Get("aa"))
 	_, t2 := NewTrie()
 	trie.NewIterator().Each(func(key string, v *ethutil.Value) {
 		if key == "aaaa" {
@@ -365,10 +328,59 @@ func TestDelete(t *testing.T) {
 	a := ethutil.NewValue(trie.Root).Bytes()
 	b := ethutil.NewValue(t2.Root).Bytes()
 
-	fmt.Printf("o: %x\nc: %x\n", a, b)
+	if bytes.Compare(a, b) != 0 {
+		t.Errorf("Expected %x and %x to be equal", a, b)
+	}
 }
-*/
 
+func TestTerminator(t *testing.T) {
+	key := CompactDecode("hello")
+	if !HasTerm(key) {
+		t.Errorf("Expected %v to have a terminator", key)
+	}
+}
+
+func TestIt(t *testing.T) {
+	_, trie := NewTrie()
+	trie.Update("cat", "cat")
+	trie.Update("doge", "doge")
+	trie.Update("wallace", "wallace")
+	it := trie.Iterator()
+
+	inputs := []struct {
+		In, Out string
+	}{
+		{"", "cat"},
+		{"bobo", "cat"},
+		{"c", "cat"},
+		{"car", "cat"},
+		{"catering", "doge"},
+		{"w", "wallace"},
+		{"wallace123", ""},
+	}
+
+	for _, test := range inputs {
+		res := string(it.Next(test.In))
+		if res != test.Out {
+			t.Errorf(test.In, "failed. Got", res, "Expected", test.Out)
+		}
+	}
+}
+
+func TestBeginsWith(t *testing.T) {
+	a := CompactDecode("hello")
+	b := CompactDecode("hel")
+
+	if BeginsWith(a, b) {
+		t.Errorf("Expected %x to begin with %x", a, b)
+	}
+
+	if BeginsWith(b, a) {
+		t.Errorf("Expected %x not to begin with %x", b, a)
+	}
+}
+
+/*
 func TestRndCase(t *testing.T) {
 	_, trie := NewTrie()
 
@@ -419,3 +431,4 @@ func TestRndCase(t *testing.T) {
 
 	fmt.Printf("%x\n", trie.Get(string(ethutil.Hex2Bytes("0000000000000000000000000000000000000000000000000000000000000001"))))
 }
+*/