Matt Jeanneret | cab955f | 2019-04-10 15:45:57 -0400 | [diff] [blame] | 1 | package ordered_map |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | ) |
| 6 | |
| 7 | type OrderedMap struct { |
| 8 | store map[interface{}]interface{} |
| 9 | mapper map[interface{}]*node |
| 10 | root *node |
| 11 | } |
| 12 | |
| 13 | func NewOrderedMap() *OrderedMap { |
| 14 | om := &OrderedMap{ |
| 15 | store: make(map[interface{}]interface{}), |
| 16 | mapper: make(map[interface{}]*node), |
| 17 | root: newRootNode(), |
| 18 | } |
| 19 | return om |
| 20 | } |
| 21 | |
| 22 | func NewOrderedMapWithArgs(args []*KVPair) *OrderedMap { |
| 23 | om := NewOrderedMap() |
| 24 | om.update(args) |
| 25 | return om |
| 26 | } |
| 27 | |
| 28 | func (om *OrderedMap) update(args []*KVPair) { |
| 29 | for _, pair := range args { |
| 30 | om.Set(pair.Key, pair.Value) |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | func (om *OrderedMap) Set(key interface{}, value interface{}) { |
| 35 | if _, ok := om.store[key]; ok == false { |
| 36 | root := om.root |
| 37 | last := root.Prev |
| 38 | last.Next = newNode(last, root, key) |
| 39 | root.Prev = last.Next |
| 40 | om.mapper[key] = last.Next |
| 41 | } |
| 42 | om.store[key] = value |
| 43 | } |
| 44 | |
| 45 | func (om *OrderedMap) Get(key interface{}) (interface{}, bool) { |
| 46 | val, ok := om.store[key] |
| 47 | return val, ok |
| 48 | } |
| 49 | |
| 50 | func (om *OrderedMap) Delete(key interface{}) { |
| 51 | _, ok := om.store[key] |
| 52 | if ok { |
| 53 | delete(om.store, key) |
| 54 | } |
| 55 | root, rootFound := om.mapper[key] |
| 56 | if rootFound { |
| 57 | prev := root.Prev |
| 58 | next := root.Next |
| 59 | prev.Next = next |
| 60 | next.Prev = prev |
| 61 | delete(om.mapper, key) |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | func (om *OrderedMap) String() string { |
| 66 | builder := make([]string, len(om.store)) |
| 67 | |
| 68 | var index int = 0 |
| 69 | iter := om.IterFunc() |
| 70 | for kv, ok := iter(); ok; kv, ok = iter() { |
| 71 | val, _ := om.Get(kv.Key) |
| 72 | builder[index] = fmt.Sprintf("%v:%v, ", kv.Key, val) |
| 73 | index++ |
| 74 | } |
| 75 | return fmt.Sprintf("OrderedMap%v", builder) |
| 76 | } |
| 77 | |
| 78 | func (om *OrderedMap) Iter() <-chan *KVPair { |
| 79 | println("Iter() method is deprecated!. Use IterFunc() instead.") |
| 80 | return om.UnsafeIter() |
| 81 | } |
| 82 | |
| 83 | /* |
| 84 | Beware, Iterator leaks goroutines if we do not fully traverse the map. |
| 85 | For most cases, `IterFunc()` should work as an iterator. |
| 86 | */ |
| 87 | func (om *OrderedMap) UnsafeIter() <-chan *KVPair { |
| 88 | keys := make(chan *KVPair) |
| 89 | go func() { |
| 90 | defer close(keys) |
| 91 | var curr *node |
| 92 | root := om.root |
| 93 | curr = root.Next |
| 94 | for curr != root { |
| 95 | v, _ := om.store[curr.Value] |
| 96 | keys <- &KVPair{curr.Value, v} |
| 97 | curr = curr.Next |
| 98 | } |
| 99 | }() |
| 100 | return keys |
| 101 | } |
| 102 | |
| 103 | func (om *OrderedMap) IterFunc() func() (*KVPair, bool) { |
| 104 | var curr *node |
| 105 | root := om.root |
| 106 | curr = root.Next |
| 107 | return func() (*KVPair, bool) { |
| 108 | for curr != root { |
| 109 | tmp := curr |
| 110 | curr = curr.Next |
| 111 | v, _ := om.store[tmp.Value] |
| 112 | return &KVPair{tmp.Value, v}, true |
| 113 | } |
| 114 | return nil, false |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | func (om *OrderedMap) Len() int { |
| 119 | return len(om.store) |
| 120 | } |
| 121 | |