Split byte streams into chunks, and arrange chunks into trees, with boundaries determined by content, not position

# Hashsplit - content-based splitting of byte streams

[![Go Reference](https://pkg.go.dev/badge/github.com/bobg/hashsplit/v2.svg)](https://pkg.go.dev/github.com/bobg/hashsplit/v2)
[![Go Report Card](https://goreportcard.com/badge/github.com/bobg/hashsplit/v2)](https://goreportcard.com/report/github.com/bobg/hashsplit/v2)
![Tests](https://github.com/bobg/hashsplit/actions/workflows/go.yml/badge.svg)
[![Coverage Status](https://coveralls.io/repos/github/bobg/hashsplit/badge.svg?branch=master)](https://coveralls.io/github/bobg/hashsplit?branch=master)

Hashsplitting is a way of dividing a byte stream into pieces
based on the stream's content rather than on any predetermined chunk size.
As the Splitter reads the stream it maintains a _rolling checksum_ of the last several bytes.
A chunk boundary occurs when the rolling checksum has enough trailing bits set to zero
(where “enough” is a configurable setting that determines the average chunk size).

## Usage

You can split the input from `r`,
an `io.Reader`,
like this:

```go
split, errptr := hashsplit.Split(r)
for chunk := range split {
  // ...handle the contents of r one chunk at a time...
}
if err := *errptr; err != nil {
  // ...handle an error reading from r...
}
```

Chunks can be arranged in a “hashsplit tree” like this:

```go
split, errptr := hashsplit.Split(r)
tree := hashsplit.Tree(split)
root := hashsplit.Root(tree)
if err := *errptr; err != nil {
  // ...handle an error reading from r...
}
```

...and now `root` is the root of a tree whose leaves contain consecutive chunks of the input.

## What is it all about?

Hashsplitting has benefits when it comes to representing multiple,
slightly different versions of the same data.
Consider, for example, the problem of adding EXIF tags to a JPEG image file.
The tags appear near the beginning of the file, and the bulk of the image data follows.
If the file were divided into chunks at (say) 8-kilobyte boundaries,
then adding EXIF data near the beginning would alter every following chunk
(except in the lucky case where the size of the added data is an exact multiple of 8kb).
With hashsplitting, only the chunks in the vicinity of the change are affected.

A sequence of hashsplit chunks can additionally be organized into a tree for even better compaction.
Each chunk has a “level” L determined by the rolling checksum,
and each node in the tree has a level N.
Tree nodes at level 0 collect chunks at level 0,
up to and including a chunk at level L>0;
then a new level-0 node begins.
Tree nodes at level N collect nodes at level N-1
up to and including a chunk at level L>N;
then a new level-N node begins.

Hashsplitting is used to dramatically reduce storage and bandwidth requirements
in projects like
[rsync](https://rsync.samba.org/),
[bup](http://bup.github.io/),
and [perkeep](https://perkeep.org/).
More information,
and a proposed standard,
can be found at
[github.com/hashsplit/hashsplit-spec](https://github.com/hashsplit/hashsplit-spec).


hashsplit

[![Go Report Card](https://goreportcard.com/badge/github.com/mauricegit/skiplist)](https://goreportcard.com/report/github.com/mauricegit/skiplist)
 [![cover.run](https://cover.run/go/github.com/MauriceGit/skiplist.svg?style=flat&tag=golang-1.10)](https://cover.run/go?tag=golang-1.10&repo=github.com%2FMauriceGit%2Fskiplist) 

## Fast Skiplist Implementation

This Go-library implements a very fast and efficient Skiplist that can be used as direct substitute for a balanced tree or linked list.
All basic operations ( `Find`, `Insert` and `Delete`) have approximate runtimes of O(log(n)) that prove real in benchmarks.

For detailed API documentation, see the official docs: [godoc.org/github.com/MauriceGit/skiplist](https://godoc.org/github.com/MauriceGit/skiplist).

This implementation introduces a minimum amount of overhead and is tailored for maximum performance across all operations.
In benchmarks, this skiplist is currently the fastest implementation in Go known to me.
See a thorough benchmark of multiple skiplist implementations at: [github.com/MauriceGit/skiplist-survey](https://github.com/MauriceGit/skiplist-survey).

### `Find`, `Insert`, `Delete` at both ends of the SkipList

*Y-Axis is measured in nanoseconds per operation for all charts*

![Find, Insert, Delete](graphs/allFunctions.png)
All functions, be it `Find`, `Insert` or `Delete` that operate on first or last elements in the skiplist behave in near Constant time, no matter how many
elements are already inserted in the skiplist.

![Random insert, random delete](graphs/randomFunctions.png)
For real-world cases where elements are inserted or removed at random positions in the skiplist, we can clearly see the approximate O(log(n)) behaviour of the
implementation which approximates to a constant value around 1800ns for `Delete` and 2200ns for `Insert`.

### Comparison to other Skiplist implementations

The following graphs are taken from [github.com/MauriceGit/skiplist-survey](https://github.com/MauriceGit/skiplist-survey). Please visit this skiplist survey for
a much more detailed comparison over several benchmarks between different skiplist implementations.

Overall, this implementation is the fastest skiplist for nearly all operations. Especially for real-world applications.

![Random insert](graphs/randomInserts.png)
If we compare random insertions of this skiplist to other implementations, it is clearly the fastest by up to 800ns per insertion for up to 3m elements.

![Random delete](graphs/randomDelete.png)
If we compare random deletions of this skiplist to other implementations, it is clearly the fastest by up to 300ns per deletion for up to 3m elements.

### Usage

```go

import (
    "github.com/MauriceGit/skiplist"
    "fmt"
)

type Element int
// Implement the interface used in skiplist
func (e Element) ExtractKey() float64 {
    return float64(e)
}
func (e Element) String() string {
    return fmt.Sprintf("%03d", e)
}

func main() {
    list := New()

    // Insert some elements
    for i := 0; i < 100; i++ {
        list.Insert(Element(i))
    }

    // Find an element
    if e, ok := list.Find(Element(53)); ok {
        fmt.Println(e)
    }

    // Delete all elements
    for i := 0; i < 100; i++ {
        list.Delete(Element(i))
    }
}

```

### Convenience functions

Other than the classic `Find`, `Insert` and `Delete`, some more convenience functions are implemented that makes this skiplist implementation very easy and straight forward to use
in real applications. All complexity values are approximates, as skiplist can only approximate runtime complexity.

| Function        | Complexity           | Description  |
| ------------- |:-------------:|:-----|
| Find | O(log(n)) | Finds an element in the skiplist |
| FindGreaterOrEqual | O(log(n)) | Finds the first element that is greater or equal the given value in the skiplist |
| Insert | O(log(n)) | Inserts an element into the skiplist |
| Delete | O(log(n)) | Deletes an element from the skiplist |
| GetSmallestNode | O(1) | Returns the smallest element in the skiplist |
| GetLargestNode | O(1) | Returns the largest element in the skiplist |
| Prev | O(1) | Given a skiplist-node, it returns the previous element (Wraps around and allows to linearly iterate the skiplist) |
| Next | O(1) | Given a skiplist-node, it returns the next element (Wraps around and allows to linearly iterate the skiplist) |
| ChangeValue | O(1) | Given a skiplist-node, the actual value can be changed, as long as the key stays the same (Example: Change a structs data) |


skiplist

skiplist
===============

reference from redis [zskiplist](https://github.com/antirez/redis)


Usage
===============

~~~Go

package main

import (
	"fmt"
	"github.com/gansidui/skiplist"
	"log"
)

type User struct {
	score float64
	id    string
}

func (u *User) Less(other interface{}) bool {
	if u.score > other.(*User).score {
		return true
	}
	if u.score == other.(*User).score && len(u.id) > len(other.(*User).id) {
		return true
	}
	return false
}

func main() {
	us := make([]*User, 7)
	us[0] = &User{6.6, "hi"}
	us[1] = &User{4.4, "hello"}
	us[2] = &User{2.2, "world"}
	us[3] = &User{3.3, "go"}
	us[4] = &User{1.1, "skip"}
	us[5] = &User{2.2, "list"}
	us[6] = &User{3.3, "lang"}

	// insert
	sl := skiplist.New()
	for i := 0; i < len(us); i++ {
		sl.Insert(us[i])
	}

	// traverse
	for e := sl.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value.(*User).id, "-->", e.Value.(*User).score)
	}
	fmt.Println()

	// rank
	rank1 := sl.GetRank(&User{2.2, "list"})
	rank2 := sl.GetRank(&User{6.6, "hi"})
	if rank1 != 6 || rank2 != 1 {
		log.Fatal()
	}
	if e := sl.GetElementByRank(2); e.Value.(*User).score != 4.4 || e.Value.(*User).id != "hello" {
		log.Fatal()
	}
}

/* output:

hi --> 6.6
hello --> 4.4
lang --> 3.3
go --> 3.3
world --> 2.2
list --> 2.2
skip --> 1.1

*/

~~~


License
===============

MIT

Topological sort lib,Sorting and pruning of DAG graphs

# graphlib
[![Go Report Card](https://goreportcard.com/badge/github.com/aio-arch/graphlib)](https://goreportcard.com/report/github.com/aio-arch/graphlib)
[![Codecov](https://img.shields.io/codecov/c/github/aio-arch/graphlib?style=flat-square&logo=codecov)](https://app.codecov.io/gh/aio-arch/graphlib)
[![GitHub Actions Workflow Status](https://img.shields.io/github/actions/workflow/status/aio-arch/graphlib/go.yml)](https://github.com/aio-arch/graphlib/actions)
![Minimum Go Version](https://img.shields.io/badge/go-%3E%3D1.18-30dff3?style=flat-square&logo=go)

A Topological sort lib.

Sorting and pruning of DAG graphs.

Ideas borrowed from [python graphlib](https://github.com/python/cpython/blob/3.14/Lib/graphlib.py)

# How to install
```bash
go get -u github.com/aio-arch/graphlib
```

# How to use
```golang
    import "github.com/aio-arch/graphlib"

    // New A graph

	// for string type
	g1 := graphlib.NewGraph[string]()

	// for int type
	g2 := graphlib.NewGraph[int]()

	// for add node and add edge
	g1.AddNode("A1")
	g1.AddNode("B2")
	g1.AddEdge("A1", "B2") // edge: A1 -> B2

	// for add mulit edge,add node inline
	g2.Add(10, 1, 9)    // edge: 1 -> 10 and 9 -> 10
	g2.Add(100, 10, 90) // edge: 10 -> 100 and 90 -> 100

	// topological order
	topo, err := graphlib.TopologicalOrder(g1)
	if err != nil {
		fmt.Println(err.Error())
	}
	fmt.Printf("Topological Order:%v\n", topo)

	// topological prune
	g3, err := graphlib.TopologicalPrune(g2, []int{10, 90})
	if err != nil {
		fmt.Println(err.Error())
	}
	_ = g3

```


graphlib

Space-efficient computation of Merkle root hashes and inclusion proofs

# Merkle - Efficient calculation of merkle roots and proofs

[![Go Reference](https://pkg.go.dev/badge/github.com/bobg/merkle/v2.svg)](https://pkg.go.dev/github.com/bobg/merkle/v2)
[![Go Report Card](https://goreportcard.com/badge/github.com/bobg/merkle/v2)](https://goreportcard.com/report/github.com/bobg/merkle)
[![Tests](https://github.com/bobg/merkle/actions/workflows/go.yml/badge.svg)](https://github.com/bobg/merkle/actions/workflows/go.yml)
[![Coverage Status](https://coveralls.io/repos/github/bobg/merkle/badge.svg?branch=master)](https://coveralls.io/github/bobg/merkle?branch=master)
[![Mentioned in Awesome Go](https://awesome.re/mentioned-badge.svg)](https://github.com/avelino/awesome-go)

This is merkle,
a Go package for computing the Merkle root hash of a sequence of byte strings,
or of their hashes.
It can also produce a compact proof that a given string belongs in a Merkle tree with a given root hash.

This implementation does not require holding all of the input in memory while computing a root hash or a proof.
Instead, it is able to operate on a stream of input strings of unbounded length,
holding incremental state that is only logarithmic [O(log N)] in the size of the input.

For more about Merkle trees,
see [the Wikipedia article](https://en.wikipedia.org/wiki/Merkle_tree).

Creating a merkle root hash:

```go
var ch <-chan []byte  // Represents some source of byte strings
tree := merkle.NewTree(sha256.New())
for str := range ch {
  tree.Add(str)
}
fmt.Printf("merkle root hash is %x\n", tree.Root())
```

Creating a merkle proof that `ref` belongs in the tree,
then verifying the proof:

```go
var (
  ch       <-chan []byte  // Represents some source of byte strings
  rootHash []byte         // Represents a previously computed merkle root hash (held by someone wishing to verify that ref is in the tree)
  ref      []byte         // Represents the string to prove is a member of the tree with the given root hash
)
tree := merkle.NewProofTree(sha256.New(), ref)
for str := range ch {
  tree.Add(str)
}
proof := tree.Proof()  // This is a compact object. For verification purposes, tree can now be discarded.

// Verification:
if bytes.Equal(rootHash, proof.Hash(sha256.New(), ref)) {
  fmt.Println("Verified!")
}
```


merkle

Generic key-sorted map using a red-black tree under the hood

TreeMap v2
==========

[![PkgGoDev](https://pkg.go.dev/badge/github.com/igrmk/treemap/v2)](https://pkg.go.dev/github.com/igrmk/treemap/v2)
[![Unlicense](https://img.shields.io/badge/license-Unlicense-brightgreen.svg)](http://unlicense.org/)
[![Build Status](https://api.travis-ci.com/igrmk/treemap.svg?branch=master)](https://app.travis-ci.com/github/igrmk/treemap)
[![Coverage Status](https://coveralls.io/repos/igrmk/treemap/badge.svg?branch=master)](https://coveralls.io/github/igrmk/treemap)
[![GoReportCard](https://goreportcard.com/badge/github.com/igrmk/treemap/v2)](https://goreportcard.com/report/github.com/igrmk/treemap/v2)
[![Mentioned in Awesome Go](https://awesome.re/mentioned-badge.svg)](https://github.com/avelino/awesome-go)

`TreeMap` is a generic key-sorted map using a red-black tree under the hood.
It requires and relies on [Go 1.18](https://tip.golang.org/doc/go1.18) generics feature.
Iterators are designed after C++.

### Usage

```go
package main

import (
	"fmt"

	"github.com/igrmk/treemap/v2"
)

func main() {
	tr := treemap.New[int, string]()
	tr.Set(1, "World")
	tr.Set(0, "Hello")
	for it := tr.Iterator(); it.Valid(); it.Next() {
		fmt.Println(it.Key(), it.Value())
	}
}

// Output:
// 0 Hello
// 1 World
```

### Install

```bash
go get github.com/igrmk/treemap/v2
```

### Complexity

|              Name              |   Time    |
|:------------------------------:|:---------:|
|             `Set`              | O(log*N*) |
|             `Del`              | O(log*N*) |
|             `Get`              | O(log*N*) |
|           `Contains`           | O(log*N*) |
|             `Len`              |   O(1)    |
|            `Clear`             |   O(1)    |
|            `Range`             | O(log*N*) |
|           `Iterator`           |   O(1)    |
|           `Reverse`            | O(log*N*) |
| Iterate through the entire map |  O(*N*)   |

### Memory usage

TreeMap uses O(*N*) memory.

### TreeMap v1

The previous version of this package used [gotemplate](https://github.com/ncw/gotemplate) library to generate a type specific file in your local directory.
Here is the link to this version [treemap v1](https://github.com/igrmk/treemap/tree/v1.0.0).

### Licensing

Copyright &copy; 2022 igrmk.
This work is free. You can redistribute it and/or modify it under the
terms of the Unlicense. See the LICENSE file for more details.

### Thanks to

[![JetBrains](svg/jetbrains.svg)](https://www.jetbrains.com/?from=treemap)


The Best Go Libraries For Data Structures and Algorithms - Trees (6)

hashsplit

skiplist

skiplist

graphlib

merkle

treemap