手撸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_patternsimport ( "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)PASSok command-line-arguments 0.002sILinkedList.go
定义FIFO队列的接口. 外部应用单向链表实现
package iteratortype ILinkedList interface { Size() int Push(it interface{}) Poll() (e error, it interface{}) Iterator() IIterator}IArrayStack.go
定义LIFO堆栈的接口. 外部应用原生数组实现
package iteratortype IArrayStack interface { Size() int Push(it interface{}) Pop() (error, interface{}) Iterator() IIterator}IIterator.go
定义迭代器接口, More()判断是否有更多元素, Next()获取下一元素
package iteratortype IIterator interface { More() bool Next() (error,interface{})}tLinkedList.go
FIFO队列, 实现ILinkedList接口
package iteratorimport "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 iteratorimport "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 iteratorimport "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 iteratorimport "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)