From 2fdccd98d65b03f6550d1824a7c5541cb1d175cf Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 5 May 2016 23:24:44 -0400
Subject: Add Fisher-Yates schuffle

---
 merkle_test.go |  1 +
 utils.go       | 13 +++++++++++++
 utils_test.go  | 12 +++++++++++-
 3 files changed, 25 insertions(+), 1 deletion(-)

diff --git a/merkle_test.go b/merkle_test.go
index b2dc9be..b6d9224 100644
--- a/merkle_test.go
+++ b/merkle_test.go
@@ -67,6 +67,7 @@ func TestProofsPostMerkle(t *testing.T) {
 func TestBatchProofsBFSMerkle(t *testing.T) {
 	m := NewBFSMerkle(25, "/mnt/data/bfs.db")
 	root := make([]byte, hashSize)
+	sort.Sort(Int64Slice(ids))
 	m.Read(root, 0)
 	start := time.Now()
 	proofs = m.BatchProofs(ids)
diff --git a/utils.go b/utils.go
index 513786c..fe17650 100644
--- a/utils.go
+++ b/utils.go
@@ -1,5 +1,10 @@
 package main
 
+import (
+	"math/rand"
+	"sort"
+)
+
 // floor of log(x) (i.e MSB for positive integers)
 func Log(x int64) int64 {
 	var r int64 = 0
@@ -34,3 +39,11 @@ func Post(size int64, height int64, id int64) int64 {
 	}
 	return r
 }
+
+func Shuffle(data sort.Interface) {
+	var j int
+	for i := data.Len() - 1; i > 0; i-- {
+		j = rand.Intn(i + 1)
+		data.Swap(i, j)
+	}
+}
diff --git a/utils_test.go b/utils_test.go
index c42ecef..7b912a0 100644
--- a/utils_test.go
+++ b/utils_test.go
@@ -1,6 +1,10 @@
 package main
 
-import "testing"
+import (
+	"fmt"
+	"sort"
+	"testing"
+)
 
 func TestLog(t *testing.T) {
 	tests := []struct {
@@ -72,3 +76,9 @@ func TestPost(t *testing.T) {
 	}
 
 }
+
+func TestShuffle(t *testing.T) {
+	a := sort.IntSlice([]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9})
+	Shuffle(a)
+	fmt.Println(a)
+}
-- 
cgit v1.2.3-70-g09d2