1Immutable    
2=========
3
4This repository contains *generic* immutable collection types for Go. It includes
5`List`, `Map`, `SortedMap`, `Set` and `SortedSet` implementations. Immutable collections can
6provide efficient, lock free sharing of data by requiring that edits to the
7collections return new collections.
8
9The collection types in this library are meant to mimic Go built-in collections
10such as`slice` and `map`. The primary usage difference between Go collections
11and `immutable` collections is that `immutable` collections always return a new
12collection on mutation so you will need to save the new reference.
13
14Immutable collections are not for every situation, however, as they can incur
15additional CPU and memory overhead. Please evaluate the cost/benefit for your
16particular project.
17
18Special thanks to the [Immutable.js](https://immutable-js.github.io/immutable-js/)
19team as the `List` & `Map` implementations are loose ports from that project.
20
21
22## List
23
24The `List` type represents a sorted, indexed collection of values and operates
25similarly to a Go slice. It supports efficient append, prepend, update, and
26slice operations.
27
28
29### Adding list elements
30
31Elements can be added to the end of the list with the `Append()` method or added
32to the beginning of the list with the `Prepend()` method. Unlike Go slices,
33prepending is as efficient as appending.
34
35```go
36// Create a list with 3 elements.
37l := immutable.NewList[string]()
38l = l.Append("foo")
39l = l.Append("bar")
40l = l.Prepend("baz")
41
42fmt.Println(l.Len()) // 3
43fmt.Println(l.Get(0)) // "baz"
44fmt.Println(l.Get(1)) // "foo"
45fmt.Println(l.Get(2)) // "bar"
46```
47
48Note that each change to the list results in a new list being created. These
49lists are all snapshots at that point in time and cannot be changed so they
50are safe to share between multiple goroutines.
51
52### Updating list elements
53
54You can also overwrite existing elements by using the `Set()` method. In the
55following example, we'll update the third element in our list and return the
56new list to a new variable. You can see that our old `l` variable retains a
57snapshot of the original value.
58
59```go
60l := immutable.NewList[string]()
61l = l.Append("foo")
62l = l.Append("bar")
63newList := l.Set(2, "baz")
64
65fmt.Println(l.Get(1)) // "bar"
66fmt.Println(newList.Get(1)) // "baz"
67```
68
69### Deriving sublists
70
71You can create a sublist by using the `Slice()` method. This method works with
72the same rules as subslicing a Go slice:
73
74```go
75l = l.Slice(0, 2)
76
77fmt.Println(l.Len()) // 2
78fmt.Println(l.Get(0)) // "baz"
79fmt.Println(l.Get(1)) // "foo"
80```
81
82Please note that since `List` follows the same rules as slices, it will panic if
83you try to `Get()`, `Set()`, or `Slice()` with indexes that are outside of
84the range of the `List`.
85
86
87
88### Iterating lists
89
90Iterators provide a clean, simple way to iterate over the elements of the list
91in order. This is more efficient than simply calling `Get()` for each index.
92
93Below is an example of iterating over all elements of our list from above:
94
95```go
96itr := l.Iterator()
97for !itr.Done() {
98 index, value, _ := itr.Next()
99 fmt.Printf("Index %d equals %v\n", index, value)
100}
101
102// Index 0 equals baz
103// Index 1 equals foo
104```
105
106By default iterators start from index zero, however, the `Seek()` method can be
107used to jump to a given index.
108
109
110### Efficiently building lists
111
112If you are building large lists, it is significantly more efficient to use the
113`ListBuilder`. It uses nearly the same API as `List` except that it updates
114a list in-place until you are ready to use it. This can improve bulk list
115building by 10x or more.
116
117```go
118b := immutable.NewListBuilder[string]()
119b.Append("foo")
120b.Append("bar")
121b.Set(2, "baz")
122
123l := b.List()
124fmt.Println(l.Get(0)) // "foo"
125fmt.Println(l.Get(1)) // "baz"
126```
127
128Builders are invalid after the call to `List()`.
129
130
131## Map
132
133The `Map` represents an associative array that maps unique keys to values. It
134is implemented to act similarly to the built-in Go `map` type. It is implemented
135as a [Hash-Array Mapped Trie](https://lampwww.epfl.ch/papers/idealhashtrees.pdf).
136
137Maps require a `Hasher` to hash keys and check for equality. There are built-in
138hasher implementations for most primitive types such as `int`, `uint`, and
139`string` keys. You may pass in a `nil` hasher to `NewMap()` if you are using
140one of these key types.
141
142### Setting map key/value pairs
143
144You can add a key/value pair to the map by using the `Set()` method. It will
145add the key if it does not exist or it will overwrite the value for the key if
146it does exist.
147
148Values may be fetched for a key using the `Get()` method. This method returns
149the value as well as a flag indicating if the key existed. The flag is useful
150to check if a `nil` value was set for a key versus a key did not exist.
151
152```go
153m := immutable.NewMap[string,int](nil)
154m = m.Set("jane", 100)
155m = m.Set("susy", 200)
156m = m.Set("jane", 300) // overwrite
157
158fmt.Println(m.Len()) // 2
159
160v, ok := m.Get("jane")
161fmt.Println(v, ok) // 300 true
162
163v, ok = m.Get("susy")
164fmt.Println(v, ok) // 200, true
165
166v, ok = m.Get("john")
167fmt.Println(v, ok) // nil, false
168```
169
170
171### Removing map keys
172
173Keys may be removed from the map by using the `Delete()` method. If the key does
174not exist then the original map is returned instead of a new one.
175
176```go
177m := immutable.NewMap[string,int](nil)
178m = m.Set("jane", 100)
179m = m.Delete("jane")
180
181fmt.Println(m.Len()) // 0
182
183v, ok := m.Get("jane")
184fmt.Println(v, ok) // nil false
185```
186
187
188### Iterating maps
189
190Maps are unsorted, however, iterators can be used to loop over all key/value
191pairs in the collection. Unlike Go maps, iterators are deterministic when
192iterating over key/value pairs.
193
194```go
195m := immutable.NewMap[string,int](nil)
196m = m.Set("jane", 100)
197m = m.Set("susy", 200)
198
199itr := m.Iterator()
200for !itr.Done() {
201 k, v := itr.Next()
202 fmt.Println(k, v)
203}
204
205// susy 200
206// jane 100
207```
208
209Note that you should not rely on two maps with the same key/value pairs to
210iterate in the same order. Ordering can be insertion order dependent when two
211keys generate the same hash.
212
213
214### Efficiently building maps
215
216If you are executing multiple mutations on a map, it can be much more efficient
217to use the `MapBuilder`. It uses nearly the same API as `Map` except that it
218updates a map in-place until you are ready to use it.
219
220```go
221b := immutable.NewMapBuilder[string,int](nil)
222b.Set("foo", 100)
223b.Set("bar", 200)
224b.Set("foo", 300)
225
226m := b.Map()
227fmt.Println(m.Get("foo")) // "300"
228fmt.Println(m.Get("bar")) // "200"
229```
230
231Builders are invalid after the call to `Map()`.
232
233
234### Implementing a custom Hasher
235
236If you need to use a key type besides `int`, `uint`, or `string` then you'll
237need to create a custom `Hasher` implementation and pass it to `NewMap()` on
238creation.
239
240Hashers are fairly simple. They only need to generate hashes for a given key
241and check equality given two keys.
242
243```go
244type Hasher[K any] interface {
245 Hash(key K) uint32
246 Equal(a, b K) bool
247}
248```
249
250Please see the internal `intHasher`, `uintHasher`, `stringHasher`, and
251`byteSliceHasher` for examples.
252
253
254## Sorted Map
255
256The `SortedMap` represents an associative array that maps unique keys to values.
257Unlike the `Map`, however, keys can be iterated over in-order. It is implemented
258as a B+tree.
259
260Sorted maps require a `Comparer` to sort keys and check for equality. There are
261built-in comparer implementations for `int`, `uint`, and `string` keys. You may
262pass a `nil` comparer to `NewSortedMap()` if you are using one of these key
263types.
264
265The API is identical to the `Map` implementation. The sorted map also has a
266companion `SortedMapBuilder` for more efficiently building maps.
267
268
269### Implementing a custom Comparer
270
271If you need to use a key type besides `int`, `uint`, or `string` or derived types, then you'll
272need to create a custom `Comparer` implementation and pass it to
273`NewSortedMap()` on creation.
274
275Comparers on have one method—`Compare()`. It works the same as the
276`strings.Compare()` function. It returns `-1` if `a` is less than `b`, returns
277`1` if a is greater than `b`, and returns `0` if `a` is equal to `b`.
278
279```go
280type Comparer[K any] interface {
281 Compare(a, b K) int
282}
283```
284
285Please see the internal `defaultComparer` for an example, bearing in mind that it works for several types.
286
287## Set
288
289The `Set` represents a collection of unique values, and it is implemented as a
290wrapper around a `Map[T, struct{}]`.
291
292Like Maps, Sets require a `Hasher` to hash keys and check for equality. There are built-in
293hasher implementations for most primitive types such as `int`, `uint`, and
294`string` keys. You may pass in a `nil` hasher to `NewMap()` if you are using
295one of these key types.
296
297
298## Sorted Set
299
300The `SortedSet` represents a sorted collection of unique values.
301Unlike the `Set`, however, keys can be iterated over in-order. It is implemented
302as a B+tree.
303
304Sorted sets require a `Comparer` to sort values and check for equality. There are
305built-in comparer implementations for `int`, `uint`, and `string` keys. You may
306pass a `nil` comparer to `NewSortedSet()` if you are using one of these key
307types.
308
309The API is identical to the `Set` implementation.
310
311
312## Contributing
313
314The goal of `immutable` is to provide stable, reasonably performant, immutable
315collections library for Go that has a simple, idiomatic API. As such, additional
316features and minor performance improvements will generally not be accepted. If
317you have a suggestion for a clearer API or substantial performance improvement,
318_please_ open an issue first to discuss. All pull requests without a related
319issue will be closed immediately.
320
321Please submit issues relating to bugs & documentation improvements.
322
View as plain text