typeparamcommon

README

type-param-common

Type parameter primitives and commons.

This repository contains type-parameter version of containers and set, iterator, queue, deque, stack implementations.

Suffixed with -param to avoid name overlapping

Wrappers of Go std lib are suffixed with -param

Package descriptions

Wrappers of container of standard

• heap-param
  • STATUS: done. doc comments needs improvement.
• list-param
  • STATUS: done. most of behavior consistent to container/list.
• ring-param
  • STATUS: Half done. Needs good testing.

Heap-param wraps container/heap of standard library. see ./heap.go, ./filterable_heap.go and corresponding test files for example usages.

list-param and ring-param wraps container/list and container/ring respectively.

*Element[T] and *Ring[T] have addtitional methods, Get, Set and Unwrap to replace direct mutation/observation of elementOrRing.Value. Some of their methods are changed their returned value from single ret T to (ret T, ok bool). This second boolean value indicates internal Value was not nil, which means returned ret T is zero value if false.

sync-param

Wrappers of sync.Map and sync.Pool.

slice

Deque[T], Queue[T], Stack[T] and helper functions. It eases pain of write-deque-everywhere.

• Deque
• Queue
• Stack
• Helper functions
  • Useful for unsorted slice.

iterator

Exerimental iterator impl for go.

• STATUS: half done. requires addition of missing tests. add benchmark for performance comparision.

iterator package's main struct is Iterator[T].

type Iterator[T any] struct {
	SeIterator[T]
}

type Nexter[T any] interface {
	Next() (next T, ok bool)
}

// Singly ended iterator.
type SeIterator[T any] interface {
	Nexter[T]
}

Usage example:

package main

import (
	"fmt"
	"strings"

	"github.com/ngicks/type-param-common/iterator"
)

func main() {
	fmt.Println(
		iterator.Fold[iterator.EnumerateEnt[string]](
			iterator.Enumerate[string](
				iterator.
					FromSlice([]string{"foo", "bar", "baz"}).
					Map(func(s string) string { return s + s }).
					Exclude(func(s string) bool { return strings.Contains(s, "az") }).
					MustReverse(),
			),
			func(accumulator map[string]int, next iterator.EnumerateEnt[string]) map[string]int {
				accumulator[next.Next] = next.Count
				return accumulator
			},
			map[string]int{},
		),
	)  // outputs: map[barbar:0 foofoo:1]
}

It requires Singly ended iterator as embeded field. Iterator[T] is thin helper type. Chance to have breaking change (e.g. new field) is low.

Iterator[T] can be created directly from

• slice []T
• listparam.List[T]
• channel <-chan T

var iter iterator.Iterator[string]
iter = iterator.FromSlice(strSlice)
// or
// for size-fixed iterator
iter = iterator.FromFixedList(list)
// for growing iterator
iter = iterator.FromList(list)
// or
iter = iterator.FromChannel(make(chan string))

Input SeIterator[T] can optionally implements interfaces shown below. Those will be used in iterator methods of corresponding name.

type SizeHinter interface {
	SizeHint() int
}

type Reverser[T any] interface {
	Reverse() (rev SeIterator[T], ok bool)
}

type Unwrapper[T any] interface {
	Unwrap() SeIterator[T]
}


// Doubly ended iterator.
type DeIterator[T any] interface {
	Nexter[T]
	NextBacker[T]
}

Documentation

Index

• func BuildExcludeFilter[T any](start, end int, filterPredicate func(T) bool) func(sl *[]T)
• func MakeHeap[T any](less func(i, j T) bool) (*HeapWrapper[T], *SliceInterface[T])
• func MakeMaxHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])
• func MakeMinHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])
• type FilterableHeap
  • func NewFilterableHeap[U any, T Lessable[U]]() *FilterableHeap[U, T]
  • func (h *FilterableHeap[U, T]) Clone() *FilterableHeap[U, T]
  • func (h *FilterableHeap[U, T]) Filter(filterFuncs ...func(innerSlice *[]T))
  • func (h *FilterableHeap[U, T]) Len() int
  • func (h *FilterableHeap[U, T]) Peek() (p T)
• type HeapWrapper
  • func NewHeapWrapper[T any](inter heapparam.Interface[T]) *HeapWrapper[T]
  • func (hw *HeapWrapper[T]) Fix(i int)
  • func (hw *HeapWrapper[T]) Init()
  • func (hw *HeapWrapper[T]) Pop() T
  • func (hw *HeapWrapper[T]) Push(x T)
  • func (hw *HeapWrapper[T]) Remove(i int) T
• type Lessable
• type SliceInterface
  • func NewSliceInterface[T any](init []T, less func(i, j T) bool) *SliceInterface[T]
  • func (sl *SliceInterface[T]) Len() int
  • func (sl *SliceInterface[T]) Less(i, j int) bool
  • func (sl *SliceInterface[T]) Pop() (p T)
  • func (sl *SliceInterface[T]) Push(x T)
  • func (sl *SliceInterface[T]) Swap(i, j int)

Functions

func BuildExcludeFilter

func BuildExcludeFilter[T any](start, end int, filterPredicate func(T) bool) func(sl *[]T)

func MakeHeap

func MakeHeap[T any](less func(i, j T) bool) (*HeapWrapper[T], *SliceInterface[T])

MakeHeap makes a heap for the type T using a less[T] function.

1st returned value is struct with basic set of heap methods. 2nd is one that implements heap.Interface[T] which is used in *HeapWrapper[T]. To add your own heap methods, embed *HeapWrapper[T] to your own struct type and manipulate SliceInterface[T].Inner slice in methods of that struct with succeeding *HeapWrapper.Init call.

func MakeMaxHeap

func MakeMaxHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])

MakeMaxHeap makes a maxheap for the type T. This is same as MakeMinHeap but uses more[T] instead.

func MakeMinHeap

func MakeMinHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])

MakeMinHeap makes a minheap for the type T.

MakeMinHeap does what MakeHeap does but with predeclared less function. T is constrained to predeclared primitive types which are compatible with less and greater comparison operations.

Types

type FilterableHeap

type FilterableHeap[U any, T Lessable[U]] struct {
	*HeapWrapper[T]
	// contains filtered or unexported fields
}

func NewFilterableHeap

func NewFilterableHeap[U any, T Lessable[U]]() *FilterableHeap[U, T]

func (*FilterableHeap[U, T]) Clone

func (h *FilterableHeap[U, T]) Clone() *FilterableHeap[U, T]

Clone clones internal slice and creates new FilterableHeap with it. This is done by simple slice copy, without succeeding Init call, which means it also clones broken invariants if any.

If type T or one of its internal value is pointer type, mutation of T porpagates cloned to original, and vice versa.

func (*FilterableHeap[U, T]) Filter

func (h *FilterableHeap[U, T]) Filter(filterFuncs ...func(innerSlice *[]T))

Filter calls filterFuncs one by one, in given order, with following heap.Init(). Each filterFunc receives innerSlice so that it can be mutated in that func.

Filter calls heap.Init() at the end of the method. So the complexity is at least O(n) where n is h.Len().

func (*FilterableHeap[U, T]) Len

func (h *FilterableHeap[U, T]) Len() int

func (*FilterableHeap[U, T]) Peek

func (h *FilterableHeap[U, T]) Peek() (p T)

Peek returns most prioritized value in heap without removing it. If this heap contains 0 element, returned p is zero value for type T.

The complexity is O(1).

type HeapWrapper

type HeapWrapper[T any] struct {
	// contains filtered or unexported fields
}

func NewHeapWrapper

func NewHeapWrapper[T any](inter heapparam.Interface[T]) *HeapWrapper[T]

func (*HeapWrapper[T]) Fix

func (hw *HeapWrapper[T]) Fix(i int)

func (*HeapWrapper[T]) Init

func (hw *HeapWrapper[T]) Init()

func (*HeapWrapper[T]) Pop

func (hw *HeapWrapper[T]) Pop() T

func (*HeapWrapper[T]) Push

func (hw *HeapWrapper[T]) Push(x T)

func (*HeapWrapper[T]) Remove

func (hw *HeapWrapper[T]) Remove(i int) T

type Lessable

type Lessable[T any] interface {
	Inner() T
	// LessThan determines self is less than input Lessable[T].
	LessThan(Lessable[T]) bool
}

type SliceInterface

type SliceInterface[T any] struct {
	Inner []T
	// contains filtered or unexported fields
}

func NewSliceInterface

func NewSliceInterface[T any](init []T, less func(i, j T) bool) *SliceInterface[T]

func (*SliceInterface[T]) Len

func (sl *SliceInterface[T]) Len() int

func (*SliceInterface[T]) Less

func (sl *SliceInterface[T]) Less(i, j int) bool

func (*SliceInterface[T]) Pop

func (sl *SliceInterface[T]) Pop() (p T)

func (*SliceInterface[T]) Push

func (sl *SliceInterface[T]) Push(x T)

func (*SliceInterface[T]) Swap

func (sl *SliceInterface[T]) Swap(i, j int)