focus/stack/listarraystack/lastack.go

174 lines
2.8 KiB
Go
Raw Permalink Normal View History

new file: .gitignore new file: LICENSE new file: README.md new file: compare/compare.go new file: for_test.go new file: heap/heap.go new file: heap/heap_test.go new file: interface.go new file: lastack/lastack.go new file: lastack/lastack_test.go new file: list/list.go new file: list/list_test.go new file: map/hashmap/hashmap.go new file: map/hashmap/hashmap_test.go new file: priority_list/iterator.go new file: priority_list/priority_list.go new file: priority_list/priority_list_test.go new file: priority_queue/iterator.go new file: priority_queue/priority_queue.go new file: priority_queue/priority_queue_test.go new file: priority_queue/vbt.go new file: priority_queue/vbt_test.go new file: priority_queuekey/iterator.go new file: priority_queuekey/priority_queuekey.go new file: priority_queuekey/priority_queuekey_test.go new file: priority_queuekey/vbt.go new file: priority_queuekey/vbt_test.go new file: set/hashset/hashset.go new file: set/hashset/hashset_test.go new file: set/treeset/treeset.go new file: set/treeset/treeset_test.go new file: sparse_array/array2/array2.go new file: sparse_array/array2/array2_test.go new file: sparse_array/array3/array3.go new file: sparse_array/array3/array3_test.go new file: sparse_array/arrayn/arrayn.go new file: sparse_array/arrayn/arrayn_test.go new file: stack/stack.go new file: stack/stack_test.go new file: tree/avl/avl.go new file: tree/avl/avl_test.go new file: tree/avl/iterator.go new file: tree/avldup/avldup.go new file: tree/avldup/avldup_test.go new file: tree/avldup/iterator.go new file: tree/avlkey/avlkey.go new file: tree/avlkey/avlkey_test.go new file: tree/avlkey/iterator.go new file: tree/avlkeydup/avlkeydup.go new file: tree/avlkeydup/avlkeydup_test.go new file: tree/avlkeydup/iterator.go new file: tree/vbt/iterator.go new file: tree/vbt/vbt.go new file: tree/vbt/vbt_test.go new file: tree/vbtkey/iterator.go new file: tree/vbtkey/vbtkey.go new file: tree/vbtkey/vbtkey_test.go
2019-05-08 02:42:51 +00:00
package lastack
import (
2019-07-25 06:30:44 +00:00
"github.com/474420502/focus/stack"
new file: .gitignore new file: LICENSE new file: README.md new file: compare/compare.go new file: for_test.go new file: heap/heap.go new file: heap/heap_test.go new file: interface.go new file: lastack/lastack.go new file: lastack/lastack_test.go new file: list/list.go new file: list/list_test.go new file: map/hashmap/hashmap.go new file: map/hashmap/hashmap_test.go new file: priority_list/iterator.go new file: priority_list/priority_list.go new file: priority_list/priority_list_test.go new file: priority_queue/iterator.go new file: priority_queue/priority_queue.go new file: priority_queue/priority_queue_test.go new file: priority_queue/vbt.go new file: priority_queue/vbt_test.go new file: priority_queuekey/iterator.go new file: priority_queuekey/priority_queuekey.go new file: priority_queuekey/priority_queuekey_test.go new file: priority_queuekey/vbt.go new file: priority_queuekey/vbt_test.go new file: set/hashset/hashset.go new file: set/hashset/hashset_test.go new file: set/treeset/treeset.go new file: set/treeset/treeset_test.go new file: sparse_array/array2/array2.go new file: sparse_array/array2/array2_test.go new file: sparse_array/array3/array3.go new file: sparse_array/array3/array3_test.go new file: sparse_array/arrayn/arrayn.go new file: sparse_array/arrayn/arrayn_test.go new file: stack/stack.go new file: stack/stack_test.go new file: tree/avl/avl.go new file: tree/avl/avl_test.go new file: tree/avl/iterator.go new file: tree/avldup/avldup.go new file: tree/avldup/avldup_test.go new file: tree/avldup/iterator.go new file: tree/avlkey/avlkey.go new file: tree/avlkey/avlkey_test.go new file: tree/avlkey/iterator.go new file: tree/avlkeydup/avlkeydup.go new file: tree/avlkeydup/avlkeydup_test.go new file: tree/avlkeydup/iterator.go new file: tree/vbt/iterator.go new file: tree/vbt/vbt.go new file: tree/vbt/vbt_test.go new file: tree/vbtkey/iterator.go new file: tree/vbtkey/vbtkey.go new file: tree/vbtkey/vbtkey_test.go
2019-05-08 02:42:51 +00:00
"github.com/davecgh/go-spew/spew"
)
type Node struct {
elements []interface{}
cur int
down *Node
}
type Stack struct {
top *Node
cache *Node
2019-07-25 06:30:44 +00:00
size uint
}
func assertImplementation() {
var _ stack.IStack = (*Stack)(nil)
new file: .gitignore new file: LICENSE new file: README.md new file: compare/compare.go new file: for_test.go new file: heap/heap.go new file: heap/heap_test.go new file: interface.go new file: lastack/lastack.go new file: lastack/lastack_test.go new file: list/list.go new file: list/list_test.go new file: map/hashmap/hashmap.go new file: map/hashmap/hashmap_test.go new file: priority_list/iterator.go new file: priority_list/priority_list.go new file: priority_list/priority_list_test.go new file: priority_queue/iterator.go new file: priority_queue/priority_queue.go new file: priority_queue/priority_queue_test.go new file: priority_queue/vbt.go new file: priority_queue/vbt_test.go new file: priority_queuekey/iterator.go new file: priority_queuekey/priority_queuekey.go new file: priority_queuekey/priority_queuekey_test.go new file: priority_queuekey/vbt.go new file: priority_queuekey/vbt_test.go new file: set/hashset/hashset.go new file: set/hashset/hashset_test.go new file: set/treeset/treeset.go new file: set/treeset/treeset_test.go new file: sparse_array/array2/array2.go new file: sparse_array/array2/array2_test.go new file: sparse_array/array3/array3.go new file: sparse_array/array3/array3_test.go new file: sparse_array/arrayn/arrayn.go new file: sparse_array/arrayn/arrayn_test.go new file: stack/stack.go new file: stack/stack_test.go new file: tree/avl/avl.go new file: tree/avl/avl_test.go new file: tree/avl/iterator.go new file: tree/avldup/avldup.go new file: tree/avldup/avldup_test.go new file: tree/avldup/iterator.go new file: tree/avlkey/avlkey.go new file: tree/avlkey/avlkey_test.go new file: tree/avlkey/iterator.go new file: tree/avlkeydup/avlkeydup.go new file: tree/avlkeydup/avlkeydup_test.go new file: tree/avlkeydup/iterator.go new file: tree/vbt/iterator.go new file: tree/vbt/vbt.go new file: tree/vbt/vbt_test.go new file: tree/vbtkey/iterator.go new file: tree/vbtkey/vbtkey.go new file: tree/vbtkey/vbtkey_test.go
2019-05-08 02:42:51 +00:00
}
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 {
2019-07-25 06:30:44 +00:00
var growsize uint
new file: .gitignore new file: LICENSE new file: README.md new file: compare/compare.go new file: for_test.go new file: heap/heap.go new file: heap/heap_test.go new file: interface.go new file: lastack/lastack.go new file: lastack/lastack_test.go new file: list/list.go new file: list/list_test.go new file: map/hashmap/hashmap.go new file: map/hashmap/hashmap_test.go new file: priority_list/iterator.go new file: priority_list/priority_list.go new file: priority_list/priority_list_test.go new file: priority_queue/iterator.go new file: priority_queue/priority_queue.go new file: priority_queue/priority_queue_test.go new file: priority_queue/vbt.go new file: priority_queue/vbt_test.go new file: priority_queuekey/iterator.go new file: priority_queuekey/priority_queuekey.go new file: priority_queuekey/priority_queuekey_test.go new file: priority_queuekey/vbt.go new file: priority_queuekey/vbt_test.go new file: set/hashset/hashset.go new file: set/hashset/hashset_test.go new file: set/treeset/treeset.go new file: set/treeset/treeset_test.go new file: sparse_array/array2/array2.go new file: sparse_array/array2/array2_test.go new file: sparse_array/array3/array3.go new file: sparse_array/array3/array3_test.go new file: sparse_array/arrayn/arrayn.go new file: sparse_array/arrayn/arrayn_test.go new file: stack/stack.go new file: stack/stack_test.go new file: tree/avl/avl.go new file: tree/avl/avl_test.go new file: tree/avl/iterator.go new file: tree/avldup/avldup.go new file: tree/avldup/avldup_test.go new file: tree/avldup/iterator.go new file: tree/avlkey/avlkey.go new file: tree/avlkey/avlkey_test.go new file: tree/avlkey/iterator.go new file: tree/avlkeydup/avlkeydup.go new file: tree/avlkeydup/avlkeydup_test.go new file: tree/avlkeydup/iterator.go new file: tree/vbt/iterator.go new file: tree/vbt/vbt.go new file: tree/vbt/vbt_test.go new file: tree/vbtkey/iterator.go new file: tree/vbtkey/vbtkey.go new file: tree/vbtkey/vbtkey_test.go
2019-05-08 02:42:51 +00:00
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
}
2019-07-25 06:30:44 +00:00
func (as *Stack) Size() uint {
new file: .gitignore new file: LICENSE new file: README.md new file: compare/compare.go new file: for_test.go new file: heap/heap.go new file: heap/heap_test.go new file: interface.go new file: lastack/lastack.go new file: lastack/lastack_test.go new file: list/list.go new file: list/list_test.go new file: map/hashmap/hashmap.go new file: map/hashmap/hashmap_test.go new file: priority_list/iterator.go new file: priority_list/priority_list.go new file: priority_list/priority_list_test.go new file: priority_queue/iterator.go new file: priority_queue/priority_queue.go new file: priority_queue/priority_queue_test.go new file: priority_queue/vbt.go new file: priority_queue/vbt_test.go new file: priority_queuekey/iterator.go new file: priority_queuekey/priority_queuekey.go new file: priority_queuekey/priority_queuekey_test.go new file: priority_queuekey/vbt.go new file: priority_queuekey/vbt_test.go new file: set/hashset/hashset.go new file: set/hashset/hashset_test.go new file: set/treeset/treeset.go new file: set/treeset/treeset_test.go new file: sparse_array/array2/array2.go new file: sparse_array/array2/array2_test.go new file: sparse_array/array3/array3.go new file: sparse_array/array3/array3_test.go new file: sparse_array/arrayn/arrayn.go new file: sparse_array/arrayn/arrayn_test.go new file: stack/stack.go new file: stack/stack_test.go new file: tree/avl/avl.go new file: tree/avl/avl_test.go new file: tree/avl/iterator.go new file: tree/avldup/avldup.go new file: tree/avldup/avldup_test.go new file: tree/avldup/iterator.go new file: tree/avlkey/avlkey.go new file: tree/avlkey/avlkey_test.go new file: tree/avlkey/iterator.go new file: tree/avlkeydup/avlkeydup.go new file: tree/avlkeydup/avlkeydup_test.go new file: tree/avlkeydup/iterator.go new file: tree/vbt/iterator.go new file: tree/vbt/vbt.go new file: tree/vbt/vbt_test.go new file: tree/vbtkey/iterator.go new file: tree/vbtkey/vbtkey.go new file: tree/vbtkey/vbtkey_test.go
2019-05-08 02:42:51 +00:00
return as.size
}
2019-07-25 06:30:44 +00:00
// String 左为Top
new file: .gitignore new file: LICENSE new file: README.md new file: compare/compare.go new file: for_test.go new file: heap/heap.go new file: heap/heap_test.go new file: interface.go new file: lastack/lastack.go new file: lastack/lastack_test.go new file: list/list.go new file: list/list_test.go new file: map/hashmap/hashmap.go new file: map/hashmap/hashmap_test.go new file: priority_list/iterator.go new file: priority_list/priority_list.go new file: priority_list/priority_list_test.go new file: priority_queue/iterator.go new file: priority_queue/priority_queue.go new file: priority_queue/priority_queue_test.go new file: priority_queue/vbt.go new file: priority_queue/vbt_test.go new file: priority_queuekey/iterator.go new file: priority_queuekey/priority_queuekey.go new file: priority_queuekey/priority_queuekey_test.go new file: priority_queuekey/vbt.go new file: priority_queuekey/vbt_test.go new file: set/hashset/hashset.go new file: set/hashset/hashset_test.go new file: set/treeset/treeset.go new file: set/treeset/treeset_test.go new file: sparse_array/array2/array2.go new file: sparse_array/array2/array2_test.go new file: sparse_array/array3/array3.go new file: sparse_array/array3/array3_test.go new file: sparse_array/arrayn/arrayn.go new file: sparse_array/arrayn/arrayn_test.go new file: stack/stack.go new file: stack/stack_test.go new file: tree/avl/avl.go new file: tree/avl/avl_test.go new file: tree/avl/iterator.go new file: tree/avldup/avldup.go new file: tree/avldup/avldup_test.go new file: tree/avldup/iterator.go new file: tree/avlkey/avlkey.go new file: tree/avlkey/avlkey_test.go new file: tree/avlkey/iterator.go new file: tree/avlkeydup/avlkeydup.go new file: tree/avlkeydup/avlkeydup_test.go new file: tree/avlkeydup/iterator.go new file: tree/vbt/iterator.go new file: tree/vbt/vbt.go new file: tree/vbt/vbt_test.go new file: tree/vbtkey/iterator.go new file: tree/vbtkey/vbtkey.go new file: tree/vbtkey/vbtkey_test.go
2019-05-08 02:42:51 +00:00
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
}
2019-07-25 06:30:44 +00:00
func (as *Stack) Index(idx int) (interface{}, bool) {
new file: .gitignore new file: LICENSE new file: README.md new file: compare/compare.go new file: for_test.go new file: heap/heap.go new file: heap/heap_test.go new file: interface.go new file: lastack/lastack.go new file: lastack/lastack_test.go new file: list/list.go new file: list/list_test.go new file: map/hashmap/hashmap.go new file: map/hashmap/hashmap_test.go new file: priority_list/iterator.go new file: priority_list/priority_list.go new file: priority_list/priority_list_test.go new file: priority_queue/iterator.go new file: priority_queue/priority_queue.go new file: priority_queue/priority_queue_test.go new file: priority_queue/vbt.go new file: priority_queue/vbt_test.go new file: priority_queuekey/iterator.go new file: priority_queuekey/priority_queuekey.go new file: priority_queuekey/priority_queuekey_test.go new file: priority_queuekey/vbt.go new file: priority_queuekey/vbt_test.go new file: set/hashset/hashset.go new file: set/hashset/hashset_test.go new file: set/treeset/treeset.go new file: set/treeset/treeset_test.go new file: sparse_array/array2/array2.go new file: sparse_array/array2/array2_test.go new file: sparse_array/array3/array3.go new file: sparse_array/array3/array3_test.go new file: sparse_array/arrayn/arrayn.go new file: sparse_array/arrayn/arrayn_test.go new file: stack/stack.go new file: stack/stack_test.go new file: tree/avl/avl.go new file: tree/avl/avl_test.go new file: tree/avl/iterator.go new file: tree/avldup/avldup.go new file: tree/avldup/avldup_test.go new file: tree/avldup/iterator.go new file: tree/avlkey/avlkey.go new file: tree/avlkey/avlkey_test.go new file: tree/avlkey/iterator.go new file: tree/avlkeydup/avlkeydup.go new file: tree/avlkeydup/avlkeydup_test.go new file: tree/avlkeydup/iterator.go new file: tree/vbt/iterator.go new file: tree/vbt/vbt.go new file: tree/vbt/vbt_test.go new file: tree/vbtkey/iterator.go new file: tree/vbtkey/vbtkey.go new file: tree/vbtkey/vbtkey_test.go
2019-05-08 02:42:51 +00:00
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
}