blob: 082b875e427d5f6ab5fa1d415be3a681a4fcaf92 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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
|
