Logo

Video: Advanced Data Structures (Bulgarian)

  • August 12, 2020
  • Nikolay Kostov (Nikolay.IT)

Topics covered:

  • Standard .NET Data Structures
    • Special .NET Collections
  • Wintellect Power Collections
    • Installation
    • Power Collection Classes
    • Implementing Priority Queue
  • C5 Collections
  • Other Advanced Data Structures
    • Suffix trees, interval trees, ropes, tries, etc.

Video (in Bulgarian)

Presentation Content

.NET Data Structures

  • Linear structures
    • Lists: List<T>, LinkedList<T>
    • Stacks: Stack<T>
    • Queues: Queue<T>
  • Dictionaries (maps)
    • Dictionary<K,V>, SortedDictionary<K,V>
    • No standard multi-dictionary .NET class
  • Balanced search tree structures
    • SortedSet<T>, SortedDictionary<K,V>
  • Sets and bags
    • Sets – HashSet<T>, SortedSet<T>
    • Bag – no standard .NET class
  • Ordered sets, bags and dictionaries
  • Priority queues / heaps → no
  • Special tree structures → no
    • Suffix tree, interval tree, index tree, trie
  • Graphs → no
    • Directed / undirected
    • Weighted / un-weighted
    • Connected / non-connected, …

Special .NET Collections

  • Collection<T>
    • Inheritable IList<T>, virtual Add() / Remove()
  • ObservableCollection<T>
    • Event CollectionChanged
  • IReadOnlyCollection<T>
    • Supports only Count and GetEnumerator()
  • IReadOnlyList<T>
    • Supports only Count, [] and GetEnumerator()
  • Concurrent collections (thread-safe)
    • BlockingCollection<T>, ConcurrentBag<T>, …

Wintellect Power Collections

  • Wintellect Power Collections is powerful open-source data structure library
  • Installing Power Collections in Visual Studio
    • Use NuGet package manager

Power Collections Classes

  • Bag<T>
    • A bag (multi-set) based on hash-table
      • Unordered collection (with duplicates)
    • Add / Find / Remove work in time O(1)
    • T should provide Equals() and GetHashCode()
  • OrderedBag<T>
    • A bag (multi-set) based on balanced search tree
    • Add / Find / Remove work in time O(log(N))
    • T should implement IComparable<T>
  • Set<T>
    • A set based on hash-table (no duplicates)
    • Add / Find / Remove work in time O(1)
    • Like .NET’s HashSet<T>
  • OrderedSet<T>
    • A set based on balanced search tree (red-black)
    • Add / Find / Remove work in time O(log(N))
    • Like .NET’s SortedSet<T>
    • Provides fast .Range(from, to) operation
  • MultiDictionary<TKey,TValue>
    • A dictionary (map) implemented by hash-table
    • Allows duplicates (configurable)
    • Add / Find / Remove work in time O(1)
    • Like Dictionary<TKey,List<TValue>>
  • OrderedDictionary<TKey,TValue> / OrderedMultiDictionary<TKey,TValue>
    • A dictionary based on balanced search tree
    • Add / Find / Remove work in time O(log(N))
    • Provides fast .Range(from,to) operation
  • Deque<T>
    • Double-ended queue (deque)
  • BigList<T>
    • Editable sequence of indexed items
    • Like List<T> but provides
      • Fast Insert / Delete operations (at any position)
      • Fast Copy / Concat / Sub-range operations
    • Implemented by the data structure "Rope"

Priority Queue

  • What is a "priority queue"?
    • Data structure to efficiently support finding the item with the highest priority
    • Like a queue, but with priorities
    • The basic operations
    • Enqueue(T element)
    • Dequeue() &rarr; T
  • There is no build-in priority queue in .NET
    • See the data structure "binary heap"
    • Can be implemented also by OrderedBag<T>

Priority Queue Implementation

class PriorityQueue<T> where T : IComparable<T>
{
   private OrderedBag<T> queue;
   public int Count 
   {
      get { return this.queue.Count; }
   }
   public PriorityQueue()
   {
      this.queue = new OrderedBag<T>();   
   }
   public void Enqueue(T element)
   {
      this.queue.Add(element);
   }
   public T Dequeue()
   {
      return this.queue.RemoveFirst();
   }
}

Advanced Data Structures

  • Suffix tree (position tree)
    • Represents the suffixes of given string
    • Used to implement fast search in string
  • Trie (prefix tree)
    • Special tree structure used for fastmulti-pattern matching
  • Rope
    • Balanced tree structure for indexed items with fast inserts / delete
    • Allows fast string edit operations
  • Interval tree
    • Keeps intervals [a…b] in ordered balanced tree
    • Allows to efficiently find all intervals that overlap with any given interval or point
  • Binary heap, Fibonacci heap
    • Special tree-like data structures to efficiently implement a priority queue
  • Index trees
    • Used to keep sorted indices of database records
    • B-tree, B+ tree, T-tree

C5 Collections

  • What are “C5 Collections”?
    • C5 Generic Collection Library for C# and CLI
    • Open-Source Data Structures Library for .NET
    • http://www.itu.dk/research/c5/
    • Have solid documentation (book)
    • The C5 library defines its own interfaces like
      • IEnumerable<T>
      • IIndexed<T>
      • IIndexedSorted<T>
      • etc.

C5 Collection Classes

  • Classical collection classes
    • ArrayList<T>, LinkedList<T>, CircularQueue<T>, HashSet<T>, TreeSet<T>, HashBag<T>, TreeBag<T>
  • HashedArrayList<T>
    • Combination of indexed list + hash-table
    • Fast Add / Find / indexer [] → O(1)
  • IntervalHeap<T>
    • Efficient double-ended priority queue

Share