Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0
ОГЛАВЛЕНИЕ
С момента первого выпуска .NET было желание написать собственную коллекцию структур данных и алгоритмов. Это попытка предоставить многоразовую, обобщенную коллекцию структур данных и алгоритмов для применения в .NET 2.0 и выше.
• Скачать исходники - 265.8 Кб (с тестами NUnit)
• Скачать двоичные файлы - 40.5 Кб
• Домашняя страница проекта NGenerics (CodePlex)
Статья не дает все подробности и полные описания внутреннего устройства этих коллекций и алгоритмов - наоборот, она дает ссылки на имеющиеся в интернете ресурсы (нет смысла пытаться обойти Википедию) и сообщает любопытные особенности данной конкретной реализации.
Справка
Каркас .NET вырос в очень богатый каркас. Он предоставляет множество продуманных интерфейсов и классов, но пренебрегает множеством структур данных и алгоритмов, имеющих важное значение в области информатики. Данная библиотека старается предоставить этот отсутствующий функционал и расширить каркас .NET.
Обзор
Сейчас реализованы следующие структуры данных и алгоритмы:
|
Новые структуры данных |
Расширенные структуры данных |
Алгоритмы сортировки |
Алгоритмы на графах |
|
Association<TKey, TValue> |
VisitableHashTable<TKey, TValue> |
пузырьковая сортировка |
алгоритм поиска кратчайшего пути одиночного источника Дейкстры |
|
Bag<T> |
VisitableLinkedList<T> |
блочная сортировка |
алгоритм минимального связывающего дерева Прима |
|
BinaryTree<T> |
VisitableList<T> |
коктейльная сортировка |
|
|
BinarySearchTree<TKey, TValue> |
VisitableQueue<T> |
сортировка гребнем |
Математические алгоритмы |
|
Deque<T> |
VisitableStack<T> |
гномья сортировка |
генерация чисел Фибоначчи. |
|
GeneralTree<T> |
древовидная сортировка |
алгоритм Евклида |
|
|
Graph<T> |
сортировка вставкой |
||
|
Heap<T> |
сортировка слиянием |
||
|
Matrix |
сортировка переносом четный- нечетный |
||
|
PascalSet |
быстрая сортировка |
||
|
PriorityQueue<T> |
сортировка выбором |
||
|
SkipList<TKey, TValue> |
сортировка перемешиванием |
||
|
SortedList<T> |
сортировка методом Шелла |
||
|
SortedList<T> |
сортировка методом Шелла |
||
|
RedBlackTree<T> |
|||
|
ReadOnlyPropertyCollection <T, TProperty> |
|||
|
ObjectMatrix<T> |
|||
|
HashList<TKey, TValue> |
Использование кода и структуры данных
Интерфейс IVisitableCollection
public interface IVisitable<T>
{
// методы
void Accept(IVisitor<T> visitor);
}
public interface IVisitableCollection<T> :
ICollection<T>, IEnumerable<T>,
IEnumerable, IComparable, IVisitable<T>
{
// свойства
bool IsEmpty { get; }
bool IsFixedSize { get; }
bool IsFull { get; }
}
Шаблон посетителя является, пожалуй, одним из наиболее используемых (и переоцененным) шаблонов в информатике. Интерфейс IVisitableCollection<T> предоставляет интерфейс для любой коллекции, чтобы принимать посетителей – тем самым изолируя действие, выполняемое над объектами, от реализации конкретной структуры данных. Дополнительную информацию о посетителях смотрите в интерфейсе IVisitor<T>.
При вызове метода Accept коллекция перечисляет все содержащиеся в ней объекты и вызывает метод Visit посетителя для каждого из них. IsEmpty и IsFull возвращают логическое значение, указывающее, пуст или полон текущий экземпляр, соответственно. Метод IsFull применяется только к коллекциям фиксированного размера и указывает, что коллекция не растет динамически по мере добавления элементов к ней.
Другой интерфейс по имени IVisitableDictionary<T> представляет коллекции на базе словарей, также реализуя интерфейс IVisitable<T>.
Ассоциация
public class Association<TKey, TValue>
{
// методы
public Association(TKey key, TValue value);
public KeyValuePair<TKey, TValue> ToKeyValuePair();
// свойства
public TKey Key { get; set; }
public TValue Value { get; set; }
}
Класс, копирующий функционал стандартного KeyValuePair<TKey, TValue>, но с добавленными устанавливающими методами для свойств Key и Value. Класс Association применяется в основном в структуре данных SortedList, где надо поддерживать отношение ключ-значение между приоритетом и значением элемента.
Мультимножество
public class Bag<T> : IVisitableCollection<T>, IBag<T>
{
// методы
public void Accept(IVisitor<KeyValuePair<T, int>> visitor);
public void Add(T item, int amount);
public Bag<T> Difference(Bag<T> bag);
public IEnumerator<KeyValuePair<T, int>> GetCountEnumerator();
public IEnumerator<T> GetEnumerator();
public Bag<T> Intersection(Bag<T> bag);
public bool IsEqual(Bag<T> bag);
public static Bag<T> operator +(Bag<T> b1, Bag<T> b2);
public static Bag<T> operator *(Bag<T> b1, Bag<T> b2);
public static Bag<T> operator -(Bag<T> b1, Bag<T> b2);
public bool Remove(T item, int max);
public Bag<T> Union(Bag<T> bag);
// ...
// свойства
public int this[T item] { get; }
// ....
}
Мультимножество является структурой данных, содержащей любое число элементов. Оно отличается от набора тем, что позволяет содержаться в коллекции множественным вхождениям элементов, следовательно, более приспособлено к подсчету элементов. Содержащаяся в этой библиотеке структура данных мультимножество реализована с помощью структуры данных Dictionary<T, int>, хранящей ссылку на число элементов, содержащееся в мультимножестве.
Класс Bag реализован с помощью объекта Dictionary<KeyType, int>, где объект хешируется с помощью счетчика, представляющего количество конкретных элементов, содержащихся в мультимножестве. Реализованы стандартные операции:
• Пересечение – возвращает мультимножество, содержащее элементы, находящиеся в обоих мультимножествах.
• Объединение - возвращает мультимножество со всеми элементами в обоих мультимножествах.
• Разность - "вычесть" одно мультимножество из другого. Эта операция вычитает количество элементов, содержащихся в другом мультимножестве, из задействованного мультимножества.
Двоичное дерево
public class BinaryTree<T> : IVisitableCollection<T>, ITree<T>
{
// методы
public void Add(BinaryTree<T> subtree);
public virtual void breadthFirstTraversal(IVisitor<T> visitor);
public virtual void
DepthFirstTraversal(OrderedVisitor<T> orderedVisitor);
public BinaryTree<T> GetChild(int index);
public bool Remove(BinaryTree<T> child);
public virtual void RemoveLeft();
public virtual void RemoveRight();
// ...
// свойства
public virtual T Data { get; set; }
public int Degree { get; }
public virtual int Height { get; }
public virtual bool IsLeafNode { get; }
public BinaryTree<T> this[int i] { get; }
public virtual BinaryTree<T> Left { get; set; }
public virtual BinaryTree<T> Right { get; set; }
// ...
}
Двоичное дерево является особым видом дерева, где каждый узел в дереве имеет максимум два дочерних узла. Класс BinaryTree<T> содержит указатели на максимум два дочерних узла. Методы BreadthFirstTraversal и DepthFirstTraversal предоставляют указанный доступ конкретным посетителям. Обход в глубину производится тремя способами: симметричный, в обратном порядке или в прямом порядке, где симметричный применим только к двоичным деревьям.
Свойство Height работает путем рекурсивного подсчета количества уровней в этом двоичном дереве и ниже. Так как каждый потомок BinaryTree сам является BinaryTree, каждый потомок имеет свою собственную высоту.
[Дополнительная информация о двоичных деревьях]
Двоичное дерево поиска
public class BinarySearchTree<TKey, TValue> :
IVisitableDictionary<TKey, TValue>,
IDictionary<TKey, TValue>,
IVisitableCollection<KeyValuePair<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 int CompareTo(object obj);
public bool Contains(KeyValuePair<TKey, TValue> item);
public bool ContainsKey(TKey key);
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex);
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
public IEnumerator<KeyValuePair<TKey, TValue>> GetSortedEnumerator();
public bool Remove(KeyValuePair<TKey, TValue> item);
public bool Remove(TKey key);
public bool TryGetValue(TKey key, out TValue value);
// ...
// свойства
public IComparer<TKey> Comparer { get; }
public int Count { get; }
public bool IsEmpty { get; }
public bool IsFixedSize { get; }
public bool IsFull { get; }
public bool IsReadOnly { get; }
public TValue this[TKey key] { get; set; }
public ICollection<TKey> Keys { get; }
public KeyValuePair<TKey, TValue> Max { get; }
public KeyValuePair<TKey, TValue> Min { get; }
public ICollection<TValue> Values { get; }
// ...
}
Двоичное дерево поиска является структурой поиска данных, имеющей форму двоичного дерева. Его внутреннее устройство простое: элементы, меньшие, чем родительский узел, помещаются в левое поддерево, а элементы, которые больше, помещаются в правое поддерево. Это обеспечивает быстрый поиск элементов путем исключения большего числа элементов на каждом уровне. Но один из его худших случаев – добавление элементов в последовательном порядке - O(n) сравнений требуется в худшем случае. Однако из-за своей простоты это подходящая структура поиска данных для рандомизированных входных данных. Если рандомизацию данных нельзя обеспечить, следует использовать сбалансированное дерево поиска (например, красно-черное дерево).
[Дополнительная информация о двоичных деревьях поиска]
Дек
public sealed class Deque<T> : IVisitableCollection<T>, IDeque<T>
{
// методы
public T DequeueHead();
public T DequeueTail();
public void EnqueueHead(T obj);
public void EnqueueTail(T obj);
// ...
// свойства
public T Head { get; }
public T Tail { get; }
// ...
}
Структура данных дек (или двусторонняя очередь) похожа на структуру данных очередь, за исключением того, что она может поставить в очередь или убрать из очереди в голове или хвосте текущей очереди. Дек реализован как связанный список, обеспечивающий легкий доступ к началу и концу списка.
[Дополнительная информация о деках]
Общее дерево
public class GeneralTree<T> : IVisitableCollection<T>, ITree<T>
{
// методы
public void Add(GeneralTree<T> child);
public void breadthFirstTraversal(Visitor<T> visitor);
public void DepthFirstTraversal(OrderedVisitor<T> orderedVisitor);
public GeneralTree<T> GetChild(int index);
public bool Remove(GeneralTree<T> child);
public void RemoveAt(int index);
public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter);
public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter,
IComparer<GeneralTree<T>> comparer);
public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter,
Comparison<GeneralTree<T>> comparison);
// ...
// свойства
public T Data { get; }
public int Degree { get; }
public int Height { get; }
public virtual bool IsLeafNode { get; }
public GeneralTree<T> this[int i] { get; }
public GeneralTree<T>[] Ancestors { get; }
public GeneralTree<T> Parent { get; }
// ...
}
Общее дерево – самый обобщенный вид структуры данных дерево. Оно разрешает любое число дочерних узлов у данного узла (в том числе ноль узлов, что делает его листовым узлом). Класс GeneralTree<T>, как класс BinaryTree<T>, предусматривает обход в ширину и обход в глубину для посетителей.
GeneralTree реализовано с помощью списка для слежения за потомками (тоже типа GeneralTree). Свойство Height работает аналогично свойству Height двоичного дерева – оно рекурсивно считает число уровней вниз по дереву.
[Дополнительная информация о деревьях]
Граф
Структура данных граф состоит из трех частей:
• Класс Vertex<T>, представляющий узел в графе.
• Класс Edge<T>, образующий связь между двумя вершинами.
• Класс Graph<T>, являющийся коллекцией ребер и вершин.
Vertex<T>
public class Vertex<T>
{
// методы
public Edge<T> GetEmanatingEdgeTo(Vertex<T> toVertex);
public Edge<T> GetIncidentEdgeWith(Vertex<T> toVertex);
public bool HasEmanatingEdgeTo(Vertex<T> toVertex);
public bool HasIncidentEdgeWith(Vertex<T> fromVertex);
// ...
// свойства
public T Data { get; set; }
public int Degree { get; }
public IEnumerator<Edge<T>> EmanatingEdges { get; }
public IEnumerator<Edge<T>> IncidentEdges { get; }
public int IncidentEdgesCount { get; }
// ...
}
Класс Vertex<T> представляет узел в графе. Он хранит список ребер (добавленный графом), выходящих из него (направленных к другой вершине), и смежные ребра. К этим спискам можно обратиться с помощью свойств EmanatingEdges и IncidentEdges. Элемент данных связан с вершиной, чтобы отличить ее от других вершин.
Edge<T>
public class Edge<T>
{
// методы
public Vertex<T> GetPartnerVertex(Vertex<T> vertex);
// ...
// свойства
public Vertex<T> FromVertex { get; }
public bool IsDirected { get; }
public Vertex<T> ToVertex { get; }
public double Weight { get; }
// ...
}
Класс Edge<T> представляет ребро между двумя вершинами в графе, которая бывает направленной или ненаправленной, в зависимости от типа графа. Ребра бывают взвешенными, т. е. ребру можно присвоить значение, представляющее его полезную нагрузку или расстояние между двумя вершинами. Метод GetPartnerVertex, если дана вершина, содержащаяся в ребре, возвращает другую вершину в отношении.
Graph<T>
public class Graph<T> : IVisitableCollection<T>
{
// методы
public void AddEdge(Edge<T> edge);
public Edge<T> AddEdge(Vertex<T> from, Vertex<T> to);
public Edge<T> AddEdge(Vertex<T> from, Vertex<T> to, double weight);
public void AddVertex(Vertex<T> vertex);
public Vertex<T> AddVertex(T item);
public void BreadthFirstTraversal(IVisitor<Vertex<T>> visitor,
Vertex<T> startVertex);
public bool ContainsEdge(Edge<T> edge);
public bool ContainsEdge(Vertex<T> from, Vertex<T> to);
public bool ContainsEdge(T fromValue, T toValue);
public bool ContainsVertex(Vertex<T> vertex);
public bool ContainsVertex(T item);
public void DepthFirstTraversal(OrderedVisitor<Vertex<T>> visitor,
Vertex<T> startVertex);
public Edge<T> GetEdge(Vertex<T> from, Vertex<T> to);
public bool RemoveEdge(Edge<T> edge);
public bool RemoveEdge(Vertex<T> from, Vertex<T> to);
public bool RemoveVertex(Vertex<T> vertex);
public bool RemoveVertex(T item);
// ...
// свойства
public int EdgeCount { get; }
public IEnumerator<Edge<T>> Edges { get; }
public bool IsDirected { get; }
public bool IsStronglyConnected { get; }
public bool IsWeaklyConnected { get; }
public int VertexCount { get; }
public IEnumerator<Vertex<T>> Vertices { get; }
// ...
}
Класс Graph<T> является контейнером вершин и ребер. Граф выполняет все операции добавления и удаления. Реализованы стандартные операции добавления, удаления и получения. Также реализованы DepthFirstTraversal и BreadthFirstTraversal аналогично структурам данных дерево, за исключением того что они требуют начальную вершину, так как граф лишен корня.
IsStronglyConnected и IsWeaklyConnected проверяют на возможность соединения в графе. Слабая связанность гарантирует наличие ненаправленного ребра между каждой вершиной в графе, то есть все вершины достижимы из любой другой вершины. Для направленного графа алгоритм представляет направленные ребра как ненаправленные ребра. Проверка, является ли граф сильно связанным, влечет за собой проверку того, что каждая вершина достижима из любой другой вершины и доступна только в направленных графах.
[Дополнительная информация о графах]
Куча
public class Heap<T> : IVisitableCollection<T>, IHeap<T>
{
// методы
public override void Add(T item);
public T RemoveSmallestItem();
// ...
// свойства}
public T SmallestItem { get; }
// ...
}
Структура данных куча является древовидной структурой с особым свойством: наименьший элемент (неубывающая куча) или наибольший элемент (невозрастающая куча) содержится в корне дерева. Куча, реализованная в этой библиотеке, может быть неубывающей кучей или невозрастающей кучей, что устанавливается в конструкторе. Для невозрастающей кучи используемый экземпляр IComparer<T> обертывается в экземпляр ReverseComparer<IComparer<T>>, тем самым инвертируя решение сравнения и сортируя в обратном порядке.
[Дополнительная информация о кучах]
Матрица
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>.
Алгоритмы вставки и удаления были адаптированы из алгоритмов Джульена Уолкера (вечно запутанный).
[Дополнительная информация о красно-черных деревьях]
Список хешей
public sealed class HashList<TKey, TValue> :
VisitableHashtable<TKey, IList<TValue>>
{
// методы
public void Add(TKey key, ICollection<TValue> values);
public void Add(TKey key, TValue value);
public IEnumerator<TValue> GetValueEnumerator();
public bool Remove(TValue item);
public bool Remove(TKey key, TValue item);
public void RemoveAll(TValue item);
// свойства
public int KeyCount { get; }
public int ValueCount { get; }
}
HashList (или мультисловарь) является HashTable, способной хранить множество значений для конкретного ключа. Он основан на стандартном классе словаря и выполняет те же функции, что и класс Dictionary<TKey, IList<TValue>>, с более приятным синтаксисом.
Отсортированный список
public class SortedList<T> : IVisitableCollection<T>, IList<T>
{
// методы
public override void Accept(IVisitor<T> visitor);
public override void Add(T item);
public override void Clear();
public override int CompareTo(object obj);
public override bool Contains(T item);
public override void CopyTo(T[] array, int arrayIndex);
public override IEnumerator<T> GetEnumerator();
public override bool Remove(T item);
public void RemoveAt(int index);
// ...
// свойства
public IComparer<T> Comparer { get; }
public T this[int i] { get; }
// ...
}
Класс SortedList<T> выполняет ту же функцию, что и стандартный класс SortedList<TKey, TValue> в каркасе .NET, не считая того что он убирает две тонкости, обнаруженные при работе с тем классом:
• Повторяющиеся элементы могут появляться в этом SortedList (они запрещены в стандартном классе).
• Элементы сортируются сами, и никакого ключа не надо (стандартный SortedList требует пары ключ-значение).
Список пропусков
public class SkipList<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 ContainsKey(TKey key);
public void CopyTo(KeyValuePair<TKey,
TValue>[] array, int arrayIndex);
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 int CurrentListLevel { get; }
public TValue this[TKey key] { get; set; }
public ICollection<TKey> Keys { get; }
public int MaxListLevel { get; }
public double Probability { get; }
public ICollection<TValue> Values { get; }
// ...
}
SkipList – хитроумная структура данных, впервые предложенная Уильямом Пугом в 1990 г. Его оригинальная статья лежит тут. Суть SkipList в том, что элементы дублируются на разных уровнях связанных списков, уровень выбирается (почти) случайно. Он обеспечивает быстрый поиск элемента путем "перескоков" через несколько элементов списка, в отличие от нормального связанного списка, где сравнения были бы последовательными.
Списки пропусков обычно реализуются одним из двух способов, с использованием нескольких связанных списков, или матричной структуры (например, двумерный связанный список). SkipList реализован здесь в стиле матрицы. Он реализует интерфейс IDictionary<TKey, TValue> и поэтому может использоваться как стандартный класс Dictionary<TKey, TValue> в каркасе.
Несмотря на то, что производительность превосходная, дублирование элементов может привести к очень быстрому истощению памяти, особенно при большом максимальном числе уровней.
[Дополнительная информация о списках пропусков]
Расширенные стандартные структуры данных
В библиотеку включены версии некоторых из стандартных обобщенных структур данных .NET, расширенных до реализации интерфейса IVisitableCollection<T>. Они следующие:
• VisitableHashtable<Tkey, TValue>
• VisitableLinkedList<T>
• VisitableList<T>
• VisitableQueue<T>
• VisitableStack<T>
Реализованные шаблоны
Синглтон
public sealed class Singleton<T> where T: new()
{
// методы
private Singleton();
// свойства
public static T Instance { get; }
// поля
private static T instance;
}
Синглтон – шаблон, снижающий число экземпляров класса до одного. С появлением обобщений в C# 2.0 реализация обобщенного синглтона стала очень изящной. Другая (более-менее такая же) реализация шаблона синглтона есть в этой статье, но лучше инициализировать значение статически.
Шаблон «Посетитель»
public interface IVisitor<T>
{
// методы
void Visit(T obj);
// свойства
bool HasCompleted { get; }
}
Шаблон «Посетитель» реализуется всеми коллекциями, унаследованными от интерфейса IVisitableCollection<T>. Посетители, унаследованные от IVisitor<T>, могут использоваться для посещения всех видов коллекций, безразлично к внутренней структуре посещаемой структуры данных. Он предоставляет два метода:
• Посетить производит некоторое действие над объектом. Например, считающий посетитель применяется к структуре данных из целых чисел и производит операцию += в методе Visit.
• Свойство HasCompleted указывает, хочет ли посетитель продолжить посещение остальных объектов, содержащихся в коллекции. Это полезно для ищущих посетителей, которые могут прекратить посещение, найдя искомый объект.
[Дополнительная информация о шаблоне посетитель]
Сортировщики
Интерфейс ISorter
public interface ISorter<T>
{
// методы
void Sort(IList<T> list);
void Sort(IList<T> list, SortOrder order);
void Sort(IList<T> list, IComparer<T> comparer);
void Sort(IList<T> list, Comparison<T> comparison);
}
В библиотеке реализовано множество сортировщиков. Стандартные библиотеки каркаса .NET дают малый выбор в плане сортировки, поэтому появились данные сортировщики. Они обобщенные в том смысле, что любой класс, реализующий IList<T>, можно отсортировать, если находящиеся в нем элементы реализуют интерфейс IComparable<T> или если предоставлен экземпляр IComparer<T>.
Предоставляются следующие сортировщики:
• BubbleSorter
• GnomeSorter
• HeapSorter
• InsertionSorter
• SelectionSorter
• MergeSorter
• QuickSorter
• ShellSorter
• BucketSorter
• CombSorter
• CocktailSorter
• OddEvenTransportSorter
• ShakerSorter
Алгоритмы
Алгоритм Дейкстры
Алгоритм Дейкстры помогает с решением задач о кратчайших путях в теории графоф. То есть, если на входе задан направленный или ненаправленный Graph<T>, на выходе выдается граф, представляющий кратчайший путь от вершины источника до любой другой вершины в графе (если вершины достижимы из вершины источника). Ниже показан пример входного и выходного графов с вершиной источника G.
Входной граф
Выходной граф – кратчайшие пути
[Дополнительная информация об алгоритме Дейкстры]
Интересные особенности
Отсутствие поддержки ковариации в C# заставляет избегать интерфейсов для данного типа работы, потому что их применение вынудило бы программиста приводить типы гораздо больше необходимого (или разработчика этой библиотеки заставило бы сделать кучу неявных реализаций).
Также взятая из C++ поддержка множественного наследования и закрытого / защищенного наследования сильно бы изменила эту структуру. Следует надеяться, их поддержка однажды появится в какой-то далекой версии спецификации языка.