File: README.md

package info (click to toggle)
golang-github-benbjohnson-immutable 0.2.0-2
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, sid
  • size: 204 kB
  • sloc: makefile: 2
file content (300 lines) | stat: -rw-r--r-- 9,164 bytes parent folder | download
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
Immutable ![release](https://img.shields.io/github/release/benbjohnson/immutable.svg?style=flat-square) ![CircleCI](https://img.shields.io/circleci/project/github/benbjohnson/immutable/master.svg?style=flat-square) ![coverage](https://img.shields.io/codecov/c/github/benbjohnson/immutable/master.svg?style=flat-square) ![license](https://img.shields.io/github/license/benbjohnson/immutable.svg?style=flat-square)
=========

This repository contains immutable collection types for Go. It includes
`List`, `Map`, and `SortedMap` implementations. Immutable collections can
provide efficient, lock free sharing of data by requiring that edits to the
collections return new collections.

The collection types in this library are meant to mimic Go built-in collections
such as`slice` and `map`. The primary usage difference between Go collections
and `immutable` collections is that `immutable` collections always return a new
collection on mutation so you will need to save the new reference.

Immutable collections are not for every situation, however, as they can incur
additional CPU and memory overhead. Please evaluate the cost/benefit for your
particular project.

Special thanks to the [Immutable.js](https://immutable-js.github.io/immutable-js/)
team as the `List` & `Map` implementations are loose ports from that project.


## List

The `List` type represents a sorted, indexed collection of values and operates
similarly to a Go slice. It supports efficient append, prepend, update, and
slice operations.


### Adding list elements

Elements can be added to the end of the list with the `Append()` method or added
to the beginning of the list with the `Prepend()` method. Unlike Go slices,
prepending is as efficient as appending.

```go
// Create a list with 3 elements.
l := immutable.NewList()
l = l.Append("foo")
l = l.Append("bar")
l = l.Prepend("baz")

fmt.Println(l.Len())  // 3
fmt.Println(l.Get(0)) // "baz"
fmt.Println(l.Get(1)) // "foo"
fmt.Println(l.Get(2)) // "bar"
```

Note that each change to the list results in a new list being created. These
lists are all snapshots at that point in time and cannot be changed so they 
are safe to share between multiple goroutines.

### Updating list elements

You can also overwrite existing elements by using the `Set()` method. In the
following example, we'll update the third element in our list and return the
new list to a new variable. You can see that our old `l` variable retains a
snapshot of the original value.

```go
l := immutable.NewList()
l = l.Append("foo")
l = l.Append("bar")
newList := l.Set(2, "baz")

fmt.Println(l.Get(1))       // "bar"
fmt.Println(newList.Get(1)) // "baz"
```

### Deriving sublists

You can create a sublist by using the `Slice()` method. This method works with
the same rules as subslicing a Go slice:

```go
l = l.Slice(0, 2)

fmt.Println(l.Len())  // 2
fmt.Println(l.Get(0)) // "baz"
fmt.Println(l.Get(1)) // "foo"
```

Please note that since `List` follows the same rules as slices, it will panic if
you try to `Get()`, `Set()`, or `Slice()` with indexes that are outside of
the range of the `List`.



### Iterating lists

Iterators provide a clean, simple way to iterate over the elements of the list
in order. This is more efficient than simply calling `Get()` for each index.

Below is an example of iterating over all elements of our list from above:

```go
itr := l.Iterator()
for !itr.Done() {
	index, value := itr.Next()
	fmt.Printf("Index %d equals %v\n", index, value)
}

// Index 0 equals baz
// Index 1 equals foo
```

By default iterators start from index zero, however, the `Seek()` method can be
used to jump to a given index.


### Efficiently building lists

If you are building large lists, it is significantly more efficient to use the
`ListBuilder`. It uses nearly the same API as `List` except that it updates
a list in-place until you are ready to use it. This can improve bulk list
building by 10x or more.

```go
b := immutable.NewListBuilder(immutable.NewList())
b.Append("foo")
b.Append("bar")
b.Set(2, "baz")

l := b.List()
fmt.Println(l.Get(0)) // "foo"
fmt.Println(l.Get(1)) // "baz"
```

Lists are safe to use even after you continue to use the builder. It is also
safe to build on top of existing lists.


## Map

The `Map` represents an associative array that maps unique keys to values. It
is implemented to act similarly to the built-in Go `map` type. It is implemented
as a [Hash-Array Mapped Trie](https://lampwww.epfl.ch/papers/idealhashtrees.pdf).

Maps require a `Hasher` to hash keys and check for equality. There are built-in
hasher implementations for `int`, `string`, and `[]byte` keys. You may pass in
a `nil` hasher to `NewMap()` if you are using one of these key types.


### Setting map key/value pairs

You can add a key/value pair to the map by using the `Set()` method. It will
add the key if it does not exist or it will overwrite the value for the key if
it does exist.

Values may be fetched for a key using the `Get()` method. This method returns
the value as well as a flag indicating if the key existed. The flag is useful
to check if a `nil` value was set for a key versus a key did not exist.

```go
m := immutable.NewMap(nil)
m = m.Set("jane", 100)
m = m.Set("susy", 200)
m = m.Set("jane", 300) // overwrite

fmt.Println(m.Len())   // 2

v, ok := m.Get("jane")
fmt.Println(v, ok)     // 300 true

v, ok = m.Get("susy")
fmt.Println(v, ok)     // 200, true

v, ok = m.Get("john")
fmt.Println(v, ok)     // nil, false
```


### Removing map keys

Keys may be removed from the map by using the `Delete()` method. If the key does
not exist then the original map is returned instead of a new one.

```go
m := immutable.NewMap(nil)
m = m.Set("jane", 100)
m = m.Delete("jane")

fmt.Println(m.Len())   // 0

v, ok := m.Get("jane")
fmt.Println(v, ok)     // nil false
```


### Iterating maps

Maps are unsorted, however, iterators can be used to loop over all key/value
pairs in the collection. Unlike Go maps, iterators are deterministic when
iterating over key/value pairs.

```go
m := immutable.NewMap(nil)
m = m.Set("jane", 100)
m = m.Set("susy", 200)

itr := m.Iterator()
for !itr.Done() {
	k, v := itr.Next()
	fmt.Println(k, v)
}

// susy 200
// jane 100
```

Note that you should not rely on two maps with the same key/value pairs to
iterate in the same order. Ordering can be insertion order dependent when two
keys generate the same hash.


### Efficiently building maps

If you are executing multiple mutations on a map, it can be much more efficient
to use the `MapBuilder`. It uses nearly the same API as `Map` except that it 
updates a map in-place until you are ready to use it. 

```go
b := immutable.NewMapBuilder(immutable.NewMap(nil))
b.Set("foo", 100)
b.Set("bar", 200)
b.Set("foo", 300)

m := b.Map()
fmt.Println(m.Get("foo")) // "300"
fmt.Println(m.Get("bar")) // "200"
```

Maps are safe to use even after you continue to use the builder. You can
also build on top of existing maps too.


### Implementing a custom Hasher

If you need to use a key type besides `int`, `string`, or `[]byte` then you'll
need to create a custom `Hasher` implementation and pass it to `NewMap()` on
creation.

Hashers are fairly simple. They only need to generate hashes for a given key
and check equality given two keys.

```go
type Hasher interface {
	Hash(key interface{}) uint32
	Equal(a, b interface{}) bool
}
```

Please see the internal `intHasher`, `stringHasher`, and `byteSliceHasher` for examples.


## Sorted Map

The `SortedMap` represents an associative array that maps unique keys to values.
Unlike the `Map`, however, keys can be iterated over in-order. It is implemented
as a B+tree.

Sorted maps require a `Comparer` to sort keys and check for equality. There are
built-in comparer implementations for `int`, `string`, and `[]byte` keys. You 
may pass a `nil` comparer to `NewSortedMap()` if you are using one of these key
types.

The API is identical to the `Map` implementation. The sorted map also has a
companion `SortedMapBuilder` for more efficiently building maps.


### Implementing a custom Comparer

If you need to use a key type besides `int`, `string`, or `[]byte` then you'll
need to create a custom `Comparer` implementation and pass it to
`NewSortedMap()` on creation.

Comparers on have one method—`Compare()`. It works the same as the
`strings.Compare()` function. It returns `-1` if `a` is less than `b`, returns
`1` if a is greater than `b`, and returns `0` if `a` is equal to `b`.

```go
type Comparer interface {
	Compare(a, b interface{}) int
}
```

Please see the internal `intComparer`, `stringComparer`, and `byteSliceComparer` for examples.



## Contributing

The goal of `immutable` is to provide stable, reasonably performant, immutable
collections library for Go that has a simple, idiomatic API. As such, additional
features and minor performance improvements will generally not be accepted. If
you have a suggestion for a clearer API or substantial performance improvement,
_please_ open an issue first to discuss. All pull requests without a related
issue will be closed immediately.

Please submit issues relating to bugs & documentation improvements.