lastack.go

package lastack

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

type Node struct {
	elements []interface{}
	cur      int
	down     *Node
}

type Stack struct {
	top   *Node
	cache *Node
	size  uint
}

func assertImplementation() {
	var _ stack.IStack = (*Stack)(nil)
}

func (as *Stack) grow() bool {
	if as.top.cur+1 == cap(as.top.elements) {

		var grownode *Node
		if as.cache != nil {
			grownode = as.cache
			grownode.cur = -1
			as.cache = nil
		} else {
			var growsize uint
			if as.size <= 256 {
				growsize = as.size << 1
			} else {
				growsize = 256 + as.size>>2
			}
			grownode = &Node{elements: make([]interface{}, growsize, growsize), cur: -1}
		}

		grownode.down = as.top
		as.top = grownode
		return true
	}

	return false
}

func (as *Stack) cacheRemove() bool {
	if as.top.cur == 0 && as.top.down != nil {
		as.cache = as.top
		as.top = as.top.down
		as.cache.down = nil
		return true
	}

	return false
}

func New() *Stack {
	s := &Stack{}
	s.size = 0
	s.top = &Node{elements: make([]interface{}, 8, 8), cur: -1}
	return s
}

func NewWithCap(cap int) *Stack {
	s := &Stack{}
	s.size = 0
	s.top = &Node{elements: make([]interface{}, cap, cap), cur: -1}
	return s
}

func (as *Stack) Clear() {
	as.size = 0

	as.top.down = nil
	as.top.cur = -1
}

func (as *Stack) Empty() bool {
	return as.size == 0
}

func (as *Stack) Size() uint {
	return as.size
}

// String 左为Top
func (as *Stack) String() string {
	content := ""
	cur := as.top
	for ; cur != nil; cur = cur.down {
		for i, _ := range cur.elements {
			if cur.cur >= i {
				content += spew.Sprint(cur.elements[cur.cur-i]) + " "
			}
		}
	}

	if len(content) > 0 {
		content = content[0 : len(content)-1]
	} else {
		content = ""
	}

	return content
}

func (as *Stack) Values() []interface{} {
	result := make([]interface{}, as.size, as.size)

	cur := as.top
	n := 0
	for ; cur != nil; cur = cur.down {
		for i, _ := range cur.elements {
			if cur.cur >= i {
				result[n] = cur.elements[cur.cur-i]
				n++
			}
		}
	}

	return result
}

func (as *Stack) Index(idx int) (interface{}, bool) {
	if idx < 0 {
		return nil, false
	}

	cur := as.top
	for cur != nil && idx-cur.cur > 0 {
		idx = idx - cur.cur - 1
		cur = cur.down
	}

	if cur == nil {
		return nil, false
	}

	return cur.elements[cur.cur-idx], true
}

func (as *Stack) Push(v interface{}) {
	as.grow()
	as.top.cur++
	as.top.elements[as.top.cur] = v
	as.size++
}

func (as *Stack) Pop() (interface{}, bool) {
	if as.size <= 0 {
		return nil, false
	}

	as.size--
	if as.cacheRemove() {
		return as.cache.elements[as.cache.cur], true
	}

	epop := as.top.elements[as.top.cur]
	as.top.cur--
	return epop, true
}

func (as *Stack) Peek() (interface{}, bool) {
	if as.size <= 0 {
		return nil, false
	}
	return as.top.elements[as.top.cur], true
}