package polyclip_test

import (
	"fmt"
	"sort"
	. "testing"
	"time"

	"github.com/henrylee2cn/algorithm/polyclip-go"
)

type sorter polyclip.Polygon

func (s sorter) Len() int      { return len(s) }
func (s sorter) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s sorter) Less(i, j int) bool {
	if len(s[i]) != len(s[j]) {
		return len(s[i]) < len(s[j])
	}
	for k := range s[i] {
		pi, pj := s[i][k], s[j][k]
		if pi.X != pj.X {
			return pi.X < pj.X
		}
		if pi.Y != pj.Y {
			return pi.Y < pj.Y
		}
	}
	return false
}

// basic normalization just for tests; to be improved if needed
func normalize(poly polyclip.Polygon) polyclip.Polygon {
	for i, c := range poly {
		if len(c) == 0 {
			continue
		}

		// find bottom-most of leftmost points, to have fixed anchor
		min := 0
		for j, p := range c {
			if p.X < c[min].X || p.X == c[min].X && p.Y < c[min].Y {
				min = j
			}
		}

		// rotate points to make sure min is first
		poly[i] = append(c[min:], c[:min]...)
	}

	sort.Sort(sorter(poly))
	return poly
}

func dump(poly polyclip.Polygon) string {
	return fmt.Sprintf("%v", normalize(poly))
}

func TestBug3(t *T) {
	cases := []struct{ subject, clipping, result polyclip.Polygon }{
		// original reported github issue #3
		{
			subject: polyclip.Polygon{{{1, 1}, {1, 2}, {2, 2}, {2, 1}}},
			clipping: polyclip.Polygon{
				{{2, 1}, {2, 2}, {3, 2}, {3, 1}},
				{{1, 2}, {1, 3}, {2, 3}, {2, 2}},
				{{2, 2}, {2, 3}, {3, 3}, {3, 2}}},
			result: polyclip.Polygon{{
				{1, 1}, {2, 1}, {3, 1},
				{3, 2}, {3, 3},
				{2, 3}, {1, 3},
				{1, 2}}},
		},
		// simplified variant of issue #3, for easier debugging
		{
			subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
			clipping: polyclip.Polygon{
				{{2, 1}, {2, 2}, {3, 2}},
				{{1, 2}, {2, 3}, {2, 2}},
				{{2, 2}, {2, 3}, {3, 2}}},
			result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 1}}},
		},
		{
			subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
			clipping: polyclip.Polygon{
				{{1, 2}, {2, 3}, {2, 2}},
				{{2, 2}, {2, 3}, {3, 2}}},
			result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 2}, {2, 1}}},
		},
		// another variation, now with single degenerated curve
		{
			subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
			clipping: polyclip.Polygon{
				{{1, 2}, {2, 3}, {2, 2}, {2, 3}, {3, 2}}},
			result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 2}, {2, 1}}},
		},
		{
			subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
			clipping: polyclip.Polygon{
				{{2, 1}, {2, 2}, {2, 3}, {3, 2}},
				{{1, 2}, {2, 3}, {2, 2}}},
			result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 1}}},
		},
		// "union" with effectively empty polygon (wholly self-intersecting)
		{
			subject:  polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
			clipping: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 3}, {1, 2}, {2, 2}, {2, 3}}},
			result:   polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
		},
	}
	for _, c := range cases {
		result := dump(c.subject.Construct(polyclip.UNION, c.clipping))
		if result != dump(c.result) {
			t.Errorf("case UNION:\nsubject:  %v\nclipping: %v\nexpected: %v\ngot:      %v",
				c.subject, c.clipping, c.result, result)
		}
	}
}

func TestBug4(t *T) {
	if Short() {
		return
	}

	cases := []struct{ subject, clipping, result polyclip.Polygon }{
		// original reported github issue #4, resulting in infinite loop
		{
			subject: polyclip.Polygon{{
				{1.427255375e+06, -2.3283064365386963e-10},
				{1.4271285e+06, 134.7111358642578},
				{1.427109e+06, 178.30108642578125}}},
			clipping: polyclip.Polygon{{
				{1.416e+06, -12000},
				{1.428e+06, -12000},
				{1.428e+06, 0},
				{1.416e+06, 0},
				{1.416e+06, -12000}}},
		},
	}
	for _, c := range cases {
		// check that we get a result in finite time

		ch := make(chan polyclip.Polygon)
		go func() {
			ch <- c.subject.Construct(polyclip.UNION, c.clipping)
		}()

		select {
		case <-ch:
		case <-time.After(1 * time.Second):
			// panicking in attempt to get full stacktrace
			panic(fmt.Sprintf("case UNION:\nsubject:  %v\nclipping: %v\ntimed out.", c.subject, c.clipping))
		}
	}
}

func TestBug5(t *T) {
	rect := polyclip.Polygon{{{24, 7}, {36, 7}, {36, 23}, {24, 23}}}
	circle := polyclip.Polygon{{{24, 7}, {24.83622770614123, 7.043824837053814}, {25.66329352654208, 7.174819194129555}, {26.472135954999587, 7.391547869638773}, {27.253893144606412, 7.691636338859195}, {28.00000000000001, 8.071796769724493}, {28.702282018339798, 8.527864045000424}, {29.35304485087088, 9.054841396180851}, {29.94515860381917, 9.646955149129141}, {30.472135954999597, 10.297717981660224}, {30.92820323027553, 11.00000000000001}, {31.308363661140827, 11.746106855393611}, {31.60845213036125, 12.527864045000435}, {31.825180805870467, 13.33670647345794}, {31.95617516294621, 14.16377229385879}, {32.00000000000002, 15.00000000000002}, {31.95617516294621, 15.83622770614125}, {31.825180805870467, 16.6632935265421}, {31.60845213036125, 17.472135954999604}, {31.308363661140827, 18.25389314460643}, {30.92820323027553, 19.00000000000003}, {30.472135954999597, 19.702282018339815}, {29.94515860381917, 20.353044850870898}, {29.35304485087088, 20.945158603819188}, {28.702282018339798, 21.472135954999615}, {28.00000000000001, 21.928203230275546}, {27.253893144606412, 22.308363661140845}, {26.472135954999587, 22.608452130361268}, {25.66329352654208, 22.825180805870485}, {24.83622770614123, 22.956175162946227}, {24, 23.00000000000004}, {23.16377229385877, 22.956175162946227}, {22.33670647345792, 22.825180805870485}, {21.527864045000413, 22.608452130361268}, {20.746106855393588, 22.308363661140845}, {19.99999999999999, 21.928203230275546}, {19.297717981660202, 21.472135954999615}, {18.64695514912912, 20.945158603819188}, {18.05484139618083, 20.353044850870898}, {17.527864045000403, 19.702282018339815}, {17.07179676972447, 19.00000000000003}, {16.691636338859173, 18.25389314460643}, {16.39154786963875, 17.472135954999604}, {16.174819194129533, 16.6632935265421}, {16.04382483705379, 15.83622770614125}, {15.999999999999977, 15.00000000000002}, {16.04382483705379, 14.16377229385879}, {16.174819194129533, 13.33670647345794}, {16.39154786963875, 12.527864045000435}, {16.691636338859173, 11.746106855393611}, {17.07179676972447, 11.00000000000001}, {17.527864045000403, 10.297717981660224}, {18.05484139618083, 9.646955149129141}, {18.64695514912912, 9.054841396180851}, {19.297717981660202, 8.527864045000424}, {19.99999999999999, 8.071796769724493}, {20.746106855393588, 7.691636338859194}, {21.527864045000413, 7.391547869638772}, {22.33670647345792, 7.1748191941295545}, {23.16377229385877, 7.043824837053813}}}

	expected := []struct {
		op     polyclip.Op
		result polyclip.Polygon
	}{
		{
			polyclip.UNION,
			polyclip.Polygon{{{36, 23}, {36, 7}, {24, 7}, {23.16377229385877, 7.043824837053813}, {22.33670647345792, 7.1748191941295545}, {21.527864045000413, 7.391547869638772}, {20.746106855393588, 7.691636338859194}, {19.99999999999999, 8.071796769724493}, {19.297717981660202, 8.527864045000424}, {18.64695514912912, 9.054841396180851}, {18.05484139618083, 9.646955149129141}, {17.527864045000403, 10.297717981660224}, {17.07179676972447, 11.00000000000001}, {16.691636338859173, 11.746106855393611}, {16.39154786963875, 12.527864045000435}, {16.174819194129533, 13.33670647345794}, {16.04382483705379, 14.16377229385879}, {15.999999999999977, 15.00000000000002}, {16.04382483705379, 15.83622770614125}, {16.174819194129533, 16.6632935265421}, {16.39154786963875, 17.472135954999604}, {16.691636338859173, 18.25389314460643}, {17.07179676972447, 19.00000000000003}, {17.527864045000403, 19.702282018339815}, {18.05484139618083, 20.353044850870898}, {18.64695514912912, 20.945158603819188}, {19.297717981660202, 21.472135954999615}, {19.99999999999999, 21.928203230275546}, {20.746106855393588, 22.308363661140845}, {21.527864045000413, 22.608452130361268}, {22.33670647345792, 22.825180805870485}, {23.16377229385877, 22.956175162946227}, {24, 23.00000000000004}, {24.000000000000746, 23}}},
		},
		{
			polyclip.INTERSECTION,
			polyclip.Polygon{{{31.95617516294621, 15.83622770614125}, {31.825180805870467, 16.6632935265421}, {31.60845213036125, 17.472135954999604}, {31.308363661140827, 18.25389314460643}, {30.92820323027553, 19.00000000000003}, {30.472135954999597, 19.702282018339815}, {29.94515860381917, 20.353044850870898}, {29.35304485087088, 20.945158603819188}, {28.702282018339798, 21.472135954999615}, {28.00000000000001, 21.928203230275546}, {27.253893144606412, 22.308363661140845}, {26.472135954999587, 22.608452130361268}, {25.66329352654208, 22.825180805870485}, {24.83622770614123, 22.956175162946227}, {24.000000000000746, 23}, {24, 23}, {24, 7}, {24.83622770614123, 7.043824837053814}, {25.66329352654208, 7.174819194129555}, {26.472135954999587, 7.391547869638773}, {27.253893144606412, 7.691636338859195}, {28.00000000000001, 8.071796769724493}, {28.702282018339798, 8.527864045000424}, {29.35304485087088, 9.054841396180851}, {29.94515860381917, 9.646955149129141}, {30.472135954999597, 10.297717981660224}, {30.92820323027553, 11.00000000000001}, {31.308363661140827, 11.746106855393611}, {31.60845213036125, 12.527864045000435}, {31.825180805870467, 13.33670647345794}, {31.95617516294621, 14.16377229385879}, {32.00000000000002, 15.00000000000002}}},
		},
		{
			polyclip.DIFFERENCE,
			polyclip.Polygon{{{24.000000000000746, 23}, {24.83622770614123, 22.956175162946227}, {25.66329352654208, 22.825180805870485}, {26.472135954999587, 22.608452130361268}, {27.253893144606412, 22.308363661140845}, {28.00000000000001, 21.928203230275546}, {28.702282018339798, 21.472135954999615}, {29.35304485087088, 20.945158603819188}, {29.94515860381917, 20.353044850870898}, {30.472135954999597, 19.702282018339815}, {30.92820323027553, 19.00000000000003}, {31.308363661140827, 18.25389314460643}, {31.60845213036125, 17.472135954999604}, {31.825180805870467, 16.6632935265421}, {31.95617516294621, 15.83622770614125}, {32.00000000000002, 15.00000000000002}, {31.95617516294621, 14.16377229385879}, {31.825180805870467, 13.33670647345794}, {31.60845213036125, 12.527864045000435}, {31.308363661140827, 11.746106855393611}, {30.92820323027553, 11.00000000000001}, {30.472135954999597, 10.297717981660224}, {29.94515860381917, 9.646955149129141}, {29.35304485087088, 9.054841396180851}, {28.702282018339798, 8.527864045000424}, {28.00000000000001, 8.071796769724493}, {27.253893144606412, 7.691636338859195}, {26.472135954999587, 7.391547869638773}, {25.66329352654208, 7.174819194129555}, {24.83622770614123, 7.043824837053814}, {24, 7}, {36, 7}, {36, 23}}},
		},
		{
			polyclip.XOR,
			polyclip.Polygon{
				{{24.000000000000746, 23}, {24, 23}, {24, 7}, {23.16377229385877, 7.043824837053813}, {22.33670647345792, 7.1748191941295545}, {21.527864045000413, 7.391547869638772}, {20.746106855393588, 7.691636338859194}, {19.99999999999999, 8.071796769724493}, {19.297717981660202, 8.527864045000424}, {18.64695514912912, 9.054841396180851}, {18.05484139618083, 9.646955149129141}, {17.527864045000403, 10.297717981660224}, {17.07179676972447, 11.00000000000001}, {16.691636338859173, 11.746106855393611}, {16.39154786963875, 12.527864045000435}, {16.174819194129533, 13.33670647345794}, {16.04382483705379, 14.16377229385879}, {15.999999999999977, 15.00000000000002}, {16.04382483705379, 15.83622770614125}, {16.174819194129533, 16.6632935265421}, {16.39154786963875, 17.472135954999604}, {16.691636338859173, 18.25389314460643}, {17.07179676972447, 19.00000000000003}, {17.527864045000403, 19.702282018339815}, {18.05484139618083, 20.353044850870898}, {18.64695514912912, 20.945158603819188}, {19.297717981660202, 21.472135954999615}, {19.99999999999999, 21.928203230275546}, {20.746106855393588, 22.308363661140845}, {21.527864045000413, 22.608452130361268}, {22.33670647345792, 22.825180805870485}, {23.16377229385877, 22.956175162946227}, {24, 23.00000000000004}},
				{{24.000000000000746, 23}, {24.83622770614123, 22.956175162946227}, {25.66329352654208, 22.825180805870485}, {26.472135954999587, 22.608452130361268}, {27.253893144606412, 22.308363661140845}, {28.00000000000001, 21.928203230275546}, {28.702282018339798, 21.472135954999615}, {29.35304485087088, 20.945158603819188}, {29.94515860381917, 20.353044850870898}, {30.472135954999597, 19.702282018339815}, {30.92820323027553, 19.00000000000003}, {31.308363661140827, 18.25389314460643}, {31.60845213036125, 17.472135954999604}, {31.825180805870467, 16.6632935265421}, {31.95617516294621, 15.83622770614125}, {32.00000000000002, 15.00000000000002}, {31.95617516294621, 14.16377229385879}, {31.825180805870467, 13.33670647345794}, {31.60845213036125, 12.527864045000435}, {31.308363661140827, 11.746106855393611}, {30.92820323027553, 11.00000000000001}, {30.472135954999597, 10.297717981660224}, {29.94515860381917, 9.646955149129141}, {29.35304485087088, 9.054841396180851}, {28.702282018339798, 8.527864045000424}, {28.00000000000001, 8.071796769724493}, {27.253893144606412, 7.691636338859195}, {26.472135954999587, 7.391547869638773}, {25.66329352654208, 7.174819194129555}, {24.83622770614123, 7.043824837053814}, {24, 7}, {36, 7}, {36, 23}},
			},
		},
	}

	for _, e := range expected {
		result := rect.Construct(e.op, circle)
		if dump(result) != dump(e.result) {
			t.Errorf("case %d expected:\n%v\ngot:\n%v", e.op, dump(e.result), dump(result))
		}
	}
}
