curl2info/structure.go

package curl2info

import (
	"container/heap"
	"log"
	"strings"

	"github.com/davecgh/go-spew/spew"
)

// trieWord Trie 需要的Word接口
type trieWord interface {
	GetWord() string
}

// TrieStrWord 最简单的TrieWord 结构
type trieStrWord string

// GetWord 获取单词
func (tsw *trieStrWord) GetWord() string {
	return (string)(*tsw)
}

// Trie 前缀树
type hTrie struct {
	isWord bool
	value  interface{}
	char   byte
	prev   *hTrie
	next   map[byte]*hTrie
}

// newTrie Initialize your data structure here.
func newTrie() *hTrie {
	return &hTrie{next: make(map[byte]*hTrie)}
}

// Insert a word into the trie.
func (trie *hTrie) Insert(iword trieWord) {
	cur := trie
	word := iword.GetWord()
	l := len(word)

	for i := 0; i < l; i++ {
		c := word[i]
		if next, ok := cur.next[c]; ok {
			cur = next
		} else {
			create := newTrie()
			cur.next[c] = create
			create.char = c
			create.prev = cur
			cur = create
		}
	}

	cur.isWord = true
	cur.value = iword
}

// AllWords 所有单词
func (trie *hTrie) AllWords() []string {
	var result []string
	for _, v := range trie.next {
		look(v, "", &result)
	}
	return result
}

func look(cur *hTrie, content string, result *[]string) {
	content += string(cur.char)
	if cur.isWord {
		*result = append(*result, content)
	}
	for _, v := range cur.next {
		look(v, content, result)
	}
}

// Remove 移除单词
func (trie *hTrie) Remove(word string) {
	cur := trie
	l := len(word)
	for i := 0; i < l; i++ {
		c := word[i]
		if next, ok := cur.next[c]; ok {
			cur = next
		} else {
			return
		}
	}

	if cur != nil {
		cur.isWord = false
		cur.value = nil

		lastchar := cur.char

		if len(cur.next) == 0 {
			for cur.isWord != true && cur.prev != nil {
				lastchar = cur.char
				cur = cur.prev
				if len(cur.next) > 1 {
					return
				}
			}
			delete(cur.next, lastchar)
		}
	}
}

// SearchMostPrefix Returns if the word is in the trie.
func (trie *hTrie) SearchDepth(iword trieWord) interface{} {
	cur := trie
	word := iword.GetWord()

	l := len(word)

	var result interface{}
	for i := 0; i < l; i++ {
		c := word[i]
		if next, ok := cur.next[c]; ok {
			cur = next
			if cur.isWord {
				result = cur.value
			} else {
				result = nil
			}
		} else {
			return result
		}
	}
	return result
}

// Match Returns if the word is in the trie.
func (trie *hTrie) Match(iword trieWord) interface{} {
	cur := trie
	word := iword.GetWord()

	l := len(word)
	for i := 0; i < l; i++ {
		c := word[i]
		if next, ok := cur.next[c]; ok {
			cur = next
		} else {
			return nil
		}
	}

	return cur.value
}

// StartsWith Returns if there is any word in the trie that starts with the given prefix. */
func (trie *hTrie) StartsWith(prefix string) bool {
	cur := trie
	l := len(prefix)
	for i := 0; i < l; i++ {
		c := prefix[i]
		if next, ok := cur.next[c]; ok {
			cur = next
		} else {
			return false
		}
	}
	return true
}

// 优先队列 所在的域

// parseQueue for Heap, Container List
type parseQueue []*parseFunction

// parseFunction 优先执行参数
type parseFunction struct {
	ExecuteFunction func(u *CURL, soption string)
	ParamCURL       *CURL
	ParamData       string
	Priority        int
}

// Execute 执行 函数
func (pf *parseFunction) Execute() {
	pf.ExecuteFunction(pf.ParamCURL, pf.ParamData)
}

// Swap 实现sort.Iterface
func (nodes *parseQueue) Swap(i, j int) {
	ns := *nodes
	ns[i], ns[j] = ns[j], ns[i]
}

// Less Priority Want Less
func (nodes *parseQueue) Less(i, j int) bool {
	ns := *nodes
	return ns[i].Priority < ns[j].Priority
}

// Push 实现heap.Interface接口定义的额外方法
func (nodes *parseQueue) Push(exec interface{}) {
	*nodes = append(*nodes, exec.(*parseFunction))
}

// Pop 堆顶
func (nodes *parseQueue) Pop() (exec interface{}) {
	nlen := nodes.Len()
	exec = (*nodes)[nlen-1]    // 返回删除的元素
	*nodes = (*nodes)[:nlen-1] // [n:m]不包括下标为m的元素
	return exec
}

// Len len(nodes)
func (nodes *parseQueue) Len() int {
	return len(*nodes)
}

// pQueueExecute 优先函数队列
type pQueueExecute struct {
	nodes parseQueue
}

// newPQueueExecute Create A pQueueExecute
func newPQueueExecute() *pQueueExecute {
	pe := &pQueueExecute{}
	pe.nodes = make(parseQueue, 0)
	heap.Init(&pe.nodes)
	return pe
}

// Push Create A pQueueExecute
func (pqe *pQueueExecute) Push(exec *parseFunction) {
	heap.Push(&pqe.nodes, exec)
}

// Pop Create A pQueueExecute
func (pqe *pQueueExecute) Pop() *parseFunction {
	return heap.Pop(&pqe.nodes).(*parseFunction)
}

// Len Create A pQueueExecute
func (pqe *pQueueExecute) Len() int {
	return pqe.nodes.Len()
}

// func (pqe *pQueueExecute) String() string {
// 	content := ""
// 	for _, node := range pqe.nodes {
// 		content += strconv.Itoa(node.Prioty)
// 		content += " "
// 	}
// 	return content
// }

// CNode 循环链表 三色标记 不确定是否会清除循环引用, 网上说会
type CNode struct {
	value interface{}
	prev  *CNode
	next  *CNode
}

// GetValue 获取到Node的值
func (node *CNode) GetValue() interface{} {
	return node.value
}

// SetValue 获取到Node的值
func (node *CNode) SetValue(value interface{}) {
	node.value = value
}

// CircularLinked 循环链表
type CircularLinked struct {
	cursor *CNode
	head   *CNode
	tail   *CNode
	size   uint64
}

// NewCircularLinked create a CircularLinked
func NewCircularLinked(values ...interface{}) *CircularLinked {
	list := &CircularLinked{}
	if len(values) > 0 {
		list.Append(values...)
	}
	return list
}

// Cursor get current Cursor
func (list *CircularLinked) Cursor() *CNode {
	if list.cursor == nil {
		list.cursor = list.head
	}
	return list.cursor
}

// MoveNext get next Cursor
func (list *CircularLinked) MoveNext() *CNode {
	if list.cursor == nil {
		list.cursor = list.head
	}
	list.cursor = list.cursor.next
	return list.cursor
}

// MovePrev get prev Cursor
func (list *CircularLinked) MovePrev() *CNode {
	if list.cursor == nil {
		list.cursor = list.head
	}
	list.cursor = list.cursor.prev
	return list.cursor
}

// CursorToHead cursor move to head
func (list *CircularLinked) CursorToHead() *CNode {
	list.cursor = list.head
	return list.cursor
}

// CursorToTail cursor move to tail
func (list *CircularLinked) CursorToTail() *CNode {
	list.cursor = list.tail
	return list.cursor
}

// GetLoopValues 获取从头到尾的值
func (list *CircularLinked) GetLoopValues() []*CNode {
	var result []*CNode

	if list.head != nil {
		result = append(result, list.head)
		for cur := list.head.next; cur != list.head; cur = cur.next {
			result = append(result, cur)
		}
	}
	return result
}

// Append a value (one or more) at the end of the list (same as Append())
func (list *CircularLinked) Append(values ...interface{}) {
	for _, value := range values {
		node := &CNode{value: value}
		if list.size == 0 {
			list.head = node
			list.tail = node
			node.next = node
			node.prev = node
		} else {
			list.tail.next = node
			node.next = list.head
			node.prev = list.tail
			list.tail = node
		}
		list.size++
	}
}

// Remove 移除一些节点
func (list *CircularLinked) Remove(node *CNode) {

	switch list.size {
	case 0:
		list.errorNotInList(node)
	case 1:
		if list.head == node {
			list.head = nil
			list.tail = nil
			node.next = nil
			node.prev = nil
			list.cursor = nil
			list.size--
		} else {
			list.errorNotInList(node)
		}
	case 2:

		node.prev = nil
		node.next = nil

		switch node {
		case list.head:
			list.head = list.tail
			list.tail.prev = list.head
			list.head.next = list.tail
			list.cursor = list.head
			list.size--
		case list.tail:
			list.tail = list.head
			list.tail.prev = list.head
			list.head.next = list.tail
			list.cursor = list.head
			list.size--
		default:
			list.errorNotInList(node)
		}

	default:
		switch node {
		case list.head:
			_, next := list.cutAndSplice(node)
			list.size--
			list.head = next
			if list.cursor == node {
				list.cursor = next
			}
		case list.tail:
			prev, _ := list.cutAndSplice(node)
			list.size--
			list.tail = prev
			if list.cursor == node {
				list.cursor = prev
			}
		default:
			_, next := list.cutAndSplice(node)
			list.size--
			if list.cursor == node {
				list.cursor = next
			}
		}
	}

}

// LookCursor for list show
func (list *CircularLinked) LookCursor() string {
	cursor := list.Cursor()

	content := "->["
	cur := list.head
	if list.size != 0 {
		for size := uint64(0); size < list.size; size++ {
			if cursor == cur {
				content += "(" + spew.Sprint(cur.value) + ")" + ", "
			} else {
				content += spew.Sprint(cur.value) + ", "
			}

			cur = cur.next
		}
	}
	content = strings.TrimRight(content, ", ")
	showlen := len(content)
	if showlen >= 64 {
		showlen = 64
	}
	content += "]" + content[0:showlen] + " ..."
	return content
}

// Clear for list show
func (list *CircularLinked) Clear() {
	if list.size != 0 {
		list.head.prev = nil
		list.tail.next = nil
		list.head = nil
		list.tail = nil
		list.cursor = nil
		list.size = 0
	}
}

// Size for list show
func (list *CircularLinked) Size() uint64 {
	return list.size
}

func (list *CircularLinked) errorNotInList(node *CNode) {
	log.Println("the node value ", spew.Sprint(node), " is not in list")
}

// cutAndSplice 不考虑边界情况 上层使用的是否判断
func (list *CircularLinked) cutAndSplice(node *CNode) (prev, next *CNode) {
	prev = node.prev
	next = node.next

	prev.next = next
	next.prev = prev

	node.prev = nil
	node.next = nil

	return prev, next
}