package euclid_test
import (
	"pythagorean"
	"pythagorean/euclid"
	"reflect"
	"testing"
)
var rangeTests = []struct {
	min, max int
	ts       []pythagorean.Triplet
}{
	{1, 10, []pythagorean.Triplet{{3, 4, 5}, {6, 8, 10}}},
	{11, 20, []pythagorean.Triplet{{12, 16, 20}}},
}
func TestRange(t *testing.T) {
	for _, test := range rangeTests {
		ts := euclid.Range(test.min, test.max)
		if !reflect.DeepEqual(ts, test.ts) {
			t.Fatalf("Range(%d, %d) = %v, want %v",
				test.min, test.max, ts, test.ts)
		}
	}
}
var sumTests = []struct {
	sum int
	ts  []pythagorean.Triplet
}{
	{180, []pythagorean.Triplet{{18, 80, 82}, {30, 72, 78}, {45, 60, 75}}},
	{1000, []pythagorean.Triplet{{200, 375, 425}}},
}
func TestSum(t *testing.T) {
	for _, test := range sumTests {
		ts := euclid.Sum(test.sum)
		if !reflect.DeepEqual(ts, test.ts) {
			t.Fatalf("Sum(%d) = %v, want %v",
				test.sum, ts, test.ts)
		}
	}
}
func BenchmarkRange(b *testing.B) {
	for i := 0; i < b.N; i++ {
		euclid.Range(1, 100)
	}
}
func BenchmarkSum(b *testing.B) {
	for i := 0; i < b.N; i++ {
		euclid.Sum(1000)
	}
}

// Package euclid generates Pythagorean-tiplets based on Euclid's method.
package euclid
import (
	"pythagorean"
	"sort"
)
// Range finds Pythagorean triplets between min and max using Euclid's method.
func Range(min, max int) []pythagorean.Triplet {
	var ret []pythagorean.Triplet
	set := make(map[pythagorean.Triplet]struct{})
	//https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple
	m := 2
	var a, b, c int
	for c <= max {
		// this method finds the primitive triplets
		for n := 1; n < m; n++ {
			a = m*m - n*n
			b = 2 * m * n
			c = m*m + n*n
			// this formula reports triplets like {15, 8, 17} so we have to sort them
			if a > b {
				a, b = b, a
			}
			if b > c {
				b, c = c, b
			}
			// we have to find _every_ triplet, not just the primitive ones
			for k := 1; ; k++ {
				if a*k >= min && c*k <= max {
					// this only counts unique triplets
					// https://stackoverflow.com/a/9251352
					set[pythagorean.Triplet{a * k, b * k, c * k}] = struct{}{}
				}
				if c*k > max {
					break
				}
			}
			if c > max {
				break
			}
		}
		m++
	}
	for tr := range set {
		ret = append(ret, tr)
	}
	sort.Slice(ret, func(i, j int) bool { return ret[i][0] < ret[j][0] })
	return ret
}
// Sum returns a list of all Pythagorean triplets where the sum a+b+c is equal to p.
func Sum(p int) []pythagorean.Triplet {
	var ret []pythagorean.Triplet
	candidates := Range(1, p/2)
	for i, tr := range candidates {
		if tr[0]+tr[1]+tr[2] == p {
			ret = append(ret, candidates[i])
		}
	}
	return ret
}