How to test presence of a set of types in a collection of object of base type?

Question

I need to intersect types of incoming objects with a set of predefined ones.

The raw approach is to scan an incoming collection for each predefined type:

trait Field
class Field1 extends Field
class Field2 extends Field
class Field3 extends Field
...

class FieldManager(shownFields:Iterable[Field]) {
  var hiddenFields = new ArrayBuffer[Field]
  var found = false
  for (sf <- shownFields) {
    if (sf.isInstanceOf[Field1]) {
      found = true
      break
    }
  if (!found)
    hiddenFields+=new Field1
  for (sf <- shownFields) {
    if (sf.isInstanceOf[Field2]) {
      found = true
      break
    }
  if (!found)
    hiddenFields+=new Field2
  for (sf <- shownFields) {
    if (sf.isInstanceOf[Field3]) {
      found = true
      break
    }
  if (!found)
    hiddenFields+=new Field3
  ...
}

Wow, this is so verbose for Scala! There should be a shorter way. Like function template in C++:

class FieldManager {
  vector<Field*> hiddenFields, shownFields;
  template<class T>
  void fillHiddenType() {
    FOR_EACH(Field *, field, shownFields) {
      if (dynamic_cast<T*>(field))
        return
      hiddenFields.push_back(new T)
    }
  }
  void fillHidden() {
    fillHiddenType<Field1>();
    fillHiddenType<Field2>();
    fillHiddenType<Field3>();
    ...
  }
};

In this C++ example we mention each type to be scanned for only once.

Ok, Scala is also good for its type parameters, lets try:

def fillHiddenType[T] {
  for (sf <- shownFields)
    if (sf.isInstanceOf[T])
      return
  hiddenFields+=new T  
}

But compiler don't like creating T instance: class type required but T found. Try passing instance as argument and the next problem appears warning: abstract type T in type is unchecked since it is eliminated by erasure and isInstanceOf[] is always true! Type T is abstarcted so good, that is erased out completly even [T <: Field] doesn't allow to compare it to types from our collection shownFields.

The question is: How to test presence of an object of a given type in a collection in a compact fashion?

Update The following working code was tested on Scala 2.7.7 Both answers were useful. Thank you, guys!

//Scala 2.7.7 misses toSet members
implicit def toSet[T](i:Iterable[T]): Set[T] = {
    val rv = new HashSet[T]
    rv ++= i
    rv
}

def filterOut[T](all:Iterable[T], toRemove:Set[T]) = {
    all.filter(x => ! toRemove.contains(x))
}

def filterOutByType[T <: AnyRef](all:Iterable[T], toFilter:Set[T]):Iterable[T] = {
    def toClass(x:AnyRef) = x.getClass.asInstanceOf[Class[T]]
    val allTypes = all map toClass
    val extraTypes = toSet(filterOut(allTypes, toFilter map toClass))
    all.filter(extraTypes contains toClass(_))
}

Answer 1

It's trivial to find the first member of a collection that has a given type:

shownFields.find(_.isInstanceOf[Field1])

but that'll still return an instance of Option[Field], and not Option[Field1] - which you want for strong typing. the collect method will help here:

showFields.collect{case x : Field1 => x}

Which will return an Iterable[Field1], you can then use headOption to select the first element of the iterable as an Option[Field1], either Some[Field1] if present, or None otherwise:

showFields.collect{case x : Field1 => x}.headOption

To make it more efficient, and not calculate ALL the Field1's in the list, I'd also make it lazy, via the view method:

showFields.view.collect{case x : Field1 => x}.headOption

and to then provide a default value if it's not found, use the getOrElse method that Options provide:

showFields.view.collect{case x : Field1 => x}.headOption getOrElse (new Field1)

Update

I just read back over the question, if seems you want hiddenFields to contain a new instance of every Field subtype for which there isn't a member in showFields.

To find all types represented in an Iterable:

val shownFieldTypes = showFields.map(_.getClass).toSet

(converting it to a set forces unique values)

If you then have a set of Fields you're interested in:

val allFieldTypes = Set(classOf[Field1], classOf[Field2], ...)

You can subtract to find the missing ones:

val hiddenFieldTypes = allFieldTypes -- shownFieldTypes

The catch here is that you'd then be stuck using newInstance, and reflection isn't always desirable... So:

val protoHiddenFields = Set(new Field1, new Field2, ...)
val allFieldTypes = protoHiddenFields.map(_.getClass)
val hiddenFieldTypes = allFieldTypes -- shownFieldTypes
val hiddenFields = protohiddenFields.filter(hiddenFieldTypes contains _.getClass)

The beauty of this approach is that your prototypes can be initialised using constructor parameters, if you so desire

Answer 2

You can maintain a set of known subclasses of Field, like so:

val allFieldClasses = Set[Class[_ <: Field]](
  classOf[Field1], 
  classOf[Field2],
  classOf[Field3],
  ...)

Then creating the hidden fields is simply a matter of filtering out the shown field classes from this set and constructing instances of the remaining ones:

def createHiddenFields(shownFields: Iterable[Field]):Set[Field] = {
  val toClass = (_:Field).getClass.asInstanceOf[Class[Field]]
  (allFieldTypes -- (shownFields map toClass)) map (_.newInstance)
}

Unfortunately, you'll have to remember to keep allFieldClasses up-to-date when you add new subclasses of Field--the compiler won't warn you that your set isn't complete--but I see no way around that.