乐趣区

关于golang:手撸golang-行为型设计模式-迭代器模式

jiezi

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

退出移动版