[Swift] Sequence実装のサンプル(独自クラスのリスト)

SequenceTypeを実装することによって独自クラスをfor-inなどでループ処理することが可能になります。

 
SequenceTypeプロトコルは
func generate() -> GeneratorType
だけを実装すれば良いのですが、
今回のサンプルでは二分探索(バイナリサーチ)によるジェネリックスなSortedListを実装してみました。
 
 

使い方はこんな感じです

// イニシャライザで比較関数を渡す
// この例ではクロージャを使っています
let sortedList = SortedList<Int>(){
    (left:Int,right:Int)-> CompareResult in
        if (left == right) {
            return .Equal
        } else if (left > right) {
            return CompareResult.LeftLarge
        }
        else {
            return CompareResult.RightLarge
        }
    }

// 要素を追加
sortedList.append(7)
sortedList.append(5)
sortedList.append(3)

// 配列からも追加
sortedList.append([1,2,9])

// for-inループで要素を列挙
// Sequenceプロトコルが使われています
for elm in sortedList {    
	println("elm:\(elm)")
}
// 追加した要素がソートされて出力されます 1,2,3,5,7,9 


// 要素のインデックスを求める
if let idx = sortedList.indexOf(4) {
	println("found index=\(idx)")
} else {
	println("not found.")
}

 
 

以下ソース

// 要素の比較結果を示すEnum
enum CompareResult {
    case Equal,LeftLarge,RightLarge
}

// SortedListの実装
class SortedList<T>:SequenceType {
    
    // データの保存先 (実装されたらprotectedにするよ)
    var data = Array<T>()
    
    // 比較関数 (実装されたらprotectedにするよ)
    var compFunc:(left:T,right:T) -> CompareResult
    
    
    // イニシャライザ
    init(f:(left:T,right:T)-> CompareResult){
        self.compFunc = f
    }
    
    convenience init(_ initialData:Array<T>, f:(left:T,right:T)-> CompareResult){
        self.init(f:f)
        self.append(initialData)
    }
    
    // Sequence.generateの実装
    // これを実装することでfor-inで反復処理できるようになるよ
    func generate() -> IndexingGenerator<T[]> {
    	// Arrayの同機能を使って簡単に実装してますがカスタムについては後述
        return self.data.generate()
    }
    

    // ここからはArrayに実装されている機能を外にインターフェース

    subscript(index: Int) -> T {
        get {
            return data[index]
        }
        set {
            data[index] = newValue
        }
    }
    
    subscript(range: Range<Int>) -> ArraySlice<T> {
        get {
            return data[range]
        }
        set {
            data[range] = newValue
        }
    }
    
    // 要素を追加する
    // 追加されたIndexを返す
    // すでに同じ値が登録されていた場合にはNoneを返す
    func append(newElement:T) -> Int? {
        if (self.data.isEmpty){
            self.data += newElement
            return 0
        } else {
            let (hit,idx) =  _insertPos(newElement)
            if hit {
				// 上書きするのであればここで
                return .None
            } else {
                data.insert(newElement,atIndex:idx)
                return idx;
            }
        }
    }
    
    // 要素の一括登録
    func append(newElements:Array<T>) {
        let rate = self.data.isEmpty ? 1.0 : Double(newElements.count) / Double(self.data.count)
        if rate > 0.5 {
            //総量の5割を超えるレコードを追加する場合は一括でappendしてあとでソートする
            data += newElements
            _sortData();
            
        } else {
            self.data.reserveCapacity(self.data.count + newElements.count)
            for elm in newElements{
                self.append(elm)
            }
        }
    }    
    
    func append(newElements:SortedList<T>){
        self.append(newElements.array)
    }
    
    func removeAtIndex(index: Int) -> T {
        return data.removeAtIndex(index)
    }

    func removeLast() -> T {
        return data.removeLast()
    }
    
    func removeAll(keepCapacity: Bool = false) {
        data.removeAll(keepCapacity: keepCapacity)
    }
    
    // 要素を削除する
    // 戻り値:削除した要素のIndexを返す
    func remove(elm:T) -> Int? {
        let (hit,idx) =  _search(elm)
        if (hit){
            data.removeAtIndex(idx)
            return idx
        } else {
            return Optional.None
        }
    }

    var array:Array<T> {
        get{
            return self.data
        }
    }
    
    
    var count: Int {
    	get {
        	return data.count
    	}
    }
    
    var isEmpty: Bool {
    	get {
        	return data.isEmpty
    	}
    }
    
    var capacity: Int {
    	get {
        	return data.capacity
    	}
    }
    
    func reserveCapacity(minimumCapacity: Int) {
        data.reserveCapacity(minimumCapacity)
    }

    func filter(includeElement: (T) -> Bool) -> SortedList<T> {
        return SortedList(data.filter(includeElement),f:self.compFunc)
    }
    
    // (mapは比較関数も変わってしまうので実装しないことにしよう..)


    func reduce<U>(initial: U, combine: (U, T) -> U) -> U {
        return data.reduce(initial, combine)
    }
    

    // ここからは独自の機能
    
    // 指定された要素を検索してデータのインデックスを求める
    func indexOf(elm:T) -> Int? {
        let (hit,idx) =  _search(elm)
        return hit ? idx : Optional.None
    }
    
    
    // 指定したインデックスの範囲の要素をもったSortedListを返却する
    func sublist(range:Range<Int>) -> SortedList<T> {
        let subdata = data[range]
        return SortedList(Array(subdata),f:self.compFunc)
    }


 	// ここからはprivate or protectedにしたいな(実装されれば)
    
    
    // 要素の位置を検索する
    // 戻り値
    //  .0:存在したか
    //  .1:Hitした場所 or 近かった場所(前後のどちらか)
    func _search(elm:T) -> (Bool,Int) {
    
        var l = 0
        var r = self.data.count-1      
        
        while l < r {
            let m = (l + r) / 2;
            
            switch self.compFunc(left:elm,right:data[m]) {
            case .LeftLarge://右を探索
                l = m + 1
            case .RightLarge://左を探索
                r = m - 1
            case .Equal:
                return (true,m)
            }
        }
        
        if self.compFunc(left:elm,right:data[l]) == .Equal {
            return (true,l)
        } else {
            return (false,l)
        }
    }
    
    // 要素をインサートする場所を見つける
    func _insertPos(elm:T) -> (Bool,Int){
        
        let (hit,idx) =  _search(elm)
        if (hit) {
            return (hit,idx);
        }
        else {
            switch self.compFunc(left:elm,right:self.data[idx]) {
            case .LeftLarge:
                //追加する要素が大きい・・・idxの後にインサート
                return (false,idx+1)
            default:
                return (false,idx)
            }
        }
    }
    
    // 一括でソートする
    func _sortData() {
        sort(data){
            (o1 : T, o2 : T) -> Bool in
            return self.compFunc(left:o1,right:o2) == .RightLarge
        }
    }
}

C#のSortedListのように使用する場合にはジェネリックス型としてタプルを使えばよいかと。
 
 

今回行ったSequenceTypeプロトコルの実装はArrayの同機能を使って簡単に実装したのですが、カスタムしたい場合には下記のようにします。 
 
方法1. GeneratorOf を使う場合

// generateを下記のようにすればループする順序をカスタマイズできます
// ※カスタマイズしたらSortedListでは無くなってしまいますが。
func generate() -> GeneratorOf<T> {
    var index : Int = 0
    return GeneratorOf<T> {
        if (index < self.data.count){
            return self.data[index++]
        } else {
            return .None
        }
    }
}

 

方法2. 独自のGeneratorを実装する場合

// こんな感じでGeneratorを定義して
class SortedListGenerator<T> : Generator {
    let list : SortedList<T>
    var index : Int
    
    init(_ list: SortedList<T>) {
        self.list = list
        index = 0
    }
    
    mutating func next() -> T? {
        if index >= list.count { return .None }
        return list[index++]
    }
}

// 独自クラスのgenerate()でこのインスタンスを返すようにする
func generate() -> SortedListGenerator<T> {
    return SortedListGenerator(self)
}

 
 

今回のサンプルではSequenceTypeプロトコル以外の機能も実装したのでちょっと長いですが、
SequenceTypeプロトコル自体は簡単に実装できます。
独自クラスを反復処理する場合にはぜひ実装してみて下さい。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です