mirror of
https://github.com/weaveworks/scope.git
synced 2026-07-18 04:49:55 +00:00
710d665c41
Upgraded from 99c19923, branch release-3.0. This required fetching or upgrading the following: * k8s.io/api to kubernetes-1.9.1 * k8s.io/apimachinery to kubernetes-1.9.1 * github.com/juju/ratelimit to 1.0.1 * github.com/spf13/pflag to 4c012f6d Also, update Scope's imports/function calls to be compatible with the new client.
47 lines
1.1 KiB
Go
47 lines
1.1 KiB
Go
// 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)
|
|
}
|
|
}
|