在第2章中讨论的TouchPainter应用程序中,有一个组合数据结构,容纳在屏幕上画线条用的所有触摸点。这一结构有个抽象类型叫Mark。Stroke对它进行了实现。第13章中对Mark及组合模式进行了详细讨论。Mark定义了包含单个点和由顶点组成的线条的“部分-整体”组合结构(树)的行为。这个“部分-整体”结构没有定义与遍历有关的任何逻辑。因为它是树,所以它可按不同顺序遍历。如果把任何遍历行为硬编码到树中,以后Mark的接口与实现以及客户代码将面临大量的改动。同把遍历策略放到树结构中相比,更好的办法是,向Mark添加一个工厂方法(见工厂方法,第4章),让协议的实现者创建并返回适当的枚举器,对树做特定顺序的遍历。我们将通过子类化NSEnumerator为Stroke实现一个迭代器(枚举器)。我们把它叫做MarkEnumerator,它对Mark组合树做后序遍历。NSEnumerator有两个抽象方法:allObjects和nextObject。allObjects返回组合体中未被遍历的Mark实例的数组,而nextObject返回名册中的下一个元素。说明这一思想的类图如图14-3所示。

开始讨论MarkEnumerator之前,先来看一下Mark,这样会对MarkEnumerator如何遍历其子节点有更好的理解。我们需要向Mark添加一个叫enumerator的工厂方法,其实现者可通过这个方法返回NSEnumerator的子类(即MarkEnumerator)的实例,如代码清单14-1所示。

enter image description here

代码清单14-1 Mark.h

@protocol Mark <NSObject>

@property (nonatomic, retain) UIColor *color;
@property (nonatomic, assign) CGFloat size;
@property (nonatomic, assign) CGPoint location;
@property (nonatomic, readonly) NSUInteger count;
@property (nonatomic, readonly) id <Mark> lastChild;

- (void) addMark:(id <Mark>) mark;
- (void) removeMark:(id <Mark>) mark;
- (id <Mark>) childMarkAtIndex:(NSUInteger) index;

- (NSEnumerator *) enumerator;

@end

MarkEnumerator会对Mark树结构执行后序遍历,一次枚举一个元素。因此我们打算用栈来实现这个功能。可是,基础框架中没有现成的栈类。我们需要自己动手做一个。但在做之前,先来完成MarkEnumerator的类定义。虽然Objective-C中在子类再次声明重载的方法不是必需的,但这么做是个好习惯。带有重载NSEnumerator方法的MarkEnumerator的类定义如代码清单14-2所示。

代码清单14-2 MarkEnumerator.h

#import "NSMutableArray+Stack.h"
#import "Mark.h"

@interface MarkEnumerator : NSEnumerator
{ 
  @private
  NSMutableArray *stack_;
}

- (NSArray *)allObjects;
- (id)nextObject;

@end

根据我们的类设计,MarkEnumerator对象应该由Mark的实现类创建并初始化。同时,MarkEnumerator在创建时需要知道要处理什么Mark,因此需要在其匿名范畴中定义一个私有的initWithMark:方法,如代码清单14-3所示。

代码清单14-3 MarkEnumerator+Private.h中声明私有方法的匿名范畴

@interface MarkEnumerator ()

- (id) initWithMark:(id <Mark>)mark;
- (void) traverseAndBuildStackWithMark:(id <Mark>)mark;

@end

把私有方法放到匿名范畴中的理由是,我们想把它们的实现也放到@implementation主代码块。在这个私有范畴中,我们还定义了另一个用于遍历Mark组合对象的私有方法。虽然在两个地方既定义了共有方法又定义了私有方法,但是它们的实现都在同一个.m文件中,如代码清单14-4所示。

代码清单14-4 MarkEnumerator.m

#import "MarkEnumerator.h"
#import "MarkEnumerator+Internal.h"

@implementation MarkEnumerator

- (NSArray *)allObjects
{
  // 返回还未访问的Mark节点的数组
  // 也就是栈中的剩余元素
  return [[stack_ reverseObjectEnumerator] allObjects];
}

- (id)nextObject
{
  return [stack_ pop];
}
- (void) dealloc
{
   [stack_ release];
   [super dealloc];
}

#pragma mark -
#pragma mark Private Methods
- (id) initWithMark:(id <Mark>)aMark
{
  if (self = [super init])
  {
    stack_ = [[NSMutableArray alloc] initWithCapacity:[aMark count]];

    // 后序遍历整个Mark聚合体
    // 然后把单个Mark加到私有栈中
     [self traverseAndBuildStackWithMark:aMark];
  }

  return self;
}

- (void) traverseAndBuildStackWithMark:(id <Mark>)mark
{
  // 把后序遍历压入栈中
  if (mark == nil) return;

  [stack_ push:mark];

  NSUInteger index = [mark count];
  id <Mark> childMark;
  while (childMark = [mark childMarkAtIndex:--index])
  {
    [self traverseAndBuildStackWithMark:childMark];
  }
}

@end

在其私有initWithMark:方法中,它使用传进来的Mark引用,然后调用自己的traverse- AndBuildStackWithMark:(id )mark方法来遍历aMark。这个方法对自身递归调用并把mark及其子节点压入栈中(在栈中构建后序遍历)。注意,子节点是被反向压入栈中的(从右至左)。当访问栈中的元素时,子节点会以原来的顺序被取出(从左至右)。现在Mark聚合体中的所有元素都放入了栈中,已做好了准备,等待客户端向MarkEnumerator发送来nextObject消息取得集合中的下一个Mark。

你也许注意到,nextObject方法只有一条语句——return [stack_ pop];。遍历Mark聚合体之后,最先压入栈中的元素将最后弹出。所以第一子节点将是nextObject方法返回的第一个元素。父节点会在所有子节点之后返回。allObjects应该返回NSArray的实例,包含未被访问的元素的集合。因为栈在集合中向前弹出,并且弹出的元素会从栈中删除,以升序方向返回栈中剩余元素就刚好合适。

我们借助栈的帮助遍历了Mark树,但是基础框架中并没有NSStack这样的类可供我们使用。因此我们需要利用基础类中最接近的一个——NSMutableArray,自己做一个栈,如代码清单14-5所示。

代码清单14-5 NSMutableArray+Stack.h

@interface NSMutableArray (Stack)

- (void) push:(id)object;
- (id) pop;

@end

我们向NSMutableArray增加了两个方法作为范畴,像真正的栈一样压入和弹出对象。它的push方法把对象添加在最后面,而pop方法总是返回并删除最后一个元素,如代码清单14-6所示。

代码清单14-6 NSMutableArray+Stack.m

#import "NSMutableArray+Stack.h"

@implementation NSMutableArray (Stack)

- (void) push:(id)object
{
  [self addObject:object];
}

- (id) pop
{
  if ([self count] == 0) return nil;

  id object = [[[self lastObject] retain] autorelease];
  [self removeLastObject];

  return object;
}

@end

现在我们回到之前离开的Mark家族。Stroke是家族中唯一一个对象含有子节点的成员,因此它实现了enumerator方法,而家族中其他成员没有。简洁起见,省去了其他成员。Stroke的enumerator方法只是创建一个MarkEnumerator实例并用self为参数进行初始化,然后返回这个实例,如代码清单14-7所示。

代码清单14-7 Stroke.m

#import "Stroke.h"
#import "MarkEnumerator+Internal.h"

@implementation Stroke

@synthesize color=color_, size=size_;

- (id) init
{
  if (self = [super init])
  {
    children_ = [[NSMutableArray alloc] initWithCapacity:5];
  }

  return self;
}

- (void) setLocation:(CGPoint)aPoint
{
// 不设定任何位置
}

- (CGPoint) location
{
  // 返回第一个子节点的位置
  if ([children_ count] > 0)
  {
    return [[children_ objectAtIndex:0] location];
  }

  // 否则,返回原点
  return CGPointZero;
}

- (void) addMark:(id <Mark>) mark
{
  [children_ addObject:mark];
}

- (void) removeMark:(id <Mark>) mark
{
  // 如果mark在这一层,将其移除并返回
  // 否则,让每个子节点去找它
  if ([children_ containsObject:mark])
  {
    [children_ removeObject:mark];
  }
  else
  {
    [children_ makeObjectsPerformSelector:@selector(removeMark:)
                               withObject:mark];
  }
}
- (id <Mark>) childMarkAtIndex:(NSUInteger) index
{
  if (index >= [children_ count]) return nil;

  return [children_ objectAtIndex:index];
}

// 返回最后子节点的便利方法
- (id <Mark>) lastChild
{
  return [children_ lastObject];
}

// 返回子节点数
- (NSUInteger) count
{
  return [children_ count];
}

- (void) dealloc
{
  [color_ release];
  [children_ release];
  [super dealloc];
}

#pragma mark -
#pragma mark enumerator method

- (NSEnumerator *) enumerator
{
  return [[[MarkEnumerator alloc] initWithMark:self] autorelease];
}

@end

因为enumerator是工厂方法,所以它可以返回不同的MarkEnumerator子类的对象而无需修改客户代码。如果想要工厂方法支持不同的遍历方式,可以增加一个参数指定遍历类型,以便在运行时选择不同的MarkEnumerator。

说明:在遍历时修改聚合体对象可能有危险。如果向聚合体添加或从聚合体删除了元素,可能导致对一个元素访问两次或完全漏掉一个元素。简单的办法是对聚合体进行一个深复制,再对副本进行遍历,但是如果创建与存储聚合体的另一个副本可能影响性能,代价就比较大。 有很多方法可以实现不受元素插入与删除影响的迭代器。大部分依靠向聚合体注册迭代器。一种实现方法是在插入与删除操作时,聚合体或者调整由它生成的迭代器的内部状态,或者在内部维护信息,以保证正确的遍历。

遍历Scribble的顶点(内部迭代器)

到目前为止所讨论的迭代器(枚举器)是个外部迭代器,就是迭代器模式的原始描述中的那种。它需要客户端请求集合对象返回其迭代器,然后通过迭代器做循环,访问其每个元素。客户端在循环中每次发一个nextObject消息给迭代器,取出一个元素,直到集合取光为止。

可以不让客户端直接使用任何迭代器(枚举器),实现一个内部迭代器作为另一种方式。内部或被动迭代器(通常就是集合对象本身)控制迭代。可以让客户端向内部迭代器提供某种回调机制,让它准备好之后返回集合中的下一个元素,来实现内部迭代器。

从iOS SDK 4.0开始,可以在应用程序的开发中使用Objective-C的块。块是一种函数类型。定义好后,便可在程序中任何地方复用。块在很多方面比C语言的函数指针功能更强大。在Objective-C用块来实现内部迭代器是自然而然的选择。

图14-4中的类图显示了Mark家族的内部迭代器的一种可能的实现方式。

我们向Mark添加了一个新方法:enumerateMarksUsingBlock:markEnumerationBlock。客户端会提供一个定义好的块作为参数,其签名为^(id item, BOOL *stop)。块定义了处理从内部迭代器返回的每个Mark元素的算法。如果算法想要在当前位置停止枚举,它可以把*stop变量设为YES。正如前面附表中讨论的那样,是组合对象本身而不是客户端在维护内部迭代器。enumerateMarksUsingBlock:方法使用通过MarkEnumerator的实例进行的循环来监控枚举过程。从枚举器得到的每个元素会被传给指定的块,以使其中的算法能够处理元素。

enter image description here 图14-4 MarkEnumerator和Stroke的修改版本的类图。通过引入MarkEnumerationBlock实现了内部迭代器

如果想让客户端只能使用内部迭代器,那么可以将返回MarkEnumerator实例的enumerator工厂方法放到匿名范畴中,就像代码清单14-3中MarkEnumerator类那样。这完全取决于设计。

代码清单14-8和代码清单14-9中的代码段显示了对Mark协议以及Stroke类的修改。

代码清单14-8 Mark.h

@protocol Mark <NSObject>

@property (nonatomic, retain) UIColor *color;
@property (nonatomic, assign) CGFloat size;
@property (nonatomic, assign) CGPoint location;
@property (nonatomic, readonly) NSUInteger count;
@property (nonatomic, readonly) id <Mark> lastChild;

- (void) addMark:(id <Mark>) mark;
- (void) removeMark:(id <Mark>) mark;
- (id <Mark>) childMarkAtIndex:(NSUInteger) index;

- (NSEnumerator *) enumerator;

// 用于实现内部迭代器
- (void) enumerateMarksUsingBlock:(void (^)(id <Mark> item, BOOL *stop)) block;

@end

Stroke中对enumerateMarksUsingBlock:(void (^)(id item, BOOL *stop)) block的实现如代码清单14-9所示。

代码清单14-9 Stroke.m中enumerateMarksUsingBlock:方法的实现

- (void) enumerateMarksUsingBlock:(void (^)(id <Mark> item, BOOL *stop)) block
{
  BOOL stop = NO;

  NSEnumerator *enumerator = [self enumerator];

  for (id <Mark> mark in enumerator)
  {
    block (mark, &stop);
    if (stop)
      break;
  }
}