Nodes merge and sort

test.go

/*
There are sets of node ids which contain partly-contiguous ranges of node ids.
The  rst part of the exercise is to (in a language of your choice) model the
ranges in a space ef cient manner.

An example set:
a/1, a/2, a/3, a/4, a/128, a/129, b/65, b/66, c/1, c/10, c/42
Secondly, given the model already developed, write an algorithm that
will add two sets, merging any overlapping ranges.

For example
Set A (same as example for part 1):
a/1, a/2, a/3, a/4, a/128, a/129, b/65, b/66, c/1, c/10, c/42 Set B:
a/1, a/2, a/3, a/4 a/5, a/126, a/127, b/100, c/2, c/3, d/1

Set A + Set B should contain:
a/1, a/2, a/3, a/4, a/5, a/126, a/127, a/128, a/129, b/65, b/66, b/100, c/1,
c/2, c/3, c/10, c/42, d/1



Test this code by using playground by golang:
https://play.golang.org


Author: Cosmin Albulescu <[email protected]>

*/

package main

import (
	"fmt"
	"math/rand"
	"strconv"
	"strings"
)

type Node struct {
	Name   string
	Number int
}

func (node *Node) lower(c *Node) bool {

	diff := strings.Compare(node.Name, c.Name)

	if diff == -1 {
		return true
	}
	if diff == 1 {
		return false
	}

	return node.Number < c.Number
}

type NodeSet struct {
	nodes []Node
	nmap  map[string]interface{} // map to avoid duplicates
}

func (set *NodeSet) mapNode(node *Node) {
	if set.nmap[node.Name] == nil {
		set.nmap[node.Name] = make(map[int]bool, 0)
	}
	set.nmap[node.Name].(map[int]bool)[node.Number] = true
}

/**
 * Populate NodeSet from input data
 */
func (set *NodeSet) Create(input string) {

	set.nodes = make([]Node, 0)
	set.nmap = make(map[string]interface{}, 0)

	for _, str := range strings.Split(input, ",") {

		params := strings.Split(strings.Trim(str, " "), "/")

		name := strings.Trim(params[0], " ")
		num, err := strconv.Atoi(params[1])

		if name == "" {
			panic("Name is empty")
		}

		if err != nil {
			panic(fmt.Sprintf("Not a number: %s", params[1]))
		}

		node := Node{name, num}

		set.mapNode(&node)

		set.nodes = append(set.nodes, node)
	}
}

func (set *NodeSet) Merge(merge *NodeSet) {
	for _, node := range merge.nodes {
		if set.nmap[node.Name] != nil &&
			set.nmap[node.Name].(map[int]bool)[node.Number] {
			continue
		}
		set.mapNode(&node)
		set.nodes = append(set.nodes, node)
	}
}

func (set *NodeSet) qsort(a []Node) []Node {

	if len(a) < 2 {
		return a
	}

	left, right := 0, len(a)-1

	pivotIndex := rand.Int() % len(a)

	a[pivotIndex], a[right] = a[right], a[pivotIndex]

	for i := range a {
		if a[i].lower(&a[right]) {
			a[i], a[left] = a[left], a[i]
			left++
		}
	}

	a[left], a[right] = a[right], a[left]

	set.qsort(a[:left])
	set.qsort(a[left+1:])

	return a
}

func (set *NodeSet) Sort() {
	set.nodes = set.qsort(set.nodes)
}

func main() {

	seta := new(NodeSet)
	seta.Create("a/1, a/2, a/3, a/4, a/128, a/129, b/65, b/66, c/1, c/10, c/42")

	setb := new(NodeSet)
	setb.Create("a/1, a/2, a/3, a/4, a/5, a/126, a/127, b/100, c/2, c/3, d/1")

	seta.Merge(setb)
	seta.Sort()

	fmt.Println(seta.nodes)
}