From 1c97e8266a0db497b4f7e50c9d75d710bd8c649d Mon Sep 17 00:00:00 2001 From: Paul Beusterien Date: Wed, 13 Sep 2017 15:35:01 -0700 Subject: Move mugs derived code to third_party with proper LICENSE (#247) --- .../project.pbxproj | 438 --------------------- .../FArraySortedDictionary.h | 37 -- .../FArraySortedDictionary.m | 282 ------------- .../FImmutableSortedDictionary-Prefix.pch | 7 - .../FImmutableSortedDictionary.h | 71 ---- .../FImmutableSortedDictionary.m | 158 -------- .../FImmutableSortedSet.h | 38 -- .../FImmutableSortedSet.m | 131 ------ .../FImmutableSortedDictionary/FLLRBEmptyNode.h | 43 -- .../FImmutableSortedDictionary/FLLRBEmptyNode.m | 87 ---- .../FImmutableSortedDictionary/FLLRBNode.h | 45 --- .../FImmutableSortedDictionary/FLLRBValueNode.h | 45 --- .../FImmutableSortedDictionary/FLLRBValueNode.m | 245 ------------ .../FTreeSortedDictionaryEnumerator.h | 25 -- .../FTreeSortedDictionaryEnumerator.m | 99 ----- .../FImmutableSortedDictionaryTests-Info.plist | 22 -- .../en.lproj/InfoPlist.strings | 2 - Firebase/Database/FTreeSortedDictionary.h | 46 --- Firebase/Database/FTreeSortedDictionary.m | 342 ---------------- .../FArraySortedDictionary.h | 21 + .../FArraySortedDictionary.m | 266 +++++++++++++ .../FImmutableSortedDictionary-Prefix.pch | 7 + .../FImmutableSortedDictionary.h | 54 +++ .../FImmutableSortedDictionary.m | 142 +++++++ .../FImmutableSortedSet.h | 22 ++ .../FImmutableSortedSet.m | 115 ++++++ .../FImmutableSortedDictionary/FLLRBEmptyNode.h | 27 ++ .../FImmutableSortedDictionary/FLLRBEmptyNode.m | 71 ++++ .../FImmutableSortedDictionary/FLLRBNode.h | 29 ++ .../FImmutableSortedDictionary/FLLRBValueNode.h | 29 ++ .../FImmutableSortedDictionary/FLLRBValueNode.m | 229 +++++++++++ .../FTreeSortedDictionary.h | 30 ++ .../FTreeSortedDictionary.m | 326 +++++++++++++++ .../FTreeSortedDictionaryEnumerator.h | 9 + .../FTreeSortedDictionaryEnumerator.m | 83 ++++ .../third_party/FImmutableSortedDictionary/LICENSE | 21 + 36 files changed, 1481 insertions(+), 2163 deletions(-) delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary.xcodeproj/project.pbxproj delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/FImmutableSortedDictionaryTests-Info.plist delete mode 100644 Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/en.lproj/InfoPlist.strings delete mode 100644 Firebase/Database/FTreeSortedDictionary.h delete mode 100644 Firebase/Database/FTreeSortedDictionary.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m create mode 100644 Firebase/Database/third_party/FImmutableSortedDictionary/LICENSE (limited to 'Firebase/Database') diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary.xcodeproj/project.pbxproj b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary.xcodeproj/project.pbxproj deleted file mode 100644 index ef72cf0..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary.xcodeproj/project.pbxproj +++ /dev/null @@ -1,438 +0,0 @@ -// !$*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 = ""; }; - 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 = ""; }; - EDB1C0BB1653283D0041897E /* en */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = en; path = en.lproj/InfoPlist.strings; sourceTree = ""; }; - EDB1C0BD1653283D0041897E /* FImmutableSortedDictionaryTests.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FImmutableSortedDictionaryTests.h; sourceTree = ""; }; - EDB1C0BE1653283D0041897E /* FImmutableSortedDictionaryTests.m */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.objc; path = FImmutableSortedDictionaryTests.m; sourceTree = ""; }; - EDB1C0CB1653286B0041897E /* FImmutableSortedDictionary.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FImmutableSortedDictionary.h; sourceTree = ""; }; - EDB1C0CC1653286B0041897E /* FImmutableSortedDictionary.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FImmutableSortedDictionary.m; sourceTree = ""; }; - EDB1C0CD1653286B0041897E /* FLLRBNode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FLLRBNode.h; sourceTree = ""; }; - EDB1C0CE1653286B0041897E /* FLLRBEmptyNode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FLLRBEmptyNode.h; sourceTree = ""; }; - EDB1C0CF1653286B0041897E /* FLLRBEmptyNode.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FLLRBEmptyNode.m; sourceTree = ""; }; - EDB1C0D01653286B0041897E /* FLLRBValueNode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FLLRBValueNode.h; sourceTree = ""; }; - EDB1C0D11653286B0041897E /* FLLRBValueNode.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FLLRBValueNode.m; sourceTree = ""; }; - EDB1C0EB165331140041897E /* FImmutableSortedDictionaryEnumerator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FImmutableSortedDictionaryEnumerator.h; sourceTree = ""; }; - EDB1C0EC165331140041897E /* FImmutableSortedDictionaryEnumerator.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FImmutableSortedDictionaryEnumerator.m; sourceTree = ""; }; -/* 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 = ""; - }; - EDB1C09E1653283D0041897E /* Products */ = { - isa = PBXGroup; - children = ( - EDB1C09D1653283D0041897E /* libFImmutableSortedDictionary.a */, - EDB1C0AE1653283D0041897E /* FImmutableSortedDictionaryTests.octest */, - ); - name = Products; - sourceTree = ""; - }; - EDB1C09F1653283D0041897E /* Frameworks */ = { - isa = PBXGroup; - children = ( - EDB1C0A01653283D0041897E /* Foundation.framework */, - EDB1C0AF1653283D0041897E /* SenTestingKit.framework */, - EDB1C0B11653283D0041897E /* UIKit.framework */, - ); - name = Frameworks; - sourceTree = ""; - }; - 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 = ""; - }; - EDB1C0A31653283D0041897E /* Supporting Files */ = { - isa = PBXGroup; - children = ( - EDB1C0A41653283D0041897E /* FImmutableSortedDictionary-Prefix.pch */, - ); - name = "Supporting Files"; - sourceTree = ""; - }; - EDB1C0B71653283D0041897E /* FImmutableSortedDictionaryTests */ = { - isa = PBXGroup; - children = ( - EDB1C0BD1653283D0041897E /* FImmutableSortedDictionaryTests.h */, - EDB1C0BE1653283D0041897E /* FImmutableSortedDictionaryTests.m */, - EDB1C0B81653283D0041897E /* Supporting Files */, - ); - path = FImmutableSortedDictionaryTests; - sourceTree = ""; - }; - EDB1C0B81653283D0041897E /* Supporting Files */ = { - isa = PBXGroup; - children = ( - EDB1C0B91653283D0041897E /* FImmutableSortedDictionaryTests-Info.plist */, - EDB1C0BA1653283D0041897E /* InfoPlist.strings */, - ); - name = "Supporting Files"; - sourceTree = ""; - }; -/* 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 = ""; - }; -/* 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 deleted file mode 100644 index 0c6c989..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h +++ /dev/null @@ -1,37 +0,0 @@ -/* - * 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 -#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 deleted file mode 100644 index f572b6b..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m +++ /dev/null @@ -1,282 +0,0 @@ -/* - * 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 deleted file mode 100644 index 88d2408..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch +++ /dev/null @@ -1,7 +0,0 @@ -// -// Prefix header for all source files of the 'FImmutableSortedDictionary' target in the 'FImmutableSortedDictionary' project -// - -#ifdef __OBJC__ - #import -#endif diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h deleted file mode 100644 index 1e7e5a3..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h +++ /dev/null @@ -1,71 +0,0 @@ -/* - * 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 - -/** - * 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 deleted file mode 100644 index 006c12d..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m +++ /dev/null @@ -1,158 +0,0 @@ -/* - * 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 deleted file mode 100644 index bb1a39c..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h +++ /dev/null @@ -1,38 +0,0 @@ -/* - * 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 - -@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 deleted file mode 100644 index 09c4164..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m +++ /dev/null @@ -1,131 +0,0 @@ -/* - * 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 deleted file mode 100644 index 3257447..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h +++ /dev/null @@ -1,43 +0,0 @@ -/* - * 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 -#import "FLLRBNode.h" - -@interface FLLRBEmptyNode : NSObject - -+ (id)emptyNode; - -- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id)aLeft withRight:(id)aRight; -- (id) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; -- (id) 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) 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 left; -@property (nonatomic, strong) id right; - -@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m deleted file mode 100644 index 5528285..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m +++ /dev/null @@ -1,87 +0,0 @@ -/* - * 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)aLeft withRight:(id)aRight { - return self; -} - -- (id) 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) 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) 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 deleted file mode 100644 index 2634494..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - * 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 - -#define RED @true -#define BLACK @false - -typedef NSNumber FLLRBColor; - -@protocol FLLRBNode - -- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id)aLeft withRight:(id)aRight; -- (id) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; -- (id) 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) 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 left; -@property (nonatomic, strong) id right; - -@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h deleted file mode 100644 index 2c64b8a..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - * 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 -#import "FLLRBNode.h" - -@interface FLLRBValueNode : NSObject - - -- (id)initWithKey:(id) key withValue:(id) value withColor:(FLLRBColor*) color withLeft:(id)left withRight:(id)right; -- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id)aLeft withRight:(id)aRight; -- (id) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; -- (id) 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) 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 left; -@property (nonatomic, strong) id right; - -@end diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m deleted file mode 100644 index fb0dc8d..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m +++ /dev/null @@ -1,245 +0,0 @@ -/* - * 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)aLeft withRight:(__unsafe_unretained id)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)aLeft withRight:(__unsafe_unretained id)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) 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) 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) 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) 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) rotateLeft { - id 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) rotateRight { - id 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) colorFlip { - id nleft = [self.left copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.left.color boolValue]] withLeft:nil withRight:nil]; - id 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) remove:(__unsafe_unretained id) aKey withComparator:(NSComparator)comparator { - id 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 deleted file mode 100644 index d7fe835..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h +++ /dev/null @@ -1,25 +0,0 @@ -/* - * 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 -#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 deleted file mode 100644 index 8eb30be..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m +++ /dev/null @@ -1,99 +0,0 @@ -/* - * 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 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 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 deleted file mode 100644 index 42887ee..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/FImmutableSortedDictionaryTests-Info.plist +++ /dev/null @@ -1,22 +0,0 @@ - - - - - CFBundleDevelopmentRegion - en - CFBundleExecutable - ${EXECUTABLE_NAME} - CFBundleIdentifier - com.firebase.mobile.ios.${PRODUCT_NAME:rfc1034identifier} - CFBundleInfoDictionaryVersion - 6.0 - CFBundlePackageType - BNDL - CFBundleShortVersionString - 1.0 - CFBundleSignature - ???? - CFBundleVersion - 1 - - diff --git a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/en.lproj/InfoPlist.strings b/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/en.lproj/InfoPlist.strings deleted file mode 100644 index 477b28f..0000000 --- a/Firebase/Database/FImmutableSortedDictionary/FImmutableSortedDictionaryTests/en.lproj/InfoPlist.strings +++ /dev/null @@ -1,2 +0,0 @@ -/* Localized versions of Info.plist keys */ - diff --git a/Firebase/Database/FTreeSortedDictionary.h b/Firebase/Database/FTreeSortedDictionary.h deleted file mode 100644 index de75988..0000000 --- a/Firebase/Database/FTreeSortedDictionary.h +++ /dev/null @@ -1,46 +0,0 @@ -/* - * 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 -#import "FImmutableSortedDictionary.h" -#import "FLLRBNode.h" - -@interface FTreeSortedDictionary : FImmutableSortedDictionary - -@property (nonatomic, copy, readonly) NSComparator comparator; -@property (nonatomic, strong, readonly) id root; - -- (id)initWithComparator:(NSComparator)aComparator; - -// Override methods to return subtype -- (FTreeSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue; -- (FTreeSortedDictionary *) removeKey:(id)aKey; - -@end diff --git a/Firebase/Database/FTreeSortedDictionary.m b/Firebase/Database/FTreeSortedDictionary.m deleted file mode 100644 index d3b00f9..0000000 --- a/Firebase/Database/FTreeSortedDictionary.m +++ /dev/null @@ -1,342 +0,0 @@ -/* - * 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 "FTreeSortedDictionary.h" -#import "FLLRBEmptyNode.h" -#import "FLLRBValueNode.h" -#import "FTreeSortedDictionaryEnumerator.h" - -typedef void (^fbt_void_nsnumber_int)(NSNumber* color, NSUInteger chunkSize); - -@interface FTreeSortedDictionary () - -@property (nonatomic, strong) id root; -@property (nonatomic, copy, readwrite) NSComparator comparator; - -@end - -@implementation FTreeSortedDictionary - -- (id)initWithComparator:(NSComparator)aComparator { - self = [super init]; - if (self) { - self.root = [FLLRBEmptyNode emptyNode]; - self.comparator = aComparator; - } - return self; -} - -- (id)initWithComparator:(NSComparator)aComparator withRoot:(__unsafe_unretained id)aRoot { - self = [super init]; - if (self) { - self.root = aRoot; - self.comparator = aComparator; - } - return self; -} - -/** - * Returns a copy of the map, with the specified key/value added or replaced. - */ -- (FTreeSortedDictionary *) insertKey:(__unsafe_unretained id)aKey withValue:(__unsafe_unretained id)aValue { - return [[FTreeSortedDictionary alloc] initWithComparator:self.comparator - withRoot:[[self.root insertKey:aKey forValue:aValue withComparator:self.comparator] - copyWith:nil - withValue:nil - withColor:BLACK - withLeft:nil - withRight:nil]]; -} - - -- (FTreeSortedDictionary *) removeKey:(__unsafe_unretained id)aKey { - // Remove is somewhat expensive even if the key doesn't exist (the tree does rebalancing and stuff). So avoid it. - if (![self contains:aKey]) { - return self; - } else { - return [[FTreeSortedDictionary alloc] - initWithComparator:self.comparator - withRoot:[[self.root remove:aKey withComparator:self.comparator] - copyWith:nil - withValue:nil - withColor:BLACK - withLeft:nil - withRight:nil]]; - } -} - -- (id) get:(__unsafe_unretained id) key { - if (key == nil) { - return nil; - } - NSComparisonResult cmp; - id node = self.root; - while(![node isEmpty]) { - cmp = self.comparator(key, node.key); - if(cmp == NSOrderedSame) { - return node.value; - } - else if (cmp == NSOrderedAscending) { - node = node.left; - } - else { - node = node.right; - } - } - return nil; -} - -- (id) getPredecessorKey:(__unsafe_unretained id) key { - NSComparisonResult cmp; - id node = self.root; - id rightParent = nil; - while(![node isEmpty]) { - cmp = self.comparator(key, node.key); - if(cmp == NSOrderedSame) { - if(![node.left isEmpty]) { - node = node.left; - while(! [node.right isEmpty]) { - node = node.right; - } - return node.key; - } - else if (rightParent != nil) { - return rightParent.key; - } - else { - return nil; - } - } - else if (cmp == NSOrderedAscending) { - node = node.left; - } - else if (cmp == NSOrderedDescending) { - rightParent = node; - node = node.right; - } - } - @throw [NSException exceptionWithName:@"NonexistentKey" reason:@"getPredecessorKey called with nonexistent key." userInfo:@{@"key": [key description] }]; -} - -- (BOOL) isEmpty { - return [self.root isEmpty]; -} - -- (int) count { - return [self.root count]; -} - -- (id) minKey { - return [self.root minKey]; -} - -- (id) maxKey { - return [self.root maxKey]; -} - -- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block -{ - [self enumerateKeysAndObjectsReverse:NO usingBlock:block]; -} - -- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block -{ - if (reverse) { - __block BOOL stop = NO; - [self.root reverseTraversal:^BOOL(id key, id value) { - block(key, value, &stop); - return stop; - }]; - } else { - __block BOOL stop = NO; - [self.root inorderTraversal:^BOOL(id key, id value) { - block(key, value, &stop); - return stop; - }]; - } -} - -- (BOOL) contains:(__unsafe_unretained id)key { - return ([self objectForKey:key] != nil); -} - -- (NSEnumerator *) keyEnumerator { - return [[FTreeSortedDictionaryEnumerator alloc] - initWithImmutableSortedDictionary:self startKey:nil isReverse:NO]; -} - -- (NSEnumerator *) keyEnumeratorFrom:(id)startKey { - return [[FTreeSortedDictionaryEnumerator alloc] - initWithImmutableSortedDictionary:self startKey:startKey isReverse:NO]; -} - -- (NSEnumerator *) reverseKeyEnumerator { - return [[FTreeSortedDictionaryEnumerator alloc] - initWithImmutableSortedDictionary:self startKey:nil isReverse:YES]; -} - -- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey { - return [[FTreeSortedDictionaryEnumerator alloc] - initWithImmutableSortedDictionary:self startKey:startKey isReverse:YES]; -} - - -#pragma mark - -#pragma mark Tree Builder - -// Code to efficiently build a RB Tree -typedef struct _base1_2list { - unsigned int bits; - unsigned short count; - unsigned short current; -} Base1_2List; - -Base1_2List *base1_2List_new(unsigned int length); -void base1_2List_free(Base1_2List* list); -unsigned int log_base2(unsigned int num); -BOOL base1_2List_next(Base1_2List* list); - -unsigned int log_base2(unsigned int num) { - return (unsigned int)(log(num) / log(2)); -} - -/** - * Works like an iterator, so it moves to the next bit. Do not call more than list->count times. - * @return whether or not the next bit is a 1 in base {1,2}. - */ -BOOL base1_2List_next(Base1_2List* list) { - BOOL result = !(list->bits & (0x1 << list->current)); - list->current--; - return result; -} - -static inline unsigned bit_mask(int x) { - return (x >= sizeof(unsigned) * CHAR_BIT) ? (unsigned) -1 : (1U << x) - 1; -} - -/** - * We represent the base{1,2} number as the combination of a binary number and a number of bits that we care about - * We iterate backwards, from most significant bit to least, to build up the llrb nodes. 0 base 2 => 1 base {1,2}, 1 base 2 => 2 base {1,2} - */ -Base1_2List *base1_2List_new(unsigned int length) { - size_t sz = sizeof(Base1_2List); - Base1_2List* list = calloc(1, sz); - // Calculate the number of bits that we care about - list->count = (unsigned short)log_base2(length + 1); - unsigned int mask = bit_mask(list->count); - list->bits = (length + 1) & mask; - list->current = list->count - 1; - return list; -} - - -void base1_2List_free(Base1_2List* list) { - free(list); -} - -+ (id) buildBalancedTree:(NSArray *)keys dictionary:(NSDictionary *)dictionary subArrayStartIndex:(NSUInteger)startIndex length:(NSUInteger)length { - length = MIN(keys.count - startIndex, length); // Bound length by the actual length of the array - if (length == 0) { - return nil; - } else if (length == 1) { - id key = keys[startIndex]; - return [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:BLACK withLeft:nil withRight:nil]; - } else { - NSUInteger middle = length / 2; - id left = [FTreeSortedDictionary buildBalancedTree:keys dictionary:dictionary subArrayStartIndex:startIndex length:middle]; - id right = [FTreeSortedDictionary buildBalancedTree:keys dictionary:dictionary subArrayStartIndex:(startIndex+middle+1) length:middle]; - id key = keys[startIndex + middle]; - return [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:BLACK withLeft:left withRight:right]; - } -} - -+ (id) rootFrom12List:(Base1_2List *)base1_2List keyList:(NSArray *)keyList dictionary:(NSDictionary *)dictionary { - __block id root = nil; - __block id node = nil; - __block NSUInteger index = keyList.count; - - fbt_void_nsnumber_int buildPennant = ^(NSNumber* color, NSUInteger chunkSize) { - NSUInteger startIndex = index - chunkSize + 1; - index -= chunkSize; - id key = keyList[index]; - id childTree = [self buildBalancedTree:keyList dictionary:dictionary subArrayStartIndex:startIndex length:(chunkSize - 1)]; - id pennant = [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:color withLeft:nil withRight:childTree]; - //attachPennant(pennant); - if (node) { - node.left = pennant; - node = pennant; - } else { - root = pennant; - node = pennant; - } - }; - - for (int i = 0; i < base1_2List->count; ++i) { - BOOL isOne = base1_2List_next(base1_2List); - NSUInteger chunkSize = (NSUInteger)pow(2.0, base1_2List->count - (i + 1)); - if (isOne) { - buildPennant(BLACK, chunkSize); - } else { - buildPennant(BLACK, chunkSize); - buildPennant(RED, chunkSize); - } - } - return root; -} - -/** - * Uses the algorithm linked here: - * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1458 - */ - -+ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator -{ - // Steps: - // 0. Sort the array - // 1. Calculate the 1-2 number - // 2. Build From 1-2 number - // 0. for each digit in 1-2 number - // 0. calculate chunk size - // 1. build 1 or 2 pennants of that size - // 2. attach pennants and update node pointer - // 1. return root - NSMutableArray *sortedKeyList = [NSMutableArray arrayWithCapacity:dictionary.count]; - [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) { - [sortedKeyList addObject:key]; - }]; - [sortedKeyList sortUsingComparator:comparator]; - - [sortedKeyList enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { - if (idx > 0) { - if (comparator(sortedKeyList[idx - 1], obj) != NSOrderedAscending) { - [NSException raise:NSInvalidArgumentException format:@"Can't create FImmutableSortedDictionary with keys with same ordering!"]; - } - } - }]; - - Base1_2List* list = base1_2List_new((unsigned int)sortedKeyList.count); - id root = [self rootFrom12List:list keyList:sortedKeyList dictionary:dictionary]; - base1_2List_free(list); - - if (root != nil) { - return [[FTreeSortedDictionary alloc] initWithComparator:comparator withRoot:root]; - } else { - return [[FTreeSortedDictionary alloc] initWithComparator:comparator]; - } -} - -@end - diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h new file mode 100644 index 0000000..3ab7476 --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.h @@ -0,0 +1,21 @@ +#import +#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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m new file mode 100644 index 0000000..15d2d8b --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FArraySortedDictionary.m @@ -0,0 +1,266 @@ +#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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary-Prefix.pch new file mode 100644 index 0000000..88d2408 --- /dev/null +++ b/Firebase/Database/third_party/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 +#endif diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h new file mode 100644 index 0000000..d6687d8 --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.h @@ -0,0 +1,54 @@ +/** + * @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 + +/** + * 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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m new file mode 100644 index 0000000..659c63b --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedDictionary.m @@ -0,0 +1,142 @@ +#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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h new file mode 100644 index 0000000..ac15c2f --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.h @@ -0,0 +1,22 @@ +#import + +@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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m new file mode 100644 index 0000000..1953af1 --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FImmutableSortedSet.m @@ -0,0 +1,115 @@ +#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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h new file mode 100644 index 0000000..833f2a5 --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.h @@ -0,0 +1,27 @@ +#import +#import "FLLRBNode.h" + +@interface FLLRBEmptyNode : NSObject + ++ (id)emptyNode; + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id)aLeft withRight:(id)aRight; +- (id) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id) 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) 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 left; +@property (nonatomic, strong) id right; + +@end diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m new file mode 100644 index 0000000..fd0c2cc --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBEmptyNode.m @@ -0,0 +1,71 @@ +#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)aLeft withRight:(id)aRight { + return self; +} + +- (id) 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) 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) 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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h new file mode 100644 index 0000000..09b234c --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBNode.h @@ -0,0 +1,29 @@ +#import + +#define RED @true +#define BLACK @false + +typedef NSNumber FLLRBColor; + +@protocol FLLRBNode + +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id)aLeft withRight:(id)aRight; +- (id) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id) 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) 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 left; +@property (nonatomic, strong) id right; + +@end diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h new file mode 100644 index 0000000..50438bb --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.h @@ -0,0 +1,29 @@ +#import +#import "FLLRBNode.h" + +@interface FLLRBValueNode : NSObject + + +- (id)initWithKey:(id) key withValue:(id) value withColor:(FLLRBColor*) color withLeft:(id)left withRight:(id)right; +- (id)copyWith:(id) aKey withValue:(id) aValue withColor:(FLLRBColor*) aColor withLeft:(id)aLeft withRight:(id)aRight; +- (id) insertKey:(id) aKey forValue:(id)aValue withComparator:(NSComparator)aComparator; +- (id) 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) 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 left; +@property (nonatomic, strong) id right; + +@end diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m new file mode 100644 index 0000000..2d8771b --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FLLRBValueNode.m @@ -0,0 +1,229 @@ +#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)aLeft withRight:(__unsafe_unretained id)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)aLeft withRight:(__unsafe_unretained id)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) 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) 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) 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) 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) rotateLeft { + id 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) rotateRight { + id 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) colorFlip { + id nleft = [self.left copyWith:nil withValue:nil withColor:[NSNumber numberWithBool:![self.left.color boolValue]] withLeft:nil withRight:nil]; + id 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) remove:(__unsafe_unretained id) aKey withComparator:(NSComparator)comparator { + id 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/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.h new file mode 100644 index 0000000..934ca8b --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.h @@ -0,0 +1,30 @@ +/** + * @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 +#import "FImmutableSortedDictionary.h" +#import "FLLRBNode.h" + +@interface FTreeSortedDictionary : FImmutableSortedDictionary + +@property (nonatomic, copy, readonly) NSComparator comparator; +@property (nonatomic, strong, readonly) id root; + +- (id)initWithComparator:(NSComparator)aComparator; + +// Override methods to return subtype +- (FTreeSortedDictionary *) insertKey:(id)aKey withValue:(id)aValue; +- (FTreeSortedDictionary *) removeKey:(id)aKey; + +@end diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.m new file mode 100644 index 0000000..e9f0683 --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionary.m @@ -0,0 +1,326 @@ +#import "FTreeSortedDictionary.h" +#import "FLLRBEmptyNode.h" +#import "FLLRBValueNode.h" +#import "FTreeSortedDictionaryEnumerator.h" + +typedef void (^fbt_void_nsnumber_int)(NSNumber* color, NSUInteger chunkSize); + +@interface FTreeSortedDictionary () + +@property (nonatomic, strong) id root; +@property (nonatomic, copy, readwrite) NSComparator comparator; + +@end + +@implementation FTreeSortedDictionary + +- (id)initWithComparator:(NSComparator)aComparator { + self = [super init]; + if (self) { + self.root = [FLLRBEmptyNode emptyNode]; + self.comparator = aComparator; + } + return self; +} + +- (id)initWithComparator:(NSComparator)aComparator withRoot:(__unsafe_unretained id)aRoot { + self = [super init]; + if (self) { + self.root = aRoot; + self.comparator = aComparator; + } + return self; +} + +/** + * Returns a copy of the map, with the specified key/value added or replaced. + */ +- (FTreeSortedDictionary *) insertKey:(__unsafe_unretained id)aKey withValue:(__unsafe_unretained id)aValue { + return [[FTreeSortedDictionary alloc] initWithComparator:self.comparator + withRoot:[[self.root insertKey:aKey forValue:aValue withComparator:self.comparator] + copyWith:nil + withValue:nil + withColor:BLACK + withLeft:nil + withRight:nil]]; +} + + +- (FTreeSortedDictionary *) removeKey:(__unsafe_unretained id)aKey { + // Remove is somewhat expensive even if the key doesn't exist (the tree does rebalancing and stuff). So avoid it. + if (![self contains:aKey]) { + return self; + } else { + return [[FTreeSortedDictionary alloc] + initWithComparator:self.comparator + withRoot:[[self.root remove:aKey withComparator:self.comparator] + copyWith:nil + withValue:nil + withColor:BLACK + withLeft:nil + withRight:nil]]; + } +} + +- (id) get:(__unsafe_unretained id) key { + if (key == nil) { + return nil; + } + NSComparisonResult cmp; + id node = self.root; + while(![node isEmpty]) { + cmp = self.comparator(key, node.key); + if(cmp == NSOrderedSame) { + return node.value; + } + else if (cmp == NSOrderedAscending) { + node = node.left; + } + else { + node = node.right; + } + } + return nil; +} + +- (id) getPredecessorKey:(__unsafe_unretained id) key { + NSComparisonResult cmp; + id node = self.root; + id rightParent = nil; + while(![node isEmpty]) { + cmp = self.comparator(key, node.key); + if(cmp == NSOrderedSame) { + if(![node.left isEmpty]) { + node = node.left; + while(! [node.right isEmpty]) { + node = node.right; + } + return node.key; + } + else if (rightParent != nil) { + return rightParent.key; + } + else { + return nil; + } + } + else if (cmp == NSOrderedAscending) { + node = node.left; + } + else if (cmp == NSOrderedDescending) { + rightParent = node; + node = node.right; + } + } + @throw [NSException exceptionWithName:@"NonexistentKey" reason:@"getPredecessorKey called with nonexistent key." userInfo:@{@"key": [key description] }]; +} + +- (BOOL) isEmpty { + return [self.root isEmpty]; +} + +- (int) count { + return [self.root count]; +} + +- (id) minKey { + return [self.root minKey]; +} + +- (id) maxKey { + return [self.root maxKey]; +} + +- (void) enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block +{ + [self enumerateKeysAndObjectsReverse:NO usingBlock:block]; +} + +- (void) enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block +{ + if (reverse) { + __block BOOL stop = NO; + [self.root reverseTraversal:^BOOL(id key, id value) { + block(key, value, &stop); + return stop; + }]; + } else { + __block BOOL stop = NO; + [self.root inorderTraversal:^BOOL(id key, id value) { + block(key, value, &stop); + return stop; + }]; + } +} + +- (BOOL) contains:(__unsafe_unretained id)key { + return ([self objectForKey:key] != nil); +} + +- (NSEnumerator *) keyEnumerator { + return [[FTreeSortedDictionaryEnumerator alloc] + initWithImmutableSortedDictionary:self startKey:nil isReverse:NO]; +} + +- (NSEnumerator *) keyEnumeratorFrom:(id)startKey { + return [[FTreeSortedDictionaryEnumerator alloc] + initWithImmutableSortedDictionary:self startKey:startKey isReverse:NO]; +} + +- (NSEnumerator *) reverseKeyEnumerator { + return [[FTreeSortedDictionaryEnumerator alloc] + initWithImmutableSortedDictionary:self startKey:nil isReverse:YES]; +} + +- (NSEnumerator *) reverseKeyEnumeratorFrom:(id)startKey { + return [[FTreeSortedDictionaryEnumerator alloc] + initWithImmutableSortedDictionary:self startKey:startKey isReverse:YES]; +} + + +#pragma mark - +#pragma mark Tree Builder + +// Code to efficiently build a RB Tree +typedef struct _base1_2list { + unsigned int bits; + unsigned short count; + unsigned short current; +} Base1_2List; + +Base1_2List *base1_2List_new(unsigned int length); +void base1_2List_free(Base1_2List* list); +unsigned int log_base2(unsigned int num); +BOOL base1_2List_next(Base1_2List* list); + +unsigned int log_base2(unsigned int num) { + return (unsigned int)(log(num) / log(2)); +} + +/** + * Works like an iterator, so it moves to the next bit. Do not call more than list->count times. + * @return whether or not the next bit is a 1 in base {1,2}. + */ +BOOL base1_2List_next(Base1_2List* list) { + BOOL result = !(list->bits & (0x1 << list->current)); + list->current--; + return result; +} + +static inline unsigned bit_mask(int x) { + return (x >= sizeof(unsigned) * CHAR_BIT) ? (unsigned) -1 : (1U << x) - 1; +} + +/** + * We represent the base{1,2} number as the combination of a binary number and a number of bits that we care about + * We iterate backwards, from most significant bit to least, to build up the llrb nodes. 0 base 2 => 1 base {1,2}, 1 base 2 => 2 base {1,2} + */ +Base1_2List *base1_2List_new(unsigned int length) { + size_t sz = sizeof(Base1_2List); + Base1_2List* list = calloc(1, sz); + // Calculate the number of bits that we care about + list->count = (unsigned short)log_base2(length + 1); + unsigned int mask = bit_mask(list->count); + list->bits = (length + 1) & mask; + list->current = list->count - 1; + return list; +} + + +void base1_2List_free(Base1_2List* list) { + free(list); +} + ++ (id) buildBalancedTree:(NSArray *)keys dictionary:(NSDictionary *)dictionary subArrayStartIndex:(NSUInteger)startIndex length:(NSUInteger)length { + length = MIN(keys.count - startIndex, length); // Bound length by the actual length of the array + if (length == 0) { + return nil; + } else if (length == 1) { + id key = keys[startIndex]; + return [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:BLACK withLeft:nil withRight:nil]; + } else { + NSUInteger middle = length / 2; + id left = [FTreeSortedDictionary buildBalancedTree:keys dictionary:dictionary subArrayStartIndex:startIndex length:middle]; + id right = [FTreeSortedDictionary buildBalancedTree:keys dictionary:dictionary subArrayStartIndex:(startIndex+middle+1) length:middle]; + id key = keys[startIndex + middle]; + return [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:BLACK withLeft:left withRight:right]; + } +} + ++ (id) rootFrom12List:(Base1_2List *)base1_2List keyList:(NSArray *)keyList dictionary:(NSDictionary *)dictionary { + __block id root = nil; + __block id node = nil; + __block NSUInteger index = keyList.count; + + fbt_void_nsnumber_int buildPennant = ^(NSNumber* color, NSUInteger chunkSize) { + NSUInteger startIndex = index - chunkSize + 1; + index -= chunkSize; + id key = keyList[index]; + id childTree = [self buildBalancedTree:keyList dictionary:dictionary subArrayStartIndex:startIndex length:(chunkSize - 1)]; + id pennant = [[FLLRBValueNode alloc] initWithKey:key withValue:dictionary[key] withColor:color withLeft:nil withRight:childTree]; + //attachPennant(pennant); + if (node) { + node.left = pennant; + node = pennant; + } else { + root = pennant; + node = pennant; + } + }; + + for (int i = 0; i < base1_2List->count; ++i) { + BOOL isOne = base1_2List_next(base1_2List); + NSUInteger chunkSize = (NSUInteger)pow(2.0, base1_2List->count - (i + 1)); + if (isOne) { + buildPennant(BLACK, chunkSize); + } else { + buildPennant(BLACK, chunkSize); + buildPennant(RED, chunkSize); + } + } + return root; +} + +/** + * Uses the algorithm linked here: + * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1458 + */ + ++ (FImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary withComparator:(NSComparator)comparator +{ + // Steps: + // 0. Sort the array + // 1. Calculate the 1-2 number + // 2. Build From 1-2 number + // 0. for each digit in 1-2 number + // 0. calculate chunk size + // 1. build 1 or 2 pennants of that size + // 2. attach pennants and update node pointer + // 1. return root + NSMutableArray *sortedKeyList = [NSMutableArray arrayWithCapacity:dictionary.count]; + [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) { + [sortedKeyList addObject:key]; + }]; + [sortedKeyList sortUsingComparator:comparator]; + + [sortedKeyList enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { + if (idx > 0) { + if (comparator(sortedKeyList[idx - 1], obj) != NSOrderedAscending) { + [NSException raise:NSInvalidArgumentException format:@"Can't create FImmutableSortedDictionary with keys with same ordering!"]; + } + } + }]; + + Base1_2List* list = base1_2List_new((unsigned int)sortedKeyList.count); + id root = [self rootFrom12List:list keyList:sortedKeyList dictionary:dictionary]; + base1_2List_free(list); + + if (root != nil) { + return [[FTreeSortedDictionary alloc] initWithComparator:comparator withRoot:root]; + } else { + return [[FTreeSortedDictionary alloc] initWithComparator:comparator]; + } +} + +@end + diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h new file mode 100644 index 0000000..d79fe8e --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.h @@ -0,0 +1,9 @@ +#import +#import "FTreeSortedDictionary.h" + +@interface FTreeSortedDictionaryEnumerator : NSEnumerator + +- (id)initWithImmutableSortedDictionary:(FTreeSortedDictionary *)aDict startKey:(id)startKey isReverse:(BOOL)reverse; +- (id)nextObject; + +@end diff --git a/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m new file mode 100644 index 0000000..2aca86e --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/FImmutableSortedDictionary/FTreeSortedDictionaryEnumerator.m @@ -0,0 +1,83 @@ +#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 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 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/third_party/FImmutableSortedDictionary/LICENSE b/Firebase/Database/third_party/FImmutableSortedDictionary/LICENSE new file mode 100644 index 0000000..b437003 --- /dev/null +++ b/Firebase/Database/third_party/FImmutableSortedDictionary/LICENSE @@ -0,0 +1,21 @@ +Copyright (c) 2012 Mads Hartmann Jensen + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. -- cgit v1.2.3