More #golang adventures..
Here is a program for sorting arbitrary amounts of data that is not already in memory.
The problem it attempts to solve is sorting data which is streaming in, ie from stdin or network, etc.
The way it's designed is by using two goroutines. One that generates the random numbers, and one that inserts the values into a binary tree. Communication is accomplished by using Go channels.
streamnumbers() seeds the pseudorandom number generator with UNIX nanoseconds, then loops infinitely, generating random integers, creating nodes, and putting them into the channel c.
The program can be altered to handle real world data by putting reading mechanisms into streamnumbers() instead of the rand.Int() stuff.
streamhandler() reads the channel c, and inputs the Nodes it receives into the binary tree.
The main execution thread runs a signal handler that catches interrupt signals (^C) which dumps the binary tree into a slice by inorder traversal, checks if it's in ascending order, and prints how many items were inserted into the tree before the interrupt.
// Simple code to binary tree sort data that is streaming in // blog.henry.is package main import ( "fmt" "math/rand" "os" "os/signal" "time" ) type Node struct { left, right, parent *Node value int } var root *Node = nil func treeinsert(r **Node, n *Node) { var y *Node = nil for x := *r; x != nil; x = x { y = x if n.value < x.value { x = x.left } else { x = x.right } } n.parent = y if y == nil { *r = n } else if n.value < y.value { y.left = n } else { y.right = n } } func treetraverse(r *Node, S *[]int) { if r == nil { return } treetraverse(r.left, S) *S = append(*S, r.value) treetraverse(r.right, S) } func checkifsorted(S []int) bool { for i, j := 0, 1; j < len(S); i, j = i+1, j+1 { if S[j] < S[i] { return false } } return true } func streamnumbers(c chan Node) { rand.Seed(time.Now().UnixNano()) for { randnum := rand.Int() newnode := new(Node) newnode.value = randnum c <- *newnode } } func streamhandler(c chan Node) { for { newnode := <-c treeinsert(&root, &newnode) } } func sighandler(s chan os.Signal) { for sig := range s { fmt.Printf("Caught: %v\n", sig) S := []int{} treetraverse(root, &S) sorted := checkifsorted(S) if !sorted { fmt.Println("Array not sorted.") os.Exit(1) } else { fmt.Println("Array is sorted.") } fmt.Printf("n=%d\n", len(S)) os.Exit(0) } } func main() { c := make(chan Node) go streamnumbers(c) go streamhandler(c) s := make(chan os.Signal, 1) signal.Notify(s, os.Interrupt) sighandler(s) os.Exit(0) }
