Move mugs derived code to third_party with proper LICENSE (#247)

17 files changed, 1481 insertions, 0 deletions

diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h
new file mode 100644
index 0000000..3ab7476
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h
@@ -0,0 +1,21 @@
+#import <Foundation/Foundation.h>
+#import "FImmutableSortedDictionary.h"
+
+/**
+ * This is an array backed implementation of FImmutableSortedDictionary. It uses arrays and linear lookups to achieve
+ * good memory efficiency while maintaining good performance for small collections. It also uses less allocations than
+ * a comparable red black tree. To avoid degrading performance with increasing collection size it will automatically
+ * convert to a FTreeSortedDictionary after an insert call above a certain threshold.
+ */
+@interface FArraySortedDictionary : FImmutableSortedDictionary
+
++ (FArraySortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator;
+
+- (id)initWithComparator:(NSComparator)comparator;
+
+#pragma mark -
+#pragma mark Properties
+
+@property (nonatomic, copy, readonly) NSComparator comparator;
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m
new file mode 100644
index 0000000..15d2d8b
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m
@@ -0,0 +1,266 @@
+#import "FArraySortedDictionary.h"
+#import "FTreeSortedDictionary.h"
+
+@interface FArraySortedDictionaryEnumerator : NSEnumerator
+
+- (id)initWithKeys:(NSArray *)keys startPos:(NSInteger)pos isReverse:(BOOL)reverse;
+- (id)nextObject;
+
+@property (nonatomic) NSInteger pos;
+@property (nonatomic) BOOL reverse;
+@property (nonatomic, strong) NSArray *keys;
+
+@end
+
+@implementation FArraySortedDictionaryEnumerator
+
+- (id)initWithKeys:(NSArray *)keys startPos:(NSInteger)pos isReverse:(BOOL)reverse
+{
+    self = [super init];
+    if (self != nil) {
+        self->_pos = pos;
+        self->_reverse = reverse;
+        self->_keys = keys;
+    }
+    return self;
+}
+
+- (id)nextObject
+{
+    NSInteger pos = self->_pos;
+    if (pos >= 0 && pos < self.keys.count) {
+        if (self.reverse) {
+            self->_pos--;
+        } else {
+            self->_pos++;
+        }
+        return self.keys[pos];
+    } else {
+        return nil;
+    }
+}
+
+@end
+
+@interface FArraySortedDictionary ()
+
+- (id)initWithComparator:(NSComparator)comparator;
+
+@property (nonatomic, copy, readwrite) NSComparator comparator;
+@property (nonatomic, strong) NSArray *keys;
+@property (nonatomic, strong) NSArray *values;
+
+@end
+
+@implementation FArraySortedDictionary
+
++ (FArraySortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator
+{
+    NSMutableArray *keys = [NSMutableArray arrayWithCapacity:dictionary.count];
+    [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
+        [keys addObject:key];
+    }];
+    [keys sortUsingComparator:comparator];
+
+    [keys enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
+        if (idx > 0) {
+            if (comparator(keys[idx - 1], obj) != NSOrderedAscending) {
+                [NSException raise:NSInvalidArgumentException format:@"Can't create FImmutableSortedDictionary with keys with same ordering!"];
+            }
+        }
+    }];
+
+    NSMutableArray *values = [NSMutableArray arrayWithCapacity:keys.count];
+    NSInteger pos = 0;
+    for (id key in keys) {
+        values[pos++] = dictionary[key];
+    }
+    NSAssert(values.count == keys.count, @"We added as many keys as values");
+    return [[FArraySortedDictionary alloc] initWithComparator:comparator keys:keys values:values];
+}
+
+- (id)initWithComparator:(NSComparator)comparator
+{
+    self = [super init];
+    if (self != nil) {
+        self->_comparator = comparator;
+        self->_keys = [NSArray array];
+        self->_values = [NSArray array];
+    }
+    return self;
+}
+
+- (id)initWithComparator:(NSComparator)comparator keys:(NSArray *)keys values:(NSArray *)values
+{
+    self = [super init];
+    if (self != nil) {
+        self->_comparator = comparator;
+        self->_keys = keys;
+        self->_values = values;
+    }
+    return self;
+}
+
+- (NSInteger) findInsertPositionForKey:(id)key
+{
+    NSInteger newPos = 0;
+    while (newPos < self.keys.count && self.comparator(self.keys[newPos], key) < NSOrderedSame) {
+        newPos++;
+    }
+    return newPos;
+}
+
+- (NSInteger) findKey:(id)key
+{
+    if (key == nil) {
+        return NSNotFound;
+    }
+    for (NSInteger pos = 0; pos < self.keys.count; pos++) {
+        NSComparisonResult result = self.comparator(key, self.keys[pos]);
+        if (result == NSOrderedSame) {
+            return pos;
+        } else if (result == NSOrderedAscending) {
+            return NSNotFound;
+        }
+    }
+    return NSNotFound;
+}
+
+- (FImmutableSortedDictionary *) insertKey:(id)key withValue:(id)value
+{
+    NSInteger pos = [self findKey:key];
+
+    if (pos == NSNotFound) {
+        /*
+         * If we're above the threshold we want to convert it to a tree backed implementation to not have
+         * degrading performance
+         */
+        if (self.count >= SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD) {
+            NSMutableDictionary *dict = [NSMutableDictionary dictionaryWithCapacity:self.count];
+            for (NSInteger i = 0; i < self.keys.count; i++) {
+                dict[self.keys[i]] = self.values[i];
+            }
+            dict[key] = value;
+            return [FTreeSortedDictionary fromDictionary:dict withComparator:self.comparator];
+        } else {
+            NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys];
+            NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values];
+            NSInteger newPos = [self findInsertPositionForKey:key];
+            [newKeys insertObject:key atIndex:newPos];
+            [newValues insertObject:value atIndex:newPos];
+            return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues];
+        }
+    } else {
+        NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys];
+        NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values];
+        newKeys[pos] = key;
+        newValues[pos] = value;
+        return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues];
+    }
+}
+
+- (FImmutableSortedDictionary *) removeKey:(id)key
+{
+    NSInteger pos = [self findKey:key];
+    if (pos == NSNotFound) {
+        return self;
+    } else {
+        NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys];
+        NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values];
+        [newKeys removeObjectAtIndex:pos];
+        [newValues removeObjectAtIndex:pos];
+        return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues];
+    }
+}
+
+- (id) get:(id)key
+{
+    NSInteger pos = [self findKey:key];
+    if (pos == NSNotFound) {
+        return nil;
+    } else {
+        return self.values[pos];
+    }
+}
+
+- (id) getPredecessorKey:(id) key {
+    NSInteger pos = [self findKey:key];
+    if (pos == NSNotFound) {
+        [NSException raise:NSInternalInconsistencyException format:@"Can't get predecessor key for non-existent key"];
+        return nil;
+    } else if (pos == 0) {
+        return nil;
+    } else {
+        return self.keys[pos - 1];
+    }
+}
+
+- (BOOL) isEmpty {
+    return self.keys.count == 0;
+}
+
+- (int) count
+{
+    return (int)self.keys.count;
+}
+
+- (id) minKey
+{
+    return [self.keys firstObject];
+}
+
+- (id) maxKey
+{
+    return [self.keys lastObject];
+}
+
+- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block
+{
+    [self enumerateKeysAndObjectsReverse:NO usingBlock:block];
+}
+
+- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block
+{
+    if (reverse) {
+        BOOL stop = NO;
+        for (NSInteger i = self.keys.count - 1; i >= 0; i--) {
+            block(self.keys[i], self.values[i], &stop);
+            if (stop) return;
+        }
+    } else {
+        BOOL stop = NO;
+        for (NSInteger i = 0; i < self.keys.count; i++) {
+            block(self.keys[i], self.values[i], &stop);
+            if (stop) return;
+        }
+    }
+}
+
+- (BOOL) contains:(id)key {
+    return [self findKey:key] != NSNotFound;
+}
+
+- (NSEnumerator *) keyEnumerator {
+    return [self.keys objectEnumerator];
+}
+
+- (NSEnumerator *) keyEnumeratorFrom:(id)startKey {
+    NSInteger startPos = [self findInsertPositionForKey:startKey];
+    return [[FArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys startPos:startPos isReverse:NO];
+}
+
+- (NSEnumerator *) reverseKeyEnumerator {
+    return [self.keys reverseObjectEnumerator];
+}
+
+- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey {
+    NSInteger startPos = [self findInsertPositionForKey:startKey];
+    // if there's no exact match, findKeyOrInsertPosition will return the index *after* the closest match, but
+    // since this is a reverse iterator, we want to start just *before* the closest match.
+    if (startPos >= self.keys.count || self.comparator(self.keys[startPos], startKey) != NSOrderedSame) {
+        startPos -= 1;
+    }
+    return [[FArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys startPos:startPos isReverse:YES];
+}
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch
new file mode 100644
index 0000000..88d2408
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch
@@ -0,0 +1,7 @@
+//
+// Prefix header for all source files of the 'FImmutableSortedDictionary' target in the 'FImmutableSortedDictionary' project
+//
+
+#ifdef __OBJC__
+    #import <Foundation/Foundation.h>
+#endif
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h
new file mode 100644
index 0000000..d6687d8
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h
@@ -0,0 +1,54 @@
+/**
+ * @fileoverview Implementation of an immutable SortedMap using a Left-leaning
+ * Red-Black Tree, adapted from the implementation in Mugs
+ * (http://mads379.github.com/mugs/) by Mads Hartmann Jensen
+ * (mads379@gmail.com).
+ *
+ * Original paper on Left-leaning Red-Black Trees:
+ *   http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
+ *
+ * Invariant 1: No red node has a red child
+ * Invariant 2: Every leaf path has the same number of black nodes
+ * Invariant 3: Only the left child can be red (left leaning)
+ */
+
+#import <Foundation/Foundation.h>
+
+/**
+ * The size threshold where we use a tree backed sorted map instead of an array backed sorted map.
+ * This is a more or less arbitrary chosen value, that was chosen to be large enough to fit most of object kind
+ * of Firebase data, but small enough to not notice degradation in performance for inserting and lookups.
+ * Feel free to empirically determine this constant, but don't expect much gain in real world performance.
+ */
+#define SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD 25
+
+@interface FImmutableSortedDictionary : NSObject
+
++ (FImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator;
++ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator;
+
+- (FImmutableSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue;
+- (FImmutableSortedDictionary *) removeKey:(id)aKey;
+- (id) get:(id) key;
+- (id) getPredecessorKey:(id) key;
+- (BOOL) isEmpty;
+- (int) count;
+- (id) minKey;
+- (id) maxKey;
+- (void) enumerateKeysAndObjectsUsingBlock:(void(^)(id key, id value, BOOL *stop))block;
+- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void(^)(id key, id value, BOOL *stop))block;
+- (BOOL) contains:(id)key;
+- (NSEnumerator *) keyEnumerator;
+- (NSEnumerator *) keyEnumeratorFrom:(id)startKey;
+- (NSEnumerator *) reverseKeyEnumerator;
+- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey;
+
+#pragma mark -
+#pragma mark Methods similar to NSMutableDictionary
+
+- (FImmutableSortedDictionary *) setObject:(id)anObject forKey:(id)aKey;
+- (id) objectForKey:(id)key;
+- (FImmutableSortedDictionary *) removeObjectForKey:(id)aKey;
+
+@end
+
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m
new file mode 100644
index 0000000..659c63b
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m
@@ -0,0 +1,142 @@
+#import "FImmutableSortedDictionary.h"
+#import "FArraySortedDictionary.h"
+#import "FTreeSortedDictionary.h"
+
+#define THROW_ABSTRACT_METHOD_EXCEPTION(sel) do { \
+  @throw [NSException exceptionWithName:NSInternalInconsistencyException \
+  reason:[NSString stringWithFormat:@"You must override %@ in a subclass", NSStringFromSelector(sel)] \
+  userInfo:nil]; \
+} while(0)
+
+@implementation FImmutableSortedDictionary
+
++ (FImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator
+{
+    return [[FArraySortedDictionary alloc] initWithComparator:comparator];
+}
+
++ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator
+{
+    if (dictionary.count <= SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD) {
+        return [FArraySortedDictionary fromDictionary:dictionary withComparator:comparator];
+    } else {
+        return [FTreeSortedDictionary fromDictionary:dictionary withComparator:comparator];
+    }
+}
+
+- (FImmutableSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(insertKey:withValue:));
+}
+
+- (FImmutableSortedDictionary *) removeKey:(id)aKey {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(removeKey:));
+}
+
+- (id) get:(id) key {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(get:));
+}
+
+- (id) getPredecessorKey:(id) key {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(getPredecessorKey:));
+}
+
+- (BOOL) isEmpty {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(isEmpty));
+}
+
+- (int) count {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector((count)));
+}
+
+- (id) minKey {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(minKey));
+}
+
+- (id) maxKey {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(maxKey));
+}
+
+- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(enumerateKeysAndObjectsUsingBlock:));
+}
+
+- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(enumerateKeysAndObjectsReverse:usingBlock:));
+}
+
+- (BOOL) contains:(id)key {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(contains:));
+}
+
+- (NSEnumerator *) keyEnumerator {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(keyEnumerator));
+}
+
+- (NSEnumerator *) keyEnumeratorFrom:(id)startKey {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(keyEnumeratorFrom:));
+}
+
+- (NSEnumerator *) reverseKeyEnumerator {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(reverseKeyEnumerator));
+}
+
+- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey {
+    THROW_ABSTRACT_METHOD_EXCEPTION(@selector(reverseKeyEnumeratorFrom:));
+}
+
+- (BOOL)isEqual:(id)object {
+    if (![object isKindOfClass:[FImmutableSortedDictionary class]]) {
+        return NO;
+    }
+    FImmutableSortedDictionary *other = (FImmutableSortedDictionary *)object;
+    if (self.count != other.count) {
+        return NO;
+    }
+    __block BOOL isEqual = YES;
+    [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+        id otherValue = [other objectForKey:key];
+        isEqual = isEqual && (value == otherValue || [value isEqual:otherValue]);
+        *stop = !isEqual;
+    }];
+    return isEqual;
+}
+
+- (NSUInteger)hash {
+    __block NSUInteger hash = 0;
+    [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+        hash = (hash * 31 + [key hash]) * 17 + [value hash];
+    }];
+    return hash;
+}
+
+- (NSString *)description {
+    NSMutableString *str = [[NSMutableString alloc] init];
+    __block BOOL first = YES;
+    [str appendString:@"{ "];
+    [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+        if (!first) {
+            [str appendString:@", "];
+        }
+        first = NO;
+        [str appendString:[NSString stringWithFormat:@"%@: %@", key, value]];
+    }];
+    [str appendString:@" }"];
+    return str;
+}
+
+#pragma mark -
+#pragma mark Methods similar to NSMutableDictionary
+
+- (FImmutableSortedDictionary *) setObject:(__unsafe_unretained id)anObject forKey:(__unsafe_unretained id)aKey {
+    return [self insertKey:aKey withValue:anObject];
+}
+
+- (FImmutableSortedDictionary *) removeObjectForKey:(__unsafe_unretained id)aKey {
+    return [self removeKey:aKey];
+}
+
+- (id) objectForKey:(__unsafe_unretained id)key {
+    return [self get:key];
+}
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h
new file mode 100644
index 0000000..ac15c2f
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h
@@ -0,0 +1,22 @@
+#import <Foundation/Foundation.h>
+
+@interface FImmutableSortedSet : NSObject
+
++ (FImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)array comparator:(NSComparator)comparator;
+
+- (BOOL)containsObject:(id)object;
+- (FImmutableSortedSet *)addObject:(id)object;
+- (FImmutableSortedSet *)removeObject:(id)object;
+- (id)firstObject;
+- (id)lastObject;
+- (NSUInteger)count;
+- (BOOL)isEmpty;
+
+- (id)predecessorEntry:(id)entry;
+
+- (void)enumerateObjectsUsingBlock:(void (^)(id obj, BOOL *stop))block;
+- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id obj, BOOL *stop))block;
+
+- (NSEnumerator *)objectEnumerator;
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m
new file mode 100644
index 0000000..1953af1
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m
@@ -0,0 +1,115 @@
+#import "FImmutableSortedSet.h"
+#import "FImmutableSortedDictionary.h"
+
+@interface FImmutableSortedSet ()
+
+@property (nonatomic, strong) FImmutableSortedDictionary *dictionary;
+
+@end
+
+@implementation FImmutableSortedSet
+
++ (FImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)dictionary comparator:(NSComparator)comparator
+{
+    FImmutableSortedDictionary *setDict = [FImmutableSortedDictionary fromDictionary:dictionary withComparator:comparator];
+    return [[FImmutableSortedSet alloc] initWithDictionary:setDict];
+}
+
+- (id)initWithDictionary:(FImmutableSortedDictionary *)dictionary
+{
+    self = [super init];
+    if (self != nil) {
+        self->_dictionary = dictionary;
+    }
+    return self;
+}
+
+- (BOOL)contains:(id)object
+{
+    return [self.dictionary contains:object];
+}
+
+- (FImmutableSortedSet *)addObject:(id)object
+{
+    FImmutableSortedDictionary *newDictionary = [self.dictionary insertKey:object withValue:[NSNull null]];
+    if (newDictionary != self.dictionary) {
+        return [[FImmutableSortedSet alloc] initWithDictionary:newDictionary];
+    } else {
+        return self;
+    }
+}
+
+- (FImmutableSortedSet *)removeObject:(id)object
+{
+    FImmutableSortedDictionary *newDictionary = [self.dictionary removeObjectForKey:object];
+    if (newDictionary != self.dictionary) {
+        return [[FImmutableSortedSet alloc] initWithDictionary:newDictionary];
+    } else {
+        return self;
+    }
+}
+
+- (BOOL)containsObject:(id)object
+{
+    return [self.dictionary contains:object];
+}
+
+- (id)firstObject
+{
+    return [self.dictionary minKey];
+}
+
+- (id)lastObject
+{
+    return [self.dictionary maxKey];
+}
+
+- (id)predecessorEntry:(id)entry
+{
+    return [self.dictionary getPredecessorKey:entry];
+}
+
+- (NSUInteger)count
+{
+    return [self.dictionary count];
+}
+
+- (BOOL)isEmpty
+{
+    return [self.dictionary isEmpty];
+}
+
+- (void)enumerateObjectsUsingBlock:(void (^)(id, BOOL *))block
+{
+    [self enumerateObjectsReverse:NO usingBlock:block];
+}
+
+- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, BOOL *))block
+{
+    [self.dictionary enumerateKeysAndObjectsReverse:reverse usingBlock:^(id key, id value, BOOL *stop) {
+        block(key, stop);
+    }];
+}
+
+- (NSEnumerator *)objectEnumerator
+{
+    return [self.dictionary keyEnumerator];
+}
+
+- (NSString *)description
+{
+    NSMutableString *str = [[NSMutableString alloc] init];
+    __block BOOL first = YES;
+    [str appendString:@"FImmutableSortedSet ( "];
+    [self enumerateObjectsUsingBlock:^(id obj, BOOL *stop) {
+        if (!first) {
+            [str appendString:@", "];
+        }
+        first = NO;
+        [str appendString:[NSString stringWithFormat:@"%@", obj]];
+    }];
+    [str appendString:@" )"];
+    return str;
+}
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h
new file mode 100644
index 0000000..833f2a5
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h
@@ -0,0 +1,27 @@
+#import <Foundation/Foundation.h>
+#import "FLLRBNode.h"
+
+@interface FLLRBEmptyNode : NSObject <FLLRBNode>
+
++ (id)emptyNode;
+
+- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight;
+- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator;
+- (id<FLLRBNode>) remove:(id) aKey withComparator:(NSComparator)aComparator;
+- (int) count;
+- (BOOL) isEmpty;
+- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action;
+- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action;
+- (id<FLLRBNode>) min;
+- (id) minKey;
+- (id) maxKey;
+- (BOOL) isRed;
+- (int) check;
+
+@property (nonatomic, strong) id key;
+@property (nonatomic, strong) id value;
+@property (nonatomic, strong) FLLRBColor* color;
+@property (nonatomic, strong) id<FLLRBNode> left;
+@property (nonatomic, strong) id<FLLRBNode> right;
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m
new file mode 100644
index 0000000..fd0c2cc
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m
@@ -0,0 +1,71 @@
+#import "FLLRBEmptyNode.h"
+#import "FLLRBValueNode.h"
+
+@implementation FLLRBEmptyNode
+
+@synthesize key, value, color, left, right;
+
+- (NSString *) description {
+    return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", key, value, (color ? @"true" : @"false")];
+}
+
++ (id)emptyNode
+{
+    static dispatch_once_t pred = 0;
+    __strong static id _sharedObject = nil;
+    dispatch_once(&pred, ^{
+        _sharedObject = [[self alloc] init]; // or some other init method
+    });
+    return _sharedObject;
+}
+
+- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight {
+    return self;
+}
+
+- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator {
+    FLLRBValueNode* result = [[FLLRBValueNode alloc] initWithKey:aKey withValue:aValue withColor:nil withLeft:nil withRight:nil];
+    return result;
+}
+
+- (id<FLLRBNode>) remove:(id) key withComparator:(NSComparator)aComparator {
+    return self;
+}
+
+- (int) count {
+    return 0;
+}
+
+- (BOOL) isEmpty {
+    return YES;
+}
+
+- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action {
+    return NO;
+}
+
+- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action {
+    return NO;
+}
+
+- (id<FLLRBNode>) min {
+    return self;
+}
+
+- (id) minKey {
+    return nil;
+}
+
+- (id) maxKey {
+    return nil;
+}
+
+- (BOOL) isRed {
+    return NO;
+}
+
+- (int) check {
+    return 0;
+}
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h
new file mode 100644
index 0000000..09b234c
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h
@@ -0,0 +1,29 @@
+#import <Foundation/Foundation.h>
+
+#define RED @true
+#define BLACK @false
+
+typedef NSNumber FLLRBColor;
+
+@protocol FLLRBNode <NSObject>
+
+- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight;
+- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator;
+- (id<FLLRBNode>) remove:(id) key withComparator:(NSComparator)aComparator;
+- (int) count;
+- (BOOL) isEmpty;
+- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action;
+- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action;
+- (id<FLLRBNode>) min;
+- (id) minKey;
+- (id) maxKey;
+- (BOOL) isRed;
+- (int) check;
+
+@property (nonatomic, strong) id key;
+@property (nonatomic, strong) id value;
+@property (nonatomic, strong) FLLRBColor* color;
+@property (nonatomic, strong) id<FLLRBNode> left;
+@property (nonatomic, strong) id<FLLRBNode> right;
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h
new file mode 100644
index 0000000..50438bb
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h
@@ -0,0 +1,29 @@
+#import <Foundation/Foundation.h>
+#import "FLLRBNode.h"
+
+@interface FLLRBValueNode : NSObject <FLLRBNode>
+
+
+- (id)initWithKey:(id) key withValue:(id) value withColor:(FLLRBColor*) color withLeft:(id<FLLRBNode>)left withRight:(id<FLLRBNode>)right;
+- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight;
+- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator;
+- (id<FLLRBNode>) remove:(id) aKey withComparator:(NSComparator)aComparator;
+- (int) count;
+- (BOOL) isEmpty;
+- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action;
+- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action;
+- (id<FLLRBNode>) min;
+- (id) minKey;
+- (id) maxKey;
+- (BOOL) isRed;
+- (int) check;
+
+- (BOOL) checkMaxDepth;
+
+@property (nonatomic, strong) id key;
+@property (nonatomic, strong) id value;
+@property (nonatomic, strong) FLLRBColor* color;
+@property (nonatomic, strong) id<FLLRBNode> left;
+@property (nonatomic, strong) id<FLLRBNode> right;
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m
new file mode 100644
index 0000000..2d8771b
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m
@@ -0,0 +1,229 @@
+#import "FLLRBValueNode.h"
+#import "FLLRBEmptyNode.h"
+
+@implementation FLLRBValueNode
+
+@synthesize key, value, color, left, right;
+
+- (NSString *) description {
+    return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", key, value, (color ? @"true" : @"false")];
+}
+
+- (id)initWithKey:(__unsafe_unretained id) aKey withValue:(__unsafe_unretained id) aValue withColor:(__unsafe_unretained FLLRBColor*) aColor withLeft:(__unsafe_unretained id<FLLRBNode>)aLeft withRight:(__unsafe_unretained id<FLLRBNode>)aRight
+{
+    self = [super init];
+    if (self) {
+        self.key = aKey;
+        self.value = aValue;
+        self.color = aColor != nil ? aColor : RED;
+        self.left = aLeft != nil ? aLeft : [FLLRBEmptyNode emptyNode];
+        self.right = aRight != nil ? aRight : [FLLRBEmptyNode emptyNode];
+    }
+    return self;
+}
+
+- (id)copyWith:(__unsafe_unretained id) aKey withValue:(__unsafe_unretained id) aValue withColor:(__unsafe_unretained FLLRBColor*) aColor withLeft:(__unsafe_unretained id<FLLRBNode>)aLeft withRight:(__unsafe_unretained id<FLLRBNode>)aRight {
+    return [[FLLRBValueNode alloc] initWithKey:(aKey != nil) ? aKey : self.key
+                                     withValue:(aValue != nil) ? aValue : self.value
+                                     withColor:(aColor != nil) ? aColor : self.color
+                                      withLeft:(aLeft != nil) ? aLeft : self.left
+                                     withRight:(aRight != nil) ? aRight : self.right];
+}
+
+- (int) count {
+    return [self.left count] + 1 + [self.right count];
+}
+
+- (BOOL) isEmpty {
+    return NO;
+}
+
+/**
+* Early terminates if aciton returns YES.
+* @return The first truthy value returned by action, or the last falsey value returned by action.
+*/
+- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action {
+    return [self.left inorderTraversal:action] ||
+        action(self.key, self.value) ||
+    [self.right inorderTraversal:action];
+}
+
+- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action {
+ return [self.right reverseTraversal:action] ||
+        action(self.key, self.value) ||
+    [self.left reverseTraversal:action];
+}
+
+- (id<FLLRBNode>) min {
+    if([self.left isEmpty]) {
+        return self;
+    }
+    else {
+        return [self.left min];
+    }
+}
+
+- (id) minKey {
+    return [[self min] key];
+}
+
+- (id) maxKey {
+    if([self.right isEmpty]) {
+        return self.key;
+    }
+    else {
+        return [self.right maxKey];
+    }
+}
+
+- (id<FLLRBNode>) insertKey:(__unsafe_unretained id) aKey forValue:(__unsafe_unretained id)aValue withComparator:(NSComparator)aComparator {
+    NSComparisonResult cmp = aComparator(aKey, self.key);
+    FLLRBValueNode* n = self;
+
+    if(cmp == NSOrderedAscending) {
+        n = [n copyWith:nil withValue:nil withColor:nil withLeft:[n.left insertKey:aKey forValue:aValue withComparator:aComparator] withRight:nil];
+    }
+    else if(cmp == NSOrderedSame) {
+        n = [n copyWith:nil withValue:aValue withColor:nil withLeft:nil withRight:nil];
+    }
+    else {
+        n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[n.right insertKey:aKey forValue:aValue withComparator:aComparator]];
+    }
+
+    return [n fixUp];
+}
+
+- (id<FLLRBNode>) removeMin {
+
+    if([self.left isEmpty]) {
+        return [FLLRBEmptyNode emptyNode];
+    }
+
+    FLLRBValueNode* n = self;
+    if(! [n.left isRed] && ! [n.left.left isRed]) {
+        n = [n moveRedLeft];
+    }
+
+    n = [n copyWith:nil withValue:nil withColor:nil withLeft:[(FLLRBValueNode*)n.left removeMin] withRight:nil];
+    return [n fixUp];
+}
+
+
+- (id<FLLRBNode>) fixUp {
+    FLLRBValueNode* n = self;
+    if([n.right isRed] && ! [n.left isRed]) n = [n rotateLeft];
+    if([n.left isRed] && [n.left.left isRed]) n = [n rotateRight];
+    if([n.left isRed] && [n.right isRed]) n = [n colorFlip];
+    return n;
+}
+
+- (FLLRBValueNode*) moveRedLeft {
+    FLLRBValueNode* n = [self colorFlip];
+    if([n.right.left isRed]) {
+        n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[(FLLRBValueNode*)n.right rotateRight]];
+        n = [n rotateLeft];
+        n = [n colorFlip];
+    }
+    return n;
+}
+
+- (FLLRBValueNode*) moveRedRight {
+    FLLRBValueNode* n = [self colorFlip];
+    if([n.left.left isRed]) {
+        n = [n rotateRight];
+        n = [n colorFlip];
+    }
+    return n;
+}
+
+- (id<FLLRBNode>) rotateLeft {
+    id<FLLRBNode> nl = [self copyWith:nil withValue:nil withColor:RED withLeft:nil withRight:self.right.left];
+    return [self.right copyWith:nil withValue:nil withColor:self.color withLeft:nl withRight:nil];;
+}
+
+- (id<FLLRBNode>) rotateRight {
+    id<FLLRBNode> nr = [self copyWith:nil withValue:nil withColor:RED withLeft:self.left.right withRight:nil];
+    return [self.left copyWith:nil withValue:nil withColor:self.color withLeft:nil withRight:nr];
+}
+
+- (id<FLLRBNode>) colorFlip {
+    id<FLLRBNode> nleft = [self.left copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.left.color boolValue]] withLeft:nil withRight:nil];
+    id<FLLRBNode> nright = [self.right copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.right.color boolValue]] withLeft:nil withRight:nil];
+
+    return [self copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.color boolValue]] withLeft:nleft withRight:nright];
+}
+
+- (id<FLLRBNode>) remove:(__unsafe_unretained id) aKey withComparator:(NSComparator)comparator {
+    id<FLLRBNode> smallest;
+    FLLRBValueNode* n = self;
+
+    if(comparator(aKey, n.key) == NSOrderedAscending) {
+        if(![n.left isEmpty] && ![n.left isRed] && ![n.left.left isRed]) {
+            n = [n moveRedLeft];
+        }
+        n = [n copyWith:nil withValue:nil withColor:nil withLeft:[n.left remove:aKey withComparator:comparator] withRight:nil];
+    }
+    else {
+        if([n.left isRed]) {
+            n = [n rotateRight];
+        }
+
+        if(![n.right isEmpty] && ![n.right isRed] && ![n.right.left isRed]) {
+            n = [n moveRedRight];
+        }
+
+        if(comparator(aKey, n.key) == NSOrderedSame) {
+            if([n.right isEmpty]) {
+                return [FLLRBEmptyNode emptyNode];
+            }
+            else {
+                smallest = [n.right min];
+                n = [n copyWith:smallest.key withValue:smallest.value withColor:nil withLeft:nil withRight:[(FLLRBValueNode*)n.right removeMin]];
+            }
+        }
+        n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[n.right remove:aKey withComparator:comparator]];
+    }
+    return [n fixUp];
+}
+
+- (BOOL) isRed {
+    return [self.color boolValue];
+}
+
+- (BOOL) checkMaxDepth {
+    int blackDepth = [self check];
+    if(pow(2.0, blackDepth) <= ([self count] + 1)) {
+        return YES;
+    }
+    else {
+        return NO;
+    }
+}
+
+- (int) check {
+    int blackDepth = 0;
+
+    if([self isRed] && [self.left isRed]) {
+        @throw [[NSException alloc] initWithName:@"check" reason:@"Red node has a red child" userInfo:nil];
+    }
+
+    if([self.right isRed]) {
+        @throw [[NSException alloc] initWithName:@"check" reason:@"Right child is red" userInfo:nil];
+    }
+
+    blackDepth = [self.left check];
+//    NSLog(err);
+    if(blackDepth != [self.right check]) {
+        NSString* err = [NSString stringWithFormat:@"(%@ -> %@)blackDepth: %d ; self.right check: %d", self.value, [self.color boolValue] ? @"red" : @"black", blackDepth, [self.right check]];
+//        return 10;
+        @throw [[NSException alloc] initWithName:@"check" reason:err userInfo:nil];
+    }
+    else {
+                int ret = blackDepth + ([self isRed] ? 0 : 1);
+//        NSLog(@"black depth is: %d; other is: %d, ret is: %d", blackDepth, ([self isRed] ? 0 : 1), ret);
+        return ret;
+    }
+}
+
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.h
new file mode 100644
index 0000000..934ca8b
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.h
@@ -0,0 +1,30 @@
+/**
+ * @fileoverview Implementation of an immutable SortedMap using a Left-leaning
+ * Red-Black Tree, adapted from the implementation in Mugs
+ * (http://mads379.github.com/mugs/) by Mads Hartmann Jensen
+ * (mads379@gmail.com).
+ *
+ * Original paper on Left-leaning Red-Black Trees:
+ *   http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
+ *
+ * Invariant 1: No red node has a red child
+ * Invariant 2: Every leaf path has the same number of black nodes
+ * Invariant 3: Only the left child can be red (left leaning)
+ */
+
+#import <Foundation/Foundation.h>
+#import "FImmutableSortedDictionary.h"
+#import "FLLRBNode.h"
+
+@interface FTreeSortedDictionary : FImmutableSortedDictionary
+
+@property (nonatomic, copy, readonly) NSComparator comparator;
+@property (nonatomic, strong, readonly) id<FLLRBNode> root;
+
+- (id)initWithComparator:(NSComparator)aComparator;
+
+// Override methods to return subtype
+- (FTreeSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue;
+- (FTreeSortedDictionary *) removeKey:(id)aKey;
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.m
new file mode 100644
index 0000000..e9f0683
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.m
@@ -0,0 +1,326 @@
+#import "FTreeSortedDictionary.h"
+#import "FLLRBEmptyNode.h"
+#import "FLLRBValueNode.h"
+#import "FTreeSortedDictionaryEnumerator.h"
+
+typedef void (^fbt_void_nsnumber_int)(NSNumber* color, NSUInteger chunkSize);
+
+@interface FTreeSortedDictionary ()
+
+@property (nonatomic, strong) id<FLLRBNode> root;
+@property (nonatomic, copy, readwrite) NSComparator comparator;
+
+@end
+
+@implementation FTreeSortedDictionary
+
+- (id)initWithComparator:(NSComparator)aComparator {
+    self = [super init];
+    if (self) {
+        self.root = [FLLRBEmptyNode emptyNode];
+        self.comparator = aComparator;
+    }
+    return self;
+}
+
+- (id)initWithComparator:(NSComparator)aComparator withRoot:(__unsafe_unretained id<FLLRBNode>)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.
+ */
+- (FTreeSortedDictionary *) insertKey:(__unsafe_unretained id)aKey withValue:(__unsafe_unretained id)aValue {
+    return [[FTreeSortedDictionary alloc] initWithComparator:self.comparator
+                                                    withRoot:[[self.root insertKey:aKey forValue:aValue withComparator:self.comparator]
+                                                              copyWith:nil
+                                                              withValue:nil
+                                                              withColor:BLACK
+                                                              withLeft:nil
+                                                              withRight:nil]];
+}
+
+
+- (FTreeSortedDictionary *) removeKey:(__unsafe_unretained id)aKey {
+    // Remove is somewhat expensive even if the key doesn't exist (the tree does rebalancing and stuff).  So avoid it.
+    if (![self contains:aKey]) {
+        return self;
+    } else {
+        return [[FTreeSortedDictionary alloc]
+                initWithComparator:self.comparator
+                withRoot:[[self.root remove:aKey withComparator:self.comparator]
+                          copyWith:nil
+                          withValue:nil
+                          withColor:BLACK
+                          withLeft:nil
+                          withRight:nil]];
+    }
+}
+
+- (id) get:(__unsafe_unretained id) key {
+    if (key == nil) {
+        return nil;
+    }
+    NSComparisonResult cmp;
+    id<FLLRBNode> 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;
+}
+
+- (id) getPredecessorKey:(__unsafe_unretained id) key {
+    NSComparisonResult cmp;
+    id<FLLRBNode> node = self.root;
+    id<FLLRBNode> 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] }];
+}
+
+- (BOOL) isEmpty {
+    return [self.root isEmpty];
+}
+
+- (int) 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) contains:(__unsafe_unretained id)key {
+    return ([self objectForKey:key] != nil);
+}
+
+- (NSEnumerator *) keyEnumerator {
+    return [[FTreeSortedDictionaryEnumerator alloc]
+            initWithImmutableSortedDictionary:self startKey:nil isReverse:NO];
+}
+
+- (NSEnumerator *) keyEnumeratorFrom:(id)startKey {
+    return [[FTreeSortedDictionaryEnumerator alloc]
+            initWithImmutableSortedDictionary:self startKey:startKey isReverse:NO];
+}
+
+- (NSEnumerator *) reverseKeyEnumerator {
+    return [[FTreeSortedDictionaryEnumerator alloc]
+            initWithImmutableSortedDictionary:self startKey:nil isReverse:YES];
+}
+
+- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey {
+    return [[FTreeSortedDictionaryEnumerator alloc]
+            initWithImmutableSortedDictionary:self startKey:startKey isReverse:YES];
+}
+
+
+#pragma mark -
+#pragma mark Tree Builder
+
+// Code to efficiently build a RB Tree
+typedef struct _base1_2list {
+    unsigned int bits;
+    unsigned short count;
+    unsigned short current;
+} Base1_2List;
+
+Base1_2List *base1_2List_new(unsigned int length);
+void base1_2List_free(Base1_2List* list);
+unsigned int log_base2(unsigned int num);
+BOOL base1_2List_next(Base1_2List* list);
+
+unsigned int log_base2(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 base1_2List_next(Base1_2List* list) {
+    BOOL result = !(list->bits & (0x1 << list->current));
+    list->current--;
+    return result;
+}
+
+static inline unsigned bit_mask(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}
+ */
+Base1_2List *base1_2List_new(unsigned int length) {
+    size_t sz = sizeof(Base1_2List);
+    Base1_2List* list = calloc(1, sz);
+    // Calculate the number of bits that we care about
+    list->count = (unsigned short)log_base2(length + 1);
+    unsigned int mask = bit_mask(list->count);
+    list->bits = (length + 1) & mask;
+    list->current = list->count - 1;
+    return list;
+}
+
+
+void base1_2List_free(Base1_2List* list) {
+    free(list);
+}
+
++ (id<FLLRBNode>) 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 [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:BLACK withLeft:nil withRight:nil];
+    } else {
+        NSUInteger middle = length / 2;
+        id<FLLRBNode> left = [FTreeSortedDictionary buildBalancedTree:keys dictionary:dictionary subArrayStartIndex:startIndex length:middle];
+        id<FLLRBNode> right = [FTreeSortedDictionary buildBalancedTree:keys dictionary:dictionary subArrayStartIndex:(startIndex+middle+1) length:middle];
+        id key = keys[startIndex + middle];
+        return [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:BLACK withLeft:left withRight:right];
+    }
+}
+
++ (id<FLLRBNode>) rootFrom12List:(Base1_2List *)base1_2List keyList:(NSArray *)keyList dictionary:(NSDictionary *)dictionary {
+    __block id<FLLRBNode> root = nil;
+    __block id<FLLRBNode> node = nil;
+    __block NSUInteger index = keyList.count;
+
+    fbt_void_nsnumber_int buildPennant = ^(NSNumber* color, NSUInteger chunkSize) {
+        NSUInteger startIndex = index - chunkSize + 1;
+        index -= chunkSize;
+        id key = keyList[index];
+        id<FLLRBNode> childTree = [self buildBalancedTree:keyList dictionary:dictionary subArrayStartIndex:startIndex length:(chunkSize - 1)];
+        id<FLLRBNode> pennant = [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:color withLeft:nil withRight:childTree];
+        //attachPennant(pennant);
+        if (node) {
+            node.left = pennant;
+            node = pennant;
+        } else {
+            root = pennant;
+            node = pennant;
+        }
+    };
+
+    for (int i = 0; i < base1_2List->count; ++i) {
+        BOOL isOne = base1_2List_next(base1_2List);
+        NSUInteger chunkSize = (NSUInteger)pow(2.0, base1_2List->count - (i + 1));
+        if (isOne) {
+            buildPennant(BLACK, chunkSize);
+        } else {
+            buildPennant(BLACK, chunkSize);
+            buildPennant(RED, chunkSize);
+        }
+    }
+    return root;
+}
+
+/**
+ * Uses the algorithm linked here:
+ * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1458
+ */
+
++ (FImmutableSortedDictionary *)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 FImmutableSortedDictionary with keys with same ordering!"];
+            }
+        }
+    }];
+
+    Base1_2List* list = base1_2List_new((unsigned int)sortedKeyList.count);
+    id<FLLRBNode> root = [self rootFrom12List:list keyList:sortedKeyList dictionary:dictionary];
+    base1_2List_free(list);
+
+    if (root != nil) {
+        return [[FTreeSortedDictionary alloc] initWithComparator:comparator withRoot:root];
+    } else {
+        return [[FTreeSortedDictionary alloc] initWithComparator:comparator];
+    }
+}
+
+@end
+
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h
new file mode 100644
index 0000000..d79fe8e
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h
@@ -0,0 +1,9 @@
+#import <Foundation/Foundation.h>
+#import "FTreeSortedDictionary.h"
+
+@interface FTreeSortedDictionaryEnumerator : NSEnumerator
+
+- (id)initWithImmutableSortedDictionary:(FTreeSortedDictionary *)aDict startKey:(id)startKey isReverse:(BOOL)reverse;
+- (id)nextObject;
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m
new file mode 100644
index 0000000..2aca86e
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m
@@ -0,0 +1,83 @@
+#import "FTreeSortedDictionaryEnumerator.h"
+
+@interface FTreeSortedDictionaryEnumerator()
+@property (nonatomic, strong) FTreeSortedDictionary* immutableSortedDictionary;
+@property (nonatomic, strong) NSMutableArray* stack;
+@property (nonatomic) BOOL isReverse;
+
+@end
+
+@implementation FTreeSortedDictionaryEnumerator
+
+- (id)initWithImmutableSortedDictionary:(FTreeSortedDictionary *)aDict
+                               startKey:(id)startKey isReverse:(BOOL)reverse {
+    self = [super init];
+    if (self) {
+        self.immutableSortedDictionary = aDict;
+        self.stack = [[NSMutableArray alloc] init];
+        self.isReverse = reverse;
+
+        NSComparator comparator = aDict.comparator;
+        id<FLLRBNode> node = self.immutableSortedDictionary.root;
+
+        NSInteger cmp;
+        while(![node isEmpty]) {
+            cmp = startKey ? comparator(node.key, startKey) : 1;
+            // flip the comparison if we're going in reverse
+            if (self.isReverse) cmp *= -1;
+
+            if (cmp < 0) {
+                // This node is less than our start key. Ignore it.
+                if (self.isReverse) {
+                    node = node.left;
+                } else {
+                    node = node.right;
+                }
+            } else if (cmp == 0) {
+                // This node is exactly equal to our start key. Push it on the stack, but stop iterating:
+                [self.stack addObject:node];
+                break;
+            } else {
+                // This node is greater than our start key, add it to the stack and move on to the next one.
+                [self.stack addObject:node];
+                if (self.isReverse) {
+                    node = node.right;
+                } else {
+                    node = node.left;
+                }
+            }
+        }
+    }
+    return self;
+}
+
+- (id)nextObject {
+    if([self.stack count] == 0) {
+        return nil;
+    }
+
+    id<FLLRBNode> node = nil;
+    @synchronized(self.stack) {
+        node = [self.stack lastObject];
+        [self.stack removeLastObject];
+    }
+    id result = node.key;
+
+    if (self.isReverse) {
+        node = node.left;
+        while (![node isEmpty]) {
+            [self.stack addObject:node];
+            node = node.right;
+        }
+    } else {
+        node = node.right;
+        while (![node isEmpty]) {
+            [self.stack addObject:node];
+            node = node.left;
+        }
+    }
+
+    return result;
+}
+
+@end
diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/LICENSE b/Firebase/Database/third_party/FImmutableSortedDictionary/LICENSE
new file mode 100644
index 0000000..b437003
--- /dev/null
+++ b/Firebase/Database/third_party/FImmutableSortedDictionary/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.