05_SortedDictionary.cs

using System;
using System.Collections.Generic;

namespace DataStructures
{
    /// <summary>
    /// Demonstrates the SortedDictionary<TKey, TValue> in C#.
    /// Keys are maintained in sorted order (ascending by default), making it ideal
    /// for scenarios where ordered traversal is required without explicit sorting.
    /// 
    /// Internally implemented as a balanced binary search tree (red-black tree).
    /// Common use cases: book indexes, ordered dictionaries, ranking systems,
    /// time-series data with ordered keys.
    /// </summary>
    public class SortedDictionaryExamples
    {
        // ─── Entry Point ───────────────────────────────────────────────
        public static void Main()
        {
            Console.WriteLine("═══════════════════════════════════════════════");
            Console.WriteLine("     C# SortedDictionary<TKey, TValue> Examples");
            Console.WriteLine("═══════════════════════════════════════════════\n");

            // ── 1. Book Index — Letter → List of Topics ────────────────
            Console.WriteLine("── Book Index (Sorted by Letter) ─────────────");
            var bookIndex = new SortedDictionary<char, List<string>>();

            // Add entries — note keys will be auto-sorted alphabetically
            bookIndex.Add('C', new List<string> { "Collections", "Concurrency", "LINQ" });
            bookIndex.Add('A', new List<string> { "Arrays", "Asynchronous Programming" });
            bookIndex.Add('D', new List<string> { "Delegates", "Dictionaries" });
            bookIndex.Add('B', new List<string> { "Binary Search", "Boxing" });
            bookIndex.Add('E', new List<string> { "Exceptions", "Events", "Enumerations" });

            // Iterate — keys are automatically in ascending order
            Console.WriteLine("  Index entries (auto-sorted by key):\n");
            foreach (KeyValuePair<char, List<string>> entry in bookIndex)
            {
                Console.WriteLine($"  [{entry.Key}]");
                foreach (string topic in entry.Value)
                {
                    Console.WriteLine($"      • {topic}");
                }
            }
            Console.WriteLine();

            // ── 2. Adding & Accessing Entries ──────────────────────────
            Console.WriteLine("── Add / Access Operations ───────────────────");

            // Adding a new entry
            bookIndex.Add('F', new List<string> { "Files", "Functions" });
            Console.WriteLine("  Added 'F' entry");

            // Accessing a value by key
            if (bookIndex.TryGetValue('C', out List<string> cTopics))
            {
                Console.WriteLine($"  Topics under 'C': {string.Join(", ", cTopics)}");
            }

            // Adding a topic to an existing entry
            if (bookIndex.ContainsKey('A'))
            {
                bookIndex['A'].Add("Abstract Classes");
                Console.WriteLine($"  'A' topics updated: {string.Join(", ", bookIndex['A'])}");
            }
            Console.WriteLine();

            // ── 3. Key & Value Properties ──────────────────────────────
            Console.WriteLine("── Properties ─────────────────────────────────");
            Console.WriteLine($"  Total index letters: {bookIndex.Count}");
            Console.WriteLine($"  Keys (sorted)      : {string.Join(", ", bookIndex.Keys)}");

            // Min/Max key access
            Console.WriteLine($"  First key           : {bookIndex.Keys.First()}");
            Console.WriteLine($"  Last key            : {bookIndex.Keys.Last()}");
            Console.WriteLine();

            // ── 4. Remove & Contains ────────────────────────────────────
            Console.WriteLine("── Remove / Contains ──────────────────────────");
            Console.WriteLine($"  ContainsKey('B')  : {bookIndex.ContainsKey('B')}");
            Console.WriteLine($"  Remove('B')       : {bookIndex.Remove('B')}");
            Console.WriteLine($"  ContainsKey('B')  : {bookIndex.ContainsKey('B')}");
            Console.WriteLine($"  Updated keys       : {string.Join(", ", bookIndex.Keys)}");
            Console.WriteLine();

            // ── 5. Full Sorted Iteration ────────────────────────────────
            Console.WriteLine("── Final Index (A–F, no B) ───────────────────");
            foreach (var entry in bookIndex)
            {
                Console.WriteLine($"  [{entry.Key}] {string.Join(", ", entry.Value)}");
            }

            Console.WriteLine("\n═══════════════════════════════════════════════");
            Console.WriteLine("  Complexity: Add O(log n) | Remove O(log n) | Lookup O(log n)");
            Console.WriteLine("  Iteration O(n) — keys always in sorted order");
            Console.WriteLine("  Backed by a red-black tree (balanced BST)");
            Console.WriteLine("═══════════════════════════════════════════════");
        }
    }
}