diff options
Diffstat (limited to 'Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary')
14 files changed, 1313 insertions, 0 deletions
diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h new file mode 100644 index 0000000..0c6c989 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h @@ -0,0 +1,37 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import <Foundation/Foundation.h> +#import "FImmutableSortedDictionary.h" + +/** + * This is an array backed implementation of FImmutableSortedDictionary. It uses arrays and linear lookups to achieve + * good memory efficiency while maintaining good performance for small collections. It also uses less allocations than + * a comparable red black tree. To avoid degrading performance with increasing collection size it will automatically + * convert to a FTreeSortedDictionary after an insert call above a certain threshold. + */ +@interface FArraySortedDictionary : FImmutableSortedDictionary + ++ (FArraySortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator; + +- (id)initWithComparator:(NSComparator)comparator; + +#pragma mark - +#pragma mark Properties + +@property (nonatomic, copy, readonly) NSComparator comparator; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m new file mode 100644 index 0000000..f572b6b --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m @@ -0,0 +1,282 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import "FArraySortedDictionary.h" +#import "FTreeSortedDictionary.h" + +@interface FArraySortedDictionaryEnumerator : NSEnumerator + +- (id)initWithKeys:(NSArray *)keys startPos:(NSInteger)pos isReverse:(BOOL)reverse; +- (id)nextObject; + +@property (nonatomic) NSInteger pos; +@property (nonatomic) BOOL reverse; +@property (nonatomic, strong) NSArray *keys; + +@end + +@implementation FArraySortedDictionaryEnumerator + +- (id)initWithKeys:(NSArray *)keys startPos:(NSInteger)pos isReverse:(BOOL)reverse +{ + self = [super init]; + if (self != nil) { + self->_pos = pos; + self->_reverse = reverse; + self->_keys = keys; + } + return self; +} + +- (id)nextObject +{ + NSInteger pos = self->_pos; + if (pos >= 0 && pos < self.keys.count) { + if (self.reverse) { + self->_pos--; + } else { + self->_pos++; + } + return self.keys[pos]; + } else { + return nil; + } +} + +@end + +@interface FArraySortedDictionary () + +- (id)initWithComparator:(NSComparator)comparator; + +@property (nonatomic, copy, readwrite) NSComparator comparator; +@property (nonatomic, strong) NSArray *keys; +@property (nonatomic, strong) NSArray *values; + +@end + +@implementation FArraySortedDictionary + ++ (FArraySortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator +{ + NSMutableArray *keys = [NSMutableArray arrayWithCapacity:dictionary.count]; + [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) { + [keys addObject:key]; + }]; + [keys sortUsingComparator:comparator]; + + [keys enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { + if (idx > 0) { + if (comparator(keys[idx - 1], obj) != NSOrderedAscending) { + [NSException raise:NSInvalidArgumentException format:@"Can't create FImmutableSortedDictionary with keys with same ordering!"]; + } + } + }]; + + NSMutableArray *values = [NSMutableArray arrayWithCapacity:keys.count]; + NSInteger pos = 0; + for (id key in keys) { + values[pos++] = dictionary[key]; + } + NSAssert(values.count == keys.count, @"We added as many keys as values"); + return [[FArraySortedDictionary alloc] initWithComparator:comparator keys:keys values:values]; +} + +- (id)initWithComparator:(NSComparator)comparator +{ + self = [super init]; + if (self != nil) { + self->_comparator = comparator; + self->_keys = [NSArray array]; + self->_values = [NSArray array]; + } + return self; +} + +- (id)initWithComparator:(NSComparator)comparator keys:(NSArray *)keys values:(NSArray *)values +{ + self = [super init]; + if (self != nil) { + self->_comparator = comparator; + self->_keys = keys; + self->_values = values; + } + return self; +} + +- (NSInteger) findInsertPositionForKey:(id)key +{ + NSInteger newPos = 0; + while (newPos < self.keys.count && self.comparator(self.keys[newPos], key) < NSOrderedSame) { + newPos++; + } + return newPos; +} + +- (NSInteger) findKey:(id)key +{ + if (key == nil) { + return NSNotFound; + } + for (NSInteger pos = 0; pos < self.keys.count; pos++) { + NSComparisonResult result = self.comparator(key, self.keys[pos]); + if (result == NSOrderedSame) { + return pos; + } else if (result == NSOrderedAscending) { + return NSNotFound; + } + } + return NSNotFound; +} + +- (FImmutableSortedDictionary *) insertKey:(id)key withValue:(id)value +{ + NSInteger pos = [self findKey:key]; + + if (pos == NSNotFound) { + /* + * If we're above the threshold we want to convert it to a tree backed implementation to not have + * degrading performance + */ + if (self.count >= SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD) { + NSMutableDictionary *dict = [NSMutableDictionary dictionaryWithCapacity:self.count]; + for (NSInteger i = 0; i < self.keys.count; i++) { + dict[self.keys[i]] = self.values[i]; + } + dict[key] = value; + return [FTreeSortedDictionary fromDictionary:dict withComparator:self.comparator]; + } else { + NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys]; + NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values]; + NSInteger newPos = [self findInsertPositionForKey:key]; + [newKeys insertObject:key atIndex:newPos]; + [newValues insertObject:value atIndex:newPos]; + return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues]; + } + } else { + NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys]; + NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values]; + newKeys[pos] = key; + newValues[pos] = value; + return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues]; + } +} + +- (FImmutableSortedDictionary *) removeKey:(id)key +{ + NSInteger pos = [self findKey:key]; + if (pos == NSNotFound) { + return self; + } else { + NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys]; + NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values]; + [newKeys removeObjectAtIndex:pos]; + [newValues removeObjectAtIndex:pos]; + return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues]; + } +} + +- (id) get:(id)key +{ + NSInteger pos = [self findKey:key]; + if (pos == NSNotFound) { + return nil; + } else { + return self.values[pos]; + } +} + +- (id) getPredecessorKey:(id) key { + NSInteger pos = [self findKey:key]; + if (pos == NSNotFound) { + [NSException raise:NSInternalInconsistencyException format:@"Can't get predecessor key for non-existent key"]; + return nil; + } else if (pos == 0) { + return nil; + } else { + return self.keys[pos - 1]; + } +} + +- (BOOL) isEmpty { + return self.keys.count == 0; +} + +- (int) count +{ + return (int)self.keys.count; +} + +- (id) minKey +{ + return [self.keys firstObject]; +} + +- (id) maxKey +{ + return [self.keys lastObject]; +} + +- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block +{ + [self enumerateKeysAndObjectsReverse:NO usingBlock:block]; +} + +- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block +{ + if (reverse) { + BOOL stop = NO; + for (NSInteger i = self.keys.count - 1; i >= 0; i--) { + block(self.keys[i], self.values[i], &stop); + if (stop) return; + } + } else { + BOOL stop = NO; + for (NSInteger i = 0; i < self.keys.count; i++) { + block(self.keys[i], self.values[i], &stop); + if (stop) return; + } + } +} + +- (BOOL) contains:(id)key { + return [self findKey:key] != NSNotFound; +} + +- (NSEnumerator *) keyEnumerator { + return [self.keys objectEnumerator]; +} + +- (NSEnumerator *) keyEnumeratorFrom:(id)startKey { + NSInteger startPos = [self findInsertPositionForKey:startKey]; + return [[FArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys startPos:startPos isReverse:NO]; +} + +- (NSEnumerator *) reverseKeyEnumerator { + return [self.keys reverseObjectEnumerator]; +} + +- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey { + NSInteger startPos = [self findInsertPositionForKey:startKey]; + // if there's no exact match, findKeyOrInsertPosition will return the index *after* the closest match, but + // since this is a reverse iterator, we want to start just *before* the closest match. + if (startPos >= self.keys.count || self.comparator(self.keys[startPos], startKey) != NSOrderedSame) { + startPos -= 1; + } + return [[FArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys startPos:startPos isReverse:YES]; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch new file mode 100644 index 0000000..88d2408 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch @@ -0,0 +1,7 @@ +// +// Prefix header for all source files of the 'FImmutableSortedDictionary' target in the 'FImmutableSortedDictionary' project +// + +#ifdef __OBJC__ + #import <Foundation/Foundation.h> +#endif diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h new file mode 100644 index 0000000..1e7e5a3 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h @@ -0,0 +1,71 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +/** + * @fileoverview Implementation of an immutable SortedMap using a Left-leaning + * Red-Black Tree, adapted from the implementation in Mugs + * (http://mads379.github.com/mugs/) by Mads Hartmann Jensen + * (mads379@gmail.com). + * + * Original paper on Left-leaning Red-Black Trees: + * http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf + * + * Invariant 1: No red node has a red child + * Invariant 2: Every leaf path has the same number of black nodes + * Invariant 3: Only the left child can be red (left leaning) + */ + +#import <Foundation/Foundation.h> + +/** + * The size threshold where we use a tree backed sorted map instead of an array backed sorted map. + * This is a more or less arbitrary chosen value, that was chosen to be large enough to fit most of object kind + * of Firebase data, but small enough to not notice degradation in performance for inserting and lookups. + * Feel free to empirically determine this constant, but don't expect much gain in real world performance. + */ +#define SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD 25 + +@interface FImmutableSortedDictionary : NSObject + ++ (FImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator; ++ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator; + +- (FImmutableSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue; +- (FImmutableSortedDictionary *) removeKey:(id)aKey; +- (id) get:(id) key; +- (id) getPredecessorKey:(id) key; +- (BOOL) isEmpty; +- (int) count; +- (id) minKey; +- (id) maxKey; +- (void) enumerateKeysAndObjectsUsingBlock:(void(^)(id key, id value, BOOL *stop))block; +- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void(^)(id key, id value, BOOL *stop))block; +- (BOOL) contains:(id)key; +- (NSEnumerator *) keyEnumerator; +- (NSEnumerator *) keyEnumeratorFrom:(id)startKey; +- (NSEnumerator *) reverseKeyEnumerator; +- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey; + +#pragma mark - +#pragma mark Methods similar to NSMutableDictionary + +- (FImmutableSortedDictionary *) setObject:(id)anObject forKey:(id)aKey; +- (id) objectForKey:(id)key; +- (FImmutableSortedDictionary *) removeObjectForKey:(id)aKey; + +@end + diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m new file mode 100644 index 0000000..006c12d --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m @@ -0,0 +1,158 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import "FImmutableSortedDictionary.h" +#import "FArraySortedDictionary.h" +#import "FTreeSortedDictionary.h" + +#define THROW_ABSTRACT_METHOD_EXCEPTION(sel) do { \ + @throw [NSException exceptionWithName:NSInternalInconsistencyException \ + reason:[NSString stringWithFormat:@"You must override %@ in a subclass", NSStringFromSelector(sel)] \ + userInfo:nil]; \ +} while(0) + +@implementation FImmutableSortedDictionary + ++ (FImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator +{ + return [[FArraySortedDictionary alloc] initWithComparator:comparator]; +} + ++ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator +{ + if (dictionary.count <= SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD) { + return [FArraySortedDictionary fromDictionary:dictionary withComparator:comparator]; + } else { + return [FTreeSortedDictionary fromDictionary:dictionary withComparator:comparator]; + } +} + +- (FImmutableSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(insertKey:withValue:)); +} + +- (FImmutableSortedDictionary *) removeKey:(id)aKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(removeKey:)); +} + +- (id) get:(id) key { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(get:)); +} + +- (id) getPredecessorKey:(id) key { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(getPredecessorKey:)); +} + +- (BOOL) isEmpty { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(isEmpty)); +} + +- (int) count { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector((count))); +} + +- (id) minKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(minKey)); +} + +- (id) maxKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(maxKey)); +} + +- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(enumerateKeysAndObjectsUsingBlock:)); +} + +- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(enumerateKeysAndObjectsReverse:usingBlock:)); +} + +- (BOOL) contains:(id)key { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(contains:)); +} + +- (NSEnumerator *) keyEnumerator { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(keyEnumerator)); +} + +- (NSEnumerator *) keyEnumeratorFrom:(id)startKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(keyEnumeratorFrom:)); +} + +- (NSEnumerator *) reverseKeyEnumerator { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(reverseKeyEnumerator)); +} + +- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(reverseKeyEnumeratorFrom:)); +} + +- (BOOL)isEqual:(id)object { + if (![object isKindOfClass:[FImmutableSortedDictionary class]]) { + return NO; + } + FImmutableSortedDictionary *other = (FImmutableSortedDictionary *)object; + if (self.count != other.count) { + return NO; + } + __block BOOL isEqual = YES; + [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + id otherValue = [other objectForKey:key]; + isEqual = isEqual && (value == otherValue || [value isEqual:otherValue]); + *stop = !isEqual; + }]; + return isEqual; +} + +- (NSUInteger)hash { + __block NSUInteger hash = 0; + [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + hash = (hash * 31 + [key hash]) * 17 + [value hash]; + }]; + return hash; +} + +- (NSString *)description { + NSMutableString *str = [[NSMutableString alloc] init]; + __block BOOL first = YES; + [str appendString:@"{ "]; + [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + if (!first) { + [str appendString:@", "]; + } + first = NO; + [str appendString:[NSString stringWithFormat:@"%@: %@", key, value]]; + }]; + [str appendString:@" }"]; + return str; +} + +#pragma mark - +#pragma mark Methods similar to NSMutableDictionary + +- (FImmutableSortedDictionary *) setObject:(__unsafe_unretained id)anObject forKey:(__unsafe_unretained id)aKey { + return [self insertKey:aKey withValue:anObject]; +} + +- (FImmutableSortedDictionary *) removeObjectForKey:(__unsafe_unretained id)aKey { + return [self removeKey:aKey]; +} + +- (id) objectForKey:(__unsafe_unretained id)key { + return [self get:key]; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h new file mode 100644 index 0000000..bb1a39c --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h @@ -0,0 +1,38 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import <Foundation/Foundation.h> + +@interface FImmutableSortedSet : NSObject + ++ (FImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)array comparator:(NSComparator)comparator; + +- (BOOL)containsObject:(id)object; +- (FImmutableSortedSet *)addObject:(id)object; +- (FImmutableSortedSet *)removeObject:(id)object; +- (id)firstObject; +- (id)lastObject; +- (NSUInteger)count; +- (BOOL)isEmpty; + +- (id)predecessorEntry:(id)entry; + +- (void)enumerateObjectsUsingBlock:(void (^)(id obj, BOOL *stop))block; +- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id obj, BOOL *stop))block; + +- (NSEnumerator *)objectEnumerator; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m new file mode 100644 index 0000000..09c4164 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m @@ -0,0 +1,131 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import "FImmutableSortedSet.h" +#import "FImmutableSortedDictionary.h" + +@interface FImmutableSortedSet () + +@property (nonatomic, strong) FImmutableSortedDictionary *dictionary; + +@end + +@implementation FImmutableSortedSet + ++ (FImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)dictionary comparator:(NSComparator)comparator +{ + FImmutableSortedDictionary *setDict = [FImmutableSortedDictionary fromDictionary:dictionary withComparator:comparator]; + return [[FImmutableSortedSet alloc] initWithDictionary:setDict]; +} + +- (id)initWithDictionary:(FImmutableSortedDictionary *)dictionary +{ + self = [super init]; + if (self != nil) { + self->_dictionary = dictionary; + } + return self; +} + +- (BOOL)contains:(id)object +{ + return [self.dictionary contains:object]; +} + +- (FImmutableSortedSet *)addObject:(id)object +{ + FImmutableSortedDictionary *newDictionary = [self.dictionary insertKey:object withValue:[NSNull null]]; + if (newDictionary != self.dictionary) { + return [[FImmutableSortedSet alloc] initWithDictionary:newDictionary]; + } else { + return self; + } +} + +- (FImmutableSortedSet *)removeObject:(id)object +{ + FImmutableSortedDictionary *newDictionary = [self.dictionary removeObjectForKey:object]; + if (newDictionary != self.dictionary) { + return [[FImmutableSortedSet alloc] initWithDictionary:newDictionary]; + } else { + return self; + } +} + +- (BOOL)containsObject:(id)object +{ + return [self.dictionary contains:object]; +} + +- (id)firstObject +{ + return [self.dictionary minKey]; +} + +- (id)lastObject +{ + return [self.dictionary maxKey]; +} + +- (id)predecessorEntry:(id)entry +{ + return [self.dictionary getPredecessorKey:entry]; +} + +- (NSUInteger)count +{ + return [self.dictionary count]; +} + +- (BOOL)isEmpty +{ + return [self.dictionary isEmpty]; +} + +- (void)enumerateObjectsUsingBlock:(void (^)(id, BOOL *))block +{ + [self enumerateObjectsReverse:NO usingBlock:block]; +} + +- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, BOOL *))block +{ + [self.dictionary enumerateKeysAndObjectsReverse:reverse usingBlock:^(id key, id value, BOOL *stop) { + block(key, stop); + }]; +} + +- (NSEnumerator *)objectEnumerator +{ + return [self.dictionary keyEnumerator]; +} + +- (NSString *)description +{ + NSMutableString *str = [[NSMutableString alloc] init]; + __block BOOL first = YES; + [str appendString:@"FImmutableSortedSet ( "]; + [self enumerateObjectsUsingBlock:^(id obj, BOOL *stop) { + if (!first) { + [str appendString:@", "]; + } + first = NO; + [str appendString:[NSString stringWithFormat:@"%@", obj]]; + }]; + [str appendString:@" )"]; + return str; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h new file mode 100644 index 0000000..3257447 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h @@ -0,0 +1,43 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import <Foundation/Foundation.h> +#import "FLLRBNode.h" + +@interface FLLRBEmptyNode : NSObject <FLLRBNode> + ++ (id)emptyNode; + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight; +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id<FLLRBNode>) remove:(id) aKey withComparator:(NSComparator)aComparator; +- (int) count; +- (BOOL) isEmpty; +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action; +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action; +- (id<FLLRBNode>) min; +- (id) minKey; +- (id) maxKey; +- (BOOL) isRed; +- (int) check; + +@property (nonatomic, strong) id key; +@property (nonatomic, strong) id value; +@property (nonatomic, strong) FLLRBColor* color; +@property (nonatomic, strong) id<FLLRBNode> left; +@property (nonatomic, strong) id<FLLRBNode> right; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m new file mode 100644 index 0000000..adbc6ca --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m @@ -0,0 +1,87 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import "FLLRBEmptyNode.h" +#import "FLLRBValueNode.h" + +@implementation FLLRBEmptyNode + +@synthesize key, value, color, left, right; + +- (NSString *) description { + return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", key, value, (color ? @"true" : @"false")]; +} + ++ (id)emptyNode +{ + static dispatch_once_t pred = 0; + __strong static id _sharedObject = nil; + dispatch_once(&pred, ^{ + _sharedObject = [[self alloc] init]; // or some other init method + }); + return _sharedObject; +} + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight { + return self; +} + +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator { + FLLRBValueNode* result = [[FLLRBValueNode alloc] initWithKey:aKey withValue:aValue withColor:nil withLeft:nil withRight:nil]; + return result; +} + +- (id<FLLRBNode>) remove:(id) key withComparator:(NSComparator)aComparator { + return self; +} + +- (int) count { + return 0; +} + +- (BOOL) isEmpty { + return YES; +} + +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action { + return NO; +} + +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action { + return NO; +} + +- (id<FLLRBNode>) min { + return self; +} + +- (id) minKey { + return nil; +} + +- (id) maxKey { + return nil; +} + +- (BOOL) isRed { + return NO; +} + +- (int) check { + return 0; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h new file mode 100644 index 0000000..2634494 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h @@ -0,0 +1,45 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import <Foundation/Foundation.h> + +#define RED @true +#define BLACK @false + +typedef NSNumber FLLRBColor; + +@protocol FLLRBNode <NSObject> + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight; +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id<FLLRBNode>) remove:(id) key withComparator:(NSComparator)aComparator; +- (int) count; +- (BOOL) isEmpty; +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action; +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action; +- (id<FLLRBNode>) min; +- (id) minKey; +- (id) maxKey; +- (BOOL) isRed; +- (int) check; + +@property (nonatomic, strong) id key; +@property (nonatomic, strong) id value; +@property (nonatomic, strong) FLLRBColor* color; +@property (nonatomic, strong) id<FLLRBNode> left; +@property (nonatomic, strong) id<FLLRBNode> right; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h new file mode 100644 index 0000000..2c64b8a --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h @@ -0,0 +1,45 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import <Foundation/Foundation.h> +#import "FLLRBNode.h" + +@interface FLLRBValueNode : NSObject <FLLRBNode> + + +- (id)initWithKey:(id) key withValue:(id) value withColor:(FLLRBColor*) color withLeft:(id<FLLRBNode>)left withRight:(id<FLLRBNode>)right; +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight; +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id<FLLRBNode>) remove:(id) aKey withComparator:(NSComparator)aComparator; +- (int) count; +- (BOOL) isEmpty; +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action; +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action; +- (id<FLLRBNode>) min; +- (id) minKey; +- (id) maxKey; +- (BOOL) isRed; +- (int) check; + +- (BOOL) checkMaxDepth; + +@property (nonatomic, strong) id key; +@property (nonatomic, strong) id value; +@property (nonatomic, strong) FLLRBColor* color; +@property (nonatomic, strong) id<FLLRBNode> left; +@property (nonatomic, strong) id<FLLRBNode> right; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m new file mode 100644 index 0000000..f361278 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m @@ -0,0 +1,245 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import "FLLRBValueNode.h" +#import "FLLRBEmptyNode.h" + +@implementation FLLRBValueNode + +@synthesize key, value, color, left, right; + +- (NSString *) description { + return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", key, value, (color ? @"true" : @"false")]; +} + +- (id)initWithKey:(__unsafe_unretained id) aKey withValue:(__unsafe_unretained id) aValue withColor:(__unsafe_unretained FLLRBColor*) aColor withLeft:(__unsafe_unretained id<FLLRBNode>)aLeft withRight:(__unsafe_unretained id<FLLRBNode>)aRight +{ + self = [super init]; + if (self) { + self.key = aKey; + self.value = aValue; + self.color = aColor != nil ? aColor : RED; + self.left = aLeft != nil ? aLeft : [FLLRBEmptyNode emptyNode]; + self.right = aRight != nil ? aRight : [FLLRBEmptyNode emptyNode]; + } + return self; +} + +- (id)copyWith:(__unsafe_unretained id) aKey withValue:(__unsafe_unretained id) aValue withColor:(__unsafe_unretained FLLRBColor*) aColor withLeft:(__unsafe_unretained id<FLLRBNode>)aLeft withRight:(__unsafe_unretained id<FLLRBNode>)aRight { + return [[FLLRBValueNode alloc] initWithKey:(aKey != nil) ? aKey : self.key + withValue:(aValue != nil) ? aValue : self.value + withColor:(aColor != nil) ? aColor : self.color + withLeft:(aLeft != nil) ? aLeft : self.left + withRight:(aRight != nil) ? aRight : self.right]; +} + +- (int) count { + return [self.left count] + 1 + [self.right count]; +} + +- (BOOL) isEmpty { + return NO; +} + +/** +* Early terminates if aciton returns YES. +* @return The first truthy value returned by action, or the last falsey value returned by action. +*/ +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action { + return [self.left inorderTraversal:action] || + action(self.key, self.value) || + [self.right inorderTraversal:action]; +} + +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action { + return [self.right reverseTraversal:action] || + action(self.key, self.value) || + [self.left reverseTraversal:action]; +} + +- (id<FLLRBNode>) min { + if([self.left isEmpty]) { + return self; + } + else { + return [self.left min]; + } +} + +- (id) minKey { + return [[self min] key]; +} + +- (id) maxKey { + if([self.right isEmpty]) { + return self.key; + } + else { + return [self.right maxKey]; + } +} + +- (id<FLLRBNode>) insertKey:(__unsafe_unretained id) aKey forValue:(__unsafe_unretained id)aValue withComparator:(NSComparator)aComparator { + NSComparisonResult cmp = aComparator(aKey, self.key); + FLLRBValueNode* n = self; + + if(cmp == NSOrderedAscending) { + n = [n copyWith:nil withValue:nil withColor:nil withLeft:[n.left insertKey:aKey forValue:aValue withComparator:aComparator] withRight:nil]; + } + else if(cmp == NSOrderedSame) { + n = [n copyWith:nil withValue:aValue withColor:nil withLeft:nil withRight:nil]; + } + else { + n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[n.right insertKey:aKey forValue:aValue withComparator:aComparator]]; + } + + return [n fixUp]; +} + +- (id<FLLRBNode>) removeMin { + + if([self.left isEmpty]) { + return [FLLRBEmptyNode emptyNode]; + } + + FLLRBValueNode* n = self; + if(! [n.left isRed] && ! [n.left.left isRed]) { + n = [n moveRedLeft]; + } + + n = [n copyWith:nil withValue:nil withColor:nil withLeft:[(FLLRBValueNode*)n.left removeMin] withRight:nil]; + return [n fixUp]; +} + + +- (id<FLLRBNode>) fixUp { + FLLRBValueNode* n = self; + if([n.right isRed] && ! [n.left isRed]) n = [n rotateLeft]; + if([n.left isRed] && [n.left.left isRed]) n = [n rotateRight]; + if([n.left isRed] && [n.right isRed]) n = [n colorFlip]; + return n; +} + +- (FLLRBValueNode*) moveRedLeft { + FLLRBValueNode* n = [self colorFlip]; + if([n.right.left isRed]) { + n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[(FLLRBValueNode*)n.right rotateRight]]; + n = [n rotateLeft]; + n = [n colorFlip]; + } + return n; +} + +- (FLLRBValueNode*) moveRedRight { + FLLRBValueNode* n = [self colorFlip]; + if([n.left.left isRed]) { + n = [n rotateRight]; + n = [n colorFlip]; + } + return n; +} + +- (id<FLLRBNode>) rotateLeft { + id<FLLRBNode> nl = [self copyWith:nil withValue:nil withColor:RED withLeft:nil withRight:self.right.left]; + return [self.right copyWith:nil withValue:nil withColor:self.color withLeft:nl withRight:nil];; +} + +- (id<FLLRBNode>) rotateRight { + id<FLLRBNode> nr = [self copyWith:nil withValue:nil withColor:RED withLeft:self.left.right withRight:nil]; + return [self.left copyWith:nil withValue:nil withColor:self.color withLeft:nil withRight:nr]; +} + +- (id<FLLRBNode>) colorFlip { + id<FLLRBNode> nleft = [self.left copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.left.color boolValue]] withLeft:nil withRight:nil]; + id<FLLRBNode> nright = [self.right copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.right.color boolValue]] withLeft:nil withRight:nil]; + + return [self copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.color boolValue]] withLeft:nleft withRight:nright]; +} + +- (id<FLLRBNode>) remove:(__unsafe_unretained id) aKey withComparator:(NSComparator)comparator { + id<FLLRBNode> smallest; + FLLRBValueNode* n = self; + + if(comparator(aKey, n.key) == NSOrderedAscending) { + if(![n.left isEmpty] && ![n.left isRed] && ![n.left.left isRed]) { + n = [n moveRedLeft]; + } + n = [n copyWith:nil withValue:nil withColor:nil withLeft:[n.left remove:aKey withComparator:comparator] withRight:nil]; + } + else { + if([n.left isRed]) { + n = [n rotateRight]; + } + + if(![n.right isEmpty] && ![n.right isRed] && ![n.right.left isRed]) { + n = [n moveRedRight]; + } + + if(comparator(aKey, n.key) == NSOrderedSame) { + if([n.right isEmpty]) { + return [FLLRBEmptyNode emptyNode]; + } + else { + smallest = [n.right min]; + n = [n copyWith:smallest.key withValue:smallest.value withColor:nil withLeft:nil withRight:[(FLLRBValueNode*)n.right removeMin]]; + } + } + n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[n.right remove:aKey withComparator:comparator]]; + } + return [n fixUp]; +} + +- (BOOL) isRed { + return [self.color boolValue]; +} + +- (BOOL) checkMaxDepth { + int blackDepth = [self check]; + if(pow(2.0, blackDepth) <= ([self count] + 1)) { + return YES; + } + else { + return NO; + } +} + +- (int) check { + int blackDepth = 0; + + if([self isRed] && [self.left isRed]) { + @throw [[NSException alloc] initWithName:@"check" reason:@"Red node has a red child" userInfo:nil]; + } + + if([self.right isRed]) { + @throw [[NSException alloc] initWithName:@"check" reason:@"Right child is red" userInfo:nil]; + } + + blackDepth = [self.left check]; +// NSLog(err); + if(blackDepth != [self.right check]) { + NSString* err = [NSString stringWithFormat:@"(%@ -> %@)blackDepth: %d ; self.right check: %d", self.value, [self.color boolValue] ? @"red" : @"black", blackDepth, [self.right check]]; +// return 10; + @throw [[NSException alloc] initWithName:@"check" reason:err userInfo:nil]; + } + else { + int ret = blackDepth + ([self isRed] ? 0 : 1); +// NSLog(@"black depth is: %d; other is: %d, ret is: %d", blackDepth, ([self isRed] ? 0 : 1), ret); + return ret; + } +} + + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h new file mode 100644 index 0000000..d7fe835 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h @@ -0,0 +1,25 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import <Foundation/Foundation.h> +#import "FTreeSortedDictionary.h" + +@interface FTreeSortedDictionaryEnumerator : NSEnumerator + +- (id)initWithImmutableSortedDictionary:(FTreeSortedDictionary *)aDict startKey:(id)startKey isReverse:(BOOL)reverse; +- (id)nextObject; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m new file mode 100644 index 0000000..6636d1e --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m @@ -0,0 +1,99 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import "FTreeSortedDictionaryEnumerator.h" + +@interface FTreeSortedDictionaryEnumerator() +@property (nonatomic, strong) FTreeSortedDictionary* immutableSortedDictionary; +@property (nonatomic, strong) NSMutableArray* stack; +@property (nonatomic) BOOL isReverse; + +@end + +@implementation FTreeSortedDictionaryEnumerator + +- (id)initWithImmutableSortedDictionary:(FTreeSortedDictionary *)aDict + startKey:(id)startKey isReverse:(BOOL)reverse { + self = [super init]; + if (self) { + self.immutableSortedDictionary = aDict; + self.stack = [[NSMutableArray alloc] init]; + self.isReverse = reverse; + + NSComparator comparator = aDict.comparator; + id<FLLRBNode> node = self.immutableSortedDictionary.root; + + NSInteger cmp; + while(![node isEmpty]) { + cmp = startKey ? comparator(node.key, startKey) : 1; + // flip the comparison if we're going in reverse + if (self.isReverse) cmp *= -1; + + if (cmp < 0) { + // This node is less than our start key. Ignore it. + if (self.isReverse) { + node = node.left; + } else { + node = node.right; + } + } else if (cmp == 0) { + // This node is exactly equal to our start key. Push it on the stack, but stop iterating: + [self.stack addObject:node]; + break; + } else { + // This node is greater than our start key, add it to the stack and move on to the next one. + [self.stack addObject:node]; + if (self.isReverse) { + node = node.right; + } else { + node = node.left; + } + } + } + } + return self; +} + +- (id)nextObject { + if([self.stack count] == 0) { + return nil; + } + + id<FLLRBNode> node = nil; + @synchronized(self.stack) { + node = [self.stack lastObject]; + [self.stack removeLastObject]; + } + id result = node.key; + + if (self.isReverse) { + node = node.left; + while (![node isEmpty]) { + [self.stack addObject:node]; + node = node.right; + } + } else { + node = node.right; + while (![node isEmpty]) { + [self.stack addObject:node]; + node = node.left; + } + } + + return result; +} + +@end |