Multifield indexed list

• Download source code - 12.37 KB

Introduction

When you are writing something like a game engine, there are usually many classes there which must be organized as containers for some data. For example, you might need to store your timers, textures, sounds, and so on.

These content classes can have additional information which must be found in the game cycle as fast as possible. It is not a big problem to store your data in List<T> containers when your have a small amount of them, but it can be a problem if you have more than 10000 objects in one container. Serial search on an unsorted list is too slow.

There are non-generic SortedList or generic SortedDictionary collections in the C# toolkit, but they can be sorted only by one field at a time and the dictionary syntax is not the best for most of your classes.

I’ve tried to solve this problem with a Generic class, which contains dynamically sorted and synchronized lists for any public property of the content class.

Background

This idea comes when I thought about how it works in databases. As far as I know, any index you add to a database becomes a sorted list of the field (fields for multifield indexes). And then, you can use fast searching algorithms on these fields.

So, I tried to realize the idea in the C# world ;).

You can add as many indexes as you wish, with your own aliases, sorting order, and unique flags.

Even more - you can add two indexes with deferent aliases for the same property if you need to have ascending and descending orders at the same time.

I’m using a fast binary search algorithm, which has one limitation – it is correct when using the BinarySearch() method only for fields with the unique flag=true. This is because my class is not accepted when searching for more then one field at the same time :( (analog of “Select” command in SQL).

All indexers are sorted by the corresponding property, lists of references to instances of the content class, so you can use them for your complex searches (function GetIndexer(string alias)).

Unique flag is used for automation of adding only instances with unique values of the target property (for the designation of key fields).

Using the code

Indexed class T by property ID. This is part of the IndexedList<T> class. Supports sorting order and unique key protection.

public class ListIndex<T>
{
    private string id;
    // Name of the indexer
    public string ID
    {
      get { return id; }
    }

    private bool unique;
    // True if all values of indexed field must be unique
    public bool Unique
    {
      get { return unique; }
    }
    
    private int direction;
    // Direction of indexing. 1 - ascending, -1 - descending
    public int Direction
    {
      get { return direction; }
    }

    private string alias;
    // Alias for indexer. Is equivalent to ID if not specified in constructor
    public string Alias
    {
      get { return alias; }
    }

    private List<T> list;
    // Container for sorted data
    public List<T> List
    {
      get { return list; }
    }

    // Default constructor for preorder sorting with not unique fields
    public ListIndex(string id)
      : this(id,id,false,false)
    {
    }

    // Constructor with possibility to select indexer alias, type of order
    // and unique flag
    public ListIndex(string id,string alias,bool backDirection,bool unique)
    {
    }

    // Disposing of indexer
    public void Dispose()
    {
    }

    ~ListIndex()
    {
      Dispose();
    }
}

The main class-container for the indexed list of classes T.

public class IndexedList<T> where T:class
{
    private List<T> list;
    // Unsorted list for situations when no one indexes present 
    // (or for geting elements in the add order)
    public List<T> List
    {
      get { return list; }
    }

    // default binding flag for supported type of fields wich can be indexed
    BindingFlags bindingAttr=BindingFlags.Public | BindingFlags.Instance;

    // default constructor for creating empty list with no indexes
    public IndexedList()
    {
    }

    // Get indexer by alias indexAlias.
    // Useful for series of searching or for direct access to sorted list
    public ListIndex<T> GetIndexer(string indexAlias)
    {
    }

    // Fast searching for object with value T.v
    // in the indexer with alias indexAlias
    public T BinarySearch(string indexAlias,object v)
    {
      return BinarySearch(GetIndexer(indexAlias),v);
    }

    // Fast searching for object with value T.v in the indexer index
    public T BinarySearch(ListIndex<T> index,object v)
    {
    }

    // Looking for the position of the value T.v in the indexer index
    // (base function for searching and inserting)
    public int Search4index(ListIndex<T> index,object v,bool inserting)
    {
    }

    // Add new object obj to collection
    public bool Add(T obj)
    {
    }

    // Delete object obj from collection.
    // Delete without fast search because it is safe for not unique fields
    public void Delete(T obj)
    {
    }

    // Delete object by indexer id indexID and value of indexed field fieldValue
    // It is possible to use only for unique indexers
    public void Delete(string indexID,object fieldValue)
    {
      Delete(GetIndexer(indexID),fieldValue);
    }

    // Delete object by indexer index and value of indexed field fieldValue
    // It is possible to use only for unique indexers
    public bool Delete(ListIndex<T> index,object fieldValue)
    {
    }

    // Add default (preorder, not unique) indexer by field T.id if present
    public bool AddIndex(string id)
    {
      return AddIndex(id,id,false,false);
    }

    // Add indexer by field T.id if present,
    // with specific order and unique or not flag
    // Fail if find same fields in unique indexer
    public bool AddIndex(string id,string alias,bool backDirection,bool unique)
    {
    }

    // Delete indexer with by alias name
    public void DelIndex(string alias)
    {
    }

    // Clear collection and free resourses
    public void Dispose()
    {
    }

    ~IndexedList()
    {
      Dispose();
    }
}

Points of interest

It was interesting to build such a generic class which can be used in many different situations.

The code

There is an example in the attachment showing how to:

1. Add/delete indexes
2. Add some data
3. Get an indexer
4. Using the binary search

Performance testing

This implementation is not very fast because of using the Reflection mechanism. But in any case, it is 3-4 times faster than serial search on a 10000 object list and more than 20 times faster when searching in a list with 100,000 objects.