mapmerge.go

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)
}