structure_old/priority_list/priority_list.go

package plist

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

// INode 比较的必须继承的接口
type INode interface {
	Compare(v INode) bool

	// GetValue 获取值
	GetValue() interface{}
	// SetValue 设置值
	SetValue(v interface{})

	GetPrev() INode
	SetPrev(INode)
	GetNext() INode
	SetNext(INode)
}

// Node 优先链表的节点
type Node struct {
	INode
	prev, next INode
	// isrelease  bool
	value interface{}
}

// NewNode 创建一个PriorityList 节点
func NewNode(v interface{}) *Node {
	n := new(Node)
	n.SetValue(v)
	return n
}

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

// SetValue 设置值
func (node *Node) SetValue(v interface{}) {
	node.value = v
}

// GetPrev 获取left值
func (node *Node) GetPrev() INode {
	return node.prev
}

// SetPrev 设置left值
func (node *Node) SetPrev(n INode) {
	node.prev = n
}

// GetNext 设置right值
func (node *Node) GetNext() INode {
	return node.next
}

// SetNext 获取left值
func (node *Node) SetNext(n INode) {
	node.next = n
}

func (node *Node) String() string {
	return spew.Sprint(node.value)
}

// PriorityList 优先列表
type PriorityList struct {
	head INode
	tail INode

	size int
}

// Size 长度
func (pl *PriorityList) Size() int {
	return pl.size
}

// Clear 清空链表, 如果外部有引用其中一个节点 要把节点Prev Next值为nil, 三色标记
func (pl *PriorityList) Clear() {
	pl.head = nil
	pl.tail = nil
	pl.size = 0
}

// GetCompare 获取比较的节点 compare >= 11这个节点小的值 [15,12,9,8,6,1] = 9
func (pl *PriorityList) GetCompare(cNode INode) INode {
	cur := pl.head
	for cur != nil {
		if !cur.Compare(cNode) {
			return cur
		}
		cur = cur.GetNext()
	}
	return nil
}

// GetCompareReverse 逆序获取比较的节点 compare >= 11这个节点大的值 [15,12,9,8,6,1] = 12
func (pl *PriorityList) GetCompareReverse(cNode INode) INode {
	cur := pl.tail
	for cur != nil {
		if cur.Compare(cNode) {
			return cur
		}
		cur = cur.GetPrev()
	}
	return nil
}

// ForEach 顺序遍历
func (pl *PriorityList) ForEach(eachfunc func(INode) bool) {
	cur := pl.head
	for cur != nil {
		if !eachfunc(cur) {
			break
		}
		cur = cur.GetNext()
	}
}

// ForEachReverse 逆遍历
func (pl *PriorityList) ForEachReverse(eachfunc func(INode) bool) {
	cur := pl.tail
	for cur != nil {
		if !eachfunc(cur) {
			break
		}
		cur = cur.GetPrev()
	}
}

// Get 获取索引长度
func (pl *PriorityList) Get(idx int) INode {
	if idx >= pl.size {
		return nil
	}
	cur := pl.head
	for i := 0; i < idx; i++ {
		cur = cur.GetNext()
	}
	return cur
}

// GetReverse 腻序获取索引长度
func (pl *PriorityList) GetReverse(idx int) INode {
	if idx >= pl.size {
		return nil
	}
	cur := pl.tail
	for i := 0; i < idx; i++ {
		cur = cur.GetPrev()
	}
	return cur
}

// Remove 删除节点
func (pl *PriorityList) Remove(node INode) {

	if pl.size <= 1 {
		pl.head = nil
		pl.tail = nil
		if pl.size == 0 {
			panic("the node is not in this list, node:" + spew.Sprint(node))
		}
		pl.size = 0
		return
	}

	pl.size--
	prev := node.GetPrev()
	next := node.GetNext()

	if prev == nil {
		pl.head = next
		next.SetPrev(nil)
		node.SetNext(nil)
	} else if next == nil {
		pl.tail = prev
		prev.SetNext(nil)
		node.SetPrev(nil)
	} else {
		prev.SetNext(next)
		next.SetPrev(prev)

		node.SetPrev(nil)
		node.SetNext(nil)
	}
}

// RemoveIndex 删除节点 并获取该节点
func (pl *PriorityList) RemoveIndex(idx int) INode {
	result := pl.Get(idx)
	pl.Remove(result)
	return result
}

// RemoveReverseIndex 逆顺序删除节点 并获取该节点
func (pl *PriorityList) RemoveReverseIndex(idx int) INode {
	result := pl.GetReverse(idx)
	pl.Remove(result)
	return result
}

func (pl *PriorityList) String() string {
	content := "["

	cur := pl.head
	for cur != nil {
		content += spew.Sprint(cur.GetValue()) + ","
		cur = cur.GetNext()
	}

	if content[len(content)-1:] == "," {
		content = content[:len(content)-1]
	}

	content += "]"
	return content
}

// Insert 插入节点
func (pl *PriorityList) Insert(node INode) {
	pl.size++
	if pl.head == nil {
		pl.head = node
		pl.tail = node
		return
	}

	cur := pl.head
	for {
		if !cur.Compare(node) {
			// 插入该值
			prev := cur.GetPrev()
			if prev == nil {
				pl.head.SetPrev(node)
				node.SetNext(pl.head)
				pl.head = node
			} else {
				prev.SetNext(node)
				node.SetNext(cur)
				cur.SetPrev(node)
				node.SetPrev(prev)
			}

			return
		}

		next := cur.GetNext()
		if next == nil {
			cur.SetNext(node)
			node.SetPrev(cur)
			pl.tail = node
			return
		}
		cur = next

	}

}

// New 创建 PriorityList
func New() *PriorityList {
	return new(PriorityList)
}