手撸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)