godtype

package module
v0.0.0-...-2c06916 Latest Latest
Warning

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

 Go to latest Published: Jan 8, 2023 License: GPL-3.0 Imports: 4 Imported by: 0

README

godtype

This is the homemade thread-safe Go data type mentioned in my leetcode project, initally built to solve some leetcode problems and turns out to be quite useful in other places.

DEPRECATED

Use this new library instead, built on Go 1.18 with the supports generics & 100% test coverage.

Usage

Create a new struct:
  • Stack: godtype.NewStack()
  • Queue: godtype.NewQueue()
  • Deque: godtype.NewDeque()
  • MonotonicQueue: godtype.NewMonotonicQueue()
  • PriorityQueue: godtype.NewPQ(values interface{}, prios interface{}, popLowest bool)
  • LinkedHashmap: godtype.NewLmap()
  • UnionFind: godtype.NewUF(n int)
  • PatternFinder(KMP): godtype.NewPatternFinder(p string)
Method:
Operation Stack Queue Deque
insert at head - - PushFirst(elem interface{})
insert at end Push(elem interface{}) Push(elem interface{}) PushLast(elem interface{})
remove from head - Pop() interface{} PopFirst() interface{}
remove from end Pop() interface{} - PopLast() interface{}
check the head - Peek() interface{} PeekFirst() interface{}
check the end Peek() interface{} - PeekLast() interface{}
check is empty IsEmpty() bool IsEmpty() bool IsEmpty() bool
check size Size() int Size() int Size() int
Notice:

The element is interface{} type, do a type assertion if needed after a get method (eg. dq.PeekFirst().(int) > 0).

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func PrintBTreeBFS 

func PrintBTreeBFS(root *TreeNode)

func PrintBTreeDFS 

func PrintBTreeDFS(root *TreeNode)

func PrintList 

func PrintList(node *ListNode)

Types

type Dag 

type Dag struct {
	// the size of the graph
	Size int
	// adjacent table for each vertex
	AdjTable map[int][]int
	// stock the result of sort, "source" vertex on the top
	// the vertex "pointed to" at the bottom
	Sorted *Stack
	// contains filtered or unexported fields
}

func NewDag 

func NewDag(size int) *Dag

initialize the graph

func (*Dag) AddEdge 

func (d *Dag) AddEdge(fromV, toV int)

build the adjacent table

func (*Dag) TopologicalSort 

func (d *Dag) TopologicalSort()

type Deque 

type Deque struct {
	Elems []interface{}
	Lock  sync.RWMutex
}

func NewDeque 

func NewDeque() *Deque

func (*Deque) IsEmpty 

func (d *Deque) IsEmpty() bool

func (*Deque) PeekFirst 

func (d *Deque) PeekFirst() interface{}

func (*Deque) PeekLast 

func (d *Deque) PeekLast() interface{}

func (*Deque) PopFirst 

func (d *Deque) PopFirst() interface{}

func (*Deque) PopLast 

func (d *Deque) PopLast() interface{}

func (*Deque) PushFirst 

func (d *Deque) PushFirst(elem interface{})

func (*Deque) PushLast 

func (d *Deque) PushLast(elem interface{})

func (*Deque) Size 

func (d *Deque) Size() int

type DoublyLList 

type DoublyLList struct {
	Head, Tail *DoublyLNode
	Len        int
}

Doubly Linked List

func NewDoublyLList 

func NewDoublyLList() *DoublyLList

func (*DoublyLList) Delete 

func (dl *DoublyLList) Delete(node *DoublyLNode)

func (*DoublyLList) Pop 

func (dl *DoublyLList) Pop() *DoublyLNode

Pop from the beginning

func (*DoublyLList) Push 

func (dl *DoublyLList) Push(node *DoublyLNode)

Push at the end

type DoublyLNode 

type DoublyLNode struct {
	Key, Val   interface{}
	Prev, Next *DoublyLNode
}

Doubly Linked Node

func NewDoublyLNode 

func NewDoublyLNode(k, v interface{}) *DoublyLNode

type Elem 

type Elem struct {
	Value    interface{}
	Priority interface{}
	Index    int
}

type Heap 

type Heap []*Elem

func (Heap) Len 

func (h Heap) Len() int

Implement sort interface

func (Heap) Less 

func (h Heap) Less(i, j int) bool

Implement sort interface

func (*Heap) Pop 

func (h *Heap) Pop() interface{}

Implement heap interface

func (*Heap) Push 

func (h *Heap) Push(item interface{})

Implement heap interface

func (Heap) Swap 

func (h Heap) Swap(i, j int)

Implement sort interface

type ListNode 

type ListNode struct {
	Val  interface{}
	Next *ListNode
}

func NewList 

func NewList(l interface{}) *ListNode

type Lmap 

type Lmap struct {
	Map   map[interface{}]*DoublyLNode
	DList *DoublyLList
}

Linked Hash Map

func NewLmap 

func NewLmap() *Lmap

func (*Lmap) BecomeNewest 

func (lm *Lmap) BecomeNewest(k interface{})

func (*Lmap) Contains 

func (lm *Lmap) Contains(k interface{}) bool

func (*Lmap) Delete 

func (lm *Lmap) Delete(k interface{})

func (*Lmap) Get 

func (lm *Lmap) Get(k interface{}) interface{}

func (*Lmap) PopEldest 

func (lm *Lmap) PopEldest() *DoublyLNode

func (*Lmap) Put 

func (lm *Lmap) Put(k, v interface{})

func (*Lmap) Size 

func (lm *Lmap) Size() int

type MonotonicQueue 

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

func NewMonotonicQueue 

func NewMonotonicQueue() *MonotonicQueue

func (*MonotonicQueue) IsEmpty 

func (mq *MonotonicQueue) IsEmpty() bool

func (*MonotonicQueue) Max 

func (mq *MonotonicQueue) Max() interface{}

func (*MonotonicQueue) Pop 

func (mq *MonotonicQueue) Pop(elem interface{})

func (*MonotonicQueue) Push 

func (mq *MonotonicQueue) Push(elem interface{})

func (*MonotonicQueue) Size 

func (mq *MonotonicQueue) Size() int

type PatternFinder 

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

func NewPatternFinder 

func NewPatternFinder(p string) *PatternFinder

use KMP algorithm

func (*PatternFinder) FindIn 

func (pf *PatternFinder) FindIn(target string) []int

func (*PatternFinder) GetLPS 

func (pf *PatternFinder) GetLPS() []int

func (*PatternFinder) Pattern 

func (pf *PatternFinder) Pattern() []rune

type PriorityQueue 

type PriorityQueue struct {
	Data      Heap
	Lock      sync.RWMutex
	PopLowest bool
}

func NewPQ 

func NewPQ(values interface{}, prios interface{}, popLowest bool) *PriorityQueue

build a priority queue with a slice of value and a slice of priority

func (*PriorityQueue) Peek 

func (pq *PriorityQueue) Peek() interface{}

Pop without remove elem from PQ

func (*PriorityQueue) Pop 

func (pq *PriorityQueue) Pop() interface{}

func (*PriorityQueue) PopWithPrio 

func (pq *PriorityQueue) PopWithPrio() []interface{}

func (*PriorityQueue) Push 

func (pq *PriorityQueue) Push(value interface{}, prio interface{})

func (*PriorityQueue) Remove 

func (pq *PriorityQueue) Remove(value interface{}) interface{}

func (*PriorityQueue) Size 

func (pq *PriorityQueue) Size() int

type Queue 

type Queue struct {
	Elems []interface{}
	Lock  sync.RWMutex
}

func NewQueue 

func NewQueue() *Queue

func (*Queue) IsEmpty 

func (q *Queue) IsEmpty() bool

func (*Queue) Peek 

func (q *Queue) Peek() interface{}

func (*Queue) Pop 

func (q *Queue) Pop() interface{}

Pop from the queue's head

func (*Queue) Push 

func (q *Queue) Push(elem interface{})

Push to the queue's end

func (*Queue) Size 

func (q *Queue) Size() int

type Stack 

type Stack struct {
	Elems []interface{}
	Lock  sync.RWMutex
}

func NewStack 

func NewStack() *Stack

func (*Stack) IsEmpty 

func (s *Stack) IsEmpty() bool

func (*Stack) Peek 

func (s *Stack) Peek() interface{}

func (*Stack) Pop 

func (s *Stack) Pop() interface{}

func (*Stack) Push 

func (s *Stack) Push(elem interface{})

func (*Stack) Size 

func (s *Stack) Size() int

type TreeNode 

type TreeNode struct {
	Val   interface{}
	Left  *TreeNode
	Right *TreeNode
}

func NewBTree 

func NewBTree(elems []interface{}) *TreeNode

从数列(完全二叉树标准)构建树

type UF 

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

func NewUF 

func NewUF(n int) *UF

func (*UF) Count 

func (uf *UF) Count() int

Getters

func (*UF) FindRoot 

func (uf *UF) FindRoot(a int) int

find current node's root, in the same time reduce tree's height

func (*UF) IsLinked 

func (uf *UF) IsLinked(a, b int) bool

test if two nodes are already connected

func (*UF) Parent 

func (uf *UF) Parent() []int

func (*UF) SetCount 

func (uf *UF) SetCount(c int)

Setters

func (*UF) SetParent 

func (uf *UF) SetParent(p []int)

func (*UF) SetSize 

func (uf *UF) SetSize(s []int)

func (*UF) Size 

func (uf *UF) Size() []int

func (*UF) Union 

func (uf *UF) Union(a, b int)

connect two node by joining their roots; Do nothing if they are already connected

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.