Protocol extensions with generics

I guess there's a better way, but:

import Darwin

protocol WeightedItemType {
    typealias Item
    var weight: Int { get }
    var item: Item { get }
}

struct WeightedItem<T>: WeightedItemType {
    typealias Item = T
    let item: Item
    let weight: Int
}

infix operator £ { precedence 0 associativity left } // Pound -> weight ... : /
func £ <T>(lhs: T, rhs: Int) -> WeightedItem<T> {
    return WeightedItem(item: lhs, weight: rhs)
}

extension SequenceType where Generator.Element: WeightedItemType {
    var weightedRandomElement: Generator.Element.Item! {
        var selectedItem: Generator.Element.Item?
        var selectedWeight = 0
        for e in self {
            if Int(arc4random_uniform(UInt32(selectedWeight + e.weight))) < e.weight {
                selectedItem = e.item
            }
            selectedWeight += e.weight
        }
        return selectedItem
    }
}

let someSequence = ["foo" £ 70, "bar" £ 20, "baz" £ 10]

for _ in 0 ..< 10 { print(someSequence.weightedRandomElement) }

Did you try Beta 2? I'm not sure if the change “Extensions to generic types can now be further constrained by placing additional protocol requirements on the type parameters of the generic type. (21142043)” applies here.

I was using beta 2, and couldn't see how that change would make anything nicer possible and couldn't find any way other than the above, but that could of course just be me.

Ooh, clever solution. Only downside I see is that it doesn't work with dictionaries (at least not directly).

Same here. I tried in beta 1 and beta 2.

I was curious if it made any difference, since the error for the first case is “Use of undeclared type 'T'”, and that Beta 2 change allows you to refer to T in that context, at least to add protocol requirements.

Edit: Oh, right. That's not your issue here because you're trying to make a new generic type, not refer to one on an already generic type. Seems reasonable and is probably worth a bug report/enhancement request.

Speaking of which, one might wonder why this shouldn't be possible:

extension Dictionary where Value == Int { // Error: Same-type requirement makes generic parameter 'Value' non-generic.
    var weightedRandomElement: Key! {
        var selectedItem: Key?
        var selectedWeight: Value = 0
        // ...
        return selectedItem
    }
}

I mean, this would be an extension applying only to some specific Dictionaries. We are using the new ability to further constrain extensions to generic types (as mentioned in the beta 2 release notes). As far as I can see, this is something that would be useful and should be allowed. Or am i missing some existing way in which you can make an extension to Dictionaries with Value == Int (and Key: Hashable)?

So in order to make a version that is an extension to Dictionary, I had to do this:

protocol ItemWeightType: Comparable, IntegerLiteralConvertible, IntegerArithmeticType {
    init(_: UInt32)
}

extension Int: ItemWeightType {}

extension Dictionary where Value: ItemWeightType {
    var weightedRandomElement: Key! {
        var selectedItem: Key?
        var selectedWeight: Value = 0
        for (item, weight) in self {
            let r = Value(arc4random_uniform(UInt32((selectedWeight + weight).toIntMax())))
            if r < weight { selectedItem = item }
            selectedWeight += weight
        }
        return selectedItem
    }
}

let someDict = ["foo": 70, "bar": 20, "baz": 10]
for _ in 0 ..< 10 { print(someDict.weightedRandomElement) }

This is nice! I'll also file a radar so that they might fix it, but this is a pretty good workaround.