genlib

README

genlib

An efficient and easy to use generic collection library based on Go 1.18+.In some degree,it likes c++ STL or java.util.collection

Some containers and algorithms adapt or borrow from other good implementations.

Feature

collection

• associative
  • b+ tree
  • b tree
  • hashmap
  • concurrencymap
  • redblacktree
  • skiplist
  • tire
• sequence
  • slicelist(warrper slice,add operators)
  • linkedlist
  • signlelist
  • deque
  • ringqueue
  • arraystack
  • lockfreequeue
  • bitmap
  • bloom fliter

b+ tree ,b tree,hashmap,concurrencymap,redblacktree,skiplist have have implemented Map[K,V] and Set[T] interfaces.

slicelist,linkedlist,singlelinkedlist have have implemented List[T] interfaces,these container support sort and parallel sort(timesort now,pdqsort in the future).

In addition ,some queues and stacks container also have implemented Queue[T] and Stack[T].

These interface defined in collection/collection.go,In this way ,eliminate differences in the underlying implementation of the same type of container.

iterator

In this way eliminate differences between containers in some dergee

every containers which implements Map[K,V],Set[T],List[T],have unifrom iterator interface.

the base design of iterator inspired by C++, there are two kinds:

• follow is simple code for view,real define please check iterator/iterator.go

type Forward[T] interface{
        SetValue(T)
        GetValue() T
        IsValid() bool
        CompValue(T) bool
        Comp(base Base[T]) bool
        Move(int)
        Next()
        CloneForward() Forward[T]
}

type Bidirectional[T] interface{
        SetValue(T)
        GetValue() T
        IsValid() bool
        CompValue(T) bool
        Comp(base Base[T]) bool
        Move(int)
        Next()
        Prev()
        CloneBidirectional() Bidirectional[T]
}

A enhance decorator for enhance the abality of iterator inspired by Java,it has been used in the package parallel for simple parallel task famework and will be used in a new struct that function like java.util.stream ,define as follow:

type Enhance[T any] interface {
	Forward[T]
	Idx() int
	Remain() int
	Clone() Enhance[T]
	BinaryTruncate() Enhance[T]
	Truncate(n int) Enhance[T]
}

algorithm

define and usage like C++STL now there are some function as follow ,in the future probably add some new:

• Count
• Countif
• Find
• FindIf
• ForEach
• Equal
• EqualWithValue
• Fill
• FillN
• Reverse
• ReverseCopy
• SwapRange
• Unique
• UniqueCopy
• Partition
• Remove
• RemoveCopy
• RemoveIf
• RemoveCopyIf
• ReplaceIf
• ReplaceCopyIf

simple parallel task famework

There are two modes:

• ProduceConsumer mode
• ForkJoin mode

example:

• ProduceConsumer model (file:parallel/parallel_test.go)

There's only one required function,so better that define a callback function,the other function can be use by option mode.

package parallel_test

import (
	"testing"
	"time"

	"github.com/edmundshelby/genlib/algorithm"
	"github.com/edmundshelby/genlib/collections/sequence/slicelist"
	"github.com/edmundshelby/genlib/iterator"
	"github.com/edmundshelby/genlib/parallel"
	"github.com/edmundshelby/genlib/util"
)

func countHandler(iter iterator.Enhance[int]) (int, error) {
	return algorithm.CountIf[int](iter, func(n int) bool {
		// simulation the long-running operator
		time.Sleep(time.Second)
		return n%3 == 0
	}), nil
}

func resultHandler(old, new int) int {
	return old + new
}

func TestParllel(t *testing.T) {
	l := slicelist.NewWithSlice(util.Range(1, 101))
	t1 := time.Now()
    // default 4 goroutines
	res, err := parallel.New(l.EnhanceIter(), countHandler,
		parallel.WithParaTaskReduce[int](resultHandler)).Run()
	t2 := time.Now()
	if err != nil {
		t.Logf(err.Error())
	}
	// for-loop will cost time:100s
	// parallel task cost time:25s
	t.Log(res, t2.Sub(t1))
}

• ForkJoin mode

There are fewer optional functions in this mode,so define a interface seems good.

package parallel_test

import (
	"math/rand"
	"testing"
	"time"

	"github.com/edmundshelby/genlib/algorithm/timsort"
	"github.com/edmundshelby/genlib/constrains"
	"github.com/edmundshelby/genlib/parallel"
)


type simpleSort struct{}

func (f *simpleSort) Work(arr []int) ([]int, error) {
	timsort.SortBuiltinType(arr)
	return arr, nil
}

func (f *simpleSort) WorkCondition(goroutineNum int, arr []int) bool {
	return goroutineNum == 1 || len(arr) < 1024
}

func (f *simpleSort) Fork(arr []int) (left []int, right []int) {
	mid := len(arr) >> 1
	return arr[:mid], arr[mid:]
}

func (f *simpleSort) Join(r1, r2 []int) []int {
	return merge(r1, r2)
}

// parallel sort
func TestForkJoin(t *testing.T) {
    // some function be omitted
	a := getTestArrBySize(400000)
	a, err := parallel.NewForkJoin[[]int, []int](a, &simpleSort{}).Run()
	if err != nil {
		t.Logf(err)
	} else {
		t.Log("res", check(a), len(a))
	}
}

The existing problems

• Documentation,testing and usage examples are sparse.It will be gradually improved in the future.
• In current golang generic grammer,define a new type in the method is infeasible,so some idea can't be implemented
• At this time I finished in my spare time, there may still be more bugs