Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0 - Матрицы, наборы и деревья

ОГЛАВЛЕНИЕ

Матрица

public class Matrix : IVisitableCollection<double>, IMathematicalMatrix<T>
{
      // методы
      public Matrix Invert();
      public bool IsEqual(Matrix m);
      public Matrix Minus(Matrix Matrix);
      public static Matrix operator +(Matrix m1, Matrix m2);
      public static Matrix operator *(Matrix m1, Matrix m2);
      public static Matrix operator *(Matrix m1, double number);
      public static Matrix operator *(double number, Matrix m2);
      public static Matrix operator -(Matrix m1, Matrix m2);
      public Matrix Plus(Matrix Matrix);
      public Matrix Times(Matrix Matrix);
      public Matrix Times(double number);
      public Matrix Transpose();
     
      public void AddColumn();
      public void AddColumn(params double[] values);
      public void AddColumns(int columnCount);
      public void AddRow();
      public void AddRow(params double[] values);
      public void AddRows(int rowCount);
     
      public Matrix GetSubMatrix(int rowStart, int columnStart,
                                 int rowCount, int columnCount);
      public void InterchangeColumns(int firstColumn, int secondColumn);
      public void InterchangeRows(int firstRow, int secondRow);

      // ...

      // свойства
      public int Columns { get; }
      public bool IsSymmetric { get; }
      public double this[int i, int j] { get; set; }
      public int Rows { get; }

      // ...
}

Класс Matrix соответствует записи матрицы в линейной алгебре. Он реализует простые операции вроде Plus, Times, Minus и IsSymmetric.
Базовое представление класса Matrix – простой двумерный массив типа double.

[Дополнительная информация о матрицах]

Матрица объектов

public class ObjectMatrix<T> : IMatrix<T>, IVisitableCollection<T>
{   
    // методы
    public void Accept(IVisitor<T> visitor);
    public void AddColumn();
    public void AddColumn(params T[] values);
    public void AddColumns(int columnCount);
    public void AddRow();
    public void AddRow(params T[] values);
    public void AddRows(int rowCount);          
    public T[] GetColumn(int columnIndex);
    public IEnumerator<T> GetEnumerator();
    public T[] GetRow(int rowIndex);
    public ObjectMatrix<T> GetSubMatrix(int rowStart,
           int columnStart, int rowCount, int columnCount);
    public void InterchangeColumns(int firstColumn, int secondColumn);
    public void InterchangeRows(int firstRow, int secondRow);
    public void Resize(int newNumberOfRows, int newNumberOfColumns);

    // ...

    // свойства
    public int Columns { get; }
    public int Count { get; }
    public bool IsSquare { get; }
    public T this[int i, int j] { get; set; }
    public int Rows { get; }
   
    // ...   
}

Класс ObjectMatrix – простое представление 2-мерного массива объектов. Он предоставляет кое-какой функционал, отличный от стандартного непрямоугольного массива, вроде изменения размеров матрицы, получения строк и столбцов по отдельности, и перестановки строк / столбцов.

Набор Паскаля

public class PascalSet : IVisitableCollection<int>, ISet
{
      // методы
      public PascalSet Difference(PascalSet set);
      public PascalSet Intersection(PascalSet set);
      public PascalSet Inverse();
      public bool IsEqual(PascalSet set);
      public bool IsProperSubsetOf(PascalSet set);
      public bool IsProperSupersetOf(PascalSet set);
      public bool IsSubsetOf(PascalSet set);
      public bool IsSupersetOf(PascalSet set);
      public static PascalSet operator +(PascalSet s1, PascalSet s2);
      public static bool operator >(PascalSet s1, PascalSet s2);
      public static bool operator >=(PascalSet s1, PascalSet s2);
      public static bool operator <(PascalSet s1, PascalSet s2);
      public static bool operator <=(PascalSet s1, PascalSet s2);
      public static PascalSet op_LogicalNot(PascalSet set);
      public static PascalSet operator *(PascalSet s1, PascalSet s2);
      public static PascalSet operator -(PascalSet s1, PascalSet s2);
      public PascalSet Union(PascalSet set);

      // ...

      // свойства
      public bool this[int i] { get; }
      public int LowerBound { get; }
      public int UpperBound { get; }

      // ...
}

Набор Паскаля (так назван, потому что реализует набор наподобие класса Set, применяемого в Pascal) соответствует математической записи набора, где элементы в некоторой конечной совокупности могут содержаться в коллекции. Класс PascalSet реализует простые операции вроде проверки поднаборов, расширенных наборов, объединений и разностей между наборами.

[Дополнительная информация о наборах]

Очередь с приоритетом

public class PriorityQueue<T> : IVisitableCollection<T>, IQueue<T>
{
      // методы
      public void Add(T item, int priority);
      public void DecreaseItemPriority(int by);
      public T Dequeue();
      public void Enqueue(T item);
      public void Enqueue(T item, int priority);
      public T Dequeue();
      public IEnumerator<Association<int, T>> GetKeyEnumerator();
      public void IncreaseItemPriority(int by);
      public T Peek();

      // ...
}

Очередь с приоритетом является особым типом очереди, где удаленный из очереди элемент всегда является наименьшим (в неубывающей очереди с приоритетом) или наибольшим (в невозрастающей очереди с приоритетом) из элементов, содержащихся в очереди. Базовое представление реализовано с помощью неубывающей/невозрастающей кучи (в зависимости от типа очереди с приоритетом). Максимальный/минимальный элемент в куче всегда хранится в корне, а значит, впереди очереди.

Также имеются методы для увеличения приоритетов и уменьшения приоритетов на конкретные величины – это не влияет на упорядоченность элементов, так как операция воздействует на все элементы.

[Дополнительная информация об очередях с приоритетом]

Коллекция свойств только для чтения

public sealed class ReadOnlyPropertyList<T, TProperty> : 
              IList<TProperty>, IVisitableCollection<TProperty>
{
    // методы
    public ReadOnlyPropertyList(IList<T> list, PropertyDescriptor property);
    public void Accept(IVisitor<TProperty> visitor);
    public int CompareTo(object obj);
    public bool Contains(TProperty item);
    public void CopyTo(TProperty[] array, int arrayIndex);
    public IEnumerator<TProperty> GetEnumerator();
    public int IndexOf(TProperty item);   
   
    // ...
   
    // свойства
    public TProperty this[int index] { get; }
    TProperty IList<TProperty>.this[int index] { get; set; }   
}

Класс ReadOnlyPropertyCollection является простой служебной коллекцией, реализующей IList<TProperty>. Он предоставляет свойство типа в списке как другой список. Например, List<Person> может предоставляться как List<string> (список имен) посредством ReadOnlyPropertyCollection, путём использования оригинального списка, не делая копию того списка.

Красно-черное дерево

public class RedBlackTree<TKey, TValue> : IVisitableDictionary<TKey, TValue>
{
    // методы
    public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
    public void Add(KeyValuePair<TKey, TValue> item);
    public void Add(TKey key, TValue value);   
    public bool Contains(KeyValuePair<TKey, TValue> item);
    public bool ContainsKey(TKey key);   
    public void DepthFirstTraversal(
           OrderedVisitor<KeyValuePair<TKey, TValue>> visitor);   
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
    public bool Remove(TKey key);
    public bool TryGetValue(TKey key, out TValue value);

    // ...

    // свойства
    public IComparer<TKey> Comparer { get; }
    public TValue this[TKey key] { get; set; }
    public ICollection<TKey> Keys { get; }
    public TKey Max { get; }
    public TKey Min { get; }
    public ICollection<TValue> Values { get; }
   
    // ...
}


Красно-черное дерево является самобалансирующимся двоичным деревом поиска. Это значит, что длина путей от корневого узла до дочерних узлов контролируется – нельзя получить крайне длинный путь к одному узлу и короткие пути к другим (что снижает производительность поиска).

Красно-черное дерево реализовано в NGenerics с реализацией интерфейса IDictionary<TKey, TValue>.

Алгоритмы вставки и удаления были адаптированы из алгоритмов Джульена Уолкера (вечно запутанный).

[Дополнительная информация о красно-черных деревьях]