1 files changed, 68 insertions, 0 deletions
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 <Foundation/Foundation.h>
+
+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 <NSObject>
+
+/**
+ * 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<FSTLLRBNode>)aLeft
+               withRight:(nullable id<FSTLLRBNode>)aRight;
+
+/** Returns a tree node with the given key-value pair set/updated. */
+- (id<FSTLLRBNode>)insertKey:(id)aKey forValue:(id)aValue withComparator:(NSComparator)aComparator;
+
+/** Returns a tree node with the given key removed. */
+- (id<FSTLLRBNode>)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<FSTLLRBNode>)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<FSTLLRBNode>)left;
+- (nullable id<FSTLLRBNode>)right;
+
+@end
+
+NS_ASSUME_NONNULL_END