segments.go

package segments

type segment struct {
	from, to int64
}

type segments []segment

func min(a, b int64) int64 {
	if a < b { return a }
	return b
}

func max(a, b int64) int64 {
	if a > b { return a }
	return b
}

func Merge(a, b segments) segments {

	result := segments{}

	// While there are entries left
	for len(a) > 0 && len(b) > 0 {

		// Set A will be the one, starting with the earliest date (smallest entry)
		if a[0].from > b[0].from {
			a, b = b, a
		}

		// While A has segments before the B starts, remove those
		if a[0].to < b[0].from {
			a = a[1:]
			continue
		}

		// We've thrown away all the non-intersecting segments at the beginning
		// So here we will have an intersection between a and b
		result = append(result, segment{
			max(a[0].from, b[0].from),
			min(a[0].to, b[0].to),
		})

		// Remove the segment of these two, which ends first
		if a[0].to < b[0].to {
			a = a[1:]
		} else {
			b = b[1:]
		}
	}

	return result
}

segments_test.go

package segments

import (
	"testing"
	"time"
)

// Date format I'll be using here
const ShortDate = "2006-01-02"

// Create segment from two strings
func fromDates(from, to string) segment {
	fromTime, _ := time.Parse(ShortDate, from)
	toTime, _ := time.Parse(ShortDate, to)

	if fromTime.After(toTime) {
		fromTime, toTime = toTime, fromTime
	}

	return segment{
		fromTime.Unix(),
		toTime.Unix(),
	}
}

func (a segments) EqualsTo(b segments) bool {
	if len(a) != len(b) {
		return false
	}

	for i, v := range a {
		if v != b[i] {
			return false
		}
	}

	return true
}

func TestBeforeAndAfter(t *testing.T) {

	a := segments{fromDates("2017-01-01", "2017-01-10") }
	b := segments{fromDates("2017-01-15", "2017-01-20") }
	expected := segments{}

	if !Merge(a, b).EqualsTo(expected) {
		t.Error("Segments are not equal")
	}

	// Reverse
	if !Merge(b, a).EqualsTo(Merge(a, b)) {
		t.Error("Segments are not equal")
	}
}

func TestBorderIntersect(t *testing.T) {

	a := segments{fromDates("2017-01-01", "2017-01-10") }
	b := segments{fromDates("2017-01-10", "2017-01-10") }

	expected := segments{fromDates("2017-01-10", "2017-01-10") }

	if !Merge(a, b).EqualsTo(expected) {
		t.Error("Segments are not equal")
	}

	// Reverse
	if !Merge(b, a).EqualsTo(Merge(a, b)) {
		t.Error("Segments are not equal")
	}
}

func TestIntersection(t *testing.T) {

	a := segments{fromDates("2017-01-01", "2017-01-10") }
	b := segments{fromDates("2017-01-05", "2017-01-10") }

	expected := segments{fromDates("2017-01-05", "2017-01-10") }

	if !Merge(a, b).EqualsTo(expected) {
		t.Error("Segments are not equal")
	}

	// Reverse
	if !Merge(b, a).EqualsTo(Merge(a, b)) {
		t.Error("Segments are not equal")
	}
}

func TestEquals(t *testing.T) {

	a := segments{fromDates("2017-01-01", "2017-01-10") }
	b := segments{fromDates("2017-01-10", "2017-01-10") }

	expected := segments{fromDates("2017-01-10", "2017-01-10") }

	if !Merge(a, b).EqualsTo(expected) {
		t.Error("Segments are not equal")
	}

	// Reverse
	if !Merge(b, a).EqualsTo(Merge(a, b)) {
		t.Error("Segments are not equal")
	}
}

func TestInterleaving(t *testing.T) {

	a := segments{
		fromDates("2017-01-01", "2017-01-01"),
		fromDates("2017-01-03", "2017-01-03"),
		fromDates("2017-01-05", "2017-01-05"),
		fromDates("2017-01-07", "2017-01-07"),
	}

	b := segments{
		fromDates("2017-01-02", "2017-01-02"),
		fromDates("2017-01-04", "2017-01-04"),
		fromDates("2017-01-06", "2017-01-06"),
		fromDates("2017-01-08", "2017-01-08"),
	}

	expected := segments{}

	if !Merge(a, b).EqualsTo(expected) {
		t.Error("Segments are not equal")
	}

	// Reverse
	if !Merge(b, a).EqualsTo(Merge(a, b)) {
		t.Error("Segments are not equal")
	}
}

func TestOneContainingAnother(t *testing.T) {

	a := segments{
		fromDates("2017-01-01", "2017-01-31"),
	}

	b := segments{
		fromDates("2017-01-02", "2017-01-02"),
		fromDates("2017-01-04", "2017-01-04"),
		fromDates("2017-01-06", "2017-01-06"),
		fromDates("2017-01-08", "2017-01-08"),
	}

	if !Merge(a, b).EqualsTo(b) {
		t.Error("Segments are not equal")
	}

	// Reverse
	if !Merge(b, a).EqualsTo(Merge(a, b)) {
		t.Error("Segments are not equal")
	}
}