Create a gist now

Instantly share code, notes, and snippets.

@viktoras25 /segments.go Secret
Last active Jan 27, 2017

What would you like to do?
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
}
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")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment