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