diff options
Diffstat (limited to 'Firebase/Database/FImmutableSortedDictionary')
17 files changed, 1775 insertions, 0 deletions
diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary.xcodeproj/project.pbxproj b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary.xcodeproj/project.pbxproj new file mode 100644 index 0000000..ef72cf0 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary.xcodeproj/project.pbxproj @@ -0,0 +1,438 @@ +// !$*UTF8*$! +{ + archiveVersion = 1; + classes = { + }; + objectVersion = 46; + objects = { + +/* Begin PBXBuildFile section */ + EDB1C0A11653283D0041897E /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = EDB1C0A01653283D0041897E /* Foundation.framework */; }; + EDB1C0B01653283D0041897E /* SenTestingKit.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = EDB1C0AF1653283D0041897E /* SenTestingKit.framework */; }; + EDB1C0B21653283D0041897E /* UIKit.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = EDB1C0B11653283D0041897E /* UIKit.framework */; }; + EDB1C0B31653283D0041897E /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = EDB1C0A01653283D0041897E /* Foundation.framework */; }; + EDB1C0B61653283D0041897E /* libFImmutableSortedDictionary.a in Frameworks */ = {isa = PBXBuildFile; fileRef = EDB1C09D1653283D0041897E /* libFImmutableSortedDictionary.a */; }; + EDB1C0BC1653283D0041897E /* InfoPlist.strings in Resources */ = {isa = PBXBuildFile; fileRef = EDB1C0BA1653283D0041897E /* InfoPlist.strings */; }; + EDB1C0BF1653283D0041897E /* FImmutableSortedDictionaryTests.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0BE1653283D0041897E /* FImmutableSortedDictionaryTests.m */; }; + EDB1C0D21653286B0041897E /* FImmutableSortedDictionary.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0CC1653286B0041897E /* FImmutableSortedDictionary.m */; }; + EDB1C0D31653286B0041897E /* FImmutableSortedDictionary.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0CC1653286B0041897E /* FImmutableSortedDictionary.m */; }; + EDB1C0D41653286B0041897E /* FLLRBEmptyNode.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0CF1653286B0041897E /* FLLRBEmptyNode.m */; }; + EDB1C0D51653286B0041897E /* FLLRBEmptyNode.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0CF1653286B0041897E /* FLLRBEmptyNode.m */; }; + EDB1C0D61653286B0041897E /* FLLRBValueNode.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0D11653286B0041897E /* FLLRBValueNode.m */; }; + EDB1C0D71653286B0041897E /* FLLRBValueNode.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0D11653286B0041897E /* FLLRBValueNode.m */; }; + EDB1C0ED165331140041897E /* FImmutableSortedDictionaryEnumerator.m in Sources */ = {isa = PBXBuildFile; fileRef = EDB1C0EC165331140041897E /* FImmutableSortedDictionaryEnumerator.m */; }; +/* End PBXBuildFile section */ + +/* Begin PBXContainerItemProxy section */ + EDB1C0B41653283D0041897E /* PBXContainerItemProxy */ = { + isa = PBXContainerItemProxy; + containerPortal = EDB1C0941653283D0041897E /* Project object */; + proxyType = 1; + remoteGlobalIDString = EDB1C09C1653283D0041897E; + remoteInfo = FImmutableSortedDictionary; + }; +/* End PBXContainerItemProxy section */ + +/* Begin PBXCopyFilesBuildPhase section */ + EDB1C09B1653283D0041897E /* CopyFiles */ = { + isa = PBXCopyFilesBuildPhase; + buildActionMask = 2147483647; + dstPath = "include/${PRODUCT_NAME}"; + dstSubfolderSpec = 16; + files = ( + ); + runOnlyForDeploymentPostprocessing = 0; + }; +/* End PBXCopyFilesBuildPhase section */ + +/* Begin PBXFileReference section */ + EDB1C09D1653283D0041897E /* libFImmutableSortedDictionary.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libFImmutableSortedDictionary.a; sourceTree = BUILT_PRODUCTS_DIR; }; + EDB1C0A01653283D0041897E /* Foundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Foundation.framework; path = System/Library/Frameworks/Foundation.framework; sourceTree = SDKROOT; }; + EDB1C0A41653283D0041897E /* FImmutableSortedDictionary-Prefix.pch */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = "FImmutableSortedDictionary-Prefix.pch"; sourceTree = "<group>"; }; + EDB1C0AE1653283D0041897E /* FImmutableSortedDictionaryTests.octest */ = {isa = PBXFileReference; explicitFileType = wrapper.cfbundle; includeInIndex = 0; path = FImmutableSortedDictionaryTests.octest; sourceTree = BUILT_PRODUCTS_DIR; }; + EDB1C0AF1653283D0041897E /* SenTestingKit.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = SenTestingKit.framework; path = Library/Frameworks/SenTestingKit.framework; sourceTree = DEVELOPER_DIR; }; + EDB1C0B11653283D0041897E /* UIKit.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = UIKit.framework; path = Library/Frameworks/UIKit.framework; sourceTree = DEVELOPER_DIR; }; + EDB1C0B91653283D0041897E /* FImmutableSortedDictionaryTests-Info.plist */ = {isa = PBXFileReference; lastKnownFileType = text.plist.xml; path = "FImmutableSortedDictionaryTests-Info.plist"; sourceTree = "<group>"; }; + EDB1C0BB1653283D0041897E /* en */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = en; path = en.lproj/InfoPlist.strings; sourceTree = "<group>"; }; + EDB1C0BD1653283D0041897E /* FImmutableSortedDictionaryTests.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FImmutableSortedDictionaryTests.h; sourceTree = "<group>"; }; + EDB1C0BE1653283D0041897E /* FImmutableSortedDictionaryTests.m */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.objc; path = FImmutableSortedDictionaryTests.m; sourceTree = "<group>"; }; + EDB1C0CB1653286B0041897E /* FImmutableSortedDictionary.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FImmutableSortedDictionary.h; sourceTree = "<group>"; }; + EDB1C0CC1653286B0041897E /* FImmutableSortedDictionary.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FImmutableSortedDictionary.m; sourceTree = "<group>"; }; + EDB1C0CD1653286B0041897E /* FLLRBNode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FLLRBNode.h; sourceTree = "<group>"; }; + EDB1C0CE1653286B0041897E /* FLLRBEmptyNode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FLLRBEmptyNode.h; sourceTree = "<group>"; }; + EDB1C0CF1653286B0041897E /* FLLRBEmptyNode.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FLLRBEmptyNode.m; sourceTree = "<group>"; }; + EDB1C0D01653286B0041897E /* FLLRBValueNode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FLLRBValueNode.h; sourceTree = "<group>"; }; + EDB1C0D11653286B0041897E /* FLLRBValueNode.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FLLRBValueNode.m; sourceTree = "<group>"; }; + EDB1C0EB165331140041897E /* FImmutableSortedDictionaryEnumerator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FImmutableSortedDictionaryEnumerator.h; sourceTree = "<group>"; }; + EDB1C0EC165331140041897E /* FImmutableSortedDictionaryEnumerator.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FImmutableSortedDictionaryEnumerator.m; sourceTree = "<group>"; }; +/* End PBXFileReference section */ + +/* Begin PBXFrameworksBuildPhase section */ + EDB1C09A1653283D0041897E /* Frameworks */ = { + isa = PBXFrameworksBuildPhase; + buildActionMask = 2147483647; + files = ( + EDB1C0A11653283D0041897E /* Foundation.framework in Frameworks */, + ); + runOnlyForDeploymentPostprocessing = 0; + }; + EDB1C0AA1653283D0041897E /* Frameworks */ = { + isa = PBXFrameworksBuildPhase; + buildActionMask = 2147483647; + files = ( + EDB1C0B01653283D0041897E /* SenTestingKit.framework in Frameworks */, + EDB1C0B21653283D0041897E /* UIKit.framework in Frameworks */, + EDB1C0B31653283D0041897E /* Foundation.framework in Frameworks */, + EDB1C0B61653283D0041897E /* libFImmutableSortedDictionary.a in Frameworks */, + ); + runOnlyForDeploymentPostprocessing = 0; + }; +/* End PBXFrameworksBuildPhase section */ + +/* Begin PBXGroup section */ + EDB1C0921653283D0041897E = { + isa = PBXGroup; + children = ( + EDB1C0A21653283D0041897E /* FImmutableSortedDictionary */, + EDB1C0B71653283D0041897E /* FImmutableSortedDictionaryTests */, + EDB1C09F1653283D0041897E /* Frameworks */, + EDB1C09E1653283D0041897E /* Products */, + ); + sourceTree = "<group>"; + }; + EDB1C09E1653283D0041897E /* Products */ = { + isa = PBXGroup; + children = ( + EDB1C09D1653283D0041897E /* libFImmutableSortedDictionary.a */, + EDB1C0AE1653283D0041897E /* FImmutableSortedDictionaryTests.octest */, + ); + name = Products; + sourceTree = "<group>"; + }; + EDB1C09F1653283D0041897E /* Frameworks */ = { + isa = PBXGroup; + children = ( + EDB1C0A01653283D0041897E /* Foundation.framework */, + EDB1C0AF1653283D0041897E /* SenTestingKit.framework */, + EDB1C0B11653283D0041897E /* UIKit.framework */, + ); + name = Frameworks; + sourceTree = "<group>"; + }; + EDB1C0A21653283D0041897E /* FImmutableSortedDictionary */ = { + isa = PBXGroup; + children = ( + EDB1C0CB1653286B0041897E /* FImmutableSortedDictionary.h */, + EDB1C0CC1653286B0041897E /* FImmutableSortedDictionary.m */, + EDB1C0CD1653286B0041897E /* FLLRBNode.h */, + EDB1C0CE1653286B0041897E /* FLLRBEmptyNode.h */, + EDB1C0CF1653286B0041897E /* FLLRBEmptyNode.m */, + EDB1C0D01653286B0041897E /* FLLRBValueNode.h */, + EDB1C0D11653286B0041897E /* FLLRBValueNode.m */, + EDB1C0EB165331140041897E /* FImmutableSortedDictionaryEnumerator.h */, + EDB1C0EC165331140041897E /* FImmutableSortedDictionaryEnumerator.m */, + EDB1C0A31653283D0041897E /* Supporting Files */, + ); + path = FImmutableSortedDictionary; + sourceTree = "<group>"; + }; + EDB1C0A31653283D0041897E /* Supporting Files */ = { + isa = PBXGroup; + children = ( + EDB1C0A41653283D0041897E /* FImmutableSortedDictionary-Prefix.pch */, + ); + name = "Supporting Files"; + sourceTree = "<group>"; + }; + EDB1C0B71653283D0041897E /* FImmutableSortedDictionaryTests */ = { + isa = PBXGroup; + children = ( + EDB1C0BD1653283D0041897E /* FImmutableSortedDictionaryTests.h */, + EDB1C0BE1653283D0041897E /* FImmutableSortedDictionaryTests.m */, + EDB1C0B81653283D0041897E /* Supporting Files */, + ); + path = FImmutableSortedDictionaryTests; + sourceTree = "<group>"; + }; + EDB1C0B81653283D0041897E /* Supporting Files */ = { + isa = PBXGroup; + children = ( + EDB1C0B91653283D0041897E /* FImmutableSortedDictionaryTests-Info.plist */, + EDB1C0BA1653283D0041897E /* InfoPlist.strings */, + ); + name = "Supporting Files"; + sourceTree = "<group>"; + }; +/* End PBXGroup section */ + +/* Begin PBXNativeTarget section */ + EDB1C09C1653283D0041897E /* FImmutableSortedDictionary */ = { + isa = PBXNativeTarget; + buildConfigurationList = EDB1C0C21653283D0041897E /* Build configuration list for PBXNativeTarget "FImmutableSortedDictionary" */; + buildPhases = ( + EDB1C0991653283D0041897E /* Sources */, + EDB1C09A1653283D0041897E /* Frameworks */, + EDB1C09B1653283D0041897E /* CopyFiles */, + ); + buildRules = ( + ); + dependencies = ( + ); + name = FImmutableSortedDictionary; + productName = FImmutableSortedDictionary; + productReference = EDB1C09D1653283D0041897E /* libFImmutableSortedDictionary.a */; + productType = "com.apple.product-type.library.static"; + }; + EDB1C0AD1653283D0041897E /* FImmutableSortedDictionaryTests */ = { + isa = PBXNativeTarget; + buildConfigurationList = EDB1C0C51653283D0041897E /* Build configuration list for PBXNativeTarget "FImmutableSortedDictionaryTests" */; + buildPhases = ( + EDB1C0A91653283D0041897E /* Sources */, + EDB1C0AA1653283D0041897E /* Frameworks */, + EDB1C0AB1653283D0041897E /* Resources */, + EDB1C0AC1653283D0041897E /* ShellScript */, + ); + buildRules = ( + ); + dependencies = ( + EDB1C0B51653283D0041897E /* PBXTargetDependency */, + ); + name = FImmutableSortedDictionaryTests; + productName = FImmutableSortedDictionaryTests; + productReference = EDB1C0AE1653283D0041897E /* FImmutableSortedDictionaryTests.octest */; + productType = "com.apple.product-type.bundle"; + }; +/* End PBXNativeTarget section */ + +/* Begin PBXProject section */ + EDB1C0941653283D0041897E /* Project object */ = { + isa = PBXProject; + attributes = { + LastUpgradeCheck = 0450; + ORGANIZATIONNAME = Firebase; + }; + buildConfigurationList = EDB1C0971653283D0041897E /* Build configuration list for PBXProject "FImmutableSortedDictionary" */; + compatibilityVersion = "Xcode 3.2"; + developmentRegion = English; + hasScannedForEncodings = 0; + knownRegions = ( + en, + ); + mainGroup = EDB1C0921653283D0041897E; + productRefGroup = EDB1C09E1653283D0041897E /* Products */; + projectDirPath = ""; + projectRoot = ""; + targets = ( + EDB1C09C1653283D0041897E /* FImmutableSortedDictionary */, + EDB1C0AD1653283D0041897E /* FImmutableSortedDictionaryTests */, + ); + }; +/* End PBXProject section */ + +/* Begin PBXResourcesBuildPhase section */ + EDB1C0AB1653283D0041897E /* Resources */ = { + isa = PBXResourcesBuildPhase; + buildActionMask = 2147483647; + files = ( + EDB1C0BC1653283D0041897E /* InfoPlist.strings in Resources */, + ); + runOnlyForDeploymentPostprocessing = 0; + }; +/* End PBXResourcesBuildPhase section */ + +/* Begin PBXShellScriptBuildPhase section */ + EDB1C0AC1653283D0041897E /* ShellScript */ = { + isa = PBXShellScriptBuildPhase; + buildActionMask = 2147483647; + files = ( + ); + inputPaths = ( + ); + outputPaths = ( + ); + runOnlyForDeploymentPostprocessing = 0; + shellPath = /bin/sh; + shellScript = "# Run the unit tests in this test bundle.\n\"${SYSTEM_DEVELOPER_DIR}/Tools/RunUnitTests\"\n"; + }; +/* End PBXShellScriptBuildPhase section */ + +/* Begin PBXSourcesBuildPhase section */ + EDB1C0991653283D0041897E /* Sources */ = { + isa = PBXSourcesBuildPhase; + buildActionMask = 2147483647; + files = ( + EDB1C0D21653286B0041897E /* FImmutableSortedDictionary.m in Sources */, + EDB1C0D41653286B0041897E /* FLLRBEmptyNode.m in Sources */, + EDB1C0D61653286B0041897E /* FLLRBValueNode.m in Sources */, + EDB1C0ED165331140041897E /* FImmutableSortedDictionaryEnumerator.m in Sources */, + ); + runOnlyForDeploymentPostprocessing = 0; + }; + EDB1C0A91653283D0041897E /* Sources */ = { + isa = PBXSourcesBuildPhase; + buildActionMask = 2147483647; + files = ( + EDB1C0BF1653283D0041897E /* FImmutableSortedDictionaryTests.m in Sources */, + EDB1C0D31653286B0041897E /* FImmutableSortedDictionary.m in Sources */, + EDB1C0D51653286B0041897E /* FLLRBEmptyNode.m in Sources */, + EDB1C0D71653286B0041897E /* FLLRBValueNode.m in Sources */, + ); + runOnlyForDeploymentPostprocessing = 0; + }; +/* End PBXSourcesBuildPhase section */ + +/* Begin PBXTargetDependency section */ + EDB1C0B51653283D0041897E /* PBXTargetDependency */ = { + isa = PBXTargetDependency; + target = EDB1C09C1653283D0041897E /* FImmutableSortedDictionary */; + targetProxy = EDB1C0B41653283D0041897E /* PBXContainerItemProxy */; + }; +/* End PBXTargetDependency section */ + +/* Begin PBXVariantGroup section */ + EDB1C0BA1653283D0041897E /* InfoPlist.strings */ = { + isa = PBXVariantGroup; + children = ( + EDB1C0BB1653283D0041897E /* en */, + ); + name = InfoPlist.strings; + sourceTree = "<group>"; + }; +/* End PBXVariantGroup section */ + +/* Begin XCBuildConfiguration section */ + EDB1C0C01653283D0041897E /* Debug */ = { + isa = XCBuildConfiguration; + buildSettings = { + ALWAYS_SEARCH_USER_PATHS = NO; + CLANG_CXX_LANGUAGE_STANDARD = "gnu++0x"; + CLANG_CXX_LIBRARY = "libc++"; + CLANG_ENABLE_OBJC_ARC = YES; + CLANG_WARN_EMPTY_BODY = YES; + CLANG_WARN__DUPLICATE_METHOD_MATCH = YES; + COPY_PHASE_STRIP = NO; + GCC_C_LANGUAGE_STANDARD = gnu99; + GCC_DYNAMIC_NO_PIC = NO; + GCC_OPTIMIZATION_LEVEL = 0; + GCC_PREPROCESSOR_DEFINITIONS = ( + "DEBUG=1", + "$(inherited)", + ); + GCC_SYMBOLS_PRIVATE_EXTERN = NO; + GCC_WARN_ABOUT_RETURN_TYPE = YES; + GCC_WARN_UNINITIALIZED_AUTOS = YES; + GCC_WARN_UNUSED_VARIABLE = YES; + IPHONEOS_DEPLOYMENT_TARGET = 6.0; + ONLY_ACTIVE_ARCH = YES; + SDKROOT = iphoneos; + }; + name = Debug; + }; + EDB1C0C11653283D0041897E /* Release */ = { + isa = XCBuildConfiguration; + buildSettings = { + ALWAYS_SEARCH_USER_PATHS = NO; + CLANG_CXX_LANGUAGE_STANDARD = "gnu++0x"; + CLANG_CXX_LIBRARY = "libc++"; + CLANG_ENABLE_OBJC_ARC = YES; + CLANG_WARN_EMPTY_BODY = YES; + CLANG_WARN__DUPLICATE_METHOD_MATCH = YES; + COPY_PHASE_STRIP = YES; + GCC_C_LANGUAGE_STANDARD = gnu99; + GCC_WARN_ABOUT_RETURN_TYPE = YES; + GCC_WARN_UNINITIALIZED_AUTOS = YES; + GCC_WARN_UNUSED_VARIABLE = YES; + IPHONEOS_DEPLOYMENT_TARGET = 6.0; + SDKROOT = iphoneos; + VALIDATE_PRODUCT = YES; + }; + name = Release; + }; + EDB1C0C31653283D0041897E /* Debug */ = { + isa = XCBuildConfiguration; + buildSettings = { + DSTROOT = /tmp/FImmutableSortedDictionary.dst; + GCC_PRECOMPILE_PREFIX_HEADER = YES; + GCC_PREFIX_HEADER = "FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch"; + OTHER_LDFLAGS = "-ObjC"; + PRODUCT_NAME = "$(TARGET_NAME)"; + SKIP_INSTALL = YES; + }; + name = Debug; + }; + EDB1C0C41653283D0041897E /* Release */ = { + isa = XCBuildConfiguration; + buildSettings = { + DSTROOT = /tmp/FImmutableSortedDictionary.dst; + GCC_PRECOMPILE_PREFIX_HEADER = YES; + GCC_PREFIX_HEADER = "FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch"; + OTHER_LDFLAGS = "-ObjC"; + PRODUCT_NAME = "$(TARGET_NAME)"; + SKIP_INSTALL = YES; + }; + name = Release; + }; + EDB1C0C61653283D0041897E /* Debug */ = { + isa = XCBuildConfiguration; + buildSettings = { + FRAMEWORK_SEARCH_PATHS = ( + "\"$(SDKROOT)/Developer/Library/Frameworks\"", + "\"$(DEVELOPER_LIBRARY_DIR)/Frameworks\"", + ); + GCC_PRECOMPILE_PREFIX_HEADER = YES; + GCC_PREFIX_HEADER = "FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch"; + INFOPLIST_FILE = "FImmutableSortedDictionaryTests/FImmutableSortedDictionaryTests-Info.plist"; + PRODUCT_NAME = "$(TARGET_NAME)"; + WRAPPER_EXTENSION = octest; + }; + name = Debug; + }; + EDB1C0C71653283D0041897E /* Release */ = { + isa = XCBuildConfiguration; + buildSettings = { + FRAMEWORK_SEARCH_PATHS = ( + "\"$(SDKROOT)/Developer/Library/Frameworks\"", + "\"$(DEVELOPER_LIBRARY_DIR)/Frameworks\"", + ); + GCC_PRECOMPILE_PREFIX_HEADER = YES; + GCC_PREFIX_HEADER = "FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch"; + INFOPLIST_FILE = "FImmutableSortedDictionaryTests/FImmutableSortedDictionaryTests-Info.plist"; + PRODUCT_NAME = "$(TARGET_NAME)"; + WRAPPER_EXTENSION = octest; + }; + name = Release; + }; +/* End XCBuildConfiguration section */ + +/* Begin XCConfigurationList section */ + EDB1C0971653283D0041897E /* Build configuration list for PBXProject "FImmutableSortedDictionary" */ = { + isa = XCConfigurationList; + buildConfigurations = ( + EDB1C0C01653283D0041897E /* Debug */, + EDB1C0C11653283D0041897E /* Release */, + ); + defaultConfigurationIsVisible = 0; + defaultConfigurationName = Release; + }; + EDB1C0C21653283D0041897E /* Build configuration list for PBXNativeTarget "FImmutableSortedDictionary" */ = { + isa = XCConfigurationList; + buildConfigurations = ( + EDB1C0C31653283D0041897E /* Debug */, + EDB1C0C41653283D0041897E /* Release */, + ); + defaultConfigurationIsVisible = 0; + defaultConfigurationName = Release; + }; + EDB1C0C51653283D0041897E /* Build configuration list for PBXNativeTarget "FImmutableSortedDictionaryTests" */ = { + isa = XCConfigurationList; + buildConfigurations = ( + EDB1C0C61653283D0041897E /* Debug */, + EDB1C0C71653283D0041897E /* Release */, + ); + defaultConfigurationIsVisible = 0; + defaultConfigurationName = Release; + }; +/* End XCConfigurationList section */ + }; + rootObject = EDB1C0941653283D0041897E /* Project object */; +} diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h new file mode 100644 index 0000000..0c6c989 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h @@ -0,0 +1,37 @@ +/* + * 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. + */ + +#import <Foundation/Foundation.h> +#import "FImmutableSortedDictionary.h" + +/** + * This is an array backed implementation of FImmutableSortedDictionary. It uses arrays and linear lookups to achieve + * good memory efficiency while maintaining good performance for small collections. It also uses less allocations than + * a comparable red black tree. To avoid degrading performance with increasing collection size it will automatically + * convert to a FTreeSortedDictionary after an insert call above a certain threshold. + */ +@interface FArraySortedDictionary : FImmutableSortedDictionary + ++ (FArraySortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator; + +- (id)initWithComparator:(NSComparator)comparator; + +#pragma mark - +#pragma mark Properties + +@property (nonatomic, copy, readonly) NSComparator comparator; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m new file mode 100644 index 0000000..f572b6b --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m @@ -0,0 +1,282 @@ +/* + * 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. + */ + +#import "FArraySortedDictionary.h" +#import "FTreeSortedDictionary.h" + +@interface FArraySortedDictionaryEnumerator : NSEnumerator + +- (id)initWithKeys:(NSArray *)keys startPos:(NSInteger)pos isReverse:(BOOL)reverse; +- (id)nextObject; + +@property (nonatomic) NSInteger pos; +@property (nonatomic) BOOL reverse; +@property (nonatomic, strong) NSArray *keys; + +@end + +@implementation FArraySortedDictionaryEnumerator + +- (id)initWithKeys:(NSArray *)keys startPos:(NSInteger)pos isReverse:(BOOL)reverse +{ + self = [super init]; + if (self != nil) { + self->_pos = pos; + self->_reverse = reverse; + self->_keys = keys; + } + return self; +} + +- (id)nextObject +{ + NSInteger pos = self->_pos; + if (pos >= 0 && pos < self.keys.count) { + if (self.reverse) { + self->_pos--; + } else { + self->_pos++; + } + return self.keys[pos]; + } else { + return nil; + } +} + +@end + +@interface FArraySortedDictionary () + +- (id)initWithComparator:(NSComparator)comparator; + +@property (nonatomic, copy, readwrite) NSComparator comparator; +@property (nonatomic, strong) NSArray *keys; +@property (nonatomic, strong) NSArray *values; + +@end + +@implementation FArraySortedDictionary + ++ (FArraySortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator +{ + NSMutableArray *keys = [NSMutableArray arrayWithCapacity:dictionary.count]; + [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) { + [keys addObject:key]; + }]; + [keys sortUsingComparator:comparator]; + + [keys enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { + if (idx > 0) { + if (comparator(keys[idx - 1], obj) != NSOrderedAscending) { + [NSException raise:NSInvalidArgumentException format:@"Can't create FImmutableSortedDictionary with keys with same ordering!"]; + } + } + }]; + + NSMutableArray *values = [NSMutableArray arrayWithCapacity:keys.count]; + NSInteger pos = 0; + for (id key in keys) { + values[pos++] = dictionary[key]; + } + NSAssert(values.count == keys.count, @"We added as many keys as values"); + return [[FArraySortedDictionary alloc] initWithComparator:comparator keys:keys values:values]; +} + +- (id)initWithComparator:(NSComparator)comparator +{ + self = [super init]; + if (self != nil) { + self->_comparator = comparator; + self->_keys = [NSArray array]; + self->_values = [NSArray array]; + } + return self; +} + +- (id)initWithComparator:(NSComparator)comparator keys:(NSArray *)keys values:(NSArray *)values +{ + self = [super init]; + if (self != nil) { + self->_comparator = comparator; + self->_keys = keys; + self->_values = values; + } + return self; +} + +- (NSInteger) findInsertPositionForKey:(id)key +{ + NSInteger newPos = 0; + while (newPos < self.keys.count && self.comparator(self.keys[newPos], key) < NSOrderedSame) { + newPos++; + } + return newPos; +} + +- (NSInteger) findKey:(id)key +{ + if (key == nil) { + return NSNotFound; + } + for (NSInteger pos = 0; pos < self.keys.count; pos++) { + NSComparisonResult result = self.comparator(key, self.keys[pos]); + if (result == NSOrderedSame) { + return pos; + } else if (result == NSOrderedAscending) { + return NSNotFound; + } + } + return NSNotFound; +} + +- (FImmutableSortedDictionary *) insertKey:(id)key withValue:(id)value +{ + NSInteger pos = [self findKey:key]; + + if (pos == NSNotFound) { + /* + * If we're above the threshold we want to convert it to a tree backed implementation to not have + * degrading performance + */ + if (self.count >= SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD) { + NSMutableDictionary *dict = [NSMutableDictionary dictionaryWithCapacity:self.count]; + for (NSInteger i = 0; i < self.keys.count; i++) { + dict[self.keys[i]] = self.values[i]; + } + dict[key] = value; + return [FTreeSortedDictionary fromDictionary:dict withComparator:self.comparator]; + } else { + NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys]; + NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values]; + NSInteger newPos = [self findInsertPositionForKey:key]; + [newKeys insertObject:key atIndex:newPos]; + [newValues insertObject:value atIndex:newPos]; + return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues]; + } + } else { + NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys]; + NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values]; + newKeys[pos] = key; + newValues[pos] = value; + return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues]; + } +} + +- (FImmutableSortedDictionary *) removeKey:(id)key +{ + NSInteger pos = [self findKey:key]; + if (pos == NSNotFound) { + return self; + } else { + NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys]; + NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values]; + [newKeys removeObjectAtIndex:pos]; + [newValues removeObjectAtIndex:pos]; + return [[FArraySortedDictionary alloc] initWithComparator:self.comparator keys:newKeys values:newValues]; + } +} + +- (id) get:(id)key +{ + NSInteger pos = [self findKey:key]; + if (pos == NSNotFound) { + return nil; + } else { + return self.values[pos]; + } +} + +- (id) getPredecessorKey:(id) key { + NSInteger pos = [self findKey:key]; + if (pos == NSNotFound) { + [NSException raise:NSInternalInconsistencyException format:@"Can't get predecessor key for non-existent key"]; + return nil; + } else if (pos == 0) { + return nil; + } else { + return self.keys[pos - 1]; + } +} + +- (BOOL) isEmpty { + return self.keys.count == 0; +} + +- (int) count +{ + return (int)self.keys.count; +} + +- (id) minKey +{ + return [self.keys firstObject]; +} + +- (id) maxKey +{ + return [self.keys lastObject]; +} + +- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block +{ + [self enumerateKeysAndObjectsReverse:NO usingBlock:block]; +} + +- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block +{ + if (reverse) { + BOOL stop = NO; + for (NSInteger i = self.keys.count - 1; i >= 0; i--) { + block(self.keys[i], self.values[i], &stop); + if (stop) return; + } + } else { + BOOL stop = NO; + for (NSInteger i = 0; i < self.keys.count; i++) { + block(self.keys[i], self.values[i], &stop); + if (stop) return; + } + } +} + +- (BOOL) contains:(id)key { + return [self findKey:key] != NSNotFound; +} + +- (NSEnumerator *) keyEnumerator { + return [self.keys objectEnumerator]; +} + +- (NSEnumerator *) keyEnumeratorFrom:(id)startKey { + NSInteger startPos = [self findInsertPositionForKey:startKey]; + return [[FArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys startPos:startPos isReverse:NO]; +} + +- (NSEnumerator *) reverseKeyEnumerator { + return [self.keys reverseObjectEnumerator]; +} + +- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey { + NSInteger startPos = [self findInsertPositionForKey:startKey]; + // if there's no exact match, findKeyOrInsertPosition will return the index *after* the closest match, but + // since this is a reverse iterator, we want to start just *before* the closest match. + if (startPos >= self.keys.count || self.comparator(self.keys[startPos], startKey) != NSOrderedSame) { + startPos -= 1; + } + return [[FArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys startPos:startPos isReverse:YES]; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch new file mode 100644 index 0000000..88d2408 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch @@ -0,0 +1,7 @@ +// +// Prefix header for all source files of the 'FImmutableSortedDictionary' target in the 'FImmutableSortedDictionary' project +// + +#ifdef __OBJC__ + #import <Foundation/Foundation.h> +#endif diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h new file mode 100644 index 0000000..1e7e5a3 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h @@ -0,0 +1,71 @@ +/* + * 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> + +/** + * 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. + */ +#define SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD 25 + +@interface FImmutableSortedDictionary : NSObject + ++ (FImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator; ++ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator; + +- (FImmutableSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue; +- (FImmutableSortedDictionary *) removeKey:(id)aKey; +- (id) get:(id) key; +- (id) getPredecessorKey:(id) key; +- (BOOL) isEmpty; +- (int) count; +- (id) minKey; +- (id) maxKey; +- (void) enumerateKeysAndObjectsUsingBlock:(void(^)(id key, id value, BOOL *stop))block; +- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void(^)(id key, id value, BOOL *stop))block; +- (BOOL) contains:(id)key; +- (NSEnumerator *) keyEnumerator; +- (NSEnumerator *) keyEnumeratorFrom:(id)startKey; +- (NSEnumerator *) reverseKeyEnumerator; +- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey; + +#pragma mark - +#pragma mark Methods similar to NSMutableDictionary + +- (FImmutableSortedDictionary *) setObject:(id)anObject forKey:(id)aKey; +- (id) objectForKey:(id)key; +- (FImmutableSortedDictionary *) removeObjectForKey:(id)aKey; + +@end + diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m new file mode 100644 index 0000000..006c12d --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m @@ -0,0 +1,158 @@ +/* + * 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. + */ + +#import "FImmutableSortedDictionary.h" +#import "FArraySortedDictionary.h" +#import "FTreeSortedDictionary.h" + +#define THROW_ABSTRACT_METHOD_EXCEPTION(sel) do { \ + @throw [NSException exceptionWithName:NSInternalInconsistencyException \ + reason:[NSString stringWithFormat:@"You must override %@ in a subclass", NSStringFromSelector(sel)] \ + userInfo:nil]; \ +} while(0) + +@implementation FImmutableSortedDictionary + ++ (FImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator +{ + return [[FArraySortedDictionary alloc] initWithComparator:comparator]; +} + ++ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator +{ + if (dictionary.count <= SORTED_DICTIONARY_ARRAY_TO_RB_TREE_SIZE_THRESHOLD) { + return [FArraySortedDictionary fromDictionary:dictionary withComparator:comparator]; + } else { + return [FTreeSortedDictionary fromDictionary:dictionary withComparator:comparator]; + } +} + +- (FImmutableSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(insertKey:withValue:)); +} + +- (FImmutableSortedDictionary *) removeKey:(id)aKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(removeKey:)); +} + +- (id) get:(id) key { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(get:)); +} + +- (id) getPredecessorKey:(id) key { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(getPredecessorKey:)); +} + +- (BOOL) isEmpty { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(isEmpty)); +} + +- (int) count { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector((count))); +} + +- (id) minKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(minKey)); +} + +- (id) maxKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(maxKey)); +} + +- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(enumerateKeysAndObjectsUsingBlock:)); +} + +- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(enumerateKeysAndObjectsReverse:usingBlock:)); +} + +- (BOOL) contains:(id)key { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(contains:)); +} + +- (NSEnumerator *) keyEnumerator { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(keyEnumerator)); +} + +- (NSEnumerator *) keyEnumeratorFrom:(id)startKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(keyEnumeratorFrom:)); +} + +- (NSEnumerator *) reverseKeyEnumerator { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(reverseKeyEnumerator)); +} + +- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey { + THROW_ABSTRACT_METHOD_EXCEPTION(@selector(reverseKeyEnumeratorFrom:)); +} + +- (BOOL)isEqual:(id)object { + if (![object isKindOfClass:[FImmutableSortedDictionary class]]) { + return NO; + } + FImmutableSortedDictionary *other = (FImmutableSortedDictionary *)object; + if (self.count != other.count) { + return NO; + } + __block BOOL isEqual = YES; + [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + id otherValue = [other objectForKey:key]; + isEqual = isEqual && (value == otherValue || [value isEqual:otherValue]); + *stop = !isEqual; + }]; + return isEqual; +} + +- (NSUInteger)hash { + __block NSUInteger hash = 0; + [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + hash = (hash * 31 + [key hash]) * 17 + [value hash]; + }]; + return hash; +} + +- (NSString *)description { + NSMutableString *str = [[NSMutableString alloc] init]; + __block BOOL first = YES; + [str appendString:@"{ "]; + [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) { + if (!first) { + [str appendString:@", "]; + } + first = NO; + [str appendString:[NSString stringWithFormat:@"%@: %@", key, value]]; + }]; + [str appendString:@" }"]; + return str; +} + +#pragma mark - +#pragma mark Methods similar to NSMutableDictionary + +- (FImmutableSortedDictionary *) setObject:(__unsafe_unretained id)anObject forKey:(__unsafe_unretained id)aKey { + return [self insertKey:aKey withValue:anObject]; +} + +- (FImmutableSortedDictionary *) removeObjectForKey:(__unsafe_unretained id)aKey { + return [self removeKey:aKey]; +} + +- (id) objectForKey:(__unsafe_unretained id)key { + return [self get:key]; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h new file mode 100644 index 0000000..bb1a39c --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h @@ -0,0 +1,38 @@ +/* + * 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. + */ + +#import <Foundation/Foundation.h> + +@interface FImmutableSortedSet : NSObject + ++ (FImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)array comparator:(NSComparator)comparator; + +- (BOOL)containsObject:(id)object; +- (FImmutableSortedSet *)addObject:(id)object; +- (FImmutableSortedSet *)removeObject:(id)object; +- (id)firstObject; +- (id)lastObject; +- (NSUInteger)count; +- (BOOL)isEmpty; + +- (id)predecessorEntry:(id)entry; + +- (void)enumerateObjectsUsingBlock:(void (^)(id obj, BOOL *stop))block; +- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id obj, BOOL *stop))block; + +- (NSEnumerator *)objectEnumerator; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m new file mode 100644 index 0000000..09c4164 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m @@ -0,0 +1,131 @@ +/* + * 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. + */ + +#import "FImmutableSortedSet.h" +#import "FImmutableSortedDictionary.h" + +@interface FImmutableSortedSet () + +@property (nonatomic, strong) FImmutableSortedDictionary *dictionary; + +@end + +@implementation FImmutableSortedSet + ++ (FImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)dictionary comparator:(NSComparator)comparator +{ + FImmutableSortedDictionary *setDict = [FImmutableSortedDictionary fromDictionary:dictionary withComparator:comparator]; + return [[FImmutableSortedSet alloc] initWithDictionary:setDict]; +} + +- (id)initWithDictionary:(FImmutableSortedDictionary *)dictionary +{ + self = [super init]; + if (self != nil) { + self->_dictionary = dictionary; + } + return self; +} + +- (BOOL)contains:(id)object +{ + return [self.dictionary contains:object]; +} + +- (FImmutableSortedSet *)addObject:(id)object +{ + FImmutableSortedDictionary *newDictionary = [self.dictionary insertKey:object withValue:[NSNull null]]; + if (newDictionary != self.dictionary) { + return [[FImmutableSortedSet alloc] initWithDictionary:newDictionary]; + } else { + return self; + } +} + +- (FImmutableSortedSet *)removeObject:(id)object +{ + FImmutableSortedDictionary *newDictionary = [self.dictionary removeObjectForKey:object]; + if (newDictionary != self.dictionary) { + return [[FImmutableSortedSet alloc] initWithDictionary:newDictionary]; + } else { + return self; + } +} + +- (BOOL)containsObject:(id)object +{ + return [self.dictionary contains:object]; +} + +- (id)firstObject +{ + return [self.dictionary minKey]; +} + +- (id)lastObject +{ + return [self.dictionary maxKey]; +} + +- (id)predecessorEntry:(id)entry +{ + return [self.dictionary getPredecessorKey:entry]; +} + +- (NSUInteger)count +{ + return [self.dictionary count]; +} + +- (BOOL)isEmpty +{ + return [self.dictionary isEmpty]; +} + +- (void)enumerateObjectsUsingBlock:(void (^)(id, BOOL *))block +{ + [self enumerateObjectsReverse:NO usingBlock:block]; +} + +- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, BOOL *))block +{ + [self.dictionary enumerateKeysAndObjectsReverse:reverse usingBlock:^(id key, id value, BOOL *stop) { + block(key, stop); + }]; +} + +- (NSEnumerator *)objectEnumerator +{ + return [self.dictionary keyEnumerator]; +} + +- (NSString *)description +{ + NSMutableString *str = [[NSMutableString alloc] init]; + __block BOOL first = YES; + [str appendString:@"FImmutableSortedSet ( "]; + [self enumerateObjectsUsingBlock:^(id obj, BOOL *stop) { + if (!first) { + [str appendString:@", "]; + } + first = NO; + [str appendString:[NSString stringWithFormat:@"%@", obj]]; + }]; + [str appendString:@" )"]; + return str; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h new file mode 100644 index 0000000..3257447 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h @@ -0,0 +1,43 @@ +/* + * 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. + */ + +#import <Foundation/Foundation.h> +#import "FLLRBNode.h" + +@interface FLLRBEmptyNode : NSObject <FLLRBNode> + ++ (id)emptyNode; + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight; +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id<FLLRBNode>) remove:(id) aKey withComparator:(NSComparator)aComparator; +- (int) count; +- (BOOL) isEmpty; +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action; +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action; +- (id<FLLRBNode>) min; +- (id) minKey; +- (id) maxKey; +- (BOOL) isRed; +- (int) check; + +@property (nonatomic, strong) id key; +@property (nonatomic, strong) id value; +@property (nonatomic, strong) FLLRBColor* color; +@property (nonatomic, strong) id<FLLRBNode> left; +@property (nonatomic, strong) id<FLLRBNode> right; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m new file mode 100644 index 0000000..adbc6ca --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m @@ -0,0 +1,87 @@ +/* + * 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. + */ + +#import "FLLRBEmptyNode.h" +#import "FLLRBValueNode.h" + +@implementation FLLRBEmptyNode + +@synthesize key, value, color, left, right; + +- (NSString *) description { + return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", key, value, (color ? @"true" : @"false")]; +} + ++ (id)emptyNode +{ + static dispatch_once_t pred = 0; + __strong static id _sharedObject = nil; + dispatch_once(&pred, ^{ + _sharedObject = [[self alloc] init]; // or some other init method + }); + return _sharedObject; +} + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight { + return self; +} + +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator { + FLLRBValueNode* result = [[FLLRBValueNode alloc] initWithKey:aKey withValue:aValue withColor:nil withLeft:nil withRight:nil]; + return result; +} + +- (id<FLLRBNode>) remove:(id) key withComparator:(NSComparator)aComparator { + return self; +} + +- (int) count { + return 0; +} + +- (BOOL) isEmpty { + return YES; +} + +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action { + return NO; +} + +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action { + return NO; +} + +- (id<FLLRBNode>) min { + return self; +} + +- (id) minKey { + return nil; +} + +- (id) maxKey { + return nil; +} + +- (BOOL) isRed { + return NO; +} + +- (int) check { + return 0; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h new file mode 100644 index 0000000..2634494 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h @@ -0,0 +1,45 @@ +/* + * 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. + */ + +#import <Foundation/Foundation.h> + +#define RED @true +#define BLACK @false + +typedef NSNumber FLLRBColor; + +@protocol FLLRBNode <NSObject> + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight; +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id<FLLRBNode>) remove:(id) key withComparator:(NSComparator)aComparator; +- (int) count; +- (BOOL) isEmpty; +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action; +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action; +- (id<FLLRBNode>) min; +- (id) minKey; +- (id) maxKey; +- (BOOL) isRed; +- (int) check; + +@property (nonatomic, strong) id key; +@property (nonatomic, strong) id value; +@property (nonatomic, strong) FLLRBColor* color; +@property (nonatomic, strong) id<FLLRBNode> left; +@property (nonatomic, strong) id<FLLRBNode> right; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h new file mode 100644 index 0000000..2c64b8a --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h @@ -0,0 +1,45 @@ +/* + * 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. + */ + +#import <Foundation/Foundation.h> +#import "FLLRBNode.h" + +@interface FLLRBValueNode : NSObject <FLLRBNode> + + +- (id)initWithKey:(id) key withValue:(id) value withColor:(FLLRBColor*) color withLeft:(id<FLLRBNode>)left withRight:(id<FLLRBNode>)right; +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id<FLLRBNode>)aLeft withRight:(id<FLLRBNode>)aRight; +- (id<FLLRBNode>) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id<FLLRBNode>) remove:(id) aKey withComparator:(NSComparator)aComparator; +- (int) count; +- (BOOL) isEmpty; +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action; +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action; +- (id<FLLRBNode>) min; +- (id) minKey; +- (id) maxKey; +- (BOOL) isRed; +- (int) check; + +- (BOOL) checkMaxDepth; + +@property (nonatomic, strong) id key; +@property (nonatomic, strong) id value; +@property (nonatomic, strong) FLLRBColor* color; +@property (nonatomic, strong) id<FLLRBNode> left; +@property (nonatomic, strong) id<FLLRBNode> right; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m new file mode 100644 index 0000000..f361278 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m @@ -0,0 +1,245 @@ +/* + * 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. + */ + +#import "FLLRBValueNode.h" +#import "FLLRBEmptyNode.h" + +@implementation FLLRBValueNode + +@synthesize key, value, color, left, right; + +- (NSString *) description { + return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", key, value, (color ? @"true" : @"false")]; +} + +- (id)initWithKey:(__unsafe_unretained id) aKey withValue:(__unsafe_unretained id) aValue withColor:(__unsafe_unretained FLLRBColor*) aColor withLeft:(__unsafe_unretained id<FLLRBNode>)aLeft withRight:(__unsafe_unretained id<FLLRBNode>)aRight +{ + self = [super init]; + if (self) { + self.key = aKey; + self.value = aValue; + self.color = aColor != nil ? aColor : RED; + self.left = aLeft != nil ? aLeft : [FLLRBEmptyNode emptyNode]; + self.right = aRight != nil ? aRight : [FLLRBEmptyNode emptyNode]; + } + return self; +} + +- (id)copyWith:(__unsafe_unretained id) aKey withValue:(__unsafe_unretained id) aValue withColor:(__unsafe_unretained FLLRBColor*) aColor withLeft:(__unsafe_unretained id<FLLRBNode>)aLeft withRight:(__unsafe_unretained id<FLLRBNode>)aRight { + return [[FLLRBValueNode alloc] initWithKey:(aKey != nil) ? aKey : self.key + withValue:(aValue != nil) ? aValue : self.value + withColor:(aColor != nil) ? aColor : self.color + withLeft:(aLeft != nil) ? aLeft : self.left + withRight:(aRight != nil) ? aRight : self.right]; +} + +- (int) count { + return [self.left count] + 1 + [self.right count]; +} + +- (BOOL) isEmpty { + return NO; +} + +/** +* Early terminates if aciton returns YES. +* @return The first truthy value returned by action, or the last falsey value returned by action. +*/ +- (BOOL) inorderTraversal:(BOOL (^)(id key, id value))action { + return [self.left inorderTraversal:action] || + action(self.key, self.value) || + [self.right inorderTraversal:action]; +} + +- (BOOL) reverseTraversal:(BOOL (^)(id key, id value))action { + return [self.right reverseTraversal:action] || + action(self.key, self.value) || + [self.left reverseTraversal:action]; +} + +- (id<FLLRBNode>) min { + if([self.left isEmpty]) { + return self; + } + else { + return [self.left min]; + } +} + +- (id) minKey { + return [[self min] key]; +} + +- (id) maxKey { + if([self.right isEmpty]) { + return self.key; + } + else { + return [self.right maxKey]; + } +} + +- (id<FLLRBNode>) insertKey:(__unsafe_unretained id) aKey forValue:(__unsafe_unretained id)aValue withComparator:(NSComparator)aComparator { + NSComparisonResult cmp = aComparator(aKey, self.key); + FLLRBValueNode* n = self; + + if(cmp == NSOrderedAscending) { + n = [n copyWith:nil withValue:nil withColor:nil withLeft:[n.left insertKey:aKey forValue:aValue withComparator:aComparator] withRight:nil]; + } + else if(cmp == NSOrderedSame) { + n = [n copyWith:nil withValue:aValue withColor:nil withLeft:nil withRight:nil]; + } + else { + n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[n.right insertKey:aKey forValue:aValue withComparator:aComparator]]; + } + + return [n fixUp]; +} + +- (id<FLLRBNode>) removeMin { + + if([self.left isEmpty]) { + return [FLLRBEmptyNode emptyNode]; + } + + FLLRBValueNode* n = self; + if(! [n.left isRed] && ! [n.left.left isRed]) { + n = [n moveRedLeft]; + } + + n = [n copyWith:nil withValue:nil withColor:nil withLeft:[(FLLRBValueNode*)n.left removeMin] withRight:nil]; + return [n fixUp]; +} + + +- (id<FLLRBNode>) fixUp { + FLLRBValueNode* n = self; + if([n.right isRed] && ! [n.left isRed]) n = [n rotateLeft]; + if([n.left isRed] && [n.left.left isRed]) n = [n rotateRight]; + if([n.left isRed] && [n.right isRed]) n = [n colorFlip]; + return n; +} + +- (FLLRBValueNode*) moveRedLeft { + FLLRBValueNode* n = [self colorFlip]; + if([n.right.left isRed]) { + n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[(FLLRBValueNode*)n.right rotateRight]]; + n = [n rotateLeft]; + n = [n colorFlip]; + } + return n; +} + +- (FLLRBValueNode*) moveRedRight { + FLLRBValueNode* n = [self colorFlip]; + if([n.left.left isRed]) { + n = [n rotateRight]; + n = [n colorFlip]; + } + return n; +} + +- (id<FLLRBNode>) rotateLeft { + id<FLLRBNode> nl = [self copyWith:nil withValue:nil withColor:RED withLeft:nil withRight:self.right.left]; + return [self.right copyWith:nil withValue:nil withColor:self.color withLeft:nl withRight:nil];; +} + +- (id<FLLRBNode>) rotateRight { + id<FLLRBNode> nr = [self copyWith:nil withValue:nil withColor:RED withLeft:self.left.right withRight:nil]; + return [self.left copyWith:nil withValue:nil withColor:self.color withLeft:nil withRight:nr]; +} + +- (id<FLLRBNode>) colorFlip { + id<FLLRBNode> nleft = [self.left copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.left.color boolValue]] withLeft:nil withRight:nil]; + id<FLLRBNode> nright = [self.right copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.right.color boolValue]] withLeft:nil withRight:nil]; + + return [self copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.color boolValue]] withLeft:nleft withRight:nright]; +} + +- (id<FLLRBNode>) remove:(__unsafe_unretained id) aKey withComparator:(NSComparator)comparator { + id<FLLRBNode> smallest; + FLLRBValueNode* n = self; + + if(comparator(aKey, n.key) == NSOrderedAscending) { + if(![n.left isEmpty] && ![n.left isRed] && ![n.left.left isRed]) { + n = [n moveRedLeft]; + } + n = [n copyWith:nil withValue:nil withColor:nil withLeft:[n.left remove:aKey withComparator:comparator] withRight:nil]; + } + else { + if([n.left isRed]) { + n = [n rotateRight]; + } + + if(![n.right isEmpty] && ![n.right isRed] && ![n.right.left isRed]) { + n = [n moveRedRight]; + } + + if(comparator(aKey, n.key) == NSOrderedSame) { + if([n.right isEmpty]) { + return [FLLRBEmptyNode emptyNode]; + } + else { + smallest = [n.right min]; + n = [n copyWith:smallest.key withValue:smallest.value withColor:nil withLeft:nil withRight:[(FLLRBValueNode*)n.right removeMin]]; + } + } + n = [n copyWith:nil withValue:nil withColor:nil withLeft:nil withRight:[n.right remove:aKey withComparator:comparator]]; + } + return [n fixUp]; +} + +- (BOOL) isRed { + return [self.color boolValue]; +} + +- (BOOL) checkMaxDepth { + int blackDepth = [self check]; + if(pow(2.0, blackDepth) <= ([self count] + 1)) { + return YES; + } + else { + return NO; + } +} + +- (int) check { + int blackDepth = 0; + + if([self isRed] && [self.left isRed]) { + @throw [[NSException alloc] initWithName:@"check" reason:@"Red node has a red child" userInfo:nil]; + } + + if([self.right isRed]) { + @throw [[NSException alloc] initWithName:@"check" reason:@"Right child is red" userInfo:nil]; + } + + blackDepth = [self.left check]; +// NSLog(err); + if(blackDepth != [self.right check]) { + NSString* err = [NSString stringWithFormat:@"(%@ -> %@)blackDepth: %d ; self.right check: %d", self.value, [self.color boolValue] ? @"red" : @"black", blackDepth, [self.right check]]; +// return 10; + @throw [[NSException alloc] initWithName:@"check" reason:err userInfo:nil]; + } + else { + int ret = blackDepth + ([self isRed] ? 0 : 1); +// NSLog(@"black depth is: %d; other is: %d, ret is: %d", blackDepth, ([self isRed] ? 0 : 1), ret); + return ret; + } +} + + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h new file mode 100644 index 0000000..d7fe835 --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h @@ -0,0 +1,25 @@ +/* + * 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. + */ + +#import <Foundation/Foundation.h> +#import "FTreeSortedDictionary.h" + +@interface FTreeSortedDictionaryEnumerator : NSEnumerator + +- (id)initWithImmutableSortedDictionary:(FTreeSortedDictionary *)aDict startKey:(id)startKey isReverse:(BOOL)reverse; +- (id)nextObject; + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m new file mode 100644 index 0000000..6636d1e --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m @@ -0,0 +1,99 @@ +/* + * 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. + */ + +#import "FTreeSortedDictionaryEnumerator.h" + +@interface FTreeSortedDictionaryEnumerator() +@property (nonatomic, strong) FTreeSortedDictionary* immutableSortedDictionary; +@property (nonatomic, strong) NSMutableArray* stack; +@property (nonatomic) BOOL isReverse; + +@end + +@implementation FTreeSortedDictionaryEnumerator + +- (id)initWithImmutableSortedDictionary:(FTreeSortedDictionary *)aDict + startKey:(id)startKey isReverse:(BOOL)reverse { + self = [super init]; + if (self) { + self.immutableSortedDictionary = aDict; + self.stack = [[NSMutableArray alloc] init]; + self.isReverse = reverse; + + NSComparator comparator = aDict.comparator; + id<FLLRBNode> node = self.immutableSortedDictionary.root; + + NSInteger cmp; + while(![node isEmpty]) { + cmp = startKey ? comparator(node.key, startKey) : 1; + // flip the comparison if we're going in reverse + if (self.isReverse) cmp *= -1; + + if (cmp < 0) { + // This node is less than our start key. Ignore it. + if (self.isReverse) { + node = node.left; + } else { + node = node.right; + } + } else if (cmp == 0) { + // This node is exactly equal to our start key. Push it on the stack, but stop iterating: + [self.stack addObject:node]; + break; + } else { + // This node is greater than our start key, add it to the stack and move on to the next one. + [self.stack addObject:node]; + if (self.isReverse) { + node = node.right; + } else { + node = node.left; + } + } + } + } + return self; +} + +- (id)nextObject { + if([self.stack count] == 0) { + return nil; + } + + id<FLLRBNode> node = nil; + @synchronized(self.stack) { + node = [self.stack lastObject]; + [self.stack removeLastObject]; + } + id result = node.key; + + if (self.isReverse) { + node = node.left; + while (![node isEmpty]) { + [self.stack addObject:node]; + node = node.right; + } + } else { + node = node.right; + while (![node isEmpty]) { + [self.stack addObject:node]; + node = node.left; + } + } + + return result; +} + +@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/FImmutableSortedDictionaryTests-Info.plist b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/FImmutableSortedDictionaryTests-Info.plist new file mode 100644 index 0000000..42887ee --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/FImmutableSortedDictionaryTests-Info.plist @@ -0,0 +1,22 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> +<plist version="1.0"> +<dict> + <key>CFBundleDevelopmentRegion</key> + <string>en</string> + <key>CFBundleExecutable</key> + <string>${EXECUTABLE_NAME}</string> + <key>CFBundleIdentifier</key> + <string>com.firebase.mobile.ios.${PRODUCT_NAME:rfc1034identifier}</string> + <key>CFBundleInfoDictionaryVersion</key> + <string>6.0</string> + <key>CFBundlePackageType</key> + <string>BNDL</string> + <key>CFBundleShortVersionString</key> + <string>1.0</string> + <key>CFBundleSignature</key> + <string>????</string> + <key>CFBundleVersion</key> + <string>1</string> +</dict> +</plist> diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/en.lproj/InfoPlist.strings b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/en.lproj/InfoPlist.strings new file mode 100644 index 0000000..477b28f --- /dev/null +++ b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/en.lproj/InfoPlist.strings @@ -0,0 +1,2 @@ +/* Localized versions of Info.plist keys */ + |