README
¶
SortedMap
SortedMap is a simple library that provides a value-sorted map[interface{}]interface{} type and methods combined from Go 1 map and slice primitives.
This data structure allows for roughly constant-time reads and for efficiently iterating over only a section of stored values.
go get -u github.com/umpc/go-sortedmap
Complexity
| Operation | Worst-Case |
|---|---|
| Has, Get | O(1) |
| Delete, Insert, Replace | O(n) |
Example Usage
package main
import (
"fmt"
"time"
"github.com/umpc/go-sortedmap"
"github.com/umpc/go-sortedmap/asc"
)
func main() {
// Create an empty SortedMap with a size suggestion and a less than function:
sm := sortedmap.New(4, asc.Time)
// Insert example records:
sm.Insert("OpenBSD", time.Date(1995, 10, 18, 8, 37, 1, 0, time.UTC))
sm.Insert("UnixTime", time.Date(1970, 1, 1, 0, 0, 0, 0, time.UTC))
sm.Insert("Linux", time.Date(1991, 8, 25, 20, 57, 8, 0, time.UTC))
sm.Insert("GitHub", time.Date(2008, 4, 10, 0, 0, 0, 0, time.UTC))
// Set iteration options:
reversed := true
lowerBound := time.Date(1994, 1, 1, 0, 0, 0, 0, time.UTC)
upperBound := time.Now()
// Select values > lowerBound and values <= upperBound.
// Loop through the values, in reverse order:
iterCh, err := sm.BoundedIterCh(reversed, lowerBound, upperBound)
if err != nil {
fmt.Println(err)
return
}
defer iterCh.Close()
for rec := range iterCh.Records() {
fmt.Printf("%+v\n", rec)
}
}
Check out the examples, documentation, and test files, for more features and further explanations.
Benchmarks
BenchmarkNew-8 20000000 98.8 ns/op 96 B/op 2 allocs/op
BenchmarkHas1of1CachedRecords-8 50000000 27.3 ns/op 0 B/op 0 allocs/op
BenchmarkHas1of1Records-8 20000000 94.1 ns/op 0 B/op 0 allocs/op
BenchmarkGet1of1CachedRecords-8 50000000 27.3 ns/op 0 B/op 0 allocs/op
BenchmarkGet1of1Records-8 20000000 96.8 ns/op 0 B/op 0 allocs/op
BenchmarkDelete1of1Records-8 5000000 285 ns/op 0 B/op 0 allocs/op
BenchmarkInsert1Record-8 3000000 442 ns/op 304 B/op 2 allocs/op
BenchmarkReplace1of1Records-8 5000000 378 ns/op 0 B/op 0 allocs/op
BenchmarkDelete1of10Records-8 2000000 615 ns/op 0 B/op 0 allocs/op
BenchmarkDelete1of100Records-8 1000000 1005 ns/op 0 B/op 0 allocs/op
BenchmarkDelete1of1000Records-8 1000000 1987 ns/op 0 B/op 0 allocs/op
BenchmarkDelete1of10000Records-8 300000 5473 ns/op 0 B/op 0 allocs/op
BenchmarkBatchDelete10of10Records-8 500000 3410 ns/op 16 B/op 1 allocs/op
BenchmarkBatchDelete100of100Records-8 30000 47069 ns/op 112 B/op 1 allocs/op
BenchmarkBatchDelete1000of1000Records-8 2000 721201 ns/op 1024 B/op 1 allocs/op
BenchmarkBatchDelete10000of10000Records-8 100 19275331 ns/op 10240 B/op 1 allocs/op
BenchmarkBatchGet10of10Records-8 2000000 902 ns/op 176 B/op 2 allocs/op
BenchmarkBatchGet100of100Records-8 300000 5550 ns/op 1904 B/op 2 allocs/op
BenchmarkBatchGet1000of1000Records-8 30000 49057 ns/op 17408 B/op 2 allocs/op
BenchmarkBatchGet10000of10000Records-8 2000 710611 ns/op 174080 B/op 2 allocs/op
BenchmarkBatchHas10of10Records-8 2000000 742 ns/op 16 B/op 1 allocs/op
BenchmarkBatchHas100of100Records-8 300000 5102 ns/op 112 B/op 1 allocs/op
BenchmarkBatchHas1000of1000Records-8 30000 46257 ns/op 1024 B/op 1 allocs/op
BenchmarkBatchHas10000of10000Records-8 3000 519497 ns/op 10240 B/op 1 allocs/op
BenchmarkBatchInsert10Records-8 300000 4164 ns/op 1382 B/op 8 allocs/op
BenchmarkBatchInsert100Records-8 30000 54184 ns/op 14912 B/op 19 allocs/op
BenchmarkBatchInsert1000Records-8 2000 844344 ns/op 201969 B/op 78 allocs/op
BenchmarkBatchInsert10000Records-8 100 25911455 ns/op 2121554 B/op 584 allocs/op
BenchmarkReplace1of10Records-8 1000000 1021 ns/op 0 B/op 0 allocs/op
BenchmarkReplace1of100Records-8 1000000 1669 ns/op 0 B/op 0 allocs/op
BenchmarkReplace1of1000Records-8 500000 3187 ns/op 0 B/op 0 allocs/op
BenchmarkReplace1of10000Records-8 200000 8778 ns/op 0 B/op 0 allocs/op
BenchmarkBatchReplace10of10Records-8 200000 6934 ns/op 0 B/op 0 allocs/op
BenchmarkBatchReplace100of100Records-8 10000 100186 ns/op 0 B/op 0 allocs/op
BenchmarkBatchReplace1000of1000Records-8 1000 1546355 ns/op 0 B/op 0 allocs/op
BenchmarkBatchReplace10000of10000Records-8 20 58396360 ns/op 0 B/op 0 allocs/op
The above benchmark tests were ran using a 4.0GHz Intel Core i7-4790K (Haswell) CPU.
License
The source code is available under the MIT License.
Documentation
¶
Index ¶
- type ComparisonFunc
- type IterCallbackFunc
- type IterChCloser
- type IterChParams
- type Record
- type SortedMap
- func (sm *SortedMap) BatchDelete(keys []interface{}) []bool
- func (sm *SortedMap) BatchGet(keys []interface{}) ([]interface{}, []bool)
- func (sm *SortedMap) BatchHas(keys []interface{}) []bool
- func (sm *SortedMap) BatchInsert(recs []Record) []bool
- func (sm *SortedMap) BatchInsertMap(v interface{}) error
- func (sm *SortedMap) BatchReplace(recs []Record)
- func (sm *SortedMap) BatchReplaceMap(v interface{}) error
- func (sm *SortedMap) BoundedDelete(lowerBound, upperBound interface{}) error
- func (sm *SortedMap) BoundedIterCh(reversed bool, lowerBound, upperBound interface{}) (IterChCloser, error)
- func (sm *SortedMap) BoundedIterFunc(reversed bool, lowerBound, upperBound interface{}, f IterCallbackFunc) error
- func (sm *SortedMap) BoundedKeys(lowerBound, upperBound interface{}) ([]interface{}, error)
- func (sm *SortedMap) CustomIterCh(params IterChParams) (IterChCloser, error)
- func (sm *SortedMap) Delete(key interface{}) bool
- func (sm *SortedMap) Get(key interface{}) (interface{}, bool)
- func (sm *SortedMap) Has(key interface{}) bool
- func (sm *SortedMap) Insert(key, val interface{}) bool
- func (sm *SortedMap) IterCh() (IterChCloser, error)
- func (sm *SortedMap) IterFunc(reversed bool, f IterCallbackFunc)
- func (sm *SortedMap) Keys() []interface{}
- func (sm *SortedMap) Len() int
- func (sm *SortedMap) Map() map[interface{}]interface{}
- func (sm *SortedMap) Replace(key, val interface{})
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ComparisonFunc ¶
type ComparisonFunc func(i, j interface{}) bool
ComparisonFunc defines the type of the comparison function for the chosen value type.
type IterCallbackFunc ¶
IterCallbackFunc defines the type of function that is passed into an IterFunc method. The function is passed a record value argument.
type IterChCloser ¶
type IterChCloser struct {
// contains filtered or unexported fields
}
IterChCloser allows records to be read through a channel that is returned by the Records method. IterChCloser values should be closed after use using the Close method.
func (*IterChCloser) Close ¶
func (iterCh *IterChCloser) Close() error
Close cancels a channel-based iteration and causes the sending goroutine to exit. Close should be used after an IterChCloser is finished being read from.
func (*IterChCloser) Records ¶
func (iterCh *IterChCloser) Records() <-chan Record
Records returns a channel that records can be read from.
type IterChParams ¶
type IterChParams struct {
Reversed bool
SendTimeout time.Duration
BufSize int
LowerBound,
UpperBound interface{}
}
IterChParams contains configurable settings for CustomIterCh. SendTimeout is disabled by default, though it should be set to allow channel send goroutines to time-out. BufSize is set to 1 if its field is set to a lower value. LowerBound and UpperBound default to regular iteration when left unset.
type Record ¶
type Record struct {
Key,
Val interface{}
}
Record defines a type used in batching and iterations, where keys and values are used together.
type SortedMap ¶
type SortedMap struct {
// contains filtered or unexported fields
}
SortedMap contains a map, a slice, and references to one or more comparison functions. SortedMap is not concurrency-safe, though it can be easily wrapped by a developer-defined type.
func New ¶
func New(n int, cmpFn ComparisonFunc) *SortedMap
New creates and initializes a new SortedMap structure and then returns a reference to it. New SortedMaps are created with a backing map/slice of length/capacity n.
func (*SortedMap) BatchDelete ¶
BatchDelete removes values from the collection, using the given keys, returning a slice of the results.
func (*SortedMap) BatchGet ¶
BatchGet retrieves values with their read statuses from the collection, using the given keys.
func (*SortedMap) BatchHas ¶
BatchHas checks if the keys exist in the collection and returns a slice containing the results.
func (*SortedMap) BatchInsert ¶
BatchInsert adds all given records to the collection and returns a slice containing each record's insert status. If a key already exists, the value will not be inserted. Use BatchReplace for the alternative functionality.
func (*SortedMap) BatchInsertMap ¶
BatchInsertMap adds all map keys and values to the collection. If a key already exists, the value will not be inserted and an error will be returned. Use BatchReplaceMap for the alternative functionality.
func (*SortedMap) BatchReplace ¶
BatchReplace adds all given records to the collection. Even if a key already exists, the value will be inserted. Use BatchInsert for the alternative functionality.
func (*SortedMap) BatchReplaceMap ¶
BatchReplaceMap adds all map keys and values to the collection. Even if a key already exists, the value will be inserted. Use BatchInsertMap for the alternative functionality.
func (*SortedMap) BoundedDelete ¶
BoundedDelete removes values that are between the given values from the collection. BoundedDelete returns true if the operation was successful, or false otherwise.
func (*SortedMap) BoundedIterCh ¶
func (sm *SortedMap) BoundedIterCh(reversed bool, lowerBound, upperBound interface{}) (IterChCloser, error)
BoundedIterCh returns a channel that sorted records can be read from and processed. BoundedIterCh starts at the lower bound value and sends all values in the collection until reaching the upper bounds value. Sort order is reversed if the reversed argument is set to true. This method defaults to the expected behavior of blocking until a channel send completes, with no timeout.
func (*SortedMap) BoundedIterFunc ¶
func (sm *SortedMap) BoundedIterFunc(reversed bool, lowerBound, upperBound interface{}, f IterCallbackFunc) error
BoundedIterFunc starts at the lower bound value and passes all values in the collection to the callback function until reaching the upper bounds value. Sort order is reversed if the reversed argument is set to true.
func (*SortedMap) BoundedKeys ¶
BoundedKeys returns a slice containing sorted keys equal to or between the given bounds. The returned slice is valid until the next modification to the SortedMap structure.
func (*SortedMap) CustomIterCh ¶
func (sm *SortedMap) CustomIterCh(params IterChParams) (IterChCloser, error)
CustomIterCh returns a channel that sorted records can be read from and processed. CustomIterCh starts at the lower bound value and sends all values in the collection until reaching the upper bounds value. Sort order is reversed if the reversed argument is set to true. This method defaults to the expected behavior of blocking until a channel send completes, with no timeout.
func (*SortedMap) Delete ¶
Delete removes a value from the collection, using the given key. Because the index position of each sorted key changes on each insert and a simpler structure was ideal, deletes can have a worse-case complexity of O(n), meaning the goroutine must loop through the sorted slice to find and delete the given key.
func (*SortedMap) Insert ¶
Insert uses the provided 'less than' function to insert sort and add the value to the collection and returns a value containing the record's insert status. If the key already exists, the value will not be inserted. Use Replace for the alternative functionality.
func (*SortedMap) IterCh ¶
func (sm *SortedMap) IterCh() (IterChCloser, error)
IterCh returns a channel that sorted records can be read from and processed. This method defaults to the expected behavior of blocking until a read, with no timeout.
func (*SortedMap) IterFunc ¶
func (sm *SortedMap) IterFunc(reversed bool, f IterCallbackFunc)
IterFunc passes each record to the specified callback function. Sort order is reversed if the reversed argument is set to true.
func (*SortedMap) Keys ¶
func (sm *SortedMap) Keys() []interface{}
Keys returns a slice containing sorted keys. The returned slice is valid until the next modification to the SortedMap structure.
func (*SortedMap) Map ¶
func (sm *SortedMap) Map() map[interface{}]interface{}
Map returns a map containing keys mapped to values. The returned map is valid until the next modification to the SortedMap structure. The map can be used with ether the Keys or BoundedKeys methods to select a range of items and iterate over them using a slice for-range loop, rather than a channel for-range loop.
Source Files
Directories