collections

package module
v0.0.2-0...-fcb6822 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 8, 2022 License: BSD-2-Clause Imports: 4 Imported by: 0

README

go-generics/collections

Go generic collections

import "github.com/go-generics/collections"

Set

Implemented as a map, indexed by T, of string{}

set := collections.NewSet(0, 1, 2)  // set is Set[int]
set.Len()  // 3

set.Has(0)  // true
set.Has(3)  // false

set.Insert(3)
set.Has(3)  // true

set.Delete(3)
set.Has(3)  // false

Deque (Queue / Stack)

Implemented as a doubly linked list.

deque := collections.NewDeque[int]()

deque.PushFront(3)
deque.PushFront(2)
deque.PushFront(1)
deque.PushBack(4)
deque.PushBack(5)
deque.PushBack(6)

fmt.Print(deque)  // [1 2 3 4 5 6]

fmt.Print(deque.Back())     // 6
fmt.Print(deque.PopBack())  // 6
fmt.Print(deque.Back())     // 5

fmt.Print(deque)  // [1 2 3 4 5]

fmt.Print(deque.Front())     // 1
fmt.Print(deque.PopFront())  // 1
fmt.Print(deque.Front())     // 2

fmt.Print(deque)  // [2 3 4 5]

Binary Tree

Implemented with nodes as structs, and references as pointers.

tree := collections.NewBinaryTree[int]()

tree.Insert(1)
tree.Insert(2)
fmt.Println(tree)  // [1 2]

tree.Delete(1)
tree.Delete(2)
fmt.Println(tree)  // []

tree.Delete(-1)
fmt.Println(tree)  // []

Implicit Treap

Implemented with a binary tree, nodes as structs and references as pointers.

Priority is random, stored in each node, and the structure is a binary heap on the priorities.

The key for every value is the position in a sequence. So the implicit key for every node is the position it has during an in-order traversal. The structure is a Binary Search Tree on the keys.

https://en.wikipedia.org/wiki/Treap

https://en.wikipedia.org/wiki/Cartesian_tree

https://cp-algorithms.com/data_structures/treap.html

treap := collections.NewImplicitTreap(3, 1, 4, 1, 5, 4, 9, 2)
fmt.Println(treap)  // 3 1 4 1 5 4 9 2

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func IsProperSubset 

func IsProperSubset[T comparable](s1 Set[T], s2 Set[T]) bool
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	a := collections.NewSet(1.2)
	b := collections.NewSet(1.2, 3.4)

	fmt.Println(!collections.IsProperSubset(a, a))
	fmt.Println(collections.IsProperSubset(a, b))
	fmt.Println(!collections.IsProperSubset(b, a))

}

Output:

true
true
true

func IsSubset 

func IsSubset[T comparable](s1 Set[T], s2 Set[T]) bool
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	a := collections.NewSet(1.2)
	b := collections.NewSet(1.2, 3.4)

	fmt.Println(collections.IsSubset(a, a))
	fmt.Println(collections.IsSubset(a, b))
	fmt.Println(!collections.IsSubset(b, a))

}

Output:

true
true
true

Types

type Backer 

type Backer[T any] interface {
	Back() T
	PopBack() T
	PushBack(item T)
}

type BinaryTree 

type BinaryTree[T ordered] interface {
	fmt.Stringer

	Collection
	Deleter[T]
	Eacher[T]
	Inserter[T]

	ToDeque() Deque[T]
	Levels()
}

func NewBinaryTree 

func NewBinaryTree[T ordered]() BinaryTree[T]

type Collection 

type Collection interface {
	Len() int
}

type Deleter 

type Deleter[T any] interface {
	Delete(item T)
}

type Deque 

type Deque[T ordered] interface {
	fmt.Stringer
	Collection
	Eacher[T]
	Backer[T]
	Fronter[T]
}

func NewDeque 

func NewDeque[T ordered]() Deque[T]

type Eacher 

type Eacher[T any] interface {
	Each(action func(index int, item T))
	EachUntil(action func(index int, item T), stop func(index int, item T) bool)
}

type Fronter 

type Fronter[T any] interface {
	Front() T
	PopFront() T
	PushFront(item T)
}

type Haser 

type Haser[T comparable] interface {
	Has(item T) bool
}

type Heap 

type Heap[T ordered] interface {
	fmt.Stringer

	Collection
	Fronter[T]
}
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	h := collections.NewHeap(2, 1, 5)
	h.PushFront(3)
	fmt.Printf("minimum: %d\n", h.Front())
	for h.Len() > 0 {
		fmt.Print(h.PopFront(), " ")
	}

}

Output:

minimum: 1
1 2 3 5

func NewHeap 

func NewHeap[T ordered](values ...T) Heap[T]

type ImplicitTreap 

type ImplicitTreap[T comparable] struct {
	Root *ImplicitTreapNode[T]
}
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	t := collections.NewImplicitTreap(3, 1, 4, 1, 5, 4, 9, 2)
	fmt.Println(t)

}

Output:

3 1 4 1 5 4 9 2

func NewImplicitTreap 

func NewImplicitTreap[T comparable](values ...T) *ImplicitTreap[T]

func (*ImplicitTreap[T]) Append 

func (it *ImplicitTreap[T]) Append(item T)

func (*ImplicitTreap[T]) At 

func (it *ImplicitTreap[T]) At(key int) T

func (*ImplicitTreap[T]) DeleteAt 

func (it *ImplicitTreap[T]) DeleteAt(pos int)

func (*ImplicitTreap[T]) Merge 

func (l *ImplicitTreap[T]) Merge(r *ImplicitTreap[T])

func (*ImplicitTreap[T]) Split 

func (it *ImplicitTreap[T]) Split(key int) (l *ImplicitTreap[T], r *ImplicitTreap[T])

func (*ImplicitTreap[T]) String 

func (n *ImplicitTreap[T]) String() string

type ImplicitTreapNode 

type ImplicitTreapNode[T comparable] struct {
	Left     *ImplicitTreapNode[T]
	Right    *ImplicitTreapNode[T]
	Value    T
	Size     int
	Priority float64
}

func NewImplicitTreapNode 

func NewImplicitTreapNode[T comparable](value T) *ImplicitTreapNode[T]

func NewImplicitTreapRoot 

func NewImplicitTreapRoot[T comparable](values ...T) *ImplicitTreapNode[T]

func (*ImplicitTreapNode[T]) At 

func (n *ImplicitTreapNode[T]) At(key int) T

func (*ImplicitTreapNode[T]) DeleteAt 

func (p *ImplicitTreapNode[T]) DeleteAt(pos int) *ImplicitTreapNode[T]

func (*ImplicitTreapNode[T]) Merge 

func (l *ImplicitTreapNode[T]) Merge(r *ImplicitTreapNode[T]) (p *ImplicitTreapNode[T])

func (*ImplicitTreapNode[T]) Split 

func (p *ImplicitTreapNode[T]) Split(key, offset int) (l *ImplicitTreapNode[T], r *ImplicitTreapNode[T])

func (*ImplicitTreapNode[T]) String 

func (n *ImplicitTreapNode[T]) String() string

type Inserter 

type Inserter[T any] interface {
	Insert(item T)
}

type Set 

type Set[T comparable] interface {
	fmt.Stringer

	Collection
	Deleter[T]
	Eacher[T]
	Inserter[T]
	Haser[T]
}

func Difference 

func Difference[T comparable](s1 Set[T], s2 Set[T]) Set[T]
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	ab := collections.NewSet("A", "B")
	bc := collections.NewSet("B", "C")

	fmt.Println(collections.Difference(ab, bc))
	fmt.Println(collections.Difference(bc, ab))

}

Output:

[A]
[C]

func Intersection 

func Intersection[T comparable](s1 Set[T], s2 Set[T]) Set[T]
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	ab := collections.NewSet("A", "B")
	bc := collections.NewSet("B", "C")
	intersection := collections.Intersection(ab, bc)

	fmt.Println(intersection.String())

	// Output
	// [B]
}

Output:

func NewSet 

func NewSet[T comparable](items ...T) Set[T]
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	set := collections.NewSet(0, 1)

	fmt.Println(set.Has(0))
	fmt.Println(set.Has(1))
	fmt.Println(!set.Has(2))

}

Output:

true
true
true

func Union 

func Union[T comparable](s1 Set[T], s2 Set[T]) Set[T]
Example 
package main

import (
	"fmt"

	"github.com/go-generics/collections"
)

func main() {
	ab := collections.NewSet("A", "B")
	bc := collections.NewSet("B", "C")
	union := collections.Union(ab, bc)

	fmt.Println(union.Has("A"))
	fmt.Println(union.Has("B"))
	fmt.Println(union.Has("C"))
	fmt.Println(union.Len())

}

Output:

true
true
true
3

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.