views:

53

answers:

2

I'm writing some of my own data structures, such as binary and quad trees, and kD-trees. Is it possible to write them in such a way that allows for any number of dimensions?

Something like:

KDTree<2, string> twoDTree = new KDTree<2, string>();
twoDTree[3,4] = "X,Y = (3,4)";

KDTree<4, string> fourDTree = new KDTree<4, string>();
fourDTree[0,1,2,3] = "x1,x2,x3,x4 = (0,1,2,3)";

The only solution I have now is to explicitly create each dimension as it's own class:

TwoDTree<string> twoDTree = new TwoDTree<string>();
twoDTree[3,4] = "X,Y = (3,4)";

FourDTree<string> fourDTree = new FourDTree<string>();
fourDTree[0,1,2,3] = "x1,x2,x3,x4 = (0,1,2,3)";

But this copy-pastes a ton of code, which should be able to be reused somehow.

A: 

You can use a multidimensional array as a generic parameter, like so:

KDTree<string[,,,]>

However, you would not be able to write generic code that indexed into the multidimensional array, without exposing it to the caller:

public class KDTree<MDT> {
    // ... 

    public MDT Data { get; }
}

var twoTree = new KDTree<string[,]>();
twoTree.Data[3,4] = "X,Y = (3,4)";

You could also consider using jagged arrays rather than multidimensional arrays. You could then create a generic class that defined the type of the data, and in the constructor specify how many dimensions to use:

public class KDTree<T> {
   private readonly T[][] m_Data;

   public KDTree( int rows, int columns )  {
      m_Data = new T[rows][];
      for( int r = 0; r < rows; r++ )
        m_Data[r] = new T[columns];
   }
}
LBushkin
+1  A: 

Not really, but I see more options:

Pass the dimensions into the constructor and use a indexer like this:

public string this[params int[] indexes] {
  get {
    // return the data fr the index
  }
}

This has the downside of not being "typesafe" at compile time (e.g. the dimensions passed in will not be checked).

Or create a bunch of interfaces and use Reflection.Emit to create instances which implement the correct interface at runtime:

public interface IMultiDimensional<T> {
  int Dimensions {
    get;
  }

  int Rank(int dimension);
}

public interface I1Dimensional<T>: IMultiDimensional<T> {
  T this[int index] {
    get;
    set;
  }
}

public interface I2Dimensional<T>: IMultiDimensional<T> {
  T this[int index1, int index2] {
    get;
    set;
  }
}

public interface I3Dimensional<T>: IMultiDimensional<T> {
  T this[int index1, int index2, int index3] {
    get;
    set;
  }
}

public interface I4Dimensional<T>: IMultiDimensional<T> {
  T this[int index1, int index2, int index3, int index4] {
    get;
    set;
  }
}

public static TDimensional CreateMulti<TDimensional, TType>() where T: IMultiDimensional<TType> {
  // emit a class with Reflection.Emit here that implements the interface
}

I4Dimensional<string> four = CreateMulti<I4Dimensional<string>, string>();
four[1,2,3,4] = "abc";
Lucero