jonasmuehlmann / datastructures.go Goto Github PK
View Code? Open in Web Editor NEWThe missing generic container library for go, featuring an extensive iterator API.
License: Other
The missing generic container library for go, featuring an extensive iterator API.
License: Other
Implement Pop functions
next *element[T]
}
// TODO: Implement Pop functions
func (list *List[T]) PopBack(n int) { panic("Not implemented") }
func (list *List[T]) PopFront(n int) { panic("Not implemented") }
// New instantiates a new list and adds the passed values, if any, to the list
func New[T any](values ...T) *List[T] {
list := &List[T]{}
if len(values) > 0 {
list.PushBack(values...)
}
return list
}
// Add appends a value (one or more) at the end of the list (same as Append())
func (list *List[T]) PushBack(values ...T) {
for _, value := range values {
newElement := &element[T]{value: value, prev: list.last}
if list.size == 0 {
052c90673567ac54e021fae0f1c0cfeb8f5a2b8b
This can be useful for when looking up the target has a complexity but getting its distance is more complex.
This should probably be done with templates as it can emulate c++ constexpr if for reduced code duplication.
Allow access to underlying map
datastructures.go/maps/hashmap/hashmap.go
Line 24 in 458e2c8
import (
"fmt"
"github.com/emirpasic/gods/maps"
)
// Assert Map implementation.
var _ maps.Map = (*Map)(nil)
// TODO: Allow access to underlying map
// Map holds the elements in go's native map.
type Map struct {
m map[interface{}]interface{}
}
// TODO: Implement NewFromMap() method which only copies map and not items
// New instantiates a hash map.
func New() *Map {
return &Map{m: make(map[interface{}]interface{})}
05d37f2766fbbff7e3a45343aa65f2defa01b399
Rename to DynamicArray
List holds the elements in a slice.
"github.com/emirpasic/gods/utils"
)
// Assert List implementation.
var _ lists.List = (*List)(nil)
// TODO: Try and reimplement methods through iterator
// TODO: Allow access to underlying slice
// TODO: Rename to DynamicArray
// List holds the elements in a slice.
type List struct {
elements []interface{}
size int
5dc394914bb0579ed51d72462e765d615a2d9ae3
Can't this be removed in favor of calls to len(list.elements)?
var _ lists.List[any] = (*List[any])(nil)
// TODO: Try and reimplement methods through iterator
// List holds the elements in a slice.
type List[T any] struct {
elements []T
// TODO: Can't this be removed in favor of calls to len(list.elements)?
size int
}
const (
5fcd0287193dbc2b1fa32adfdcde293122e9dffe
Refactor tests with testify and table tests
import (
"encoding/json"
"strings"
"testing"
"github.com/JonasMuehlmann/datastructures.go/utils"
"github.com/stretchr/testify/assert"
)
// TODO: Refactor tests with testify and table tests
func TestListNew(t *testing.T) {
list1 := New[int]()
if actualValue := list1.IsEmpty(); actualValue != true {
t.Errorf("Got %v expected %v", actualValue, true)
}
list2 := New[string]("a", "b")
if actualValue := list2.Size(); actualValue != 2 {
t.Errorf("Got %v expected %v", actualValue, 2)
}
if actualValue, ok := list2.Get(0); actualValue != "a" || !ok {
t.Errorf("Got %v expected %v", actualValue, "a")
}
if actualValue, ok := list2.Get(1); actualValue != "b" || !ok {
t.Errorf("Got %v expected %v", actualValue, "b")
}
if _, ok := list2.Get(2); ok {
t.Errorf("Got %v expected %v", ok, false)
}
}
func TestListAdd(t *testing.T) {
list := New[string]()
list.Add("a")
list.Add("b", "c")
if actualValue := list.IsEmpty(); actualValue != false {
t.Errorf("Got %v expected %v", actualValue, false)
}
if actualValue := list.Size(); actualValue != 3 {
80825b6d3f0c3ad63d643f250e400dc9d53e7c3f
Implement NewFromSlice() method which only copies slice header and not items
New instantiates a new list and adds the passed values, if any, to the list.
shrinkFactor = float32(0.25) // shrink when size is 25% of capacity (0 means never shrink)
)
// TODO: Implement NewFromSlice() method which only copies slice header and not items
// New instantiates a new list and adds the passed values, if any, to the list.
func New(values ...interface{}) *List {
list := &List{}
if len(values) > 0 {
7a8a41aafa951d39d2e4ab665fd860c8602f29d4
Can we use type parameters in interfaces to embed? This could simplify variant creation like BidirectionalIterator vs OrderedBidirectionalIterator
datastructures.go/ds/iterator.go
Line 9 in 4a06393
package ds
// TODO: Implement Constructors for types, which take iterators to materialize
// TODO: Can we use type parameters in interfaces to embed? This could simplify variant creation like BidirectionalIterator vs OrderedBidirectionalIterator
type BoundsSentinel int
2f426f4f42528a3ddbc832ed02496d9cca0ff046
Should be implement an Equaler interface?
Assert Map implementation
import (
"fmt"
"github.com/JonasMuehlmann/datastructures.go/maps"
"github.com/JonasMuehlmann/datastructures.go/maps/hashmap"
)
// TODO: Should be implement an Equaler interface?
// Assert Map implementation
var _ maps.BidiMap[string, string] = (*Map[string, string])(nil)
// Map holds the elements in two hashmaps.
type Map[TKey comparable, TValue comparable] struct {
forwardMap hashmap.Map[TKey, TValue]
inverseMap hashmap.Map[TValue, TKey]
}
func (m *Map[TKey, TValue]) MergeWith(other *maps.Map[TKey, TValue]) bool {
panic("Not implemented")
}
func (m *Map[TKey, TValue]) MergeWithSafe(other *maps.Map[TKey, TValue], overwriteOriginal bool) {
panic("Not implemented")
}
// New instantiates a bidirectional map.
func New[TKey comparable, TValue comparable]() *Map[TKey, TValue] {
return &Map[TKey, TValue]{*hashmap.New[TKey, TValue](), *hashmap.New[TValue, TKey]()}
}
// Put inserts element into the map.
func (m *Map[TKey, TValue]) Put(key TKey, value TValue) {
if valueByKey, ok := m.forwardMap.Get(key); ok {
m.inverseMap.Remove(valueByKey)
}
fc2e54e1033277cc3984694ccdcb023fd1823b7e
Use template for ReverseOrderedIterator
and OrderedIterator
We can use guru
to document what interface a type (e.g. iterator or container) implements.
Use template for ValueIterator
and ElementIterator
Implement RemoveStable which does a swap and shrink
Remove removes the element at the given index from the list.
return list.elements[index], true
}
// TODO: Implement RemoveStable which does a swap and shrink
// Remove removes the element at the given index from the list.
func (list *List) Remove(index int) {
if !list.withinRange(index) {
return
}
a123cc4ed15a0097814191eb923824aff44eaed1
Compare lists after operations, to require correctnes
package linkedhashset
import (
"testing"
"github.com/JonasMuehlmann/datastructures.go/tests"
"github.com/JonasMuehlmann/datastructures.go/utils"
"github.com/stretchr/testify/assert"
"golang.org/x/exp/maps"
)
func TestRemove(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
newSet *Set[string]
toRemove string
}{
{
name: "empty list",
originalSet: New[string](),
newSet: New[string](),
toRemove: "foo",
},
{
name: "single item",
toRemove: "foo",
originalSet: NewFromSlice[string]([]string{"foo"}),
newSet: New[string](),
},
{
name: "single item, target does not exist",
toRemove: "bar",
originalSet: NewFromSlice[string]([]string{"foo"}),
newSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
toRemove: "bar",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
newSet: NewFromSlice[string]([]string{"foo", "baz"}),
},
}
for _, test := range tests {
test.originalSet.Remove(utils.BasicComparator[string], test.toRemove)
assert.Equalf(t, test.originalSet, test.newSet, test.name)
}
}
func TestAdd(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
newSet *Set[string]
keyToAdd string
valueToAdd int
}{
{
name: "empty list",
originalSet: New[string](),
newSet: NewFromSlice[string]([]string{"foo"}),
keyToAdd: "foo",
},
{
name: "single item",
keyToAdd: "foo",
newSet: NewFromSlice[string]([]string{"foo"}),
originalSet: New[string](),
},
{
name: "single item, overwrite",
keyToAdd: "foo",
originalSet: NewFromSlice[string]([]string{"foo"}),
newSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
keyToAdd: "bar",
originalSet: NewFromSlice[string]([]string{"foo", "baz"}),
newSet: NewFromSlice[string]([]string{"foo", "baz", "bar"}),
},
}
for _, test := range tests {
test.originalSet.Add(test.keyToAdd)
assert.Equalf(t, test.originalSet, test.newSet, test.name)
}
}
func TestGetValues(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
values []string
}{
{
name: "empty list",
originalSet: New[string](),
values: []string{},
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
values: []string{"foo"},
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
values: []string{"foo", "bar", "baz"},
},
}
for _, test := range tests {
values := test.originalSet.GetValues()
assert.ElementsMatchf(t, test.values, values, test.name)
}
}
func TestContains(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
value string
doesContain bool
}{
{
name: "empty list",
originalSet: New[string](),
value: "foo",
doesContain: false,
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
value: "foo",
doesContain: true,
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
value: "foo",
doesContain: true,
},
}
for _, test := range tests {
assert.Equalf(t, test.doesContain, test.originalSet.Contains(test.value), test.name)
}
}
func TestIsEmpty(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
isEmpty bool
}{
{
name: "empty list",
originalSet: New[string](),
isEmpty: true,
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
isEmpty: false,
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
isEmpty: false,
},
}
for _, test := range tests {
isEmpty := test.originalSet.IsEmpty()
assert.Equal(t, test.isEmpty, isEmpty, test.name)
}
}
func TestClear(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
isEmptyBefore bool
isEmptyAfter bool
}{
{
name: "empty list",
originalSet: New[string](),
isEmptyBefore: true,
isEmptyAfter: true,
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
isEmptyBefore: false,
isEmptyAfter: true,
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
isEmptyBefore: false,
isEmptyAfter: true,
},
}
for _, test := range tests {
isEmptyBefore := test.originalSet.IsEmpty()
assert.Equal(t, test.isEmptyBefore, isEmptyBefore, test.name)
test.originalSet.Clear()
isEmptAfter := test.originalSet.IsEmpty()
assert.Equal(t, test.isEmptyAfter, isEmptAfter, test.name)
}
}
func TestNewFromIterator(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
}{
{
name: "empty list",
originalSet: New[string](),
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
},
}
for _, test := range tests {
it := test.originalSet.First(utils.BasicComparator[string])
newSet := NewFromIterator[string](it)
assert.ElementsMatchf(t, test.originalSet.GetValues(), newSet.GetValues(), test.name)
}
}
func TestNewFromIterators(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
}{
{
name: "empty list",
originalSet: New[string](),
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
},
}
for _, test := range tests {
first := test.originalSet.First(utils.BasicComparator[string])
end := test.originalSet.End(utils.BasicComparator[string])
newSet := NewFromIterators[string](first, end)
assert.ElementsMatchf(t, test.originalSet.GetValues(), newSet.GetValues(), test.name)
}
}
func TestMakeIntersectionWith(t *testing.T) {
tests := []struct {
name string
a *Set[string]
b *Set[string]
intersection *Set[string]
}{
{
name: "first empty",
a: New[string](),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "Second empty",
a: New[string]("foo", "bar", "baz"),
b: New[string](),
intersection: New[string](),
},
{
name: "equal",
a: New[string]("foo", "bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "first shorter",
a: New[string]("bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("bar", "baz"),
},
{
name: "second shorter",
a: New[string]("foo", "bar", "baz"),
b: New[string]("bar", "baz"),
intersection: New[string]("bar", "baz"),
},
{
name: "No overlap",
a: New[string]("foo", "bar", "baz"),
b: New[string]("1", "2"),
intersection: New[string](),
},
}
for _, test := range tests {
newSet := test.a.MakeIntersectionWith(test.b)
assert.ElementsMatchf(t, test.intersection.GetValues(), newSet.GetValues(), test.name)
}
}
func TestMakeUnionWith(t *testing.T) {
tests := []struct {
name string
a *Set[string]
b *Set[string]
intersection *Set[string]
}{
{
name: "first empty",
a: New[string](),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "Second empty",
a: New[string]("foo", "bar", "baz"),
b: New[string](),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "equal",
a: New[string]("foo", "bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "first shorter",
a: New[string]("bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "second shorter",
a: New[string]("foo", "bar", "baz"),
b: New[string]("bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "No overlap",
a: New[string]("foo", "bar", "baz"),
b: New[string]("1", "2"),
intersection: New[string]("foo", "bar", "baz", "1", "2"),
},
}
for _, test := range tests {
newSet := test.a.MakeUnionWith(test.b)
assert.ElementsMatchf(t, test.intersection.GetValues(), newSet.GetValues(), test.name)
}
}
func TestMakeDifferenceWith(t *testing.T) {
tests := []struct {
name string
a *Set[string]
b *Set[string]
intersection *Set[string]
}{
{
name: "first empty",
a: New[string](),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "Second empty",
a: New[string]("foo", "bar", "baz"),
b: New[string](),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "equal",
a: New[string]("foo", "bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "first shorter",
a: New[string]("bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "second shorter",
a: New[string]("foo", "bar", "baz"),
b: New[string]("bar", "baz"),
intersection: New[string]("foo"),
},
{
name: "No overlap",
a: New[string]("foo", "bar", "baz"),
b: New[string]("1", "2"),
intersection: New[string]("foo", "bar", "baz"),
},
}
for _, test := range tests {
newSet := test.a.MakeDifferenceWith(test.b)
assert.ElementsMatchf(t, test.intersection.GetValues(), newSet.GetValues(), test.name)
}
}
// TODO: Compare lists after operations, to require correctnes
func BenchmarkLinkedHashSetRemove(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := New[int]()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StartTimer()
for i := 0; i < n; i++ {
m.Remove(utils.BasicComparator[int], i)
}
b.StopTimer()
},
},
{
name: "Raw",
f: func(n int, name string) {
m := make(map[int]struct{})
for i := 0; i < n; i++ {
m[i] = struct{}{}
}
b.StartTimer()
for i := 0; i < n; i++ {
delete(m, i)
}
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
func BenchmarkLinkedHashSetAdd(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := New[int]()
b.StartTimer()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StopTimer()
},
},
{
name: "Raw",
f: func(n int, name string) {
m := make(map[int]struct{})
b.StartTimer()
for i := 0; i < n; i++ {
m[i] = struct{}{}
}
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
func BenchmarkLinkedHashSetGetValues(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := New[int]()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StartTimer()
_ = m.GetValues()
b.StopTimer()
},
},
{
name: "golang.org_x_exp",
f: func(n int, name string) {
m := New[int]()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StartTimer()
_ = maps.Keys(m.table)
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
5d96af45ccc5bd75ef73bd6d0d381ad506fa5516
Compare lists after operations, to require correctnes
}
}
// TODO: Compare lists after operations, to require correctnes
func BenchmarkHashMapRemove(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := New[int, string]()
for i := 0; i < n; i++ {
m.Put(i, "foo")
c2ba0325afdb95fbc0f129f9b9e092e89904e4cb
Compare lists after operations, to require correctnes
func BenchmarkHashMapRemove(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := NewWithint, string
for i := 0; i < n; i++ {
m.Put(i, "foo")
}
b.StartTimer()
for i := 0; i < n; i++ {
m.Remove(utils.BasicComparator[int], i)
}
b.StopTimer()
},
},
{
name: "Raw",
f: func(n int, name string) {
m := make(map[int]string)
for i := 0; i < n; i++ {
m[i] = "foo"
}
b.StartTimer()
for i := 0; i < n; i++ {
delete(m, i)
}
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := NewWithint, string
for i := 0; i < n; i++ {
m.Put(i, "foo")
}
b.StartTimer()
for i := 0; i < n; i++ {
_, _ = m.Get(i)
}
b.StopTimer()
},
},
{
name: "Raw",
f: func(n int, name string) {
m := make(map[int]string)
for i := 0; i < n; i++ {
m[i] = "foo"
}
b.StartTimer()
for i := 0; i < n; i++ {
_, _ = m[i]
}
b.StopTimer()
},
},
}
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := NewWithint, string
b.StartTimer()
for i := 0; i < n; i++ {
m.Put(i, "foo")
}
b.StopTimer()
},
},
{
name: "Raw",
f: func(n int, name string) {
m := make(map[int]string)
b.StartTimer()
for i := 0; i < n; i++ {
m[i] = "foo"
}
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := NewWithint, string
for i := 0; i < n; i++ {
m.Put(i, "foo")
}
b.StartTimer()
_ = m.GetKeys()
b.StopTimer()
},
},
{
name: "golang.org_x_exp",
f: func(n int, name string) {
m := NewWithint, string
for i := 0; i < n; i++ {
m.Put(i, "foo")
}
b.StartTimer()
_ = maps.Keys(m.)
b.StopTimer()
},
},
}
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := NewWithint, string
for i := 0; i < n; i++ {
m.Put(i, "foo")
}
b.StartTimer()
_ = m.GetValues()
b.StopTimer()
},
},
{
name: "golang.org_x_exp",
f: func(n int, name string) {
m := NewWithint, string
for i := 0; i < n; i++ {
m.Put(i, "foo")
}
b.StartTimer()
_ = maps.Values(m.m)
b.StopTimer()
},
},
}
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
package redblacktree
import (
"testing"
"github.com/JonasMuehlmann/datastructures.go/maps/hashmap"
"github.com/JonasMuehlmann/datastructures.go/utils"
"github.com/stretchr/testify/assert"
)
func TestRemove(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
newMap *Tree[string, int]
toRemove string
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
newMap: NewWith[string, int](utils.BasicComparator[string]),
toRemove: "foo",
},
{
name: "single item",
toRemove: "foo",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
newMap: NewWith[string, int](utils.BasicComparator[string]),
},
{
name: "single item, target does not exist",
toRemove: "bar",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
newMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
},
{
name: "3 items",
toRemove: "bar",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
newMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "baz": 3}),
},
}
for _, test := range tests {
test.originalMap.Remove(test.toRemove)
assert.Equalf(t, test.originalMap.GetValues(), test.newMap.GetValues(), test.name)
}
}
func TestPut(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
newMap *Tree[string, int]
keyToAdd string
valueToAdd int
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
newMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
keyToAdd: "foo",
valueToAdd: 1,
},
{
name: "single item",
keyToAdd: "foo",
valueToAdd: 1,
newMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
originalMap: NewWith[string, int](utils.BasicComparator[string]),
},
{
name: "single item, overwrite",
keyToAdd: "foo",
valueToAdd: 2,
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
newMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 2}),
},
{
name: "3 items",
keyToAdd: "bar",
valueToAdd: 2,
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "baz": 3}),
newMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
},
}
for _, test := range tests {
test.originalMap.Put(test.keyToAdd, test.valueToAdd)
assert.Equalf(t, test.originalMap.GetValues(), test.newMap.GetValues(), test.name)
}
}
func TestGet(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
keyToGet string
value int
found bool
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
keyToGet: "foo",
found: false,
},
{
name: "single item",
keyToGet: "foo",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
value: 1,
found: true,
},
{
name: "single item, target does not exist",
keyToGet: "bar",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
found: false,
},
{
name: "3 items",
keyToGet: "bar",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
value: 2,
found: true,
},
}
for _, test := range tests {
value, found := test.originalMap.Get(test.keyToGet)
assert.Equalf(t, test.value, value, test.name)
assert.Equalf(t, test.found, found, test.name)
}
}
func TestGetNode(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
keyToGet string
value int
found bool
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
keyToGet: "foo",
found: false,
},
{
name: "single item",
keyToGet: "foo",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
value: 1,
found: true,
},
{
name: "single item, target does not exist",
keyToGet: "bar",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
found: false,
},
{
name: "3 items",
keyToGet: "bar",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
value: 2,
found: true,
},
}
for _, test := range tests {
node := test.originalMap.GetNode(test.keyToGet)
assert.Equalf(t, test.found, node != nil, test.name)
if test.found {
assert.Equalf(t, test.value, node.Value, test.name)
}
}
}
func TestRight(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[int, string]
value string
found bool
}{
{
name: "empty list",
originalMap: NewWith[int, string](utils.BasicComparator[int]),
found: false,
},
{
name: "single item",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo"}),
value: "foo",
found: true,
},
{
name: "3 items",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo", 2: "bar", 3: "baz"}),
value: "baz",
found: true,
},
}
for _, test := range tests {
node := test.originalMap.Right()
assert.Equalf(t, test.found, node != nil, test.name)
if test.found {
assert.Equalf(t, test.value, node.Value, test.name)
}
}
}
func TestLeft(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[int, string]
value string
found bool
}{
{
name: "empty list",
originalMap: NewWith[int, string](utils.BasicComparator[int]),
found: false,
},
{
name: "single item",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo"}),
value: "foo",
found: true,
},
{
name: "3 items",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo", 2: "bar", 3: "baz"}),
value: "foo",
found: true,
},
}
for _, test := range tests {
node := test.originalMap.Left()
assert.Equalf(t, test.found, node != nil, test.name)
if test.found {
assert.Equalf(t, test.value, node.Value, test.name)
}
}
}
func TestCeiling(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[int, string]
key int
value string
found bool
}{
{
name: "empty list",
originalMap: NewWith[int, string](utils.BasicComparator[int]),
key: 1,
found: false,
},
{
name: "single item",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo"}),
value: "foo",
found: true,
},
{
name: "3 items",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{0: "foo", 2: "bar", 3: "baz"}),
key: 1,
value: "bar",
found: true,
},
{
name: "3 items, no ceilling",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo", 2: "bar", 3: "baz"}),
key: 4,
found: false,
},
}
for _, test := range tests {
node, found := test.originalMap.Ceiling(test.key)
assert.Equalf(t, test.found, found, test.name)
if test.found {
assert.Equalf(t, test.value, node.Value, test.name)
}
}
}
func TestFloor(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[int, string]
key int
value string
found bool
}{
{
name: "empty list",
originalMap: NewWith[int, string](utils.BasicComparator[int]),
key: 1,
found: false,
},
{
name: "single item",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo"}),
key: 1,
value: "foo",
found: true,
},
{
name: "3 items",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo", 2: "bar", 4: "baz"}),
key: 3,
value: "bar",
found: true,
},
{
name: "3 items, no floor",
originalMap: NewFromMapWith[int, string](utils.BasicComparator[int], map[int]string{1: "foo", 2: "bar", 3: "baz"}),
key: 0,
found: false,
},
}
for _, test := range tests {
node, found := test.originalMap.Floor(test.key)
assert.Equalf(t, test.found, found, test.name)
if test.found {
assert.Equalf(t, test.value, node.Value, test.name)
}
}
}
func TestGetKeys(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
keys []string
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
keys: []string{},
},
{
name: "single item",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
keys: []string{"foo"},
},
{
name: "3 items",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
keys: []string{"foo", "bar", "baz"},
},
}
for _, test := range tests {
keys := test.originalMap.GetKeys()
assert.ElementsMatch(t, test.keys, keys, test.name)
}
}
func TestGetValues(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
values []int
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
values: []int{},
},
{
name: "single item",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
values: []int{1},
},
{
name: "3 items",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
values: []int{1, 2, 3},
},
}
for _, test := range tests {
values := test.originalMap.GetValues()
assert.ElementsMatch(t, test.values, values, test.name)
}
}
func TestIsEmpty(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
isEmpty bool
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
isEmpty: true,
},
{
name: "single item",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
isEmpty: false,
},
{
name: "3 items",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
isEmpty: false,
},
}
for _, test := range tests {
isEmpty := test.originalMap.IsEmpty()
assert.Equal(t, test.isEmpty, isEmpty, test.name)
}
}
func TestClear(t *testing.T) {
tests := []struct {
name string
originalMap *Tree[string, int]
isEmptyBefore bool
isEmptyAfter bool
}{
{
name: "empty list",
originalMap: NewWith[string, int](utils.BasicComparator[string]),
isEmptyBefore: true,
isEmptyAfter: true,
},
{
name: "single item",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1}),
isEmptyBefore: false,
isEmptyAfter: true,
},
{
name: "3 items",
originalMap: NewFromMapWith[string, int](utils.BasicComparator[string], map[string]int{"foo": 1, "bar": 2, "baz": 3}),
isEmptyBefore: false,
isEmptyAfter: true,
},
}
for _, test := range tests {
isEmptyBefore := test.originalMap.IsEmpty()
assert.Equal(t, test.isEmptyBefore, isEmptyBefore, test.name)
test.originalMap.Clear()
isEmptAfter := test.originalMap.IsEmpty()
assert.Equal(t, test.isEmptyAfter, isEmptAfter, test.name)
}
}
func TestNewFromIteratorWith(t *testing.T) {
tests := []struct {
name string
originalMap *hashmap.Map[string, int]
}{
{
name: "empty list",
originalMap: hashmap.New[string, int](),
},
{
name: "single item",
originalMap: hashmap.NewFromMap[string, int](map[string]int{"foo": 1}),
},
{
name: "3 items",
originalMap: hashmap.NewFromMap[string, int](map[string]int{"foo": 1, "bar": 2, "baz": 3}),
},
}
for _, test := range tests {
it := test.originalMap.OrderedFirst(utils.BasicComparator[string])
newMap := NewFromIteratorWith[string, int](utils.BasicComparator[string], it)
assert.ElementsMatchf(t, test.originalMap.GetValues(), newMap.GetValues(), test.name)
}
}
func TestNewFromIteratorsWith(t *testing.T) {
tests := []struct {
name string
originalMap *hashmap.Map[string, int]
}{
{
name: "empty list",
originalMap: hashmap.New[string, int](),
},
{
name: "single item",
originalMap: hashmap.NewFromMap[string, int](map[string]int{"foo": 1}),
},
{
name: "3 items",
originalMap: hashmap.NewFromMap[string, int](map[string]int{"foo": 1, "bar": 2, "baz": 3}),
},
}
for _, test := range tests {
first := test.originalMap.OrderedFirst(utils.BasicComparator[string])
end := test.originalMap.OrderedEnd(utils.BasicComparator[string])
newMap := NewFromIteratorsWith[string, int](utils.BasicComparator[string], first, end)
assert.ElementsMatchf(t, test.originalMap.GetValues(), newMap.GetValues(), test.name)
}
}
// TODO: Compare lists after operations, to require correctnes
// func BenchmarkHashMapRemove(b *testing.B) {
// b.StopTimer()
// variants := []struct {
// name string
// f func(n int, name string)
// }{
// {
// name: "Ours",
// f: func(n int, name string) {
// m := NewWith[int, string](utils.BasicComparator[string])
// for i := 0; i < n; i++ {
// m.Put(i, "foo")
// }
// b.StartTimer()
// for i := 0; i < n; i++ {
// m.Remove(utils.BasicComparator[int], i)
// }
// b.StopTimer()
// },
// },
// {
// name: "Raw",
// f: func(n int, name string) {
// m := make(map[int]string)
// for i := 0; i < n; i++ {
// m[i] = "foo"
// }
// b.StartTimer()
// for i := 0; i < n; i++ {
// delete(m, i)
// }
// b.StopTimer()
// },
// },
// }
// for _, variant := range variants {
// tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
// }
// }
// func BenchmarkHashMapGet(b *testing.B) {
// b.StopTimer()
// variants := []struct {
// name string
// f func(n int, name string)
// }{
// {
// name: "Ours",
// f: func(n int, name string) {
// m := NewWith[int, string](utils.BasicComparator[int])
// for i := 0; i < n; i++ {
// m.Put(i, "foo")
// }
// b.StartTimer()
// for i := 0; i < n; i++ {
// _, _ = m.Get(i)
// }
// b.StopTimer()
// },
// },
// {
// name: "Raw",
// f: func(n int, name string) {
// m := make(map[int]string)
// for i := 0; i < n; i++ {
// m[i] = "foo"
// }
// b.StartTimer()
// for i := 0; i < n; i++ {
// _, _ = m[i]
// }
// b.StopTimer()
// },
// },
// }
// for _, variant := range variants {
// tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
// }
// }
// func BenchmarkHashMapPut(b *testing.B) {
// b.StopTimer()
// variants := []struct {
// name string
// f func(n int, name string)
// }{
// {
// name: "Ours",
// f: func(n int, name string) {
// m := NewWith[int, string](utils.BasicComparator[int])
// b.StartTimer()
// for i := 0; i < n; i++ {
// m.Put(i, "foo")
// }
// b.StopTimer()
// },
// },
// {
// name: "Raw",
// f: func(n int, name string) {
// m := make(map[int]string)
// b.StartTimer()
// for i := 0; i < n; i++ {
// m[i] = "foo"
// }
// b.StopTimer()
// },
// },
// }
// for _, variant := range variants {
// tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
// }
// }
// func BenchmarkHashMapGetKeys(b *testing.B) {
// b.StopTimer()
// variants := []struct {
// name string
// f func(n int, name string)
// }{
// {
// name: "Ours",
// f: func(n int, name string) {
// m := NewWith[int, string](utils.BasicComparator[int])
// for i := 0; i < n; i++ {
// m.Put(i, "foo")
// }
// b.StartTimer()
// _ = m.GetKeys()
// b.StopTimer()
// },
// },
// {
// name: "golang.org_x_exp",
// f: func(n int, name string) {
// m := NewWith[int, string](utils.BasicComparator[int])
// for i := 0; i < n; i++ {
// m.Put(i, "foo")
// }
// b.StartTimer()
// _ = maps.Keys(m.)
// b.StopTimer()
// },
// },
// }
// for _, variant := range variants {
// tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
// }
// }
// func BenchmarkHashMapGetValues(b *testing.B) {
// b.StopTimer()
// variants := []struct {
// name string
// f func(n int, name string)
// }{
// {
// name: "Ours",
// f: func(n int, name string) {
// m := NewWith[int, string](utils.BasicComparator[int])
// for i := 0; i < n; i++ {
// m.Put(i, "foo")
// }
// b.StartTimer()
// _ = m.GetValues()
// b.StopTimer()
// },
// },
// {
// name: "golang.org_x_exp",
// f: func(n int, name string) {
// m := NewWith[int, string](utils.BasicComparator[int])
// for i := 0; i < n; i++ {
// m.Put(i, "foo")
// }
// b.StartTimer()
// _ = maps.Values(m.m)
// b.StopTimer()
// },
// },
// }
// for _, variant := range variants {
// tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
// }
// }
fe1d44c33565230993c76d6ac10a102479a2713d
Compare lists after operations, to require correctnes
package hashset
import (
"testing"
"github.com/JonasMuehlmann/datastructures.go/tests"
"github.com/JonasMuehlmann/datastructures.go/utils"
"github.com/stretchr/testify/assert"
"golang.org/x/exp/maps"
)
func TestRemove(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
newSet *Set[string]
toRemove string
}{
{
name: "empty list",
originalSet: New[string](),
newSet: New[string](),
toRemove: "foo",
},
{
name: "single item",
toRemove: "foo",
originalSet: NewFromSlice[string]([]string{"foo"}),
newSet: New[string](),
},
{
name: "single item, target does not exist",
toRemove: "bar",
originalSet: NewFromSlice[string]([]string{"foo"}),
newSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
toRemove: "bar",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
newSet: NewFromSlice[string]([]string{"foo", "baz"}),
},
}
for _, test := range tests {
test.originalSet.Remove(utils.BasicComparator[string], test.toRemove)
assert.Equalf(t, test.originalSet, test.newSet, test.name)
}
}
func TestAdd(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
newSet *Set[string]
keyToAdd string
valueToAdd int
}{
{
name: "empty list",
originalSet: New[string](),
newSet: NewFromSlice[string]([]string{"foo"}),
keyToAdd: "foo",
},
{
name: "single item",
keyToAdd: "foo",
newSet: NewFromSlice[string]([]string{"foo"}),
originalSet: New[string](),
},
{
name: "single item, overwrite",
keyToAdd: "foo",
originalSet: NewFromSlice[string]([]string{"foo"}),
newSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
keyToAdd: "bar",
originalSet: NewFromSlice[string]([]string{"foo", "baz"}),
newSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
},
}
for _, test := range tests {
test.originalSet.Add(test.keyToAdd)
assert.Equalf(t, test.originalSet, test.newSet, test.name)
}
}
func TestGetValues(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
values []string
}{
{
name: "empty list",
originalSet: New[string](),
values: []string{},
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
values: []string{"foo"},
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
values: []string{"foo", "bar", "baz"},
},
}
for _, test := range tests {
values := test.originalSet.GetValues()
assert.ElementsMatchf(t, test.values, values, test.name)
}
}
func TestContains(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
value string
doesContain bool
}{
{
name: "empty list",
originalSet: New[string](),
value: "foo",
doesContain: false,
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
value: "foo",
doesContain: true,
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
value: "foo",
doesContain: true,
},
}
for _, test := range tests {
assert.Equalf(t, test.doesContain, test.originalSet.Contains(test.value), test.name)
}
}
func TestIsEmpty(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
isEmpty bool
}{
{
name: "empty list",
originalSet: New[string](),
isEmpty: true,
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
isEmpty: false,
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
isEmpty: false,
},
}
for _, test := range tests {
isEmpty := test.originalSet.IsEmpty()
assert.Equal(t, test.isEmpty, isEmpty, test.name)
}
}
func TestClear(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
isEmptyBefore bool
isEmptyAfter bool
}{
{
name: "empty list",
originalSet: New[string](),
isEmptyBefore: true,
isEmptyAfter: true,
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
isEmptyBefore: false,
isEmptyAfter: true,
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
isEmptyBefore: false,
isEmptyAfter: true,
},
}
for _, test := range tests {
isEmptyBefore := test.originalSet.IsEmpty()
assert.Equal(t, test.isEmptyBefore, isEmptyBefore, test.name)
test.originalSet.Clear()
isEmptAfter := test.originalSet.IsEmpty()
assert.Equal(t, test.isEmptyAfter, isEmptAfter, test.name)
}
}
func TestNewFromIterator(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
}{
{
name: "empty list",
originalSet: New[string](),
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
},
}
for _, test := range tests {
it := test.originalSet.OrderedFirst(utils.BasicComparator[string])
newSet := NewFromIterator[string](it)
assert.ElementsMatchf(t, test.originalSet.GetValues(), newSet.GetValues(), test.name)
}
}
func TestNewFromIterators(t *testing.T) {
tests := []struct {
name string
originalSet *Set[string]
}{
{
name: "empty list",
originalSet: New[string](),
},
{
name: "single item",
originalSet: NewFromSlice[string]([]string{"foo"}),
},
{
name: "3 items",
originalSet: NewFromSlice[string]([]string{"foo", "bar", "baz"}),
},
}
for _, test := range tests {
first := test.originalSet.OrderedFirst(utils.BasicComparator[string])
end := test.originalSet.OrderedEnd(utils.BasicComparator[string])
newSet := NewFromIterators[string](first, end)
assert.ElementsMatchf(t, test.originalSet.GetValues(), newSet.GetValues(), test.name)
}
}
func TestMakeIntersectionWith(t *testing.T) {
tests := []struct {
name string
a *Set[string]
b *Set[string]
intersection *Set[string]
}{
{
name: "first empty",
a: New[string](),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "Second empty",
a: New[string]("foo", "bar", "baz"),
b: New[string](),
intersection: New[string](),
},
{
name: "equal",
a: New[string]("foo", "bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "first shorter",
a: New[string]("bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("bar", "baz"),
},
{
name: "second shorter",
a: New[string]("foo", "bar", "baz"),
b: New[string]("bar", "baz"),
intersection: New[string]("bar", "baz"),
},
{
name: "No overlap",
a: New[string]("foo", "bar", "baz"),
b: New[string]("1", "2"),
intersection: New[string](),
},
}
for _, test := range tests {
newSet := test.a.MakeIntersectionWith(test.b)
assert.ElementsMatchf(t, test.intersection.GetValues(), newSet.GetValues(), test.name)
}
}
func TestMakeUnionWith(t *testing.T) {
tests := []struct {
name string
a *Set[string]
b *Set[string]
intersection *Set[string]
}{
{
name: "first empty",
a: New[string](),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "Second empty",
a: New[string]("foo", "bar", "baz"),
b: New[string](),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "equal",
a: New[string]("foo", "bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "first shorter",
a: New[string]("bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "second shorter",
a: New[string]("foo", "bar", "baz"),
b: New[string]("bar", "baz"),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "No overlap",
a: New[string]("foo", "bar", "baz"),
b: New[string]("1", "2"),
intersection: New[string]("foo", "bar", "baz", "1", "2"),
},
}
for _, test := range tests {
newSet := test.a.MakeUnionWith(test.b)
assert.ElementsMatchf(t, test.intersection.GetValues(), newSet.GetValues(), test.name)
}
}
func TestMakeDifferenceWith(t *testing.T) {
tests := []struct {
name string
a *Set[string]
b *Set[string]
intersection *Set[string]
}{
{
name: "first empty",
a: New[string](),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "Second empty",
a: New[string]("foo", "bar", "baz"),
b: New[string](),
intersection: New[string]("foo", "bar", "baz"),
},
{
name: "equal",
a: New[string]("foo", "bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "first shorter",
a: New[string]("bar", "baz"),
b: New[string]("foo", "bar", "baz"),
intersection: New[string](),
},
{
name: "second shorter",
a: New[string]("foo", "bar", "baz"),
b: New[string]("bar", "baz"),
intersection: New[string]("foo"),
},
{
name: "No overlap",
a: New[string]("foo", "bar", "baz"),
b: New[string]("1", "2"),
intersection: New[string]("foo", "bar", "baz"),
},
}
for _, test := range tests {
newSet := test.a.MakeDifferenceWith(test.b)
assert.ElementsMatchf(t, test.intersection.GetValues(), newSet.GetValues(), test.name)
}
}
// TODO: Compare lists after operations, to require correctnes
func BenchmarkHashSetRemove(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := New[int]()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StartTimer()
for i := 0; i < n; i++ {
m.Remove(utils.BasicComparator[int], i)
}
b.StopTimer()
},
},
{
name: "Raw",
f: func(n int, name string) {
m := make(map[int]struct{})
for i := 0; i < n; i++ {
m[i] = struct{}{}
}
b.StartTimer()
for i := 0; i < n; i++ {
delete(m, i)
}
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
func BenchmarkHashSetAdd(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := New[int]()
b.StartTimer()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StopTimer()
},
},
{
name: "Raw",
f: func(n int, name string) {
m := make(map[int]struct{})
b.StartTimer()
for i := 0; i < n; i++ {
m[i] = struct{}{}
}
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
func BenchmarkHashSetGetValues(b *testing.B) {
b.StopTimer()
variants := []struct {
name string
f func(n int, name string)
}{
{
name: "Ours",
f: func(n int, name string) {
m := New[int]()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StartTimer()
_ = m.GetValues()
b.StopTimer()
},
},
{
name: "golang.org_x_exp",
f: func(n int, name string) {
m := New[int]()
for i := 0; i < n; i++ {
m.Add(i)
}
b.StartTimer()
_ = maps.Keys(m.items)
b.StopTimer()
},
},
}
for _, variant := range variants {
tests.RunBenchmarkWithDefualtInputSizes(b, variant.name, variant.f)
}
}
4ceb4a6b256b7b03c799eab76831bf8353d9c6f7
Try and reimplement methods through iterator
"github.com/emirpasic/gods/utils"
)
// Assert List implementation.
var _ lists.List = (*List)(nil)
// TODO: Try and reimplement methods through iterator
// TODO: Allow access to underlying slice
// TODO: Rename to DynamicArray
// List holds the elements in a slice.
type List struct {
elements []interface{}
size int
0d4357a1daa8870c979484b809902f66004fa070
Add methods:
Contains()
IndexOf()
Since it does not alter the API, the implemented iterators can be different without implementing the interface.
testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)testify/assert
)Sentinel iterators can be cheaper to construct.
Implement a ComparableIterator
s for each appropriate container, not a general one.
Disallowing it could make implementations a lot easier
I might need to reimplement this in go
#!/usr/bin/env python3
import asyncio
import re
import signal
from dataclasses import dataclass
from typing import Dict, List, Optional, Tuple
from matplotlib._api import itertools
FILE_HEADER: str = """// Copyright (c) 2022, Jonas Muehlmann. All rights reserved.
// Copyright (c) 2015, Emir Pasic. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package ds"""
BOOL: str = "bool"
INT: str = "int"
T: str = "T"
ITERATOR: str = "Z"
ORDERED_ITERATOR: str = "Ordered_"
COMPARABLE_ITERATOR: str = "Comparable_"
SIZED_ITERATOR: str = "Sized_"
WRITEABLE_ITERATOR: str = "Writeable_"
READABLE_ITERATOR: str = "Readable_"
FORWARD_ITERATOR: str = "Forward_"
REVERSED_ITERATOR: str = "Reversed_"
BACKWARD_ITERATOR: str = "Backward_"
UNORDERED_FORWARD_ITERATOR: str = "UnorderedForward_"
UNORDERED_REVERSED_ITERATOR: str = "UnorderedReversed_"
UNORDERED_BACKWARD_ITERATOR: str = "UnorderedBackward_"
BIDIRECTIONAL_ITERATOR: str = "Bidirectional_"
RANDOM_ACCESS_ITERATOR: str = "RandomAccess_"
GENERATED_INTERFACES: Dict[str, "Interface"] = {}
PERMUTATION_LENGHT: int = 0
PREVIOUS_PERMUTATION_LENGTH: int = -1
def split_name(names: List[str]) -> List[str]:
new_names: List[str] = []
for name in names:
tmp = name.split("_")
try:
tmp.remove("")
except ValueError:
pass
new_names += tmp
new_names = [name for name in new_names if name != ITERATOR]
return new_names
def does_hierarchy_contain_interface(
target: "Interface", hierarchy: "Interface"
) -> bool:
if hierarchy.name == target.name:
return True
if hierarchy.inherited_interfaces is None:
return False
return any(
does_hierarchy_contain_interface(target, GENERATED_INTERFACES[interface])
for interface in hierarchy.inherited_interfaces
)
def interface_contained_in_combinations_hierarchy(combination: List[str]) -> bool:
for interface in combination:
hierarchies_names: List[str] = combination.copy()
hierarchies_names.remove(interface)
for hierarchy_name in hierarchies_names:
if does_hierarchy_contain_interface(
GENERATED_INTERFACES[interface], GENERATED_INTERFACES[hierarchy_name]
):
return True
return False
def is_method_generic(method: "Method") -> bool:
if method.parameters is None:
return False
return any(p.type == T for p in method.parameters)
def is_interface_generic(interface: "Interface") -> bool:
has_generic_methods: bool = False
has_generic_inherited_interface: bool = False
if interface.methods is not None:
has_generic_methods = any(map(is_method_generic, interface.methods))
if interface.inherited_interfaces is not None:
has_generic_inherited_interface = any(
is_interface_generic(GENERATED_INTERFACES[name])
for name in interface.inherited_interfaces
)
return has_generic_methods or has_generic_inherited_interface
def make_inherited_interface_name(interface: "Interface") -> str:
name: str = interface.name
if is_interface_generic(interface):
name += "[T any]"
return name
@dataclass
class Parameter:
name: str
type: str
def __str__(self):
return f"{self.name} {self.type}"
@dataclass
class Method:
name: str
parameters: Optional[List[Parameter]] = None
return_value: str = ""
def __str__(self):
return f"{self.name}({', '.join(map(str, self.parameters if self.parameters is not None else ''))}) {self.return_value}"
@dataclass
class Interface:
name: str
methods: Optional[List[Method]] = None
inherited_interfaces: Optional[List[str]] = None
def __str__(self):
inherited_methods_fragment: str = ""
if self.inherited_interfaces is not None:
inherited_methods_fragment = "\n ".join(
make_inherited_interface_name(GENERATED_INTERFACES[name])
for name in self.inherited_interfaces
)
methods_fragment: str = "\n ".join(
map(str, self.methods if self.methods else "")
)
type_param_fragment: str = "[T any]" if is_interface_generic(self) else ""
return f"type {self.name}{type_param_fragment} interface {{\n {inherited_methods_fragment}\n\n {methods_fragment}\n}}"
iterator: Interface = Interface(
name="Iterator",
methods=[
Method(name="Begin"),
Method(name="End"),
Method(name="IsBegin", return_value=BOOL),
Method(name="IsEnd", return_value=BOOL),
Method(name="First", return_value=BOOL),
Method(name="Last", return_value=BOOL),
Method(name="IsValid", return_value=BOOL),
],
)
BASE_INTERFACES: Dict[str, Interface] = {
ORDERED_ITERATOR: Interface(
name=ORDERED_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="IsBefore",
parameters=[Parameter("other", ORDERED_ITERATOR)],
return_value=BOOL,
),
Method(
name="After",
parameters=[Parameter("other", ORDERED_ITERATOR)],
return_value=BOOL,
),
Method(
name="DistanceTo",
parameters=[Parameter("other", ORDERED_ITERATOR)],
return_value=INT,
),
],
),
COMPARABLE_ITERATOR: Interface(
name=COMPARABLE_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="IsEqual",
parameters=[Parameter("other", COMPARABLE_ITERATOR)],
return_value=BOOL,
),
],
),
SIZED_ITERATOR: Interface(
name=SIZED_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="Size",
return_value=INT,
),
],
),
WRITEABLE_ITERATOR: Interface(
name=WRITEABLE_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="SET",
parameters=[Parameter("value", T)],
),
],
),
READABLE_ITERATOR: Interface(
name=READABLE_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="Get",
parameters=[Parameter("value", T)],
),
],
),
FORWARD_ITERATOR: Interface(
name=FORWARD_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="Advance",
return_value=BOOL,
),
Method(
name="Next",
return_value=FORWARD_ITERATOR,
),
Method(
name="AdvanceN",
parameters=[Parameter("n", INT)],
return_value=BOOL,
),
Method(
name="NextN",
parameters=[Parameter("n", INT)],
return_value=FORWARD_ITERATOR,
),
],
),
REVERSED_ITERATOR: Interface(
name=REVERSED_ITERATOR, inherited_interfaces=[FORWARD_ITERATOR]
),
BACKWARD_ITERATOR: Interface(
name=BACKWARD_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="Recede",
return_value=BOOL,
),
Method(
name="Previous",
return_value=BACKWARD_ITERATOR,
),
Method(
name="RecedeN",
parameters=[Parameter("n", INT)],
return_value=BOOL,
),
Method(
name="PreviousN",
parameters=[Parameter("n", INT)],
return_value=BACKWARD_ITERATOR,
),
],
),
UNORDERED_FORWARD_ITERATOR: Interface(
name=UNORDERED_FORWARD_ITERATOR,
inherited_interfaces=[FORWARD_ITERATOR],
methods=[
Method(
name="AdvanceOrdered",
return_value=BOOL,
),
Method(
name="NextOrdered",
return_value=UNORDERED_FORWARD_ITERATOR,
),
Method(
name="AdvanceOrderedN",
parameters=[Parameter("n", INT)],
return_value=BOOL,
),
Method(
name="NextOrderedN",
parameters=[Parameter("n", INT)],
return_value=UNORDERED_FORWARD_ITERATOR,
),
],
),
UNORDERED_REVERSED_ITERATOR: Interface(
name=UNORDERED_REVERSED_ITERATOR,
inherited_interfaces=[REVERSED_ITERATOR],
),
UNORDERED_BACKWARD_ITERATOR: Interface(
name=UNORDERED_BACKWARD_ITERATOR,
inherited_interfaces=[BACKWARD_ITERATOR],
methods=[
Method(
name="RecedeOrdered",
return_value=BOOL,
),
Method(
name="PreviousOrdered",
return_value=UNORDERED_BACKWARD_ITERATOR,
),
Method(
name="RecedeOrderedN",
parameters=[Parameter("n", INT)],
return_value=BOOL,
),
Method(
name="PreviousOrderedN",
parameters=[Parameter("n", INT)],
return_value=UNORDERED_BACKWARD_ITERATOR,
),
],
),
BIDIRECTIONAL_ITERATOR: Interface(
name=BIDIRECTIONAL_ITERATOR,
inherited_interfaces=[FORWARD_ITERATOR, BACKWARD_ITERATOR],
methods=[
Method(
name="MoveBy",
parameters=[Parameter("n", INT)],
return_value=BOOL,
),
Method(
name="Nth",
parameters=[Parameter("n", INT)],
return_value=BIDIRECTIONAL_ITERATOR,
),
],
),
RANDOM_ACCESS_ITERATOR: Interface(
name=RANDOM_ACCESS_ITERATOR,
inherited_interfaces=[ITERATOR],
methods=[
Method(
name="MoveTo",
parameters=[Parameter("i", INT)],
return_value=BOOL,
),
Method(
name="GetAt",
parameters=[Parameter("i", INT)],
return_value=BOOL,
),
Method(
name="SetAt",
parameters=[Parameter("i", INT), Parameter("value", T)],
return_value=BOOL,
),
Method(
name="Index",
return_value=T,
),
],
),
}
def add_interface(combination: List[str]):
new_interface_name: str = ""
# print(combination)
for interface in combination:
new_interface_name += GENERATED_INTERFACES[interface].name.split(ITERATOR)[0]
new_interface_name += ITERATOR
new_interface = Interface(
name=new_interface_name,
inherited_interfaces=[
GENERATED_INTERFACES[interface].name for interface in combination
],
)
GENERATED_INTERFACES[new_interface_name] = new_interface
def generate_interfaces():
global GENERATED_INTERFACES
global PERMUTATION_LENGHT
global PREVIOUS_PERMUTATION_LENGTH
GENERATED_INTERFACES = BASE_INTERFACES
GENERATED_INTERFACES[ITERATOR] = iterator
PERMUTATION_LENGHT = len(BASE_INTERFACES) + 1
while PREVIOUS_PERMUTATION_LENGTH != PERMUTATION_LENGHT:
for next_combination_length in range(2, PERMUTATION_LENGHT):
next_combinations: List[Tuple[str]] = list(
itertools.combinations(
GENERATED_INTERFACES.keys(), next_combination_length
)
)
for combination in next_combinations:
combination = list(combination)
if ITERATOR in combination:
continue
split: List[str] = sorted(split_name(combination)) + [ITERATOR]
split_set: List[str] = sorted(list(set(split_name(combination)))) + [
ITERATOR
]
if len(split) != len(split_set):
continue
if (
(FORWARD_ITERATOR[:-1] in split and BACKWARD_ITERATOR[:-1] in split)
or (
FORWARD_ITERATOR[:-1] in split
and BIDIRECTIONAL_ITERATOR[:-1] in split
)
or (
FORWARD_ITERATOR[:-1] in split
and REVERSED_ITERATOR[:-1] in split
)
or (
BACKWARD_ITERATOR[:-1] in split
and REVERSED_ITERATOR[:-1] in split
)
or (
BACKWARD_ITERATOR[:-1] in split
and BIDIRECTIONAL_ITERATOR[:-1] in split
)
):
continue
if ORDERED_ITERATOR[:-1] in split and (
UNORDERED_BACKWARD_ITERATOR[:-1] in split
or UNORDERED_FORWARD_ITERATOR[:-1]
or UNORDERED_REVERSED_ITERATOR[:-1] in split
):
continue
if interface_contained_in_combinations_hierarchy(combination):
continue
print(split)
add_interface(combination)
print("Generated interfaces: ", len(GENERATED_INTERFACES))
PREVIOUS_PERMUTATION_LENGTH = PERMUTATION_LENGHT
PERMUTATION_LENGHT = len(GENERATED_INTERFACES)
print(PERMUTATION_LENGHT)
def signal_handler(signum, frame):
print("Generated interfaces: ", len(GENERATED_INTERFACES))
write_interfaces()
raise Exception("Timed out or cancelled!")
def write_interfaces():
with open("interfaces.go", "w+", encoding="utf-8") as f:
f.write(
"\n\n".join([FILE_HEADER] + list(map(str, GENERATED_INTERFACES.values())))
)
def main():
signal.signal(signal.SIGALRM, signal_handler)
signal.signal(signal.SIGINT, signal_handler)
signal.signal(signal.SIGHUP, signal_handler)
signal.signal(signal.SIGTERM, signal_handler)
# signal.alarm(5) # Ten seconds
generate_interfaces()
write_interfaces()
# TODO: I might need to reimplement this in go
if __name__ == "__main__":
main()
print("Done")
e769559277e7ff1804753e94c732d089c5b67ea9
Implement NewFromMap() method which only copies map and not items
New instantiates a hash map.
datastructures.go/maps/hashmap/hashmap.go
Line 31 in 458e2c8
import (
"fmt"
"github.com/emirpasic/gods/maps"
)
// Assert Map implementation.
var _ maps.Map = (*Map)(nil)
// TODO: Allow access to underlying map
// Map holds the elements in go's native map.
type Map struct {
m map[interface{}]interface{}
}
// TODO: Implement NewFromMap() method which only copies map and not items
// New instantiates a hash map.
func New() *Map {
return &Map{m: make(map[interface{}]interface{})}
78668f9ea70474e3e2a112324cc07c7cabcf3236
Iterate over elements only once and keep counter of found values
defer testCommon.HandlePanic(t, test.name)
in FIRST LINE of the test loop.
Implement Pop functions
next *element[T]
}
// TODO: Implement Pop functions
func (list *List[T]) PopBack(n int) { panic("Not implemented") }
func (list *List[T]) PopFront(n int) { panic("Not implemented") }
// New instantiates a new list and adds the passed values, if any, to the list
func New[T any](values ...T) *List[T] {
list := &List[T]{}
if len(values) > 0 {
list.PushBack(values...)
}
return list
}
// Add appends a value (one or more) at the end of the list (same as Append())
func (list *List[T]) PushBack(values ...T) {
for _, value := range values {
newElement := &element[T]{value: value}
if list.size == 0 {
4229c8d7366bc1608603756e9c6dae24553e6f36
Some license headers falsely state the original author as a copyright holder.
Allow access to underlying slice
"github.com/emirpasic/gods/utils"
)
// Assert List implementation.
var _ lists.List = (*List)(nil)
// TODO: Try and reimplement methods through iterator
// TODO: Allow access to underlying slice
// TODO: Rename to DynamicArray
// List holds the elements in a slice.
type List struct {
elements []interface{}
size int
9299fc4941327a893bb4dbb1e32a7af6ff271c2d
Can we use type parameters in interfaces to embed? This could simplify variant creation like BidirectionalIterator vs UnorderedBidirectionalIterator
Iterator defines the minimum functionality required for all other iterators.
datastructures.go/ds/iterator.go
Line 9 in fdc27db
package ds
// TODO: Implement Constructors for types, which take iterators to materialize
// TODO: Can we use type parameters in interfaces to embed? This could simplify variant creation like BidirectionalIterator vs UnorderedBidirectionalIterator
// Iterator defines the minimum functionality required for all other iterators.
type Iterator interface {
12f6d5342737b465ab11048f8f43aad1d505cece
Why not just use list.elemens = append(list.elements, ...values)?
https://github.com/golang/go/blob/master/src/runtime/slice.go
shrinkFactor = float32(0.25) // shrink when size is 25% of capacity (0 means never shrink)
)
// New instantiates a new list and adds the passed values, if any, to the list.
func New[T any](values ...T) *List[T] {
list := &List[T]{}
if len(values) > 0 {
list.PushBack(values...)
}
return list
}
// NewFromSLice instantiates a new list containing the provided slice.
func NewFromSlice[T any](slice []T) *List[T] {
list := &List[T]{elements: slice, size: len(slice)}
return list
}
// Add appends a value at the end of the list.
func (list *List[T]) PushBack(values ...T) {
// TODO: Why not just use list.elemens = append(list.elements, ...values)?
// https://github.com/golang/go/blob/master/src/runtime/slice.go
list.growBy(len(values))
for _, value := range values {
list.elements[list.size] = value
5f13fa0c5b83e523cacbcc2c2244deed2b53f9fa
Implement Constructors for types, which take iterators to materialize
Unless Next() is called, the iterator is in an invalid state.
Unless Previous() is called, the iterator is in an invalid state.
Next() ForwardIterator
NextN(n int) ForwardIterator
This iterator would allow you to e.g. iterate over a builtin map in the lexographical order of the keys.
NextOrdered() UnorderedForwardIterator
NextOrderedN(n int) UnorderedForwardIterator
This allows using ForwardIterator and ReversedIterator with the same API.
Previous() BackwardIterator
PreviousN(n int) BackwardIterator
This iterator would allow you to e.g. iterate over a builtin map in the reverse lexographical order of the keys.
PreviousOrdered() UnorderedBackwardIterator
PreviousOrderedN(n int) UnorderedBackwardIterator
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package ds
// TODO: Implement Constructors for types, which take iterators to materialize
// Iterator defines the minimum functionality required for all other iterators.
type Iterator interface {
// Begin returns an initialized iterator, which points to one element before it's first.
// Unless Next() is called, the iterator is in an invalid state.
Begin() Iterator
// End returns an initialized iterator, which points to one element afrer it's last.
// Unless Previous() is called, the iterator is in an invalid state.
End() Iterator
// IsBegin checks if the iterator is pointing to one element before it's first element, unless Next() is called, the iterator is in an invalid state.
IsBegin() bool
// IsEnd checks if the iterator is pointing to one element past it's last element, unless Previous() is called, the iterator is in an invalid state.
IsEnd() bool
// First returns an initialized iterator, which points to it's first element.
First() Iterator
// Last returns an initialized iterator, which points to it's last element.
Last() Iterator
// IsFirst checks if the iterator is pointing to it's first element, when Next() is called, the iterator is in an invalid state.
IsFirst() bool
// IsBegin checks if the iterator is pointing to it's last element, when Previous() is called, the iterator is in an invalid state.
IsLast() bool
// IsValid checks if the iterator is in a valid position and not e.g. out of bounds.
IsValid() bool
}
// OrderedIterator defines an Iterator, which can be said to be in a position before or after others's position.
type OrderedIterator interface {
// ********************* Inherited methods ********************//
Iterator
// ************************ Own methods ***********************//
// IsBefore checks if the iterator's position is said to come before other's position.
IsBefore(other OrderedIterator) bool
// IsBefore checks if the iterator's position is said to come after other's position.
IsAfter(other OrderedIterator) bool
// DistanceTo returns the signed distance of the iterator's position to other's position.
DistanceTo(other OrderedIterator) int
}
// ComparableIterator defines an Iterator, which can be said to be in a position equal to other's position.
type ComparableIterator interface {
// ********************* Inherited methods ********************//
Iterator
// ************************ Own methods ***********************//
// IsEqualTo checks if the iterator's position is said to be equal to other's position.
IsEqual(other ComparableIterator) bool
}
// SizedIterator defines an Iterator, which can be said to have a fixed size.
type SizedIterator[T any] interface {
// ********************* Inherited methods ********************//
Iterator
// ************************ Own methods ***********************//
// Size returns the number of elements in the iterator.
Size() int
}
// CollectionIterator defines a SizedIterator, which can be said to reference a collection of elements.
type CollectionIterator[T any] interface {
// ********************* Inherited methods ********************//
SizedIterator[T]
// ************************ Own methods ***********************//
// Index returns the index of the iterator's position in the collection.
Index() T
}
// WritableIterator defines an Iterator, which can be used to write to the underlying values.
type WritableIterator[T any] interface {
// ********************* Inherited methods ********************//
Iterator
// ************************ Own methods ***********************//
// Set sets the value at the iterator's position.
Set(value T)
}
// ReadableIterator defines an Iterator, which can be used to read the underlying values.
type ReadableIterator[T any] interface {
// ********************* Inherited methods ********************//
Iterator
// ************************ Own methods ***********************//
// Get returns the value at the iterator's position.
Get() T
}
// ForwardIterator defines an ordered Iterator, which can be moved forward according to the indexes ordering.
type ForwardIterator interface {
// ********************* Inherited methods ********************//
Iterator
// ************************ Own methods ***********************//
// Next moves the iterator forward by one position.
Next()
// NextN moves the iterator forward by n positions.
NextN(i int)
// Advance() bool
// Next() ForwardIterator
// AdvanceN(n int) bool
// NextN(n int) ForwardIterator
}
// UnorderedForwardIterator defines an unordered ForwardIterator, which can be moved forward according to the indexes ordering in addition to the underlying data structure's ordering.
// This iterator would allow you to e.g. iterate over a builtin map in the lexographical order of the keys.
type UnorderedForwardIterator interface {
// ********************* Inherited methods ********************//
ForwardIterator
// ************************ Own methods ***********************//
// NextOrdered moves the iterator forward by one position according to the indexes lexographical ordering instead of the underlying data structure's ordering.
NextOrdered()
// NextOrdered moves the iterator forward by n positions according to the indexes lexographical ordering instead of the underlying data structure's ordering.
NextOrderedN(n int)
// AdvanceOrdered() bool
// NextOrdered() UnorderedForwardIterator
// AdvanceOrderedN(n int) bool
// NextOrderedN(n int) UnorderedForwardIterator
}
// ReversedIterator defines a a ForwardIterator, whose iteration direction is reversed.
// This allows using ForwardIterator and ReversedIterator with the same API.
type ReversedIterator interface {
// ********************* Inherited methods ********************//
ForwardIterator
// ************************ Own methods ***********************//
}
// BackwardIterator defines an Iterator, which can be moved backward according to the indexes ordering.
type BackwardIterator interface {
// ********************* Inherited methods ********************//
Iterator
// ************************ Own methods ***********************//
// Next moves the iterator backward by one position.
Previous()
// NextN moves the iterator backward by n positions.
PreviousN(n int)
// Recede() bool
// Previous() BackwardIterator
// RecedeN(n int) bool
// PreviousN(n int) BackwardIterator
}
// UnorderedBackwardIterator defines an unordered BackwardIterator, which can be moved backward according to the indexes ordering in addition to the underlying data structure's ordering.
// This iterator would allow you to e.g. iterate over a builtin map in the reverse lexographical order of the keys.
type UnorderedBackwardIterator interface {
// ********************* Inherited methods ********************//
BackwardIterator
// ************************ Own methods ***********************//
// PreviousOrdered moves the iterator backward by one position according to the indexes lexographical ordering instead of the underlying data structure's ordering.
PreviousOrdered()
// PreviousOrdered moves the iterator backward by n positions according to the indexes lexographical ordering instead of the underlying data structure's ordering.
PreviousOrderedN(n int)
// RecedeOrdered() bool
// PreviousOrdered() UnorderedBackwardIterator
// RecedeOrderedN(n int) bool
// PreviousOrderedN(n int) UnorderedBackwardIterator
}
// BidirectionalIterator defines a ForwardIterator and BackwardIterator, which can be moved forward and backward according to the underlying data structure's ordering.
type BidirectionalIterator interface {
// ********************* Inherited methods ********************//
ForwardIterator
BackwardIterator
// ************************ Own methods ***********************//
// Next moves the iterator forward/backward by n positions.
MoveBy(n int) bool
// Nth(n int) BidirectionalIterator
}
// RandomAccessIterator defines a BidirectionalIterator and CollectionIterator, which can be moved to every position in the iterator.
type RandomAccessIterator[T any] interface {
// ********************* Inherited methods ********************//
BidirectionalIterator
CollectionIterator[T]
// ************************ Own methods ***********************//
// MoveTo moves the iterator to the given index.
MoveTo(i T) bool
}
// RandomAccessReadableIterator defines a RandomAccessIterator and ReadableIterator, which can read from every index in the iterator.
type RandomAccessReadableIterator[T any, V any] interface {
// ********************* Inherited methods ********************//
RandomAccessIterator[T]
ReadableIterator[T]
// ************************ Own methods ***********************//
// GetAt returns the value at the given index of the iterator.
GetAt(i T) V
}
// RandomAccessReadableIterator defines a RandomAccessIterator and WritableIterator, which can write from every index in the iterator.
type RandomAccessWriteableIterator[T any, V any] interface {
// ********************* Inherited methods ********************//
RandomAccessIterator[T]
WritableIterator[V]
// ************************ Own methods ***********************//
// GetAt sets the value at the given index of the iterator.
SetAt(i T, value V)
}
5ca287a7c0b223d2a22a9ef6d1f0f11b6256a9df
Implement PushBack, PopBack, PushFront PopFront, Reverse
List interface that all lists implement.
datastructures.go/lists/lists.go
Line 18 in 458e2c8
"github.com/emirpasic/gods/utils"
)
// TODO: Implement PushBack, PopBack, PushFront PopFront, Reverse
// List interface that all lists implement.
type List interface {
Get(index int) (interface{}, bool)
Remove(index int)
03a82b9adb592df6391a50816232af27dea17d6d
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.