/**
* Beispiel aus
*
* - Algorithmen und Datenstrukturen für Dummies
*   - von Andreas Gogol-Döring und Thomas Letschert
*   - Verlag Wiley-VCH; Oktober 2019
*  - Kapitel 9, Mengen und ihre Speicherung
*
* @author A. Gogol-Döring, Th. Letschert
*/

import Foundation

struct AuD_09_01_SetImpArrayBased {

    enum SetError: Error {
        case full
    }

    class ArraySet: CustomStringConvertible {
        let size: Int
        var top: Int
        var a: [Int]

        init (size: Int) {
            self.size = size
            top = 0
            a = [Int](repeating: 0, count: size)
        }

        func insert(x: Int) throws {
            if (Contains(x: x)) {
                return
            }
            if (top < size) {
                a[top] = x
                top = top + 1
            } else {
                throw SetError.full
            }
        }


        func Contains(x: Int) -> Bool {
            for i in 0 ... top {
                if (a[i] == x) {
                    return true
                }
            }
            return false
        }

        func Intersection(other: ArraySet) {
            var i = 0
            while (i < top) {
                if !(other.Contains(x: a[i])) {
                    a[i] = a[top - 1]
                    a[top - 1] = 0
                    top = top - 1
                }
                i = i+1
            }
        }

        var description: String {
            "{\((a[0 ..< top]).map( { i in String(i) } ).joined(separator: ","))}"
        }

    }

    static func run() {
        let set1: ArraySet = ArraySet(size: 10)
        let set2: ArraySet = ArraySet(size: 10)

        for i in [1,2,3,4,5] {
            do {
                try set1.insert(x: i)
            } catch {
                print("Set overflow")
                return
            }
        }
        print(set1)

        for i in [1,3,5,7,9] {
            do {
                try set2.insert(x: i)
            } catch {
                print("Set overflow")
                return
            }
        }
        print(set2)

        set1.Intersection(other: set2)
        print(set1)

    }

}