diff options
author | Paul Beusterien <paulbeusterien@google.com> | 2017-05-15 12:27:07 -0700 |
---|---|---|
committer | Paul Beusterien <paulbeusterien@google.com> | 2017-05-15 12:27:07 -0700 |
commit | 98ba64449a632518bd2b86fe8d927f4a960d3ddc (patch) | |
tree | 131d9c4272fa6179fcda6c5a33fcb3b1bd57ad2e /Firebase/Database/FTreeSortedDictionary.h | |
parent | 32461366c9e204a527ca05e6e9b9404a2454ac51 (diff) |
Initial
Diffstat (limited to 'Firebase/Database/FTreeSortedDictionary.h')
-rw-r--r-- | Firebase/Database/FTreeSortedDictionary.h | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/Firebase/Database/FTreeSortedDictionary.h b/Firebase/Database/FTreeSortedDictionary.h new file mode 100644 index 0000000..de75988 --- /dev/null +++ b/Firebase/Database/FTreeSortedDictionary.h @@ -0,0 +1,46 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @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 |