Merge "Several cleanups suggested by mab."

go/client/client.go

diff --git a/go/client/client.go b/go/client/client.go
index 4a9db0b..7938e72 100644
--- a/go/client/client.go
+++ b/go/client/client.go
@@ -206,23 +206,16 @@
 	s.max.Sub(s.max, delta)
 }
 
+// contains returns true iff p belongs to s
+func (s *timeSample) contains(p *big.Int) bool {
+	return s.max.Cmp(p) >= 0 && s.min.Cmp(p) <= 0
+}
+
 // overlaps returns true iff s and other have any timespan in common.
 func (s *timeSample) overlaps(other *timeSample) bool {
 	return s.max.Cmp(other.min) >= 0 && other.max.Cmp(s.min) >= 0
 }
 
-// overlapsAll returns true iff s has s timespan in common with all of the
-// elements of others.
-func (s *timeSample) overlapsAll(others []*timeSample) bool {
-	for _, other := range others {
-		if !s.overlaps(other) {
-			return false
-		}
-	}
-
-	return true
-}
-
 // query sends a request to s, appends it to chain, and returns the resulting
 // timeSample.
 func (c *Client) query(server *config.Server, chain *config.Chain) (*timeSample, error) {
@@ -415,10 +408,10 @@
 
 	for _, sample := range samples[1:] {
 		if ret.min.Cmp(sample.min) < 0 {
-			sample.min.Set(ret.min)
+			ret.min.Set(sample.min)
 		}
 		if ret.max.Cmp(sample.max) > 0 {
-			sample.max.Set(ret.max)
+			ret.max.Set(sample.max)
 		}
 	}
 
@@ -437,11 +430,13 @@
 
 	overlapping := make([]*timeSample, 0, n)
 
-	for i, initial := range samples {
-		overlapping = append(overlapping, initial)
+	for _, initial := range samples {
+		// An intersection of any subset of intervals will be an interval that contains
+		// the starting point of one of the intervals (possibly as its own starting point).
+		point := initial.min
 
-		for _, candidate := range samples[i+1:] {
-			if candidate.overlapsAll(overlapping) {
+		for _, candidate := range samples {
+			if candidate.contains(point) {
 				overlapping = append(overlapping, candidate)
 			}
 

go/client/client_test.go

diff --git a/go/client/client_test.go b/go/client/client_test.go
index bebec9f..d08d955 100644
--- a/go/client/client_test.go
+++ b/go/client/client_test.go
@@ -17,6 +17,7 @@
 import (
 	"crypto/rand"
 	"encoding/json"
+	"math/big"
 	"net"
 	"strconv"
 	"sync"
@@ -333,3 +334,56 @@
 		addr:      localAddr,
 	}, nil
 }
+
+func TestFindNOverlapping(t *testing.T) {
+	type sample struct {
+		min int64
+		max int64
+	}
+	testcases := []struct {
+		samples []sample
+		maxN    int
+	}{
+		{
+			samples: []sample{
+				{0, 2},
+				{1, 3},
+			},
+			maxN: 2,
+		},
+		{
+			samples: []sample{
+				{0, 2},
+				{1, 3},
+				{4, 5},
+			},
+			maxN: 2,
+		},
+		{
+			samples: []sample{
+				{0, 10},
+				{1, 2},
+				{5, 10},
+				{6, 10},
+			},
+			maxN: 3,
+		},
+	}
+	for i, tc := range testcases {
+		samples := make([]*timeSample, len(tc.samples))
+		for j, s := range tc.samples {
+			samples[j] = &timeSample{
+				base: big.NewInt(0),
+				min:  big.NewInt(s.min),
+				max:  big.NewInt(s.max),
+			}
+		}
+		for n := 1; n <= len(samples); n++ {
+			expectedOk := n <= tc.maxN
+			_, ok := findNOverlapping(samples, n)
+			if ok != expectedOk {
+				t.Errorf("#%d: findNOverlapping(n=%d) returned %v, wanted %v", i, n, ok, expectedOk)
+			}
+		}
+	}
+}