odmap

README

Order map - Keep everything in order

We ensure that the API and semantics are compatible with sync.Map. If you have any questions, please raise them in the issue

Installation

go get github.com/RealFax/order-map@latest

Quickstart

package main

import odmap "github.com/RealFax/order-map"

func main() {
	m := odmap.New[int, string]()
	m.Store(0, "Hello")
	m.Store(1, "World")
	m.Store(2, "😄😄😄")

	m.Range(func(key int, value string) bool {
		print(value, " ")
		return true
	})
}

Roadmap

Welcome to propose more features in the issue

• Concurrency safety (add --tags=safety_map enabled)

⚠️Note. Features such as: Len (safety_map unsupported), Contains are not stable and may be removed or have semantic changes in the future.

Documentation

Index

• Constants
• type Color
• type ConstBidIterator
• type ConstIterator
• type Entry
  • func (n *Entry[K, V]) Key() K
  • func (n *Entry[K, V]) Next() *Entry[K, V]
  • func (n *Entry[K, V]) Prev() *Entry[K, V]
  • func (n *Entry[K, V]) Value() V
• type KVisitor
• type Map
  • func New[K cmp.Ordered, V any](opts ...Option[K, V]) Map[K, V]
• type Option
  • func WithComparer[K cmp.Ordered, V any](comparer func(K, K) int) Option[K, V]
• type RBTree
  • func NewRBTree[K cmp.Ordered, V any](comparer func(K, K) int) *RBTree[K, V]
  • func (t *RBTree[K, V]) Begin() *Entry[K, V]
  • func (t *RBTree[K, V]) Clear()
  • func (t *RBTree[K, V]) Delete(node *Entry[K, V])
  • func (t *RBTree[K, V]) Empty() bool
  • func (t *RBTree[K, V]) FindLowerBoundNode(key K) *Entry[K, V]
  • func (t *RBTree[K, V]) FindNode(key K) *Entry[K, V]
  • func (t *RBTree[K, V]) FindUpperBoundNode(key K) *Entry[K, V]
  • func (t *RBTree[K, V]) First() *Entry[K, V]
  • func (t *RBTree[K, V]) Insert(key K, value V)
  • func (t *RBTree[K, V]) IterFirst() *RBTreeIterator[K, V]
  • func (t *RBTree[K, V]) IterLast() *RBTreeIterator[K, V]
  • func (t *RBTree[K, V]) Last() *Entry[K, V]
  • func (t *RBTree[K, V]) RBegin() *Entry[K, V]
  • func (t *RBTree[K, V]) Size() int
  • func (t *RBTree[K, V]) Traversal(visitor KVisitor[K, V])
• type RBTreeIterator
  • func NewIterator[K cmp.Ordered, V any](node *Entry[K, V]) *RBTreeIterator[K, V]
  • func (iter *RBTreeIterator[K, V]) Clone() ConstIterator[V]
  • func (iter *RBTreeIterator[K, V]) Equal(other ConstIterator[V]) bool
  • func (iter *RBTreeIterator[K, V]) IsValid() bool
  • func (iter *RBTreeIterator[K, V]) Key() K
  • func (iter *RBTreeIterator[K, V]) Next() ConstIterator[V]
  • func (iter *RBTreeIterator[K, V]) Prev() ConstBidIterator[V]
  • func (iter *RBTreeIterator[K, V]) SetValue(val V) error
  • func (iter *RBTreeIterator[K, V]) Value() V

Examples

• New

Constants

const (
	RED   = false
	BLACK = true
)

Define node 's colors

Types

type Color

type Color bool

Color defines node color type

type ConstBidIterator

type ConstBidIterator[T any] interface {
	ConstIterator[T]
	Prev() ConstBidIterator[T]
}

ConstBidIterator is an interface of const bidirectional iterator

type ConstIterator

type ConstIterator[T any] interface {
	IsValid() bool
	Next() ConstIterator[T]
	Value() T
	Clone() ConstIterator[T]
	Equal(other ConstIterator[T]) bool
}

ConstIterator is an interface of const iterator

type Entry

type Entry[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Entry is a tree entry

func (*Entry[K, V]) Key

func (n *Entry[K, V]) Key() K

Key returns node's key

func (*Entry[K, V]) Next

func (n *Entry[K, V]) Next() *Entry[K, V]

Next returns the Entry's successor as an iterator.

func (*Entry[K, V]) Prev

func (n *Entry[K, V]) Prev() *Entry[K, V]

Prev returns the Entry's predecessor as an iterator.

func (*Entry[K, V]) Value

func (n *Entry[K, V]) Value() V

Value returns node's value

type KVisitor

type KVisitor[K cmp.Ordered, V any] func(key K, value V) bool

type Map

type Map[K cmp.Ordered, V any] interface {
	// contains filtered or unexported methods
}

func New

func New[K cmp.Ordered, V any](opts ...Option[K, V]) Map[K, V]

Example

package main

import (
	odmap "github.com/RealFax/order-map"
)

func main() {
	m := odmap.New[int, string]()
	m.Store(0, "Hello")
	m.Store(1, "World")
	m.Store(2, "😄😄😄")

	m.Range(func(key int, value string) bool {
		print(value, " ")
		return true
	})
}

type Option

type Option[K cmp.Ordered, V any] func(m *omap[K, V])

func WithComparer

func WithComparer[K cmp.Ordered, V any](comparer func(K, K) int) Option[K, V]

type RBTree

type RBTree[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

RBTree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

func NewRBTree

func NewRBTree[K cmp.Ordered, V any](comparer func(K, K) int) *RBTree[K, V]

NewRBTree creates a new RBTree

func (*RBTree[K, V]) Begin

func (t *RBTree[K, V]) Begin() *Entry[K, V]

Begin returns the node with minimum key in the RBTree

func (*RBTree[K, V]) Clear

func (t *RBTree[K, V]) Clear()

Clear clears the RBTree

func (*RBTree[K, V]) Delete

func (t *RBTree[K, V]) Delete(node *Entry[K, V])

Delete deletes node from the RBTree

func (*RBTree[K, V]) Empty

func (t *RBTree[K, V]) Empty() bool

Empty returns true if Tree is empty,otherwise returns false.

func (*RBTree[K, V]) FindLowerBoundNode

func (t *RBTree[K, V]) FindLowerBoundNode(key K) *Entry[K, V]

FindLowerBoundNode finds the first node that its key is equal or greater than the passed key, and returns it

func (*RBTree[K, V]) FindNode

func (t *RBTree[K, V]) FindNode(key K) *Entry[K, V]

FindNode the first node that the key is equal to the passed key and return it

func (*RBTree[K, V]) FindUpperBoundNode

func (t *RBTree[K, V]) FindUpperBoundNode(key K) *Entry[K, V]

FindUpperBoundNode finds the first node that its key is greater than the passed key, and returns it

func (*RBTree[K, V]) First

func (t *RBTree[K, V]) First() *Entry[K, V]

First returns the node with minimum key in the RBTree

func (*RBTree[K, V]) Insert

func (t *RBTree[K, V]) Insert(key K, value V)

Insert inserts a key-value pair into the RBTree.

func (*RBTree[K, V]) IterFirst

func (t *RBTree[K, V]) IterFirst() *RBTreeIterator[K, V]

IterFirst returns the iterator of first node

func (*RBTree[K, V]) IterLast

func (t *RBTree[K, V]) IterLast() *RBTreeIterator[K, V]

IterLast returns the iterator of first node

func (*RBTree[K, V]) Last

func (t *RBTree[K, V]) Last() *Entry[K, V]

Last returns the Entry with maximum key in the RBTree

func (*RBTree[K, V]) RBegin

func (t *RBTree[K, V]) RBegin() *Entry[K, V]

RBegin returns the Entry with maximum key in the RBTree

func (*RBTree[K, V]) Size

func (t *RBTree[K, V]) Size() int

Size returns the size of the rbtree.

func (*RBTree[K, V]) Traversal

func (t *RBTree[K, V]) Traversal(visitor KVisitor[K, V])

Traversal traversals elements in the RBTree, it will not stop until to the end of RBTree or the visitor returns false

type RBTreeIterator

type RBTreeIterator[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

RBTreeIterator is an iterator implementation of RBTree

func NewIterator

func NewIterator[K cmp.Ordered, V any](node *Entry[K, V]) *RBTreeIterator[K, V]

NewIterator creates a RBTreeIterator from the passed node

func (*RBTreeIterator[K, V]) Clone

func (iter *RBTreeIterator[K, V]) Clone() ConstIterator[V]

Clone clones the iterator into a new RBTreeIterator

func (*RBTreeIterator[K, V]) Equal

func (iter *RBTreeIterator[K, V]) Equal(other ConstIterator[V]) bool

Equal returns true if the iterator is equal to the passed iterator

func (*RBTreeIterator[K, V]) IsValid

func (iter *RBTreeIterator[K, V]) IsValid() bool

IsValid returns true if the iterator is valid, otherwise returns false

func (*RBTreeIterator[K, V]) Key

func (iter *RBTreeIterator[K, V]) Key() K

Key returns the node's key of the iterator point to

func (*RBTreeIterator[K, V]) Next

func (iter *RBTreeIterator[K, V]) Next() ConstIterator[V]

Next moves the pointer of the iterator to the next node, and returns itself

func (*RBTreeIterator[K, V]) Prev

func (iter *RBTreeIterator[K, V]) Prev() ConstBidIterator[V]

Prev moves the pointer of the iterator to the previous node, and returns itself

func (*RBTreeIterator[K, V]) SetValue

func (iter *RBTreeIterator[K, V]) SetValue(val V) error

SetValue sets the node's value of the iterator point to

func (*RBTreeIterator[K, V]) Value

func (iter *RBTreeIterator[K, V]) Value() V

Value returns the node's value of the iterator point to