sortedmap

package module
v1.0.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 7, 2023 License: MIT Imports: 6 Imported by: 2

README

SortedMap

Go Report Card GoDoc

SortedMap is a simple library that provides a value-sorted map[K]V 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/tobshub/go-sortedmap
Complexity
Operation Worst-Case
Has, Get O(1)
Delete, Insert, Replace O(n)

Example Usage

package main

import (
  "fmt"
  "time"

  "github.com/tobshub/go-sortedmap"
  "github.com/tobshub/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                               	    500	       88.52 ns/op

BenchmarkHas1of1CachedRecords-8              	    500	        7.754 ns/op
BenchmarkHas1of1Records-8                    	    500	       88.17 ns/op

BenchmarkGet1of1CachedRecords-8              	    500	       12.22 ns/op
BenchmarkGet1of1Records-8                    	    500	       78.72 ns/op

BenchmarkDelete1of1Records-8                 	    500	      156.5 ns/op

BenchmarkInsert1Record-8                     	    500	      835.6 ns/op
BenchmarkReplace1of1Records-8                	    500	      314.2 ns/op

BenchmarkDelete1of10Records-8                	    500	      567.0 ns/op
BenchmarkDelete1of100Records-8               	    500	     1895 ns/op
BenchmarkDelete1of1000Records-8              	    500	     2314 ns/op
BenchmarkDelete1of10000Records-8             	    500	    37247 ns/op

BenchmarkBatchDelete10of10Records-8          	    500	     2730 ns/op
BenchmarkBatchDelete100of100Records-8        	    500	    38437 ns/op
BenchmarkBatchDelete1000of1000Records-8      	    500	   586059 ns/op
BenchmarkBatchDelete10000of10000Records-8    	    500	 16578997 ns/op

BenchmarkBatchGet10of10Records-8             	    500	      907.9 ns/op
BenchmarkBatchGet100of100Records-8           	    500	     6139 ns/op
BenchmarkBatchGet1000of1000Records-8         	    500	    43334 ns/op
BenchmarkBatchGet10000of10000Records-8       	    500	   559872 ns/op

BenchmarkBatchHas10of10Records-8             	    500	      629.0 ns/op
BenchmarkBatchHas100of100Records-8           	    500	     5277 ns/op
BenchmarkBatchHas1000of1000Records-8         	    500	    35924 ns/op
BenchmarkBatchHas10000of10000Records-8       	    500	   510189 ns/op

BenchmarkBatchInsert10Records-8              	    500	     6093 ns/op
BenchmarkBatchInsert100Records-8             	    500	    64635 ns/op
BenchmarkBatchInsert1000Records-8            	    500	   861841 ns/op
BenchmarkBatchInsert10000Records-8           	    500	 19096605 ns/op

BenchmarkReplace1of10Records-8               	    500	      800.1 ns/op
BenchmarkReplace1of100Records-8              	    500	     2721 ns/op
BenchmarkReplace1of1000Records-8             	    500	     3647 ns/op
BenchmarkReplace1of10000Records-8            	    500	    56905 ns/op

BenchmarkBatchReplace10of10Records-8         	    500	     8055 ns/op
BenchmarkBatchReplace100of100Records-8       	    500	   104597 ns/op
BenchmarkBatchReplace1000of1000Records-8     	    500	  1580840 ns/op
BenchmarkBatchReplace10000of10000Records-8   	    500	 53922019 ns/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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type ComparisonFunc 

type ComparisonFunc[V any] func(i, j V) bool

ComparisonFunc defines the type of the comparison function for the chosen value type.

type IterCallbackFunc 

type IterCallbackFunc[K comparable, V any] func(rec Record[K, V]) bool

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[K comparable, V any] 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[K, V]) Close 

func (iterCh *IterChCloser[K, V]) 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[K, V]) Records 

func (iterCh *IterChCloser[K, V]) Records() <-chan Record[K, V]

Records returns a channel that records can be read from.

type IterChParams 

type IterChParams[V any] struct {
	Reversed               bool
	SendTimeout            time.Duration
	BufSize                int
	LowerBound, UpperBound V
}

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[K comparable, V any] struct {
	Key K
	Val V
}

Record defines a type used in batching and iterations, where keys and values are used together.

type SortedMap 

type SortedMap[K comparable, V any] 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[K comparable, V any](n int, cmpFn ComparisonFunc[V]) *SortedMap[K, V]

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[K, V]) BatchDelete 

func (sm *SortedMap[K, V]) BatchDelete(keys []K) []bool

BatchDelete removes values from the collection, using the given keys, returning a slice of the results.

func (*SortedMap[K, V]) BatchGet 

func (sm *SortedMap[K, V]) BatchGet(keys []K) ([]V, []bool)

BatchGet retrieves values with their read statuses from the collection, using the given keys.

func (*SortedMap[K, V]) BatchHas 

func (sm *SortedMap[K, V]) BatchHas(keys []K) []bool

BatchHas checks if the keys exist in the collection and returns a slice containing the results.

func (*SortedMap[K, V]) BatchInsert 

func (sm *SortedMap[K, V]) BatchInsert(recs []Record[K, V]) []bool

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[K, V]) BatchInsertMap 

func (sm *SortedMap[K, V]) BatchInsertMap(v map[K]V) error

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[K, V]) BatchReplace 

func (sm *SortedMap[K, V]) BatchReplace(recs []Record[K, V])

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[K, V]) BatchReplaceMap 

func (sm *SortedMap[K, V]) BatchReplaceMap(v map[K]V) error

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[K, V]) BoundedDelete 

func (sm *SortedMap[K, V]) BoundedDelete(lowerBound, upperBound V) error

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[K, V]) BoundedIterCh 

func (sm *SortedMap[K, V]) BoundedIterCh(reversed bool, lowerBound, upperBound V) (IterChCloser[K, V], 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[K, V]) BoundedIterFunc 

func (sm *SortedMap[K, V]) BoundedIterFunc(reversed bool, lowerBound, upperBound V, f IterCallbackFunc[K, V]) 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[K, V]) BoundedKeys 

func (sm *SortedMap[K, V]) BoundedKeys(lowerBound, upperBound V) ([]K, error)

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[K, V]) CustomIterCh 

func (sm *SortedMap[K, V]) CustomIterCh(params IterChParams[V]) (IterChCloser[K, V], 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[K, V]) Delete 

func (sm *SortedMap[K, V]) Delete(key K) bool

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[K, V]) Get 

func (sm *SortedMap[K, V]) Get(key K) (V, bool)

Get retrieves a value from the collection, using the given key.

func (*SortedMap[K, V]) Has 

func (sm *SortedMap[K, V]) Has(key K) bool

Has checks if the key exists in the collection.

func (*SortedMap[K, V]) Insert 

func (sm *SortedMap[K, V]) Insert(key K, val V) bool

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[K, V]) IterCh 

func (sm *SortedMap[K, V]) IterCh() (IterChCloser[K, V], 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[K, V]) IterFunc 

func (sm *SortedMap[K, V]) IterFunc(reversed bool, f IterCallbackFunc[K, V])

IterFunc passes each record to the specified callback function. Sort order is reversed if the reversed argument is set to true.

func (*SortedMap[K, V]) Keys 

func (sm *SortedMap[K, V]) Keys() []K

Keys returns a slice containing sorted keys. The returned slice is valid until the next modification to the SortedMap structure.

func (*SortedMap[K, V]) Len 

func (sm *SortedMap[K, V]) Len() int

Len returns the number of items in the collection.

func (*SortedMap[K, V]) Map 

func (sm *SortedMap[K, V]) Map() map[K]V

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.

func (*SortedMap[K, V]) MarshalJSON added in v1.0.1 

func (m *SortedMap[K, V]) MarshalJSON() ([]byte, error)

func (*SortedMap[K, V]) Replace 

func (sm *SortedMap[K, V]) Replace(key K, val V)

Replace uses the provided 'less than' function to insert sort. Even if the key already exists, the value will be inserted. Use Insert for the alternative functionality.

func (*SortedMap[K, V]) SetComparisonFunc added in v1.0.1 

func (m *SortedMap[K, V]) SetComparisonFunc(cmpFn ComparisonFunc[V])

func (*SortedMap[K, V]) UnmarshalJSON added in v1.0.1 

func (m *SortedMap[K, V]) UnmarshalJSON(data []byte) error

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.