Skip to content

Instantly share code, notes, and snippets.

@tangqiaoboy

tangqiaoboy/NSArrayIterator.h Secret

Last active Feb 3, 2017
Embed
What would you like to do?
给你一个嵌套的 NSArray 数据,实现一个迭代器类,该类提供一个 next() 方法,可以依次的取出这个 NSArray 中的数据。 比如 NSArray 如果是 `[1,[4,3],6,[5,[1,0]]]`, 则最终应该输出:`1, 4, 3, 6, 5, 1, 0` 。 另外,实现一个 `allObjects` 方法,可以一次性取出所有元素。
//
// AlgorithmSolutionCode
//
// Created by TangQiao on 12/13/16.
// Copyright © 2016 Tang Qiao. All rights reserved.
//
#import <Foundation/Foundation.h>
@interface NSArrayIterator : NSObject
- (id)initWithArray:(NSArray *)array;
- (id)next;
- (NSArray *)allObjects;
@end
//
// AlgorithmSolutionCode
//
// Created by TangQiao on 12/13/16.
// Copyright © 2016 Tang Qiao. All rights reserved.
//
#import "NSArrayIterator.h"
@interface NSArrayIteratorCursor : NSObject
@property (nonatomic) NSArray *array;
@property (nonatomic) NSUInteger index;
@end
@implementation NSArrayIteratorCursor
- (id)initWithArray:(NSArray *)array {
self = [super init];
if (self) {
_array = array;
_index = 0;
}
return self;
}
@end
@implementation NSArrayIterator {
NSMutableArray *_stack;
NSArray *_originArray;
}
- (id)initWithArray:(NSArray *)array {
self = [super init];
if (self) {
_originArray = array;
_stack = [NSMutableArray array];
[self setupStackWithArray:array];
}
return self;
}
- (void)setupStackWithArray:(NSArray *)array {
NSArrayIteratorCursor *c = [[NSArrayIteratorCursor alloc] initWithArray:array];
[_stack addObject:c];
}
- (id)next {
// 1. 判断栈是否为空,如果为空则返回 nil。
if (_stack.count == 0) {
return nil;
}
// 2. 从栈中取出元素,看是否遍历到了结尾,如果是的话,则出栈。
NSArrayIteratorCursor *c;
c = [_stack lastObject];
while (c.index == c.array.count && _stack.count > 0) {
[_stack removeLastObject];
c = [_stack lastObject];
}
// 3. 判断第2步是否使栈为空,如果为空,则返回 nil。
if (_stack.count == 0) {
return nil;
}
// 4. 终于拿到元素了,这一步判断拿到的元素是否是数组。
id item = c.array[c.index];
if ([item isKindOfClass:[NSArray class]]) {
c.index++;
// 5. 如果是数组,则重新生成一个遍历的
// NSArrayIteratorCursor 对象,放到栈中, 然后递归调用 next 方法
[self setupStackWithArray:item];
return [self next];
}
// 6. 如果到了这一步,说明拿到了一个非数组的元素,这样就可以把元素返回,
// 同时更新索引到下一个位置。
c.index++;
return item;
}
- (NSArray *)allObjects {
NSMutableArray *result = [NSMutableArray array];
[self fillArray:_originArray into:result];
return result;
}
- (void)fillArray:(NSArray *)array into:(NSMutableArray *)result {
for (id item in array) {
if ([item isKindOfClass:[NSArray class]]) {
[self fillArray:item into:result];
} else {
[result addObject:item];
}
}
}
@end
//
// NSArrayIteratorTest.m
// AlgorithmSolutionCode
//
// Created by TangQiao on 12/13/16.
// Copyright © 2016 Tang Qiao. All rights reserved.
//
#import <XCTest/XCTest.h>
#import "NSArrayIterator.h"
@interface NSArrayIteratorTest : XCTestCase
@end
@implementation NSArrayIteratorTest
- (void)testNext {
NSArray *arr = @[@1, @2, @[ @[ @5], @3, @4], @[@6, @7, @[ @[ @[ @8 ]]]]];
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr];
XCTAssertEqualObjects(@1, [c next]);
XCTAssertEqualObjects(@2, [c next]);
XCTAssertEqualObjects(@5, [c next]);
XCTAssertEqualObjects(@3, [c next]);
XCTAssertEqualObjects(@4, [c next]);
XCTAssertEqualObjects(@6, [c next]);
XCTAssertEqualObjects(@7, [c next]);
XCTAssertEqualObjects(@8, [c next]);
XCTAssertEqualObjects(nil, [c next]);
XCTAssertEqualObjects(nil, [c next]);
}
- (void)testEmptyNestedArray {
NSArray *arr = @[@1, @2, @[ @[ ], @3, @4, @[]], @[@6, @7, @[ @[ @[ @8 ]]]]];
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr];
XCTAssertEqualObjects(@1, [c next]);
XCTAssertEqualObjects(@2, [c next]);
XCTAssertEqualObjects(@3, [c next]);
XCTAssertEqualObjects(@4, [c next]);
XCTAssertEqualObjects(@6, [c next]);
XCTAssertEqualObjects(@7, [c next]);
XCTAssertEqualObjects(@8, [c next]);
XCTAssertEqualObjects(nil, [c next]);
XCTAssertEqualObjects(nil, [c next]);
}
- (void)testEmptyArray {
NSArray *arr = @[ @[ @[ ]], @[@[ @[ @[ ]]]]];
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr];
XCTAssertEqualObjects(nil, [c next]);
XCTAssertEqualObjects(nil, [c next]);
}
- (void)testAllObjects {
NSArray *arr = @[@1, @2, @[ @[ @5], @3, @4], @[@6, @7, @[ @[ @[ @8 ]]]]];
NSArray *expect = @[@1, @2, @5, @3, @4, @6, @7, @8];
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr];
XCTAssertEqualObjects(expect, [c allObjects]);
}
@end
@haoero

This comment has been minimized.

Copy link

@haoero haoero commented Dec 13, 2016

唐大神,我刚看了你的博文,然后我之前刚好写过一个类似的,实现方法有点类似,但是跟你的有一点不同,我用了一个辅助的hasNext方法,麻烦帮忙看一下可行否?

https://github.com/haoero/NSNestedNumberEnumerator

@tangqiaoboy

This comment has been minimized.

Copy link
Owner Author

@tangqiaoboy tangqiaoboy commented Dec 14, 2016

@haoero 我觉得是可以的。你的方法和我类似,不过你把数组内容多展开了一维(把数据元素放到stack中了),这样stack里面的东西会稍多一些。

@toolazytoname

This comment has been minimized.

Copy link

@toolazytoname toolazytoname commented Dec 29, 2016

我也自己实现了一个next,和你们的方法思路不太一样。我会维护一个游标curser和一个是否打印的标记变量flag。遍历过程中如果curser==current一样了,就是到了目标位置的上一个number,那么设置一下flag = YES,下次到了number 的时候就给拿出来。自己觉得这个思路挺简单的,不用维护一个栈,只是在递归调用的路上加了两个变量,找到next object。

@codetalks-new

This comment has been minimized.

Copy link

@codetalks-new codetalks-new commented Jan 11, 2017

我觉得在初始化时 就调用 fillArray 来获得一个 flatArray .
然后.
next() 就简单了.

self.pos++; // 使用 self 记录当前迭代索引位置.
if(self.pos >= self.count){
  return nil
}
return self.flatArray[self.pos]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.