06_SortedSet.cs

using System;
using System.Collections.Generic;

namespace DataStructures
{
    /// <summary>
    /// Demonstrates the SortedSet<T> collection in C#.
    /// A SortedSet maintains elements in sorted order and guarantees uniqueness.
    /// It supports mathematical set operations and provides efficient range queries.
    /// 
    /// Internally implemented as a red-black tree.
    /// Common use cases: leaderboards, priority sets, range queries,
    /// unique sorted collections, set algebra.
    /// </summary>
    public class SortedSetExamples
    {
        // ─── Entry Point ───────────────────────────────────────────────
        public static void Main()
        {
            Console.WriteLine("═══════════════════════════════════════════════");
            Console.WriteLine("         C# SortedSet<T> Examples              ");
            Console.WriteLine("═══════════════════════════════════════════════\n");

            // ── 1. Basic Operations ─────────────────────────────────────
            Console.WriteLine("── Basic Add / Remove ─────────────────────────");
            var scores = new SortedSet<int> { 85, 92, 78, 95, 88 };

            Console.WriteLine($"  Initial scores (auto-sorted): {string.Join(", ", scores)}");

            scores.Add(70);       // Add a new element
            scores.Add(92);       // Duplicate — ignored
            Console.WriteLine($"  After Add(70), Add(92): {string.Join(", ", scores)}");

            scores.Remove(78);
            Console.WriteLine($"  After Remove(78):       {string.Join(", ", scores)}");
            Console.WriteLine($"  Min: {scores.Min}  |  Max: {scores.Max}");
            Console.WriteLine();

            // ── 2. Mathematical Set Operations ──────────────────────────
            Console.WriteLine("── Set Operations ─────────────────────────────");
            var setA = new SortedSet<int> { 1, 2, 3, 4, 5 };
            var setB = new SortedSet<int> { 3, 4, 5, 6, 7 };

            Console.WriteLine($"  Set A: {string.Join(", ", setA)}");
            Console.WriteLine($"  Set B: {string.Join(", ", setB)}");

            // Union — all elements from both sets
            var union = new SortedSet<int>(setA);
            union.UnionWith(setB);
            Console.WriteLine($"  Union (A ∪ B)    : {string.Join(", ", union)}");

            // Intersection — elements common to both sets
            var intersect = new SortedSet<int>(setA);
            intersect.IntersectWith(setB);
            Console.WriteLine($"  Intersect (A ∩ B): {string.Join(", ", intersect)}");

            // Symmetric Except — elements in A or B but not both
            var symExcept = new SortedSet<int>(setA);
            symExcept.SymmetricExceptWith(setB);
            Console.WriteLine($"  SymExcept (A △ B): {string.Join(", ", symExcept)}");

            // Difference — elements in A that are not in B
            var diff = new SortedSet<int>(setA);
            diff.ExceptWith(setB);
            Console.WriteLine($"  Difference (A−B) : {string.Join(", ", diff)}");
            Console.WriteLine();

            // ── 3. Unique Elements from Random Data ─────────────────────
            Console.WriteLine("── Extracting Unique Sorted Elements ──────────");
            var random = new Random();
            var numbers = new List<int>();
            for (int i = 0; i < 15; i++)
            {
                numbers.Add(random.Next(1, 20));
            }
            Console.WriteLine($"  Random list ({numbers.Count} items): {string.Join(", ", numbers)}");

            var uniqueSorted = new SortedSet<int>(numbers);
            Console.WriteLine($"  Unique sorted ({uniqueSorted.Count} items): {string.Join(", ", uniqueSorted)}");
            Console.WriteLine($"  Duplicates removed: {numbers.Count - uniqueSorted.Count}");
            Console.WriteLine();

            // ── 4. Range Queries ────────────────────────────────────────
            Console.WriteLine("── Range Queries ──────────────────────────────");
            var data = new SortedSet<int> { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 };
            Console.WriteLine($"  Full set: {string.Join(", ", data)}");

            // GetViewBetween — returns a subset within a range
            var range = data.GetViewBetween(15, 40);
            Console.WriteLine($"  Range [15..40]: {string.Join(", ", range)}");

            // Subset checks
            var small = new SortedSet<int> { 10, 20, 30 };
            Console.WriteLine($"  {{10,20,30}} IsSubsetOf data: {small.IsSubsetOf(data)}");
            Console.WriteLine($"  {{10,20,30}} Overlaps {{1,2,3}}: {small.Overlaps(new SortedSet<int> { 1, 2, 3 })}");

            Console.WriteLine("\n═══════════════════════════════════════════════");
            Console.WriteLine("  Complexity: Add O(log n) | Remove O(log n) | Contains O(log n)");
            Console.WriteLine("  Iteration O(n) — always in sorted order");
            Console.WriteLine("  Set operations: O(n + m)");
            Console.WriteLine("═══════════════════════════════════════════════");
        }
    }
}