zyedidia/generic

A collection of generic data structures written in Go.

generic's Issues

Add FIFO Queue

Hi @zyedidia, I'd like to contribute a simple FIFO queue.

Using doubly-linked list nodes defined in list package it should be quick to add a simple First In First Out (FIFO) queue.

What are your thoughts?

functional operations support

Is there a plan to support iterator and common functional operations such as map reduce filter scan fold...

are these structures concurrent safe?

a quick look at the code does not find locking used

Add Unrolled Linked List

Hey @zyedidia, I was thinking of contributing an unrolled linked list implementation.
https://en.wikipedia.org/wiki/Unrolled_linked_list

I am implementing one for another project but thought your repo is probably a good home for it. Let me know if you would like me to work on it and send a PR.

Thanks,
Anand

Trie Remove implementation is inefficient

The implementation of (*Trie).Remove causes the trie to become steadily less efficient as more keys are deleted.

By inserting a tombstone instead of recursively deleting unused nodes, many redundant nodes may remain in place. This increases the the worst-case time for a search miss from logarithmic to linear.

For example, imagine our trie contains only the key "APPLE". We call, t.Remove("APPLE"), which replaces the value at the final "E" character with a tombstone. If we now search for "APPLES", we must check the nodes "A", "P", "P", "L" and "E", before finding that "APPLES" is not in the trie, since none of these nodes were deleted when "APPLE" was removed.

What should happen in this scenario is that we delete "APPLE", causing all of its nodes to be recursively deleted from the trie. Now when we search for "APPLES", we immediately miss when looking up the letter "A".

Please correct me if there's a use case for the tombstone that I've misunderstood. Otherwise I'm happy to open a PR to fix this.

Add Persistent Rope

Hello @zyedidia, I was thinking of contributing a persistent rope to the project.

Does it fit in to the project? There is already a rope, but adding immutable methods to it would cause undefined behavior if you used them with the mutable ones.

Thank you for your time!

Support for sorting elements in descending order in AVL tree

avl.New[int, string](g.Less[int])

We should be able to use a custom comparator for sorting elements but currently that is not supported

This can be accomplished by adding the following func in the generic.go file

func Greater[T constraints.Ordered](a, b T) bool {
	return a > b
}

Trie implementation is incompatible with non-ASCII characters

The current trie implementation fails for Unicode characters greater than 1 byte in size. This is because it indexes string keys directly rather than first converting strings to rune slices, wherein each rune represents a whole Unicode character.

This occurs in both the get and put methods.

If you agree this is a problem, I'm happy to open a PR.

bugfix: you should always check the parameter x1, x2 value of array2d.RowSpan(x1, x2, y int) []T method.

In array2d.RowSpan(x1, x2, y int) []T method, you should alway check the parameter value of x1 ,x2. it will panic if x2 less than x1.
The solution like below:

ulist package is missing a README.md

• Generate the readme for the package
• Update the root to include the newly added ulist data structure

Opt-in to hacktoberfest

I'd like to contribute to this repository as part of Hacktoberfest.
In order for the Pull Requests to count toward my Hacktoberfest contributions, it is necessary for the maintainer to add hacktoberfest as a repository topic.
Can you do that?
https://hacktoberfest.com/participation/#maintainers

Trie is broken

func TestKeys(t *testing.T) {
	tr := trie.New[int]()
	tr.Put("topic1", 1)
	tr.Put("topic2", 2)
	assert.Equal(t, []string{"topic1", "topic2"}, tr.Keys())
}

The result is

--- FAIL: TestKeys (0.00s)
    trie_test.go:68: 
                Error Trace:    trie_test.go:68
                Error:          Not equal: 
                                expected: []string{"topic1", "topic2"}
                                actual  : []string{"topic1", "topi2"}
                            
                                Diff:
                                --- Expected
                                +++ Actual
                                @@ -2,3 +2,3 @@
                                  (string) (len=6) "topic1",
                                - (string) (len=6) "topic2"
                                + (string) (len=5) "topi2"
                                 }
                Test:           TestKeys
FAIL
exit status 1
FAIL    github.com/zhulik/go-eventbus/trie      0.004s

Gomarkdoc does not support go 1.18

Method receivers with type parameters are rendered as BADRECV in the generated documentation. There are also some other problems with links.

Feature Request - Generic Algorithms

Any Generic Types library needs an Algorithmic Generics library.

I propose adding in AbstractDataTypes(ADT) as a Type Parameter with internal (K,V) types and then accept an Algorithm Type Parameter which can successfully call on ADT iterators.

This concept is simply an extension of C++ generics and corollaries can be found I believe in the STL library.

package "constraints" has been removed since go 1.18 rc1

running into this problem

go get -u github.com/zyedidia/generic
github.com/zyedidia/generic imports
	constraints: package constraints is not in GOROOT (/usr/local/go/src/constraints)

I confirmed the package is not in the src path.

Then I found the constraints will be removed in 1.18
see golang/go#50792

The generic List implementation leaks

I reported this downstream (I assume they've attributed your code appropriately?), and was referred here:

fufuok/utils#1

More features for `mapset`

Hello,

We have our own implementation of sets in our codebase (which is not relying on generics), and we would like to switch to a generics aproach for this.

The mapset package looks great but we can't use this as is without adding more features.
Here are some methods that we use regularly and that we would need.

// returns items of the set in a slice
func (s Set[K]) Items() []K

// creates a new set from a slice
func FromSlice[K]([]K) Set[K]

func (s Set[K]) Copy() Set[K]

// set with all items that are in both s and other
func (s Set[K]) Intersection(other Set[K]) Set[K]

// set with all items that are in either s or other
func (s Set[K]) Union(other Set[K]) Set[K]

// all items that are in s but not in other
func (s Set[K]) Substraction(other Set[K]) Set[K]

// are the sets equal
func (s Set[K]) Equals(other Set[K]) bool

// and maybe this one
// returns true if all items of other are included in s
func (s Set[K]) IsSuperSet(other Set[K]) bool

If you think that we should integrate those methods, I can take care of creating some PRs for this.

Cheers

Improving/Measure performance of hashmap

There exists different algorithm to handle collisions for the linear probing strategy. One interesting an practicable way is the Robin Hood hashing.

good illustration:
https://programming.guide/robin-hood-hashing.html

c++ implementation:
https://github.com/Tessil/robin-map/blob/master/include/tsl/robin_hash.h

I created a pull request as a first draft: #41

What do you think about such performance issues? It is still an open task to measure it. What do you think about to create a performance measure tooling like: https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html in golang? Or do you know good tools?

Add support for converting a HashSet to an Array or a Slice

I think this will be a very handful feature and such a method is really common and is provided by other languages such as Java or Python for example. Let me know if you need any help with the implementation

Btree Each() need exit

Btree Each function needs to set the exit, otherwise it can't exit manually, it has to force the loop to finish.

Like this, Exit the loop when the callback fn returns true.
func (t *Tree[K, V]) Each(fn func(key K, val V) bool)

prope is not included in release 1.21.1

Attempting to run

go get github.com/zyedidia/generic/prope

Results in the following error:

go: module github.com/zyedidia/generic@upgrade found (v1.2.1), but does not contain package github.com/zyedidia/generic/prope

I can retrieve the entire package with

go get github.com/zyedidia/generic

But when I try to use propfe with
package main

import (
"github.com/zyedidia/generic/prope"
)

func main() {
data := "=ℇ∞∏"
runes := []rune(data)
r := prope.Newrune
r.Insert(1, []rune{32})
}

I get the error message

main.go:7:2: no required module provides package github.com/zyedidia/generic/prope; to add it:
go get github.com/zyedidia/generic/prope

If I download the 1.21.1 release directly from GitHub I can see that the distribution archive does not contain the `prope` package. 
 

that queue's Dequeue and Peek methods can occur panic is unacceptable

make it return double values maybe better

also can make stack's Peek and Pop methods return double values