IOS-1455 sorted set IOS-1455
authorXavier Algarra <xavier@pep-project.org>
Tue, 12 Feb 2019 15:04:30 +0100
branchIOS-1455
changeset 76160ed2059a0f71
parent 7613 ba69967473eb
child 7617 19410eed7a28
IOS-1455 sorted set
pEpUtilities/pEpUtilities/pEpUtilities.xcodeproj/project.pbxproj
pEpUtilities/pEpUtilities/pEpUtilities/Foundation/SortedSet.swift
     1.1 --- a/pEpUtilities/pEpUtilities/pEpUtilities.xcodeproj/project.pbxproj	Tue Feb 12 12:19:16 2019 +0100
     1.2 +++ b/pEpUtilities/pEpUtilities/pEpUtilities.xcodeproj/project.pbxproj	Tue Feb 12 15:04:30 2019 +0100
     1.3 @@ -40,6 +40,7 @@
     1.4  		B7A46C58220DA6190027CCB5 /* String+Email.swift in Sources */ = {isa = PBXBuildFile; fileRef = B7A46C57220DA6190027CCB5 /* String+Email.swift */; };
     1.5  		B7A46C5E220DBAF00027CCB5 /* OperationQueue+Extension.swift in Sources */ = {isa = PBXBuildFile; fileRef = B7A46C5D220DBAF00027CCB5 /* OperationQueue+Extension.swift */; };
     1.6  		B7A46C62220DCEA80027CCB5 /* NSAttributedString+Parsing.swift in Sources */ = {isa = PBXBuildFile; fileRef = B7A46C61220DCEA80027CCB5 /* NSAttributedString+Parsing.swift */; };
     1.7 +		B7DB7F4E2213098B003968DA /* SortedSet.swift in Sources */ = {isa = PBXBuildFile; fileRef = B7DB7F4D2213098A003968DA /* SortedSet.swift */; };
     1.8  /* End PBXBuildFile section */
     1.9  
    1.10  /* Begin PBXFileReference section */
    1.11 @@ -78,6 +79,7 @@
    1.12  		B7A46C57220DA6190027CCB5 /* String+Email.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = "String+Email.swift"; sourceTree = "<group>"; };
    1.13  		B7A46C5D220DBAF00027CCB5 /* OperationQueue+Extension.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = "OperationQueue+Extension.swift"; sourceTree = "<group>"; };
    1.14  		B7A46C61220DCEA80027CCB5 /* NSAttributedString+Parsing.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = "NSAttributedString+Parsing.swift"; sourceTree = "<group>"; };
    1.15 +		B7DB7F4D2213098A003968DA /* SortedSet.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = SortedSet.swift; sourceTree = "<group>"; };
    1.16  /* End PBXFileReference section */
    1.17  
    1.18  /* Begin PBXFrameworksBuildPhase section */
    1.19 @@ -94,6 +96,7 @@
    1.20  		B70A3A5222005A7600EDCE61 /* Foundation */ = {
    1.21  			isa = PBXGroup;
    1.22  			children = (
    1.23 +				B7DB7F4D2213098A003968DA /* SortedSet.swift */,
    1.24  				B7465DCB2211BEE9008A1708 /* Tuple.swift */,
    1.25  				B7A46C51220C732E0027CCB5 /* Data+Extensions.swift */,
    1.26  				B7A46C53220C73BE0027CCB5 /* String+Extensions.swift */,
    1.27 @@ -268,6 +271,7 @@
    1.28  				B7911EC221F8694100D7F66F /* UIColor+Extension.swift in Sources */,
    1.29  				B753907E2212D6B500B1FCF9 /* CGSize+Extension.swift in Sources */,
    1.30  				B75390802212DD0600B1FCF9 /* UIView+Util.swift in Sources */,
    1.31 +				B7DB7F4E2213098B003968DA /* SortedSet.swift in Sources */,
    1.32  				B7911EC621F88AF800D7F66F /* UIImage+Extension.swift in Sources */,
    1.33  				B70A3A77220091D400EDCE61 /* Logger.swift in Sources */,
    1.34  				B7A46C56220DA5EB0027CCB5 /* Substring+Email.swift in Sources */,
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/pEpUtilities/pEpUtilities/pEpUtilities/Foundation/SortedSet.swift	Tue Feb 12 15:04:30 2019 +0100
     2.3 @@ -0,0 +1,220 @@
     2.4 +//
     2.5 +//  SortedSet.swift
     2.6 +//  pEp
     2.7 +//
     2.8 +//  Created by Andreas Buff on 02.10.17.
     2.9 +//  Copyright © 2017 p≡p Security S.A. All rights reserved.
    2.10 +//
    2.11 +
    2.12 +import UIKit
    2.13 +import pEpUtilities
    2.14 +
    2.15 +/// Automatically keeps containted objects sorted to the criteria of a given sort block.
    2.16 +/// The implementation is completely trival and unperformant.
    2.17 +/// Has to be improved if this causes performance issue in the app.
    2.18 +class SortedSet<T: Equatable>: Sequence {
    2.19 +    // MARK: - Public API
    2.20 +
    2.21 +    typealias SortBlock = (_ first: T,_  second: T) -> ComparisonResult
    2.22 +
    2.23 +    public var count: Int {
    2.24 +        return set.count
    2.25 +    }
    2.26 +    
    2.27 +    init(array: [T], sortBlock block: @escaping SortBlock) {
    2.28 +        set = NSMutableOrderedSet(array: array)
    2.29 +        sortBlock = block
    2.30 +        sort()
    2.31 +    }
    2.32 +    
    2.33 +    /// Inserts an object keeping the Set sorted. Returns the index it has been inserted to.
    2.34 +    ///
    2.35 +    /// - Parameter object: object to insert
    2.36 +    /// - Returns: index the object has been inserted to
    2.37 +    @discardableResult public func insert(object: T) -> Int {
    2.38 +        objc_sync_enter(self)
    2.39 +        defer { objc_sync_exit(self) }
    2.40 +
    2.41 +        let idx = indexOfObjectIfInserted(obj: object)
    2.42 +        set.insert(object, at: idx)
    2.43 +        return idx
    2.44 +    }
    2.45 +    
    2.46 +    public func remove(object: T) {
    2.47 +        objc_sync_enter(self)
    2.48 +        defer { objc_sync_exit(self) }
    2.49 +
    2.50 +        set.remove(object)
    2.51 +    }
    2.52 +    
    2.53 +    public func removeObject(at index: Int) {
    2.54 +        objc_sync_enter(self)
    2.55 +        defer { objc_sync_exit(self) }
    2.56 +
    2.57 +        guard isValidIndex(index) else {
    2.58 +            Logger.frontendLogger.errorAndCrash("Index out of range")
    2.59 +            return
    2.60 +        }
    2.61 +        set.removeObject(at: index)
    2.62 +    }
    2.63 +    
    2.64 +    public func replaceObject(at index: Int, with object: T) {
    2.65 +        objc_sync_enter(self)
    2.66 +        defer { objc_sync_exit(self) }
    2.67 +
    2.68 +        guard isValidIndex(index) else {
    2.69 +            Logger.frontendLogger.errorAndCrash("Index out of range")
    2.70 +            return
    2.71 +        }
    2.72 +        set.replaceObject(at: index, with: object)
    2.73 +    }
    2.74 +
    2.75 +    public func object(at index: Int) -> T? {
    2.76 +        objc_sync_enter(self)
    2.77 +        defer { objc_sync_exit(self) }
    2.78 +
    2.79 +        guard isValidIndex(index) else {
    2.80 +            Logger.frontendLogger.errorAndCrash("Index out of range")
    2.81 +            return nil
    2.82 +        }
    2.83 +
    2.84 +        return set.object(at: index) as? T
    2.85 +    }
    2.86 +
    2.87 +    /**
    2.88 +     - Returns: The index of `object` or nil.
    2.89 +     */
    2.90 +    public func index(of object: T) -> Int? {
    2.91 +        let idx = indexOrNotFound(of: object)
    2.92 +        if idx != NSNotFound {
    2.93 +            return idx
    2.94 +        } else {
    2.95 +            return nil
    2.96 +        }
    2.97 +    }
    2.98 +
    2.99 +    /**
   2.100 +     - Returns: The index of `object` or NSNotFound.
   2.101 +     */
   2.102 +    public func indexOrNotFound(of object: T) -> Int {
   2.103 +        objc_sync_enter(self)
   2.104 +        defer { objc_sync_exit(self) }
   2.105 +
   2.106 +        for i in 0..<set.count {
   2.107 +            guard let testee = set.object(at: i) as? T else {
   2.108 +                Logger.frontendLogger.errorAndCrash("error casting")
   2.109 +                return NSNotFound
   2.110 +            }
   2.111 +            if testee == object {
   2.112 +                return i
   2.113 +            }
   2.114 +        }
   2.115 +        return NSNotFound
   2.116 +    }
   2.117 +    
   2.118 +    public func removeAllObjects() {
   2.119 +        objc_sync_enter(self)
   2.120 +        defer { objc_sync_exit(self) }
   2.121 +        set.removeAllObjects()
   2.122 +    }
   2.123 +
   2.124 +    // MARK: - Array Support
   2.125 +
   2.126 +    public func array() -> [T] {
   2.127 +        objc_sync_enter(self)
   2.128 +        defer { objc_sync_exit(self) }
   2.129 +
   2.130 +        if let theArray = set.array as? [T] {
   2.131 +            return theArray
   2.132 +        } else {
   2.133 +            return []
   2.134 +        }
   2.135 +    }
   2.136 +
   2.137 +    public subscript(safe index: Int) -> T? {
   2.138 +        objc_sync_enter(self)
   2.139 +        defer { objc_sync_exit(self) }
   2.140 +
   2.141 +        if index >= set.count {
   2.142 +            return nil
   2.143 +        }
   2.144 +
   2.145 +        if let obj = set.object(at: index) as? T {
   2.146 +            return obj
   2.147 +        } else {
   2.148 +            return nil
   2.149 +        }
   2.150 +    }
   2.151 +
   2.152 +    // MARK: - Sequence
   2.153 +
   2.154 +    public typealias Iterator = SortedSetIterator<T>
   2.155 +
   2.156 +    public func makeIterator() -> SortedSet<T>.SortedSetIterator<T> {
   2.157 +        return SortedSetIterator.init(elements: set.array as! [T])
   2.158 +    }
   2.159 +
   2.160 +    // MARK: - Iterator
   2.161 +
   2.162 +    public struct SortedSetIterator<T>: IteratorProtocol {
   2.163 +        public typealias Element = T
   2.164 +
   2.165 +        private let elements: [T]
   2.166 +        private var index = 0
   2.167 +        private let maxIndex: Int
   2.168 +
   2.169 +        public init(elements: [T]) {
   2.170 +            self.elements = elements
   2.171 +            maxIndex = elements.count - 1
   2.172 +        }
   2.173 +
   2.174 +        public mutating func next() -> SortedSetIterator.Element? {
   2.175 +            if index > maxIndex {
   2.176 +                return nil
   2.177 +            } else {
   2.178 +                let e = elements[index]
   2.179 +                index += 1
   2.180 +                return e
   2.181 +            }
   2.182 +        }
   2.183 +    }
   2.184 +
   2.185 +    // MARK: -
   2.186 +    
   2.187 +    private var set = NSMutableOrderedSet()
   2.188 +    private var sortBlock: SortBlock
   2.189 +
   2.190 +    private func sort()  {
   2.191 +        set.sort { (first: Any, second: Any) -> ComparisonResult in
   2.192 +            guard let firstT = first as? T,
   2.193 +                let secondT = second as? T else {
   2.194 +                    Logger.frontendLogger.errorAndCrash("Error casting.")
   2.195 +                    return .orderedSame
   2.196 +            }
   2.197 +            return sortBlock(firstT, secondT)
   2.198 +        }
   2.199 +    }
   2.200 +    
   2.201 +    private func indexOfObjectIfInserted(obj: T) -> Int {
   2.202 +        for i in 0..<set.count {
   2.203 +            guard let testee = set.object(at: i) as? T else {
   2.204 +                Logger.frontendLogger.errorAndCrash("Error casing")
   2.205 +                return 0
   2.206 +            }
   2.207 +            if set.count == 0 {
   2.208 +                //set is empty
   2.209 +                return 0
   2.210 +            }
   2.211 +            if sortBlock(obj, testee) == .orderedAscending {
   2.212 +                // following object found
   2.213 +                return i
   2.214 +            }
   2.215 +        }
   2.216 +        // we would insert as the last object
   2.217 +        return Swift.max(0, set.count)
   2.218 +    }
   2.219 +
   2.220 +    private func isValidIndex(_ idx: Int) -> Bool {
   2.221 +        return idx >= 0 && idx < set.count
   2.222 +    }
   2.223 +}