README
¶
Ordered map
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
- iancoleman/orderedmap — has O(n) time for Delete
- wk8/go-ordered-map — Unmarshal creates nested maps as native unordered maps, which makes it useless for my purposes
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 ¶
- func GetAs[T any](m *Map, key Key) (value T, ok bool)
- type Element
- type Key
- type Map
- func (m *Map) Clear()
- func (m *Map) Delete(key Key)
- func (m *Map) First() *Element
- func (m *Map) Get(key Key) (value Value, ok bool)
- func (m *Map) GetElement(key Key) *Element
- func (m *Map) KeyIndex(key Key) int
- func (m *Map) Keys() []Key
- func (m *Map) Last() *Element
- func (m *Map) Len() int
- func (m *Map) MarshalJSON() ([]byte, error)
- func (m *Map) Pop() (key Key, value Value, ok bool)
- func (m *Map) PopFront() (key Key, value Value, ok bool)
- func (m *Map) Push(key Key, value Value)
- func (m *Map) PushFront(key Key, value Value)
- func (m *Map) Set(key Key, value Value)
- func (m *Map) SetFront(key Key, value Value)
- func (m *Map) SortKeys(less func(a, b Key) bool)
- func (m *Map) String() string
- func (m *Map) UnmarshalJSON(data []byte) error
- func (m *Map) Values() []Value
- type Value
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
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) Next ¶ added in v0.2.0
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())
}
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 (*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) First ¶ added in v0.2.0
First returns the first element in the map, for iteration. Returns nil if the map is empty. O(1) time.
func (*Map) Get ¶
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
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
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) Last ¶ added in v0.2.0
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 ¶
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 ¶
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
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
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 ¶
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
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 ¶
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
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
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) UnmarshalJSON ¶
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}`))
Source Files
Directories