Created
March 20, 2013 01:13
-
-
Save bemasher/5201562 to your computer and use it in GitHub Desktop.
This file contains hidden or 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 main | |
import ( | |
"fmt" | |
"sort" | |
"time" | |
"math/rand" | |
) | |
const ( | |
N = 4 | |
) | |
type Range struct { | |
Min, Max int | |
} | |
type RangeMap map[int]int | |
// Given a list of ranges, add them to the map | |
func (r RangeMap) MergeList(l []Range) { | |
for _, i := range l { | |
// Set the value for the lower bound key if it doesn't exist in the | |
// map or if the existing value is smaller than the current bound | |
if v, exists := r[i.Min]; !exists || v <= i.Max { | |
r[i.Min] = i.Max | |
} | |
} | |
} | |
// Return the list of merged intervals | |
func (r RangeMap) List() (p []Range) { | |
// Create a list of all interval lower bounds | |
mins := make([]int, 0) | |
for k := range r { | |
mins = append(mins, k) | |
} | |
// Sort the starting values since map iteration | |
// order in golang is undefined | |
sort.Ints(mins) | |
var ( | |
prev *int | |
max int | |
) | |
// For each interval lower bound | |
for _, min := range mins { | |
max = r[min] | |
// If there is no previous range or this interval doesn't overlap | |
// with the previous interval, append it to the result list | |
if prev == nil || *prev < min { | |
p = append(p, Range{min, max}) | |
prev = &p[len(p)-1].Max | |
// Move on to next interval from the map | |
continue | |
} | |
// If the current interval overlaps the previous range and the | |
// current interval is larger than the previous upper bound, set | |
// the previous upper bound to the current interval's upper bound | |
if *prev >= min && *prev < max { | |
*prev = max | |
} | |
} | |
return | |
} | |
func main() { | |
// Generate a random list of intervals to merge | |
l := make([]Range, 0) | |
r := rand.New(rand.NewSource(time.Now().UnixNano())) | |
fmt.Printf("Generating %d ranges with intervals smaller than %d in the range (0, %d)...\n", N << 3, N << 3, N << 6) | |
for len(l) < N << 3 { | |
lower, upper := r.Intn(N << 6), r.Intn(N << 6) | |
if lower <= upper && upper - lower < N << 3 { | |
l = append(l, Range{lower, upper}) | |
} | |
} | |
fmt.Println(len(l), l) | |
fmt.Println() | |
rm := make(RangeMap) | |
rm.MergeList(l) | |
fmt.Println("Merged Intervals:") | |
pairs := rm.List() | |
fmt.Println(len(pairs), pairs) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment