timesortedlist

README

time-sorted-list

Time sorted list in Golang.

What this data structure for?

• in memory time series data store
• any data sorted in time series
• query data using from or until in unixtime

and requires only standard package

Structure

Searching data through unixtime

Since this data structure intented to store time series data, it has ability to search item via unix time.

timeItems := tsl.GetItemsFrom(unixTime)
timeItems := tsl.GetItemsUntil(unixTime)

Add item

When you add item, it will automatically sort

tsl.AddItem(unixTime, timeItem)

Background

When we handle time series data, we need something like a sorted list (In Golang, by implementing sort.Interface we can do this).

Most of cases, we need not only storing data in time sequence but also querying data by time.

This data structure is intented to handle such cases.

On going

• User can decide which item (old or new) should be dropped if list is filled

Test

We use ginkgo for testing

$ ginkgo -r -v .

••••••••••••••••••••
Ran 20 of 20 Specs in 0.002 seconds
SUCCESS! -- 20 Passed | 0 Failed | 0 Pending | 0 Skipped
PASS
coverage: 100.0% of statements

Documentation

Overview

Package timesortedlist is a package of a data structure storing time series data. It's goal is to store data such as logs, sequence, ... that should be ordered.

Feature

• in memory time series data store
• any data sorted in time series
• query data using from or until in unixtime

Usage

Here is a simple usage.

Add item

When you add item, this list will automatically sort.

tsl.AddItem(unixTime, timeItem)

Searching data through unixtime

Since this data structure intented to store time series data, it has abilty to search item via unix time.

timeItems := tsl.GetItemsFrom(unixTime)
timeItems := tsl.GetItemsUntil(unixTime)

Index

• type ITimeSortedList
  • func NewTimeSortedList(capacity int) ITimeSortedList
• type TimeItem
• type TimeSortedList
  • func (tsl *TimeSortedList) AddItem(unixTime int64, item interface{})
  • func (tsl *TimeSortedList) AddTimeItem(item *TimeItem)
  • func (tsl *TimeSortedList) Cap() int
  • func (tsl *TimeSortedList) Filled() bool
  • func (tsl *TimeSortedList) GetItem(idx int) *TimeItem
  • func (tsl *TimeSortedList) GetItemsFrom(fromUnixTime int64) []TimeItem
  • func (tsl *TimeSortedList) GetItemsFromUntil(fromUnixTime, untilUnixTime int64) []TimeItem
  • func (tsl *TimeSortedList) GetItemsUntil(untilUnixTime int64) []TimeItem
  • func (tsl *TimeSortedList) Len() int

Types

type ITimeSortedList

type ITimeSortedList interface {
	Len() int
	Cap() int
	AddItem(unixTime int64, item interface{})
	AddTimeItem(item *TimeItem)
	Filled() bool
	GetItem(idx int) *TimeItem
	GetItemsFrom(fromUnixTime int64) []TimeItem
	GetItemsUntil(untilUnixTime int64) []TimeItem
	GetItemsFromUntil(fromUnixTime, untilUnixTime int64) []TimeItem
}

ITimeSortedList is a interface of TimeSortedList. Use for mocking in your test.

func NewTimeSortedList

func NewTimeSortedList(capacity int) ITimeSortedList

NewTimeSortedList initializes TimeSortedList. capacity is the max size of internal slice for not using more memory.

type TimeItem

type TimeItem struct {
	UnixTime int64
	Item     interface{}
}

TimeItem is a struct for storing item with time infomation.

type TimeSortedList

type TimeSortedList struct {
	// contains filtered or unexported fields
}

TimeSortedList holds time series items which are sorted. Inserted items can be obtained by specifying unix time.

func (*TimeSortedList) AddItem

func (tsl *TimeSortedList) AddItem(unixTime int64, item interface{})

AddItem adds any structure with specified time.

func (*TimeSortedList) AddTimeItem

func (tsl *TimeSortedList) AddTimeItem(item *TimeItem)

AddTimeItem adds TimeItem with time ordered.

func (*TimeSortedList) Cap

func (tsl *TimeSortedList) Cap() int

Cap gets initialized capacity. If length of list is same as Cap then the list is filled.

func (*TimeSortedList) Filled

func (tsl *TimeSortedList) Filled() bool

Filled checks if the list is filled.

func (*TimeSortedList) GetItem

func (tsl *TimeSortedList) GetItem(idx int) *TimeItem

GetItem gets item with specified index.

func (*TimeSortedList) GetItemsFrom

func (tsl *TimeSortedList) GetItemsFrom(fromUnixTime int64) []TimeItem

GetItemsFrom gets item from specified time

func (*TimeSortedList) GetItemsFromUntil

func (tsl *TimeSortedList) GetItemsFromUntil(fromUnixTime, untilUnixTime int64) []TimeItem

GetItemsFromUntil get items with specified time range

func (*TimeSortedList) GetItemsUntil

func (tsl *TimeSortedList) GetItemsUntil(untilUnixTime int64) []TimeItem

GetItemsUntil gets item until specified time

func (*TimeSortedList) Len

func (tsl *TimeSortedList) Len() int

Len gets actual length of list.