Dependencies for the affinity router and the
affinity routing daemon.
Change-Id: Icda72c3594ef7f8f0bc0c33dc03087a4c25529ca
diff --git a/vendor/github.com/petar/GoLLRB/llrb/llrb-stats.go b/vendor/github.com/petar/GoLLRB/llrb/llrb-stats.go
new file mode 100644
index 0000000..47126a3
--- /dev/null
+++ b/vendor/github.com/petar/GoLLRB/llrb/llrb-stats.go
@@ -0,0 +1,46 @@
+// Copyright 2010 Petar Maymounkov. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package llrb
+
+// GetHeight() returns an item in the tree with key @key, and it's height in the tree
+func (t *LLRB) GetHeight(key Item) (result Item, depth int) {
+ return t.getHeight(t.root, key)
+}
+
+func (t *LLRB) getHeight(h *Node, item Item) (Item, int) {
+ if h == nil {
+ return nil, 0
+ }
+ if less(item, h.Item) {
+ result, depth := t.getHeight(h.Left, item)
+ return result, depth + 1
+ }
+ if less(h.Item, item) {
+ result, depth := t.getHeight(h.Right, item)
+ return result, depth + 1
+ }
+ return h.Item, 0
+}
+
+// HeightStats() returns the average and standard deviation of the height
+// of elements in the tree
+func (t *LLRB) HeightStats() (avg, stddev float64) {
+ av := &avgVar{}
+ heightStats(t.root, 0, av)
+ return av.GetAvg(), av.GetStdDev()
+}
+
+func heightStats(h *Node, d int, av *avgVar) {
+ if h == nil {
+ return
+ }
+ av.Add(float64(d))
+ if h.Left != nil {
+ heightStats(h.Left, d+1, av)
+ }
+ if h.Right != nil {
+ heightStats(h.Right, d+1, av)
+ }
+}