diff options
Diffstat (limited to 'Example/Database/Tests/Unit/FTreeSortedDictionaryTests.m')
-rw-r--r-- | Example/Database/Tests/Unit/FTreeSortedDictionaryTests.m | 574 |
1 files changed, 574 insertions, 0 deletions
diff --git a/Example/Database/Tests/Unit/FTreeSortedDictionaryTests.m b/Example/Database/Tests/Unit/FTreeSortedDictionaryTests.m new file mode 100644 index 0000000..6aee84d --- /dev/null +++ b/Example/Database/Tests/Unit/FTreeSortedDictionaryTests.m @@ -0,0 +1,574 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#import <XCTest/XCTest.h> + +#import "FTreeSortedDictionary.h" +#import "FLLRBNode.h" +#import "FLLRBEmptyNode.h" +#import "FLLRBValueNode.h" + +@interface FLLRBValueNode (Tests) +- (id<FLLRBNode>) rotateLeft; +- (id<FLLRBNode>) rotateRight; +@end + +@interface FTreeSortedDictionaryTests : XCTestCase + +@end + +@implementation FTreeSortedDictionaryTests + +- (NSComparator) defaultComparator { + return ^(id obj1, id obj2) { + if([obj1 respondsToSelector:@selector(compare:)] && [obj2 respondsToSelector:@selector(compare:)]) { + return [obj1 compare:obj2]; + } + else { + if(obj1 < obj2) { + return (NSComparisonResult)NSOrderedAscending; + } + else if (obj1 > obj2) { + return (NSComparisonResult)NSOrderedDescending; + } + else { + return (NSComparisonResult)NSOrderedSame; + } + } + }; +} + +- (void)testCreateNode +{ + FTreeSortedDictionary* map = [[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@"key" withValue:@"value"]; + XCTAssertTrue([map.root.left isEmpty], @"Left child is properly empty"); + XCTAssertTrue([map.root.right isEmpty], @"Right child is properly empty"); +} + +- (void)testGetNilReturnsNil { + FImmutableSortedDictionary *map1 = [[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@"key" withValue:@"value"]; + XCTAssertNil([map1 get:nil]); + + FImmutableSortedDictionary *map2 = [[[FTreeSortedDictionary alloc] initWithComparator:^NSComparisonResult(id obj1, id obj2) { + return [obj1 compare:obj2]; + }] + insertKey:@"key" withValue:@"value"]; + XCTAssertNil([map2 get:nil]); +} + +- (void)testSearchForSpecificKey { + FTreeSortedDictionary* map = [[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@2 withValue:@2]; + + XCTAssertEqualObjects([map get:@1], @1, @"Found first object"); + XCTAssertEqualObjects([map get:@2], @2, @"Found second object"); + XCTAssertNil([map get:@3], @"Properly not found object"); +} + +- (void)testInsertNewKeyValuePair { + FTreeSortedDictionary* map = [[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@2 withValue:@2]; + + XCTAssertEqualObjects(map.root.key, @2, @"Check the root key"); + XCTAssertEqualObjects(map.root.left.key, @1, @"Check the root.left key"); +} + +- (void)testRemoveKeyValuePair { + FTreeSortedDictionary* map = [[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@2 withValue:@2]; + + FImmutableSortedDictionary* newMap = [map removeKey:@1]; + XCTAssertEqualObjects([newMap get:@2], @2, @"Found second object"); + XCTAssertNil([newMap get:@1], @"Properly not found object"); + + // Make sure the original one is not mutated + XCTAssertEqualObjects([map get:@1], @1, @"Found first object"); + XCTAssertEqualObjects([map get:@2], @2, @"Found second object"); +} + +- (void)testMoreRemovals { + FTreeSortedDictionary* map = [[[[[[[[[[[[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@50 withValue:@50] + insertKey:@3 withValue:@3] + insertKey:@4 withValue:@4] + insertKey:@7 withValue:@7] + insertKey:@9 withValue:@9] + insertKey:@20 withValue:@20] + insertKey:@18 withValue:@18] + insertKey:@2 withValue:@2] + insertKey:@71 withValue:@71] + insertKey:@42 withValue:@42] + insertKey:@88 withValue:@88]; + XCTAssertNotNil([map get:@7], @"Found object"); + XCTAssertNotNil([map get:@3], @"Found object"); + XCTAssertNotNil([map get:@1], @"Found object"); + + + FImmutableSortedDictionary* m1 = [map removeKey:@7]; + FImmutableSortedDictionary* m2 = [map removeKey:@3]; + FImmutableSortedDictionary* m3 = [map removeKey:@1]; + + XCTAssertNil([m1 get:@7], @"Removed object"); + XCTAssertNotNil([m1 get:@3], @"Found object"); + XCTAssertNotNil([m1 get:@1], @"Found object"); + + XCTAssertNil([m2 get:@3], @"Removed object"); + XCTAssertNotNil([m2 get:@7], @"Found object"); + XCTAssertNotNil([m2 get:@1], @"Found object"); + + + XCTAssertNil([m3 get:@1], @"Removed object"); + XCTAssertNotNil([m3 get:@7], @"Found object"); + XCTAssertNotNil([m3 get:@3], @"Found object"); +} + +- (void) testRemovalBug { + FTreeSortedDictionary* map = [[[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@2 withValue:@2] + insertKey:@3 withValue:@3]; + + XCTAssertEqualObjects([map get:@1], @1, @"Found object"); + XCTAssertEqualObjects([map get:@2], @2, @"Found object"); + XCTAssertEqualObjects([map get:@3], @3, @"Found object"); + + FImmutableSortedDictionary* m1 = [map removeKey:@2]; + XCTAssertEqualObjects([m1 get:@1], @1, @"Found object"); + XCTAssertEqualObjects([m1 get:@3], @3, @"Found object"); + XCTAssertNil([m1 get:@2], @"Removed object"); +} + +- (void) testIncreasing { + int total = 100; + + FTreeSortedDictionary* map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + for(int i = 0; i < total; i++) { + NSNumber* item = [NSNumber numberWithInt:i]; + map = [map insertKey:item withValue:item]; + } + + XCTAssertTrue([map count] == 100, @"Check if all 100 objects are in the map"); + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)map.root checkMaxDepth], @"Checking valid depth and tree structure"); + + for(int i = 0; i < total; i++) { + NSNumber* item = [NSNumber numberWithInt:i]; + map = [map removeKey: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 responsd to this check + XCTAssertTrue([map.root isMemberOfClass:[FLLRBEmptyNode class]], @"Root is an empty node"); + XCTAssertFalse([map respondsToSelector:@selector(checkMaxDepth)], @"The empty node doesn't respond to this selector."); +} + +- (void) testStructureShouldBeValidAfterInsertionA { + FTreeSortedDictionary* map = [[[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@2 withValue:@2] + insertKey:@3 withValue:@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 { + FTreeSortedDictionary* map = [[[[[[[[[[[[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@50 withValue:@50] + insertKey:@3 withValue:@3] + insertKey:@4 withValue:@4] + insertKey:@7 withValue:@7] + insertKey:@9 withValue:@9] + insertKey:@20 withValue:@20] + insertKey:@18 withValue:@18] + insertKey:@2 withValue:@2] + insertKey:@71 withValue:@71] + insertKey:@42 withValue:@42] + insertKey:@88 withValue:@88]; + + XCTAssertTrue([map count] == 12, @"Check if all 12 objects are in the map"); + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)map.root checkMaxDepth], @"Checking valid depth and tree structure"); +} + +- (void) testRotateLeftLeavesTreeInAValidState { + FLLRBValueNode* node = [[FLLRBValueNode alloc] initWithKey:@4 withValue:@4 withColor:BLACK withLeft: + [[FLLRBValueNode alloc] initWithKey:@2 withValue:@2 withColor:BLACK withLeft:nil withRight:nil] withRight:[[FLLRBValueNode alloc]initWithKey:@7 withValue:@7 withColor:RED withLeft:[[FLLRBValueNode alloc ]initWithKey:@5 withValue:@5 withColor:BLACK withLeft:nil withRight:nil] withRight:[[FLLRBValueNode alloc] initWithKey:@8 withValue:@8 withColor:BLACK withLeft:nil withRight:nil]]]; + + FLLRBValueNode* node2 = [node performSelector:@selector(rotateLeft)]; + + XCTAssertTrue([node2 count] == 5, @"Make sure the count is correct"); + XCTAssertTrue([node2 checkMaxDepth], @"Check proper structure"); +} + +- (void) testRotateRightLeavesTreeInAValidState { + FLLRBValueNode* node = [[FLLRBValueNode alloc] initWithKey:@7 withValue:@7 withColor:BLACK withLeft:[[FLLRBValueNode alloc] initWithKey:@4 withValue:@4 withColor:RED withLeft:[[FLLRBValueNode alloc] initWithKey:@2 withValue:@2 withColor:BLACK withLeft:nil withRight:nil] withRight:[[FLLRBValueNode alloc] initWithKey:@5 withValue:@5 withColor:BLACK withLeft:nil withRight:nil]] withRight:[[FLLRBValueNode alloc] initWithKey:@8 withValue:@8 withColor:BLACK withLeft:nil withRight:nil]]; + + FLLRBValueNode* node2 = [node performSelector:@selector(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 { + FTreeSortedDictionary* map = [[[[[[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@50 withValue:@50] + insertKey:@3 withValue:@3] + insertKey:@4 withValue:@4] + insertKey:@7 withValue:@7] + insertKey:@9 withValue:@9]; + + XCTAssertTrue([map count] == 6, @"Check if all 6 objects are in the map"); + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)map.root checkMaxDepth], @"Checking valid depth and tree structure"); + + FTreeSortedDictionary* m2 = [[[map insertKey:@20 withValue:@20] + insertKey:@18 withValue:@18] + insertKey:@2 withValue:@2]; + XCTAssertTrue([m2 count] == 9, @"Check if all 9 objects are in the map"); + XCTAssertTrue([m2.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)m2.root checkMaxDepth], @"Checking valid depth and tree structure"); + + FTreeSortedDictionary* m3 = [[[[m2 insertKey:@71 withValue:@71] + insertKey:@42 withValue:@42] + insertKey:@88 withValue:@88] + insertKey:@20 withValue:@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:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)m3.root checkMaxDepth], @"Checking valid depth and tree structure"); +} + +- (void) testOverride { + FTreeSortedDictionary* map = [[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@10 withValue:@10] + insertKey:@10 withValue:@8]; + + XCTAssertEqualObjects([map get:@10], @8, @"Found first object"); +} +- (void) testEmpty { + FTreeSortedDictionary* map = [[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@10 withValue:@10] + removeKey:@10]; + + XCTAssertTrue([map isEmpty], @"Properly empty"); + +} + +- (void) testEmptyGet { + FTreeSortedDictionary* map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + XCTAssertNil([map get:@"something"], @"Properly nil"); +} + +- (void) testEmptyCount { + FTreeSortedDictionary* map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + XCTAssertTrue([map count] == 0, @"Properly zero count"); +} + +- (void) testEmptyRemoval { + FTreeSortedDictionary* map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + XCTAssertTrue([[map removeKey:@"sometjhing"] count] == 0, @"Properly zero count"); +} + +- (void) testReverseTraversal { + FTreeSortedDictionary* map = [[[[[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@5 withValue:@5] + insertKey:@3 withValue:@3] + insertKey:@2 withValue:@2] + insertKey:@4 withValue:@4]; + + __block int next = 5; + [map enumerateKeysAndObjectsReverse:YES usingBlock:^(id key, id value, BOOL *stop) { + XCTAssertEqualObjects(key, [NSNumber numberWithInt:next], @"Properly equal"); + next = next - 1; + }]; +} + + +- (void) testInsertionAndRemovalOfAHundredItems { + int N = 100; + NSMutableArray* toInsert = [[NSMutableArray alloc] initWithCapacity:N]; + NSMutableArray* toRemove = [[NSMutableArray alloc] initWithCapacity:N]; + + for(int i = 0; i < N; i++) { + [toInsert addObject:[NSNumber numberWithInt:i]]; + [toRemove addObject:[NSNumber numberWithInt:i]]; + } + + + [self shuffleArray:toInsert]; + [self shuffleArray:toRemove]; + + FTreeSortedDictionary* map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for(int i = 0; i < N; i++) { + map = [map insertKey:[toInsert objectAtIndex:i] withValue:[toInsert objectAtIndex:i]]; + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)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, [NSNumber numberWithInt:next], @"Correct key"); + XCTAssertEqualObjects(value, [NSNumber numberWithInt:next], @"Correct value"); + next = next + 1; + }]; + XCTAssertEqual(next, N, @"Check we traversed all of the items"); + + // remove them + + for(int i = 0; i < N; i++) { + if([map.root isMemberOfClass:[FLLRBValueNode class]]) { + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)map.root checkMaxDepth], @"Checking valid depth and tree structure"); + } + map = [map removeKey:[toRemove objectAtIndex: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++) { + NSInteger nElements = count - i; + NSInteger n = (arc4random() % nElements) + i; + [array exchangeObjectAtIndex:i withObjectAtIndex:n]; + } +} + +- (void) testBalanceProblem { + + NSArray* toInsert = [[NSArray alloc] initWithObjects:@1,@7,@8,@5,@2,@6,@4,@0,@3, nil]; + + FTreeSortedDictionary* map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for(int i = 0; i < [toInsert count]; i++) { + map = [map insertKey:[toInsert objectAtIndex:i] withValue:[toInsert objectAtIndex:i]]; + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)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, [NSNumber numberWithInt:next], @"Correct key"); + XCTAssertEqualObjects(value, [NSNumber numberWithInt:next], @"Correct value"); + next = next + 1; + }]; + XCTAssertEqual(next, [[NSNumber numberWithUnsignedInteger:[toInsert count]] intValue], @"Check we traversed all of the items"); + + // removing one triggers the balance problem + + map = [map removeKey:@5]; + + if([map.root isMemberOfClass:[FLLRBValueNode class]]) { + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)map.root checkMaxDepth], @"Checking valid depth and tree structure"); + } +} + +- (void) testPredecessorKey { + FTreeSortedDictionary* map = [[[[[[[[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]] + insertKey:@1 withValue:@1] + insertKey:@50 withValue:@50] + insertKey:@3 withValue:@3] + insertKey:@4 withValue:@4] + insertKey:@7 withValue:@7] + insertKey:@9 withValue:@9]; + + XCTAssertNil([map getPredecessorKey:@1], @"First object doesn't have a predecessor"); + XCTAssertEqualObjects([map getPredecessorKey:@3], @1, @"@1"); + XCTAssertEqualObjects([map getPredecessorKey:@4], @3, @"@3"); + XCTAssertEqualObjects([map getPredecessorKey:@7], @4, @"@4"); + XCTAssertEqualObjects([map getPredecessorKey:@9], @7, @"@7"); + XCTAssertEqualObjects([map getPredecessorKey:@50], @9, @"@9"); + XCTAssertThrows([map getPredecessorKey:@777], @"Expect exception about nonexistant key"); +} + +- (void) testEnumerator { + int N = 100; + NSMutableArray* toInsert = [[NSMutableArray alloc] initWithCapacity:N]; + NSMutableArray* toRemove = [[NSMutableArray alloc] initWithCapacity:N]; + + for(int i = 0; i < N; i++) { + [toInsert addObject:[NSNumber numberWithInt:i]]; + [toRemove addObject:[NSNumber numberWithInt:i]]; + } + + + [self shuffleArray:toInsert]; + [self shuffleArray:toRemove]; + + FTreeSortedDictionary* map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for(int i = 0; i < N; i++) { + map = [map insertKey:[toInsert objectAtIndex:i] withValue:[toInsert objectAtIndex:i]]; + XCTAssertTrue([map.root isMemberOfClass:[FLLRBValueNode class]], @"Root is a value node"); + XCTAssertTrue([(FLLRBValueNode *)map.root checkMaxDepth], @"Checking valid depth and tree structure"); + } + XCTAssertTrue([map count] == N, @"Check if all N objects are in the map"); + + NSEnumerator* enumerator = [map keyEnumerator]; + id next = [enumerator nextObject]; + int correctValue = 0; + while(next != nil) { + XCTAssertEqualObjects(next, [NSNumber numberWithInt:correctValue], @"Correct key"); + next = [enumerator nextObject]; + correctValue = correctValue + 1; + } +} + +- (void) testReverseEnumerator { + int N = 20; + NSMutableArray* toInsert = [[NSMutableArray alloc] initWithCapacity:N]; + + for(int i = 0; i < N; i++) { + [toInsert addObject:[NSNumber numberWithInt:i]]; + } + + [self shuffleArray:toInsert]; + + FImmutableSortedDictionary *map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for(int i = 0; i < N; i++) { + map = [map insertKey:[toInsert objectAtIndex:i] withValue:[toInsert objectAtIndex:i]]; + } + XCTAssertTrue([map count] == N, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:[FTreeSortedDictionary class]], @"Make sure we still have a array backed dictionary"); + + NSEnumerator* enumerator = [map reverseKeyEnumerator]; + id next = [enumerator nextObject]; + int correctValue = N - 1; + while(next != nil) { + XCTAssertEqualObjects(next, [NSNumber numberWithInt:correctValue], @"Correct key"); + next = [enumerator nextObject]; + correctValue--; + } +} + +- (void) testEnumeratorFrom { + int N = 20; + NSMutableArray* toInsert = [[NSMutableArray alloc] initWithCapacity:N]; + + for(int i = 0; i < N; i++) { + [toInsert addObject:[NSNumber numberWithInt:i*2]]; + } + + [self shuffleArray:toInsert]; + + FImmutableSortedDictionary *map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for(int i = 0; i < N; i++) { + map = [map insertKey:[toInsert objectAtIndex:i] withValue:[toInsert objectAtIndex:i]]; + } + XCTAssertTrue([map count] == N, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:[FTreeSortedDictionary class]], @"Make sure we still have a array backed dictionary"); + + // Test from inbetween keys + { + NSEnumerator* enumerator = [map keyEnumeratorFrom:@11]; + id next = [enumerator nextObject]; + int correctValue = 12; + while(next != nil) { + XCTAssertEqualObjects(next, [NSNumber numberWithInt:correctValue], @"Correct key"); + next = [enumerator nextObject]; + correctValue = correctValue + 2; + } + } + + // Test from key in map + { + NSEnumerator* enumerator = [map keyEnumeratorFrom:@10]; + id next = [enumerator nextObject]; + int correctValue = 10; + while(next != nil) { + XCTAssertEqualObjects(next, [NSNumber numberWithInt:correctValue], @"Correct key"); + next = [enumerator nextObject]; + correctValue = correctValue + 2; + } + } +} + +- (void) testReverseEnumeratorFrom { + int N = 20; + NSMutableArray* toInsert = [[NSMutableArray alloc] initWithCapacity:N]; + + for(int i = 0; i < N; i++) { + [toInsert addObject:[NSNumber numberWithInt:i*2]]; + } + + [self shuffleArray:toInsert]; + + FImmutableSortedDictionary *map = [[FTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]]; + + // add them to the dictionary + for(int i = 0; i < N; i++) { + map = [map insertKey:[toInsert objectAtIndex:i] withValue:[toInsert objectAtIndex:i]]; + } + XCTAssertTrue([map count] == N, @"Check if all N objects are in the map"); + XCTAssertTrue([map isKindOfClass:[FTreeSortedDictionary class]], @"Make sure we still have a array backed dictionary"); + + // Test from inbetween keys + { + NSEnumerator* enumerator = [map reverseKeyEnumeratorFrom:@11]; + id next = [enumerator nextObject]; + int correctValue = 10; + while(next != nil) { + XCTAssertEqualObjects(next, [NSNumber numberWithInt:correctValue], @"Correct key"); + next = [enumerator nextObject]; + correctValue = correctValue - 2; + } + } + + // Test from key in map + { + NSEnumerator* enumerator = [map reverseKeyEnumeratorFrom:@10]; + id next = [enumerator nextObject]; + int correctValue = 10; + while(next != nil) { + XCTAssertEqualObjects(next, [NSNumber numberWithInt:correctValue], @"Correct key"); + next = [enumerator nextObject]; + correctValue = correctValue - 2; + } + } +} + +@end |