From bde743ed25166a0b320ae157bfb1d68064f531c9 Mon Sep 17 00:00:00 2001 From: Gil Date: Tue, 3 Oct 2017 08:55:22 -0700 Subject: Release 4.3.0 (#327) Initial release of Firestore at 0.8.0 Bump FirebaseCommunity to 0.1.3 --- .../Immutable/FSTArraySortedDictionary.h | 35 ++ .../Immutable/FSTArraySortedDictionary.m | 242 ++++++++ .../Immutable/FSTArraySortedDictionaryEnumerator.h | 26 + .../Immutable/FSTArraySortedDictionaryEnumerator.m | 54 ++ .../Immutable/FSTImmutableSortedDictionary.h | 120 ++++ .../Immutable/FSTImmutableSortedDictionary.m | 143 +++++ .../third_party/Immutable/FSTImmutableSortedSet.h | 47 ++ .../third_party/Immutable/FSTImmutableSortedSet.m | 144 +++++ Firestore/third_party/Immutable/FSTLLRBEmptyNode.h | 11 + Firestore/third_party/Immutable/FSTLLRBEmptyNode.m | 102 ++++ Firestore/third_party/Immutable/FSTLLRBNode.h | 68 +++ Firestore/third_party/Immutable/FSTLLRBValueNode.h | 29 + Firestore/third_party/Immutable/FSTLLRBValueNode.m | 308 ++++++++++ .../Immutable/FSTTreeSortedDictionary.h | 41 ++ .../Immutable/FSTTreeSortedDictionary.m | 382 ++++++++++++ .../Immutable/FSTTreeSortedDictionaryEnumerator.h | 21 + .../Immutable/FSTTreeSortedDictionaryEnumerator.m | 114 ++++ Firestore/third_party/Immutable/LICENSE | 21 + .../Tests/FSTArraySortedDictionaryTests.m | 467 +++++++++++++++ .../Tests/FSTImmutableSortedDictionary+Testing.h | 17 + .../Tests/FSTImmutableSortedDictionary+Testing.m | 17 + .../Tests/FSTImmutableSortedSet+Testing.h | 20 + .../Tests/FSTImmutableSortedSet+Testing.m | 17 + .../Immutable/Tests/FSTLLRBValueNode+Test.h | 10 + .../Immutable/Tests/FSTTreeSortedDictionaryTests.m | 655 +++++++++++++++++++++ 25 files changed, 3111 insertions(+) create mode 100644 Firestore/third_party/Immutable/FSTArraySortedDictionary.h create mode 100644 Firestore/third_party/Immutable/FSTArraySortedDictionary.m create mode 100644 Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.h create mode 100644 Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.m create mode 100644 Firestore/third_party/Immutable/FSTImmutableSortedDictionary.h create mode 100644 Firestore/third_party/Immutable/FSTImmutableSortedDictionary.m create mode 100644 Firestore/third_party/Immutable/FSTImmutableSortedSet.h create mode 100644 Firestore/third_party/Immutable/FSTImmutableSortedSet.m create mode 100644 Firestore/third_party/Immutable/FSTLLRBEmptyNode.h create mode 100644 Firestore/third_party/Immutable/FSTLLRBEmptyNode.m create mode 100644 Firestore/third_party/Immutable/FSTLLRBNode.h create mode 100644 Firestore/third_party/Immutable/FSTLLRBValueNode.h create mode 100644 Firestore/third_party/Immutable/FSTLLRBValueNode.m create mode 100644 Firestore/third_party/Immutable/FSTTreeSortedDictionary.h create mode 100644 Firestore/third_party/Immutable/FSTTreeSortedDictionary.m create mode 100644 Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.h create mode 100644 Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.m create mode 100644 Firestore/third_party/Immutable/LICENSE create mode 100644 Firestore/third_party/Immutable/Tests/FSTArraySortedDictionaryTests.m create mode 100644 Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.h create mode 100644 Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.m create mode 100644 Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.h create mode 100644 Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.m create mode 100644 Firestore/third_party/Immutable/Tests/FSTLLRBValueNode+Test.h create mode 100644 Firestore/third_party/Immutable/Tests/FSTTreeSortedDictionaryTests.m (limited to 'Firestore/third_party') diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionary.h b/Firestore/third_party/Immutable/FSTArraySortedDictionary.h new file mode 100644 index 0000000..4b78360 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTArraySortedDictionary.h @@ -0,0 +1,35 @@ +#import + +#import "FSTImmutableSortedDictionary.h" + +NS_ASSUME_NONNULL_BEGIN + +/** + * FSTArraySortedDictionary is an array backed implementation of FSTImmutableSortedDictionary. + * + * You should not use this class directly. You should use FSTImmutableSortedDictionary. + * + * FSTArraySortedDictionary uses arrays and linear lookups to achieve good memory efficiency while + * maintaining good performance for small collections. It also uses fewer allocations than a + * comparable red black tree. To avoid degrading performance with increasing collection size it + * will automatically convert to a FSTTreeSortedDictionary after an insert call above a certain + * threshold. + */ +@interface FSTArraySortedDictionary : + FSTImmutableSortedDictionary + ++ (FSTArraySortedDictionary *) + dictionaryWithDictionary:(NSDictionary *)dictionary + comparator:(NSComparator)comparator; + +- (id)init __attribute__((unavailable("Use initWithComparator:keys:values: instead."))); + +- (instancetype)initWithComparator:(NSComparator)comparator; + +- (instancetype)initWithComparator:(NSComparator)comparator + keys:(NSArray *)keys + values:(NSArray *)values NS_DESIGNATED_INITIALIZER; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionary.m b/Firestore/third_party/Immutable/FSTArraySortedDictionary.m new file mode 100644 index 0000000..fd3bfd7 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTArraySortedDictionary.m @@ -0,0 +1,242 @@ +#import "FSTArraySortedDictionary.h" + +#import "FSTArraySortedDictionaryEnumerator.h" +#import "FSTAssert.h" +#import "FSTTreeSortedDictionary.h" + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTArraySortedDictionary () +@property(nonatomic, copy, readwrite) NSComparator comparator; +@property(nonatomic, strong) NSArray *keys; +@property(nonatomic, strong) NSArray *values; +@end + +@implementation FSTArraySortedDictionary + ++ (FSTArraySortedDictionary *)dictionaryWithDictionary:(NSDictionary *)dictionary + comparator:(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 FSTImmutableSortedDictionary with keys " + @"with same ordering!"]; + } + } + }]; + + NSMutableArray *values = [NSMutableArray arrayWithCapacity:keys.count]; + NSInteger pos = 0; + for (id key in keys) { + values[pos++] = dictionary[key]; + } + FSTAssert(values.count == keys.count, @"We added as many keys as values"); + return [[FSTArraySortedDictionary alloc] initWithComparator:comparator keys:keys values:values]; +} + +- (id)initWithComparator:(NSComparator)comparator { + return [self initWithComparator:comparator keys:[NSArray array] values:[NSArray array]]; +} + +// Designated initializer. +- (id)initWithComparator:(NSComparator)comparator keys:(NSArray *)keys values:(NSArray *)values { + self = [super init]; + if (self != nil) { + FSTAssert(keys.count == values.count, @"keys and values must have the same count"); + _comparator = comparator; + _keys = keys; + _values = values; + } + return self; +} + +/** Returns the index of the first position where array[position] >= key. */ +- (int)findInsertPositionForKey:(id)key { + int 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; +} + +- (FSTImmutableSortedDictionary *)dictionaryBySettingObject:(id)value forKey:(id)key { + 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 >= kSortedDictionaryArrayToRBTreeSizeThreshold) { + 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 [FSTTreeSortedDictionary dictionaryWithDictionary:dict comparator: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 [[FSTArraySortedDictionary 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 [[FSTArraySortedDictionary alloc] initWithComparator:self.comparator + keys:newKeys + values:newValues]; + } +} + +- (FSTImmutableSortedDictionary *)dictionaryByRemovingObjectForKey:(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 [[FSTArraySortedDictionary alloc] initWithComparator:self.comparator + keys:newKeys + values:newValues]; + } +} + +- (nullable id)objectForKey:(id)key { + NSInteger pos = [self findKey:key]; + if (pos == NSNotFound) { + return nil; + } else { + return self.values[pos]; + } +} + +- (nullable id)predecessorKey:(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]; + } +} + +- (NSUInteger)indexOfKey:(id)key { + return [self findKey:key]; +} + +- (BOOL)isEmpty { + return self.keys.count == 0; +} + +- (NSUInteger)count { + return 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)containsKey:(id)key { + return [self findKey:key] != NSNotFound; +} + +- (NSEnumerator *)keyEnumerator { + return [self.keys objectEnumerator]; +} + +- (NSEnumerator *)keyEnumeratorFrom:(id)startKey { + return [self keyEnumeratorFrom:startKey to:nil]; +} + +- (NSEnumerator *)keyEnumeratorFrom:(id)startKey to:(nullable id)endKey { + int start = [self findInsertPositionForKey:startKey]; + int end = (int)self.count; + if (endKey) { + end = [self findInsertPositionForKey:endKey]; + } + return [[FSTArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys + startPos:start + endPos:end + isReverse:NO]; +} + +- (NSEnumerator *)reverseKeyEnumerator { + return [self.keys reverseObjectEnumerator]; +} + +- (NSEnumerator *)reverseKeyEnumeratorFrom:(id)startKey { + int 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 [[FSTArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys + startPos:startPos + endPos:-1 + isReverse:YES]; +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.h b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.h new file mode 100644 index 0000000..36c4f32 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.h @@ -0,0 +1,26 @@ +#import + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTArraySortedDictionaryEnumerator : NSEnumerator + +- (id)init __attribute__((unavailable("Use initWithKeys:startPos:endPos:isReverse: instead."))); + +/** + * An enumerator for use with a dictionary. + * + * @param keys The keys to enumerator within. + * @param start The index of the initial key to return. + * @param end If end is after (or equal to) start (or before, if reverse), then the enumerator will + * stop and not return the value once it reaches end. + */ +- (instancetype)initWithKeys:(NSArray *)keys + startPos:(int)start + endPos:(int)end + isReverse:(BOOL)reverse NS_DESIGNATED_INITIALIZER; + +- (_Nullable ValueType)nextObject; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.m b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.m new file mode 100644 index 0000000..e8fdfcc --- /dev/null +++ b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.m @@ -0,0 +1,54 @@ +#import "FSTArraySortedDictionaryEnumerator.h" + +NS_ASSUME_NONNULL_BEGIN + +// clang-format off +// For some reason, clang-format messes this line up... +@interface FSTArraySortedDictionaryEnumerator () +@property(nonatomic, assign) int pos; +@property(nonatomic, assign) int start; +@property(nonatomic, assign) int end; +@property(nonatomic, assign) BOOL reverse; +@property(nonatomic, strong) NSArray *keys; +@end +// clang-format on + +@implementation FSTArraySortedDictionaryEnumerator + +- (id)initWithKeys:(NSArray *)keys startPos:(int)start endPos:(int)end isReverse:(BOOL)reverse { + self = [super init]; + if (self != nil) { + _keys = keys; + _start = start; + _end = end; + _pos = start; + _reverse = reverse; + } + return self; +} + +- (nullable id)nextObject { + if (self.pos < 0 || self.pos >= self.keys.count) { + return nil; + } + if (self.reverse) { + if (self.pos <= self.end) { + return nil; + } + } else { + if (self.pos >= self.end) { + return nil; + } + } + int pos = self.pos; + if (self.reverse) { + self.pos--; + } else { + self.pos++; + } + return self.keys[pos]; +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.h b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.h new file mode 100644 index 0000000..a2264ec --- /dev/null +++ b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.h @@ -0,0 +1,120 @@ +/** + * 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 + +NS_ASSUME_NONNULL_BEGIN + +/** + * 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. + */ +extern const int kSortedDictionaryArrayToRBTreeSizeThreshold; + +/** + * FSTImmutableSortedDictionary is a dictionary. It is immutable, but has methods to create new + * dictionaries that are mutations of it, in an efficient way. + */ +@interface FSTImmutableSortedDictionary : NSObject + ++ (FSTImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator; ++ (FSTImmutableSortedDictionary *)dictionaryWithDictionary: + (NSDictionary *)dictionary + comparator:(NSComparator)comparator; + +/** + * Creates a new dictionary identical to this one, but with a key-value pair added or updated. + * + * @param aValue The value to associate with the key. + * @param aKey The key to insert/update. + * @return A new dictionary with the added/updated value. + */ +- (FSTImmutableSortedDictionary *)dictionaryBySettingObject:(ValueType)aValue + forKey:(KeyType)aKey; + +/** + * Creates a new dictionary identical to this one, but with a key removed from it. + * + * @param aKey The key to remove. + * @return A new dictionary without that value. + */ +- (FSTImmutableSortedDictionary *)dictionaryByRemovingObjectForKey: + (KeyType)aKey; + +/** + * Looks up a value in the dictionary. + * + * @param key The key to look up. + * @return The value for the key, if present. + */ +- (nullable ValueType)objectForKey:(KeyType)key; + +/** + * Looks up a value in the dictionary. + * + * @param key The key to look up. + * @return The value for the key, if present. + */ +- (ValueType)objectForKeyedSubscript:(KeyType)key; + +/** + * Gets the key before the given key in sorted order. + * + * @param key The key to look before. + * @return The key before the given one. + */ +- (nullable KeyType)predecessorKey:(KeyType)key; + +/** + * Returns the index of the key or NSNotFound if the key is not found. + * + * @param key The key to return the index for. + * @return The index of the key, or NSNotFound if key not found. + */ +- (NSUInteger)indexOfKey:(KeyType)key; + +/** Returns true if the dictionary contains no elements. */ +- (BOOL)isEmpty; + +/** Returns the number of items in this dictionary. */ +- (NSUInteger)count; + +/** Returns the smallest key in this dictionary. */ +- (KeyType)minKey; + +/** Returns the largest key in this dictionary. */ +- (KeyType)maxKey; + +/** Calls the given block with each of the items in this dictionary, in order. */ +- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(KeyType key, ValueType value, BOOL *stop))block; + +/** Calls the given block with each of the items in this dictionary, in reverse order. */ +- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse + usingBlock:(void (^)(KeyType key, ValueType value, BOOL *stop))block; + +/** Returns true if the dictionary contains the given key. */ +- (BOOL)containsKey:(KeyType)key; + +- (NSEnumerator *)keyEnumerator; +- (NSEnumerator *)keyEnumeratorFrom:(KeyType)startKey; +/** Enumerator for the range [startKey, endKey). */ +- (NSEnumerator *)keyEnumeratorFrom:(KeyType)startKey to:(nullable KeyType)endKey; +- (NSEnumerator *)reverseKeyEnumerator; +- (NSEnumerator *)reverseKeyEnumeratorFrom:(KeyType)startKey; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.m b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.m new file mode 100644 index 0000000..a858529 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.m @@ -0,0 +1,143 @@ +#import "FSTImmutableSortedDictionary.h" + +#import "FSTArraySortedDictionary.h" +#import "FSTClasses.h" +#import "FSTTreeSortedDictionary.h" + +NS_ASSUME_NONNULL_BEGIN + +const int kSortedDictionaryArrayToRBTreeSizeThreshold = 25; + +@implementation FSTImmutableSortedDictionary + ++ (FSTImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator { + return [[FSTArraySortedDictionary alloc] initWithComparator:comparator]; +} + ++ (FSTImmutableSortedDictionary *)dictionaryWithDictionary:(NSDictionary *)dictionary + comparator:(NSComparator)comparator { + if (dictionary.count <= kSortedDictionaryArrayToRBTreeSizeThreshold) { + return [FSTArraySortedDictionary dictionaryWithDictionary:dictionary comparator:comparator]; + } else { + return [FSTTreeSortedDictionary dictionaryWithDictionary:dictionary comparator:comparator]; + } +} + +- (FSTImmutableSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (FSTImmutableSortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (BOOL)isEqual:(id)object { + if (![object isKindOfClass:[FSTImmutableSortedDictionary class]]) { + return NO; + } + + // TODO(klimt): We could make this more efficient if we put the comparison inside the + // implementations and short-circuit if they share the same tree node, for instance. + FSTImmutableSortedDictionary *other = (FSTImmutableSortedDictionary *)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; +} + +- (nullable id)objectForKey:(id)key { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (id)objectForKeyedSubscript:(id)key { + return [self objectForKey:key]; +} + +- (nullable id)predecessorKey:(id)key { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (NSUInteger)indexOfKey:(id)key { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (BOOL)isEmpty { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (NSUInteger)count { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (id)minKey { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (id)maxKey { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (BOOL)containsKey:(id)key { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (NSEnumerator *)keyEnumerator { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (NSEnumerator *)keyEnumeratorFrom:(id)startKey { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (NSEnumerator *)keyEnumeratorFrom:(id)startKey to:(nullable id)endKey { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (NSEnumerator *)reverseKeyEnumerator { + @throw FSTAbstractMethodException(); // NOLINT +} + +- (NSEnumerator *)reverseKeyEnumeratorFrom:(id)startKey { + @throw FSTAbstractMethodException(); // NOLINT +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedSet.h b/Firestore/third_party/Immutable/FSTImmutableSortedSet.h new file mode 100644 index 0000000..d0f9906 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTImmutableSortedSet.h @@ -0,0 +1,47 @@ +#import + +NS_ASSUME_NONNULL_BEGIN + +/** + * FSTImmutableSortedSet is a set. It is immutable, but has methods to create new sets that are + * mutations of it, in an efficient way. + */ +@interface FSTImmutableSortedSet : NSObject + ++ (FSTImmutableSortedSet *)setWithComparator:(NSComparator)comparator; + ++ (FSTImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)array + comparator:(NSComparator)comparator; + +- (BOOL)containsObject:(KeyType)object; + +- (FSTImmutableSortedSet *)setByAddingObject:(KeyType)object; +- (FSTImmutableSortedSet *)setByRemovingObject:(KeyType)object; + +- (KeyType)firstObject; +- (KeyType)lastObject; +- (NSUInteger)count; +- (BOOL)isEmpty; + +- (KeyType)predecessorObject:(KeyType)entry; + +/** + * Returns the index of the object or NSNotFound if the object is not found. + * + * @param object The object to return the index for. + * @return The index of the object, or NSNotFound if not found. + */ +- (NSUInteger)indexOfObject:(KeyType)object; + +- (void)enumerateObjectsUsingBlock:(void (^)(KeyType obj, BOOL *stop))block; +- (void)enumerateObjectsFrom:(KeyType)start + to:(_Nullable KeyType)end + usingBlock:(void (^)(KeyType obj, BOOL *stop))block; +- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(KeyType obj, BOOL *stop))block; + +- (NSEnumerator *)objectEnumerator; +- (NSEnumerator *)objectEnumeratorFrom:(KeyType)startKey; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedSet.m b/Firestore/third_party/Immutable/FSTImmutableSortedSet.m new file mode 100644 index 0000000..a13a79e --- /dev/null +++ b/Firestore/third_party/Immutable/FSTImmutableSortedSet.m @@ -0,0 +1,144 @@ +#import "FSTImmutableSortedSet.h" + +#import "FSTImmutableSortedDictionary.h" + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTImmutableSortedSet () +@property(nonatomic, strong) FSTImmutableSortedDictionary *dictionary; +@end + +@implementation FSTImmutableSortedSet + ++ (FSTImmutableSortedSet *)setWithComparator:(NSComparator)comparator { + return [FSTImmutableSortedSet setWithKeysFromDictionary:@{} comparator:comparator]; +} + ++ (FSTImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)dictionary + comparator:(NSComparator)comparator { + FSTImmutableSortedDictionary *setDict = + [FSTImmutableSortedDictionary dictionaryWithDictionary:dictionary comparator:comparator]; + return [[FSTImmutableSortedSet alloc] initWithDictionary:setDict]; +} + +// Designated initializer. +- (id)initWithDictionary:(FSTImmutableSortedDictionary *)dictionary { + self = [super init]; + if (self != nil) { + _dictionary = dictionary; + } + return self; +} + +- (BOOL)isEqual:(id)object { + if (![object isKindOfClass:[FSTImmutableSortedSet class]]) { + return NO; + } + + FSTImmutableSortedSet *other = (FSTImmutableSortedSet *)object; + + return [self.dictionary isEqual:other.dictionary]; +} + +- (NSUInteger)hash { + return [self.dictionary hash]; +} + +- (BOOL)containsObject:(id)object { + return [self.dictionary containsKey:object]; +} + +- (FSTImmutableSortedSet *)setByAddingObject:(id)object { + FSTImmutableSortedDictionary *newDictionary = + [self.dictionary dictionaryBySettingObject:[NSNull null] forKey:object]; + if (newDictionary != self.dictionary) { + return [[FSTImmutableSortedSet alloc] initWithDictionary:newDictionary]; + } else { + return self; + } +} + +- (FSTImmutableSortedSet *)setByRemovingObject:(id)object { + FSTImmutableSortedDictionary *newDictionary = + [self.dictionary dictionaryByRemovingObjectForKey:object]; + if (newDictionary != self.dictionary) { + return [[FSTImmutableSortedSet alloc] initWithDictionary:newDictionary]; + } else { + return self; + } +} + +- (id)firstObject { + return [self.dictionary minKey]; +} + +- (id)lastObject { + return [self.dictionary maxKey]; +} + +- (id)predecessorObject:(id)entry { + return [self.dictionary predecessorKey:entry]; +} + +- (NSUInteger)indexOfObject:(id)object { + return [self.dictionary indexOfKey:object]; +} + +- (NSUInteger)count { + return [self.dictionary count]; +} + +- (BOOL)isEmpty { + return [self.dictionary isEmpty]; +} + +- (void)enumerateObjectsUsingBlock:(void (^)(id, BOOL *))block { + [self enumerateObjectsReverse:NO usingBlock:block]; +} + +- (void)enumerateObjectsFrom:(id)start to:(_Nullable id)end usingBlock:(void (^)(id, BOOL *))block { + NSEnumerator *enumerator = [self.dictionary keyEnumeratorFrom:start to:end]; + id item = [enumerator nextObject]; + while (item) { + BOOL stop = NO; + block(item, &stop); + if (stop) { + return; + } + item = [enumerator nextObject]; + } +} + +- (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]; +} + +- (NSEnumerator *)objectEnumeratorFrom:(id)startKey { + return [self.dictionary keyEnumeratorFrom:startKey]; +} + +- (NSString *)description { + NSMutableString *str = [[NSMutableString alloc] init]; + __block BOOL first = YES; + [str appendString:@"FSTImmutableSortedSet ( "]; + [self enumerateObjectsUsingBlock:^(id obj, BOOL *stop) { + if (!first) { + [str appendString:@", "]; + } + first = NO; + [str appendString:[NSString stringWithFormat:@"%@", obj]]; + }]; + [str appendString:@" )"]; + return str; +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTLLRBEmptyNode.h b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.h new file mode 100644 index 0000000..4c3c2af --- /dev/null +++ b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.h @@ -0,0 +1,11 @@ +#import + +#import "FSTLLRBNode.h" + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTLLRBEmptyNode : NSObject ++ (instancetype)emptyNode; +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTLLRBEmptyNode.m b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.m new file mode 100644 index 0000000..ec49c2c --- /dev/null +++ b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.m @@ -0,0 +1,102 @@ +#import "FSTLLRBEmptyNode.h" + +#import "FSTLLRBValueNode.h" + +NS_ASSUME_NONNULL_BEGIN + +@implementation FSTLLRBEmptyNode + +- (NSString *)description { + return @"[empty node]"; +} + ++ (instancetype)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; +} + +- (nullable id)key { + return nil; +} + +- (nullable id)value { + return nil; +} + +- (FSTLLRBColor)color { + return FSTLLRBColorUnspecified; +} + +- (nullable id)left { + return nil; +} + +- (nullable id)right { + return nil; +} + +- (instancetype)copyWith:(id _Nullable)aKey + withValue:(id _Nullable)aValue + withColor:(FSTLLRBColor)aColor + withLeft:(id _Nullable)aLeft + withRight:(id _Nullable)aRight { + // This class is a singleton anyway, so this is more efficient than calling the constructor again. + return self; +} + +- (id)insertKey:(id)aKey forValue:(id)aValue withComparator:(NSComparator)aComparator { + FSTLLRBValueNode *result = [[FSTLLRBValueNode alloc] initWithKey:aKey + withValue:aValue + withColor:FSTLLRBColorUnspecified + withLeft:nil + withRight:nil]; + return result; +} + +- (id)remove:(id)key withComparator:(NSComparator)aComparator { + return self; +} + +- (NSUInteger)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)min { + return self; +} + +- (nullable id)minKey { + return nil; +} + +- (nullable id)maxKey { + return nil; +} + +- (BOOL)isRed { + return NO; +} + +- (int)check { + return 0; +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTLLRBNode.h b/Firestore/third_party/Immutable/FSTLLRBNode.h new file mode 100644 index 0000000..082b875 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTLLRBNode.h @@ -0,0 +1,68 @@ +#import + +NS_ASSUME_NONNULL_BEGIN + +/** + * A FSTLLRBColor is the color of a tree node. It can be RED, BLACK, or unset. + */ +typedef NS_ENUM(NSInteger, FSTLLRBColor) { + FSTLLRBColorUnspecified = 0, + FSTLLRBColorRed = 1, + FSTLLRBColorBlack = 2, +}; + +/** + * FSTLLRBNode is the interface for a node in a FSTTreeSortedDictionary. + */ +@protocol FSTLLRBNode + +/** + * Creates a copy of the given node, changing any values that were specified. + * For any parameter that is left as nil, this instance's value will be used. + */ +- (instancetype)copyWith:(nullable id)aKey + withValue:(nullable id)aValue + withColor:(FSTLLRBColor)aColor + withLeft:(nullable id)aLeft + withRight:(nullable id)aRight; + +/** Returns a tree node with the given key-value pair set/updated. */ +- (id)insertKey:(id)aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; + +/** Returns a tree node with the given key removed. */ +- (id)remove:(id)key withComparator:(NSComparator)aComparator; + +/** Returns the number of elements at this node or beneath it in the tree. */ +- (NSUInteger)count; + +/** Returns true if this is an FSTLLRBEmptyNode -- a leaf node in the tree. */ +- (BOOL)isEmpty; + +- (BOOL)inorderTraversal:(BOOL (^)(id key, id value))action; +- (BOOL)reverseTraversal:(BOOL (^)(id key, id value))action; + +/** Returns the left-most node under (or including) this node. */ +- (id)min; + +/** Returns the key of the left-most node under (or including) this node. */ +- (nullable id)minKey; + +/** Returns the key of the right-most node under (or including) this node. */ +- (nullable id)maxKey; + +/** Returns true if this node is red (as opposed to black). */ +- (BOOL)isRed; + +/** Checks that this node and below it hold the red-black invariants. Throws otherwise. */ +- (int)check; + +// Accessors for properties. +- (nullable id)key; +- (nullable id)value; +- (FSTLLRBColor)color; +- (nullable id)left; +- (nullable id)right; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTLLRBValueNode.h b/Firestore/third_party/Immutable/FSTLLRBValueNode.h new file mode 100644 index 0000000..4a0873c --- /dev/null +++ b/Firestore/third_party/Immutable/FSTLLRBValueNode.h @@ -0,0 +1,29 @@ +#import + +#import "FSTLLRBNode.h" + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTLLRBValueNode : NSObject + +- (id)init __attribute__(( + unavailable("Use initWithKey:withValue:withColor:withLeft:withRight: instead."))); + +- (instancetype)initWithKey:(nullable id)key + withValue:(nullable id)value + withColor:(FSTLLRBColor)color + withLeft:(nullable id)left + withRight:(nullable id)right NS_DESIGNATED_INITIALIZER; + +@property(nonatomic, assign, readonly) FSTLLRBColor color; +@property(nonatomic, strong, readonly, nullable) id key; +@property(nonatomic, strong, readonly, nullable) id value; +@property(nonatomic, strong, readonly, nullable) id right; + +// This property cannot be readonly, because it is set when building the tree. +// TODO(klimt): Find a way to build the tree without mutating this. +@property(nonatomic, strong, nullable) id left; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTLLRBValueNode.m b/Firestore/third_party/Immutable/FSTLLRBValueNode.m new file mode 100644 index 0000000..d048012 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTLLRBValueNode.m @@ -0,0 +1,308 @@ +#import "FSTLLRBValueNode.h" + +#import "FSTAssert.h" +#import "FSTLLRBEmptyNode.h" + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTLLRBValueNode () +@property(nonatomic, assign) FSTLLRBColor color; +@property(nonatomic, assign) NSUInteger count; +@property(nonatomic, strong) id key; +@property(nonatomic, strong) id value; +@property(nonatomic, strong) id right; +@end + +@implementation FSTLLRBValueNode + +- (NSString *)colorDescription { + NSString *color = @"unspecified"; + if (self.color == FSTLLRBColorRed) { + color = @"red"; + } else if (self.color == FSTLLRBColorBlack) { + color = @"black"; + } + return color; +} + +- (NSString *)description { + NSString *color = self.colorDescription; + return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", self.key, self.value, color]; +} + +// Designated initializer. +- (instancetype)initWithKey:(id _Nullable)aKey + withValue:(id _Nullable)aValue + withColor:(FSTLLRBColor)aColor + withLeft:(id _Nullable)aLeft + withRight:(id _Nullable)aRight { + self = [super init]; + if (self) { + _key = aKey; + _value = aValue; + _color = aColor != FSTLLRBColorUnspecified ? aColor : FSTLLRBColorRed; + _left = aLeft != nil ? aLeft : [FSTLLRBEmptyNode emptyNode]; + _right = aRight != nil ? aRight : [FSTLLRBEmptyNode emptyNode]; + _count = NSNotFound; + } + return self; +} + +- (instancetype)copyWith:(id _Nullable)aKey + withValue:(id _Nullable)aValue + withColor:(FSTLLRBColor)aColor + withLeft:(id _Nullable)aLeft + withRight:(id _Nullable)aRight { + return [[FSTLLRBValueNode alloc] + initWithKey:(aKey != nil) ? aKey : self.key + withValue:(aValue != nil) ? aValue : self.value + withColor:(aColor != FSTLLRBColorUnspecified) ? aColor : self.color + withLeft:(aLeft != nil) ? aLeft : self.left + withRight:(aRight != nil) ? aRight : self.right]; +} + +- (void)setLeft:(nullable id)left { + // Setting the left node should be only done by the builder, so doing it after someone has + // memoized count is an error. + FSTAssert(_count == NSNotFound, @"Can't update left node after using count"); + _left = left; +} + +- (NSUInteger)count { + if (_count == NSNotFound) { + _count = _left.count + 1 + _right.count; + } + return _count; +} + +- (BOOL)isEmpty { + return NO; +} + +/** + * Early terminates if action 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)min { + if ([self.left isEmpty]) { + return self; + } else { + return [self.left min]; + } +} + +- (nullable id)minKey { + return [[self min] key]; +} + +- (nullable id)maxKey { + if ([self.right isEmpty]) { + return self.key; + } else { + return [self.right maxKey]; + } +} + +- (id)insertKey:(id)aKey forValue:(id)aValue withComparator:(NSComparator)aComparator { + NSComparisonResult cmp = aComparator(aKey, self.key); + FSTLLRBValueNode *n = self; + + if (cmp == NSOrderedAscending) { + n = [n copyWith:nil + withValue:nil + withColor:FSTLLRBColorUnspecified + withLeft:[n.left insertKey:aKey forValue:aValue withComparator:aComparator] + withRight:nil]; + } else if (cmp == NSOrderedSame) { + n = [n copyWith:nil + withValue:aValue + withColor:FSTLLRBColorUnspecified + withLeft:nil + withRight:nil]; + } else { + n = [n copyWith:nil + withValue:nil + withColor:FSTLLRBColorUnspecified + withLeft:nil + withRight:[n.right insertKey:aKey forValue:aValue withComparator:aComparator]]; + } + + return [n fixUp]; +} + +- (id)removeMin { + if ([self.left isEmpty]) { + return [FSTLLRBEmptyNode emptyNode]; + } + + FSTLLRBValueNode *n = self; + if (![n.left isRed] && ![n.left.left isRed]) { + n = [n moveRedLeft]; + } + + n = [n copyWith:nil + withValue:nil + withColor:FSTLLRBColorUnspecified + withLeft:[(FSTLLRBValueNode *)n.left removeMin] + withRight:nil]; + return [n fixUp]; +} + +- (id)fixUp { + FSTLLRBValueNode *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; +} + +- (FSTLLRBValueNode *)moveRedLeft { + FSTLLRBValueNode *n = [self colorFlip]; + if ([n.right.left isRed]) { + n = [n copyWith:nil + withValue:nil + withColor:FSTLLRBColorUnspecified + withLeft:nil + withRight:[(FSTLLRBValueNode *)n.right rotateRight]]; + n = [n rotateLeft]; + n = [n colorFlip]; + } + return n; +} + +- (FSTLLRBValueNode *)moveRedRight { + FSTLLRBValueNode *n = [self colorFlip]; + if ([n.left.left isRed]) { + n = [n rotateRight]; + n = [n colorFlip]; + } + return n; +} + +- (id)rotateLeft { + id nl = [self copyWith:nil + withValue:nil + withColor:FSTLLRBColorRed + withLeft:nil + withRight:self.right.left]; + return [self.right copyWith:nil withValue:nil withColor:self.color withLeft:nl withRight:nil]; +} + +- (id)rotateRight { + id nr = [self copyWith:nil + withValue:nil + withColor:FSTLLRBColorRed + withLeft:self.left.right + withRight:nil]; + return [self.left copyWith:nil withValue:nil withColor:self.color withLeft:nil withRight:nr]; +} + +- (id)colorFlip { + FSTLLRBColor color = self.color == FSTLLRBColorBlack ? FSTLLRBColorRed : FSTLLRBColorBlack; + FSTLLRBColor leftColor = + self.left.color == FSTLLRBColorBlack ? FSTLLRBColorRed : FSTLLRBColorBlack; + FSTLLRBColor rightColor = + self.right.color == FSTLLRBColorBlack ? FSTLLRBColorRed : FSTLLRBColorBlack; + + id nleft = + [self.left copyWith:nil withValue:nil withColor:leftColor withLeft:nil withRight:nil]; + id nright = + [self.right copyWith:nil withValue:nil withColor:rightColor withLeft:nil withRight:nil]; + + return [self copyWith:nil withValue:nil withColor:color withLeft:nleft withRight:nright]; +} + +- (id)remove:(id)aKey withComparator:(NSComparator)comparator { + id smallest; + FSTLLRBValueNode *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:FSTLLRBColorUnspecified + 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 [FSTLLRBEmptyNode emptyNode]; + } else { + smallest = [n.right min]; + n = [n copyWith:smallest.key + withValue:smallest.value + withColor:FSTLLRBColorUnspecified + withLeft:nil + withRight:[(FSTLLRBValueNode *)n.right removeMin]]; + } + } + n = [n copyWith:nil + withValue:nil + withColor:FSTLLRBColorUnspecified + withLeft:nil + withRight:[n.right remove:aKey withComparator:comparator]]; + } + return [n fixUp]; +} + +- (BOOL)isRed { + return self.color == FSTLLRBColorRed; +} + +- (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]; + if (blackDepth != [self.right check]) { + NSString *err = + [NSString stringWithFormat:@"(%@ -> %@)blackDepth: %d ; self.right check: %d", self.value, + self.colorDescription, blackDepth, [self.right check]]; + @throw [[NSException alloc] initWithName:@"check" reason:err userInfo:nil]; + } else { + int ret = blackDepth + ([self isRed] ? 0 : 1); + return ret; + } +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionary.h b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.h new file mode 100644 index 0000000..6c26e5f --- /dev/null +++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.h @@ -0,0 +1,41 @@ +/** + * 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 + +#import "FSTImmutableSortedDictionary.h" +#import "FSTLLRBNode.h" + +NS_ASSUME_NONNULL_BEGIN + +/** + * FSTTreeSortedDictionary is a tree-based implementation of FSTImmutableSortedDictionary. + * You should not use this class directly. You should use FSTImmutableSortedDictionary. + */ +@interface FSTTreeSortedDictionary : + FSTImmutableSortedDictionary + +@property(nonatomic, copy, readonly) NSComparator comparator; +@property(nonatomic, strong, readonly) id root; + +- (id)init __attribute__((unavailable("Use initWithComparator:withRoot: instead."))); + +- (instancetype)initWithComparator:(NSComparator)aComparator; + +- (instancetype)initWithComparator:(NSComparator)aComparator + withRoot:(id)aRoot NS_DESIGNATED_INITIALIZER; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionary.m b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.m new file mode 100644 index 0000000..4059951 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.m @@ -0,0 +1,382 @@ +#import "FSTTreeSortedDictionary.h" + +#import "FSTLLRBEmptyNode.h" +#import "FSTLLRBValueNode.h" +#import "FSTTreeSortedDictionaryEnumerator.h" + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTTreeSortedDictionary () + +- (FSTTreeSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey; + +@property(nonatomic, strong) id root; +@property(nonatomic, copy, readwrite) NSComparator comparator; +@end + +@implementation FSTTreeSortedDictionary + ++ (FSTTreeSortedDictionary *)dictionaryWithDictionary:(NSDictionary *)dictionary + comparator:(NSComparator)comparator { + __block FSTTreeSortedDictionary *dict = + [[FSTTreeSortedDictionary alloc] initWithComparator:comparator]; + [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) { + dict = [dict dictionaryBySettingObject:obj forKey:key]; + }]; + return dict; +} + +- (id)initWithComparator:(NSComparator)aComparator { + return [self initWithComparator:aComparator withRoot:[FSTLLRBEmptyNode emptyNode]]; +} + +// Designated initializer. +- (id)initWithComparator:(NSComparator)aComparator withRoot:(id)aRoot { + self = [super init]; + if (self) { + self.root = aRoot; + self.comparator = aComparator; + } + return self; +} + +/** + * Returns a copy of the map, with the specified key/value added or replaced. + */ +- (FSTTreeSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey { + return [[FSTTreeSortedDictionary alloc] + initWithComparator:self.comparator + withRoot:[[self.root insertKey:aKey forValue:aValue withComparator:self.comparator] + copyWith:nil + withValue:nil + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil]]; +} + +- (FSTTreeSortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey { + // Remove is somewhat expensive even if the key doesn't exist (the tree does rebalancing and + // stuff). So avoid it. + if (![self containsKey:aKey]) { + return self; + } else { + return [[FSTTreeSortedDictionary alloc] + initWithComparator:self.comparator + withRoot:[[self.root remove:aKey withComparator:self.comparator] + copyWith:nil + withValue:nil + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil]]; + } +} + +- (nullable id)objectForKey:(id)key { + NSComparisonResult cmp; + id node = self.root; + while (![node isEmpty]) { + cmp = self.comparator(key, node.key); + if (cmp == NSOrderedSame) { + return node.value; + } else if (cmp == NSOrderedAscending) { + node = node.left; + } else { + node = node.right; + } + } + return nil; +} + +- (nullable id)predecessorKey:(id)key { + NSComparisonResult cmp; + id node = self.root; + id rightParent = nil; + while (![node isEmpty]) { + cmp = self.comparator(key, node.key); + if (cmp == NSOrderedSame) { + if (![node.left isEmpty]) { + node = node.left; + while (![node.right isEmpty]) { + node = node.right; + } + return node.key; + } else if (rightParent != nil) { + return rightParent.key; + } else { + return nil; + } + } else if (cmp == NSOrderedAscending) { + node = node.left; + } else if (cmp == NSOrderedDescending) { + rightParent = node; + node = node.right; + } + } + @throw [NSException exceptionWithName:@"NonexistentKey" + reason:@"getPredecessorKey called with nonexistent key." + userInfo:@{@"key" : [key description]}]; +} + +- (NSUInteger)indexOfKey:(id)key { + NSUInteger prunedNodes = 0; + id node = self.root; + while (![node isEmpty]) { + NSComparisonResult cmp = self.comparator(key, node.key); + if (cmp == NSOrderedSame) { + return prunedNodes + node.left.count; + } else if (cmp == NSOrderedAscending) { + node = node.left; + } else if (cmp == NSOrderedDescending) { + prunedNodes += node.left.count + 1; + node = node.right; + } + } + return NSNotFound; +} + +- (BOOL)isEmpty { + return [self.root isEmpty]; +} + +- (NSUInteger)count { + return [self.root count]; +} + +- (id)minKey { + return [self.root minKey]; +} + +- (id)maxKey { + return [self.root maxKey]; +} + +- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block { + [self enumerateKeysAndObjectsReverse:NO usingBlock:block]; +} + +- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block { + if (reverse) { + __block BOOL stop = NO; + [self.root reverseTraversal:^BOOL(id key, id value) { + block(key, value, &stop); + return stop; + }]; + } else { + __block BOOL stop = NO; + [self.root inorderTraversal:^BOOL(id key, id value) { + block(key, value, &stop); + return stop; + }]; + } +} + +- (BOOL)containsKey:(id)key { + return ([self objectForKey:key] != nil); +} + +- (NSEnumerator *)keyEnumerator { + return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self + startKey:nil + endKey:nil + isReverse:NO]; +} + +- (NSEnumerator *)keyEnumeratorFrom:(id)startKey { + return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self + startKey:startKey + endKey:nil + isReverse:NO]; +} + +- (NSEnumerator *)keyEnumeratorFrom:(id)startKey to:(nullable id)endKey { + return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self + startKey:startKey + endKey:endKey + isReverse:NO]; +} + +- (NSEnumerator *)reverseKeyEnumerator { + return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self + startKey:nil + endKey:nil + isReverse:YES]; +} + +- (NSEnumerator *)reverseKeyEnumeratorFrom:(id)startKey { + return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self + startKey:startKey + endKey:nil + isReverse:YES]; +} + +#pragma mark - +#pragma mark Tree Builder + +// Code to efficiently build a red black tree. + +typedef struct { + unsigned int bits; + unsigned short count; + unsigned short current; +} Base12List; + +unsigned int LogBase2(unsigned int num) { + return (unsigned int)(log(num) / log(2)); +} + +/** + * Works like an iterator, so it moves to the next bit. Do not call more than list->count times. + * @return whether or not the next bit is a 1 in base {1,2}. + */ +BOOL Base12ListNext(Base12List *list) { + BOOL result = !(list->bits & (0x1 << list->current)); + list->current--; + return result; +} + +static inline unsigned BitMask(int x) { + return (x >= sizeof(unsigned) * CHAR_BIT) ? (unsigned)-1 : (1U << x) - 1; +} + +/** + * We represent the base{1,2} number as the combination of a binary number and a number of bits that + * we care about. We iterate backwards, from most significant bit to least, to build up the llrb + * nodes. 0 base 2 => 1 base {1,2}, 1 base 2 => 2 base {1,2} + */ +Base12List *NewBase12List(unsigned int length) { + size_t sz = sizeof(Base12List); + Base12List *list = calloc(1, sz); + // Calculate the number of bits that we care about + list->count = (unsigned short)LogBase2(length + 1); + unsigned int mask = BitMask(list->count); + list->bits = (length + 1) & mask; + list->current = list->count - 1; + return list; +} + +void FreeBase12List(Base12List *list) { + free(list); +} + ++ (id)buildBalancedTree:(NSArray *)keys + dictionary:(NSDictionary *)dictionary + subArrayStartIndex:(NSUInteger)startIndex + length:(NSUInteger)length { + length = MIN(keys.count - startIndex, length); // Bound length by the actual length of the array + if (length == 0) { + return nil; + } else if (length == 1) { + id key = keys[startIndex]; + return [[FSTLLRBValueNode alloc] initWithKey:key + withValue:dictionary[key] + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil]; + } else { + NSUInteger middle = length / 2; + id left = [FSTTreeSortedDictionary buildBalancedTree:keys + dictionary:dictionary + subArrayStartIndex:startIndex + length:middle]; + id right = [FSTTreeSortedDictionary buildBalancedTree:keys + dictionary:dictionary + subArrayStartIndex:(startIndex + middle + 1) + length:middle]; + id key = keys[startIndex + middle]; + return [[FSTLLRBValueNode alloc] initWithKey:key + withValue:dictionary[key] + withColor:FSTLLRBColorBlack + withLeft:left + withRight:right]; + } +} + ++ (nullable id)rootFrom12List:(Base12List *)base12List + keyList:(NSArray *)keyList + dictionary:(NSDictionary *)dictionary { + __block FSTLLRBValueNode *root = nil; + __block FSTLLRBValueNode *node = nil; + __block NSUInteger index = keyList.count; + + void (^buildPennant)(FSTLLRBColor, NSUInteger) = ^(FSTLLRBColor color, NSUInteger chunkSize) { + NSUInteger startIndex = index - chunkSize + 1; + index -= chunkSize; + id key = keyList[index]; + FSTLLRBValueNode *childTree = [self buildBalancedTree:keyList + dictionary:dictionary + subArrayStartIndex:startIndex + length:(chunkSize - 1)]; + FSTLLRBValueNode *pennant = [[FSTLLRBValueNode alloc] initWithKey:key + withValue:dictionary[key] + withColor:color + withLeft:nil + withRight:childTree]; + if (node) { + // This is the only place this property is set. + node.left = pennant; + node = pennant; + } else { + root = pennant; + node = pennant; + } + }; + + for (int i = 0; i < base12List->count; ++i) { + BOOL isOne = Base12ListNext(base12List); + NSUInteger chunkSize = (NSUInteger)pow(2.0, base12List->count - (i + 1)); + if (isOne) { + buildPennant(FSTLLRBColorBlack, chunkSize); + } else { + buildPennant(FSTLLRBColorBlack, chunkSize); + buildPennant(FSTLLRBColorRed, chunkSize); + } + } + return root; +} + +/** + * Uses the algorithm linked here: + * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1458 + */ ++ (FSTImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary + withComparator:(NSComparator)comparator { + // Steps: + // 0. Sort the array + // 1. Calculate the 1-2 number + // 2. Build From 1-2 number + // 0. for each digit in 1-2 number + // 0. calculate chunk size + // 1. build 1 or 2 pennants of that size + // 2. attach pennants and update node pointer + // 1. return root + NSMutableArray *sortedKeyList = [NSMutableArray arrayWithCapacity:dictionary.count]; + [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) { + [sortedKeyList addObject:key]; + }]; + [sortedKeyList sortUsingComparator:comparator]; + + [sortedKeyList enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { + if (idx > 0) { + if (comparator(sortedKeyList[idx - 1], obj) != NSOrderedAscending) { + [NSException raise:NSInvalidArgumentException + format: + @"Can't create FSTImmutableSortedDictionary " + @"with keys with same ordering!"]; + } + } + }]; + + Base12List *list = NewBase12List((unsigned int)sortedKeyList.count); + id root = [self rootFrom12List:list keyList:sortedKeyList dictionary:dictionary]; + FreeBase12List(list); + + if (root != nil) { + return [[FSTTreeSortedDictionary alloc] initWithComparator:comparator withRoot:root]; + } else { + return [[FSTTreeSortedDictionary alloc] initWithComparator:comparator]; + } +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.h b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.h new file mode 100644 index 0000000..ab82f00 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.h @@ -0,0 +1,21 @@ +#import + +#import "FSTTreeSortedDictionary.h" + +NS_ASSUME_NONNULL_BEGIN + +@interface FSTTreeSortedDictionaryEnumerator : NSEnumerator + +- (id)init __attribute__(( + unavailable("Use initWithImmutableSortedDictionary:startKey:isReverse: instead."))); + +- (instancetype)initWithImmutableSortedDictionary: + (FSTTreeSortedDictionary *)aDict + startKey:(KeyType _Nullable)startKey + endKey:(KeyType _Nullable)endKey + isReverse:(BOOL)reverse NS_DESIGNATED_INITIALIZER; +- (nullable ValueType)nextObject; + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.m b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.m new file mode 100644 index 0000000..bfdfba5 --- /dev/null +++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.m @@ -0,0 +1,114 @@ +#import "FSTTreeSortedDictionaryEnumerator.h" + +NS_ASSUME_NONNULL_BEGIN + +// clang-format off +// For some reason, clang-format messes this line up... +@interface FSTTreeSortedDictionaryEnumerator () +/** The dictionary being enumerated. */ +@property(nonatomic, strong) FSTTreeSortedDictionary *immutableSortedDictionary; +/** The stack of tree nodes above the current node that will need to be revisited later. */ +@property(nonatomic, strong) NSMutableArray> *stack; +/** The direction of the traversal. YES=Descending. NO=Ascending. */ +@property(nonatomic, assign) BOOL isReverse; +/** If set, the enumerator should stop at this key and not return it. */ +@property(nonatomic, strong, nullable) id endKey; +@end +// clang-format on + +@implementation FSTTreeSortedDictionaryEnumerator + +- (instancetype)initWithImmutableSortedDictionary:(FSTTreeSortedDictionary *)aDict + startKey:(id _Nullable)startKey + endKey:(id _Nullable)endKey + isReverse:(BOOL)reverse { + self = [super init]; + if (self) { + _immutableSortedDictionary = aDict; + _stack = [[NSMutableArray alloc] init]; + _isReverse = reverse; + _endKey = endKey; + + NSComparator comparator = aDict.comparator; + id node = aDict.root; + + NSComparisonResult comparedToStart; + NSComparisonResult comparedToEnd; + while (![node isEmpty]) { + comparedToStart = NSOrderedDescending; + if (startKey) { + comparedToStart = comparator(node.key, startKey); + if (reverse) { + comparedToStart *= -1; + } + } + comparedToEnd = NSOrderedAscending; + if (endKey) { + comparedToEnd = comparator(node.key, endKey); + if (reverse) { + comparedToEnd *= -1; + } + } + + if (comparedToStart == NSOrderedAscending) { + // This node is less than our start key. Ignore it. + if (reverse) { + node = node.left; + } else { + node = node.right; + } + } else if (comparedToStart == NSOrderedSame) { + // This node is exactly equal to our start key. If it's less than the end key, push it on + // the stack, but stop iterating. + if (comparedToEnd == NSOrderedAscending) { + [_stack addObject:node]; + } + break; + } else { + // This node is greater than our start key. If it's less than our end key, add it to the + // stack and move on to the next one. + if (comparedToEnd == NSOrderedAscending) { + [_stack addObject:node]; + } + if (reverse) { + node = node.right; + } else { + node = node.left; + } + } + } + } + return self; +} + +- (nullable id)nextObject { + if ([self.stack count] == 0) { + return nil; + } + + id node = [self.stack lastObject]; + [self.stack removeLastObject]; + id result = node.key; + NSComparator comparator = self.immutableSortedDictionary.comparator; + + node = self.isReverse ? node.left : node.right; + while (![node isEmpty]) { + NSComparisonResult comparedToEnd = NSOrderedAscending; + if (self.endKey) { + comparedToEnd = comparator(node.key, self.endKey); + if (self.isReverse) { + comparedToEnd *= -1; + } + } + if (comparedToEnd == NSOrderedAscending) { + [self.stack addObject:node]; + } + node = self.isReverse ? node.right : node.left; + } + + return result; +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/LICENSE b/Firestore/third_party/Immutable/LICENSE new file mode 100644 index 0000000..b437003 --- /dev/null +++ b/Firestore/third_party/Immutable/LICENSE @@ -0,0 +1,21 @@ +Copyright (c) 2012 Mads Hartmann Jensen + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/Firestore/third_party/Immutable/Tests/FSTArraySortedDictionaryTests.m b/Firestore/third_party/Immutable/Tests/FSTArraySortedDictionaryTests.m new file mode 100644 index 0000000..68f2fc3 --- /dev/null +++ b/Firestore/third_party/Immutable/Tests/FSTArraySortedDictionaryTests.m @@ -0,0 +1,467 @@ +#import "Immutable/FSTArraySortedDictionary.h" + +#import + +#import "Util/FSTAssert.h" + +@interface FSTArraySortedDictionary (Test) +// Override methods to return subtype. +- (FSTArraySortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey; +- (FSTArraySortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey; +@end + +@interface FSTArraySortedDictionaryTests : XCTestCase +@end + +@implementation FSTArraySortedDictionaryTests + +- (NSComparator)defaultComparator { + return ^(id obj1, id obj2) { + FSTAssert([obj1 respondsToSelector:@selector(compare:)] && + [obj2 respondsToSelector:@selector(compare:)], + @"Objects must support compare: %@ %@", obj1, obj2); + return [obj1 compare:obj2]; + }; +} + +- (void)testSearchForSpecificKey { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + + XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object"); + XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object"); + XCTAssertEqualObjects(map[@1], @1, @"Found first object"); + XCTAssertEqualObjects(map[@2], @2, @"Found second object"); + XCTAssertNil([map objectForKey:@3], @"Properly not found object"); +} + +- (void)testRemoveKeyValuePair { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + + FSTImmutableSortedDictionary *newMap = [map dictionaryByRemovingObjectForKey:@1]; + XCTAssertEqualObjects([newMap objectForKey:@2], @2, @"Found second object"); + XCTAssertNil([newMap objectForKey:@1], @"Properly not found object"); + + // Make sure the original one is not mutated + XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object"); + XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object"); +} + +- (void)testMoreRemovals { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + map = [map dictionaryBySettingObject:@1 forKey:@20]; + map = [map dictionaryBySettingObject:@18 forKey:@18]; + map = [map dictionaryBySettingObject:@3 forKey:@2]; + map = [map dictionaryBySettingObject:@4 forKey:@71]; + map = [map dictionaryBySettingObject:@7 forKey:@42]; + map = [map dictionaryBySettingObject:@9 forKey:@88]; + + XCTAssertNotNil([map objectForKey:@7], @"Found object"); + XCTAssertNotNil([map objectForKey:@3], @"Found object"); + XCTAssertNotNil([map objectForKey:@1], @"Found object"); + + FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@7]; + FSTImmutableSortedDictionary *m2 = [map dictionaryByRemovingObjectForKey:@3]; + FSTImmutableSortedDictionary *m3 = [map dictionaryByRemovingObjectForKey:@1]; + + XCTAssertNil([m1 objectForKey:@7], @"Removed object"); + XCTAssertNotNil([m1 objectForKey:@3], @"Found object"); + XCTAssertNotNil([m1 objectForKey:@1], @"Found object"); + + XCTAssertNil([m2 objectForKey:@3], @"Removed object"); + XCTAssertNotNil([m2 objectForKey:@7], @"Found object"); + XCTAssertNotNil([m2 objectForKey:@1], @"Found object"); + + XCTAssertNil([m3 objectForKey:@1], @"Removed object"); + XCTAssertNotNil([m3 objectForKey:@7], @"Found object"); + XCTAssertNotNil([m3 objectForKey:@3], @"Found object"); +} + +- (void)testRemovalBug { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + + XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found object"); + XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found object"); + XCTAssertEqualObjects([map objectForKey:@3], @3, @"Found object"); + + FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@2]; + XCTAssertEqualObjects([m1 objectForKey:@1], @1, @"Found object"); + XCTAssertEqualObjects([m1 objectForKey:@3], @3, @"Found object"); + XCTAssertNil([m1 objectForKey:@2], @"Removed object"); +} + +- (void)testIncreasing { + int total = 100; + + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + for (int i = 0; i < total; i++) { + NSNumber *item = @(i); + map = [map dictionaryBySettingObject:item forKey:item]; + } + + XCTAssertTrue(map.count == 100, @"Check if all 100 objects are in the map"); + + for (int i = 0; i < total; i++) { + NSNumber *item = @(i); + map = [map dictionaryByRemovingObjectForKey:item]; + } + + XCTAssertTrue(map.count == 0, @"Check if all 100 objects were removed"); +} + +- (void)testOverride { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@10 forKey:@10]; + map = [map dictionaryBySettingObject:@8 forKey:@10]; + + XCTAssertEqualObjects([map objectForKey:@10], @8, @"Found first object"); +} + +- (void)testEmpty { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@10 forKey:@10]; + map = [map dictionaryByRemovingObjectForKey:@10]; + + XCTAssertTrue([map isEmpty], @"Properly empty"); +} + +- (void)testEmptyGet { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + XCTAssertNil([map objectForKey:@"something"], @"Properly nil"); +} + +- (void)testEmptyCount { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + XCTAssertTrue([map count] == 0, @"Properly zero count"); +} + +- (void)testEmptyRemoval { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryByRemovingObjectForKey:@"something"]; + XCTAssertTrue(map.count == 0, @"Properly zero count"); +} + +- (void)testReverseTraversal { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@5 forKey:@5]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + + __block int next = 5; + [map enumerateKeysAndObjectsReverse:YES + usingBlock:^(id key, id value, BOOL *stop) { + XCTAssertEqualObjects(key, @(next), @"Properly equal"); + next = next - 1; + }]; +} + +- (void)testInsertionAndRemovalOfAHundredItems { + NSUInteger n = 100; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n]; + + for (NSUInteger i = 0; i < n; i++) { + [toInsert addObject:@(i)]; + [toRemove addObject:@(i)]; + } + + [self shuffleArray:toInsert]; + [self shuffleArray:toRemove]; + + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + + // check the order is correct + __block int next = 0; + [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + XCTAssertEqualObjects(key, @(next), @"Correct key"); + XCTAssertEqualObjects(value, @(next), @"Correct value"); + next = next + 1; + }]; + XCTAssertEqual(next, n, @"Check we traversed all of the items"); + + // remove them + + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryByRemovingObjectForKey:toRemove[i]]; + } + + XCTAssertEqual(map.count, 0, @"Check we removed all of the items"); +} + +- (void)shuffleArray:(NSMutableArray *)array { + NSUInteger count = array.count; + for (NSUInteger i = 0; i < count; i++) { + NSUInteger nElements = count - i; + NSUInteger n = (arc4random() % nElements) + i; + [array exchangeObjectAtIndex:i withObjectAtIndex:n]; + } +} + +- (void)testBalanceProblem { + NSArray *toInsert = @[ @1, @7, @8, @5, @2, @6, @4, @0, @3 ]; + + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for (NSUInteger i = 0; i < toInsert.count; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == toInsert.count, @"Check if all N objects are in the map"); + + // check the order is correct + __block int next = 0; + [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + XCTAssertEqualObjects(key, @(next), @"Correct key"); + XCTAssertEqualObjects(value, @(next), @"Correct value"); + next = next + 1; + }]; + XCTAssertEqual((int)next, (int)toInsert.count, @"Check we traversed all of the items"); +} + +- (void)testPredecessorKey { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + + XCTAssertNil([map predecessorKey:@1], @"First object doesn't have a predecessor"); + XCTAssertEqualObjects([map predecessorKey:@3], @1, @"@1"); + XCTAssertEqualObjects([map predecessorKey:@4], @3, @"@3"); + XCTAssertEqualObjects([map predecessorKey:@7], @4, @"@4"); + XCTAssertEqualObjects([map predecessorKey:@9], @7, @"@7"); + XCTAssertEqualObjects([map predecessorKey:@50], @9, @"@9"); + XCTAssertThrows([map predecessorKey:@777], @"Expect exception about nonexistent key"); +} + +// This is a macro instead of a method so that the failures show on the proper lines. +#define ASSERT_ENUMERATOR(enumerator, start, end, step) \ + do { \ + NSEnumerator *e = (enumerator); \ + id next = nil; \ + for (NSUInteger i = (start); i != (end); i += (step)) { \ + next = [e nextObject]; \ + XCTAssertNotNil(next, @"expected %lu. got nil.", (unsigned long)i); \ + XCTAssertEqualObjects(next, @(i), "expected %lu. got %@.", (unsigned long)i, next); \ + } \ + next = [e nextObject]; \ + XCTAssertNil(next, @"expected nil. got %@.", next); \ + } while (0) + +- (void)testEnumerator { + NSUInteger n = 100; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n]; + + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i)]; + [toRemove addObject:@(i)]; + } + + [self shuffleArray:toInsert]; + [self shuffleArray:toRemove]; + + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:self.defaultComparator]; + + // add them to the dictionary + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + + ASSERT_ENUMERATOR([map keyEnumerator], 0, 100, 1); +} + +- (void)testReverseEnumerator { + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i)]; + } + + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // Add them to the dictionary. + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class], + @"Make sure we still have a array backed dictionary"); + + ASSERT_ENUMERATOR([map reverseKeyEnumerator], n - 1, -1, -1); +} + +- (void)testEnumeratorFrom { + // Create a dictionary with the even numbers in [2, 42). + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i * 2 + 2)]; + } + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // Add them to the dictionary. + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class], + @"Make sure we still have a array backed dictionary"); + + // Test from before keys. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0], 2, n * 2 + 2, 2); + + // Test from after keys. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100], 0, 0, 2); + + // Test from key in map. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@10], 10, n * 2 + 2, 2); + + // Test from in between keys. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@11], 12, n * 2 + 2, 2); +} + +- (void)testEnumeratorFromTo { + // Create a dictionary with the even numbers in [2, 42). + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i * 2 + 2)]; + } + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // Add them to the dictionary. + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class], + @"Make sure we still have an array backed dictionary"); + + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@1], 2, 2, 2); // before to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@100], 2, n * 2 + 2, 2); // before to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@6], 2, 6, 2); // before to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@7], 2, 8, 2); // before to in between keys + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@0], 2, 2, 2); // after to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@110], 2, 2, 2); // after to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@6], 2, 2, 2); // after to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@7], 2, 2, 2); // after to in between + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@0], 6, 6, 2); // key in map to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@100], 6, n * 2 + 2, 2); // key in map to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@10], 6, 10, 2); // key in map to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@11], 6, 12, 2); // key in map to in between + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@0], 8, 8, 2); // in between to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@100], 8, n * 2 + 2, 2); // in between to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@10], 8, 10, 2); // in between to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@13], 8, 14, 2); // in between to in between +} + +- (void)testReverseEnumeratorFrom { + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i * 2 + 2)]; + } + + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class], + @"Make sure we still have a array backed dictionary"); + + // Test from before keys. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@0], 0, 0, -2); + + // Test from after keys. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@100], n * 2, 0, -2); + + // Test from key in map. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@10], 10, 0, -2); + + // Test from in between keys. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@11], 10, 0, -2); +} + +#undef ASSERT_ENUMERATOR + +- (void)testIndexOf { + FSTArraySortedDictionary *map = + [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + + XCTAssertEqual([map indexOfKey:@0], NSNotFound); + XCTAssertEqual([map indexOfKey:@1], 0); + XCTAssertEqual([map indexOfKey:@2], NSNotFound); + XCTAssertEqual([map indexOfKey:@3], 1); + XCTAssertEqual([map indexOfKey:@4], 2); + XCTAssertEqual([map indexOfKey:@5], NSNotFound); + XCTAssertEqual([map indexOfKey:@6], NSNotFound); + XCTAssertEqual([map indexOfKey:@7], 3); + XCTAssertEqual([map indexOfKey:@8], NSNotFound); + XCTAssertEqual([map indexOfKey:@9], 4); + XCTAssertEqual([map indexOfKey:@50], 5); +} + +@end diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.h b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.h new file mode 100644 index 0000000..7496173 --- /dev/null +++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.h @@ -0,0 +1,17 @@ +#import + +#import "Immutable/FSTImmutableSortedDictionary.h" + +NS_ASSUME_NONNULL_BEGIN + +// clang-format doesn't yet deal with generic parameters and categories :-( +// clang-format off +@interface FSTImmutableSortedDictionary (Testing) + +/** Converts the values of the dictionary to an array preserving order. */ +- (NSArray *)values; + +@end +// clang-format on + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.m b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.m new file mode 100644 index 0000000..d402916 --- /dev/null +++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.m @@ -0,0 +1,17 @@ +#import "FSTImmutableSortedDictionary+Testing.h" + +NS_ASSUME_NONNULL_BEGIN + +@implementation FSTImmutableSortedDictionary (Testing) + +- (NSArray *)values { + NSMutableArray *result = [NSMutableArray array]; + [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + [result addObject:value]; + }]; + return result; +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.h b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.h new file mode 100644 index 0000000..a0e25d7 --- /dev/null +++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.h @@ -0,0 +1,20 @@ +#import "Immutable/FSTImmutableSortedSet.h" + +NS_ASSUME_NONNULL_BEGIN + +// clang-format doesn't yet deal with generic parameters and categories :-( +// clang-format off +@interface FSTImmutableSortedSet (Testing) + +/** + * An array containing the set’s members, or an empty array if the set has no members. + * + * Implemented here for compatibility with NSSet in testing though we'd never want to do this + * in production code. + */ +- (NSArray *)allObjects; + +@end +// clang-format on + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.m b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.m new file mode 100644 index 0000000..d4d81e0 --- /dev/null +++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.m @@ -0,0 +1,17 @@ +#import "FSTImmutableSortedSet+Testing.h" + +NS_ASSUME_NONNULL_BEGIN + +@implementation FSTImmutableSortedSet (Testing) + +- (NSArray *)allObjects { + NSMutableArray *result = [NSMutableArray array]; + [self enumerateObjectsUsingBlock:^(id object, BOOL *stop) { + [result addObject:object]; + }]; + return result; +} + +@end + +NS_ASSUME_NONNULL_END diff --git a/Firestore/third_party/Immutable/Tests/FSTLLRBValueNode+Test.h b/Firestore/third_party/Immutable/Tests/FSTLLRBValueNode+Test.h new file mode 100644 index 0000000..3b05647 --- /dev/null +++ b/Firestore/third_party/Immutable/Tests/FSTLLRBValueNode+Test.h @@ -0,0 +1,10 @@ +#import "Immutable/FSTLLRBValueNode.h" + +#import + +/** Extra methods exposed only for testing. */ +@interface FSTLLRBValueNode (Test) +- (id)rotateLeft; +- (id)rotateRight; +- (BOOL)checkMaxDepth; +@end diff --git a/Firestore/third_party/Immutable/Tests/FSTTreeSortedDictionaryTests.m b/Firestore/third_party/Immutable/Tests/FSTTreeSortedDictionaryTests.m new file mode 100644 index 0000000..352ac4e --- /dev/null +++ b/Firestore/third_party/Immutable/Tests/FSTTreeSortedDictionaryTests.m @@ -0,0 +1,655 @@ +#import + +#import "Immutable/FSTLLRBEmptyNode.h" +#import "Immutable/FSTLLRBNode.h" +#import "Immutable/FSTLLRBValueNode.h" +#import "Immutable/FSTTreeSortedDictionary.h" +#import "Util/FSTAssert.h" + +#import "FSTLLRBValueNode+Test.h" + +@interface FSTTreeSortedDictionary (Test) +// Override methods to return subtype. +- (FSTTreeSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey; +- (FSTTreeSortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey; +@end + +@interface FSTTreeSortedDictionaryTests : XCTestCase +@end + +@implementation FSTTreeSortedDictionaryTests + +- (NSComparator)defaultComparator { + return ^(id obj1, id obj2) { + FSTAssert([obj1 respondsToSelector:@selector(compare:)] && + [obj2 respondsToSelector:@selector(compare:)], + @"Objects must support compare: %@ %@", obj1, obj2); + return [obj1 compare:obj2]; + }; +} + +- (void)testCreateNode { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@"value" forKey:@"key"]; + XCTAssertTrue([map.root.left isEmpty], @"Left child is properly empty"); + XCTAssertTrue([map.root.right isEmpty], @"Right child is properly empty"); +} + +- (void)testSearchForSpecificKey { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + + XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object"); + XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object"); + XCTAssertEqualObjects(map[@1], @1, @"Found first object"); + XCTAssertEqualObjects(map[@2], @2, @"Found second object"); + XCTAssertNil([map objectForKey:@3], @"Properly not found object"); +} + +- (void)testInsertNewKeyValuePair { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + + XCTAssertEqualObjects(map.root.key, @2, @"Check the root key"); + XCTAssertEqualObjects(map.root.left.key, @1, @"Check the root.left key"); +} + +- (void)testRemoveKeyValuePair { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + + FSTImmutableSortedDictionary *newMap = [map dictionaryByRemovingObjectForKey:@1]; + XCTAssertEqualObjects([newMap objectForKey:@2], @2, @"Found second object"); + XCTAssertNil([newMap objectForKey:@1], @"Properly not found object"); + + // Make sure the original one is not mutated + XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object"); + XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object"); +} + +- (void)testMoreRemovals { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + map = [map dictionaryBySettingObject:@1 forKey:@20]; + map = [map dictionaryBySettingObject:@18 forKey:@18]; + map = [map dictionaryBySettingObject:@3 forKey:@2]; + map = [map dictionaryBySettingObject:@4 forKey:@71]; + map = [map dictionaryBySettingObject:@7 forKey:@42]; + map = [map dictionaryBySettingObject:@9 forKey:@88]; + + XCTAssertNotNil([map objectForKey:@7], @"Found object"); + XCTAssertNotNil([map objectForKey:@3], @"Found object"); + XCTAssertNotNil([map objectForKey:@1], @"Found object"); + + FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@7]; + FSTImmutableSortedDictionary *m2 = [map dictionaryByRemovingObjectForKey:@3]; + FSTImmutableSortedDictionary *m3 = [map dictionaryByRemovingObjectForKey:@1]; + + XCTAssertNil([m1 objectForKey:@7], @"Removed object"); + XCTAssertNotNil([m1 objectForKey:@3], @"Found object"); + XCTAssertNotNil([m1 objectForKey:@1], @"Found object"); + + XCTAssertNil([m2 objectForKey:@3], @"Removed object"); + XCTAssertNotNil([m2 objectForKey:@7], @"Found object"); + XCTAssertNotNil([m2 objectForKey:@1], @"Found object"); + + XCTAssertNil([m3 objectForKey:@1], @"Removed object"); + XCTAssertNotNil([m3 objectForKey:@7], @"Found object"); + XCTAssertNotNil([m3 objectForKey:@3], @"Found object"); +} + +- (void)testRemovalBug { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + + XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found object"); + XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found object"); + XCTAssertEqualObjects([map objectForKey:@3], @3, @"Found object"); + + FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@2]; + XCTAssertEqualObjects([m1 objectForKey:@1], @1, @"Found object"); + XCTAssertEqualObjects([m1 objectForKey:@3], @3, @"Found object"); + XCTAssertNil([m1 objectForKey:@2], @"Removed object"); +} + +- (void)testIncreasing { + int total = 100; + + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + for (int i = 0; i < total; i++) { + NSNumber *item = @(i); + map = [map dictionaryBySettingObject:item forKey:item]; + } + + XCTAssertTrue(map.count == 100, @"Check if all 100 objects are in the map"); + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); + + for (int i = 0; i < total; i++) { + NSNumber *item = @(i); + map = [map dictionaryByRemovingObjectForKey:item]; + } + + XCTAssertTrue(map.count == 0, @"Check if all 100 objects were removed"); + // We can't check the depth here because the map no longer contains values, so we check that it + // doesn't respond to this check + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBEmptyNode.class], @"Root is an empty node"); + XCTAssertFalse([map respondsToSelector:@selector(checkMaxDepth)], + @"The empty node doesn't respond to this selector."); +} + +- (void)testStructureShouldBeValidAfterInsertionA { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + + XCTAssertEqualObjects(map.root.key, @2, @"Check root key"); + XCTAssertEqualObjects(map.root.left.key, @1, @"Check the left key is correct"); + XCTAssertEqualObjects(map.root.right.key, @3, @"Check the right key is correct"); +} + +- (void)testStructureShouldBeValidAfterInsertionB { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + map = [map dictionaryBySettingObject:@1 forKey:@20]; + map = [map dictionaryBySettingObject:@18 forKey:@18]; + map = [map dictionaryBySettingObject:@3 forKey:@2]; + map = [map dictionaryBySettingObject:@4 forKey:@71]; + map = [map dictionaryBySettingObject:@7 forKey:@42]; + map = [map dictionaryBySettingObject:@9 forKey:@88]; + + XCTAssertTrue(map.count == 12, @"Check if all 12 objects are in the map"); + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); +} + +- (void)testRotateLeftLeavesTreeInAValidState { + FSTLLRBValueNode *node = [[FSTLLRBValueNode alloc] + initWithKey:@4 + withValue:@4 + withColor:FSTLLRBColorBlack + withLeft:[[FSTLLRBValueNode alloc] initWithKey:@2 + withValue:@2 + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil] + withRight:[[FSTLLRBValueNode alloc] + initWithKey:@7 + withValue:@7 + withColor:FSTLLRBColorRed + withLeft:[[FSTLLRBValueNode alloc] initWithKey:@5 + withValue:@5 + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil] + withRight:[[FSTLLRBValueNode alloc] initWithKey:@8 + withValue:@8 + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil]]]; + + FSTLLRBValueNode *node2 = [node rotateLeft]; + + XCTAssertTrue(node2.count == 5, @"Make sure the count is correct"); + XCTAssertTrue([node2 checkMaxDepth], @"Check proper structure"); +} + +- (void)testRotateRightLeavesTreeInAValidState { + FSTLLRBValueNode *node = [[FSTLLRBValueNode alloc] + initWithKey:@7 + withValue:@7 + withColor:FSTLLRBColorBlack + withLeft:[[FSTLLRBValueNode alloc] + initWithKey:@4 + withValue:@4 + withColor:FSTLLRBColorRed + withLeft:[[FSTLLRBValueNode alloc] initWithKey:@2 + withValue:@2 + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil] + withRight:[[FSTLLRBValueNode alloc] initWithKey:@5 + withValue:@5 + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil]] + withRight:[[FSTLLRBValueNode alloc] initWithKey:@8 + withValue:@8 + withColor:FSTLLRBColorBlack + withLeft:nil + withRight:nil]]; + + FSTLLRBValueNode *node2 = [node rotateRight]; + XCTAssertTrue(node2.count == 5, @"Make sure the count is correct"); + XCTAssertEqualObjects(node2.key, @4, @"Check roots key"); + XCTAssertEqualObjects(node2.left.key, @2, @"Check first left child key"); + XCTAssertEqualObjects(node2.right.key, @7, @"Check first right child key"); + XCTAssertEqualObjects(node2.right.left.key, @5, @"Check second right left key"); + XCTAssertEqualObjects(node2.right.right.key, @8, @"Check second right left key"); +} + +- (void)testStructureShouldBeValidAfterInsertionC { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + + XCTAssertTrue(map.count == 6, @"Check if all 6 objects are in the map"); + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); + + FSTTreeSortedDictionary *m2 = map; + m2 = [m2 dictionaryBySettingObject:@20 forKey:@20]; + m2 = [m2 dictionaryBySettingObject:@18 forKey:@18]; + m2 = [m2 dictionaryBySettingObject:@2 forKey:@2]; + + XCTAssertTrue(m2.count == 9, @"Check if all 9 objects are in the map"); + XCTAssertTrue([m2.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)m2.root checkMaxDepth], + @"Checking valid depth and tree structure"); + + FSTTreeSortedDictionary *m3 = m2; + m3 = [m3 dictionaryBySettingObject:@71 forKey:@71]; + m3 = [m3 dictionaryBySettingObject:@42 forKey:@42]; + m3 = [m3 dictionaryBySettingObject:@88 forKey:@88]; + m3 = [m3 dictionaryBySettingObject:@20 forKey:@20]; // Add a dupe to see if the size is correct + + XCTAssertTrue(m3.count == 12, @"Check if all 12 (minus dupe @20) objects are in the map"); + XCTAssertTrue([m3.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)m3.root checkMaxDepth], + @"Checking valid depth and tree structure"); +} + +- (void)testOverride { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@10 forKey:@10]; + map = [map dictionaryBySettingObject:@8 forKey:@10]; + + XCTAssertEqualObjects([map objectForKey:@10], @8, @"Found first object"); +} +- (void)testEmpty { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@10 forKey:@10]; + map = [map dictionaryByRemovingObjectForKey:@10]; + + XCTAssertTrue([map isEmpty], @"Properly empty"); +} + +- (void)testEmptyGet { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + XCTAssertNil([map objectForKey:@"something"], @"Properly nil"); +} + +- (void)testEmptyCount { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + XCTAssertTrue([map count] == 0, @"Properly zero count"); +} + +- (void)testEmptyRemoval { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryByRemovingObjectForKey:@"something"]; + XCTAssertTrue(map.count == 0, @"Properly zero count"); +} + +- (void)testReverseTraversal { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@5 forKey:@5]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@2 forKey:@2]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + + __block int next = 5; + [map enumerateKeysAndObjectsReverse:YES + usingBlock:^(id key, id value, BOOL *stop) { + XCTAssertEqualObjects(key, @(next), @"Properly equal"); + next = next - 1; + }]; +} + +- (void)testInsertionAndRemovalOfAHundredItems { + NSUInteger n = 100; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n]; + + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i)]; + [toRemove addObject:@(i)]; + } + + [self shuffleArray:toInsert]; + [self shuffleArray:toRemove]; + + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + + // check the order is correct + __block int next = 0; + [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + XCTAssertEqualObjects(key, @(next), @"Correct key"); + XCTAssertEqualObjects(value, @(next), @"Correct value"); + next = next + 1; + }]; + XCTAssertEqual(next, n, @"Check we traversed all of the items"); + + // remove them + + for (NSUInteger i = 0; i < n; i++) { + if ([map.root isMemberOfClass:FSTLLRBValueNode.class]) { + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); + } + map = [map dictionaryByRemovingObjectForKey:toRemove[i]]; + } + + XCTAssertEqual(map.count, 0, @"Check we removed all of the items"); +} + +- (void)shuffleArray:(NSMutableArray *)array { + NSUInteger count = array.count; + for (NSUInteger i = 0; i < count; i++) { + NSUInteger nElements = count - i; + NSUInteger n = (arc4random() % nElements) + i; + [array exchangeObjectAtIndex:i withObjectAtIndex:n]; + } +} + +- (void)testBalanceProblem { + NSArray *toInsert = @[ @1, @7, @8, @5, @2, @6, @4, @0, @3 ]; + + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for (NSUInteger i = 0; i < toInsert.count; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); + } + XCTAssertTrue(map.count == toInsert.count, @"Check if all N objects are in the map"); + + // check the order is correct + __block int next = 0; + [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + XCTAssertEqualObjects(key, @(next), @"Correct key"); + XCTAssertEqualObjects(value, @(next), @"Correct value"); + next = next + 1; + }]; + XCTAssertEqual((int)next, (int)toInsert.count, @"Check we traversed all of the items"); + + // removing one triggers the balance problem + map = [map dictionaryByRemovingObjectForKey:@5]; + + if ([map.root isMemberOfClass:FSTLLRBValueNode.class]) { + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); + } +} + +- (void)testPredecessorKey { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + + XCTAssertNil([map predecessorKey:@1], @"First object doesn't have a predecessor"); + XCTAssertEqualObjects([map predecessorKey:@3], @1, @"@1"); + XCTAssertEqualObjects([map predecessorKey:@4], @3, @"@3"); + XCTAssertEqualObjects([map predecessorKey:@7], @4, @"@4"); + XCTAssertEqualObjects([map predecessorKey:@9], @7, @"@7"); + XCTAssertEqualObjects([map predecessorKey:@50], @9, @"@9"); + XCTAssertThrows([map predecessorKey:@777], @"Expect exception about nonexistent key"); +} + +// This is a macro instead of a method so that the failures show on the proper lines. +#define ASSERT_ENUMERATOR(enumerator, start, end, step) \ + do { \ + NSEnumerator *e = (enumerator); \ + id next = nil; \ + for (NSUInteger i = (start); i != (end); i += (step)) { \ + next = [e nextObject]; \ + XCTAssertNotNil(next, @"expected %lu. got nil.", (unsigned long)i); \ + XCTAssertEqualObjects(next, @(i), "expected %lu. got %@.", (unsigned long)i, next); \ + } \ + next = [e nextObject]; \ + XCTAssertNil(next, @"expected nil. got %@.", next); \ + } while (0) + +- (void)testEnumerator { + NSUInteger n = 100; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n]; + + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i)]; + [toRemove addObject:@(i)]; + } + + [self shuffleArray:toInsert]; + [self shuffleArray:toRemove]; + + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:self.defaultComparator]; + + // add them to the dictionary + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node"); + XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth], + @"Checking valid depth and tree structure"); + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + + ASSERT_ENUMERATOR([map keyEnumerator], 0, 100, 1); +} + +- (void)testReverseEnumerator { + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i)]; + } + + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // Add them to the dictionary. + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class], + @"Make sure we still have a tree backed dictionary"); + + ASSERT_ENUMERATOR([map reverseKeyEnumerator], n - 1, -1, -1); +} + +- (void)testEnumeratorFrom { + // Create a dictionary with the even numbers in [2, 42). + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i * 2 + 2)]; + } + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // Add them to the dictionary. + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class], + @"Make sure we still have a tree backed dictionary"); + + // Test from before keys. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0], 2, n * 2 + 2, 2); + + // Test from after keys. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100], 0, 0, 2); + + // Test from key in map. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@10], 10, n * 2 + 2, 2); + + // Test from in between keys. + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@11], 12, n * 2 + 2, 2); +} + +- (void)testEnumeratorFromTo { + // Create a dictionary with the even numbers in [2, 42). + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i * 2 + 2)]; + } + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // Add them to the dictionary. + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class], + @"Make sure we still have a tree backed dictionary"); + + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@1], 2, 2, 2); // before to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@100], 2, n * 2 + 2, 2); // before to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@6], 2, 6, 2); // before to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@7], 2, 8, 2); // before to in between keys + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@0], 2, 2, 2); // after to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@110], 2, 2, 2); // after to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@6], 2, 2, 2); // after to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@7], 2, 2, 2); // after to in between + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@0], 6, 6, 2); // key in map to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@100], 6, n * 2 + 2, 2); // key in map to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@10], 6, 10, 2); // key in map to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@11], 6, 12, 2); // key in map to in between + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@0], 8, 8, 2); // in between to before + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@100], 8, n * 2 + 2, 2); // in between to after + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@10], 8, 10, 2); // in between to key in map + ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@13], 8, 14, 2); // in between to in between +} + +- (void)testReverseEnumeratorFrom { + NSUInteger n = 20; + NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n]; + + for (int i = 0; i < n; i++) { + [toInsert addObject:@(i * 2 + 2)]; + } + + [self shuffleArray:toInsert]; + + FSTImmutableSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for (NSUInteger i = 0; i < n; i++) { + map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]]; + } + XCTAssertTrue(map.count == n, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class], + @"Make sure we still have a tree backed dictionary"); + + // Test from before keys. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@0], 0, 0, -2); + + // Test from after keys. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@100], n * 2, 0, -2); + + // Test from key in map. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@10], 10, 0, -2); + + // Test from in between keys. + ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@11], 10, 0, -2); +} + +#undef ASSERT_ENUMERATOR + +- (void)testIndexOf { + FSTTreeSortedDictionary *map = + [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + map = [map dictionaryBySettingObject:@1 forKey:@1]; + map = [map dictionaryBySettingObject:@50 forKey:@50]; + map = [map dictionaryBySettingObject:@3 forKey:@3]; + map = [map dictionaryBySettingObject:@4 forKey:@4]; + map = [map dictionaryBySettingObject:@7 forKey:@7]; + map = [map dictionaryBySettingObject:@9 forKey:@9]; + + XCTAssertEqual([map indexOfKey:@0], NSNotFound); + XCTAssertEqual([map indexOfKey:@1], 0); + XCTAssertEqual([map indexOfKey:@2], NSNotFound); + XCTAssertEqual([map indexOfKey:@3], 1); + XCTAssertEqual([map indexOfKey:@4], 2); + XCTAssertEqual([map indexOfKey:@5], NSNotFound); + XCTAssertEqual([map indexOfKey:@6], NSNotFound); + XCTAssertEqual([map indexOfKey:@7], 3); + XCTAssertEqual([map indexOfKey:@8], NSNotFound); + XCTAssertEqual([map indexOfKey:@9], 4); + XCTAssertEqual([map indexOfKey:@50], 5); +} + +@end -- cgit v1.2.3