introduce multimap (#7)

zyedidia · Apr 13, 2022 · c1f83ec · c1f83ec
1 parent 7bf8496
commit c1f83ec
Show file tree

Hide file tree

Showing 8 changed files with 667 additions and 1 deletion.
diff --git a/Makefile b/Makefile
@@ -1,4 +1,4 @@
-DOCS=avl/README.md btree/README.md cache/README.md hashmap/README.md hashset/README.md interval/README.md list/README.md mapset/README.md rope/README.md stack/README.md trie/README.md DOC.md queue/README.md
+DOCS=avl/README.md btree/README.md cache/README.md hashmap/README.md hashset/README.md interval/README.md list/README.md mapset/README.md multimap/README.md rope/README.md stack/README.md trie/README.md DOC.md queue/README.md
 
 all: $(DOCS)
 

diff --git a/README.md b/README.md
@@ -13,6 +13,7 @@ This package implements some generic data structures.
   the hashmap can be efficiently copied, using copy-on-write under the hood.
 * [`hashset`](./hashset): a hashset that uses the hashmap as the underlying storage.
 * [`mapset`](./mapset): a set that uses Go's built-in map as the underlying storage.
+* [`multimap`](./multimap): an associative container that permits multiple entries with the same key.
 * [`interval`](./interval): an interval tree, implemented as an augmented AVL tree.
 * [`list`](./list): a doubly-linked list.
 * [`rope`](./rope): a generic rope, which is similar to an array but supports efficient

diff --git a/multimap/README.md b/multimap/README.md
@@ -0,0 +1,93 @@
+<!-- Code generated by gomarkdoc. DO NOT EDIT -->
+
+# multimap
+
+```go
+import "github.com/zyedidia/generic/multimap"
+```
+
+Package multimap provides an associative container that permits multiple entries with the same key\.
+
+There are four implementations of the MultiMap data structure\, identified by separate New\* functions\. They differ in the following ways: \- whether key type and value type must be comparable\. \- whether duplicate entries \(same key and same value\) are permitted\. \- whether keys and values are sorted or unsorted in Get\, Each\, and EachAssociation methods\.
+
+## Index
+
+- [type MultiMap](<#type-multimap>)
+  - [func NewAvlSet[K, V any](keyLess g.LessFn[K], valueLess g.LessFn[V]) MultiMap[K, V]](<#func-newavlset>)
+  - [func NewAvlSlice[K any, V comparable](keyLess g.LessFn[K]) MultiMap[K, V]](<#func-newavlslice>)
+  - [func NewMapSet[K comparable, V any](valueLess g.LessFn[V]) MultiMap[K, V]](<#func-newmapset>)
+  - [func NewMapSlice[K, V comparable]() MultiMap[K, V]](<#func-newmapslice>)
+
+
+## type MultiMap
+
+MultiMap is an associative container that contains a list of key\-value pairs\, while permitting multiple entries with the same key\.
+
+```go
+type MultiMap[K, V any] interface {
+    // Dimension returns number of distinct keys.
+    Dimension() int
+    // Size returns total number of entries.
+    Size() int
+
+    // Count returns number of entries with a given key.
+    Count(key K) int
+    // Has determines whether at least one entry exists with a given key.
+    Has(key K) bool
+    // Get returns a list of values with a given key.
+    Get(key K) []V
+
+    // Put adds an entry.
+    // Whether duplicate entries are allowed depends on the chosen implementation.
+    Put(key K, value V)
+    // Remove removes an entry.
+    // If duplicate entries are allowed, this removes only one entry.
+    // This is a no-op if the entry does not exist.
+    Remove(key K, value V)
+    // RemoveAll removes every entry with a given key.
+    RemoveAll(key K)
+    // Clear deletes all entries.
+    Clear()
+
+    // Each calls 'fn' on every entry.
+    Each(fn func(key K, value V))
+    // EachAssociation calls 'fn' on every key and list of values.
+    EachAssociation(fn func(key K, values []V))
+}
+```
+
+### func NewAvlSet
+
+```go
+func NewAvlSet[K, V any](keyLess g.LessFn[K], valueLess g.LessFn[V]) MultiMap[K, V]
+```
+
+NewAvlSet creates a MultiMap using AVL tree and AVL set\. \- Duplicate entries are not permitted\. \- Both keys and values are sorted\.
+
+### func NewAvlSlice
+
+```go
+func NewAvlSlice[K any, V comparable](keyLess g.LessFn[K]) MultiMap[K, V]
+```
+
+NewAvlSlice creates a MultiMap using AVL tree and builtin slice\. \- Value type must be comparable\. \- Duplicate entries are permitted\. \- Keys are sorted\, but values are unsorted\.
+
+### func NewMapSet
+
+```go
+func NewMapSet[K comparable, V any](valueLess g.LessFn[V]) MultiMap[K, V]
+```
+
+NewMapSet creates a MultiMap using builtin map and AVL set\. \- Key type must be comparable\. \- Duplicate entries are not permitted\. \- Values are sorted\, but keys are unsorted\.
+
+### func NewMapSlice
+
+```go
+func NewMapSlice[K, V comparable]() MultiMap[K, V]
+```
+
+NewMapSlice creates a MultiMap using builtin map and builtin slice\. \- Both key type and value type must be comparable\. \- Duplicate entries are permitted\. \- Both keys and values are unsorted\.
+
+
+
+Generated by [gomarkdoc](<https://github.com/princjef/gomarkdoc>)
diff --git a/multimap/avl.go b/multimap/avl.go
@@ -0,0 +1,120 @@
+package multimap
+
+import (
+	g "github.com/zyedidia/generic"
+	"github.com/zyedidia/generic/avl"
+)
+
+type avlMultiMap[K, V any, C valuesContainer[V]] struct {
+	baseMultiMap
+	keyLess    g.LessFn[K]
+	keys       *avl.Tree[K, C]
+	makeValues func() C
+}
+
+func (m *avlMultiMap[K, V, C]) Dimension() int {
+	return m.keys.Size()
+}
+
+func (m *avlMultiMap[K, V, C]) Count(key K) int {
+	values, ok := m.keys.Get(key)
+	if !ok {
+		return 0
+	}
+	return values.Size()
+}
+
+func (m *avlMultiMap[K, V, C]) Has(key K) bool {
+	_, ok := m.keys.Get(key)
+	return ok
+}
+
+func (m *avlMultiMap[K, V, C]) Get(key K) []V {
+	values, ok := m.keys.Get(key)
+	if !ok {
+		return nil
+	}
+	return values.List()
+}
+
+func (m *avlMultiMap[K, V, C]) Put(key K, value V) {
+	values, ok := m.keys.Get(key)
+	if !ok {
+		values = m.makeValues()
+		m.keys.Put(key, values)
+	}
+
+	m.size += values.Put(value)
+}
+
+func (m *avlMultiMap[K, V, C]) Remove(key K, value V) {
+	values, ok := m.keys.Get(key)
+	if !ok {
+		return
+	}
+
+	m.size -= values.Remove(value)
+	if values.Empty() {
+		m.keys.Remove(key)
+	}
+}
+
+func (m *avlMultiMap[K, V, C]) RemoveAll(key K) {
+	values, ok := m.keys.Get(key)
+	if !ok {
+		return
+	}
+
+	m.size -= values.Size()
+	m.keys.Remove(key)
+}
+
+func (m *avlMultiMap[K, V, C]) Clear() {
+	m.size = 0
+	m.keys = avl.New[K, C](m.keyLess)
+}
+
+func (m *avlMultiMap[K, V, C]) Each(fn func(key K, value V)) {
+	m.keys.Each(func(key K, values C) {
+		values.Each(func(value V) {
+			fn(key, value)
+		})
+	})
+}
+
+func (m *avlMultiMap[K, V, C]) EachAssociation(fn func(key K, values []V)) {
+	m.keys.Each(func(key K, values C) {
+		fn(key, values.List())
+	})
+}
+
+// NewAvlSlice creates a MultiMap using AVL tree and builtin slice.
+//  - Value type must be comparable.
+//  - Duplicate entries are permitted.
+//  - Keys are sorted, but values are unsorted.
+func NewAvlSlice[K any, V comparable](keyLess g.LessFn[K]) MultiMap[K, V] {
+	m := &avlMultiMap[K, V, *valuesSlice[V]]{
+		keyLess: keyLess,
+		makeValues: func() *valuesSlice[V] {
+			return &valuesSlice[V]{}
+		},
+	}
+	m.Clear()
+	return m
+}
+
+// NewAvlSet creates a MultiMap using AVL tree and AVL set.
+//  - Duplicate entries are not permitted.
+//  - Both keys and values are sorted.
+func NewAvlSet[K, V any](keyLess g.LessFn[K], valueLess g.LessFn[V]) MultiMap[K, V] {
+	m := &avlMultiMap[K, V, valuesSet[V]]{
+		keyLess: keyLess,
+		makeValues: func() valuesSet[V] {
+			return valuesSet[V]{
+				t: avl.New[V, struct{}](valueLess),
+			}
+		},
+	}
+	m.Clear()
+	return m
+}
diff --git a/multimap/map.go b/multimap/map.go
@@ -0,0 +1,118 @@
+package multimap
+
+import (
+	g "github.com/zyedidia/generic"
+	"github.com/zyedidia/generic/avl"
+)
+
+type mapMultiMap[K comparable, V any, C valuesContainer[V]] struct {
+	baseMultiMap
+	keys       map[K]C
+	makeValues func() C
+}
+
+func (m *mapMultiMap[K, V, C]) Dimension() int {
+	return len(m.keys)
+}
+
+func (m *mapMultiMap[K, V, C]) Count(key K) int {
+	values, ok := m.keys[key]
+	if !ok {
+		return 0
+	}
+	return values.Size()
+}
+
+func (m *mapMultiMap[K, V, C]) Has(key K) bool {
+	_, ok := m.keys[key]
+	return ok
+}
+
+func (m *mapMultiMap[K, V, C]) Get(key K) []V {
+	values, ok := m.keys[key]
+	if !ok {
+		return nil
+	}
+	return values.List()
+}
+
+func (m *mapMultiMap[K, V, C]) Put(key K, value V) {
+	values, ok := m.keys[key]
+	if !ok {
+		values = m.makeValues()
+		m.keys[key] = values
+	}
+
+	m.size += values.Put(value)
+}
+
+func (m *mapMultiMap[K, V, C]) Remove(key K, value V) {
+	values, ok := m.keys[key]
+	if !ok {
+		return
+	}
+
+	m.size -= values.Remove(value)
+	if values.Empty() {
+		delete(m.keys, key)
+	}
+}
+
+func (m *mapMultiMap[K, V, C]) RemoveAll(key K) {
+	values, ok := m.keys[key]
+	if !ok {
+		return
+	}
+
+	m.size -= values.Size()
+	delete(m.keys, key)
+}
+
+func (m *mapMultiMap[K, V, C]) Clear() {
+	m.size = 0
+	m.keys = map[K]C{}
+}
+
+func (m *mapMultiMap[K, V, C]) Each(fn func(key K, value V)) {
+	for key, values := range m.keys {
+		values.Each(func(value V) {
+			fn(key, value)
+		})
+	}
+}
+
+func (m *mapMultiMap[K, V, C]) EachAssociation(fn func(key K, values []V)) {
+	for key, values := range m.keys {
+		fn(key, values.List())
+	}
+}
+
+// NewMapSlice creates a MultiMap using builtin map and builtin slice.
+//  - Both key type and value type must be comparable.
+//  - Duplicate entries are permitted.
+//  - Both keys and values are unsorted.
+func NewMapSlice[K, V comparable]() MultiMap[K, V] {
+	m := &mapMultiMap[K, V, *valuesSlice[V]]{
+		makeValues: func() *valuesSlice[V] {
+			return &valuesSlice[V]{}
+		},
+	}
+	m.Clear()
+	return m
+}
+
+// NewMapSet creates a MultiMap using builtin map and AVL set.
+//  - Key type must be comparable.
+//  - Duplicate entries are not permitted.
+//  - Values are sorted, but keys are unsorted.
+func NewMapSet[K comparable, V any](valueLess g.LessFn[V]) MultiMap[K, V] {
+	m := &mapMultiMap[K, V, valuesSet[V]]{
+		makeValues: func() valuesSet[V] {
+			return valuesSet[V]{
+				t: avl.New[V, struct{}](valueLess),
+			}
+		},
+	}
+	m.Clear()
+	return m
+}
diff --git a/multimap/multimap.go b/multimap/multimap.go
@@ -0,0 +1,48 @@
+// Package multimap provides an associative container that permits multiple entries with the same key.
+//
+// There are four implementations of the MultiMap data structure, identified by separate New* functions.
+// They differ in the following ways:
+//  - whether key type and value type must be comparable.
+//  - whether duplicate entries (same key and same value) are permitted.
+//  - whether keys and values are sorted or unsorted in Get, Each, and EachAssociation methods.
+package multimap
+
+// MultiMap is an associative container that contains a list of key-value pairs, while permitting multiple entries with the same key.
+type MultiMap[K, V any] interface {
+	// Dimension returns number of distinct keys.
+	Dimension() int
+	// Size returns total number of entries.
+	Size() int
+
+	// Count returns number of entries with a given key.
+	Count(key K) int
+	// Has determines whether at least one entry exists with a given key.
+	Has(key K) bool
+	// Get returns a list of values with a given key.
+	Get(key K) []V
+
+	// Put adds an entry.
+	// Whether duplicate entries are allowed depends on the chosen implementation.
+	Put(key K, value V)
+	// Remove removes an entry.
+	// If duplicate entries are allowed, this removes only one entry.
+	// This is a no-op if the entry does not exist.
+	Remove(key K, value V)
+	// RemoveAll removes every entry with a given key.
+	RemoveAll(key K)
+	// Clear deletes all entries.
+	Clear()
+
+	// Each calls 'fn' on every entry.
+	Each(fn func(key K, value V))
+	// EachAssociation calls 'fn' on every key and list of values.
+	EachAssociation(fn func(key K, values []V))
+}
+
+type baseMultiMap struct {
+	size int
+}
+
+func (m baseMultiMap) Size() int {
+	return m.size
+}