1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
// Copyright (c) 2015, Emir Pasic. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package treebidimap implements a bidirectional map backed by two red-black tree.
//
// This structure guarantees that the map will be in both ascending key and value order.
//
// Other than key and value ordering, the goal with this structure is to avoid duplication of elements, which can be significant if contained elements are large.
//
// A bidirectional map, or hash bag, is an associative data structure in which the (key,value) pairs form a one-to-one correspondence.
// Thus the binary relation is functional in each direction: value can also act as a key to key.
// A pair (a,b) thus provides a unique coupling between 'a' and 'b' so that 'b' can be found when 'a' is used as a key and 'a' can be found when 'b' is used as a key.
//
// Structure is not thread safe.
//
// Reference: https://en.wikipedia.org/wiki/Bidirectional_map
package treebidimap
import (
"fmt"
"github.com/emirpasic/gods/maps"
"github.com/emirpasic/gods/trees/redblacktree"
"github.com/emirpasic/gods/utils"
"strings"
)
func assertMapImplementation() {
var _ maps.BidiMap = (*Map)(nil)
}
// Map holds the elements in two red-black trees.
type Map struct {
forwardMap redblacktree.Tree
inverseMap redblacktree.Tree
keyComparator utils.Comparator
valueComparator utils.Comparator
}
type data struct {
key interface{}
value interface{}
}
// NewWith instantiates a bidirectional map.
func NewWith(keyComparator utils.Comparator, valueComparator utils.Comparator) *Map {
return &Map{
forwardMap: *redblacktree.NewWith(keyComparator),
inverseMap: *redblacktree.NewWith(valueComparator),
keyComparator: keyComparator,
valueComparator: valueComparator,
}
}
// NewWithIntComparators instantiates a bidirectional map with the IntComparator for key and value, i.e. keys and values are of type int.
func NewWithIntComparators() *Map {
return NewWith(utils.IntComparator, utils.IntComparator)
}
// NewWithStringComparators instantiates a bidirectional map with the StringComparator for key and value, i.e. keys and values are of type string.
func NewWithStringComparators() *Map {
return NewWith(utils.StringComparator, utils.StringComparator)
}
// Put inserts element into the map.
func (m *Map) Put(key interface{}, value interface{}) {
if d, ok := m.forwardMap.Get(key); ok {
m.inverseMap.Remove(d.(*data).value)
}
if d, ok := m.inverseMap.Get(value); ok {
m.forwardMap.Remove(d.(*data).key)
}
d := &data{key: key, value: value}
m.forwardMap.Put(key, d)
m.inverseMap.Put(value, d)
}
// Get searches the element in the map by key and returns its value or nil if key is not found in map.
// Second return parameter is true if key was found, otherwise false.
func (m *Map) Get(key interface{}) (value interface{}, found bool) {
if d, ok := m.forwardMap.Get(key); ok {
return d.(*data).value, true
}
return nil, false
}
// GetKey searches the element in the map by value and returns its key or nil if value is not found in map.
// Second return parameter is true if value was found, otherwise false.
func (m *Map) GetKey(value interface{}) (key interface{}, found bool) {
if d, ok := m.inverseMap.Get(value); ok {
return d.(*data).key, true
}
return nil, false
}
// Remove removes the element from the map by key.
func (m *Map) Remove(key interface{}) {
if d, found := m.forwardMap.Get(key); found {
m.forwardMap.Remove(key)
m.inverseMap.Remove(d.(*data).value)
}
}
// Empty returns true if map does not contain any elements
func (m *Map) Empty() bool {
return m.Size() == 0
}
// Size returns number of elements in the map.
func (m *Map) Size() int {
return m.forwardMap.Size()
}
// Keys returns all keys (ordered).
func (m *Map) Keys() []interface{} {
return m.forwardMap.Keys()
}
// Values returns all values (ordered).
func (m *Map) Values() []interface{} {
return m.inverseMap.Keys()
}
// Clear removes all elements from the map.
func (m *Map) Clear() {
m.forwardMap.Clear()
m.inverseMap.Clear()
}
// String returns a string representation of container
func (m *Map) String() string {
str := "TreeBidiMap\nmap["
it := m.Iterator()
for it.Next() {
str += fmt.Sprintf("%v:%v ", it.Key(), it.Value())
}
return strings.TrimRight(str, " ") + "]"
}
|
