How to quickly search for objects of certain class or child classes in C#

Question

I want to make a collection of objects of various classes, and be able to quickly search for all instances that can be assigned to a specific class, without having to iterate the entire list. I can use a Dictionary<System.Type, List<object>>, however that won't find me all child classes/interfaces.

public class Parent {
}

public class Child : Parent {
}

public class Other {
}


public class ObjHolder {
    Dictionary<System.Type, List<object>> objs = new Dictionary<System.Type, List<object>>();

    public void AddObject(object obj) {
        if (!objs.ContainsKey(obj.GetType()) {
            objs[obj.GetType()] = new List<object>();
        }

        objs[obj.GetType()].Add(obj);
    }

    public List<object> GetObjectsOfType<T>() {
        return objs.ContainsKey(typeof(T)) ? objs[typeof(T)] : new List<object>();
    }
}

Now this will work great for the following:

ObjHolder o = new ObjHolder();
o.AddObject(new Parent());
o.AddObject(new Other());
o.GetObjectsOfType<Parent>(); // Returns only the Parent object    

But this won't work in the following case:

ObjHolder o = new ObjHolder();
o.AddObject(new Child());
o.AddObject(new Other());
o.GetObjectsOfType<Parent>(); // Returns an empty list

I want to be able to grab all objects that can be assigned to Parent, and that includes the Child object, but the code won't return it.

Any ideas how to get this done in an efficient matter?

Answer 1

So what you want is something similar to dictionary. Let us try to implement it step by step. My code is heavily commented so I will let the code do the talking. Basically all you have to do is leave bread crumbs along the way when you add your object into your object holder.

public class InheritanceInfo
{
    private class InheritanceChain
    {
        /// <summary>
        /// LinkedList which holds inheritance chain from least derived to most derived for a given Type.
        /// </summary>
        private readonly LinkedList<Type> _linkedList = new LinkedList<Type>();

        /// <summary>
        /// Creates an Inheritance chain for a given type which holds information about base types.
        /// </summary>
        /// <param name="t">Type for which inheritance chain will be created.</param>
        public InheritanceChain(Type t)
        {
            Type type = t;
            do
            {
                if (type == typeof(object))
                {
                    break;
                }
                _linkedList.AddFirst(type);
                type = type.BaseType;
            } while (true);
        }

        /// <summary>
        /// First element of LinkedList. This will be used for iteration.
        /// </summary>
        public LinkedListNode<Type> First => _linkedList.First;
    }

    /// <summary>
    /// Dictionary which holds Type vs DerivedTypes information. Basically does the all handling.
    /// </summary>
    private readonly ConcurrentDictionary<Type, SingleStepDerivedTypes> _inheritanceDictionary;

    /// <summary>
    /// InheritanceInfo class holds information about each Type's inheritance tree.
    /// Each Type holds information about one step down the inheritance tree.
    /// Example: public class C:B{}
    ///          public class B:A{}
    ///          public class A  {}
    /// Inheritance infor for class A holds info about only B because C is derived from B and
    /// it is not a direct descendant of A.
    /// </summary>
    public InheritanceInfo() {
        _inheritanceDictionary = new ConcurrentDictionary<Type, SingleStepDerivedTypes>();
    }

    /// <summary>
    /// Updates the given Type inheritance tree info.
    /// </summary>
    /// <param name="type"></param>
    public void Update(Type type) {
        var element = new InheritanceChain(type).First;
        while (element.Next != null) {
            _inheritanceDictionary.AddOrUpdate(element.Value, (_)=>AddValueFactory(element.Next.Value), (_,sdt)=>UpdateValueFactory(element.Next.Value,sdt));
            element = element.Next;
        }
    }

    /// <summary>
    /// Gets all the assignable types for the given type t.
    /// </summary>
    /// <param name="t">Type for which assignable types will be searched.</param>
    /// <returns>All the assignable types for Type t.</returns>
    public IEnumerable<Type> GetAssignables(Type t)
    {
        if(_inheritanceDictionary.TryGetValue(t ,out var derivedTypes) == false) {
            return Array.Empty<Type>();
        }
        var recursive = derivedTypes.GetTypes().SelectMany(tp=>GetAssignables(tp));
        return recursive.Concat(derivedTypes.GetTypes());
    }

    /// <summary>
    /// Add value to the dictionary
    /// </summary>
    /// <param name="t">Type to add to ConcurrentDictionary</param>
    /// <returns>SingleStepDerivedTypes which holds information about derived type t</returns>
    private static SingleStepDerivedTypes AddValueFactory(Type t) {
        var s = new SingleStepDerivedTypes();
        s.Add(t);
        return s;
    }

    /// <summary>
    /// Updates the already created SingleStepDerivedTypes object.
    /// </summary>
    /// <param name="t">Type to add</param>
    /// <param name="sdt">SingleStepDerivedTypes</param>
    /// <returns>Updated SingleStepDerivedTypes.</returns>
    private static SingleStepDerivedTypes UpdateValueFactory(Type t, SingleStepDerivedTypes sdt) {
        sdt.Add(t);
        return sdt;
    }
}



public class SingleStepDerivedTypes
{
    /// <summary>
    /// HashSet which holds information about derived Types.
    /// </summary>
    private readonly HashSet<Type> _singleStepDerivedTypes;

    /// <summary>
    /// Constructor ;)
    /// </summary>
    public SingleStepDerivedTypes() {
        _singleStepDerivedTypes = new HashSet<Type>();
    }

    /// <summary>
    /// Adds a Type to the Derived Type information.
    /// </summary>
    /// <param name="type">Type to add.</param>
    public void Add(Type type) {
        _singleStepDerivedTypes.Add(type);
    }

    /// <summary>
    /// Gets the contained information about types.
    /// </summary>
    /// <returns>IEnumerable of Types contained in this object.</returns>
    public IEnumerable<Type> GetTypes() {
        return _singleStepDerivedTypes;
    }
}

Finally let us have a look at ObjectHolder as I imagined it to be. The hard part in your case, I think you did not keep the Single Responsibility principle and tried to do everything in one go.

 public class Objectholder
 {
    /// <summary>
    /// Holds Type vs object information.
    /// Each object is seperated into its own Type.
    /// </summary>
    private readonly ConcurrentDictionary<Type, List<object>> _dict = new ConcurrentDictionary<Type, List<object>>();

    /// <summary>
    /// I already explained about this class before so here I will pass.
    /// </summary>
    private readonly InheritanceInfo inheritanceInfo = new InheritanceInfo();

    /// <summary>
    /// Adds an object to ObjectHolder.
    /// </summary>
    /// <param name="obj">Object to add</param>
    public void AddObject(object obj) {
        _dict.AddOrUpdate(obj.GetType(), t => AddValueFactory(obj), (t, li) => UpdateValueFactory(obj, li));
    }

    /// <summary>
    /// Gets Objects which are assignable to type of T.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <returns></returns>
    public IEnumerable<T> GetObjectsOf<T>() {
        var tree = inheritanceInfo.GetAssignables(typeof(T)).Concat(new[] { typeof(T) });
        return tree.SelectMany(t => _dict[t]).Cast<T>();
    }

    /// <summary>
    /// Adds a value to dictionary.
    /// </summary>
    /// <param name="obj">Object to add.</param>
    /// <returns></returns>
    private List<object> AddValueFactory(object obj)
    {
        inheritanceInfo.Update(obj.GetType());
        var l = new List<object>();
        l.Add(obj);
        return l;
    }

    /// <summary>
    /// Updates a value in dictionary.
    /// </summary>
    /// <param name="obj">Object to add.</param>
    /// <param name="li">List of objects</param>
    /// <returns></returns>
    private List<object> UpdateValueFactory(object obj, List<object> li)
    {
        inheritanceInfo.Update(obj.GetType());
        li.Add(obj);
        return li;
    }
}

// Mock classes
public class A { }
public class B : A { }
public class C : B { }

The usage of ObjectHolder is the same as the way you wanted to do.

var a = new A();
var b = new B();
var c = new C();
var objectholder = new Objectholder();
objectholder.AddObject(a);
objectholder.AddObject(b);
objectholder.AddObject(c);
// Contains A and B and C
var allA = objectholder.GetObjectsOf<A>().ToArray();

Answer 2

You can use the Type.IsAssignableFrom method to determine which classes are assignable to the generic.

Change the GetObjectsOfType<T> method to the following:

return objs.Where(x => typeof(T).IsAssignableFrom(x.Key))
           .Select(x => x.Value)
           .ToList<object>();

And also:

objs[obj.GetType()] = obj;

should be:

objs[obj.GetType()].Add(obj);

Answer 3

You need to check that if cached list contains an Assignable object from type T. Try code below that check for this relation

public List<object> GetObjectsOfType<T>()
{
   foreach (var pair in objs)
   {
      if (pair.Key == typeof(T) || typeof(T).IsAssignableFrom(pair.Key))
      {
         return pair.Value;
      }
   }

   return new List<object>();
}

I know that your code above is just to demonstrate the case, but there is a bug in AddObject function, you always save an object rather than a list, the function should be something like this:

public void AddObject(object obj)
{
    if (!objs.ContainsKey(obj.GetType()))
    {
        objs[obj.GetType()] = new List<object>() { obj };
    }
    else
    {
        objs[obj.GetType()].Add(obj);
    }
}

Answer 4

If I understand it correctly, if B inherits A and you search for A, you want to return all B objects as well.

I would do it this way: Change your existing AddObject method to add the object to multiple collections. You can use Type.BaseType property to get the base type. Do it in a loop, until you reach object class.

public void AddObject(object obj) {
    Type type;
    do {
        type = obj.GetType();
        if (!objs.ContainsKey(type) {
            objs[type] = new List<object>();
        }
        objs[type] = obj;
        if(type == typeof(object)) break;
        type = type.BaseType;
    } while(true);
}