Algorithms and data structures.CLRS study

# algorithms
[![Go Report Card](https://goreportcard.com/badge/github.com/shady831213/algorithms)](https://goreportcard.com/report/github.com/shady831213/algorithms)[![Build Status](https://travis-ci.org/shady831213/algorithms.svg?branch=master)](https://travis-ci.org/shady831213/algorithms)[![Maintainability](https://api.codeclimate.com/v1/badges/87b7c7f1222dfb1db63e/maintainability)](https://codeclimate.com/github/shady831213/algorithms/maintainability)[![Test Coverage](https://api.codeclimate.com/v1/badges/87b7c7f1222dfb1db63e/test_coverage)](https://codeclimate.com/github/shady831213/algorithms/test_coverage)
<a href="https://996.icu"><img src="https://img.shields.io/badge/link-996.icu-red.svg"></a>

CLRS study. Codes are written with golang.

----------------

go version: 1.11

----------------

  
- [Heap](https://github.com/shady831213/algorithms/tree/master/heap)
  - [BinaryHeap on array](https://github.com/shady831213/algorithms/blob/master/heap/arrayHeap.go)
  - [BinaryHeap on linkedlist](https://github.com/shady831213/algorithms/blob/master/heap/linkedHeap.go)
  - [LeftistHeap](https://github.com/shady831213/algorithms/blob/master/heap/leftistHeap.go)
  - [FibonacciHeap](https://github.com/shady831213/algorithms/blob/master/heap/fibHeap.go)
  
- [Tree](https://github.com/shady831213/algorithms/tree/master/tree)
  - [binaryTree](https://github.com/shady831213/algorithms/tree/master/tree/binaryTree)
    - [BST](https://github.com/shady831213/algorithms/blob/master/tree/binaryTree/binarySearchTree.go)
    - [RedBlackTree](https://github.com/shady831213/algorithms/blob/master/tree/binaryTree/rbTree.go)
  - [B-Tree](https://github.com/shady831213/algorithms/tree/master/tree/bTree)
  - [RS-vEB-Tree](https://github.com/shady831213/algorithms/tree/master/tree/vEBTree)(Support single key multi value.Lazy hashtable is used to instead of array to reduce space complexity.Including Go Mixin design pattern)
  - [Disjoint-Set-Tree](https://github.com/shady831213/algorithms/tree/master/tree/disjointSetTree)
  
- [Graph](https://github.com/shady831213/algorithms/tree/master/graph) (including linkedMap, iterator)
  - [graph](https://github.com/shady831213/algorithms/blob/master/graph/graph.go)
  - [BFS](https://github.com/shady831213/algorithms/blob/master/graph/bfs.go)
  - [DFS](https://github.com/shady831213/algorithms/blob/master/graph/dfs.go)(use stack)
  - [StronglyConnectedComponents](https://github.com/shady831213/algorithms/blob/master/graph/stronglyConnectedComp.go)
  - [BioConnectedComponents](https://github.com/shady831213/algorithms/blob/master/graph/bioConnectedComp.go)(vertex bcc & edge bcc, use stack)  
  - [eulerCircuit](https://github.com/shady831213/algorithms/blob/master/graph/eulerCircuit.go)  
  - [mst](https://github.com/shady831213/algorithms/blob/master/graph/mst.go)(including Kruskal([disjointSet](https://github.com/shady831213/algorithms/tree/master/tree/disjointSetTree)) , Prim([fibonacci heap](https://github.com/shady831213/algorithms/blob/master/heap/fibHeap.go)), secondaryMst, mst reduce for Prim, linear time bottleneck spanning tree)
  - [Single-Source Shortest Path](https://github.com/shady831213/algorithms/blob/master/graph/sssp.go) (including bellmanFord, SPFA, Dijkstra, Gabow )
  - [All-Pairs Shortest Path](https://github.com/shady831213/algorithms/blob/master/graph/apsp.go) (including FloydWarshall, Johnson)
  - [Max Flow](https://github.com/shady831213/algorithms/blob/master/graph/flowGraph.go) (including flowGraph , preFlowGraph and allowedGraph data structure, Edmondes Karp, Push Relabel, Relabel to Front, Bipartite Graph Max Match and Hopcraft-Karp)
  
- [HashMap](https://github.com/shady831213/algorithms/tree/master/hashMap)(Support UpScale and DownScale)
  - [OpenAddressHashMap](https://github.com/shady831213/algorithms/blob/master/hashMap/openHashMap.go)
  - [LinkedListHashMap](https://github.com/shady831213/algorithms/blob/master/hashMap/chainedHashMap.go)
  
- [DynamicProgramming](https://github.com/shady831213/algorithms/tree/master/dp) (Including OOP pattern of golang)
  - [Double adjustable Euclidean traveling salesman](https://github.com/shady831213/algorithms/blob/master/dp/bitonicTSP.go)
  - [Pretty Print](https://github.com/shady831213/algorithms/blob/master/dp/prettyPrint.go)
  - [Levenshtein Distance](https://github.com/shady831213/algorithms/blob/master/dp/levenshteinDistance.go)
  - [Chess Game](https://github.com/shady831213/algorithms/blob/master/dp/chessGame.go)
  
- [GreedyAlgorithm](https://github.com/shady831213/algorithms/tree/master/greedy)
  - [Minimum average end time scheduling](https://github.com/shady831213/algorithms/blob/master/greedy/minAvgCompletedTimeSch.go)
  

- [Sort](https://github.com/shady831213/algorithms/tree/master/sort)
  - [CountingSort](https://github.com/shady831213/algorithms/blob/master/sort/countingSort.go)
  - [HeapSort](https://github.com/shady831213/algorithms/blob/master/sort/heapSort.go)
  - [InsertSort](https://github.com/shady831213/algorithms/blob/master/sort/insertionSort.go)
  - [MergeSort](https://github.com/shady831213/algorithms/blob/master/sort/mergeSort.go)
  - [QuickSort](https://github.com/shady831213/algorithms/blob/master/sort/quickSort.go)


algorithms

Collection of useful, performant, and thread-safe data structures

go-datastructures
=================

Go-datastructures is a collection of useful, performant, and threadsafe Go
datastructures.

### NOTE: only tested with Go 1.3+.

#### Augmented Tree

Interval tree for collision in n-dimensional ranges.  Implemented via a
red-black augmented tree.  Extra dimensions are handled in simultaneous
inserts/queries to save space although this may result in suboptimal time
complexity.  Intersection determined using bit arrays.  In a single dimension,
inserts, deletes, and queries should be in O(log n) time.

#### Bitarray

Bitarray used to detect existence without having to resort to hashing with
hashmaps.  Requires entities have a uint64 unique identifier.  Two
implementations exist, regular and sparse.  Sparse saves a great deal of space
but insertions are O(log n).  There are some useful functions on the BitArray
interface to detect intersection between two bitarrays. This package also
includes bitmaps of length 32 and 64 that provide increased speed and O(1) for
all operations by storing the bitmaps in unsigned integers rather than arrays.

#### Futures

A helpful tool to send a "broadcast" message to listeners.  Channels have the
issue that once one listener takes a message from a channel the other listeners
aren't notified.  There were many cases when I wanted to notify many listeners
of a single event and this package helps.

#### Queue

Package contains both a normal and priority queue.  Both implementations never
block on send and grow as much as necessary.  Both also only return errors if
you attempt to push to a disposed queue and will not panic like sending a
message on a closed channel.  The priority queue also allows you to place items
in priority order inside the queue.  If you give a useful hint to the regular
queue, it is actually faster than a channel.  The priority queue is somewhat
slow currently and targeted for an update to a Fibonacci heap.

Also included in the queue package is a MPMC threadsafe ring buffer. This is a
block full/empty queue, but will return a blocked thread if the queue is
disposed while a thread is blocked.  This can be used to synchronize goroutines
and ensure goroutines quit so objects can be GC'd.  Threadsafety is achieved
using only CAS operations making this queue quite fast.  Benchmarks can be found
in that package.

#### Fibonacci Heap

A standard Fibonacci heap providing the usual operations. Can be useful in executing Dijkstra or Prim's algorithms in the theoretically minimal time. Also useful as a general-purpose priority queue. The special thing about Fibonacci heaps versus other heap variants is the cheap decrease-key operation. This heap has a constant complexity for find minimum, insert and merge of two heaps, an amortized constant complexity for decrease key and O(log(n)) complexity for a deletion or dequeue minimum. In practice the constant factors are large, so Fibonacci heaps could be slower than Pairing heaps, depending on usage. Benchmarks - in the project subfolder. The heap has not been designed for thread-safety.

#### Range Tree

Useful to determine if n-dimensional points fall within an n-dimensional range.
Not a typical range tree however, as we are actually using an n-dimensional
sorted list of points as this proved to be simpler and faster than attempting a
traditional range tree while saving space on any dimension greater than one.
Inserts are typical BBST times at O(log n^d) where d is the number of
dimensions.

#### Set
Our Set implementation is very simple, accepts items of type `interface{}` and
includes only a few methods. If your application requires a richer Set
implementation over lists of type `sort.Interface`, see
[xtgo/set](https://github.com/xtgo/set) and
[goware/set](https://github.com/goware/set).

#### Threadsafe
A package that is meant to contain some commonly used items but in a threadsafe
way.  Example: there's a threadsafe error in there as I commonly found myself
wanting to set an error in many threads at the same time (yes, I know, but
channels are slow).

#### AVL Tree

This is an example of a branch copy immutable AVL BBST.  Any operation on a node
makes a copy of that node's branch.  Because of this, this tree is inherently
threadsafe although the writes will likely still need to be serialized.  This
structure is good if your use case is a large number of reads and infrequent
writes as reads will be highly available but writes somewhat slow due to the
copying.  This structure serves as a basis for a large number of functional data
structures.

#### X-Fast Trie

An interesting design that treats integers as words and uses a trie structure to
reduce time complexities by matching prefixes.  This structure is really fast
for finding values or making predecessor/successor types of queries, but also
results in greater than linear space consumption.  The exact time complexities
can be found in that package.

#### Y-Fast Trie

An extension of the X-Fast trie in which an X-Fast trie is combined with some
other ordered data structure to reduce space consumption and improve CRUD types
of operations.  These secondary structures are often BSTs, but our implementation
uses a simple ordered list as I believe this improves cache locality.  We also
use fixed size buckets to aid in parallelization of operations.  Exact time
complexities are in that package.

#### Fast integer hashmap

A datastructure used for checking existence but without knowing the bounds of
your data.  If you have a limited small bounds, the bitarray package might be a
better choice.  This implementation uses a fairly simple hashing algorithm
combined with linear probing and a flat datastructure to provide optimal
performance up to a few million integers (faster than the native Golang
implementation).  Beyond that, the native implementation is faster (I believe
they are using a large -ary B-tree).  In the future, this will be implemented
with a B-tree for scale.

#### Skiplist

An ordered structure that provides amortized logarithmic operations but without
the complication of rotations that are required by BSTs.  In testing, however,
the performance of the skip list is often far worse than the guaranteed log n
time of a BBST.  Tall nodes tend to "cast shadows", especially when large
bitsizes are required as the optimum maximum height for a node is often based on
this.  More detailed performance characteristics are provided in that package.

#### Sort

The sort package implements a multithreaded bucket sort that can be up to 3x
faster than the native Golang sort package.  These buckets are then merged using
a symmetrical merge, similar to the stable sort in the Golang package.  However,
our algorithm is modified so that two sorted lists can be merged by using
symmetrical decomposition.

#### Numerics

Early work on some nonlinear optimization problems.  The initial implementation
allows a simple use case with either linear or nonlinear constraints.  You can
find min/max or target an optimal value.  The package currently employs a
probabilistic global restart system in an attempt to avoid local critical points.
More details can be found in that package.

#### B+ Tree

Initial implementation of a B+ tree.  Delete method still needs added as well as
some performance optimization.  Specific performance characteristics can be
found in that package.  Despite the theoretical superiority of BSTs, the B-tree
often has better all around performance due to cache locality.  The current
implementation is mutable, but the immutable AVL tree can be used to build an
immutable version.  Unfortunately, to make the B-tree generic we require an
interface and the most expensive operation in CPU profiling is the interface
method which in turn calls into runtime.assertI2T.  We need generics.

#### Immutable B Tree
A btree based on two principles, immutability and concurrency. 
Somewhat slow for single value lookups and puts, it is very fast for bulk operations.
A persister can be injected to make this index persistent.

#### Ctrie

A concurrent, lock-free hash array mapped trie with efficient non-blocking
snapshots. For lookups, Ctries have comparable performance to concurrent skip
lists and concurrent hashmaps. One key advantage of Ctries is they are
dynamically allocated. Memory consumption is always proportional to the number
of keys in the Ctrie, while hashmaps typically have to grow and shrink. Lookups,
inserts, and removes are O(logn).

One interesting advantage Ctries have over traditional concurrent data
structures is support for lock-free, linearizable, constant-time snapshots.
Most concurrent data structures do not support snapshots, instead opting for
locks or requiring a quiescent state. This allows Ctries to have O(1) iterator
creation and clear operations and O(logn) size retrieval.

#### Dtrie

A persistent hash trie that dynamically expands or shrinks to provide efficient
memory allocation. Being persistent, the Dtrie is immutable and any modification
yields a new version of the Dtrie rather than changing the original. Bitmapped
nodes allow for O(log32(n)) get, remove, and update operations. Insertions are
O(n) and iteration is O(1).

#### Persistent List

A persistent, immutable linked list. All write operations yield a new, updated
structure which preserve and reuse previous versions. This uses a very
functional, cons-style of list manipulation. Insert, get, remove, and size
operations are O(n) as you would expect.

#### Simple Graph

A mutable, non-persistent undirected graph where parallel edges and self-loops are 
not permitted. Operations to add an edge as well as retrieve the total number of 
vertices/edges are O(1) while the operation to retrieve the vertices adjacent to a
target is O(n). For more details see [wikipedia](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Simple_graph)

### Installation

 1. Install Go 1.3 or higher.
 2. Run `go get github.com/Workiva/go-datastructures/...`

### Updating

When new code is merged to master, you can use

	go get -u github.com/Workiva/go-datastructures/...

To retrieve the latest version of go-datastructures.

### Testing

To run all the unit tests use these commands:

	cd $GOPATH/src/github.com/Workiva/go-datastructures
	go get -t -u ./...
	go test ./...

Once you've done this once, you can simply use this command to run all unit tests:

	go test ./...


### Contributing

Requirements to commit here:

 - Branch off master, PR back to master.
 - `gofmt`'d code.
 - Compliance with [these guidelines](https://code.google.com/p/go-wiki/wiki/CodeReviewComments)
 - Unit test coverage
 - [Good commit messages](http://tbaggery.com/2008/04/19/a-note-about-git-commit-messages.html)


### Maintainers
 - Alexander Campbell <[alexander.campbell@workiva.com](mailto:alexander.campbell@workiva.com)>
 - Dustin Hiatt <[dustin.hiatt@workiva.com](mailto:dustin.hiatt@workiva.com)>
 - Ryan Jackson <[ryan.jackson@workiva.com](mailto:ryan.jackson@workiva.com)>


go-datastructures

Go Data Structures. Containers, Sets, Lists, Stacks, Maps, BidiMaps, Trees, HashSet etc

gods

Data structure and algorithm library for go, designed to provide functions similar to C++ STL

# GoSTL

[![GoDoc](https://godoc.org/github.com/liyue201/gostl?status.svg)](https://godoc.org/github.com/liyue201/gostl)
[![Goreportcard](https://goreportcard.com/badge/github.com/liyue201/gostl)](https://goreportcard.com/report/github.com/liyue201/gostl)
[![Build Status](https://travis-ci.org/liyue201/gostl.svg?branch=master)](https://travis-ci.org/liyue201/gostl)
[![Coverall](https://coveralls.io/repos/github/liyue201/gostl/badge.svg?branch=master)](https://coveralls.io/github/liyue201/gostl)
[![License](https://img.shields.io/badge/license-MIT-brightgreen.svg)](/LICENSE)
[![View examples](https://img.shields.io/badge/learn-examples-brightgreen.svg)](/examples)

English | [简体中文](./README_CN.md)

## Introduction
GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more powerful. Combined with the characteristics of go language, most of the data structures have realized goroutine-safe. When creating objects, you can specify whether to turn it on or not through configuration parameters.


## Function list
- data structure
    - [slice](#slice)
    - [array](#array)
    - [vector](#vector)
    - [list](#list)
    - [deque](#deque)
    - [queue](#queue)
    - [priority_queue](#priority_queue)
    - [stack](#stack)
    - [rbtree(red_black_tree)](#rbtree)
    - [map/multimap](#map)
    - [set/multiset](#set)
    - [bitmap](#bitmap)
    - [bloom_filter](#bloom_filter)
    - [hamt(hash_array_mapped_trie)](#hamt)
    - [ketama](#ketama)
    - [skiplist](#skiplist)
- algorithm
    - [sort(quick_sort)](#sort)
    - [stable_sort(merge_sort)](#sort)
    - [binary_search](#sort)
    - [lower_bound](#sort)
    - [upper_bound](#sort)
    - [next_permutation](#next_permutation)
    - [nth_element](#nth_element)
    - [swap](#algo_op)
    - [reverse](#algo_op)
    - [count/count_if](#algo_op_const)
    - [find/find_if](#algo_op_const)
    - [min_element/max_element](#algo_op_const)
    
 ## Examples

 ### <a name="slice">slice</a>
The slice in this library is a wrapper of go native slice.

 ```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm/sort"
  "github.com/liyue201/gostl/ds/slice"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  a := make([]int, 0)
  a = append(a, 2)
  a = append(a, 1)
  a = append(a, 3)
  fmt.Printf("%v\n", a)

  wa := slice.NewSliceWrapper(a)

  // sort in ascending
  sort.Sort[int](wa.Begin(), wa.End(), comparator.IntComparator)
  fmt.Printf("%v\n", a)

  // sort in descending
  sort.Sort[int](wa.Begin(), wa.End(), comparator.Reverse(comparator.IntComparator))
  fmt.Printf("%v\n", a)
}

 ```
 
### <a name="array">array</a>
Array is a data structure with fixed length once it is created, which supports random access and iterator access.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/array"
)

func main() {
  a := array.New[int](5)
  for i := 0; i < a.Size(); i++ {
    a.Set(i, i+1)
  }
  for i := 0; i < a.Size(); i++ {
    fmt.Printf("%v ", a.At(i))
  }

  fmt.Printf("\n")
  for iter := a.Begin(); iter.IsValid(); iter.Next() {
    fmt.Printf("%v ", iter.Value())
  }
}

```

### <a name="vector">vector</a>
Vector is a kind of data structure whose size can be automatically expanded, which is realized by slice internally. Supports random access and iterator access.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm/sort"
  "github.com/liyue201/gostl/ds/vector"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  v := vector.New[int]()
  v.PushBack(1)
  v.PushBack(2)
  v.PushBack(3)
  for i := 0; i < v.Size(); i++ {
    fmt.Printf("%v ", v.At(i))
  }
  fmt.Printf("\n")

  // sort in descending
  sort.Sort[int](v.Begin(), v.End(), comparator.Reverse(comparator.IntComparator))
  for iter := v.Begin(); iter.IsValid(); iter.Next() {
    fmt.Printf("%v ", iter.Value())
  }
}

```


### <a name="list">list</a>
- simple list  
Simple list is a one directional list, which supports inserting data from the head and tail, and only traversing data from the head.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/list/simplelist"
)

func main() {
  l := simplelist.New[int]()
  l.PushBack(1)
  l.PushFront(2)
  l.PushFront(3)
  l.PushBack(4)
  for n := l.FrontNode(); n != nil; n = n.Next() {
    fmt.Printf("%v ", n.Value)
  }
  fmt.Printf("\n===============\n")
}

```
  
- bidirectional list  
Bidirectional list supports inserting data from the head and tail, and traversing data from the head and tail.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/list/bidlist"
)

func main() {
  l := bidlist.New[int]()
  l.PushBack(1)
  l.PushFront(2)
  l.PushFront(3)
  l.PushBack(4)
  for n := l.FrontNode(); n != nil; n = n.Next() {
    fmt.Printf("%v ", n.Value)
  }
  fmt.Printf("\n")

  for n := l.BackNode(); n != nil; n = n.Prev() {
    fmt.Printf("%v ", n.Value)
  }
}
```

### <a name="deque">deque</a>
Deque supports efficient data insertion from the head and tail, random access and iterator access.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm/sort"
  "github.com/liyue201/gostl/ds/deque"
  "github.com/liyue201/gostl/utils/comparator"
  "math/rand"
)

func main() {
  q := deque.New[int]()
  for i := 0; i < 100; i++ {
    r := rand.Int() % 100
    q.PushBack(r)
    q.PushFront(r)
  }
  fmt.Printf("%v\n", q)

  sort.Sort[int](q.Begin(), q.End(), comparator.IntComparator)
  fmt.Printf("%v\n", q)

  for !q.Empty() {
    r := rand.Int() % q.Size()
    q.EraseAt(r)
  }
  fmt.Printf("%v\n", q)
}

```

### <a name="queue">queue</a>
Queue is a first-in-first-out data structure. The bottom layer uses the deque or list as the container. By default, the deque is used. If you want to use the list, you can use the `queue.WithListContainer()` parameter when creating an object. Goroutine safety is supported.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/queue"
)

func main() {
  q := queue.New[int]()
  for i := 0; i < 5; i++ {
    q.Push(i)
  }
  for !q.Empty() {
    fmt.Printf("%v\n", q.Pop())
  }
}

```

### <a name="priority_queue">priority_queue</a>
Priority Queue is an abstract data type that is similar to a queue, and every element has some priority value associated with it. The priority of the elements in a priority queue determines the order in which elements are served (i.e., the order in which they are removed). If in any case the elements have same priority, they are served as per their ordering in the queue.
```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/priorityqueue"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  q := priorityqueue.New[int](comparator.Reverse(comparator.IntComparator),
    priorityqueue.WithGoroutineSafe())
  q.Push(4)
  q.Push(13)
  q.Push(7)
  q.Push(9)
  q.Push(0)
  q.Push(88)

  for !q.Empty() {
    fmt.Printf("%v\n", q.Pop())
  }
}

```

### <a name="stack">stack</a>
Stack is a kind of last-in-first-out data structure. The bottom layer uses the deque or list as the container. By default, the deque is used. If you want to use the list, you can use the `queue.WithListContainer()` parameter when creating an object.  Goroutine safety is supported.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/stack"
)

func main() {
  s := stack.New[int]()
  s.Push(1)
  s.Push(2)
  s.Push(3)
  for !s.Empty() {
    fmt.Printf("%v\n", s.Pop())
  }
}
```

### <a name="rbtree">rbtree</a>
Red black tree is a balanced binary sort tree, which is used to insert and find data efficiently.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/rbtree"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  tree := rbtree.New[int, string](comparator.IntComparator)
  tree.Insert(1, "aaa")
  tree.Insert(5, "bbb")
  tree.Insert(3, "ccc")
  v, _ := tree.Find(5)
  fmt.Printf("find %v returns %v\n", 5, v)

  tree.Traversal(func(key int, value string) bool {
    fmt.Printf("%v : %v\n", key, value)
    return true
  })
  tree.Delete(tree.FindNode(3))
}

```

### <a name="map">map</a>
The Map bottom layer is implemented by using red black tree, and supports iterative access in key order, which is different from the go native map type (the go native map bottom layer is hash, and does not support iterative access in key order). Goroutine safety is supported.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/map"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  m := treemap.New[string, string](comparator.StringComparator, treemap.WithGoroutineSafe())

  m.Insert("a", "aaa")
  m.Insert("b", "bbb")

  a, _ := m.Get("a")
  b, _ := m.Get("b")
  fmt.Printf("a = %v\n", a)
  fmt.Printf("b = %v\n", b)

  m.Erase("b")
}

```

### <a name="set">set</a>
The Set bottom layer is implemented by red black tree, which supports goroutine safety. Support basic operations of set, such as union, intersection and difference. Goroutine safety is supported.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/set"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  s := set.New[int](comparator.IntComparator, set.WithGoroutineSafe())
  s.Insert(1)
  s.Insert(5)
  s.Insert(3)
  s.Insert(4)
  s.Insert(2)

  s.Erase(4)

  for iter := s.Begin(); iter.IsValid(); iter.Next() {
    fmt.Printf("%v\n", iter.Value())
  }

  fmt.Printf("%v\n", s.Contains(3))
  fmt.Printf("%v\n", s.Contains(10))
}

```

### <a name="bitmap">bitmap</a>
Bitmap is used to quickly mark and find whether a non negative integer is in a set. It takes up less memory than map or array.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/bitmap"
)

func main() {
  bm := bitmap.New(1000)
  bm.Set(6)
  bm.Set(10)

  fmt.Printf("%v\n", bm.IsSet(5))
  fmt.Printf("%v\n", bm.IsSet(6))
  bm.Unset(6)
  fmt.Printf("%v\n", bm.IsSet(6))
}

```
### <a name="bloom_filter">bloom_filter</a>
Boomfilter is used to quickly determine whether the data is in the collection. The bottom layer is implemented with bitmap, which uses less memory than map. The disadvantage is that it does not support deletion and has a certain error rate. Goroutine safety is supported , supports data export and reconstruction through exported data.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/bloomfilter"
)

func main() {
  filter := bloom.New(100, 4, bloom.WithGoroutineSafe())
  filter.Add("hhhh")
  filter.Add("gggg")

  fmt.Printf("%v\n", filter.Contains("aaaa"))
  fmt.Printf("%v\n", filter.Contains("gggg"))
}

```

### <a name="hamt">hamt</a>
Compared with the traditional hash (open address method or linked list method hash), hamt has lower probability of hash conflict and higher space utilization. The time complexity of capacity expansion is low. Goroutine safety is supported.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/hamt"
)

func main() {
  h := hamt.New[string](hamt.WithGoroutineSafe())
  key := []byte("aaaaa")
  val := "bbbbbbbbbbbbb"

  h.Insert(key, val)
  v, _ := h.Get(key)
  fmt.Printf("%v = %v\n", string(key), v)

  h.Erase(key)
  v, _ = h.Get(key)
  fmt.Printf("%v = %v\n", string(key), v)
}

```

### <a name="ketama">ketama</a>
Consistent hash Ketama algorithm, using 64 bit hash function and map storage, has less conflict probability. Goroutine safety is supported.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/ketama"
)

func main() {
  k := ketama.New()
  k.Add("1.2.3.3")
  k.Add("2.4.5.6")
  k.Add("5.5.5.1")

  for i := 0; i < 10; i++ {
    node, _ := k.Get(fmt.Sprintf("%d", i))
    fmt.Printf("%v\n", node)
  }
  k.Remove("2.4.5.6")
}


```
### <a name="skiplist">skiplist</a>
Skiplist is a kind of data structure which can search quickly by exchanging space for time. Goroutine safety is supported.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/skiplist"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  list := skiplist.New[string, string](comparator.StringComparator, skiplist.WithMaxLevel(15))
  list.Insert("aaa", "1111")
  list.Insert("bbb", "2222")
  v1, _ := list.Get("aaa")
  v2, _ := list.Get("bbb")
  fmt.Printf("aaa = %v\n", v1)
  fmt.Printf("bbb = %v\n", v2)

  list.Traversal(func(key, value string) bool {
    fmt.Printf("key:%v value:%v\n", key, value)
    return true
  })

  list.Remove("aaa")
}

```

### <a name="sort">sort</a>
Sort: quick sort algorithm is used internally.  
Stable: stable sorting. Merge sorting is used internally.  
Binarysearch: determine whether an element is in the scope of iterator by binary search.  
Lowerbound: find the first data equal to the element and return the iterator by binary search.  
Upperbound: find the first data larger than the element and return the iterator by binary search.  

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm/sort"
  "github.com/liyue201/gostl/ds/slice"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  a := make([]string, 0)
  a = append(a, "bbbb")
  a = append(a, "ccc")
  a = append(a, "aaaa")
  a = append(a, "bbbb")
  a = append(a, "bb")

  sliceA := slice.NewSliceWrapper(a)

  ////Sort in ascending order
  sort.Sort[string](sliceA.Begin(), sliceA.End(), comparator.OrderedTypeCmp[string])

  sort.Stable[string](sliceA.Begin(), sliceA.End(), comparator.StringComparator)
  fmt.Printf("%v\n", a)

  if sort.BinarySearch[string](sliceA.Begin(), sliceA.End(), "bbbb", comparator.StringComparator) {
    fmt.Printf("BinarySearch: found bbbb\n")
  }

  iter := sort.LowerBound[string](sliceA.Begin(), sliceA.End(), "bbbb", comparator.StringComparator)
  if iter.IsValid() {
    fmt.Printf("LowerBound bbbb: %v\n", iter.Value())
  }
  iter = sort.UpperBound[string](sliceA.Begin(), sliceA.End(), "bbbb", comparator.StringComparator)
  if iter.IsValid() {
    fmt.Printf("UpperBound bbbb: %v\n", iter.Value())
  }
  //Sort in descending order
  sort.Sort[string](sliceA.Begin(), sliceA.End(), comparator.Reverse(comparator.StringComparator))
  //sort.Stable[string](sliceA.Begin(), sliceA.End(), comparator.Reverse(comparator.StringComparator))
  fmt.Printf("%v\n", a)
}

```

### <a name="next_permutation">next_permutation</a>
This function modifies the data in the iterator range to the next sort combination.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm/sort"
  "github.com/liyue201/gostl/ds/slice"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  a := make([]int, 0)
  for i := 1; i <= 3; i++ {
    a = append(a, i)
  }
  wa := slice.NewSliceWrapper(a)
  fmt.Println("NextPermutation")
  for {
    fmt.Printf("%v\n", a)
    if !sort.NextPermutation[int](wa.Begin(), wa.End(), comparator.IntComparator) {
      break
    }
  }
  fmt.Println("PrePermutation")
  for {
    fmt.Printf("%v\n", a)
    if !sort.NextPermutation[int](wa.Begin(), wa.End(), comparator.Reverse(comparator.IntComparator)) {
      break
    }
  }
}

```

### <a name="nth_element">nth_element</a>
Place the nth element in the scope of the iterator in the position of N, and put the element less than or equal to it on the left, and the element greater than or equal to it on the right.

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm/sort"
  "github.com/liyue201/gostl/ds/deque"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  a := deque.New[int]()
  a.PushBack(9)
  a.PushBack(8)
  a.PushBack(7)
  a.PushBack(6)
  a.PushBack(5)
  a.PushBack(4)
  a.PushBack(3)
  a.PushBack(2)
  a.PushBack(1)
  fmt.Printf("%v\n", a)
  sort.NthElement[int](a.Begin(), a.End(), 3, comparator.IntComparator)
  fmt.Printf("%v\n", a.At(3))
  fmt.Printf("%v\n", a)
}
```

### <a name="algo_op"> swap/reverse </a>
- swap: swap the values of two iterators
- reverse: Reverse values in the range of two iterators

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm"
  "github.com/liyue201/gostl/ds/deque"
)

func main() {
  a := deque.New[int]()
  for i := 0; i < 9; i++ {
    a.PushBack(i)
  }
  fmt.Printf("%v\n", a)

  algorithm.Swap[int](a.First(), a.Last())
  fmt.Printf("%v\n", a)

  algorithm.Reverse[int](a.Begin(), a.End())
  fmt.Printf("%v\n", a)
}

```

### <a name="algo_op_const"> count/count_if/find/find_if </a>
- Count : Count the number of elements equal to the specified value in the iterator interval
- CountIf: Count the number of elements that satisfy the function f in the iterator interval
- Find: Find the first element equal to the specified value in the iterator interval and returns its iterator
- FindIf：Find the first element satisfying function f in the iterator interval and return its iterator
- MaxElement : Find the largest element and return its iterator
- MinElement : Find the smallest element and return its iterator
- AnyOf : Returns true if any element satisfies the function f in the iterator interval
- AllOf: Returns true if all elements satisfy the function f in the iterator interval
- NoneOf: Returns true if none of the elements satisfy the function f in the iterator interval

```go
package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm"
  "github.com/liyue201/gostl/ds/deque"
  "github.com/liyue201/gostl/utils/comparator"
  "github.com/liyue201/gostl/utils/iterator"
)

func isEven(iter iterator.ConstIterator[int]) bool {
  return iter.Value()%2 == 0
}

func greaterThan5(iter iterator.ConstIterator[int]) bool {
  return iter.Value() > 5
}

func main() {
  a := deque.New[int]()
  for i := 0; i < 10; i++ {
    a.PushBack(i)
  }
  for i := 0; i < 5; i++ {
    a.PushBack(i)
  }
  fmt.Printf("%v\n", a)

  fmt.Printf("Count 2: %v\n", algorithm.Count[int](a.Begin(), a.End(), 2, comparator.IntComparator))

  fmt.Printf("Count 2: %v\n", algorithm.CountIf[int](a.Begin(), a.End(), isEven))

  iter := algorithm.Find[int](a.Begin(), a.End(), 2, comparator.IntComparator)
  if !iter.Equal(a.End()) {
    fmt.Printf("Fund %v\n", iter.Value())
  }
  iter = algorithm.FindIf[int](a.Begin(), a.End(), greaterThan5)
  if !iter.Equal(a.End()) {
    fmt.Printf("FindIf greaterThan5 : %v\n", iter.Value())
  }
  iter = algorithm.MaxElement[int](a.Begin(), a.End(), comparator.IntComparator)
  if !iter.Equal(a.End()) {
    fmt.Printf("largest value : %v\n", iter.Value())
  }
  iter = algorithm.MinElement[int](a.Begin(), a.End(), comparator.IntComparator)
  if !iter.Equal(a.End()) {
    fmt.Printf("largest value : %v\n", iter.Value())
  }

	fmt.Printf("Any even: %v\n", algorithm.AnyOf[int](a.Begin(), a.End(), isEven))
	fmt.Printf("All even: %v\n", algorithm.AllOf[int](a.Begin(), a.End(), isEven))
	fmt.Printf("None even: %v\n", algorithm.NoneOf[int](a.Begin(), a.End(), isEven))
}


```

## Stargazers over time

[![Stargazers over time](https://starchart.cc/liyue201/gostl.svg)](https://starchart.cc/liyue201/gostl)


The Best Go Libraries For Data Structures and Algorithms - Data Structure and Algorithm Collections (4)

algorithms

go-datastructures

gods

gostl