Merge "Several cleanups suggested by mab."
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)
}
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)
+ }
+ }
+ }
+}
