spatial/vptree: return error rather than panic

BarrensZeppelin · Jun 28, 2019 · 536a303 · 536a303
1 parent 6006dfb
commit 536a303
Show file tree

Hide file tree

Showing 4 changed files with 71 additions and 18 deletions.
diff --git a/spatial/vptree/vptree.go b/spatial/vptree/vptree.go
@@ -6,6 +6,7 @@ package vptree
 
 import (
 	"container/heap"
+	"errors"
 	"math"
 	"sort"
 
@@ -63,10 +64,9 @@ type Tree struct {
 // vantage point. If effort is one or less, random vantage points are chosen.
 // The order of elements in p will be altered after New returns. The src parameter
 // provides the source of randomness for vantage point selection. If src is nil
-// global rand package functions are used.
-//
-// Points in p must not be infinitely distant, otherwise New will panic.
-func New(p []Comparable, effort int, src rand.Source) *Tree {
+// global rand package functions are used. Points in p must not be infinitely
+// distant.
+func New(p []Comparable, effort int, src rand.Source) (t *Tree, err error) {
 	var intn func(int) int
 	var shuf func(n int, swap func(i, j int))
 	if src == nil {
@@ -78,12 +78,27 @@ func New(p []Comparable, effort int, src rand.Source) *Tree {
 		shuf = rnd.Shuffle
 	}
 	b := builder{work: make([]float64, len(p)), intn: intn, shuf: shuf}
-	return &Tree{
+
+	defer func() {
+		switch r := recover(); r {
+		case nil:
+		case pointAtInfinity:
+			t = nil
+			err = pointAtInfinity
+		default:
+			panic(r)
+		}
+	}()
+
+	t = &Tree{
 		Root:  b.build(p, effort),
 		Count: len(p),
 	}
+	return t, nil
 }
 
+var pointAtInfinity = errors.New("vptree: point at infinity")
+
 // builder performs vp-tree construction as described for the simple vp-tree
 // algorithm in http://pnylab.com/papers/vptree/vptree.pdf.
 type builder struct {
@@ -122,7 +137,7 @@ func (b *builder) selectVantage(s []Comparable, effort int) Comparable {
 		for i, q := range choices {
 			d := p.Distance(q)
 			if math.IsInf(d, 0) {
-				panic("vptree: point at infinity")
+				panic(pointAtInfinity)
 			}
 			b.work[i] = d
 		}
@@ -151,7 +166,7 @@ func (b *builder) partition(v Comparable, s []Comparable) (radius float64, close
 	for i, p := range s {
 		d := v.Distance(p)
 		if math.IsInf(d, 0) {
-			panic("vptree: point at infinity")
+			panic(pointAtInfinity)
 		}
 		b.work[i] = d
 	}

diff --git a/spatial/vptree/vptree_simple_example_test.go b/spatial/vptree/vptree_simple_example_test.go
@@ -6,6 +6,7 @@ package vptree_test
 
 import (
 	"fmt"
+	"log"
 
 	"gonum.org/v1/gonum/spatial/vptree"
 )
@@ -21,7 +22,10 @@ func ExampleTree() {
 		vptree.Point{7, 2},
 	}
 
-	t := vptree.New(points, 3, nil)
+	t, err := vptree.New(points, 3, nil)
+	if err != nil {
+		log.Fatal(err)
+	}
 	q := vptree.Point{8, 7}
 	p, d := t.Nearest(q)
 	fmt.Printf("%v is closest point to %v, d=%f\n", p, q, d)
@@ -41,7 +45,10 @@ func ExampleTree_Do() {
 	}
 
 	// Print all points in the data set within 3 of (3, 5).
-	t := vptree.New(points, 0, nil)
+	t, err := vptree.New(points, 0, nil)
+	if err != nil {
+		log.Fatal(err)
+	}
 	q := vptree.Point{3, 5}
 	t.Do(func(c vptree.Comparable, _ int) (done bool) {
 		// Compare each distance and output points

diff --git a/spatial/vptree/vptree_test.go b/spatial/vptree/vptree_test.go
@@ -49,19 +49,24 @@ var newTests = []struct {
 func TestNew(t *testing.T) {
 	for i, test := range newTests {
 		var tree *Tree
+		var err error
 		var panicked bool
 		func() {
 			defer func() {
 				if r := recover(); r != nil {
 					panicked = true
 				}
 			}()
-			tree = New(test.data, test.effort, rand.NewSource(1))
+			tree, err = New(test.data, test.effort, rand.NewSource(1))
 		}()
 		if panicked {
 			t.Errorf("unexpected panic for test %d", i)
 			continue
 		}
+		if err != nil {
+			t.Errorf("unexpected error for test %d: %v", i, err)
+			continue
+		}
 
 		if !tree.Root.isVPTree() {
 			t.Errorf("tree %d is not vp-tree", i)
@@ -139,7 +144,10 @@ func TestNearestRandom(t *testing.T) {
 		}
 		randData = append(randData, p)
 	}
-	tree := New(randData, 10, rand.NewSource(1))
+	tree, err := New(randData, 10, rand.NewSource(1))
+	if err != nil {
+		t.Fatalf("unexpected error: %v", err)
+	}
 
 	for i := 0; i < setSize; i++ {
 		q := make(Point, dims)
@@ -156,7 +164,10 @@ func TestNearestRandom(t *testing.T) {
 }
 
 func TestNearest(t *testing.T) {
-	tree := New(wpData, 3, rand.NewSource(1))
+	tree, err := New(wpData, 3, rand.NewSource(1))
+	if err != nil {
+		t.Fatalf("unexpected error: %v", err)
+	}
 	for _, q := range append([]Comparable{
 		Point{4, 6},
 		// Point{7, 5}, // Omitted because it is ambiguously finds [9 6] or [5 4].
@@ -213,7 +224,10 @@ func TestNearestSetN(t *testing.T) {
 		Point{-1e5, 0}},
 		wpData[:len(wpData)-1]...)
 
-	tree := New(wpData, 3, rand.NewSource(1))
+	tree, err := New(wpData, 3, rand.NewSource(1))
+	if err != nil {
+		t.Fatalf("unexpected error: %v", err)
+	}
 	for k := 1; k <= len(wpData); k++ {
 		for _, q := range data {
 			wantP := nearestN(k, q, wpData)
@@ -273,7 +287,10 @@ var nearestSetDistTests = []Point{
 }
 
 func TestNearestSetDist(t *testing.T) {
-	tree := New(wpData, 3, rand.NewSource(1))
+	tree, err := New(wpData, 3, rand.NewSource(1))
+	if err != nil {
+		t.Fatalf("unexpected error: %v", err)
+	}
 	for i, q := range nearestSetDistTests {
 		for d := 1.0; d < 100; d += 0.1 {
 			dk := NewDistKeeper(d)
@@ -311,7 +328,10 @@ func TestNearestSetDist(t *testing.T) {
 }
 
 func TestDo(t *testing.T) {
-	tree := New(wpData, 3, rand.NewSource(1))
+	tree, err := New(wpData, 3, rand.NewSource(1))
+	if err != nil {
+		t.Fatalf("unexpected error: %v", err)
+	}
 	var got []Point
 	fn := func(c Comparable, _ int) (done bool) {
 		got = append(got, c.(Point))
@@ -365,7 +385,10 @@ func BenchmarkNew(b *testing.B) {
 			}
 			b.ResetTimer()
 			for i := 0; i < b.N; i++ {
-				_ = New(p, effort, rand.NewSource(1))
+				_, err := New(p, effort, rand.NewSource(1))
+				if err != nil {
+					b.Fatalf("unexpected error: %v", err)
+				}
 			}
 		})
 	}
@@ -444,7 +467,11 @@ func Benchmark(b *testing.B) {
 		for i := range data {
 			data[i] = Point{rnd.Float64(), rnd.Float64(), rnd.Float64()}
 		}
-		tree := New(data, effort, rand.NewSource(1))
+		tree, err := New(data, effort, rand.NewSource(1))
+		if err != nil {
+			b.Errorf("unexpected error for effort=%d: %v", effort, err)
+			continue
+		}
 
 		if !tree.Root.isVPTree() {
 			b.Fatal("tree is not vantage point tree")

diff --git a/spatial/vptree/vptree_user_type_example_test.go b/spatial/vptree/vptree_user_type_example_test.go
@@ -6,6 +6,7 @@ package vptree_test
 
 import (
 	"fmt"
+	"log"
 	"math"
 
 	"gonum.org/v1/gonum/spatial/vptree"
@@ -15,7 +16,10 @@ func Example_accessiblePublicTransport() {
 	// Construct a vp tree of train station locations
 	// to identify accessible public transport for the
 	// elderly.
-	t := vptree.New(stations, 5, nil)
+	t, err := vptree.New(stations, 5, nil)
+	if err != nil {
+		log.Fatal(err)
+	}
 
 	// Residence.
 	q := place{lat: 51.501476, lon: -0.140634}