-
-
Save viktoras25/1582c22c69ee7d2bd70478eefe30f0c0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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