行为型 迭代器模式
为什么需要迭代器模式模式
迭代器在很多语言都会提供,主要作用就是用来里边集合(容器)对象,可以是数组、链表各种树。
采用迭代器可以封装遍历方法,如果是图、树这些数据结构,最好采用迭代器模式来进行封装,避免客户端自行去实现造成错误。
每个迭代器独享一份下标信息,多个迭代器同时访问容器不会造成影响。
实现
大家可以顺利考虑一下王争(我推荐的极客时间)说的快照实现。
写这个需要注意Next的关系,很容易写错。我这里起始点不是在0那里,而是在root那里,需要第一次调用后才到0那个位置。
go.mod
module iterator
go 1.13
iterator.go
package iterator
type TreeNode struct {
Left *TreeNode
Right *TreeNode
Value int
}
func NewNode(value int) *TreeNode {
return &TreeNode{
Value: value,
}
}
func (node *TreeNode) Iterator() Iterator {
return &MorrisInOrderIterator{
node: node,
}
}
type Iterator interface {
HasNext() bool
Next() int
Cur() int
}
// InInOrderIterator is implemented in a morris way which will actually modify the tree structure.
type MorrisInOrderIterator struct {
node *TreeNode
}
func (it *MorrisInOrderIterator) HasNext() bool {
return it.node != nil
}
func (it *MorrisInOrderIterator) Cur() int {
return it.node.Value
}
func (it *MorrisInOrderIterator) Next() int {
var res int
cur := it.node
for cur != nil {
left := cur.Left
if left == nil {
res = cur.Value
cur = cur.Right
break
} else {
for left.Right != nil && left.Right != cur {
left = left.Right
}
if left.Right == cur {
res = cur.Value
cur = cur.Right
left.Right = nil
break
} else {
left.Right = cur
cur = cur.Left
}
}
}
it.node = cur
return res
}
iterator_test.go
package iterator_test
import (
"fmt"
"iterator"
"testing"
)
func TestIterator(t *testing.T) {
root := iterator.NewNode(3)
node1 := iterator.NewNode(1)
node2 := iterator.NewNode(0)
node3 := iterator.NewNode(2)
node4 := iterator.NewNode(4)
root.Left = node1
node1.Left = node2
node1.Right = node3
root.Right = node4
it := root.Iterator()
for i := 0; i < 5; i++ {
if !it.HasNext() {
t.Fatal("Error ended HasNext()", it.Cur())
}
cur := it.Next()
fmt.Println("Debug:", cur)
if cur != i {
t.Fatal(fmt.Sprintf("Expecting %d but got %d", i, cur))
}
}
}
执行:
go test iterator -v