ds

package
v0.0.0-...-90b48ae Latest Latest
Warning

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

 Go to latest Published: Nov 22, 2024 License: BSD-2-Clause Imports: 8 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	Head balanceOrder = iota
	Tail
)

Variables

This section is empty.

Functions

func NewBool2d 

func NewBool2d(a, b int, value bool) [][]bool

func NewFloat2d 

func NewFloat2d(a, b int, value float64) [][]float64

func NewInt2d 

func NewInt2d(a, b, value int) [][]int

func NewInt3d 

func NewInt3d(a, b, c, value int) [][][]int

func Unique 

func Unique[V constraints.Ordered](arr []V) []V

Uniqueは配列から重複要素を削除し、ソートして返します。

Types

type BitSet 

type BitSet struct {
	// contains filtered or unexported fields
}

func NewBitSet 

func NewBitSet(size int) *BitSet

NewBitSetはsizeだけのboolを管理できるBitSetを作ります。

func (*BitSet) And 

func (bs *BitSet) And(other *BitSet)

Andは渡されたBitSetとの論理積を設定します。

func (*BitSet) Clear 

func (bs *BitSet) Clear()

Clearは全boolをfalseにします。

func (*BitSet) Count 

func (bs *BitSet) Count() int

Countはtrueになっている要素を数えて返します。

func (*BitSet) Get 

func (bs *BitSet) Get(index int) bool

Getはindex番目のboolを取得します。

func (*BitSet) Or 

func (bs *BitSet) Or(other *BitSet)

Orは渡されたBitSetとの論理和を設定します。

func (*BitSet) Set 

func (bs *BitSet) Set(index int, value bool)

Setはindex番目のboolをvalueにします。

func (*BitSet) Xor 

func (bs *BitSet) Xor(other *BitSet)

Xorは渡されたBitSetとの排他的論理和を設定します。

type Counter 

type Counter map[int]int

Counterは整数の多重集合を扱う簡易な実装です。

func NewCounter 

func NewCounter() Counter

func (*Counter) Add 

func (c *Counter) Add(value int)

Addはvalueの個数を増やします。

func (*Counter) Count 

func (c *Counter) Count(value int) int

Countはvalueの個数を返します。

func (*Counter) CountTypes 

func (c *Counter) CountTypes() int

CountTypesはこの集合に含まれる数値の種類を返します。

func (*Counter) Remove 

func (c *Counter) Remove(value int)

Removeはvalueの個数を減らします。

type Deque 

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

DequeはStackを2つ使用したDequeの実装です。

func NewDeque 

func NewDeque[T any]() *Deque[T]

func (*Deque[T]) Add 

func (queue *Deque[T]) Add(value T)

AddはQueue.Addの実装

func (*Deque[T]) AddFirst 

func (queue *Deque[T]) AddFirst(value T)

func (*Deque[T]) AddLast 

func (queue *Deque[T]) AddLast(value T)

func (*Deque[T]) Count 

func (queue *Deque[T]) Count() int

CountはQueue.Countの実装

func (*Deque[T]) First 

func (queue *Deque[T]) First() T

func (*Deque[T]) Get 

func (queue *Deque[T]) Get() T

GetはQueue.Getの実装

func (*Deque[T]) HasElements 

func (queue *Deque[T]) HasElements() bool

HasElementsはQueue.HasElementsの実装

func (*Deque[T]) IsEmpty 

func (queue *Deque[T]) IsEmpty() bool

IsEmptyはQueue.IsEmptyの実装

func (*Deque[T]) Last 

func (queue *Deque[T]) Last() T

func (*Deque[T]) Peek 

func (queue *Deque[T]) Peek() T

PeekはStack.Peekの実装

func (*Deque[T]) Pop 

func (queue *Deque[T]) Pop() T

PopはStack.Popの実装

func (*Deque[T]) Push 

func (queue *Deque[T]) Push(value T)

PushはStack.Pushの実装

func (*Deque[T]) Remove 

func (queue *Deque[T]) Remove() T

RemoveはQueue.Removeの実装

func (*Deque[T]) RemoveFirst 

func (queue *Deque[T]) RemoveFirst() T

func (*Deque[T]) RemoveLast 

func (queue *Deque[T]) RemoveLast() T

type DijkstraResult 

type DijkstraResult struct {
	// Costsは各頂点へのコスト
	Costs []int

	// Prevsは各頂点に最短距離で到着したとき、直前にいた頂点。開始地点は-1になる
	Prevs []int
}

func (*DijkstraResult) Path 

func (dr *DijkstraResult) Path(t int) []int

Pathはtまでの頂点を順に返します。

type DualSegmentTree 

type DualSegmentTree[V, X, F any] struct {
	Init func(n int) *DualSegmentTree[V, X, F]

	Update func(l, r int, value F)

	Query func(i int) V
}

Vは扱う値、Xは保持する値、Fは適用する値

func NewDualSegmentTree 

func NewDualSegmentTree[V, X, F any](

	mapping func(x *X, v *V),

	composition func(f *F, x *X),

	e func() V,

	id func() X,
) *DualSegmentTree[V, X, F]

type Edge 

type Edge struct {
	From int

	// 行き先
	To int

	// 重み
	Weight int

	// 辺の番号 (0-indexed)
	Index int
}

Edge は辺を表現する構造体です

type Graph 

type Graph struct {
	// 隣接リスト
	List [][]*Edge
	// 辺のリスト
	Edges []*Edge
}

Graph はグラフを表現する構造です

func NewGraph 

func NewGraph(n int) *Graph

NewGraph はグラフを作成します

func (*Graph) AddDirectedEdge 

func (g *Graph) AddDirectedEdge(u, v int)

AddDirectedEdgeはuからvへ重み1の有向辺を追加します。

func (*Graph) AddDirectedWeightedEdge 

func (g *Graph) AddDirectedWeightedEdge(u, v, w int)

AddDirectedWeightedEdgeはuからvへ重みwの有向辺を追加します。

func (*Graph) AddEdge 

func (g *Graph) AddEdge(u, v int)

AddEdge uからvへの重み1の無向辺を追加します。

func (*Graph) AddEdge1 

func (g *Graph) AddEdge1(u, v int)

AddEdge1はuからv(1-indexed)への重み1の無向辺を追加します。

func (*Graph) AddWeightedEdge 

func (g *Graph) AddWeightedEdge(u, v, w int)

AddWeightedEdge はuからvへ重みwの無向辺を追加します。

func (*Graph) BellmanFord 

func (g *Graph) BellmanFord(s, t int)

BellmanFord はsからtへの最短ルートを返します。

func (*Graph) CountNodes 

func (g *Graph) CountNodes() int

CountNodesはノードの数を返します。

func (*Graph) Dijkstra 

func (g *Graph) Dijkstra(s int) *DijkstraResult

Dijkstra はsから各頂点への最短距離を返します。 重みが負の辺があるときには使用できません。 計算量: |V| + |E|log|V|

func (*Graph) Lca 

func (g *Graph) Lca(root int) *Lca

Lcaはrootを木の根とした最小共通祖先を作成します。

func (*Graph) MaxFlow 

func (g *Graph) MaxFlow(s, t int) int

MaxFlowはsからtへの最大流を求めます。

func (*Graph) Scc 

func (g *Graph) Scc() Scc

sccは与えられたグラフgを強連結成分分解した結果を返します。

func (*Graph) WarshallFloyd 

func (g *Graph) WarshallFloyd() [][]int

WarshallFloyd は全点対の最短ルートを返します。

type Int2d 

type Int2d [][]int

func (*Int2d) Init 

func (arr *Int2d) Init(v int)

type Int4d 

type Int4d [][][][]int

func NewInt4d 

func NewInt4d(a, b, c, d, value int) Int4d

type IntLazySegmentTree 

type IntLazySegmentTree struct {
	// Initは長さnの配列として初期化します
	Init func(n int) *IntLazySegmentTree

	// InitByArrayはarrとして初期化します。
	InitByArray func(arr []int) *IntLazySegmentTree

	// Updateは[l, r)をfで更新します。
	Update func(l, r int, f int)

	// Queryは[l, r)の値を返します。
	Query func(l, r int) int
}

func NewIntLazySegmentTree 

func NewIntLazySegmentTree(
	operate func(a, b int) int,
	mapping func(f int, x int) int,
	composition func(f, g int) int,
	e func() int,
	id func() int,
) *IntLazySegmentTree

NewIntLazySegmentTreeは遅延評価セグメントツリーの実装を返します。 Vは扱うモノイドの型、Fはモノイドに適用する写像をあらわします。

type LargeBitSet 

type LargeBitSet struct {

	// Addはこの集合にvを追加します。
	Add func(v int)

	// Hasはこの集合にvが含まれるかどうかを判断します。
	Has func(v int) bool

	// Removeはこの集合からvを削除します。
	Remove func(v int)

	// Beforeはこの集合に含まれるv未満の要素のうち、最大の要素を返します。
	// 存在しない場合はnilを返します。
	Before func(v int) *int

	// Afterはこの集合に含まれるvを超える要素のうち、最小の要素を返します。
	// 存在しない場合はnilを返します。
	After func(v int) *int
	// contains filtered or unexported fields
}

巨大サイズの非負整数の集合を管理します。

func NewLargeBitSet 

func NewLargeBitSet() *LargeBitSet

type LargeBitSetNode 

type LargeBitSetNode struct {
	// contains filtered or unexported fields
}

func (*LargeBitSetNode) Index 

func (n *LargeBitSetNode) Index(v int) int

Indexはこのノードが持つ子要素のうち、vに対応するインデックスを返します。

func (*LargeBitSetNode) Range 

func (n *LargeBitSetNode) Range() int

Rangeはこのノードが持つ区間集合のサイズを返します。

func (*LargeBitSetNode) String 

func (n *LargeBitSetNode) String() string

type LazySegmentTree 

type LazySegmentTree[V, F any] struct {
	// Initは長さnの配列として初期化します
	Init func(n int) *LazySegmentTree[V, F]

	// InitByArrayはarrとして初期化します。
	InitByArray func(arr []V) *LazySegmentTree[V, F]

	// Updateは[l, r)をfで更新します。
	Update func(l, r int, f F)

	// Queryは[l, r)の値を返します。
	Query func(l, r int) V
}

func NewLazySegmentTree 

func NewLazySegmentTree[V, F any](
	operate func(a, b, ab *V),
	mapping func(f *F, x *V),
	composition func(f, g, fg *F),
	e func() V,
	id func() F,
) *LazySegmentTree[V, F]

NewLazySegmentTreeは遅延評価セグメントツリーの実装を返します。 Vは扱うモノイドの型、Fはモノイドに適用する写像をあらわします。

例えば range add range max queryの場合、以下のようになります。

st := NewLazySegmentTree[int, int]( 

max,
func(f, x int) int { return f + x },
func(f, g int) int { return f + g },
func() int { return 0 },
func() int { return 0 },

)

type Lca 

type Lca struct {
	// contains filtered or unexported fields
}

Lcaは最小共通祖先を提供します。

func (*Lca) Distance 

func (lca *Lca) Distance(a, b int) int

Distanceはaとbの距離を返します。

func (*Lca) Of 

func (lca *Lca) Of(a, b int) int

Ofはaとbの最小共通祖先を返します。

type LinkedList 

type LinkedList[V any] struct {
	// contains filtered or unexported fields
}

func NewLinkedList 

func NewLinkedList[V any]() *LinkedList[V]

func (*LinkedList[V]) Add 

func (list *LinkedList[V]) Add(value V) *LinkedListNode[V]

func (*LinkedList[V]) AddBack 

func (list *LinkedList[V]) AddBack(value V) *LinkedListNode[V]

func (*LinkedList[V]) AddFront 

func (list *LinkedList[V]) AddFront(value V) *LinkedListNode[V]

func (*LinkedList[V]) Back 

func (list *LinkedList[V]) Back() V

func (*LinkedList[V]) Front 

func (list *LinkedList[V]) Front() V

func (*LinkedList[V]) Len 

func (list *LinkedList[V]) Len() int

func (*LinkedList[V]) RemoveBack 

func (list *LinkedList[V]) RemoveBack() V

func (*LinkedList[V]) RemoveFront 

func (list *LinkedList[V]) RemoveFront() V

func (*LinkedList[V]) ToArray 

func (list *LinkedList[V]) ToArray() []V

type LinkedListNode 

type LinkedListNode[V any] struct {
	// contains filtered or unexported fields
}

func (*LinkedListNode[V]) AddAfter 

func (node *LinkedListNode[V]) AddAfter(value V) *LinkedListNode[V]

func (*LinkedListNode[V]) AddBefore 

func (node *LinkedListNode[V]) AddBefore(value V) *LinkedListNode[V]

func (*LinkedListNode[V]) Remove 

func (node *LinkedListNode[V]) Remove() V

type PriorityQueue 

type PriorityQueue[T any] struct {

	// Pushは優先度付きキューに要素を一つ追加します。
	Push func(value T)

	// Popは優先度付きキューから要素を一つ取り出します。
	Pop func() T

	// Peekは優先度つきキューの先頭要素を返します。
	Peek func() T

	// IsEmptyは優先度付きキューが空かどうかを判断します。
	IsEmpty func() bool

	// HasElementsはこの優先度付きキューが要素を持つかどうかを判断します。
	HasElements func() bool

	// Countはこの優先度付きキューがもつ要素の数を返します。
	Count func() int
	// contains filtered or unexported fields
}

PriorityQueue は優先度付きキューを表す

func NewPriorityQueue 

func NewPriorityQueue[T any](prior func(a, b T) bool) *PriorityQueue[T]

NewPriorityQueueはpriorで優先度が決まる空の優先度付きキューを返します。

type PriorityQueueList 

type PriorityQueueList struct {
	// contains filtered or unexported fields
}

PriorityQueueListは優先度付きキューのリストを表す この型はPriorityQueueとheapが要求するメソッド名が重複しないようにするための

func (PriorityQueueList) Len 

func (list PriorityQueueList) Len() int

Len は要素の数を返します。

func (PriorityQueueList) Less 

func (list PriorityQueueList) Less(i, j int) bool

Less は要素を比較し、優先度が低いかどうかを判断します

func (*PriorityQueueList) Pop 

func (list *PriorityQueueList) Pop() interface{}

Pop は要素を取り出して返します。

func (*PriorityQueueList) Push 

func (list *PriorityQueueList) Push(item interface{})

Push は要素を追加します。

func (PriorityQueueList) Swap 

func (list PriorityQueueList) Swap(i, j int)

Swap は要素を交換します。

type RedBlackTree 

type RedBlackTree[K any, V any] struct {
	// contains filtered or unexported fields
}

func NewRedBlackTree 

func NewRedBlackTree[K any, V any](comparator func(a, b K) int) *RedBlackTree[K, V]

func (*RedBlackTree[K, V]) Ceiling 

func (tree *RedBlackTree[K, V]) Ceiling(key K) (*K, *V)

func (*RedBlackTree[K, V]) Empty 

func (tree *RedBlackTree[K, V]) Empty() bool

func (*RedBlackTree[K, V]) Floor 

func (tree *RedBlackTree[K, V]) Floor(key K) (*K, *V)

func (*RedBlackTree[K, V]) Get 

func (tree *RedBlackTree[K, V]) Get(key K) *V

func (*RedBlackTree[K, V]) HasEntry 

func (tree *RedBlackTree[K, V]) HasEntry() bool

func (*RedBlackTree[K, V]) Left 

func (tree *RedBlackTree[K, V]) Left() (*K, *V)

func (*RedBlackTree[K, V]) Put 

func (tree *RedBlackTree[K, V]) Put(key K, value V)

func (*RedBlackTree[K, V]) Remove 

func (tree *RedBlackTree[K, V]) Remove(key K)

func (*RedBlackTree[K, V]) Size 

func (tree *RedBlackTree[K, V]) Size() int

func (*RedBlackTree[K, V]) String 

func (tree *RedBlackTree[K, V]) String() string

type Scc 

type Scc struct {
	// nは強連結成分分解後の頂点数
	Size int
	// Graphは強連結成分分解後のグラフ
	Graph [][]int
	// Componentsは強連結成分分解後の頂点(0-indexed)と、その頂点に対応する、もとのグラフの頂点(0-indexed)の配列
	Components [][]int
	// Nodesはもとのグラフの頂点(0-indexed)と、対応する新しい頂点(0-indexed)
	Nodes map[int]int
}

Sccは強連結成分分解の結果を表します。

type SegmentTree 

type SegmentTree[V any] struct {
	// Initは[0, n)のsegment treeを初期化します。
	// 各要素の値は単位元となります。
	// tested:
	//
	//	https://atcoder.jp/contests/abl/tasks/abl_d
	Init func(n int) *SegmentTree[V]

	// InitAsArrayはvalsで配列を初期化します。
	// 区間の長さはlen(vals)になります。
	// tested:
	//
	//	https://judge.yosupo.jp/problem/staticrmq
	InitAsArray func(arr []V) *SegmentTree[V]

	// Updateはi(0-based)番目の値をvalueに更新します。
	// tested:
	//
	//	https://atcoder.jp/contests/abl/tasks/abl_d
	Update func(i int, value V)

	// Queryは[l, r) (0-based)の計算値を返します。
	// tested:
	//
	//	https://atcoder.jp/contests/abl/tasks/abl_d
	Query func(l, r int) V
}

func NewSegmentTree 

func NewSegmentTree[V any](
	e func() V,
	calc func(a, b, ab *V),
) *SegmentTree[V]

NewSegmentTreeは区間和を扱うSegmentTreeを返します。 tested: 

https://atcoder.jp/contests/abl/tasks/abl_d

type Stack 

type Stack[T any] struct {

	// PushはこのStackの末尾に要素を追加します。
	Push func(value T)

	// PopはこのStackの末尾から要素を取り出し、その要素を返します。
	Pop func() T

	// PeekはこのStackの末尾の要素を返します。
	// 末尾の要素は削除されません。
	Peek func() T

	// CountはこのStackに保存されている要素の数を返します。
	Count func() int

	// HasElementsはこのStackに要素が設定されているかを判断します。
	HasElements func() bool

	// IsEmptyはこのStackが空かどうかを判断します。
	IsEmpty func() bool
	// contains filtered or unexported fields
}

Stackは先入れ後出しのデータ構造を表現します。

func NewStack 

func NewStack[T any]() *Stack[T]

type UnionFind 

type UnionFind struct {
	// contains filtered or unexported fields
}

UnionFind : UnionFind構造を保持する構造体

func NewUnionFind 

func NewUnionFind(n int) *UnionFind

NewUnionFindは、[0, n)のノードを持つUnion-Findを作る

func (*UnionFind) Root 

func (uf *UnionFind) Root(x int) int

Root はxのルートを得る

func (*UnionFind) Same 

func (uf *UnionFind) Same(x, y int) bool

Same はxとyが同じノードにいるかを判断する

func (*UnionFind) Size 

func (uf *UnionFind) Size(x int) int

Size は xの集合のサイズを返します。

func (*UnionFind) Unite 

func (uf *UnionFind) Unite(x, y int) bool

Unite はxとyを併合する。集合の構造が変更された(== 呼び出し前は異なる集合だった)かどうかを返す

type WeightedUnionFind 

type WeightedUnionFind struct {
	// contains filtered or unexported fields
}

重み付きUnion-Findは集合と、各ノードがルートからどれくらい距離があるかを管理します。

func NewWeightedUnionFind 

func NewWeightedUnionFind(n int) *WeightedUnionFind

NewWeightedUnionFindは重み付きUnion-Findの実装を返します。

func (*WeightedUnionFind) Diff 

func (uf *WeightedUnionFind) Diff(x, y int) int

weight[y]-weight[x]を返します。

func (*WeightedUnionFind) IsSame 

func (uf *WeightedUnionFind) IsSame(x, y int) bool

xとyが同じ集合にいるかを判断します。

func (*WeightedUnionFind) Merge 

func (uf *WeightedUnionFind) Merge(x, y, w int) bool

weight[y]-weight[x] = wとなるようにマージします

func (*WeightedUnionFind) Root 

func (uf *WeightedUnionFind) Root(x int) int

xが接続されているルートを返します。

func (*WeightedUnionFind) Weight 

func (uf *WeightedUnionFind) Weight(x int) int

xの重みを返します。

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.