//
//  ViewController3.swift
//  swiftT
//
//  Created by wjwdive
//  Copyright © 2020 wjwdive. All rights reserved.
//

import UIKit

struct Person {
    var name: String
    var age: Int
}
//准守 Hashable 协议， 不实现该方法会报错：Type 'Person' does not conform to protocol 'Hashable'
extension Person: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(age)
        hasher.combine(name)
    }
}

extension Person: Equatable {
    static func ==(lhs: Self, rhs: Person) -> Bool {
        return lhs.name == rhs.name
    }
}

class ViewController3: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        //创建Set
        let person: Set<Person> = [Person(name: "Jarvis", age: 18)]
        print(person)
        
        // 遍历Set
        //可以使用For-in 遍历 Set
        //因为Set 是无序的，如果需要顺序遍历Set,使用 sorted() 方法。
        
        //访问Set
       //Set.count
       //Set.isEmpty()
       
       //Set 添加元素
       //insert(_:)  添加一个元素到Set
       //update(with:) 如果已经有相等的元素，替换为新元素。如果Set 中没有，则插入
       
       //Set 移除元素
       //filter(_:) 返回一个新的Set, 新Set的元素是Set符合条件的元素
       //remove(_:) 从Set中移除一个s元素。如果元素是Set的成员就移除它，并且返回移除的值，如果集合中没有这个元素就返回你了
       //removeAll()   移除所有元素
       //removeFirst()  移除Set 的第一个元素，并不是第一个放入的元素，而是 hash后排序的第一个元素
       
        
        let course: Set = ["Math", "English", "History"]
        for c in course {
            print(c)
        }
        
        for cs in course.sorted() {
            print(cs)
        }
        
        var personsSet: Set<Person> = [Person(name: "Jarvis", age: 18), Person(name: "lisi", age: 18)]
        personsSet.update(with: Person(name:"Harvis", age: 20))
        //移除集合首部的元素
        personsSet.removeFirst()
        print("移除集合首部的元素 ", personsSet)
            
        print("filter : ", personsSet.filter({$0.age > 20}))
        
       
        //集合的计算
        //交，差（对称差集，所有属于A和B切不属于A和B的交集的元素），并，补（所有属于A但不属于B的元素）
        let a: Set<Character> = ["A", "B", "C"]
        let b: Set<Character> = ["B", "E", "F", "G"]
        print("a 交 b", a.intersection(b))
        print("a 并 b", a.union(b))
        print("a 对称差集 b", a.symmetricDifference(b))
        print("a 补 b", a.subtracting(b))

        print("a b, 有无相同元素", a.isDisjoint(with: b))
        
        //Set 的判断方法
        //isSubSet(of:) 判断是否是另一个Set或者Sequence的子集
        //isSuperSet(of:)   判断是否是另一个Set 或者 Sequence 的超集
        //isStrictSubset(of:) isStrictSuperset(of:)  判断是否是另一个Set的子集或者超集，但是又不等于另一个Set
        //isDisjoint(with:) 判断两个Set 是否有公共元素，如果没有返回True, 如果有返回false
        
        let smallSet: Set = [1, 2, 3]
        let bigSet: Set = [1, 2, 3, 4]
        print(smallSet.isSubset(of: bigSet))
        print(bigSet.isSuperset(of: smallSet))
        print(smallSet.isStrictSubset(of: bigSet))
        print(bigSet.isStrictSuperset(of: smallSet))
        print(smallSet.isDisjoint(with: bigSet))
        
        //实现自己的集合算法
        //给定一个集合，返回该集合的所有子集
        
        let sett: Set = ["A", "B", "C"]
        let subSets = getSubsets(sett)
           for subSet in subSets {
                print(subSet)
            }
           
    }
    
    //求给定集合的所有子集， 1、位法， 局限：只能计算出集合中元素个数小于计算机位数的集合的所有子集，超出计算机位数，无法用该方法
    func getSubsets<T>(_ set: Set<T>) -> Array<Set<T>> {
        let count = 1 << set.count  // 左移count位， 2的 conut 次方个子集
        let elements = Array(set)   // 包含所有set元素的array
        var subsets = [Set<T>]()    // 可变数组，存储 set的子集
        for i in 0..<count {        // 针对每个子集的值 写入到待返回数组，每次的循环次数依次是 0， 1， 10， 11， 110，111，。。。 1代表对应数组位选中，0 代表不选中
            var subset = Set<T>()   // 用来保存子集的临时变量
            for j in 0..<elements.count {   // 针对已知集合中的每个元素，右移并和1做与操作，然后和1比较，结果为1 存入临时变量 subset, 否则不存入
                if((i >> j) & 1) == 1{  // 把 i 依次移位，
                    subset.insert(elements[j])
                }
            }
            subsets.append(subset)
        }
        return subsets
    }
    
   //求给定集合的左右子集， 2、递归法 每个元素构成子集的时候都有入选子集合不入选子集两种选择
    func getSubsetsRescue<T>(set: Set<T>) -> Array<Set<T>> {
        let elements = Array(set)
        return getSubsetPart(elements, index:elements.count - 1, count:elements.count )
    }
    
    
    func getSubsetPart<T>(_ elements: Array<T>, index: Int, count: Int) -> Array<Set<T>>{
        var subsets = Array<Set<T>>()
        //只有一个元素时
        if index == 0 {
            subsets.append(Set<T>())//添加空集到子集合数组
            var subset = Set<T>()
            subset.insert(elements[0])//构建只有一个元素的集合
            subsets.append(subset)//添加一个元素集合到子集合数组
            return subsets
        }
        
        //递归调用
        subsets = getSubsetPart(elements, index: index - 1, count: count)
        //
        for subset in subsets {
            var subsetWithCurrent = Set(subset)
            subsetWithCurrent.insert(elements[index])
            subsets.append(subsetWithCurrent)
        }
        return subsets
    }

    /*
    // MARK: - Navigation

    // In a storyboard-based application, you will often want to do a little preparation before navigation
    override func prepare(for segue: UIStoryboardSegue, sender: Any?) {
        // Get the new view controller using segue.destination.
        // Pass the selected object to the new view controller.
    }
    */

}