Order nodes by priority (sub-nodes count)

tree.go

diff --git a/tree.go b/tree.go
index df88ba7..00ba564 100644
--- a/tree.go
+++ b/tree.go
@@ -26,11 +26,32 @@
 	wildChild bool
 	nType     nodeType
 	handle    map[string]Handle
+	priority  uint32
+}
+
+// increments priority of the given child and reorders if necessary
+func (n *node) incrementChildPrio(i int) int {
+	n.children[i].priority++
+	prio := n.children[i].priority
+	// adjust position (move to front)
+	for j := i - 1; j >= 0 && n.children[j].priority < prio; j-- {
+		// swap node positions
+		tmpN := n.children[j]
+		n.children[j] = n.children[i]
+		n.children[i] = tmpN
+		tmpI := n.indices[j]
+		n.indices[j] = n.indices[i]
+		n.indices[i] = tmpI
+
+		i--
+	}
+	return i
 }
 
 // addRoute adds a node with the given handle to the path.
 // Not concurrency-safe!
 func (n *node) addRoute(method, path string, handle Handle) {
+	n.priority++
 	// non-empty tree
 	if len(n.path) != 0 {
 	OUTER:
@@ -50,6 +71,7 @@
 					children:  n.children,
 					handle:    n.handle,
 					wildChild: n.wildChild,
+					priority:  n.priority - 1,
 				}}
 				n.indices = []byte{n.path[i]}
 				n.path = path[:i]
@@ -64,6 +86,7 @@
 				// catchAll
 				if n.wildChild {
 					n = n.children[0]
+					n.priority++
 
 					// Check if the wildcard matches
 					if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
@@ -81,12 +104,14 @@
 				// param
 				if n.nType == param && c == '/' && len(n.children) == 1 {
 					n = n.children[0]
+					n.priority++
 					continue OUTER
 				}
 
 				// Check if a child with the next path byte exists
 				for i, index := range n.indices {
 					if c == index {
+						i = n.incrementChildPrio(i)
 						n = n.children[i]
 						continue OUTER
 					}
@@ -98,6 +123,7 @@
 					child := &node{}
 					n.children = append(n.children, child)
 
+					n.incrementChildPrio(len(n.indices) - 1)
 					n = child
 				}
 				n.insertChild(method, path, handle)
@@ -157,6 +183,7 @@
 				n.children = []*node{child}
 				n.wildChild = true
 				n = child
+				n.priority++
 
 				// if the path doesn't end with the wildcard, then there will be
 				// another non-wildcard subpath starting with '/'
@@ -167,6 +194,7 @@
 					child := &node{}
 					n.children = []*node{child}
 					n = child
+					n.priority++
 				}
 
 			} else { // catchAll
@@ -190,6 +218,7 @@
 				n.children = []*node{child}
 				n.indices = []byte{path[i]}
 				n = child
+				n.priority++
 
 				// second node: node holding the variable
 				child = &node{
@@ -197,7 +226,8 @@
 					handle: map[string]Handle{
 						method: handle,
 					},
-					nType: catchAll,
+					nType:    catchAll,
+					priority: 1,
 				}
 				n.children = []*node{child}
 

tree_test.go

diff --git a/tree_test.go b/tree_test.go
index 291cb3b..d30c074 100644
--- a/tree_test.go
+++ b/tree_test.go
@@ -12,7 +12,7 @@
 )
 
 func printChildren(n *node, prefix string) {
-	fmt.Printf("%s%s[%d]  %v %t \r\n", prefix, n.path, len(n.children), n.handle, n.wildChild)
+	fmt.Printf(" %02d %s%s[%d] %v %t \r\n", n.priority, prefix, n.path, len(n.children), n.handle, n.wildChild)
 	for l := len(n.path); l > 0; l-- {
 		prefix += " "
 	}
@@ -60,6 +60,23 @@
 	}
 }
 
+func checkPriorities(t *testing.T, n *node) uint32 {
+	var prio uint32
+	for i := range n.children {
+		prio += checkPriorities(t, n.children[i])
+	}
+	prio += uint32(len(n.handle))
+
+	if n.priority != prio {
+		t.Errorf(
+			"priority mismatch for node '%s': is %d, should be %d",
+			n.path, n.priority, prio,
+		)
+	}
+
+	return prio
+}
+
 func TestTreeAddAndGet(t *testing.T) {
 	tree := &node{}
 
@@ -91,6 +108,8 @@
 		{"/no", true, "", nil},   // no matching child
 		{"/ab", false, "/ab", nil},
 	})
+
+	checkPriorities(t, tree)
 }
 
 func TestTreeWildcard(t *testing.T) {
@@ -130,6 +149,8 @@
 		{"/user_gopher/about", false, "/user_:name/about", map[string]string{"name": "gopher"}},
 		{"/files/js/inc/framework.js", false, "/files/:dir/*filepath", map[string]string{"dir": "js", "filepath": "/inc/framework.js"}},
 	})
+
+	checkPriorities(t, tree)
 }
 
 func catchPanic(testFunc func()) (recv interface{}) {