README.md
1[![GoDoc](https://godoc.org/github.com/emirpasic/gods?status.svg)](https://godoc.org/github.com/emirpasic/gods) [![Build Status](https://travis-ci.org/emirpasic/gods.svg)](https://travis-ci.org/emirpasic/gods) [![Go Report Card](https://goreportcard.com/badge/github.com/emirpasic/gods)](https://goreportcard.com/report/github.com/emirpasic/gods) [![PyPI](https://img.shields.io/pypi/l/Django.svg?maxAge=2592000)](https://github.com/emirpasic/gods/blob/master/LICENSE)
2
3# GoDS (Go Data Structures)
4
5Implementation of various data structures and algorithms in Go.
6
7## Data Structures
8
9- [Containers](#containers)
10 - [Lists](#lists)
11 - [ArrayList](#arraylist)
12 - [SinglyLinkedList](#singlylinkedlist)
13 - [DoublyLinkedList](#doublylinkedlist)
14 - [Sets](#sets)
15 - [HashSet](#hashset)
16 - [TreeSet](#treeset)
17 - [LinkedHashSet](#linkedhashset)
18 - [Stacks](#stacks)
19 - [LinkedListStack](#linkedliststack)
20 - [ArrayStack](#arraystack)
21 - [Maps](#maps)
22 - [HashMap](#hashmap)
23 - [TreeMap](#treemap)
24 - [LinkedHashMap](#linkedhashmap)
25 - [HashBidiMap](#hashbidimap)
26 - [TreeBidiMap](#treebidimap)
27 - [Trees](#trees)
28 - [RedBlackTree](#redblacktree)
29 - [AVLTree](#avltree)
30 - [BTree](#btree)
31 - [BinaryHeap](#binaryheap)
32- [Functions](#functions)
33 - [Comparator](#comparator)
34 - [Iterator](#iterator)
35 - [IteratorWithIndex](#iteratorwithindex)
36 - [IteratorWithKey](#iteratorwithkey)
37 - [ReverseIteratorWithIndex](#reverseiteratorwithindex)
38 - [ReverseIteratorWithKey](#reverseiteratorwithkey)
39 - [Enumerable](#enumerable)
40 - [EnumerableWithIndex](#enumerablewithindex)
41 - [EnumerableWithKey](#enumerablewithkey)
42 - [Serialization](#serialization)
43 - [JSONSerializer](#jsonserializer)
44 - [JSONDeserializer](#jsondeserializer)
45 - [Sort](#sort)
46 - [Container](#container)
47- [Appendix](#appendix)
48
49
50## Containers
51
52All data structures implement the container interface with the following methods:
53
54```go
55type Container interface {
56 Empty() bool
57 Size() int
58 Clear()
59 Values() []interface{}
60}
61```
62
63Containers are either ordered or unordered. All ordered containers provide [stateful iterators](#iterator) and some of them allow [enumerable functions](#enumerable).
64
65| **Data** | **Structure** | **Ordered** | **[Iterator](#iterator)** | **[Enumerable](#enumerable)** | **Referenced by** |
66| :--- | :--- | :---: | :---: | :---: | :---: |
67| [Lists](#lists) |
68| | [ArrayList](#arraylist) | yes | yes* | yes | index |
69| | [SinglyLinkedList](#singlylinkedlist) | yes | yes | yes | index |
70| | [DoublyLinkedList](#doublylinkedlist) | yes | yes* | yes | index |
71| [Sets](#sets) |
72| | [HashSet](#hashset) | no | no | no | index |
73| | [TreeSet](#treeset) | yes | yes* | yes | index |
74| | [LinkedHashSet](#linkedhashset) | yes | yes* | yes | index |
75| [Stacks](#stacks) |
76| | [LinkedListStack](#linkedliststack) | yes | yes | no | index |
77| | [ArrayStack](#arraystack) | yes | yes* | no | index |
78| [Maps](#maps) |
79| | [HashMap](#hashmap) | no | no | no | key |
80| | [TreeMap](#treemap) | yes | yes* | yes | key |
81| | [LinkedHashMap](#linkedhashmap) | yes | yes* | yes | key |
82| | [HashBidiMap](#hashbidimap) | no | no | no | key* |
83| | [TreeBidiMap](#treebidimap) | yes | yes* | yes | key* |
84| [Trees](#trees) |
85| | [RedBlackTree](#redblacktree) | yes | yes* | no | key |
86| | [AVLTree](#avltree) | yes | yes* | no | key |
87| | [BTree](#btree) | yes | yes* | no | key |
88| | [BinaryHeap](#binaryheap) | yes | yes* | no | index |
89| | | | <sub><sup>*reversible</sup></sub> | | <sub><sup>*bidirectional</sup></sub> |
90
91### Lists
92
93A list is a data structure that stores values and may have repeated values.
94
95Implements [Container](#containers) interface.
96
97```go
98type List interface {
99 Get(index int) (interface{}, bool)
100 Remove(index int)
101 Add(values ...interface{})
102 Contains(values ...interface{}) bool
103 Sort(comparator utils.Comparator)
104 Swap(index1, index2 int)
105 Insert(index int, values ...interface{})
106 Set(index int, value interface{})
107
108 containers.Container
109 // Empty() bool
110 // Size() int
111 // Clear()
112 // Values() []interface{}
113}
114```
115
116#### ArrayList
117
118A [list](#lists) backed by a dynamic array that grows and shrinks implicitly.
119
120Implements [List](#lists), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
121
122```go
123package main
124
125import (
126 "github.com/emirpasic/gods/lists/arraylist"
127 "github.com/emirpasic/gods/utils"
128)
129
130func main() {
131 list := arraylist.New()
132 list.Add("a") // ["a"]
133 list.Add("c", "b") // ["a","c","b"]
134 list.Sort(utils.StringComparator) // ["a","b","c"]
135 _, _ = list.Get(0) // "a",true
136 _, _ = list.Get(100) // nil,false
137 _ = list.Contains("a", "b", "c") // true
138 _ = list.Contains("a", "b", "c", "d") // false
139 list.Swap(0, 1) // ["b","a",c"]
140 list.Remove(2) // ["b","a"]
141 list.Remove(1) // ["b"]
142 list.Remove(0) // []
143 list.Remove(0) // [] (ignored)
144 _ = list.Empty() // true
145 _ = list.Size() // 0
146 list.Add("a") // ["a"]
147 list.Clear() // []
148 list.Insert(0, "b") // ["b"]
149 list.Insert(0, "a") // ["a","b"]
150}
151```
152
153#### SinglyLinkedList
154
155A [list](#lists) where each element points to the next element in the list.
156
157Implements [List](#lists), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
158
159```go
160package main
161
162import (
163 sll "github.com/emirpasic/gods/lists/singlylinkedlist"
164 "github.com/emirpasic/gods/utils"
165)
166
167func main() {
168 list := sll.New()
169 list.Add("a") // ["a"]
170 list.Add("c", "b") // ["a","c","b"]
171 list.Sort(utils.StringComparator) // ["a","b","c"]
172 _, _ = list.Get(0) // "a",true
173 _, _ = list.Get(100) // nil,false
174 _ = list.Contains("a", "b", "c") // true
175 _ = list.Contains("a", "b", "c", "d") // false
176 list.Swap(0, 1) // ["b","a",c"]
177 list.Remove(2) // ["b","a"]
178 list.Remove(1) // ["b"]
179 list.Remove(0) // []
180 list.Remove(0) // [] (ignored)
181 _ = list.Empty() // true
182 _ = list.Size() // 0
183 list.Add("a") // ["a"]
184 list.Clear() // []
185 list.Insert(0, "b") // ["b"]
186 list.Insert(0, "a") // ["a","b"]
187}
188```
189
190#### DoublyLinkedList
191
192A [list](#lists) where each element points to the next and previous elements in the list.
193
194Implements [List](#lists), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
195
196```go
197package main
198
199import (
200 dll "github.com/emirpasic/gods/lists/doublylinkedlist"
201 "github.com/emirpasic/gods/utils"
202)
203
204func main() {
205 list := dll.New()
206 list.Add("a") // ["a"]
207 list.Add("c", "b") // ["a","c","b"]
208 list.Sort(utils.StringComparator) // ["a","b","c"]
209 _, _ = list.Get(0) // "a",true
210 _, _ = list.Get(100) // nil,false
211 _ = list.Contains("a", "b", "c") // true
212 _ = list.Contains("a", "b", "c", "d") // false
213 list.Swap(0, 1) // ["b","a",c"]
214 list.Remove(2) // ["b","a"]
215 list.Remove(1) // ["b"]
216 list.Remove(0) // []
217 list.Remove(0) // [] (ignored)
218 _ = list.Empty() // true
219 _ = list.Size() // 0
220 list.Add("a") // ["a"]
221 list.Clear() // []
222 list.Insert(0, "b") // ["b"]
223 list.Insert(0, "a") // ["a","b"]
224}
225```
226
227### Sets
228
229A set is a data structure that can store elements and has no repeated values. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests an element for membership in a set. This structure is often used to ensure that no duplicates are present in a container.
230
231Implements [Container](#containers) interface.
232
233```go
234type Set interface {
235 Add(elements ...interface{})
236 Remove(elements ...interface{})
237 Contains(elements ...interface{}) bool
238
239 containers.Container
240 // Empty() bool
241 // Size() int
242 // Clear()
243 // Values() []interface{}
244}
245```
246
247#### HashSet
248
249A [set](#sets) backed by a hash table (actually a Go's map). It makes no guarantees as to the iteration order of the set.
250
251Implements [Set](#sets), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
252
253```go
254package main
255
256import "github.com/emirpasic/gods/sets/hashset"
257
258func main() {
259 set := hashset.New() // empty
260 set.Add(1) // 1
261 set.Add(2, 2, 3, 4, 5) // 3, 1, 2, 4, 5 (random order, duplicates ignored)
262 set.Remove(4) // 5, 3, 2, 1 (random order)
263 set.Remove(2, 3) // 1, 5 (random order)
264 set.Contains(1) // true
265 set.Contains(1, 5) // true
266 set.Contains(1, 6) // false
267 _ = set.Values() // []int{5,1} (random order)
268 set.Clear() // empty
269 set.Empty() // true
270 set.Size() // 0
271}
272```
273
274#### TreeSet
275
276A [set](#sets) backed by a [red-black tree](#redblacktree) to keep the elements ordered with respect to the [comparator](#comparator).
277
278Implements [Set](#sets), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
279
280```go
281package main
282
283import "github.com/emirpasic/gods/sets/treeset"
284
285func main() {
286 set := treeset.NewWithIntComparator() // empty (keys are of type int)
287 set.Add(1) // 1
288 set.Add(2, 2, 3, 4, 5) // 1, 2, 3, 4, 5 (in order, duplicates ignored)
289 set.Remove(4) // 1, 2, 3, 5 (in order)
290 set.Remove(2, 3) // 1, 5 (in order)
291 set.Contains(1) // true
292 set.Contains(1, 5) // true
293 set.Contains(1, 6) // false
294 _ = set.Values() // []int{1,5} (in order)
295 set.Clear() // empty
296 set.Empty() // true
297 set.Size() // 0
298}
299```
300
301#### LinkedHashSet
302
303A [set](#sets) that preserves insertion-order. Data structure is backed by a hash table to store values and [doubly-linked list](#doublylinkedlist) to store insertion ordering.
304
305Implements [Set](#sets), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
306
307```go
308package main
309
310import "github.com/emirpasic/gods/sets/linkedhashset"
311
312func main() {
313 set := linkedhashset.New() // empty
314 set.Add(5) // 5
315 set.Add(4, 4, 3, 2, 1) // 5, 4, 3, 2, 1 (in insertion-order, duplicates ignored)
316 set.Add(4) // 5, 4, 3, 2, 1 (duplicates ignored, insertion-order unchanged)
317 set.Remove(4) // 5, 3, 2, 1 (in insertion-order)
318 set.Remove(2, 3) // 5, 1 (in insertion-order)
319 set.Contains(1) // true
320 set.Contains(1, 5) // true
321 set.Contains(1, 6) // false
322 _ = set.Values() // []int{5, 1} (in insertion-order)
323 set.Clear() // empty
324 set.Empty() // true
325 set.Size() // 0
326}
327```
328
329### Stacks
330
331A stack that represents a last-in-first-out (LIFO) data structure. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack.
332
333Implements [Container](#containers) interface.
334
335```go
336type Stack interface {
337 Push(value interface{})
338 Pop() (value interface{}, ok bool)
339 Peek() (value interface{}, ok bool)
340
341 containers.Container
342 // Empty() bool
343 // Size() int
344 // Clear()
345 // Values() []interface{}
346}
347```
348
349#### LinkedListStack
350
351A [stack](#stacks) based on a [linked list](#singlylinkedlist).
352
353Implements [Stack](#stacks), [IteratorWithIndex](#iteratorwithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
354
355```go
356package main
357
358import lls "github.com/emirpasic/gods/stacks/linkedliststack"
359
360func main() {
361 stack := lls.New() // empty
362 stack.Push(1) // 1
363 stack.Push(2) // 1, 2
364 stack.Values() // 2, 1 (LIFO order)
365 _, _ = stack.Peek() // 2,true
366 _, _ = stack.Pop() // 2, true
367 _, _ = stack.Pop() // 1, true
368 _, _ = stack.Pop() // nil, false (nothing to pop)
369 stack.Push(1) // 1
370 stack.Clear() // empty
371 stack.Empty() // true
372 stack.Size() // 0
373}
374```
375
376#### ArrayStack
377
378A [stack](#stacks) based on a [array list](#arraylist).
379
380Implements [Stack](#stacks), [IteratorWithIndex](#iteratorwithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
381
382```go
383package main
384
385import "github.com/emirpasic/gods/stacks/arraystack"
386
387func main() {
388 stack := arraystack.New() // empty
389 stack.Push(1) // 1
390 stack.Push(2) // 1, 2
391 stack.Values() // 2, 1 (LIFO order)
392 _, _ = stack.Peek() // 2,true
393 _, _ = stack.Pop() // 2, true
394 _, _ = stack.Pop() // 1, true
395 _, _ = stack.Pop() // nil, false (nothing to pop)
396 stack.Push(1) // 1
397 stack.Clear() // empty
398 stack.Empty() // true
399 stack.Size() // 0
400}
401```
402
403### Maps
404
405A Map is a data structure that maps keys to values. A map cannot contain duplicate keys and each key can map to at most one value.
406
407Implements [Container](#containers) interface.
408
409```go
410type Map interface {
411 Put(key interface{}, value interface{})
412 Get(key interface{}) (value interface{}, found bool)
413 Remove(key interface{})
414 Keys() []interface{}
415
416 containers.Container
417 // Empty() bool
418 // Size() int
419 // Clear()
420 // Values() []interface{}
421}
422```
423
424A BidiMap is an extension to the Map. A bidirectional map (BidiMap), also called a hash bag, is an associative data structure in which the key-value pairs form a one-to-one relation. This relation works in both directions by allow the value to also act as a key to key, e.g. a pair (a,b) thus provides a 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.
425
426```go
427type BidiMap interface {
428 GetKey(value interface{}) (key interface{}, found bool)
429
430 Map
431}
432```
433
434#### HashMap
435
436A [map](#maps) based on hash tables. Keys are unordered.
437
438Implements [Map](#maps), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
439
440```go
441package main
442
443import "github.com/emirpasic/gods/maps/hashmap"
444
445func main() {
446 m := hashmap.New() // empty
447 m.Put(1, "x") // 1->x
448 m.Put(2, "b") // 2->b, 1->x (random order)
449 m.Put(1, "a") // 2->b, 1->a (random order)
450 _, _ = m.Get(2) // b, true
451 _, _ = m.Get(3) // nil, false
452 _ = m.Values() // []interface {}{"b", "a"} (random order)
453 _ = m.Keys() // []interface {}{1, 2} (random order)
454 m.Remove(1) // 2->b
455 m.Clear() // empty
456 m.Empty() // true
457 m.Size() // 0
458}
459```
460
461#### TreeMap
462
463A [map](#maps) based on [red-black tree](#redblacktree). Keys are ordered ordered with respect to the [comparator](#comparator).
464
465Implements [Map](#maps), [IteratorWithKey](#iteratorwithkey), [EnumerableWithKey](#enumerablewithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
466
467```go
468package main
469
470import "github.com/emirpasic/gods/maps/treemap"
471
472func main() {
473 m := treemap.NewWithIntComparator() // empty (keys are of type int)
474 m.Put(1, "x") // 1->x
475 m.Put(2, "b") // 1->x, 2->b (in order)
476 m.Put(1, "a") // 1->a, 2->b (in order)
477 _, _ = m.Get(2) // b, true
478 _, _ = m.Get(3) // nil, false
479 _ = m.Values() // []interface {}{"a", "b"} (in order)
480 _ = m.Keys() // []interface {}{1, 2} (in order)
481 m.Remove(1) // 2->b
482 m.Clear() // empty
483 m.Empty() // true
484 m.Size() // 0
485
486 // Other:
487 m.Min() // Returns the minimum key and its value from map.
488 m.Max() // Returns the maximum key and its value from map.
489}
490```
491
492#### LinkedHashMap
493
494A [map](#maps) that preserves insertion-order. It is backed by a hash table to store values and [doubly-linked list](doublylinkedlist) to store ordering.
495
496Implements [Map](#maps), [IteratorWithKey](#iteratorwithkey), [EnumerableWithKey](#enumerablewithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
497
498```go
499package main
500
501import "github.com/emirpasic/gods/maps/linkedhashmap"
502
503func main() {
504 m := linkedhashmap.New() // empty (keys are of type int)
505 m.Put(2, "b") // 2->b
506 m.Put(1, "x") // 2->b, 1->x (insertion-order)
507 m.Put(1, "a") // 2->b, 1->a (insertion-order)
508 _, _ = m.Get(2) // b, true
509 _, _ = m.Get(3) // nil, false
510 _ = m.Values() // []interface {}{"b", "a"} (insertion-order)
511 _ = m.Keys() // []interface {}{2, 1} (insertion-order)
512 m.Remove(1) // 2->b
513 m.Clear() // empty
514 m.Empty() // true
515 m.Size() // 0
516}
517
518```
519
520#### HashBidiMap
521
522A [map](#maps) based on two hashmaps. Keys are unordered.
523
524Implements [BidiMap](#maps), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
525
526```go
527package main
528
529import "github.com/emirpasic/gods/maps/hashbidimap"
530
531func main() {
532 m := hashbidimap.New() // empty
533 m.Put(1, "x") // 1->x
534 m.Put(3, "b") // 1->x, 3->b (random order)
535 m.Put(1, "a") // 1->a, 3->b (random order)
536 m.Put(2, "b") // 1->a, 2->b (random order)
537 _, _ = m.GetKey("a") // 1, true
538 _, _ = m.Get(2) // b, true
539 _, _ = m.Get(3) // nil, false
540 _ = m.Values() // []interface {}{"a", "b"} (random order)
541 _ = m.Keys() // []interface {}{1, 2} (random order)
542 m.Remove(1) // 2->b
543 m.Clear() // empty
544 m.Empty() // true
545 m.Size() // 0
546}
547```
548
549#### TreeBidiMap
550
551A [map](#maps) based on red-black tree. This map 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 (unlike in [HashBidiMap](#hashbidimap)), which can be significant if contained elements are large.
552
553Implements [BidiMap](#maps), [IteratorWithKey](#iteratorwithkey), [EnumerableWithKey](#enumerablewithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
554
555```go
556package main
557
558import (
559 "github.com/emirpasic/gods/maps/treebidimap"
560 "github.com/emirpasic/gods/utils"
561)
562
563func main() {
564 m := treebidimap.NewWith(utils.IntComparator, utils.StringComparator)
565 m.Put(1, "x") // 1->x
566 m.Put(3, "b") // 1->x, 3->b (ordered)
567 m.Put(1, "a") // 1->a, 3->b (ordered)
568 m.Put(2, "b") // 1->a, 2->b (ordered)
569 _, _ = m.GetKey("a") // 1, true
570 _, _ = m.Get(2) // b, true
571 _, _ = m.Get(3) // nil, false
572 _ = m.Values() // []interface {}{"a", "b"} (ordered)
573 _ = m.Keys() // []interface {}{1, 2} (ordered)
574 m.Remove(1) // 2->b
575 m.Clear() // empty
576 m.Empty() // true
577 m.Size() // 0
578}
579```
580
581### Trees
582
583A tree is a widely used data data structure that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes; thus no cyclic links.
584
585Implements [Container](#containers) interface.
586
587```go
588type Tree interface {
589 containers.Container
590 // Empty() bool
591 // Size() int
592 // Clear()
593 // Values() []interface{}
594}
595```
596
597#### RedBlackTree
598
599A red–black [tree](#trees) is a binary search tree with an extra bit of data per node, its color, which can be either red or black. The extra bit of storage ensures an approximately balanced tree by constraining how nodes are colored from any path from the root to the leaf. Thus, it is a data structure which is a type of self-balancing binary search tree.
600
601The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time. <sub><sup>[Wikipedia](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree)</sup></sub>
602
603Implements [Tree](#trees), [ReverseIteratorWithKey](#reverseiteratorwithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
604
605<p align="center"><img src="http://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png" width="400px" height="200px" /></p>
606
607```go
608package main
609
610import (
611 "fmt"
612 rbt "github.com/emirpasic/gods/trees/redblacktree"
613)
614
615func main() {
616 tree := rbt.NewWithIntComparator() // empty (keys are of type int)
617
618 tree.Put(1, "x") // 1->x
619 tree.Put(2, "b") // 1->x, 2->b (in order)
620 tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
621 tree.Put(3, "c") // 1->a, 2->b, 3->c (in order)
622 tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order)
623 tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
624 tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)
625
626 fmt.Println(tree)
627 //
628 // RedBlackTree
629 // │ ┌── 6
630 // │ ┌── 5
631 // │ ┌── 4
632 // │ │ └── 3
633 // └── 2
634 // └── 1
635
636 _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f"} (in order)
637 _ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6} (in order)
638
639 tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order)
640 fmt.Println(tree)
641 //
642 // RedBlackTree
643 // │ ┌── 6
644 // │ ┌── 5
645 // └── 4
646 // │ ┌── 3
647 // └── 1
648
649 tree.Clear() // empty
650 tree.Empty() // true
651 tree.Size() // 0
652
653 // Other:
654 tree.Left() // gets the left-most (min) node
655 tree.Right() // get the right-most (max) node
656 tree.Floor(1) // get the floor node
657 tree.Ceiling(1) // get the ceiling node
658}
659```
660
661Extending the red-black tree's functionality has been demonstrated in the following [example](https://github.com/emirpasic/gods/blob/master/examples/redblacktreeextended/redblacktreeextended.go).
662
663#### AVLTree
664
665AVL [tree](#trees) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
666
667AVL trees are often compared with red–black trees because both support the same set of operations and take O(log n) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. <sub><sup>[Wikipedia](https://en.wikipedia.org/wiki/AVL_tree)</sup></sub>
668
669Implements [Tree](#trees), [ReverseIteratorWithKey](#reverseiteratorwithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
670
671<p align="center"><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/AVL-tree-wBalance_K.svg/262px-AVL-tree-wBalance_K.svg.png" width="300px" height="180px" /><br/><sub>AVL tree with balance factors (green)</sub></p>
672
673```go
674package main
675
676import (
677 "fmt"
678 avl "github.com/emirpasic/gods/trees/avltree"
679)
680
681func main() {
682 tree := avl.NewWithIntComparator() // empty(keys are of type int)
683
684 tree.Put(1, "x") // 1->x
685 tree.Put(2, "b") // 1->x, 2->b (in order)
686 tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
687 tree.Put(3, "c") // 1->a, 2->b, 3->c (in order)
688 tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order)
689 tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
690 tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)
691
692 fmt.Println(tree)
693 //
694 // AVLTree
695 // │ ┌── 6
696 // │ ┌── 5
697 // └── 4
698 // │ ┌── 3
699 // └── 2
700 // └── 1
701
702
703 _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f"} (in order)
704 _ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6} (in order)
705
706 tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order)
707 fmt.Println(tree)
708 //
709 // AVLTree
710 // │ ┌── 6
711 // │ ┌── 5
712 // └── 4
713 // └── 3
714 // └── 1
715
716 tree.Clear() // empty
717 tree.Empty() // true
718 tree.Size() // 0
719}
720```
721
722#### BTree
723
724B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.
725
726According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:
727
728- Every node has at most m children.
729- Every non-leaf node (except root) has at least ⌈m/2⌉ children.
730- The root has at least two children if it is not a leaf node.
731- A non-leaf node with k children contains k−1 keys.
732- All leaves appear in the same level
733
734Each internal node’s keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2.<sub><sup>[Wikipedia](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree)</sub></sup>
735
736Implements [Tree](#trees), [ReverseIteratorWithKey](#reverseiteratorwithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
737
738<p align="center"><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/6/65/B-tree.svg/831px-B-tree.svg.png" width="400px" height="111px" /></p>
739
740```go
741package main
742
743import (
744 "fmt"
745 "github.com/emirpasic/gods/trees/btree"
746)
747
748func main() {
749 tree := btree.NewWithIntComparator(3) // empty (keys are of type int)
750
751 tree.Put(1, "x") // 1->x
752 tree.Put(2, "b") // 1->x, 2->b (in order)
753 tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
754 tree.Put(3, "c") // 1->a, 2->b, 3->c (in order)
755 tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order)
756 tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
757 tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)
758 tree.Put(7, "g") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f, 7->g (in order)
759
760 fmt.Println(tree)
761 // BTree
762 // 1
763 // 2
764 // 3
765 // 4
766 // 5
767 // 6
768 // 7
769
770 _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f", "g"} (in order)
771 _ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6, 7} (in order)
772
773 tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order)
774 fmt.Println(tree)
775 // BTree
776 // 1
777 // 3
778 // 4
779 // 5
780 // 6
781
782 tree.Clear() // empty
783 tree.Empty() // true
784 tree.Size() // 0
785
786 // Other:
787 tree.Height() // gets the height of the tree
788 tree.Left() // gets the left-most (min) node
789 tree.LeftKey() // get the left-most (min) node's key
790 tree.LeftValue() // get the left-most (min) node's value
791 tree.Right() // get the right-most (max) node
792 tree.RightKey() // get the right-most (max) node's key
793 tree.RightValue() // get the right-most (max) node's value
794}
795```
796
797#### BinaryHeap
798
799A binary heap is a [tree](#trees) created using a binary tree. It can be seen as a binary tree with two additional constraints:
800
801- Shape property:
802
803 A binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
804- Heap property:
805
806 All nodes are either greater than or equal to or less than or equal to each of its children, according to a comparison predicate defined for the heap. <sub><sup>[Wikipedia](http://en.wikipedia.org/wiki/Binary_heap)</sub></sup>
807
808Implements [Tree](#trees), [ReverseIteratorWithIndex](#reverseiteratorwithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
809
810<p align="center"><img src="http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/501px-Max-Heap.svg.png" width="300px" height="200px" /></p>
811
812```go
813package main
814
815import (
816 "github.com/emirpasic/gods/trees/binaryheap"
817 "github.com/emirpasic/gods/utils"
818)
819
820func main() {
821
822 // Min-heap
823 heap := binaryheap.NewWithIntComparator() // empty (min-heap)
824 heap.Push(2) // 2
825 heap.Push(3) // 2, 3
826 heap.Push(1) // 1, 3, 2
827 heap.Values() // 1, 3, 2
828 _, _ = heap.Peek() // 1,true
829 _, _ = heap.Pop() // 1, true
830 _, _ = heap.Pop() // 2, true
831 _, _ = heap.Pop() // 3, true
832 _, _ = heap.Pop() // nil, false (nothing to pop)
833 heap.Push(1) // 1
834 heap.Clear() // empty
835 heap.Empty() // true
836 heap.Size() // 0
837
838 // Max-heap
839 inverseIntComparator := func(a, b interface{}) int {
840 return -utils.IntComparator(a, b)
841 }
842 heap = binaryheap.NewWith(inverseIntComparator) // empty (min-heap)
843 heap.Push(2, 3, 1) // 3, 2, 1 (bulk optimized)
844 heap.Values() // 3, 2, 1
845}
846```
847
848## Functions
849
850Various helper functions used throughout the library.
851
852### Comparator
853
854Some data structures (e.g. TreeMap, TreeSet) require a comparator function to automatically keep their elements sorted upon insertion. This comparator is necessary during the initalization.
855
856Comparator is defined as:
857
858Return values (int):
859
860```go
861negative , if a < b
862zero , if a == b
863positive , if a > b
864```
865
866Comparator signature:
867
868```go
869type Comparator func(a, b interface{}) int
870```
871
872All common comparators for builtin types are included in the library:
873
874```go
875func StringComparator(a, b interface{}) int
876
877func IntComparator(a, b interface{}) int
878
879func Int8Comparator(a, b interface{}) int
880
881func Int16Comparator(a, b interface{}) int
882
883func Int32Comparator(a, b interface{}) int
884
885func Int64Comparator(a, b interface{}) int
886
887func UIntComparator(a, b interface{}) int
888
889func UInt8Comparator(a, b interface{}) int
890
891func UInt16Comparator(a, b interface{}) int
892
893func UInt32Comparator(a, b interface{}) int
894
895func UInt64Comparator(a, b interface{}) int
896
897func Float32Comparator(a, b interface{}) int
898
899func Float64Comparator(a, b interface{}) int
900
901func ByteComparator(a, b interface{}) int
902
903func RuneComparator(a, b interface{}) int
904
905func TimeComparator(a, b interface{}) int
906```
907
908Writing custom comparators is easy:
909
910```go
911package main
912
913import (
914 "fmt"
915 "github.com/emirpasic/gods/sets/treeset"
916)
917
918type User struct {
919 id int
920 name string
921}
922
923// Custom comparator (sort by IDs)
924func byID(a, b interface{}) int {
925
926 // Type assertion, program will panic if this is not respected
927 c1 := a.(User)
928 c2 := b.(User)
929
930 switch {
931 case c1.id > c2.id:
932 return 1
933 case c1.id < c2.id:
934 return -1
935 default:
936 return 0
937 }
938}
939
940func main() {
941 set := treeset.NewWith(byID)
942
943 set.Add(User{2, "Second"})
944 set.Add(User{3, "Third"})
945 set.Add(User{1, "First"})
946 set.Add(User{4, "Fourth"})
947
948 fmt.Println(set) // {1 First}, {2 Second}, {3 Third}, {4 Fourth}
949}
950```
951
952### Iterator
953
954All ordered containers have stateful iterators. Typically an iterator is obtained by _Iterator()_ function of an ordered container. Once obtained, iterator's _Next()_ function moves the iterator to the next element and returns true if there was a next element. If there was an element, then element's can be obtained by iterator's _Value()_ function. Depending on the ordering type, it's position can be obtained by iterator's _Index()_ or _Key()_ functions. Some containers even provide reversible iterators, essentially the same, but provide another extra _Prev()_ function that moves the iterator to the previous element and returns true if there was a previous element.
955
956Note: it is unsafe to remove elements from container while iterating.
957
958#### IteratorWithIndex
959
960An [iterator](#iterator) whose elements are referenced by an index.
961
962Typical usage:
963```go
964it := list.Iterator()
965for it.Next() {
966 index, value := it.Index(), it.Value()
967 ...
968}
969```
970
971Other usages:
972```go
973if it.First() {
974 firstIndex, firstValue := it.Index(), it.Value()
975 ...
976}
977```
978
979```go
980for it.Begin(); it.Next(); {
981 ...
982}
983```
984
985#### IteratorWithKey
986
987An [iterator](#iterator) whose elements are referenced by a key.
988
989Typical usage:
990```go
991it := tree.Iterator()
992for it.Next() {
993 key, value := it.Key(), it.Value()
994 ...
995}
996```
997
998Other usages:
999```go
1000if it.First() {
1001 firstKey, firstValue := it.Key(), it.Value()
1002 ...
1003}
1004```
1005
1006```go
1007for it.Begin(); it.Next(); {
1008 ...
1009}
1010```
1011
1012#### ReverseIteratorWithIndex
1013
1014An [iterator](#iterator) whose elements are referenced by an index. Provides all functions as [IteratorWithIndex](#iteratorwithindex), but can also be used for reverse iteration.
1015
1016Typical usage of iteration in reverse:
1017```go
1018it := list.Iterator()
1019for it.End(); it.Prev(); {
1020 index, value := it.Index(), it.Value()
1021 ...
1022}
1023```
1024
1025Other usages:
1026```go
1027if it.Last() {
1028 lastIndex, lastValue := it.Index(), it.Value()
1029 ...
1030}
1031```
1032
1033#### ReverseIteratorWithKey
1034
1035An [iterator](#iterator) whose elements are referenced by a key. Provides all functions as [IteratorWithKey](#iteratorwithkey), but can also be used for reverse iteration.
1036
1037Typical usage of iteration in reverse:
1038```go
1039it := tree.Iterator()
1040for it.End(); it.Prev(); {
1041 key, value := it.Key(), it.Value()
1042 ...
1043}
1044```
1045
1046Other usages:
1047```go
1048if it.Last() {
1049 lastKey, lastValue := it.Key(), it.Value()
1050 ...
1051}
1052```
1053
1054### Enumerable
1055
1056Enumerable functions for ordered containers that implement [EnumerableWithIndex](#enumerablewithindex) or [EnumerableWithKey](#enumerablewithkey) interfaces.
1057
1058#### EnumerableWithIndex
1059
1060[Enumerable](#enumerable) functions for ordered containers whose values can be fetched by an index.
1061
1062**Each**
1063
1064Calls the given function once for each element, passing that element's index and value.
1065
1066```go
1067Each(func(index int, value interface{}))
1068```
1069
1070**Map**
1071
1072Invokes the given function once for each element and returns a container containing the values returned by the given function.
1073
1074```go
1075Map(func(index int, value interface{}) interface{}) Container
1076```
1077
1078**Select**
1079
1080Returns a new container containing all elements for which the given function returns a true value.
1081
1082```go
1083Select(func(index int, value interface{}) bool) Container
1084```
1085
1086**Any**
1087
1088Passes each element of the container to the given function and returns true if the function ever returns true for any element.
1089
1090```go
1091Any(func(index int, value interface{}) bool) bool
1092```
1093
1094**All**
1095
1096Passes each element of the container to the given function and returns true if the function returns true for all elements.
1097
1098```go
1099All(func(index int, value interface{}) bool) bool
1100```
1101
1102**Find**
1103
1104Passes each element of the container to the given function and returns the first (index,value) for which the function is true or -1,nil otherwise if no element matches the criteria.
1105
1106```go
1107Find(func(index int, value interface{}) bool) (int, interface{})}
1108```
1109
1110**Example:**
1111
1112```go
1113package main
1114
1115import (
1116 "fmt"
1117 "github.com/emirpasic/gods/sets/treeset"
1118)
1119
1120func printSet(txt string, set *treeset.Set) {
1121 fmt.Print(txt, "[ ")
1122 set.Each(func(index int, value interface{}) {
1123 fmt.Print(value, " ")
1124 })
1125 fmt.Println("]")
1126}
1127
1128func main() {
1129 set := treeset.NewWithIntComparator()
1130 set.Add(2, 3, 4, 2, 5, 6, 7, 8)
1131 printSet("Initial", set) // [ 2 3 4 5 6 7 8 ]
1132
1133 even := set.Select(func(index int, value interface{}) bool {
1134 return value.(int)%2 == 0
1135 })
1136 printSet("Even numbers", even) // [ 2 4 6 8 ]
1137
1138 foundIndex, foundValue := set.Find(func(index int, value interface{}) bool {
1139 return value.(int)%2 == 0 && value.(int)%3 == 0
1140 })
1141 if foundIndex != -1 {
1142 fmt.Println("Number divisible by 2 and 3 found is", foundValue, "at index", foundIndex) // value: 6, index: 4
1143 }
1144
1145 square := set.Map(func(index int, value interface{}) interface{} {
1146 return value.(int) * value.(int)
1147 })
1148 printSet("Numbers squared", square) // [ 4 9 16 25 36 49 64 ]
1149
1150 bigger := set.Any(func(index int, value interface{}) bool {
1151 return value.(int) > 5
1152 })
1153 fmt.Println("Set contains a number bigger than 5 is ", bigger) // true
1154
1155 positive := set.All(func(index int, value interface{}) bool {
1156 return value.(int) > 0
1157 })
1158 fmt.Println("All numbers are positive is", positive) // true
1159
1160 evenNumbersSquared := set.Select(func(index int, value interface{}) bool {
1161 return value.(int)%2 == 0
1162 }).Map(func(index int, value interface{}) interface{} {
1163 return value.(int) * value.(int)
1164 })
1165 printSet("Chaining", evenNumbersSquared) // [ 4 16 36 64 ]
1166}
1167```
1168
1169#### EnumerableWithKey
1170
1171Enumerable functions for ordered containers whose values whose elements are key/value pairs.
1172
1173**Each**
1174
1175Calls the given function once for each element, passing that element's key and value.
1176
1177```go
1178Each(func(key interface{}, value interface{}))
1179```
1180
1181**Map**
1182
1183Invokes the given function once for each element and returns a container containing the values returned by the given function as key/value pairs.
1184
1185```go
1186Map(func(key interface{}, value interface{}) (interface{}, interface{})) Container
1187```
1188
1189**Select**
1190
1191Returns a new container containing all elements for which the given function returns a true value.
1192
1193```go
1194Select(func(key interface{}, value interface{}) bool) Container
1195```
1196
1197**Any**
1198
1199Passes each element of the container to the given function and returns true if the function ever returns true for any element.
1200
1201```go
1202Any(func(key interface{}, value interface{}) bool) bool
1203```
1204
1205**All**
1206
1207Passes each element of the container to the given function and returns true if the function returns true for all elements.
1208
1209```go
1210All(func(key interface{}, value interface{}) bool) bool
1211```
1212
1213**Find**
1214
1215Passes each element of the container to the given function and returns the first (key,value) for which the function is true or nil,nil otherwise if no element matches the criteria.
1216
1217```go
1218Find(func(key interface{}, value interface{}) bool) (interface{}, interface{})
1219```
1220
1221**Example:**
1222
1223```go
1224package main
1225
1226import (
1227 "fmt"
1228 "github.com/emirpasic/gods/maps/treemap"
1229)
1230
1231func printMap(txt string, m *treemap.Map) {
1232 fmt.Print(txt, " { ")
1233 m.Each(func(key interface{}, value interface{}) {
1234 fmt.Print(key, ":", value, " ")
1235 })
1236 fmt.Println("}")
1237}
1238
1239func main() {
1240 m := treemap.NewWithStringComparator()
1241 m.Put("g", 7)
1242 m.Put("f", 6)
1243 m.Put("e", 5)
1244 m.Put("d", 4)
1245 m.Put("c", 3)
1246 m.Put("b", 2)
1247 m.Put("a", 1)
1248 printMap("Initial", m) // { a:1 b:2 c:3 d:4 e:5 f:6 g:7 }
1249
1250 even := m.Select(func(key interface{}, value interface{}) bool {
1251 return value.(int) % 2 == 0
1252 })
1253 printMap("Elements with even values", even) // { b:2 d:4 f:6 }
1254
1255 foundKey, foundValue := m.Find(func(key interface{}, value interface{}) bool {
1256 return value.(int) % 2 == 0 && value.(int) % 3 == 0
1257 })
1258 if foundKey != nil {
1259 fmt.Println("Element with value divisible by 2 and 3 found is", foundValue, "with key", foundKey) // value: 6, index: 4
1260 }
1261
1262 square := m.Map(func(key interface{}, value interface{}) (interface{}, interface{}) {
1263 return key.(string) + key.(string), value.(int) * value.(int)
1264 })
1265 printMap("Elements' values squared and letters duplicated", square) // { aa:1 bb:4 cc:9 dd:16 ee:25 ff:36 gg:49 }
1266
1267 bigger := m.Any(func(key interface{}, value interface{}) bool {
1268 return value.(int) > 5
1269 })
1270 fmt.Println("Map contains element whose value is bigger than 5 is", bigger) // true
1271
1272 positive := m.All(func(key interface{}, value interface{}) bool {
1273 return value.(int) > 0
1274 })
1275 fmt.Println("All map's elements have positive values is", positive) // true
1276
1277 evenNumbersSquared := m.Select(func(key interface{}, value interface{}) bool {
1278 return value.(int) % 2 == 0
1279 }).Map(func(key interface{}, value interface{}) (interface{}, interface{}) {
1280 return key, value.(int) * value.(int)
1281 })
1282 printMap("Chaining", evenNumbersSquared) // { b:4 d:16 f:36 }
1283}
1284```
1285
1286### Serialization
1287
1288All data structures can be serialized (marshalled) and deserialized (unmarshalled). Currently only JSON support is available.
1289
1290#### JSONSerializer
1291
1292Outputs the container into its JSON representation.
1293
1294Typical usage for key-value structures:
1295```go
1296package main
1297
1298import (
1299 "fmt"
1300 "github.com/emirpasic/gods/maps/hashmap"
1301)
1302
1303func main() {
1304 m := hashmap.New()
1305 m.Put("a", "1")
1306 m.Put("b", "2")
1307 m.Put("c", "3")
1308
1309 json, err := m.ToJSON()
1310 if err != nil {
1311 fmt.Println(err)
1312 }
1313 fmt.Println(string(json)) // {"a":"1","b":"2","c":"3"}
1314```
1315
1316Typical usage for value-only structures:
1317```go
1318package main
1319
1320import (
1321 "fmt"
1322 "github.com/emirpasic/gods/lists/arraylist"
1323)
1324
1325func main() {
1326 list := arraylist.New()
1327 list.Add("a", "b", "c")
1328
1329 json, err := list.ToJSON()
1330 if err != nil {
1331 fmt.Println(err)
1332 }
1333 fmt.Println(string(json)) // ["a","b","c"]
1334}
1335```
1336
1337#### JSONDeserializer
1338
1339Populates the container with elements from the input JSON representation.
1340
1341Typical usage for key-value structures:
1342```go
1343package main
1344
1345import (
1346 "fmt"
1347 "github.com/emirpasic/gods/maps/hashmap"
1348)
1349
1350func main() {
1351 hm := hashmap.New()
1352
1353 json := []byte(`{"a":"1","b":"2"}`)
1354 err := hm.FromJSON(json)
1355 if err != nil {
1356 fmt.Println(err)
1357 }
1358 fmt.Println(hm) // HashMap map[b:2 a:1]
1359}
1360```
1361
1362Typical usage for value-only structures:
1363```go
1364package main
1365
1366import (
1367 "fmt"
1368 "github.com/emirpasic/gods/lists/arraylist"
1369)
1370
1371func main() {
1372 list := arraylist.New()
1373
1374 json := []byte(`["a","b"]`)
1375 err := list.FromJSON(json)
1376 if err != nil {
1377 fmt.Println(err)
1378 }
1379 fmt.Println(list) // ArrayList ["a","b"]
1380}
1381```
1382
1383### Sort
1384
1385Sort is a general purpose sort function.
1386
1387Lists have an in-place _Sort()_ function and all containers can return their sorted elements via _containers.GetSortedValues()_ function.
1388
1389Internally these all use the _utils.Sort()_ method:
1390
1391```go
1392package main
1393
1394import "github.com/emirpasic/gods/utils"
1395
1396func main() {
1397 strings := []interface{}{} // []
1398 strings = append(strings, "d") // ["d"]
1399 strings = append(strings, "a") // ["d","a"]
1400 strings = append(strings, "b") // ["d","a",b"
1401 strings = append(strings, "c") // ["d","a",b","c"]
1402 utils.Sort(strings, utils.StringComparator) // ["a","b","c","d"]
1403}
1404```
1405
1406### Container
1407
1408Container specific operations:
1409
1410```go
1411// Returns sorted container''s elements with respect to the passed comparator.
1412// Does not effect the ordering of elements within the container.
1413func GetSortedValues(container Container, comparator utils.Comparator) []interface{}
1414```
1415
1416Usage:
1417
1418```go
1419package main
1420
1421import (
1422 "github.com/emirpasic/gods/lists/arraylist"
1423 "github.com/emirpasic/gods/utils"
1424)
1425
1426func main() {
1427 list := arraylist.New()
1428 list.Add(2, 1, 3)
1429 values := GetSortedValues(container, utils.StringComparator) // [1, 2, 3]
1430}
1431```
1432
1433## Appendix
1434
1435### Motivation
1436
1437Collections and data structures found in other languages: Java Collections, C++ Standard Template Library (STL) containers, Qt Containers, Ruby Enumerable etc.
1438
1439### Goals
1440
1441**Fast algorithms**:
1442
1443 - Based on decades of knowledge and experiences of other libraries mentioned above.
1444
1445**Memory efficient algorithms**:
1446
1447 - Avoiding to consume memory by using optimal algorithms and data structures for the given set of problems, e.g. red-black tree in case of TreeMap to avoid keeping redundant sorted array of keys in memory.
1448
1449**Easy to use library**:
1450
1451 - Well-structured library with minimalistic set of atomic operations from which more complex operations can be crafted.
1452
1453**Stable library**:
1454
1455 - Only additions are permitted keeping the library backward compatible.
1456
1457**Solid documentation and examples**:
1458
1459 - Learning by example.
1460
1461**Production ready**:
1462
1463 - Used in production.
1464
1465**No dependencies**:
1466
1467 - No external imports.
1468
1469There is often a tug of war between speed and memory when crafting algorithms. We choose to optimize for speed in most cases within reasonable limits on memory consumption.
1470
1471Thread safety is not a concern of this project, this should be handled at a higher level.
1472
1473### Testing and Benchmarking
1474
1475This takes a while, so test within sub-packages:
1476
1477`go test -run=NO_TEST -bench . -benchmem -benchtime 1s ./...`
1478
1479<p align="center"><img src="https://cloud.githubusercontent.com/assets/3115942/16892979/5e698d46-4b27-11e6-864b-cb2b865327b6.png" /></p>
1480
1481### Contributing
1482
1483Biggest contribution towards this library is to use it and give us feedback for further improvements and additions.
1484
1485For direct contributions, _pull request_ into master branch or ask to become a contributor.
1486
1487Coding style:
1488
1489```shell
1490# Install tooling and set path:
1491go get github.com/golang/lint/golint
1492go get github.com/fzipp/gocyclo
1493go get github.com/kisielk/errcheck
1494export PATH=$PATH:$GOPATH/bin
1495
1496# Fix errors and warnings:
1497go fmt ./... && gofmt -s -w . && go vet ./... && go get ./... && go test ./... && golint ./... && gocyclo -avg -over 15 . && errcheck ./...
1498```
1499
1500### License
1501
1502This library is distributed under the BSD-style license found in the [LICENSE](https://github.com/emirpasic/gods/blob/master/LICENSE) file.
1503
1504### Sponsors
1505
1506## <a href="https://www.browserstack.com/?ref=gods"><img src="http://www.hajdarevic.net/browserstack.svg" alt="BrowserStack" width="250"/></a>
1507[BrowserStack](https://www.browserstack.com/?ref=webhook) is a cloud-based cross-browser testing tool that enables developers to test their websites across various browsers on different operating systems and mobile devices, without requiring users to install virtual machines, devices or emulators.
1508