Можно ли реализовать универсальные структуры данных? - PullRequest
Новая
       23

Можно ли реализовать универсальные структуры данных?

1 голос
/ 29 июня 2010

Я пишу некоторые из своих собственных структур данных, таких как двоичные и четырехугольные деревья и kD-деревья. Можно ли записать их таким образом, чтобы учитывалось любое количество измерений?

Что-то вроде: 

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)";

Единственное решение, которое у меня сейчас есть, это явное создание каждого измерения как его собственного класса: 

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)";

Но эта копия копирует тонну кода, который можно как-то использовать повторно.

Ответы [ 2 ]

1 голос
/ 29 июня 2010

Не совсем, но я вижу больше вариантов:

Передайте размеры в конструктор и используйте индексатор, подобный этому: 

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

Недостатком является то, что во время компиляции вы не «безопасны» (например, передаваемые размеры не проверяются).

Или создайте группу интерфейсов и используйте Reflection.Emit для создания экземпляров, которые реализуют правильный интерфейс во время выполнения: 

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";
0 голосов
/ 29 июня 2010

Вы можете использовать многомерный массив в качестве общего параметра, например: 

KDTree<string[,,,]>

Однако вы не сможете написать общий код, который проиндексирован в многомерный массив, без предоставления его вызывающей стороне: 

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

    public MDT Data { get; }
}

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

Можно также рассмотреть возможность использования зубчатых массивов , а не многомерных массивов. Затем вы можете создать универсальный класс, который определит тип данных, и в конструкторе укажите, сколько измерений использовать: 

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];
   }
}
...