diff options
author | Gil <mcg@google.com> | 2017-10-03 08:55:22 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-10-03 08:55:22 -0700 |
commit | bde743ed25166a0b320ae157bfb1d68064f531c9 (patch) | |
tree | 4dd7525d9df32fa5dbdb721d4b0d4f9b87f5e884 /Firestore/third_party/Immutable/FSTTreeSortedDictionary.h | |
parent | bf550507ffa8beee149383a5bf1e2363bccefbb4 (diff) |
Release 4.3.0 (#327)
Initial release of Firestore at 0.8.0
Bump FirebaseCommunity to 0.1.3
Diffstat (limited to 'Firestore/third_party/Immutable/FSTTreeSortedDictionary.h')
-rw-r--r-- | Firestore/third_party/Immutable/FSTTreeSortedDictionary.h | 41 |
1 files changed, 41 insertions, 0 deletions
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 <Foundation/Foundation.h> + +#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 <KeyType, ValueType> : + FSTImmutableSortedDictionary<KeyType, ValueType> + +@property(nonatomic, copy, readonly) NSComparator comparator; +@property(nonatomic, strong, readonly) id<FSTLLRBNode> root; + +- (id)init __attribute__((unavailable("Use initWithComparator:withRoot: instead."))); + +- (instancetype)initWithComparator:(NSComparator)aComparator; + +- (instancetype)initWithComparator:(NSComparator)aComparator + withRoot:(id<FSTLLRBNode>)aRoot NS_DESIGNATED_INITIALIZER; + +@end + +NS_ASSUME_NONNULL_END |