internal/timeseries/timeseries.go - net - Git at Google

 // Copyright 2015 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // Package timeseries implements a time series structure for stats collection.
 package timeseries // import "golang.org/x/net/internal/timeseries"

 import (
 	"fmt"
 	"log"
 	"time"
 )

 const (
 	timeSeriesNumBuckets       = 64
 	minuteHourSeriesNumBuckets = 60
 )

 var timeSeriesResolutions = []time.Duration{
 	1 * time.Second,
 	10 * time.Second,
 	1 * time.Minute,
 	10 * time.Minute,
 	1 * time.Hour,
 	6 * time.Hour,
 	24 * time.Hour,          // 1 day
 	7 * 24 * time.Hour,      // 1 week
 	4 * 7 * 24 * time.Hour,  // 4 weeks
 	16 * 7 * 24 * time.Hour, // 16 weeks
 }

 var minuteHourSeriesResolutions = []time.Duration{
 	1 * time.Second,
 	1 * time.Minute,
 }

 // An Observable is a kind of data that can be aggregated in a time series.
 type Observable interface {
 	Multiply(ratio float64)    // Multiplies the data in self by a given ratio
 	Add(other Observable)      // Adds the data from a different observation to self
 	Clear()                    // Clears the observation so it can be reused.
 	CopyFrom(other Observable) // Copies the contents of a given observation to self
 }

 // Float attaches the methods of Observable to a float64.
 type Float float64

 // NewFloat returns a Float.
 func NewFloat() Observable {
 	f := Float(0)
 	return &f
 }

 // String returns the float as a string.
 func (f *Float) String() string { return fmt.Sprintf("%g", f.Value()) }

 // Value returns the float's value.
 func (f *Float) Value() float64 { return float64(*f) }

 func (f *Float) Multiply(ratio float64) { *f *= Float(ratio) }

 func (f *Float) Add(other Observable) {
 	o := other.(*Float)
 	*f += *o
 }

 func (f *Float) Clear() { *f = 0 }

 func (f *Float) CopyFrom(other Observable) {
 	o := other.(*Float)
 	*f = *o
 }

 // A Clock tells the current time.
 type Clock interface {
 	Time() time.Time
 }

 type defaultClock int

 var defaultClockInstance defaultClock

 func (defaultClock) Time() time.Time { return time.Now() }

 // Information kept per level. Each level consists of a circular list of
 // observations. The start of the level may be derived from end and the
 // len(buckets) * sizeInMillis.
 type tsLevel struct {
 	oldest   int               // index to oldest bucketed Observable
 	newest   int               // index to newest bucketed Observable
 	end      time.Time         // end timestamp for this level
 	size     time.Duration     // duration of the bucketed Observable
 	buckets  []Observable      // collections of observations
 	provider func() Observable // used for creating new Observable
 }

 func (l *tsLevel) Clear() {
 	l.oldest = 0
 	l.newest = len(l.buckets) - 1
 	l.end = time.Time{}
 	for i := range l.buckets {
 		if l.buckets[i] != nil {
 			l.buckets[i].Clear()
 			l.buckets[i] = nil
 		}
 	}
 }

 func (l *tsLevel) InitLevel(size time.Duration, numBuckets int, f func() Observable) {
 	l.size = size
 	l.provider = f
 	l.buckets = make([]Observable, numBuckets)
 }

 // Keeps a sequence of levels. Each level is responsible for storing data at
 // a given resolution. For example, the first level stores data at a one
 // minute resolution while the second level stores data at a one hour
 // resolution.

 // Each level is represented by a sequence of buckets. Each bucket spans an
 // interval equal to the resolution of the level. New observations are added
 // to the last bucket.
 type timeSeries struct {
 	provider    func() Observable // make more Observable
 	numBuckets  int               // number of buckets in each level
 	levels      []*tsLevel        // levels of bucketed Observable
 	lastAdd     time.Time         // time of last Observable tracked
 	total       Observable        // convenient aggregation of all Observable
 	clock       Clock             // Clock for getting current time
 	pending     Observable        // observations not yet bucketed
 	pendingTime time.Time         // what time are we keeping in pending
 	dirty       bool              // if there are pending observations
 }

 // init initializes a level according to the supplied criteria.
 func (ts *timeSeries) init(resolutions []time.Duration, f func() Observable, numBuckets int, clock Clock) {
 	ts.provider = f
 	ts.numBuckets = numBuckets
 	ts.clock = clock
 	ts.levels = make([]*tsLevel, len(resolutions))

 	for i := range resolutions {
 		if i > 0 && resolutions[i-1] >= resolutions[i] {
 			log.Print("timeseries: resolutions must be monotonically increasing")
 			break
 		}
 		newLevel := new(tsLevel)
 		newLevel.InitLevel(resolutions[i], ts.numBuckets, ts.provider)
 		ts.levels[i] = newLevel
 	}

 	ts.Clear()
 }

 // Clear removes all observations from the time series.
 func (ts *timeSeries) Clear() {
 	ts.lastAdd = time.Time{}
 	ts.total = ts.resetObservation(ts.total)
 	ts.pending = ts.resetObservation(ts.pending)
 	ts.pendingTime = time.Time{}
 	ts.dirty = false

 	for i := range ts.levels {
 		ts.levels[i].Clear()
 	}
 }

 // Add records an observation at the current time.
 func (ts *timeSeries) Add(observation Observable) {
 	ts.AddWithTime(observation, ts.clock.Time())
 }

 // AddWithTime records an observation at the specified time.
 func (ts *timeSeries) AddWithTime(observation Observable, t time.Time) {

 	smallBucketDuration := ts.levels[0].size

 	if t.After(ts.lastAdd) {
 		ts.lastAdd = t
 	}

 	if t.After(ts.pendingTime) {
 		ts.advance(t)
 		ts.mergePendingUpdates()
 		ts.pendingTime = ts.levels[0].end
 		ts.pending.CopyFrom(observation)
 		ts.dirty = true
 	} else if t.After(ts.pendingTime.Add(-1 * smallBucketDuration)) {
 		// The observation is close enough to go into the pending bucket.
 		// This compensates for clock skewing and small scheduling delays
 		// by letting the update stay in the fast path.
 		ts.pending.Add(observation)
 		ts.dirty = true
 	} else {
 		ts.mergeValue(observation, t)
 	}
 }

 // mergeValue inserts the observation at the specified time in the past into all levels.
 func (ts *timeSeries) mergeValue(observation Observable, t time.Time) {
 	for _, level := range ts.levels {
 		index := (ts.numBuckets - 1) - int(level.end.Sub(t)/level.size)
 		if 0 <= index && index < ts.numBuckets {
 			bucketNumber := (level.oldest + index) % ts.numBuckets
 			if level.buckets[bucketNumber] == nil {
 				level.buckets[bucketNumber] = level.provider()
 			}
 			level.buckets[bucketNumber].Add(observation)
 		}
 	}
 	ts.total.Add(observation)
 }

 // mergePendingUpdates applies the pending updates into all levels.
 func (ts *timeSeries) mergePendingUpdates() {
 	if ts.dirty {
 		ts.mergeValue(ts.pending, ts.pendingTime)
 		ts.pending = ts.resetObservation(ts.pending)
 		ts.dirty = false
 	}
 }

 // advance cycles the buckets at each level until the latest bucket in
 // each level can hold the time specified.
 func (ts *timeSeries) advance(t time.Time) {
 	if !t.After(ts.levels[0].end) {
 		return
 	}
 	for i := 0; i < len(ts.levels); i++ {
 		level := ts.levels[i]
 		if !level.end.Before(t) {
 			break
 		}

 		// If the time is sufficiently far, just clear the level and advance
 		// directly.
 		if !t.Before(level.end.Add(level.size * time.Duration(ts.numBuckets))) {
 			for _, b := range level.buckets {
 				ts.resetObservation(b)
 			}
 			level.end = time.Unix(0, (t.UnixNano()/level.size.Nanoseconds())*level.size.Nanoseconds())
 		}

 		for t.After(level.end) {
 			level.end = level.end.Add(level.size)
 			level.newest = level.oldest
 			level.oldest = (level.oldest + 1) % ts.numBuckets
 			ts.resetObservation(level.buckets[level.newest])
 		}

 		t = level.end
 	}
 }

 // Latest returns the sum of the num latest buckets from the level.
 func (ts *timeSeries) Latest(level, num int) Observable {
 	now := ts.clock.Time()
 	if ts.levels[0].end.Before(now) {
 		ts.advance(now)
 	}

 	ts.mergePendingUpdates()

 	result := ts.provider()
 	l := ts.levels[level]
 	index := l.newest

 	for i := 0; i < num; i++ {
 		if l.buckets[index] != nil {
 			result.Add(l.buckets[index])
 		}
 		if index == 0 {
 			index = ts.numBuckets
 		}
 		index--
 	}

 	return result
 }

 // LatestBuckets returns a copy of the num latest buckets from level.
 func (ts *timeSeries) LatestBuckets(level, num int) []Observable {
 	if level < 0 || level > len(ts.levels) {
 		log.Print("timeseries: bad level argument: ", level)
 		return nil
 	}
 	if num < 0 || num >= ts.numBuckets {
 		log.Print("timeseries: bad num argument: ", num)
 		return nil
 	}

 	results := make([]Observable, num)
 	now := ts.clock.Time()
 	if ts.levels[0].end.Before(now) {
 		ts.advance(now)
 	}

 	ts.mergePendingUpdates()

 	l := ts.levels[level]
 	index := l.newest

 	for i := 0; i < num; i++ {
 		result := ts.provider()
 		results[i] = result
 		if l.buckets[index] != nil {
 			result.CopyFrom(l.buckets[index])
 		}

 		if index == 0 {
 			index = ts.numBuckets
 		}
 		index -= 1
 	}
 	return results
 }

 // ScaleBy updates observations by scaling by factor.
 func (ts *timeSeries) ScaleBy(factor float64) {
 	for _, l := range ts.levels {
 		for i := 0; i < ts.numBuckets; i++ {
 			l.buckets[i].Multiply(factor)
 		}
 	}

 	ts.total.Multiply(factor)
 	ts.pending.Multiply(factor)
 }

 // Range returns the sum of observations added over the specified time range.
 // If start or finish times don't fall on bucket boundaries of the same
 // level, then return values are approximate answers.
 func (ts *timeSeries) Range(start, finish time.Time) Observable {
 	return ts.ComputeRange(start, finish, 1)[0]
 }

 // Recent returns the sum of observations from the last delta.
 func (ts *timeSeries) Recent(delta time.Duration) Observable {
 	now := ts.clock.Time()
 	return ts.Range(now.Add(-delta), now)
 }

 // Total returns the total of all observations.
 func (ts *timeSeries) Total() Observable {
 	ts.mergePendingUpdates()
 	return ts.total
 }

 // ComputeRange computes a specified number of values into a slice using
 // the observations recorded over the specified time period. The return
 // values are approximate if the start or finish times don't fall on the
 // bucket boundaries at the same level or if the number of buckets spanning
 // the range is not an integral multiple of num.
 func (ts *timeSeries) ComputeRange(start, finish time.Time, num int) []Observable {
 	if start.After(finish) {
 		log.Printf("timeseries: start > finish, %v>%v", start, finish)
 		return nil
 	}

 	if num < 0 {
 		log.Printf("timeseries: num < 0, %v", num)
 		return nil
 	}

 	results := make([]Observable, num)

 	for _, l := range ts.levels {
 		if !start.Before(l.end.Add(-l.size * time.Duration(ts.numBuckets))) {
 			ts.extract(l, start, finish, num, results)
 			return results
 		}
 	}

 	// Failed to find a level that covers the desired range. So just
 	// extract from the last level, even if it doesn't cover the entire
 	// desired range.
 	ts.extract(ts.levels[len(ts.levels)-1], start, finish, num, results)

 	return results
 }

 // RecentList returns the specified number of values in slice over the most
 // recent time period of the specified range.
 func (ts *timeSeries) RecentList(delta time.Duration, num int) []Observable {
 	if delta < 0 {
 		return nil
 	}
 	now := ts.clock.Time()
 	return ts.ComputeRange(now.Add(-delta), now, num)
 }

 // extract returns a slice of specified number of observations from a given
 // level over a given range.
 func (ts *timeSeries) extract(l *tsLevel, start, finish time.Time, num int, results []Observable) {
 	ts.mergePendingUpdates()

 	srcInterval := l.size
 	dstInterval := finish.Sub(start) / time.Duration(num)
 	dstStart := start
 	srcStart := l.end.Add(-srcInterval * time.Duration(ts.numBuckets))

 	srcIndex := 0

 	// Where should scanning start?
 	if dstStart.After(srcStart) {
 		advance := int(dstStart.Sub(srcStart) / srcInterval)
 		srcIndex += advance
 		srcStart = srcStart.Add(time.Duration(advance) * srcInterval)
 	}

 	// The i'th value is computed as show below.
 	// interval = (finish/start)/num
 	// i'th value = sum of observation in range
 	//   [ start + i       * interval,
 	//     start + (i + 1) * interval )
 	for i := 0; i < num; i++ {
 		results[i] = ts.resetObservation(results[i])
 		dstEnd := dstStart.Add(dstInterval)
 		for srcIndex < ts.numBuckets && srcStart.Before(dstEnd) {
 			srcEnd := srcStart.Add(srcInterval)
 			if srcEnd.After(ts.lastAdd) {
 				srcEnd = ts.lastAdd
 			}

 			if !srcEnd.Before(dstStart) {
 				srcValue := l.buckets[(srcIndex+l.oldest)%ts.numBuckets]
 				if !srcStart.Before(dstStart) && !srcEnd.After(dstEnd) {
 					// dst completely contains src.
 					if srcValue != nil {
 						results[i].Add(srcValue)
 					}
 				} else {
 					// dst partially overlaps src.
 					overlapStart := maxTime(srcStart, dstStart)
 					overlapEnd := minTime(srcEnd, dstEnd)
 					base := srcEnd.Sub(srcStart)
 					fraction := overlapEnd.Sub(overlapStart).Seconds() / base.Seconds()

 					used := ts.provider()
 					if srcValue != nil {
 						used.CopyFrom(srcValue)
 					}
 					used.Multiply(fraction)
 					results[i].Add(used)
 				}

 				if srcEnd.After(dstEnd) {
 					break
 				}
 			}
 			srcIndex++
 			srcStart = srcStart.Add(srcInterval)
 		}
 		dstStart = dstStart.Add(dstInterval)
 	}
 }

 // resetObservation clears the content so the struct may be reused.
 func (ts *timeSeries) resetObservation(observation Observable) Observable {
 	if observation == nil {
 		observation = ts.provider()
 	} else {
 		observation.Clear()
 	}
 	return observation
 }

 // TimeSeries tracks data at granularities from 1 second to 16 weeks.
 type TimeSeries struct {
 	timeSeries
 }

 // NewTimeSeries creates a new TimeSeries using the function provided for creating new Observable.
 func NewTimeSeries(f func() Observable) *TimeSeries {
 	return NewTimeSeriesWithClock(f, defaultClockInstance)
 }

 // NewTimeSeriesWithClock creates a new TimeSeries using the function provided for creating new Observable and the clock for
 // assigning timestamps.
 func NewTimeSeriesWithClock(f func() Observable, clock Clock) *TimeSeries {
 	ts := new(TimeSeries)
 	ts.timeSeries.init(timeSeriesResolutions, f, timeSeriesNumBuckets, clock)
 	return ts
 }

 // MinuteHourSeries tracks data at granularities of 1 minute and 1 hour.
 type MinuteHourSeries struct {
 	timeSeries
 }

 // NewMinuteHourSeries creates a new MinuteHourSeries using the function provided for creating new Observable.
 func NewMinuteHourSeries(f func() Observable) *MinuteHourSeries {
 	return NewMinuteHourSeriesWithClock(f, defaultClockInstance)
 }

 // NewMinuteHourSeriesWithClock creates a new MinuteHourSeries using the function provided for creating new Observable and the clock for
 // assigning timestamps.
 func NewMinuteHourSeriesWithClock(f func() Observable, clock Clock) *MinuteHourSeries {
 	ts := new(MinuteHourSeries)
 	ts.timeSeries.init(minuteHourSeriesResolutions, f,
 		minuteHourSeriesNumBuckets, clock)
 	return ts
 }

 func (ts *MinuteHourSeries) Minute() Observable {
 	return ts.timeSeries.Latest(0, 60)
 }

 func (ts *MinuteHourSeries) Hour() Observable {
 	return ts.timeSeries.Latest(1, 60)
 }

 func minTime(a, b time.Time) time.Time {
 	if a.Before(b) {
 		return a
 	}
 	return b
 }

 func maxTime(a, b time.Time) time.Time {
 	if a.After(b) {
 		return a
 	}
 	return b
 }
	// Copyright 2015 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// Package timeseries implements a time series structure for stats collection.
	package timeseries // import "golang.org/x/net/internal/timeseries"

	import (
	"fmt"
	"log"
	"time"
	)

	const (
	timeSeriesNumBuckets = 64
	minuteHourSeriesNumBuckets = 60
	)

	var timeSeriesResolutions = []time.Duration{
	1 * time.Second,
	10 * time.Second,
	1 * time.Minute,
	10 * time.Minute,
	1 * time.Hour,
	6 * time.Hour,
	24 * time.Hour, // 1 day
	7 * 24 * time.Hour, // 1 week
	4 * 7 * 24 * time.Hour, // 4 weeks
	16 * 7 * 24 * time.Hour, // 16 weeks
	}

	var minuteHourSeriesResolutions = []time.Duration{
	1 * time.Second,
	1 * time.Minute,
	}

	// An Observable is a kind of data that can be aggregated in a time series.
	type Observable interface {
	Multiply(ratio float64) // Multiplies the data in self by a given ratio
	Add(other Observable) // Adds the data from a different observation to self
	Clear() // Clears the observation so it can be reused.
	CopyFrom(other Observable) // Copies the contents of a given observation to self
	}

	// Float attaches the methods of Observable to a float64.
	type Float float64

	// NewFloat returns a Float.
	func NewFloat() Observable {
	f := Float(0)
	return &f
	}

	// String returns the float as a string.
	func (f *Float) String() string { return fmt.Sprintf("%g", f.Value()) }

	// Value returns the float's value.
	func (f Float) Value() float64 { return float64(f) }

	func (f Float) Multiply(ratio float64) { f *= Float(ratio) }

	func (f *Float) Add(other Observable) {
	o := other.(*Float)
	f += o
	}

	func (f Float) Clear() { f = 0 }

	func (f *Float) CopyFrom(other Observable) {
	o := other.(*Float)
	f = o
	}

	// A Clock tells the current time.
	type Clock interface {
	Time() time.Time
	}

	type defaultClock int

	var defaultClockInstance defaultClock

	func (defaultClock) Time() time.Time { return time.Now() }

	// Information kept per level. Each level consists of a circular list of
	// observations. The start of the level may be derived from end and the
	// len(buckets) * sizeInMillis.
	type tsLevel struct {
	oldest int // index to oldest bucketed Observable
	newest int // index to newest bucketed Observable
	end time.Time // end timestamp for this level
	size time.Duration // duration of the bucketed Observable
	buckets []Observable // collections of observations
	provider func() Observable // used for creating new Observable
	}

	func (l *tsLevel) Clear() {
	l.oldest = 0
	l.newest = len(l.buckets) - 1
	l.end = time.Time{}
	for i := range l.buckets {
	if l.buckets[i] != nil {
	l.buckets[i].Clear()
	l.buckets[i] = nil
	}
	}
	}

	func (l *tsLevel) InitLevel(size time.Duration, numBuckets int, f func() Observable) {
	l.size = size
	l.provider = f
	l.buckets = make([]Observable, numBuckets)
	}

	// Keeps a sequence of levels. Each level is responsible for storing data at
	// a given resolution. For example, the first level stores data at a one
	// minute resolution while the second level stores data at a one hour
	// resolution.

	// Each level is represented by a sequence of buckets. Each bucket spans an
	// interval equal to the resolution of the level. New observations are added
	// to the last bucket.
	type timeSeries struct {
	provider func() Observable // make more Observable
	numBuckets int // number of buckets in each level
	levels []*tsLevel // levels of bucketed Observable
	lastAdd time.Time // time of last Observable tracked
	total Observable // convenient aggregation of all Observable
	clock Clock // Clock for getting current time
	pending Observable // observations not yet bucketed
	pendingTime time.Time // what time are we keeping in pending
	dirty bool // if there are pending observations
	}

	// init initializes a level according to the supplied criteria.
	func (ts *timeSeries) init(resolutions []time.Duration, f func() Observable, numBuckets int, clock Clock) {
	ts.provider = f
	ts.numBuckets = numBuckets
	ts.clock = clock
	ts.levels = make([]*tsLevel, len(resolutions))

	for i := range resolutions {
	if i > 0 && resolutions[i-1] >= resolutions[i] {
	log.Print("timeseries: resolutions must be monotonically increasing")
	break
	}
	newLevel := new(tsLevel)
	newLevel.InitLevel(resolutions[i], ts.numBuckets, ts.provider)
	ts.levels[i] = newLevel
	}

	ts.Clear()
	}

	// Clear removes all observations from the time series.
	func (ts *timeSeries) Clear() {
	ts.lastAdd = time.Time{}
	ts.total = ts.resetObservation(ts.total)
	ts.pending = ts.resetObservation(ts.pending)
	ts.pendingTime = time.Time{}
	ts.dirty = false

	for i := range ts.levels {
	ts.levels[i].Clear()
	}
	}

	// Add records an observation at the current time.
	func (ts *timeSeries) Add(observation Observable) {
	ts.AddWithTime(observation, ts.clock.Time())
	}

	// AddWithTime records an observation at the specified time.
	func (ts *timeSeries) AddWithTime(observation Observable, t time.Time) {

	smallBucketDuration := ts.levels[0].size

	if t.After(ts.lastAdd) {
	ts.lastAdd = t
	}

	if t.After(ts.pendingTime) {
	ts.advance(t)
	ts.mergePendingUpdates()
	ts.pendingTime = ts.levels[0].end
	ts.pending.CopyFrom(observation)
	ts.dirty = true
	} else if t.After(ts.pendingTime.Add(-1 * smallBucketDuration)) {
	// The observation is close enough to go into the pending bucket.
	// This compensates for clock skewing and small scheduling delays
	// by letting the update stay in the fast path.
	ts.pending.Add(observation)
	ts.dirty = true
	} else {
	ts.mergeValue(observation, t)
	}
	}

	// mergeValue inserts the observation at the specified time in the past into all levels.
	func (ts *timeSeries) mergeValue(observation Observable, t time.Time) {
	for _, level := range ts.levels {
	index := (ts.numBuckets - 1) - int(level.end.Sub(t)/level.size)
	if 0 <= index && index < ts.numBuckets {
	bucketNumber := (level.oldest + index) % ts.numBuckets
	if level.buckets[bucketNumber] == nil {
	level.buckets[bucketNumber] = level.provider()
	}
	level.buckets[bucketNumber].Add(observation)
	}
	}
	ts.total.Add(observation)
	}

	// mergePendingUpdates applies the pending updates into all levels.
	func (ts *timeSeries) mergePendingUpdates() {
	if ts.dirty {
	ts.mergeValue(ts.pending, ts.pendingTime)
	ts.pending = ts.resetObservation(ts.pending)
	ts.dirty = false
	}
	}

	// advance cycles the buckets at each level until the latest bucket in
	// each level can hold the time specified.
	func (ts *timeSeries) advance(t time.Time) {
	if !t.After(ts.levels[0].end) {
	return
	}
	for i := 0; i < len(ts.levels); i++ {
	level := ts.levels[i]
	if !level.end.Before(t) {
	break
	}

	// If the time is sufficiently far, just clear the level and advance
	// directly.
	if !t.Before(level.end.Add(level.size * time.Duration(ts.numBuckets))) {
	for _, b := range level.buckets {
	ts.resetObservation(b)
	}
	level.end = time.Unix(0, (t.UnixNano()/level.size.Nanoseconds())*level.size.Nanoseconds())
	}

	for t.After(level.end) {
	level.end = level.end.Add(level.size)
	level.newest = level.oldest
	level.oldest = (level.oldest + 1) % ts.numBuckets
	ts.resetObservation(level.buckets[level.newest])
	}

	t = level.end
	}
	}

	// Latest returns the sum of the num latest buckets from the level.
	func (ts *timeSeries) Latest(level, num int) Observable {
	now := ts.clock.Time()
	if ts.levels[0].end.Before(now) {
	ts.advance(now)
	}

	ts.mergePendingUpdates()

	result := ts.provider()
	l := ts.levels[level]
	index := l.newest

	for i := 0; i < num; i++ {
	if l.buckets[index] != nil {
	result.Add(l.buckets[index])
	}
	if index == 0 {
	index = ts.numBuckets
	}
	index--
	}

	return result
	}

	// LatestBuckets returns a copy of the num latest buckets from level.
	func (ts *timeSeries) LatestBuckets(level, num int) []Observable {
	if level < 0 \|\| level > len(ts.levels) {
	log.Print("timeseries: bad level argument: ", level)
	return nil
	}
	if num < 0 \|\| num >= ts.numBuckets {
	log.Print("timeseries: bad num argument: ", num)
	return nil
	}

	results := make([]Observable, num)
	now := ts.clock.Time()
	if ts.levels[0].end.Before(now) {
	ts.advance(now)
	}

	ts.mergePendingUpdates()

	l := ts.levels[level]
	index := l.newest

	for i := 0; i < num; i++ {
	result := ts.provider()
	results[i] = result
	if l.buckets[index] != nil {
	result.CopyFrom(l.buckets[index])
	}

	if index == 0 {
	index = ts.numBuckets
	}
	index -= 1
	}
	return results
	}

	// ScaleBy updates observations by scaling by factor.
	func (ts *timeSeries) ScaleBy(factor float64) {
	for _, l := range ts.levels {
	for i := 0; i < ts.numBuckets; i++ {
	l.buckets[i].Multiply(factor)
	}
	}

	ts.total.Multiply(factor)
	ts.pending.Multiply(factor)
	}

	// Range returns the sum of observations added over the specified time range.
	// If start or finish times don't fall on bucket boundaries of the same
	// level, then return values are approximate answers.
	func (ts *timeSeries) Range(start, finish time.Time) Observable {
	return ts.ComputeRange(start, finish, 1)[0]
	}

	// Recent returns the sum of observations from the last delta.
	func (ts *timeSeries) Recent(delta time.Duration) Observable {
	now := ts.clock.Time()
	return ts.Range(now.Add(-delta), now)
	}

	// Total returns the total of all observations.
	func (ts *timeSeries) Total() Observable {
	ts.mergePendingUpdates()
	return ts.total
	}

	// ComputeRange computes a specified number of values into a slice using
	// the observations recorded over the specified time period. The return
	// values are approximate if the start or finish times don't fall on the
	// bucket boundaries at the same level or if the number of buckets spanning
	// the range is not an integral multiple of num.
	func (ts *timeSeries) ComputeRange(start, finish time.Time, num int) []Observable {
	if start.After(finish) {
	log.Printf("timeseries: start > finish, %v>%v", start, finish)
	return nil
	}

	if num < 0 {
	log.Printf("timeseries: num < 0, %v", num)
	return nil
	}

	results := make([]Observable, num)

	for _, l := range ts.levels {
	if !start.Before(l.end.Add(-l.size * time.Duration(ts.numBuckets))) {
	ts.extract(l, start, finish, num, results)
	return results
	}
	}

	// Failed to find a level that covers the desired range. So just
	// extract from the last level, even if it doesn't cover the entire
	// desired range.
	ts.extract(ts.levels[len(ts.levels)-1], start, finish, num, results)

	return results
	}

	// RecentList returns the specified number of values in slice over the most
	// recent time period of the specified range.
	func (ts *timeSeries) RecentList(delta time.Duration, num int) []Observable {
	if delta < 0 {
	return nil
	}
	now := ts.clock.Time()
	return ts.ComputeRange(now.Add(-delta), now, num)
	}

	// extract returns a slice of specified number of observations from a given
	// level over a given range.
	func (ts timeSeries) extract(l tsLevel, start, finish time.Time, num int, results []Observable) {
	ts.mergePendingUpdates()

	srcInterval := l.size
	dstInterval := finish.Sub(start) / time.Duration(num)
	dstStart := start
	srcStart := l.end.Add(-srcInterval * time.Duration(ts.numBuckets))

	srcIndex := 0

	// Where should scanning start?
	if dstStart.After(srcStart) {
	advance := int(dstStart.Sub(srcStart) / srcInterval)
	srcIndex += advance
	srcStart = srcStart.Add(time.Duration(advance) * srcInterval)
	}

	// The i'th value is computed as show below.
	// interval = (finish/start)/num
	// i'th value = sum of observation in range
	// [ start + i * interval,
	// start + (i + 1) * interval )
	for i := 0; i < num; i++ {
	results[i] = ts.resetObservation(results[i])
	dstEnd := dstStart.Add(dstInterval)
	for srcIndex < ts.numBuckets && srcStart.Before(dstEnd) {
	srcEnd := srcStart.Add(srcInterval)
	if srcEnd.After(ts.lastAdd) {
	srcEnd = ts.lastAdd
	}

	if !srcEnd.Before(dstStart) {
	srcValue := l.buckets[(srcIndex+l.oldest)%ts.numBuckets]
	if !srcStart.Before(dstStart) && !srcEnd.After(dstEnd) {
	// dst completely contains src.
	if srcValue != nil {
	results[i].Add(srcValue)
	}
	} else {
	// dst partially overlaps src.
	overlapStart := maxTime(srcStart, dstStart)
	overlapEnd := minTime(srcEnd, dstEnd)
	base := srcEnd.Sub(srcStart)
	fraction := overlapEnd.Sub(overlapStart).Seconds() / base.Seconds()

	used := ts.provider()
	if srcValue != nil {
	used.CopyFrom(srcValue)
	}
	used.Multiply(fraction)
	results[i].Add(used)
	}

	if srcEnd.After(dstEnd) {
	break
	}
	}
	srcIndex++
	srcStart = srcStart.Add(srcInterval)
	}
	dstStart = dstStart.Add(dstInterval)
	}
	}

	// resetObservation clears the content so the struct may be reused.
	func (ts *timeSeries) resetObservation(observation Observable) Observable {
	if observation == nil {
	observation = ts.provider()
	} else {
	observation.Clear()
	}
	return observation
	}

	// TimeSeries tracks data at granularities from 1 second to 16 weeks.
	type TimeSeries struct {
	timeSeries
	}

	// NewTimeSeries creates a new TimeSeries using the function provided for creating new Observable.
	func NewTimeSeries(f func() Observable) *TimeSeries {
	return NewTimeSeriesWithClock(f, defaultClockInstance)
	}

	// NewTimeSeriesWithClock creates a new TimeSeries using the function provided for creating new Observable and the clock for
	// assigning timestamps.
	func NewTimeSeriesWithClock(f func() Observable, clock Clock) *TimeSeries {
	ts := new(TimeSeries)
	ts.timeSeries.init(timeSeriesResolutions, f, timeSeriesNumBuckets, clock)
	return ts
	}

	// MinuteHourSeries tracks data at granularities of 1 minute and 1 hour.
	type MinuteHourSeries struct {
	timeSeries
	}

	// NewMinuteHourSeries creates a new MinuteHourSeries using the function provided for creating new Observable.
	func NewMinuteHourSeries(f func() Observable) *MinuteHourSeries {
	return NewMinuteHourSeriesWithClock(f, defaultClockInstance)
	}

	// NewMinuteHourSeriesWithClock creates a new MinuteHourSeries using the function provided for creating new Observable and the clock for
	// assigning timestamps.
	func NewMinuteHourSeriesWithClock(f func() Observable, clock Clock) *MinuteHourSeries {
	ts := new(MinuteHourSeries)
	ts.timeSeries.init(minuteHourSeriesResolutions, f,
	minuteHourSeriesNumBuckets, clock)
	return ts
	}

	func (ts *MinuteHourSeries) Minute() Observable {
	return ts.timeSeries.Latest(0, 60)
	}

	func (ts *MinuteHourSeries) Hour() Observable {
	return ts.timeSeries.Latest(1, 60)
	}

	func minTime(a, b time.Time) time.Time {
	if a.Before(b) {
	return a
	}
	return b
	}

	func maxTime(a, b time.Time) time.Time {
	if a.After(b) {
	return a
	}
	return b
	}