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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/**
* 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>
NS_ASSUME_NONNULL_BEGIN
/**
* 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.
*/
extern const int kSortedDictionaryArrayToRBTreeSizeThreshold;
/**
* FSTImmutableSortedDictionary is a dictionary. It is immutable, but has methods to create new
* dictionaries that are mutations of it, in an efficient way.
*/
@interface FSTImmutableSortedDictionary <KeyType, __covariant ValueType> : NSObject
+ (FSTImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator;
+ (FSTImmutableSortedDictionary *)dictionaryWithDictionary:
(NSDictionary<KeyType, ValueType> *)dictionary
comparator:(NSComparator)comparator;
/**
* Creates a new dictionary identical to this one, but with a key-value pair added or updated.
*
* @param aValue The value to associate with the key.
* @param aKey The key to insert/update.
* @return A new dictionary with the added/updated value.
*/
- (FSTImmutableSortedDictionary<KeyType, ValueType> *)dictionaryBySettingObject:(ValueType)aValue
forKey:(KeyType)aKey;
/**
* Creates a new dictionary identical to this one, but with a key removed from it.
*
* @param aKey The key to remove.
* @return A new dictionary without that value.
*/
- (FSTImmutableSortedDictionary<KeyType, ValueType> *)dictionaryByRemovingObjectForKey:
(KeyType)aKey;
/**
* Looks up a value in the dictionary.
*
* @param key The key to look up.
* @return The value for the key, if present.
*/
- (nullable ValueType)objectForKey:(KeyType)key;
/**
* Looks up a value in the dictionary.
*
* @param key The key to look up.
* @return The value for the key, if present.
*/
- (ValueType)objectForKeyedSubscript:(KeyType)key;
/**
* Returns the index of the key or NSNotFound if the key is not found.
*
* @param key The key to return the index for.
* @return The index of the key, or NSNotFound if key not found.
*/
- (NSUInteger)indexOfKey:(KeyType)key;
/** Returns true if the dictionary contains no elements. */
- (BOOL)isEmpty;
/** Returns the number of items in this dictionary. */
- (NSUInteger)count;
/** Returns the smallest key in this dictionary. */
- (KeyType)minKey;
/** Returns the largest key in this dictionary. */
- (KeyType)maxKey;
/** Calls the given block with each of the items in this dictionary, in order. */
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(KeyType key, ValueType value, BOOL *stop))block;
/** Calls the given block with each of the items in this dictionary, in reverse order. */
- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse
usingBlock:(void (^)(KeyType key, ValueType value, BOOL *stop))block;
/** Returns true if the dictionary contains the given key. */
- (BOOL)containsKey:(KeyType)key;
- (NSEnumerator<KeyType> *)keyEnumerator;
- (NSEnumerator<KeyType> *)keyEnumeratorFrom:(KeyType)startKey;
/** Enumerator for the range [startKey, endKey). */
- (NSEnumerator<KeyType> *)keyEnumeratorFrom:(KeyType)startKey to:(nullable KeyType)endKey;
- (NSEnumerator<KeyType> *)reverseKeyEnumerator;
- (NSEnumerator<KeyType> *)reverseKeyEnumeratorFrom:(KeyType)startKey;
@end
NS_ASSUME_NONNULL_END
|
