README
¶
ordered 
Implementation of generic ordered map and set. An ordered map is a special hashmap which maintains the insertion order of the key-vale pair. The ordered set is a wrapper around the ordered map which keeps the unique elements according to their insertion order.
Features:
- Amortized
O(1)time complexity for insertion, remove and get - Supports generics
- JSON marshalling and unmarshalling
- Gob encoding and decoding
Limitations:
- Not safe for concurrent use
- The map key and the set element must be
comparable
Usage
Prerequisites
The go version should be >=1.18
Installation
go get github.com/nhAnik/ordered
Example
Example of ordered map:
package main
import (
"encoding/json"
"fmt"
"github.com/nhAnik/ordered"
)
type point struct{ X, Y int }
func main() {
// Create a new generic ordered map
om := ordered.NewMap[string, point]()
// Put key-value pair in the map
om.Put("p1", point{1, 2})
om.Put("p2", point{2, 4})
om.Put("p3", point{3, 6})
if p2, ok := om.Get("p2"); ok {
// Get value of p2
fmt.Println(p2)
}
// Update value of p1
// This will not affect the insertion order
om.Put("p1", point{0, 0})
// Iterate key-value pairs according to insertion order
// p1 --> {0 0}
// p2 --> {2 4}
// p3 --> {3 6}
for _, kv := range om.KeyValues() {
fmt.Printf("%s --> %v\n", kv.Key, kv.Value)
}
// Remove p1 key and its mapped value
om.Remove("p1")
// Iterate values according to insertion order
for _, v := range om.Values() {
fmt.Println(v)
}
// Checks if the map is empty
if om.IsEmpty() {
fmt.Println("Empty map")
}
// Print string representation of the map
fmt.Println(om) // map{p2:{2 4} p3:{3 6}}
// Marshals the map to json according to order
b, _ := json.Marshal(om)
fmt.Println(string(b)) // {"p2":{"X":2,"Y":4},"p3":{"X":3,"Y":6}}
// Serialize using gob maintaining order
f, _ := os.Create("foo")
defer f.Close()
gob.NewEncoder(f).Encode(om)
}
Example of ordered set:
package main
import (
"encoding/json"
"fmt"
"github.com/nhAnik/ordered"
)
func main() {
// Create a new generic ordered set
s := ordered.NewSet[string]()
// Add new values in the set
s.Add("C++")
s.Add("Java")
s.Add("Go")
// Duplicate will not be added and will not
// affect insertion order.
s.Add("Java")
// Check if an element exists
if ok := s.Contains("Go"); ok {
fmt.Println("Found Go")
}
// Iterate elements according to insertion order
// C++
// Java
// Go
for _, elem := range s.Elements() {
fmt.Println(elem)
}
// Remove element if exists
s.Remove("Java")
// Checks if the set is empty
if s.IsEmpty() {
fmt.Println("Empty set")
}
// Print string representation of the set
fmt.Println(s) // set{C++ Go}
// Marshals the set to json according to order
mp := ordered.NewMap[string, *ordered.Set[string]]()
mp.Put("language", ordered.NewSetWithElems[string]("C++", "Go", "Python"))
mp.Put("editor", ordered.NewSetWithElems[string]("VSCode", "Vim"))
b, _ := json.Marshal(mp)
fmt.Println(string(b)) // {"language":["C++","Go","Python"],"editor":["VSCode","Vim"]}
// Serialize using gob maintaining order
f, _ := os.Create("foo")
defer f.Close()
gob.NewEncoder(f).Encode(s)
}
Documentation
Documentation is available on pkg.go.dev.
License
Documentation
¶
Index ¶
- type KeyValue
- type Map
- func (o *Map[K, V]) Clear()
- func (o *Map[K, V]) ContainsKey(key K) bool
- func (o *Map[K, V]) ForEach(f func(K, V))
- func (o *Map[K, V]) Get(key K) (V, bool)
- func (o *Map[K, V]) GetOrDefault(key K, defaultValue V) V
- func (o *Map[K, V]) GobDecode(b []byte) error
- func (o Map[K, V]) GobEncode() ([]byte, error)
- func (o *Map[K, V]) IsEmpty() bool
- func (o *Map[K, V]) KeyValues() []KeyValue[K, V]
- func (o *Map[K, V]) Keys() []K
- func (o *Map[K, V]) Len() int
- func (o Map[K, V]) MarshalJSON() ([]byte, error)
- func (o *Map[K, V]) Put(key K, value V)
- func (o *Map[K, V]) Remove(key K) V
- func (o *Map[K, V]) String() string
- func (o *Map[K, V]) UnmarshalJSON(b []byte) error
- func (o *Map[K, V]) Values() []V
- type Set
- func (s *Set[T]) Add(elem T)
- func (s *Set[T]) Clear()
- func (s *Set[T]) Contains(elem T) bool
- func (s *Set[T]) Elements() []T
- func (o *Set[T]) ForEach(f func(T))
- func (s *Set[T]) GobDecode(b []byte) error
- func (s Set[T]) GobEncode() ([]byte, error)
- func (s *Set[T]) IsEmpty() bool
- func (s *Set[T]) Len() int
- func (s Set[T]) MarshalJSON() ([]byte, error)
- func (s *Set[T]) Remove(elem T) bool
- func (s *Set[T]) String() string
- func (s *Set[T]) UnmarshalJSON(b []byte) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type KeyValue ¶
type KeyValue[K comparable, V any] struct { Key K Value V }
KeyValue represents a map elements as a key-value pair.
type Map ¶
type Map[K comparable, V any] struct { // contains filtered or unexported fields }
Map represents an ordered map which is an extension of hashmap. Unlike hashmap, the ordered map maintains the insertion order i.e. the order in which the keys and their mapped values are inserted in the map. The insertion order is not changed if a key which already exists in the map is re-inserted.
func NewMapWithCapacity ¶ added in v1.1.0
func NewMapWithCapacity[K comparable, V any](capacity int) *Map[K, V]
NewMapWithCapacity initializes an ordered map with the given initial capacity.
func NewMapWithKVs ¶ added in v1.0.0
func NewMapWithKVs[K comparable, V any](kvs ...KeyValue[K, V]) *Map[K, V]
NewMapWithKVs initializes an ordered map and inserts the given key-value pair in the map.
func (*Map[K, V]) Clear ¶
func (o *Map[K, V]) Clear()
Clear removes all the keys and their mapped values from the map.
func (*Map[K, V]) ContainsKey ¶
ContainsKey checks if the map contains a mapping for the given key.
func (*Map[K, V]) ForEach ¶ added in v1.1.0
func (o *Map[K, V]) ForEach(f func(K, V))
ForEach invokes the given function f for each element of the map.
func (*Map[K, V]) Get ¶
Get returns the mapped value for the given key and a bool indicating whether the key exists or not.
func (*Map[K, V]) GetOrDefault ¶ added in v1.0.0
func (o *Map[K, V]) GetOrDefault(key K, defaultValue V) V
GetOrDefault returns the mapped value for the given key if it exists. Otherwise, it returns the default value.
func (*Map[K, V]) KeyValues ¶
KeyValues returns all the keys and values from the map according to their insertion order. The first element of the slice is the oldest key and value in the map.
func (*Map[K, V]) Keys ¶
func (o *Map[K, V]) Keys() []K
Keys returns all the keys from the map according to their insertion order. The first element of the slice is the oldest key in the map.
func (Map[K, V]) MarshalJSON ¶
MarshalJSON implements json.Marshaler interface.
func (*Map[K, V]) Put ¶
func (o *Map[K, V]) Put(key K, value V)
Put inserts a key and its mapped value in the map. If the key already exists, the mapped value is replaced by the new value.
func (*Map[K, V]) Remove ¶
func (o *Map[K, V]) Remove(key K) V
Remove removes the key with its mapped value from the map and returns the value if the key exists.
func (*Map[K, V]) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler interface.
type Set ¶
type Set[T comparable] struct { // contains filtered or unexported fields }
Set represents an ordered set which is a special hashset keeping the insertion order intact. The insertion order is not changed if a element which already exists in the set is re-inserted.
func NewSetWithCapacity ¶ added in v1.1.0
func NewSetWithCapacity[T comparable](capacity int) *Set[T]
NewSetWithCapacity initializes an ordered set with the given initial capacity..
func NewSetWithElems ¶
func NewSetWithElems[T comparable](elems ...T) *Set[T]
NewSetWithElems initializes an ordered set and adds the elements in the set.
func (*Set[T]) Elements ¶
func (s *Set[T]) Elements() []T
Elements returns all the elements of the set according to their insertion order. The first element of the slice is the oldest element in the set.
func (*Set[T]) ForEach ¶ added in v1.1.0
func (o *Set[T]) ForEach(f func(T))
ForEach invokes the given function f for each element of the set.
func (Set[T]) MarshalJSON ¶
MarshalJSON implements json.Marshaler interface.
func (*Set[T]) Remove ¶
Remove removes the given element from the set if the elements is already there in the set. The returned boolean value indicates whether the element is removed or not.
func (*Set[T]) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler interface.
Source Files