godata

README

godata

Basic data structures and operations written in Go which golang.org/pkg/container don't support such as stack, queue, etc.

Quick start

package main
import(
  "github.com/googege/godata"
)
func main(){
// stack
    stack := godata.NewStack(5)
    stack.Push(1)
    stack.Length()
    stack.Top()
    stack.Pop()
// trie
    trie := NewTrie()
    trie.Insert("hello world")
    trie.Insert("hello China")
    trie.Insert("hello My dear")
    trie.Search("hello world")
    trie.StartWith("he")
    trie.Image("he")
}

HERE

项目	介绍
对我的赞助
便宜服务器推荐	阿里云，梯子服务器:支持支付宝
微信公众号
知识讨论微信群
我的社交平台	b站，YouTube，微博，抖音：googege

Documentation

Index

• Constants
• func HashShower(data []byte, seed uint32) uint64
• func PopMin(m *MinHeap) int
• func PushMin(m *MinHeap, value int)
• func TopMin(m *MinHeap) int
• type BitMap
  • func NewBitMap(max uint64) *BitMap
  • func (b *BitMap) Add(num uint64)
  • func (b *BitMap) Delete(num uint64)
  • func (b *BitMap) Init()
  • func (b *BitMap) IsExit(num uint64) bool
• type BloomFilter
  • func NewBloomFilter(k int) *BloomFilter
  • func (b *BloomFilter) Add(value []byte)
  • func (b *BloomFilter) IsExit(value []byte) bool
• type DNode
  • func (d *DNode) DFS(ma map[*DNode]int, value interface{}) *DNode
• type LRUCache
  • func NewLRU(capacity int) LRUCache
  • func (l *LRUCache) Get(key int) int
  • func (l *LRUCache) Put(key int, value int)
  • func (l *LRUCache) ReBuild()
• type LRUNode
• type MinHeap
  • func (h MinHeap) Len() int
  • func (h MinHeap) Less(i, j int) bool
  • func (h *MinHeap) Pop() interface{}
  • func (h *MinHeap) Push(x interface{})
  • func (h MinHeap) Swap(i, j int)
• type Node
  • func (n *Node) BFS(value interface{}) *Node
• type Queue
  • func NewQueue(count int) *Queue
  • func (q *Queue) Length() int
  • func (q *Queue) Pop() interface{}
  • func (q *Queue) PopBack() interface{}
  • func (q *Queue) Push(value interface{}) int
  • func (q *Queue) Top() interface{}
• type Stack
  • func NewStack(count int) *Stack
  • func (s *Stack) Length() int
  • func (s *Stack) Pop() interface{}
  • func (s *Stack) Push(v interface{}) int
  • func (s *Stack) Top() interface{}
• type Trie
  • func NewTrie() *Trie
  • func (t *Trie) Image(prefix string) [][]rune
  • func (t *Trie) Insert(word string)
  • func (t *Trie) Search(word string) bool
  • func (t *Trie) StartsWith(prefix string) (bool, *Trie)
• type UnionFind
  • func NewUnionFind(roots int) *UnionFind
  • func (u *UnionFind) FindRoot(i int) int
  • func (u *UnionFind) Union(x, y int)

Constants

const (
	MAX_DB = 8388609
)

Functions

func HashShower

func HashShower(data []byte, seed uint32) uint64

this HashShower fuction is fast but not safety.

func PopMin

func PopMin(m *MinHeap) int

func PushMin

func PushMin(m *MinHeap, value int)

func TopMin

func TopMin(m *MinHeap) int

Types

type BitMap

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

位图

func NewBitMap

func NewBitMap(max uint64) *BitMap

return a new bit map. if max > 2^64-1 ,return nil

func (*BitMap) Add

func (b *BitMap) Add(num uint64)

is right return true ,or false

func (*BitMap) Delete

func (b *BitMap) Delete(num uint64)

func (*BitMap) Init

func (b *BitMap) Init()

init the bitMap.

func (*BitMap) IsExit

func (b *BitMap) IsExit(num uint64) bool

type BloomFilter

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

func NewBloomFilter

func NewBloomFilter(k int) *BloomFilter

max is the max of bitmap number k is the number of HashShower fuction.

func (*BloomFilter) Add

func (b *BloomFilter) Add(value []byte)

add data

func (*BloomFilter) IsExit

func (b *BloomFilter) IsExit(value []byte) bool

is exit.

type DNode

type DNode struct {
	Value interface{}
	Child []*DNode
}

func (*DNode) DFS

func (d *DNode) DFS(ma map[*DNode]int, value interface{}) *DNode

type LRUCache

type LRUCache struct {
	Cache map[int]*list.Element
	Cap   int
	List  *list.List
}

func NewLRU

func NewLRU(capacity int) LRUCache

new a LRU

func (*LRUCache) Get

func (l *LRUCache) Get(key int) int

exist:value, no:-1

func (*LRUCache) Put

func (l *LRUCache) Put(key int, value int)

put a new data

func (*LRUCache) ReBuild

func (l *LRUCache) ReBuild()

Rebuild the LRU.

type LRUNode

type LRUNode struct {
	Key, Value int
}

type MinHeap

type MinHeap []int

func (MinHeap) Len

func (h MinHeap) Len() int

func (MinHeap) Less

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

func (*MinHeap) Pop

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

func (*MinHeap) Push

func (h *MinHeap) Push(x interface{})

func (MinHeap) Swap

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

type Node

type Node struct {
	Value interface{}
	Child []*Node
}

func (*Node) BFS

func (n *Node) BFS(value interface{}) *Node

寻找到目标值，并且返回目标struct. node是要加入搜索的root节点，value是目标值

type Queue

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

func NewQueue

func NewQueue(count int) *Queue

return cap of the slice.

func (*Queue) Length

func (q *Queue) Length() int

func (*Queue) Pop

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

return the top of queue,and delete a node of the queue.

func (*Queue) PopBack

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

func (*Queue) Push

func (q *Queue) Push(value interface{}) int

return length of the queue

func (*Queue) Top

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

type Stack

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

func NewStack

func NewStack(count int) *Stack

return the cap of the slice.

func (*Stack) Length

func (s *Stack) Length() int

func (*Stack) Pop

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

func (*Stack) Push

func (s *Stack) Push(v interface{}) int

func (*Stack) Top

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

type Trie

type Trie struct {
	// 都是存在于children中的
	Children map[rune]*Trie
	IsWord   bool
}

support all utf8 code.

func NewTrie

func NewTrie() *Trie

* Initialize your data structure here.

func (*Trie) Image

func (t *Trie) Image(prefix string) [][]rune

func (*Trie) Insert

func (t *Trie) Insert(word string)

* Inserts a word into the trie.

func (*Trie) Search

func (t *Trie) Search(word string) bool

* Returns if the word is in the trie.

func (*Trie) StartsWith

func (t *Trie) StartsWith(prefix string) (bool, *Trie)

* Returns if there is any word in the trie that starts with the given prefix.

type UnionFind

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

func NewUnionFind

func NewUnionFind(roots int) *UnionFind

new a union & find.

func (*UnionFind) FindRoot

func (u *UnionFind) FindRoot(i int) int

寻找老大的过程

func (*UnionFind) Union

func (u *UnionFind) Union(x, y int)