Skip to content

chentaihan/container

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

43 Commits
array
array
 
 
binaryTree
binaryTree
 
 
btree
btree
 
 
common
common
 
 
demo
demo
 
 
hashmap
hashmap
 
 
heap
heap
 
 
link
link
 
 
lru
lru
 
 
pool
pool
 
 
queue
queue
 
 
set
set
 
 
skipLink
skipLink
 
 
stack
stack
 
 
trie
trie
 
 
.gitignore
.gitignore
 
 
README.md
README.md
 
 
go.mod
go.mod
 
 

Repository files navigation

Container

golang实现常用集合原理介绍      demo

常用集合实现

1：队列

type IQueue interface {
    Enqueue(val interface{})      //入队
    Dequeue() (interface{}, bool) //出队
    Empty() bool                  //队列是否为空
    Len() int                     //队列长度
    Cap() int                     //队列容量
    Peek() (interface{}, bool)    //取队首元素
    ToList() []interface{}        //转换成数组
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/queue"
)

func main() {
	queueTest()         //普通队列测试
	priorityQueueTest() //优先级队列测试
}

func queueTest() {
	size := 2000
	var q queue.IQueue = queue.NewQueue(size) //数组实现队列
	//var q queue.IQueue = queue.NewQueueLink() //链表实现队列
	for i := 0; i < size; i++ {
		q.Enqueue(i)
	}
	if q.Len() != size {
		fmt.Println("queue len error")
	}
	if q.Cap() != size {
		fmt.Println("queue cap error,cap=", q.Cap())
	}
	value, isOK := q.Peek()
	if isOK {
		if value.(int) != 0 {
			fmt.Println("queue peek error")
		}
	}

	for i := 0; i < size; i++ {
		q.Enqueue(i)
	}
	if q.Cap() != size*2 {
		fmt.Println("queue cap error,cap=", q.Cap())
	}
	count := q.Len()
	index := 0
	for !q.Empty() {
		q.Dequeue()
		index++
	}
	if count != index {
		fmt.Println(fmt.Sprintf("len = %v != count = %v", index, count))
	}
	for i := 0; i < size*8; i++ {
		q.Enqueue(i)
	}
	if q.Cap() != size*8 {
		fmt.Println(fmt.Sprintf("queue cap error,cap=%v,want cap=%v", q.Cap(), size*8))
	}
}

type integer int

func (i integer) GetPriority() int {
	return int(i)
}

func (i integer) GetHashCode() int {
	return int(i)
}

func priorityQueueTest() {
	count := 100
	heap := queue.NewPriorityQueue(count)
	for i := 0; i < count; i++ {
		heap.Push(integer(i))
	}
	if !heap.Contains(integer(20)) {
		fmt.Println("Contain error")
	}
	if !heap.Remove(integer(20)) {
		fmt.Println("remove error")
	}
	heap.Push(integer(20))
	for heap.Len() > 0 {
		l := heap.Len()
		val := heap.Pop()
		if val.GetHashCode() != count-l {
			fmt.Println("pop error", val.GetHashCode(), count-l)
		}
	}
	for i := 0; i < count; i++ {
		heap.Push(integer(i))
	}
	list := heap.GetArray()
	fmt.Println(list)
	heap.Pop()
	list = heap.GetArray()
	fmt.Println(list)
	heap.Push(integer(20))
	list = heap.GetArray()
	fmt.Println(list)
	for heap.Len() > 0 {
		heap.Pop()
	}
	if !heap.Empty() {
		fmt.Println("clear error")
	}
	heap.Clear()
	if !heap.Empty() {
		fmt.Println("clear error")
	}
}

2：栈

//栈接口

type IStack interface {
	Push(x interface{})       //入栈
	Pop() (interface{}, bool) //出栈
	Top() (interface{}, bool) //栈顶元素
	Empty() bool              //栈是否为空
	Len() int                 //栈元素个数
	Cap() int                 //栈容量
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/stack"
)

func main() {
	var s stack.IStack = stack.NewStack(100)
	//var s stack.IStack = stack.NewStackLink()
	size := 10
	for i := 0; i < size; i++ {
		s.Push(i)
	}
	if s.Len() != size {
		fmt.Println("len error")
	}
	fmt.Println("cap=", s.Cap())
	for !s.Empty() {
		if val, exist := s.Top(); exist {
			fmt.Println(val)
		}
		s.Pop()
	}
	if s.Len() != 0 {
		fmt.Println("empty error")
	}
}

3：排序数组

//数组接口

type IArray interface {
	Add(val IObject)                       //添加元素
	Get(index int) (IObject, bool)         //根据下标获取元素
	Index(val IObject) int                 //获取指定值对应的下标，不存在就返回-1
	RemoveIndex(index int) (IObject, bool) //删除对应下标的元素
	Remove(value IObject) int              //删除指定的值
	Len() int                              //元素个数
	Clear()                                //删除所有元素
	GetArray() []IObject                   //返回所有元素（不复制）
	Copy() []IObject                       //复制所有元素
}

type IObject interface {
	GetHashCode() int //按照这个函数排序
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/array"
)

type integer int

func (i integer) GetHashCode() int {
	return int(i)
}

func main() {
	tests := []struct {
		array  []integer
		result []integer
	}{
		{
			[]integer{1, 3, 2, 4, 6, 5, 9, 8, 7},
			[]integer{1, 2, 3, 4, 5, 6, 7, 8, 9},
		},
	}
	for index, test := range tests {
		as := array.NewArraySort(0)
		for i := 0; i < len(test.array); i++ {
			as.Add(test.array[i])
		}
		var result []array.IObject
		for i := 0; i < len(test.result); i++ {
			result = append(result, test.result[i])
		}
		list := as.GetArray()
		if !IntEqual(list, result) {
			fmt.Println(list, test.result)
			fmt.Println("add error ", index)
		}
		as.Remove(integer(1))
	}
}

func IntEqual(nums1, nums2 []array.IObject) bool {
	if len(nums1) != len(nums2) {
		return false
	}
	for i := 0; i < len(nums1); i++ {
		if nums1[i].GetHashCode() != nums2[i].GetHashCode() {
			return false
		}
	}
	return true
}

4：单链表

//链表接口
type ILinkList interface {
	PushFront(val interface{})        //首部添加元素
	PushBack(val interface{})         //尾部添加元素
	RemoveFront() (interface{}, bool) //删除首部元素，成功true，失败false
	RemoveBack() (interface{}, bool)  //删除尾部元素，成功true，失败false
	RemoveValue(val interface{}) int  ////删除指定值，返回被删除元素数量
	Front() (interface{}, bool)       //返回首部元素，存在true，不存在false
	Back() (interface{}, bool)        //返回尾部元素，存在true，不存在false
	Len() int                         //元素个数
	Exist(val interface{}) bool       //指定元素是否存在
	ToList() []interface{}            //转换成数组
	Clear()                           //删除所有元素
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/link"
)

func main() {
	list := link.NewLinkedList()
	const count = 20
	for i := 0; i < count; i++ {
		list.PushBack(i)
	}
	if list.Len() != count {
		fmt.Println("len error")
	}
	first, _ := list.Front()
	if first != 0 {
		fmt.Println("Front error")
	}
	last, _ := list.Back()
	if last != count-1 {
		fmt.Println("Back error")
	}

	list.RemoveFront()
	first, _ = list.Front()
	if first != 1 {
		fmt.Println("Front error")
	}
	list.RemoveBack()
	last, _ = list.Back()
	if last != count-2 {
		fmt.Println("Back error ", last)
	}
	if list.RemoveValue(10) != 1 {
		fmt.Println("RemoveValue error")
	}
	array := list.ToList()
	fmt.Println(array)
	for i := 0; i < count; i++ {
		list.PushBack(10)
	}
	array = list.ToList()
	fmt.Println(array)
	if list.RemoveValue(10) != count {
		fmt.Println("RemoveValue error")
	}
	array = list.ToList()
	fmt.Println(array)

	if list.Exist(10) {
		fmt.Println("Exist error")
	}
	list.PushBack(10)
	if !list.Exist(10) {
		fmt.Println("Exist error")
	}
}

4：Map

type IMap interface {
	Set(key string, value interface{})  //添加元素，已存在就覆盖
	Get(key string) (interface{}, bool) //根据key获取元素，bool：true存在，false不存在
	Exist(key string) bool              //判断key是否存在
	Remove(key string) bool             //删除指定的key
	Len() int                           //元素个数
	Clear()                             //清除所有元素
	Values() []interface{}              //获取所有值
	Keys() []string                     //获取所有key
	Marshal() ([]byte, error)           //序列化
	Unmarshal(data []byte) error        //反序列化
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/hashmap"
)

func main() {
	tests := []struct {
		key   string
		value string
	}{
		{
			"key1",
			"value1",
		},
		{
			"key2",
			"value2",
		},
		{
			"key3",
			"value3",
		},
		{
			"key4",
			"value4",
		},
		{
			"key5",
			"value5",
		},
	}
	sm := hashmap.NewMap()       //map简单封装
	//sm := hashmap.NewMapSync() //同步map
	//sm := hashmap.NewTreeMap() //二叉树map
	//sm := hashmap.NewLinkMap() //顺序map
	for _, test := range tests {
		sm.Set(test.key, test.value)
	}
	for _, test := range tests {
		value, _ := sm.Get(test.key)
		if value.(string) != test.value {
			fmt.Println("equal ", test.key, value.(string), test.value)
		}
		if !sm.Exist(test.key) {
			fmt.Println("exist ", test.key, test.value)
		}
	}
	if sm.Len() != len(tests) {
		fmt.Println("len: ", sm.Len(), len(tests))
	}
	if sm.Exist("asdfghjtre") {
		fmt.Println("exist ", "asdfghjtre")
	}
	data, _ := sm.Marshal()
	fmt.Println(string(data))
	fmt.Println("success")

	dataString := `{"key1":"value1","key2":"value2","key3":"value3","key4":"value4","key5":"value5","key6":"value6"}`
	err := sm.Unmarshal([]byte(dataString))
	if err != nil {
		fmt.Println(err)
	}
	for _, test := range tests {
		if !sm.Exist(test.key) {
			fmt.Println("exist ", test.key, test.value)
		}
	}
	if !sm.Exist("key6") {
		fmt.Println("key6 not exist ")
	}
	value6, _ := sm.Get("key6")
	if value6 != "value6" {
		fmt.Println("key6 value error ", value6)
	}
	sm.Clear()
	if sm.Len() != 0 {
		fmt.Println("clear ", sm.Len())
	}
}

5：Set

type ISet interface {
	Add(val int) bool    //添加元素
	Exist(val int) bool  //判断是否存在
	Remove(val int) bool //删除指定的值
	Len() int            //元素个数
	Clear()              //删除所有元素
	GetArray() []int     //返回所有元素（不复制）
	Copy() []int         //复制并返回所有元素
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/common"
	"github.com/chentaihan/container/set"
)

func main() {
	tests := []struct {
		list     []int
		sortList []int
		size     int
	}{
		{
			[]int{1, 1, 1, 1, 1, 1, 1},
			[]int{1},
			1,
		},
		{
			[]int{1, 3, 5, 7, 9, 2, 4, 6, 8, 0},
			[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
			10,
		},
	}

	for index, test := range tests {
		var s set.ISet = set.NewSet()
		for i := 0; i < len(test.list); i++ {
			s.Add(test.list[i])
		}
		if s.Len() != test.size {
			fmt.Println("size error", index)
		}
		if !common.IntEqualSort(s.GetArray(), test.sortList) {
			fmt.Println("add error", index)
		}
		s.Remove(1)
		s.Clear()
	}
}

6：二叉搜索树

//树接口

type ITree interface {
	Add(val IObject)                  //添加元素
	Find(val IObject) *TreeNode       //查找元素
	GetRoot() *TreeNode               //获取根节点
	Remove(val IObject) bool          //删除元素
	GetDepth() int                    //树深度
	GetCount() int                    //节点个数
	MinNode(root *TreeNode) *TreeNode //获取最小子节点（从当前节点开始查找）
	MaxNode(root *TreeNode) *TreeNode //获取最大子节点（从当前节点开始查找）
	ToList() []IObject                //获取所有节点值
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/tree"
)

type integer int

func (i integer) GetHashCode() int {
	return int(i)
}

func intEqual(nums1, nums2 []tree.IObject) bool {
	if (nums1 == nil && nums2 != nil) || (nums1 != nil && nums2 == nil) {
		return false
	}
	if len(nums1) != len(nums2) {
		return false
	}
	for i := 0; i < len(nums1); i++ {
		if nums1[i].GetHashCode() != nums2[i].GetHashCode() {
			return false
		}
	}
	return true
}


func main() {
	tests := []struct {
		nums       []integer
		depth      int
		count      int
		minVal     int
		maxVal     int
		findVal    int
		findResult bool
		list       []integer
	}{
		{
			[]integer{5, 4, 8, 2, 3, 9, 1, 6, 7, 15, 12, 20, 14, 11, 25, 18, 30},
			7,
			17,
			1,
			30,
			13,
			false,
			[]integer{1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 15, 18, 20, 25, 30},
		},
	}
	for _, test := range tests {
		root := tree.NewBinaryTree()
		for i := 0; i < len(test.nums); i++ {
			root.Add(test.nums[i])
		}
		if root.GetDepth() != test.depth {
			fmt.Println("GetDepth error")
		}
		count := root.GetCount()
		if count != test.count {
			fmt.Println("GetCount error")
		}
		if test.minVal != root.MinNode(root.GetRoot()).Val.GetHashCode() {
			fmt.Println("MinNode error")
		}
		if test.maxVal != root.MaxNode(root.GetRoot()).Val.GetHashCode() {
			fmt.Println("MaxNode error")
		}
		if test.findResult != (root.Find(integer(test.findVal)) != nil) {
			fmt.Println("Find error")
		}
		var list []tree.IObject
		for i := 0; i < len(test.list); i++ {
			list = append(list, test.list[i])
		}
		if !intEqual(list, root.ToList()) {
			fmt.Println("ToList error")
		}
	}
}

6：LRU

/**
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，
选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，
用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，
选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
*/

type ILru interface {
	Add(key string, val interface{})       //添加元素
	Get(key string) (interface{}, bool)    //获取元素，不存在返回false
	Remove(key string) (interface{}, bool) //删除元素，删除失败返回false
	Len() int                              //元素个数
	Cap() int                              //容量
	SetCap(cap int)                        //调整容量，只缩不增
	Clear()                                //删除所有元素
	Values() []interface{}                 //获取所有值
	Keys() []string                        //获取所有key
}

/**
基于过期时间的LRU，将元素保存到集合中，expireTime秒后自动删除
采取的是惰性删除机制，访问任何一个接口，都会删除一定数量的过期的数据
*/
type ILruTime interface {
	// 添加元素，如果已经存在的就更新过期时间
	// expireTime秒后自动删除
	Add(val IObject, expireTime int64)
	//获取元素，不存在返回false
	Get(hashCode int) (IObject, bool)
	//获取队首元素，即将被删除的元素
	Peek() (IObject, bool)
	//元素个数
	Len() int
	//删除所有元素
	Clear()
	//获取所有值
	GetArray() []IObject
	//删除一定数量的过期数据，返回删除数量
	RemoveOutOfTime() int
	//停止处理
	Stop()
}
package main

import (
	"fmt"
	"github.com/chentaihan/container/cache"
	"github.com/chentaihan/container/common"
	"strconv"
)

func toIntArray(array []interface{}) []int {
	list := make([]int, len(array))
	for i := 0; i < len(list); i++ {
		list[i] = common.ToInt(array[i])
	}
	return list
}

func main() {
	tests := []struct {
		list []int
		cap  int
	}{
		{
			[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
			10,
		},
		{
			[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
			11,
		},
	}

	for index, test := range tests {
		lru := lru.NewLru(test.cap)
		for i := 0; i < len(test.list); i++ {
			lru.Add(strconv.Itoa(test.list[i]), test.list[i])
			list := toIntArray(lru.Values())
			var array []int
			if i < test.cap {
				array = test.list[:i+1]
			} else {
				ii := i - test.cap + 1
				array = test.list[ii : ii+test.cap]
			}
			if !common.IntEqualSort(list, array) {
				fmt.Println(list, array)
				fmt.Println("add error", index, i, test.cap)
			}
			fmt.Println(index, i, "success")
		}
	}
}

7：堆

//堆接口

type IObject interface {
	GetHashCode() int //按照这个函数排序
}

type IHeap interface {
	Push(h IObject)          //添加元素
	Pop() IObject            //删除顶部元素（第0个元素）
	Peek() IObject           //获取顶部元素（第0个元素）
	Remove(h IObject) bool   //删除指定下标元素
	Len() int                //元素个数
	Cap() int                //容量
	Empty() bool             //堆是否为空
	Exist(h IObject) bool    //是否包含指定元素
	Clear()                  //删除所有元素
	GetArray() []IObject     //获取元素数组（不复制）
	Copy() []IObject         //复制所有元素
}
package main

import (
	"fmt"
	heap2 "github.com/chentaihan/container/heap"
)

type integer int

func (i integer) GetHashCode() int {
	return int(i)
}

func main() {
	count := 100
	heap := heap2.NewBigHeap(count) //大堆
	//heap := heap2.NewSmallHeap(count) //小堆
	for i := 0; i < count; i++ {
		heap.Push(integer(i))
	}
	if !heap.Contains(integer(20)) {
		fmt.Println("Contain error")
	}
	if !heap.Remove(integer(20)) {
		fmt.Println("remove error")
	}
	heap.Push(integer(20))
	for heap.Len() > 0 {
		l := heap.Len()
		val := heap.Pop()
		if val.GetHashCode() != l-1 {
			fmt.Println("pop error", val.GetHashCode(), l-1)
		}
	}
	for i := 0; i < count; i++ {
		heap.Push(integer(i))
	}
	list := heap.GetArray()
	fmt.Println(list)
	heap.Pop()
	list = heap.GetArray()
	fmt.Println(list)
	heap.Push(integer(20))
	list = heap.GetArray()
	fmt.Println(list)
	for heap.Len() > 0 {
		heap.Pop()
	}
	if !heap.Empty() {
		fmt.Println("clear error")
	}
	heap.Clear()
	if !heap.Empty() {
		fmt.Println("clear error")
	}

}

About

golang实现常用集合

Topics

go map golang set stack queue datastructures lru pool trie heap linkedlist skiplist binarytree btree

Resources

Readme
Activity

Stars

28 stars

Watchers

3 watching

Forks

16 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages