Fix findNOverlapping and intesection. Add test.
Previous implementation of findNOverlapping failed on the last
testcase in the test that this change adds. The new version works,
because an intersection of any subset of intervals starts in the
starting point of one of them.
Change-Id: I9a99ba1910f18f70069c6ab8c4bef6da35733286
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)
+ }
+ }
+ }
+}
