indexmap

README

IndexMap

We often created a map with $ID \to Object$ to seek data, but this limits us to seek the data with only ID. to seek data with any field without SQL in database, IndexMap is the data structure you can reach this.

Installation

To get the IndexMap package:

go get -u "github.com/yah01/indexmap"

Import the package:

import "github.com/yah01/indexmap"

Get Started

First, to create a IndexMap with primary index:

type Person struct {
	ID   int64
	Name string
	Age  int
	City string
	Like []string
}

persons := indexmap.NewIndexMap(indexmap.NewPrimaryIndex(func(value *Person) int64 {
    return value.ID
}))

Now it's just like the common map type, but then you can add index to seek person with the other field:

persons.AddIndex("name", indexmap.NewSecondaryIndex(func(value *Person) []any {
    return []any{value.Name}
}))

You have to provide the way to extract keys for the inserted object, all keys must be comparable.

The insertion updates indexes automatically:

ashe := &Person{
    ID:   1,
    Name: "Ashe",
    Age:  39,
    City: "San Francisco",
    Like: []string{"Bob", "Cassidy"},
}
bob := &Person{
    ID:   2,
    Name: "Bob",
    Age:  18,
    City: "San Francisco",
}
cassidy := &Person{
    ID:   3,
    Name: "Cassidy",
    Age:  40,
    City: "Shanghai",
    Like: []string{"Ashe", "Bob"},
}

persons.Insert(ashe)
persons.Insert(bob)
persons.Insert(cassidy)

Adding index after inserting data also works:

persons.AddIndex("city", indexmap.NewSecondaryIndex(func(value *Person) []any {
    return []any{value.City}
}))

// Like is a "contain" index
persons.AddIndex("like", indexmap.NewSecondaryIndex(func(value *Person) []any {
    like := make([]any, 0, len(value.Like))
    for i := range value.Like {
        like = append(like, value.Like[i])
    }
    return like
}))

And seek data with primary index or the added index:

fmt.Println("Search with ID or Name:")
fmt.Printf("%+v\n", persons.Get(ashe.ID))
fmt.Printf("%+v\n", persons.GetBy("name", ashe.Name))

fmt.Println("\nSearch persons come from San Francisco:")
for _, person := range persons.GetAllBy("city", "San Francisco") {
    fmt.Printf("%+v\n", person)
}

fmt.Println("\nSearch persons like Bob")
for _, person := range persons.GetAllBy("like", "Bob") {
    fmt.Printf("%+v\n", person)
}

which outputs:

Search with ID or Name:
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}

Search persons come from San Francisco:
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}
&{ID:2 Name:Bob Age:18 City:San Francisco Like:[]}

Search persons like Bob
&{ID:3 Name:Cassidy Age:40 City:Shanghai Like:[Ashe Bob]}
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}

Document

API Reference

Update Value

Inserting the different values with the same key works like the normal map type, the last one overwrites the others, but for a inserted value, modifing it outside may confuse the index, modify an internal value with Update()/UpdateBy():

// DO NOT:
person := persons.GetBy("name", "Ashe")
person.City = "Shanghai"
persons.Insert(person)

// Modify the internal value with Update()/UpdateBy()
persons.UpdateBy("name", "Ashe", func(value *Person) (*Person, bool) {
    if value.City == "Shanghai" {
        return value, false
    }
    value.City = "Shanghai"
    return value, true
})

Serialize & Deserialize

You can serialize an IndexMap to JSON, the result is the same as serializing a normal map type, doesn't contain the index information, so you can't recover the indexes from that:

// Serialize
imapData, err := json.Marshal(imap)

// Deserialize
// You have to create an IndexMap with primary index,
// it's acceptable to add secondary index after deserializing
imap := NewIndexMap(NewPrimaryIndex(func(value *Person) int64 {
    return value.ID
}))
err := json.Unmarshal(imapData, &imap)

Iterate

Like sync.Map, you can iterate the IndexMap with Range() method:

imap.Range(func(key int64, value *Person) bool {
    fmt.Printf("key=%v, value=%+v\n", key, value)
    return true
})

An useful method to get all keys and values:

keys, values := imap.Collect()

Performance

Let $n$ be the number of elements inserted, $m$ be the number of indexes:

Operation	Complexity
Get	$O(1)$
GetBy	$O(1)$
Insert	$O(m)$
Update	$O(m)$
Remove	$O(m)$
AddIndex	$O(n)$

The more indexes, the slower the write operations.

Documentation

Index

• type IndexMap
  • func NewIndexMap[K comparable, V any](primaryIndex *PrimaryIndex[K, V]) *IndexMap[K, V]
  • func (imap *IndexMap[K, V]) AddIndex(indexName string, index *SecondaryIndex[V]) bool
  • func (imap *IndexMap[K, V]) Clear()
  • func (imap *IndexMap[K, V]) Collect() ([]K, []*V)
  • func (imap *IndexMap[K, V]) Contain(key K) bool
  • func (imap *IndexMap[K, V]) Get(key K) *V
  • func (imap *IndexMap[K, V]) GetAllBy(indexName string, key any) []*V
  • func (imap *IndexMap[K, V]) GetBy(indexName string, key any) *V
  • func (imap *IndexMap[K, V]) Insert(values ...*V)
  • func (imap *IndexMap[K, V]) Len() int
  • func (imap *IndexMap[K, V]) MarshalJSON() ([]byte, error)
  • func (imap *IndexMap[K, V]) Range(fn func(key K, value *V) bool)
  • func (imap *IndexMap[K, V]) Remove(keys ...K)
  • func (imap *IndexMap[K, V]) RemoveBy(indexName string, keys ...any)
  • func (imap *IndexMap[K, V]) UnmarshalJSON(data []byte) error
  • func (imap *IndexMap[K, V]) Update(key K, updateFn UpdateFn[V])
  • func (imap *IndexMap[K, V]) UpdateBy(indexName string, key any, updateFn UpdateFn[V])
• type PrimaryIndex
  • func NewPrimaryIndex[K comparable, V any](extractField func(value *V) K) *PrimaryIndex[K, V]
• type SecondaryIndex
  • func NewSecondaryIndex[V any](extractField func(value *V) []any) *SecondaryIndex[V]
• type UpdateFn

Types

type IndexMap

type IndexMap[K comparable, V any] struct {
	// contains filtered or unexported fields
}

IndexMap is a map supports seeking data with more indexes. Serializing a IndexMap as JSON results in the same as serializing a map, the result doesn't contain the index information, only data. NOTE: DO NOT insert nil value into the IndexMap

func NewIndexMap

func NewIndexMap[K comparable, V any](primaryIndex *PrimaryIndex[K, V]) *IndexMap[K, V]

Create a IndexMap with a primary index, the primary index must be a one-to-one mapping.

func (*IndexMap[K, V]) AddIndex

func (imap *IndexMap[K, V]) AddIndex(indexName string, index *SecondaryIndex[V]) bool

Add a secondary index, build index for the data inserted, the return value indicates whether succeed to add index, false if the indexName existed.

func (*IndexMap[K, V]) Clear

func (imap *IndexMap[K, V]) Clear()

Remove all values.

func (*IndexMap[K, V]) Collect

func (imap *IndexMap[K, V]) Collect() ([]K, []*V)

Return all the keys and values.

func (*IndexMap[K, V]) Contain

func (imap *IndexMap[K, V]) Contain(key K) bool

Return true if the value with given key exists, false otherwise.

func (*IndexMap[K, V]) Get

func (imap *IndexMap[K, V]) Get(key K) *V

Get value by the primary key, nil if key not exists.

func (*IndexMap[K, V]) GetAllBy

func (imap *IndexMap[K, V]) GetAllBy(indexName string, key any) []*V

Return all values the seeked by the key, nil if index or key not exists.

func (*IndexMap[K, V]) GetBy

func (imap *IndexMap[K, V]) GetBy(indexName string, key any) *V

Return one of the values for the given secondary key, No guarantee for which one is returned if more than one elements indexed by the key.

func (*IndexMap[K, V]) Insert

func (imap *IndexMap[K, V]) Insert(values ...*V)

Insert values into the map, also updates the indexes added, overwrite if a value with the same primary key existed. NOTE: insert an modified existed value with the same address may confuse the index, use Update() to do this.

func (*IndexMap[K, V]) Len

func (imap *IndexMap[K, V]) Len() int

The number of elements.

func (*IndexMap[K, V]) MarshalJSON

func (imap *IndexMap[K, V]) MarshalJSON() ([]byte, error)

func (*IndexMap[K, V]) Range

func (imap *IndexMap[K, V]) Range(fn func(key K, value *V) bool)

Iterate all the elements, stop iteration if fn returns false, no any guarantee to the order.

func (*IndexMap[K, V]) Remove

func (imap *IndexMap[K, V]) Remove(keys ...K)

Remove values into the map, also updates the indexes added.

func (*IndexMap[K, V]) RemoveBy

func (imap *IndexMap[K, V]) RemoveBy(indexName string, keys ...any)

Remove values into the map, also updates the indexes added.

func (*IndexMap[K, V]) UnmarshalJSON

func (imap *IndexMap[K, V]) UnmarshalJSON(data []byte) error

func (*IndexMap[K, V]) Update

func (imap *IndexMap[K, V]) Update(key K, updateFn UpdateFn[V])

Update the value for the given key, it removes the old one if exists, and inserts updateFn(old) if modified and not nil.

func (*IndexMap[K, V]) UpdateBy

func (imap *IndexMap[K, V]) UpdateBy(indexName string, key any, updateFn UpdateFn[V])

Update the values for the given index and key, it removes the old ones if exist, and inserts updateFn(old) for every old ones if not nil. NOTE: the modified values have to be with unique primary key

type PrimaryIndex

type PrimaryIndex[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewPrimaryIndex

func NewPrimaryIndex[K comparable, V any](extractField func(value *V) K) *PrimaryIndex[K, V]

Create an primary index, the extractField func must guarantee it makes the index one-to-one.

type SecondaryIndex

type SecondaryIndex[V any] struct {
	// contains filtered or unexported fields
}

func NewSecondaryIndex

func NewSecondaryIndex[V any](extractField func(value *V) []any) *SecondaryIndex[V]

Create a secondary index, the extractField func returns the keys for seeking the value, It's OK that the same key seeks more than one values.

type UpdateFn

type UpdateFn[V any] func(value *V) (*V, bool)

An UpdateFn modifies the given value, and returns the modified value, they could be the same object, true if the object is modified, false otherwise