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