共计 5626 个字符,预计需要花费 15 分钟才能阅读完成。
手撸 golang 行为型设计模式 迭代器模式
缘起
最近温习设计模式
拜读谭勇德的 << 设计模式就该这样学 >>
本系列笔记拟采纳 golang 练习之
迭代器模式
迭代器模式(Iterator Pattern)又叫作游标模式(Cursor Pattern),它提供一种按程序拜访汇合 / 容器对象元素的办法,而又毋庸裸露汇合外部示意。迭代器模式能够为不同的容器提供统一的遍历行为,而不必关怀容器内元素的组成构造,属于行为型设计模式。迭代器模式的实质是把汇合对象的迭代行为抽离到迭代器中,提供统一的拜访接口。(摘自 谭勇德 << 设计模式就该这样学 >>)
场景
- 最近业务 Team 的小伙伴埋怨, golang 自带的汇合类型还是太少, 不太够用
- Leader 张阿蛋于是让码农王二狗参考 java 的汇合库, 先搞个队列和堆栈
- 王二狗翻了好几遍尘封已久的 << 数据结构与算法 >> , 九牛二虎, 终于捣鼓出 tLinkedList 和 tArrayStack, 别离实现了 FIFO 队列和 LIFO 堆栈
-
正当王二狗自信满满的 commit 到 gitee 仓库, 张阿蛋很快过去谈心了:
- 张阿蛋: 狗子, 我看你的队列和堆栈的确基本功能是有了, 但没有遍历的办法
- 王二狗: 这个 … 要不都实现 ToArray()办法, 拷贝到数组里?
- 张阿蛋: 唔, ToArray 尽管可行, 然而还要多一次 copy, 有点侈靡啊
- 王二狗: 那张哥有何高见?
- 张阿蛋: 上个 迭代器, 有 More 和 Next 办法就够了
- 王二狗: 张哥, 强!
设计
- ILinkedList: 定义 FIFO 队列的接口. 外部应用单向链表实现
- IArrayStack: 定义 LIFO 堆栈的接口. 外部应用原生数组实现
- IIterator: 定义迭代器接口, More()判断是否有更多元素, Next()获取下一元素
- tLinkedList: FIFO 队列, 实现 ILinkedList 接口
- tLinkedListIterator: 队列迭代器, 实现 IIterator 接口
- tArrayStack: LIFO 堆栈, 实现 IArrayStack 接口
- tArrayStackIterator: 堆栈迭代器, 实现 IIterator 接口
单元测试
iterator_pattern_test.go, 别离测试队列和堆栈的元素进出, 以及遍历
package behavioral_patterns
import (
"learning/gooop/behavioral_patterns/iterator"
"testing"
)
func Test_IteratorPattern(t *testing.T) {fnAssert := func(b bool, msg string) {
if !b {panic(msg)
}
}
// testing ILinkedList //////////////////////////////
queue := iterator.NewLinkedList()
fnAssert(queue.Size() == 0, "expecting queue.size == 0")
queue.Push(1)
queue.Push(2)
queue.Push(3)
fnAssert(queue.Size() == 3, "expecting queue.size == 3")
e,v := queue.Poll()
fnAssert(e == nil && v == 1, "expecting queue.poll 1")
e,v = queue.Poll()
fnAssert(e == nil && v == 2, "expecting queue.poll 2")
e,v = queue.Poll()
fnAssert(e == nil && v == 3, "expecting queue.poll 3")
e,v = queue.Poll()
fnAssert(e != nil, "expecting error")
queue.Push(1)
queue.Push(2)
queue.Push(3)
iter := queue.Iterator()
for iter.More() {e,v = iter.Next()
if e != nil {t.Error(e)
} else {t.Log(v)
}
}
// end testing ILinkedList //////////////////////////
// testing IArrayStack //////////////////////////////
stack := iterator.NewArrayStack()
fnAssert(stack.Size() == 0, "expecting size==0")
stack.Push(1)
stack.Push(2)
stack.Push(3)
fnAssert(stack.Size() == 3, "expecting stack.size == 3")
e,v = stack.Pop()
fnAssert(e == nil && v == 3, "expecting stack.pop 3")
e,v = stack.Pop()
fnAssert(e == nil && v == 2, "expecting stack.pop 2")
e,v = stack.Pop()
fnAssert(e == nil && v == 1, "expecting stack.pop 1")
e,v = stack.Pop()
fnAssert(e != nil, "expecting stack.pop error")
stack.Push(1)
stack.Push(2)
stack.Push(3)
iter = queue.Iterator()
for iter.More() {e,v = iter.Next()
if e != nil {t.Error(e)
} else {t.Log(v)
}
}
// end testing IArrayStack //////////////////////////
}
测试输入
$ go test -v iterator_pattern_test.go
=== RUN Test_IteratorPattern
iterator_pattern_test.go:45: 1
iterator_pattern_test.go:45: 2
iterator_pattern_test.go:45: 3
iterator_pattern_test.go:80: 1
iterator_pattern_test.go:80: 2
iterator_pattern_test.go:80: 3
--- PASS: Test_IteratorPattern (0.00s)
PASS
ok command-line-arguments 0.002s
ILinkedList.go
定义 FIFO 队列的接口. 外部应用单向链表实现
package iterator
type ILinkedList interface {Size() int
Push(it interface{})
Poll() (e error, it interface{})
Iterator() IIterator}
IArrayStack.go
定义 LIFO 堆栈的接口. 外部应用原生数组实现
package iterator
type IArrayStack interface {Size() int
Push(it interface{})
Pop() (error, interface{})
Iterator() IIterator}
IIterator.go
定义迭代器接口, More()判断是否有更多元素, Next()获取下一元素
package iterator
type IIterator interface {More() bool
Next() (error,interface{})
}
tLinkedList.go
FIFO 队列, 实现 ILinkedList 接口
package iterator
import "errors"
type tLinkedList struct {
size int
head *tLinkedNode
tail *tLinkedNode
}
func NewLinkedList() ILinkedList {
return &tLinkedList{0, nil, nil,}
}
type tLinkedNode struct {value interface{}
next *tLinkedNode
}
func newLinkedNode(v interface{}) *tLinkedNode {
return &tLinkedNode{v, nil,}
}
func (me *tLinkedList) Size() int {return me.size}
func (me *tLinkedList) Push(it interface{}) {node := newLinkedNode(it)
if me.head == nil {me.head, me.tail = node, node} else {
me.tail.next = node
me.tail = node
}
me.size++
}
func (me *tLinkedList) Poll() (error, interface{}) {
if me.size <= 0 {return errors.New("empty list"), nil
}
node := me.head
me.head = me.head.next
me.size--
return nil, node.value
}
func (me *tLinkedList) Iterator() IIterator {return newLinkedListIterator(me)
}
tLinkedListIterator.go
队列迭代器, 实现 IIterator 接口
package iterator
import "errors"
type tLinkedListIterator struct {
list *tLinkedList
current *tLinkedNode
}
func newLinkedListIterator(list *tLinkedList) IIterator {
return &tLinkedListIterator{list, list.head,}
}
func (me *tLinkedListIterator) More() bool {return me.current != nil}
func (me *tLinkedListIterator) Next() (error, interface{}) {
node := me.current
if node == nil {return errors.New("no more elements"), nil
}
me.current = me.current.next
return nil, node.value
}
tArrayStack.go
LIFO 堆栈, 实现 IArrayStack 接口
package iterator
import "errors"
type tArrayStack struct {
size int
items []interface{}
}
func NewArrayStack() IArrayStack {
return &tArrayStack{
0,
make([]interface{}, 0),
}
}
func (me *tArrayStack) Size() int {return me.size}
func (me *tArrayStack) Push(it interface{}) {me.items = append(me.items, it)
me.size++
}
func (me *tArrayStack) Pop() (error, interface{}) {
if me.size <= 0 {return errors.New("empty stack"), nil
}
last := me.items[me.size - 1]
me.items = me.items[0:me.size-1]
me.size--
return nil,last
}
func (me *tArrayStack) Iterator() IIterator {return newArrayStackIterator(me)
}
tArrayStackIterator.go
堆栈迭代器, 实现 IIterator 接口
package iterator
import "errors"
type tArrayStackIterator struct {
stack *tArrayStack
index int
}
func newArrayStackIterator(stack *tArrayStack) IIterator {
return &tArrayStackIterator{
stack,
0,
}
}
func (me *tArrayStackIterator) More() bool {return me.index < me.stack.size}
func (me *tArrayStackIterator) Next() (error, interface{}) {
if me.index >= me.stack.size {return errors.New("no more elements"), nil
}
it := me.stack.items[me.index]
me.index++
return nil, it
}
迭代器模式小结
迭代器模式的长处(1)多态迭代:为不同的聚合构造提供统一的遍历接口,即一个迭代接口能够拜访不同的汇合对象。(2)简化汇合对象接口:迭代器模式将汇合对象自身应该提供的元素迭代接口抽取到迭代器中,使汇合对象毋庸关怀具体迭代行为。(3)元素迭代性能多样化:每个汇合对象都能够提供一个或多个不同的迭代器,使得同种元素的聚合构造能够有不同的迭代行为。(4)解耦迭代与汇合:迭代器模式封装了具体的迭代算法,迭代算法的变动不会影响到汇合对象的架构。迭代器模式的毛病(1)对于比较简单的遍历(如数组或者有序列表),应用迭代器模式遍历较为繁缛。(2)在日常开发中,咱们简直不会本人写迭代器。除非须要定制一个本人实现的数据结构对应的迭代器,否则,开源框架提供的 API 齐全够用。(摘自 谭勇德 << 设计模式就该这样学 >>)
(end)
正文完