// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//

/****************       Immutable Ordered Set   ****************/
public class NSOrderedSet : NSObject, NSCopying, NSMutableCopying, NSSecureCoding, ArrayLiteralConvertible {
    internal var _storage: Set<NSObject>
    internal var _orderedStorage: [NSObject]
    
    public override func copy() -> AnyObject {
        return copyWithZone(nil)
    }
    
    public func copyWithZone(_ zone: NSZone) -> AnyObject {
        NSUnimplemented()
    }

    public override func mutableCopy() -> AnyObject {
        return mutableCopyWithZone(nil)
    }

    public func mutableCopyWithZone(_ zone: NSZone) -> AnyObject {
        NSUnimplemented()
    }
    
    public static func supportsSecureCoding() -> Bool {
        return true
    }
    
    public override func isEqual(_ object: AnyObject?) -> Bool {
        if let orderedSet = object as? NSOrderedSet {
            return isEqualToOrderedSet(orderedSet)
        } else {
            return false
        }
    }
    
    public func encodeWithCoder(_ aCoder: NSCoder) {
        if aCoder.allowsKeyedCoding {
            for idx in 0..<self.count {
                aCoder.encodeObject(self.objectAtIndex(idx), forKey:"NS.object.\(idx)")
            }
        } else {
            NSUnimplemented()
        }
    }
    
    public required convenience init?(coder aDecoder: NSCoder) {
        if aDecoder.allowsKeyedCoding {
            var idx = 0
            var objects : [AnyObject] = []
            while aDecoder.containsValueForKey(("NS.object.\(idx)")) {
                guard let object = aDecoder.decodeObjectForKey("NS.object.\(idx)") else {
                    return nil
                }
                objects.append(object)
                idx += 1
            }
            self.init(array: objects)
        } else {
            NSUnimplemented()
        }
    }
    
    public var count: Int {
        return _storage.count
    }

    public func objectAtIndex(_ idx: Int) -> AnyObject {
        return _orderedStorage[idx]
    }

    public func indexOfObject(_ object: AnyObject) -> Int {
        guard let object = object as? NSObject else {
            return NSNotFound
        }

        return _orderedStorage.index(of: object) ?? NSNotFound
    }

    public convenience override init() {
        self.init(objects: [], count: 0)
    }

    public init(objects: UnsafePointer<AnyObject?>, count cnt: Int) {
        _storage = Set<NSObject>()
        _orderedStorage = [NSObject]()

        super.init()

        _insertObjects(objects, count: cnt)
    }
    
    required public convenience init(arrayLiteral elements: AnyObject...) {
      self.init(array: elements)
    }

    public convenience init(objects elements: AnyObject...) {
      self.init(array: elements)
    }
    
    public subscript (idx: Int) -> AnyObject {
        return objectAtIndex(idx)
    }

    private func _insertObject(_ object: AnyObject) {
        guard !containsObject(object), let object = object as? NSObject else {
            return
        }

        _storage.insert(object)
        _orderedStorage.append(object)
    }

    private func _insertObjects(_ objects: UnsafePointer<AnyObject?>, count cnt: Int) {
        let buffer = UnsafeBufferPointer(start: objects, count: cnt)
        for obj in buffer {
            _insertObject(obj!)
        }
    }
}

extension NSOrderedSet : Sequence {
    /// Return a *generator* over the elements of this *sequence*.
    ///
    /// - Complexity: O(1).
    public typealias Iterator = NSEnumerator.Iterator
    public func makeIterator() -> Iterator {
        return self.objectEnumerator().makeIterator()
    }
}

extension NSOrderedSet {

    public func getObjects(_ objects: inout [AnyObject], range: NSRange) {
        for idx in range.location..<(range.location + range.length) {
            objects.append(_orderedStorage[idx])
        }
    }

    public func objectsAtIndexes(_ indexes: NSIndexSet) -> [AnyObject] {
        var entries = [AnyObject]()
        for idx in indexes {
            if idx >= count && idx < 0 {
                fatalError("\(self): Index out of bounds")
            }
            entries.append(objectAtIndex(idx))
        }
        return entries
    }

    public var firstObject: AnyObject? {
        return _orderedStorage.first
    }

    public var lastObject: AnyObject? {
        return _orderedStorage.last
    }

    public func isEqualToOrderedSet(_ otherOrderedSet: NSOrderedSet) -> Bool {
        if count != otherOrderedSet.count {
            return false
        }
        
        for idx in 0..<count {
            let obj1 = objectAtIndex(idx) as! NSObject
            let obj2 = otherOrderedSet.objectAtIndex(idx) as! NSObject
            if obj1 === obj2 {
                continue
            }
            if !obj1.isEqual(obj2) {
                return false
            }
        }
        
        return true
    }
    
    public func containsObject(_ object: AnyObject) -> Bool {
        if let object = object as? NSObject {
            return _storage.contains(object)
        }
        return false
    }

    public func intersectsOrderedSet(_ other: NSOrderedSet) -> Bool {
        if count < other.count {
            return contains { obj in other.containsObject(obj as! NSObject) }
        } else {
            return other.contains { obj in containsObject(obj) }
        }
    }

    public func intersectsSet(_ set: Set<NSObject>) -> Bool {
        if count < set.count {
            return contains { obj in set.contains(obj as! NSObject) }
        } else {
            return set.contains { obj in containsObject(obj) }
        }
    }
    
    public func isSubsetOfOrderedSet(_ other: NSOrderedSet) -> Bool {
        return !self.contains { obj in
            !other.containsObject(obj as! NSObject)
        }
    }

    public func isSubsetOfSet(_ set: Set<NSObject>) -> Bool {
        return !self.contains { obj in
            !set.contains(obj as! NSObject)
        }
    }
    
    public func objectEnumerator() -> NSEnumerator {
        if self.dynamicType === NSOrderedSet.self || self.dynamicType === NSMutableOrderedSet.self {
            return NSGeneratorEnumerator(_orderedStorage.makeIterator())
        } else {
            NSRequiresConcreteImplementation()
        }
    }

    public func reverseObjectEnumerator() -> NSEnumerator { 
        if self.dynamicType === NSOrderedSet.self || self.dynamicType === NSMutableOrderedSet.self {
            return NSGeneratorEnumerator(_orderedStorage.reversed().makeIterator())
        } else {
            NSRequiresConcreteImplementation()
        }
    }
    
    /*@NSCopying*/ 
    public var reversedOrderedSet: NSOrderedSet { 
        return NSOrderedSet(array: _orderedStorage.reversed().bridge().bridge())     
    }
    
    // These two methods return a facade object for the receiving ordered set,
    // which acts like an immutable array or set (respectively).  Note that
    // while you cannot mutate the ordered set through these facades, mutations
    // to the original ordered set will "show through" the facade and it will
    // appear to change spontaneously, since a copy of the ordered set is not
    // being made.
    public var array: [AnyObject] { NSUnimplemented() }
    public var set: Set<NSObject> { NSUnimplemented() }
    
    public func enumerateObjectsUsingBlock(_ block: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Void) { NSUnimplemented() }
    public func enumerateObjectsWithOptions(_ opts: NSEnumerationOptions, usingBlock block: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Void) { NSUnimplemented() }
    public func enumerateObjectsAtIndexes(_ s: NSIndexSet, options opts: NSEnumerationOptions, usingBlock block: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Void) { NSUnimplemented() }
    
    public func indexOfObjectPassingTest(_ predicate: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Bool) -> Int { NSUnimplemented() }
    public func indexOfObjectWithOptions(_ opts: NSEnumerationOptions, passingTest predicate: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Bool) -> Int { NSUnimplemented() }
    public func indexOfObjectAtIndexes(_ s: NSIndexSet, options opts: NSEnumerationOptions, passingTest predicate: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Bool) -> Int { NSUnimplemented() }
    
    public func indexesOfObjectsPassingTest(_ predicate: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Bool) -> NSIndexSet { NSUnimplemented() }
    public func indexesOfObjectsWithOptions(_ opts: NSEnumerationOptions, passingTest predicate: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Bool) -> NSIndexSet { NSUnimplemented() }
    public func indexesOfObjectsAtIndexes(_ s: NSIndexSet, options opts: NSEnumerationOptions, passingTest predicate: (AnyObject, Int, UnsafeMutablePointer<ObjCBool>) -> Bool) -> NSIndexSet { NSUnimplemented() }
    
    public func indexOfObject(_ object: AnyObject, inSortedRange range: NSRange, options opts: NSBinarySearchingOptions, usingComparator cmp: NSComparator) -> Int { NSUnimplemented() } // binary search
    
    public func sortedArrayUsingComparator(_ cmptr: NSComparator) -> [AnyObject] { NSUnimplemented() }
    public func sortedArrayWithOptions(_ opts: NSSortOptions, usingComparator cmptr: NSComparator) -> [AnyObject] { NSUnimplemented() }
    
    public func descriptionWithLocale(_ locale: AnyObject?) -> String { NSUnimplemented() }
    public func descriptionWithLocale(_ locale: AnyObject?, indent level: Int) -> String { NSUnimplemented() }
}

extension NSOrderedSet {
    
    public convenience init(object: AnyObject) {
        self.init(array: [object])
    }
    
    public convenience init(orderedSet set: NSOrderedSet) {
        self.init(orderedSet: set, copyItems: false)
    }

    public convenience init(orderedSet set: NSOrderedSet, copyItems flag: Bool) {
        self.init(orderedSet: set, range: NSMakeRange(0, set.count), copyItems: flag)
    }

    public convenience init(orderedSet set: NSOrderedSet, range: NSRange, copyItems flag: Bool) {
        // TODO: Use the array method here when available.
        self.init(array: set.map { $0 }, range: range, copyItems: flag)
    }

    public convenience init(array: [AnyObject]) {
        let buffer = UnsafeMutablePointer<AnyObject?>(allocatingCapacity: array.count)
        for (idx, element) in array.enumerated() {
            buffer.advanced(by: idx).initialize(with: element)
        }
        self.init(objects: buffer, count: array.count)
        buffer.deinitialize(count: array.count)
        buffer.deallocateCapacity(array.count)
    }

    public convenience init(array set: [AnyObject], copyItems flag: Bool) {
        self.init(array: set, range: NSMakeRange(0, set.count), copyItems: flag)
    }

    public convenience init(array set: [AnyObject], range: NSRange, copyItems flag: Bool) {
        var objects = set

        if let range = range.toRange() where range.count != set.count || flag {
            objects = [AnyObject]()
            for index in range.indices {
                let object = set[index] as! NSObject
                objects.append(flag ? object.copy() : object)
            }
        }

        self.init(array: objects)
    }

    public convenience init(set: Set<NSObject>) {
        self.init(set: set, copyItems: false)
    }

    public convenience init(set: Set<NSObject>, copyItems flag: Bool) {
        self.init(array: set.map { $0 as AnyObject }, copyItems: flag)
    }
}


/****************       Mutable Ordered Set     ****************/

public class NSMutableOrderedSet : NSOrderedSet {
    
    public func insertObject(_ object: AnyObject, atIndex idx: Int) {
        guard idx < count && idx >= 0 else {
            fatalError("\(self): Index out of bounds")
        }

        if containsObject(object) {
            return
        }

        if let object = object as? NSObject {
            _storage.insert(object)
            _orderedStorage.insert(object, at: idx)
        }
    }

    public func removeObjectAtIndex(_ idx: Int) {
        _storage.remove(_orderedStorage[idx])
        _orderedStorage.remove(at: idx)
    }

    public func replaceObjectAtIndex(_ idx: Int, withObject object: AnyObject) {
        guard idx < count && idx >= 0 else {
            fatalError("\(self): Index out of bounds")
        }

        if let objectToReplace = objectAtIndex(idx) as? NSObject, object = object as? NSObject {
            _orderedStorage[idx] = object
            _storage.remove(objectToReplace)
            _storage.insert(object)
        }
    }

    public init(capacity numItems: Int) {
        super.init(objects: [], count: 0)
    }

    required public convenience init(arrayLiteral elements: AnyObject...) {
        self.init(capacity: 0)

        addObjectsFromArray(elements)
    }

    public required init?(coder aDecoder: NSCoder) { NSUnimplemented() }

    private func _removeObject(_ object: AnyObject) {
      guard containsObject(object), let object = object as? NSObject else {
        return
      }

      _storage.remove(object)
      _orderedStorage.remove(at: indexOfObject(object))
    }
}

extension NSMutableOrderedSet {
    
    public func addObject(_ object: AnyObject) {
        _insertObject(object)
    }

    public func addObjects(_ objects: UnsafePointer<AnyObject?>, count: Int) {
        _insertObjects(objects, count: count)
    }

    public func addObjectsFromArray(_ array: [AnyObject]) {
        for object in array {
            _insertObject(object)
        }
    }
    
    public func exchangeObjectAtIndex(_ idx1: Int, withObjectAtIndex idx2: Int) {
        guard idx1 < count && idx1 >= 0 && idx2 < count && idx2 >= 0 else {
            fatalError("\(self): Index out of bounds")
        }

        if let object1 = objectAtIndex(idx1) as? NSObject, object2 = objectAtIndex(idx2) as? NSObject {
            _orderedStorage[idx1] = object2
            _orderedStorage[idx2] = object1
        }
    }

    public func moveObjectsAtIndexes(_ indexes: NSIndexSet, toIndex idx: Int) {
        var removedObjects = [NSObject]()
        for index in indexes.lazy.reversed() {
            if let object = objectAtIndex(index) as? NSObject {
                removedObjects.append(object)
                removeObjectAtIndex(index)
            }
        }
        for removedObject in removedObjects {
            insertObject(removedObject, atIndex: idx)
        }
    }
    
    public func insertObjects(_ objects: [AnyObject], atIndexes indexes: NSIndexSet) {
        for (indexLocation, index) in indexes.enumerated() {
            if let object = objects[indexLocation] as? NSObject {
                insertObject(object, atIndex: index)
            }
        }
    }
    
    public func setObject(_ obj: AnyObject, atIndex idx: Int) {
        if let object = obj as? NSObject {
            _storage.insert(object)
            if idx == _orderedStorage.count {
                _orderedStorage.append(object)
            } else {
                _orderedStorage[idx] = object
            }
        }
    }
    
    public func replaceObjectsInRange(_ range: NSRange, withObjects objects: UnsafePointer<AnyObject?>, count: Int) {
        if let range = range.toRange() {
            let buffer = UnsafeBufferPointer(start: objects, count: count)
            for (indexLocation, index) in range.indices.lazy.reversed().enumerated() {
                if let object = buffer[indexLocation] as? NSObject {
                    replaceObjectAtIndex(index, withObject: object)
                }
            }
        }
    }

    public func replaceObjectsAtIndexes(_ indexes: NSIndexSet, withObjects objects: [AnyObject]) {
        for (indexLocation, index) in indexes.enumerated() {
            if let object = objects[indexLocation] as? NSObject {
                replaceObjectAtIndex(index, withObject: object)
            }
        }
    }
    
    public func removeObjectsInRange(_ range: NSRange) {
        if let range = range.toRange() {
            for index in range.indices.lazy.reversed() {
                removeObjectAtIndex(index)
            }
        }
    }

    public func removeObjectsAtIndexes(_ indexes: NSIndexSet) {
        for index in indexes.lazy.reversed() {
            removeObjectAtIndex(index)
        }
    }

    public func removeAllObjects() {
        _storage.removeAll()
        _orderedStorage.removeAll()
    }
    
    public func removeObject(_ object: AnyObject) {
        if let object = object as? NSObject {
            _storage.remove(object)
            _orderedStorage.remove(at: indexOfObject(object))
        }
    }

    public func removeObjectsInArray(_ array: [AnyObject]) {
        array.forEach(removeObject)
    }
    
    public func intersectOrderedSet(_ other: NSOrderedSet) {
        for case let item as NSObject in self where !other.containsObject(item) {
            removeObject(item)
        }
    }

    public func minusOrderedSet(_ other: NSOrderedSet) {
        for item in other where containsObject(item) {
            removeObject(item)
        }
    }

    public func unionOrderedSet(_ other: NSOrderedSet) {
        other.forEach(addObject)
    }
    
    public func intersectSet(_ other: Set<NSObject>) {
        for case let item as NSObject in self where !other.contains(item) {
            removeObject(item)
        }
    }

    public func minusSet(_ other: Set<NSObject>) {
        for item in other where containsObject(item) {
            removeObject(item)
        }
    }

    public func unionSet(_ other: Set<NSObject>) {
        other.forEach(addObject)
    }
    
    public func sortUsingComparator(_ cmptr: NSComparator) {
        sortRange(NSMakeRange(0, count), options: [], usingComparator: cmptr)
    }

    public func sortWithOptions(_ opts: NSSortOptions, usingComparator cmptr: NSComparator) {
        sortRange(NSMakeRange(0, count), options: opts, usingComparator: cmptr)
    }

    public func sortRange(_ range: NSRange, options opts: NSSortOptions, usingComparator cmptr: NSComparator) {
        // The sort options are not available. We use the Array's sorting algorithm. It is not stable neither concurrent.
        guard opts.isEmpty else {
            NSUnimplemented()
        }

        let swiftRange = range.toRange()!
        _orderedStorage[swiftRange].sort { lhs, rhs in
            return cmptr(lhs, rhs) == .orderedAscending
        }
    }
}