jsonmap

package module
v0.5.0 Latest Latest
Warning

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

Go to latest
Published: Jun 20, 2024 License: MIT Imports: 6 Imported by: 1

README

Ordered map

go test workflow go report codecov go doc MIT license

Simple ordered map for Go, with JSON restrictions. The main purpose is to keep same order of keys after parsing JSON and generating it again, so Unmarshal followed by Marshal generates exactly the same JSON structure

Keys are strings, Values are any JSON values (number, string, boolean, null, array, map/object)

Storage is O(n), operations are O(1), except for optional operations in slow.go file

When Unmarshalling, any nested map from JSON is created as ordered jsonmap, including maps in nested arrays

Inspired by wk8/go-ordered-map and iancoleman/orderedmap

Performance

Similar to Go native map, jsonmap has O(1) time for Get, Set, Delete. Additionally it has Push, First, Last, Next, Prev operations, which are also O(1)

➜ go test -bench . -benchmem
...

Benchmark/Ops/Get/gomap-10             10916256               110.7 ns/op             0 B/op          0 allocs/op
Benchmark/Ops/Get/jsonmap-10           10133562               118.1 ns/op             0 B/op          0 allocs/op

Benchmark/Ops/SetExisting/gomap-10      7771100               144.1 ns/op             7 B/op          0 allocs/op
Benchmark/Ops/SetExisting/jsonmap-10    3813949               278.3 ns/op            25 B/op          1 allocs/op

Benchmark/Ops/SetNew/gomap-10           6028083               168.5 ns/op            15 B/op          1 allocs/op
Benchmark/Ops/SetNew/jsonmap-10         3636994               292.2 ns/op            55 B/op          1 allocs/op

Benchmark/Ops/Delete/gomap-10           9750571               114.8 ns/op             0 B/op          0 allocs/op
Benchmark/Ops/Delete/jsonmap-10         5974435               192.0 ns/op             0 B/op          0 allocs/op

Suite benchmark does 10k of Set and Get, and 1k of Delete operations. jsonmap performance is on par with native Go map

Benchmark/Suite/gomap-10                      38          30634451 ns/op        23947561 B/op     521837 allocs/op
Benchmark/Suite/jsonmap-10                    33          33939048 ns/op        24056151 B/op     621895 allocs/op

Installation

$ go get github.com/metalim/jsonmap

Usage

package main

import (
	"encoding/json"
	"fmt"

	"github.com/metalim/jsonmap"
)

const sampleJSON = `{"an":"article","empty":null,"sub":{"s":1,"e":2,"x":3,"y":4},"bool":false,"array":[1,2,3]}`

func main() {
	m := jsonmap.New()

	// unmarshal, keeping order
	err := json.Unmarshal([]byte(sampleJSON), &m)
	if err != nil {
		panic(err)
	}

	// get values
	val, ok := m.Get("an")
	fmt.Println("an: ", val, ok) // article true
	val, ok = m.Get("non-existant")
	fmt.Println("non-existant", val, ok) // <nil> false

	// marshal, keeping order
	output, err := json.Marshal(&m)
	if err != nil {
		panic(err)
	}

	if string(output) == sampleJSON {
		fmt.Println("output == sampleJSON")
	}

	// iterate
	fmt.Println("forward order:")
	for el := m.First(); el != nil; el = el.Next() {
		fmt.Printf("\t%s: %v\n", el.Key(), el.Value())
	}
	fmt.Println()

	fmt.Println("backwards order:")
	for el := m.Last(); el != nil; el = el.Prev() {
		fmt.Printf("\t%s: %v\n", el.Key(), el.Value())
	}
	fmt.Println()

	fmt.Println(`forward from key "sub":`)
	for el := m.GetElement("sub"); el != nil; el = el.Next() {
		fmt.Printf("\t%s: %v\n", el.Key(), el.Value())
	}
	fmt.Println()

	// print map
	fmt.Println(m) // map[an:article empty:<nil> sub:map[s:1 e:2 x:3 y:4] bool:false array:[1 2 3]]

	// set new values, keeping order of existing keys
	m.Set("an", "bar")
	m.Set("truth", true)
	fmt.Println(m) // map[an:bar empty:<nil> sub:map[s:1 e:2 x:3 y:4] bool:false array:[1 2 3] truth:true]

	// delete key "sub"
	m.Delete("sub")
	fmt.Println(m) // map[an:bar empty:<nil> bool:false array:[1 2 3] truth:true]

	// update value for key "an", and move it to the end
	m.Push("an", "end")
	fmt.Println(m) // map[empty:<nil> bool:false array:[1 2 3] truth:true an:end]

	data, err := json.Marshal(&m)
	if err != nil {
		panic(err)
	}
	fmt.Println(string(data)) // {"empty":null,"bool":false,"array":[1,2,3],"truth":true,"an":"end"}
}

Alternatives

Let me know of other alternatives, I'll add them here

Documentation

Overview

jsonmap is an ordered map. Same as native Go map, but keeps order of insertion when iterating or serializing to JSON, and with additional methods to iterate from any point. Similar to native map, user has to take care of concurrency and nil map value.

Create new map:

m := jsonmap.New()

Set values (remembering order of insertion):

m.Set("someString", "value1")
m.Set("someNumber", 42.1)
m.Set("someArray", []string{"a", "b", "c"})

Get value:

value, ok := m.Get("someString")
str, ok := value.(string) // value can be any type
fmt.Println(str, ok)

Get value as specific type:

str, ok := jsonmap.GetAs[string](m, "someString")
fmt.Println(str, ok) // str is string

Iterate forwards:

for elem := m.First(); elem != nil; elem = elem.Next() {
    fmt.Println(elem.Key(), elem.Value())
}

Iterate backwards:

for elem := m.Last(); elem != nil; elem = elem.Prev() {
    fmt.Println(elem.Key(), elem.Value())
}

Iterate from any point:

for elem := m.GetElement("someNumber"); elem != nil; elem = elem.Next() {
    fmt.Println(elem.Key(), elem.Value())
}

Delete element:

m.Delete("someNumber")

Push element to the end:

m.Push("someNumber", 42.1)

Pop element from the end:

key, value, ok := m.Pop()

Clear map:

m.Clear()

Serialize to JSON:

data, err := json.Marshal(m)

Deserialize from JSON:

err = json.Unmarshal(data, &m)

or use jsonmap.Map as a field in a struct:

type MyStruct struct {
    SomeMap *jsonmap.Map `json:"someMap"`
}

And serialize/deserialize the struct:

data, err := json.Marshal(myStruct)
err = json.Unmarshal(data, &myStruct)

Time complexity of operations:

| Operation | Time        |
|-----------|-------------|
| Clear     | O(1)        |
| Get       | O(1)        |
| Set       | O(1)        |
| Delete    | O(1)        |
| Push      | O(1)        |
| Pop       | O(1)        |
|           |             |
| First     | O(1)        |
| Last      | O(1)        |
| GetElement| O(1)        |
| el.Next   | O(1)        |
| el.Prev   | O(1)        |
|           |             |
| SetFront  | O(1)        |
| PushFront | O(1)        |
| PopFront  | O(1)        |
|           |             |
| KeyIndex  | O(N)        |
| Keys      | O(N)        |
| Values    | O(N)        |
| SortKeys  | O(N*log(N)) |

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func GetAs added in v0.3.0

func GetAs[T any](m *Map, key Key) (value T, ok bool)

Helper function to get the value as a specific type. Returns ok=false if the key is not in the map or the value is not of the requested type.

str, ok := jsonmap.GetAs[string](m, key)

Types

type Element added in v0.2.0

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

Element of a map, to be used in iteration.

for elem := m.First(); elem != nil; elem = elem.Next() {
    fmt.Println(elem.Key(), elem.Value())
}

func (*Element) Key added in v0.2.0

func (e *Element) Key() Key

Key returns the key of the element.

key := elem.Key()

func (*Element) Next added in v0.2.0

func (e *Element) Next() *Element

Next returns the next element in the map, for iteration. Returns nil if this is the last element. O(1) time.

for elem := m.First(); elem != nil; elem = elem.Next() {
    fmt.Println(elem.Key(), elem.Value())
}

func (*Element) Prev added in v0.2.0

func (e *Element) Prev() *Element

Prev returns the previous element in the map, for backwards iteration. Returns nil if this is the first element. O(1) time.

for elem := m.Last(); elem != nil; elem = elem.Prev() {
    fmt.Println(elem.Key(), elem.Value())
}

func (*Element) Value added in v0.2.0

func (e *Element) Value() Value

Value returns the value of the element.

value := elem.Value()

type Key

type Key = string

type Map

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

Map is a map with saved order of elements. It is useful for marshaling/unmarshaling JSON objects.

Same as native map, but it keeps order of insertion when iterating or serializing to JSON, and has additional methods to iterate from any element. Similar to native map, user has to take care of concurrent access and nil map value.

func New

func New() *Map

New returns a new map. O(1) time.

m := jsonmap.New()

func (*Map) Clear added in v0.2.0

func (m *Map) Clear()

Clear removes all elements from the map. O(1) time.

m.Clear()

func (*Map) Delete

func (m *Map) Delete(key Key)

Delete removes the element from the map. O(1) time.

m.Delete(key)

func (*Map) First added in v0.2.0

func (m *Map) First() *Element

First returns the first element in the map, for iteration. Returns nil if the map is empty. O(1) time.

func (*Map) Get

func (m *Map) Get(key Key) (value Value, ok bool)

Get returns the value for the key, similar to m[key] for native map. Returns ok=false if the key is not in the map. O(1) time.

value, ok := m.Get(key)

func (*Map) GetElement added in v0.2.0

func (m *Map) GetElement(key Key) *Element

GetElement returns the element for the key, for iteration from a needle. Returns nil if the key is not in the map. O(1) time.

func (*Map) KeyIndex added in v0.2.0

func (m *Map) KeyIndex(key Key) int

KeyIndex returns index of key. O(n) time. If key is not in the map, it returns -1. O(n) time if the key exists. O(1) time if the key does not exist.

i := m.KeyIndex(key)

func (*Map) Keys

func (m *Map) Keys() []Key

Keys returns all keys in the map. O(n) time and space.

keys := m.Keys()

func (*Map) Last added in v0.2.0

func (m *Map) Last() *Element

Last returns the last element in the map, for iteration for backwards iteration. Returns nil if the map is empty. O(1) time.

func (*Map) Len

func (m *Map) Len() int

Len returns the number of elements in the map, similar to len(m) for native map. O(1) time.

l := m.Len()

func (*Map) MarshalJSON

func (m *Map) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler interface. It marshals the map into JSON object.

data, err := json.Marshal(m)

func (*Map) Pop added in v0.4.0

func (m *Map) Pop() (key Key, value Value, ok bool)

Pop removes the last element from the map and returns it. Returns ok=false if the map is empty. O(1) time.

key, value, ok := m.Pop()

func (*Map) PopFront added in v0.4.0

func (m *Map) PopFront() (key Key, value Value, ok bool)

PopFront removes the first element from the map and returns its key and value. Returns ok=false if the map is empty. O(1) time.

key, value, ok := m.PopFront()

func (*Map) Push

func (m *Map) Push(key Key, value Value)

Push is same as Set, but moves the element to the end of the map, as if it was just added. O(1) time.

m.Push(key, value)

func (*Map) PushFront added in v0.2.0

func (m *Map) PushFront(key Key, value Value)

PushFront is same as SetFront, but moves the element to the front of the map, as if it was just added. O(1) time.

m.PushFront(key, value)

func (*Map) Set

func (m *Map) Set(key Key, value Value)

Set sets the value for the key. If key is already in the map, it replaces the value, but keeps the original order of the element. O(1) time.

m.Set(key, value)

func (*Map) SetFront added in v0.2.0

func (m *Map) SetFront(key Key, value Value)

SetFront sets the value for the key. If key is already in the map, it replaces the value, but keeps the original order of the element. If key is not in the map, it adds the element to the front of the map. O(1) time.

func (*Map) SortKeys added in v0.2.0

func (m *Map) SortKeys(less func(a, b Key) bool)

SortKeys sorts keys in the map. O(n*log(n)) time, O(n) space. O(n*log(n)) time, O(n) space.

m.SortKeys(func(a, b Key) bool {
	return a < b
})

func (*Map) String added in v0.2.0

func (m *Map) String() string

String returns a string representation of the map. O(n) time.

func (*Map) UnmarshalJSON

func (m *Map) UnmarshalJSON(data []byte) error

UnmarshalJSON implements json.Unmarshaler interface. It supports nested maps and arrays.

Note: it does not clear the map before unmarshaling. If you want to clear it, call Clear() before UnmarshalJSON().

err := m.UnmarshalJSON([]byte(`{"a":1,"b":2}`))

func (*Map) Values added in v0.2.0

func (m *Map) Values() []Value

Values returns all values in the map. O(n) time and space.

values := m.Values()

type Value

type Value = any

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL