Rebuilding visitor paths with a linear sort

using System;

namespace WebApplication1
{
    /// <summary>
    /// CSC 482 HW4 - the linear sort. RADIX-SORT from CLRS 8.3 (notes8b), built out of the stable
    /// COUNTING-SORT from CLRS 8.2 (notes8c), over fixed-width byte keys such as IP addresses.
    /// The HW4 page (linearsort/default.aspx), the benchmark and the Visitor paths panel on
    /// admin_activity.aspx all call Order() below.
    ///
    /// Every result Order() returns is checked by SortCheck (sorted, every index exactly once,
    /// equal keys still in their original order). If it ever got one wrong, the callers would
    /// report that on the page and use LINQ's OrderBy (stable, O(n lg n)) instead.
    /// </summary>
    public static class RadixSort
    {
        /// <summary>The widest key Order() takes: 16 bytes, an IPv6 address.</summary>
        public const int MaxWidth = 16;

        /// <summary>
        /// Stable LSD radix sort of n fixed-width keys. Does not change <paramref name="keys"/>;
        /// it returns the sorted order instead, so the caller can line up any records that go with
        /// the keys (activity events here).
        /// </summary>
        /// <param name="keys">
        /// n keys of <paramref name="width"/> bytes each, back to back, most significant byte first -
        /// the way an IP address is written. Key i is keys[i * width] .. keys[i * width + width - 1].
        /// 203.0.113.9 is the 4 bytes { 203, 0, 113, 9 }.
        /// </param>
        /// <param name="width">Bytes per key: 4 for IPv4 addresses, 16 for IPv6 ones (d in RADIX-SORT(A, d)).</param>
        /// <returns>
        /// order, with order[r] = the index (0 .. n-1) of the key that belongs at position r. Keys that
        /// are equal keep their original order (stable): if keys 7 and 12 are the same address,
        /// 7 comes first. The log is in time order, so that is what keeps each visitor's path in order.
        /// </returns>
        public static int[] Order(byte[] keys, int width)
        {
            if (keys == null)
                throw new ArgumentNullException("keys");
            if (width < 1 || width > MaxWidth)
                throw new ArgumentOutOfRangeException("width", "width must be 1 to " + MaxWidth + " bytes");
            if (keys.Length % width != 0)
                throw new ArgumentException("keys.Length must be a multiple of width", "keys");

            int n = keys.Length / width;
            if (n == 0)
                return new int[0];

            // In the notes' terms: each byte is one digit with k = 256 possible values, and there are
            // d = width digits per key. RADIX-SORT runs a stable COUNTING-SORT on the least significant
            // digit, then the next, ... up to the most significant: d passes of Θ(n + k) work, which is
            // Θ(d(n + 256)) - linear in n for a fixed width.
            //
            // Layout. The obvious way to sort "indices by key" is to keep an int[] order and look up
            // keys[order[j] * width + digit] on every pass. Measured on this machine, that version ran
            // at 27 ns per element for n = 1,000,000 and 110 ns per element for n = 10,000,000 - the
            // lookups jump all over a 40 MB array and miss the cache, and at 10 million it was slower
            // than Array.Sort. CLRS warns about exactly this in 8.3 ("quicksort often uses hardware
            // caches more effectively than radix sort"). So each record carries its key and its index
            // together, and every pass is one straight walk through memory: 26 ns per element at both
            // sizes. Keys up to 4 bytes fit a single ulong with the index; wider keys use a small struct.
            return width <= 4 ? OrderPacked(keys, width, n) : OrderWide(keys, width, n);
        }

        // Report progress (for the HW4 progress bar) once every SortProgress.Every elements placed.
        // Every is a power of two, so this is one AND and one compare per element.
        private const int ReportMask = SortProgress.Every - 1;

        // ---- Keys of 1 to 4 bytes: one ulong per record ----

        /// <summary>The key (most significant byte first) in the high 32 bits, the original index in the low 32.</summary>
        private static int[] OrderPacked(byte[] keys, int width, int n)
        {
            var a = new ulong[n];
            var b = new ulong[n];
            for (int i = 0; i < n; i++)
            {
                ulong key = 0;
                int p = i * width;
                for (int d = 0; d < width; d++)
                    key = (key << 8) | keys[p + d];
                a[i] = (key << 32) | (uint)i;
            }

            var count = new int[256];
            long total = (long)width * n;
            // notes8b line 1: for j = d downto 1 - the least significant byte sits at bit 32.
            for (int pass = 0; pass < width; pass++)
            {
                int shift = 32 + 8 * pass;
                if (CountingSortPass(a, b, n, shift, count, (long)pass * n, total))
                {
                    ulong[] t = a; a = b; b = t;     // this pass's output is the next pass's input
                }
            }

            var order = new int[n];
            for (int r = 0; r < n; r++)
                order[r] = (int)(a[r] & 0xFFFFFFFFu);
            return order;
        }

        /// <summary>
        /// COUNTING-SORT (notes8c) of <paramref name="from"/> into <paramref name="to"/> on the byte at
        /// <paramref name="shift"/>. Returns false, leaving <paramref name="to"/> untouched, when every
        /// record has the same byte there: a stable sort of equal keys is the identity, so there is
        /// nothing to move (the counting still costs n, so the bound is unchanged).
        /// </summary>
        private static bool CountingSortPass(ulong[] from, ulong[] to, int n, int shift, int[] count, long placedBefore, long total)
        {
            // Lines 1-3: C[i] = how many records have byte value i.
            Array.Clear(count, 0, 256);
            for (int j = 0; j < n; j++)
                count[(int)((from[j] >> shift) & 0xFF)]++;

            if (count[(int)((from[0] >> shift) & 0xFF)] == n)
            {
                SortProgress.Report(placedBefore + n, total);
                return false;
            }

            // Line 4: C[i] = how many records have byte value <= i, which is one past the last slot
            // that value i may use.
            for (int v = 1; v < 256; v++)
                count[v] += count[v - 1];

            // Lines 5-7: walk the input from the END, dropping each record into the last free slot for
            // its value and moving that boundary down. Going backwards is what makes the pass stable:
            // of two records with the same byte, the later one is placed first, into the later slot.
            // LSD radix sort is only correct when every pass is stable.
            for (int j = n - 1; j >= 0; j--)
            {
                ulong x = from[j];
                to[--count[(int)((x >> shift) & 0xFF)]] = x;
                if ((j & ReportMask) == 0)
                    SortProgress.Report(placedBefore + (n - j), total);
            }
            return true;
        }

        // ---- Keys of 5 to 16 bytes: a 24-byte struct per record ----

        /// <summary>The key as a 128-bit number (most significant byte first, right-aligned) plus its index.</summary>
        private struct Record
        {
            public ulong Hi;      // bytes 0 .. width-9 of the key (zero for keys of 8 bytes or fewer)
            public ulong Lo;      // the last 8 bytes of the key
            public int Index;

            /// <summary>Byte number <paramref name="pass"/> counting from the least significant end.</summary>
            public int Digit(int pass)
            {
                int shift = 8 * pass;
                return (int)((shift < 64 ? Lo >> shift : Hi >> (shift - 64)) & 0xFF);
            }
        }

        private static int[] OrderWide(byte[] keys, int width, int n)
        {
            var a = new Record[n];
            var b = new Record[n];
            for (int i = 0; i < n; i++)
            {
                ulong hi = 0, lo = 0;
                int p = i * width;
                for (int d = 0; d < width; d++)
                {
                    hi = (hi << 8) | (lo >> 56);
                    lo = (lo << 8) | keys[p + d];
                }
                a[i].Hi = hi;
                a[i].Lo = lo;
                a[i].Index = i;
            }

            var count = new int[256];
            long total = (long)width * n;
            for (int pass = 0; pass < width; pass++)
            {
                if (CountingSortPass(a, b, n, pass, count, (long)pass * n, total))
                {
                    Record[] t = a; a = b; b = t;
                }
            }

            var order = new int[n];
            for (int r = 0; r < n; r++)
                order[r] = a[r].Index;
            return order;
        }

        /// <summary>The same COUNTING-SORT pass as above, for the wide records.</summary>
        private static bool CountingSortPass(Record[] from, Record[] to, int n, int pass, int[] count, long placedBefore, long total)
        {
            Array.Clear(count, 0, 256);
            for (int j = 0; j < n; j++)
                count[from[j].Digit(pass)]++;

            if (count[from[0].Digit(pass)] == n)
            {
                SortProgress.Report(placedBefore + n, total);
                return false;
            }

            for (int v = 1; v < 256; v++)
                count[v] += count[v - 1];

            for (int j = n - 1; j >= 0; j--)
            {
                to[--count[from[j].Digit(pass)]] = from[j];
                if ((j & ReportMask) == 0)
                    SortProgress.Report(placedBefore + (n - j), total);
            }
            return true;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Threading;
using System.Web.Hosting;
using System.Web.Script.Serialization;
using Microsoft.Win32;

namespace WebApplication1
{
    /// <summary>One size of n: how long each sort took (median of the trials) and whether its answer checked out.</summary>
    public class BenchmarkRow
    {
        public int N { get; set; }
        public int Visitors { get; set; }
        public double? RadixMs { get; set; }         // null when RadixSort.Order isn't written or got it wrong
        public double? Radix16Ms { get; set; }       // the same radix sort on 16-byte (IPv6-sized) keys
        public double ArraySortMs { get; set; }
        public double OrderByMs { get; set; }
        public string RadixProblem { get; set; }     // null = sorted, stable, every index once
        public int ArraySortBreaks { get; set; }     // equal addresses that came out in the wrong time order
        public int OrderByBreaks { get; set; }
    }

    public class BenchmarkResult
    {
        public DateTime RanAt { get; set; }          // local
        public string Machine { get; set; }
        public string Runtime { get; set; }
        public int Trials { get; set; }
        public double Seconds { get; set; }
        public string Note { get; set; }             // why a run stopped early, if it did
        public List<BenchmarkRow> Rows { get; set; }
    }

    /// <summary>
    /// The HW4 timing loop. For n = 10, 100, ... up to the chosen limit it makes a fresh random data
    /// set - n activity events in time order, each with a visitor's address, a few heavy visitors and
    /// many light ones - and copies it for each sort, then times:
    ///   RadixSort.Order on the 4-byte keys (linear, O(d(n + k)))
    ///   Array.Sort on the same addresses as uint numbers (introsort, O(n lg n), NOT stable)
    ///   Enumerable.OrderBy on them (O(n lg n), stable)
    ///   RadixSort.Order again on 16-byte keys, to show what a longer key (bigger d) costs.
    /// Every answer is checked, each sort runs <see cref="Trials"/> times per n and the median is
    /// kept. Which sort goes first rotates from trial to trial, so none of them always runs on a
    /// cold cache. Building the keys and the copies is never inside the timer.
    /// It runs on a background thread (the admin starts it from the HW4 page) and saves to
    /// App_Data\LinearSort\benchmark.json; the public page shows the last saved run.
    /// </summary>
    public static class LinearSortBenchmark
    {
        public const int Trials = 3;
        private const string FileName = "benchmark.json";
        private static readonly JavaScriptSerializer Serializer = new JavaScriptSerializer();
        private static readonly object Gate = new object();

        // Progress, for the bar on the page. Read under Gate.
        private static bool running;
        private static int stepsDone, stepsTotal;
        private static string message = "";
        private static string lastError;

        public class Progress
        {
            public bool Running { get; set; }
            public int Percent { get; set; }
            public string Message { get; set; }
            public string Error { get; set; }
        }

        public static Progress Status()
        {
            lock (Gate)
            {
                return new Progress
                {
                    Running = running,
                    Percent = stepsTotal == 0 ? 0 : (int)(100L * stepsDone / stepsTotal),
                    Message = message,
                    Error = lastError
                };
            }
        }

        /// <summary>Starts a run in the background. False when one is already going.</summary>
        public static bool Start(int maxN)
        {
            // One heavy job at a time: both want every core and a lot of memory.
            if (RadixProgressRun.IsRunning)
                return false;
            lock (Gate)
            {
                if (running)
                    return false;
                running = true;
                stepsDone = 0;
                stepsTotal = 0;
                message = "Starting…";
                lastError = null;
            }
            // QueueBackgroundWorkItem lets IIS know about the work, so a recycle waits for it (briefly)
            // instead of killing it mid-sort.
            HostingEnvironment.QueueBackgroundWorkItem(ct => Run(maxN, ct));
            return true;
        }

        public static BenchmarkResult LoadLast()
        {
            try
            {
                string file = LinearSortFiles.PathOf(FileName);
                return File.Exists(file) ? Serializer.Deserialize<BenchmarkResult>(File.ReadAllText(file)) : null;
            }
            catch
            {
                return null;
            }
        }

        // ---- The loop ----

        private static void Run(int maxN, CancellationToken ct)
        {
            try
            {
                BenchmarkResult result = RunLoop(maxN, ct);
                File.WriteAllText(LinearSortFiles.PathOf(FileName), Serializer.Serialize(result));
                SetMessage("Finished in " + result.Seconds.ToString("0.0") + " s");
            }
            catch (Exception ex)
            {
                lock (Gate)
                    lastError = ex.GetType().Name + ": " + ex.Message;
            }
            finally
            {
                lock (Gate)
                {
                    running = false;
                    stepsDone = stepsTotal;
                }
            }
        }

        /// <summary>
        /// The whole loop, n = 10 up to <paramref name="maxN"/>, without saving anything - so it can
        /// also be run outside IIS (a console program referencing the site's DLL), where nothing
        /// else is competing for the CPU.
        /// </summary>
        public static BenchmarkResult RunLoop(int maxN, CancellationToken ct)
        {
            var total = Stopwatch.StartNew();
            var result = new BenchmarkResult
            {
                Machine = MachineName(),
                Runtime = (Environment.Is64BitProcess ? "64-bit" : "32-bit") + " .NET Framework (CLR " + Environment.Version + ")",
                Trials = Trials,
                Rows = new List<BenchmarkRow>()
            };

            var sizes = new List<int>();
            for (long n = 10; n <= maxN; n *= 10)
                sizes.Add((int)n);
            lock (Gate)
                stepsTotal = sizes.Count * Trials * 4;

            bool radixWritten = VisitorPaths.SelfTest() == null;
            // The first call to anything pays for the JIT compiling it; get that out of the way
            // on a small array so it doesn't land on n = 10.
            SetMessage("Warming up");
            Measure(1000, new Random(1), radixWritten, null, CancellationToken.None);

            var rng = new Random();
            foreach (int n in sizes)
            {
                if (ct.IsCancellationRequested)
                {
                    result.Note = "Stopped early: the site was shutting down.";
                    break;
                }
                try
                {
                    result.Rows.Add(Measure(n, rng, radixWritten, n.ToString("N0"), ct));
                }
                catch (OutOfMemoryException)
                {
                    result.Note = "Stopped at n = " + n.ToString("N0") + ": the server ran out of memory.";
                    break;
                }
            }

            result.RanAt = DateTime.Now;
            result.Seconds = total.Elapsed.TotalSeconds;
            return result;
        }

        /// <summary>One time through the loop: fresh data of size n, then every sort, Trials times each.</summary>
        private static BenchmarkRow Measure(int n, Random rng, bool radixWritten, string label, CancellationToken ct)
        {
            // Visitors: one for every 10 events. Each has an IPv4 address and a 16-byte (IPv6-sized)
            // one, random in every byte: Order skips a pass when a byte is the same in every key, so
            // a shared prefix like 2001:db8 would quietly make the 16-byte column a 12-pass cost.
            int visitors = Math.Max(1, n / 10);
            var pool4 = new uint[visitors];
            var pool16 = new byte[visitors * 16];
            rng.NextBytes(pool16);
            var bytes = new byte[4];
            for (int v = 0; v < visitors; v++)
            {
                rng.NextBytes(bytes);
                pool4[v] = (uint)(bytes[0] << 24 | bytes[1] << 16 | bytes[2] << 8 | bytes[3]);
            }

            // The data set: event i (time order) belongs to visitor who. u * u favours low numbers,
            // so some visitors show up again and again - lots of equal keys, like the real log.
            var ips = new uint[n];
            var keys4 = new byte[n * 4];
            var keys16 = new byte[(long)n * 16];
            for (int i = 0; i < n; i++)
            {
                double u = rng.NextDouble();
                int who = (int)(u * u * visitors);
                ips[i] = pool4[who];
                VisitorPaths.WriteUInt(ips[i], keys4, i * 4);
                Buffer.BlockCopy(pool16, who * 16, keys16, i * 16, 16);
            }

            var row = new BenchmarkRow { N = n, Visitors = visitors };
            var radix = new List<double>();
            var radix16 = new List<double>();
            var arraySort = new List<double>();
            var orderBy = new List<double>();
            if (!radixWritten)
                row.RadixProblem = "RadixSort.Order isn't written yet";

            // The four sorts, each on its own copy of the data.
            string[] names = { "RadixSort.Order", "Array.Sort", "OrderBy", "RadixSort.Order, 16-byte keys" };
            Action[] sorts =
            {
                // Linear: RadixSort.Order on the 4-byte keys.
                () =>
                {
                    if (row.RadixProblem != null)
                        return;
                    byte[] copy = (byte[])keys4.Clone();
                    double ms;
                    int[] order = TimeRadix(copy, 4, out ms, row);
                    if (order != null)
                    {
                        row.RadixProblem = SortCheck.Problem(keys4, 4, order);
                        radix.Add(ms);
                    }
                },

                // Comparison: Array.Sort carries an index array along with the numbers it sorts.
                () =>
                {
                    uint[] copy = (uint[])ips.Clone();
                    int[] index = Enumerable.Range(0, n).ToArray();
                    double ms;
                    Time(() => { Array.Sort(copy, index); return index; }, out ms);
                    // Out of order would be a real failure; out of time order among equal keys is
                    // just Array.Sort not being stable, which is counted instead.
                    string check = SortCheck.Problem(keys4, 4, index);
                    if (check != null && !check.Contains("not stable"))
                        throw new InvalidOperationException("Array.Sort check failed: " + check);
                    row.ArraySortBreaks = SortCheck.StabilityBreaks(keys4, 4, index);
                    arraySort.Add(ms);
                },

                // Comparison: OrderBy, LINQ's stable sort.
                () =>
                {
                    uint[] copy = (uint[])ips.Clone();
                    double ms;
                    int[] order = Time(() => Enumerable.Range(0, n).OrderBy(i => copy[i]).ToArray(), out ms);
                    string check = SortCheck.Problem(keys4, 4, order);
                    if (check != null && !check.Contains("not stable"))
                        throw new InvalidOperationException("OrderBy check failed: " + check);
                    row.OrderByBreaks = SortCheck.StabilityBreaks(keys4, 4, order);
                    orderBy.Add(ms);
                },

                // Linear again, with keys four times as long.
                () =>
                {
                    if (row.RadixProblem != null)
                        return;
                    byte[] copy = (byte[])keys16.Clone();
                    double ms;
                    int[] order = TimeRadix(copy, 16, out ms, row);
                    if (order != null)
                    {
                        string problem = SortCheck.Problem(keys16, 16, order);
                        if (problem != null)
                            row.RadixProblem = "16-byte keys: " + problem;
                        radix16.Add(ms);
                    }
                }
            };

            for (int t = 0; t < Trials; t++)
            {
                if (ct.IsCancellationRequested)
                    break;
                string trial = label == null ? null : "n = " + label + " · trial " + (t + 1) + " of " + Trials;

                // Trial 1 runs them in the order above, trial 2 starts with the second, and so on:
                // whichever goes first finds a cold cache and the others' garbage just collected, and
                // rotating shares that out instead of always handing it to the radix sort.
                for (int s = 0; s < sorts.Length; s++)
                {
                    int which = (t + s) % sorts.Length;
                    Step(trial, names[which]);
                    sorts[which]();
                }
            }

            row.ArraySortMs = Median(arraySort);
            row.OrderByMs = Median(orderBy);
            if (row.RadixProblem == null)
            {
                row.RadixMs = Median(radix);
                row.Radix16Ms = Median(radix16);
            }
            return row;
        }

        /// <summary>Runs one sort with a clean slate: garbage from the last sort collected first, so it isn't billed to this one.</summary>
        private static int[] Time(Func<int[]> sort, out double ms)
        {
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
            var watch = Stopwatch.StartNew();
            int[] order = sort();
            watch.Stop();
            ms = watch.Elapsed.TotalMilliseconds;
            return order;
        }

        /// <summary>Times RadixSort.Order; if it throws, the row says so and the run carries on without it.</summary>
        private static int[] TimeRadix(byte[] keys, int width, out double ms, BenchmarkRow row)
        {
            try
            {
                return Time(() => RadixSort.Order(keys, width), out ms);
            }
            catch (OutOfMemoryException)
            {
                throw;
            }
            catch (Exception ex)
            {
                ms = 0;
                row.RadixProblem = (width == 16 ? "16-byte keys: " : "") + "threw " + ex.GetType().Name + ": " + ex.Message;
                return null;
            }
        }

        private static double Median(List<double> times)
        {
            if (times.Count == 0)
                return 0;
            var sorted = times.OrderBy(t => t).ToList();
            return sorted[sorted.Count / 2];
        }

        private static void Step(string trial, string sort)
        {
            if (trial == null)
                return;     // the warm-up doesn't count towards the bar
            lock (Gate)
            {
                stepsDone++;
                message = trial + " · " + sort;
            }
        }

        private static void SetMessage(string text)
        {
            lock (Gate)
                message = text;
        }

        /// <summary>"AMD Ryzen 7 5800H with Radeon Graphics, 16 logical cores" - the CPU, as the assignment asks.</summary>
        private static string MachineName()
        {
            string cpu = null;
            try
            {
                using (RegistryKey key = Registry.LocalMachine.OpenSubKey(@"HARDWARE\DESCRIPTION\System\CentralProcessor\0"))
                    cpu = key == null ? null : (key.GetValue("ProcessorNameString") as string);
            }
            catch { /* not allowed to look: leave it out */ }
            return (string.IsNullOrWhiteSpace(cpu) ? "Unknown CPU" : cpu.Trim()) + ", " + Environment.ProcessorCount + " logical cores";
        }
    }

    /// <summary>
    /// The HW4 progress bar (extra credit): one big, UNTIMED radix sort in the background, with
    /// the bar on the page following the SortProgress.Report calls RadixSort.Order makes as it
    /// goes. Untimed because reporting is extra work, and because the assignment says the
    /// visualization doesn't need timing. The answer is still checked afterwards.
    /// </summary>
    public static class RadixProgressRun
    {
        private static readonly object Gate = new object();
        private static bool running;
        private static long n, done, total;
        private static int width, reports;
        private static Stopwatch watch = new Stopwatch();
        private static string stage = "", summary, error;

        public static bool IsRunning
        {
            get { lock (Gate) return running; }
        }

        /// <summary>Where the run has got, in the same shape as the benchmark's, for status.ashx?what=sort.</summary>
        public static LinearSortBenchmark.Progress Status()
        {
            lock (Gate)
            {
                string text;
                if (!running)
                    text = summary ?? "";
                else if (reports == 0)
                    text = stage;
                else
                {
                    // Elements placed out of width × n: the pass is how many n's are done so far.
                    long pass = Math.Min(width, done / Math.Max(1, n) + 1);
                    text = "Pass " + pass + " of " + width + " · " + done.ToString("N0") + " of " + total.ToString("N0")
                           + " placed · " + watch.Elapsed.TotalSeconds.ToString("0.0") + " s";
                }
                return new LinearSortBenchmark.Progress
                {
                    Running = running,
                    Percent = total > 0 ? (int)Math.Min(100, 100 * done / total) : 0,
                    Message = text,
                    Error = error
                };
            }
        }

        /// <summary>Whether there's anything to show: a run going, or the last one's outcome.</summary>
        public static bool HasNews
        {
            get { lock (Gate) return running || summary != null || error != null; }
        }

        /// <summary>Starts a run in the background. False when it or the benchmark is already going.</summary>
        public static bool Start(int count, int keyWidth)
        {
            if (LinearSortBenchmark.Status().Running)
                return false;
            lock (Gate)
            {
                if (running)
                    return false;
                // Clear the last run now, so the bar doesn't show its numbers before Run starts.
                running = true;
                done = total = 0;
                reports = 0;
                summary = error = null;
                stage = "Starting…";
            }
            HostingEnvironment.QueueBackgroundWorkItem(ct => Run(count, keyWidth));
            return true;
        }

        /// <summary>
        /// The run itself, on whatever thread calls it: make <paramref name="count"/> random keys of
        /// <paramref name="keyWidth"/> bytes (lots of repeats, like the benchmark), sort them while
        /// listening for reports, then check the answer.
        /// </summary>
        public static void Run(int count, int keyWidth)
        {
            lock (Gate)
            {
                running = true;
                n = count;
                width = keyWidth;
                done = 0;
                total = 0;
                reports = 0;
                summary = null;
                error = null;
                stage = "Making " + count.ToString("N0") + " random " + keyWidth + "-byte keys…";
                watch.Reset();
            }
            try
            {
                byte[] keys = RandomKeys(count, keyWidth, new Random());

                lock (Gate)
                {
                    stage = "Sorting… no progress reported yet";
                    watch.Start();
                }
                int[] order = SortProgress.Listen((d, t) =>
                {
                    lock (Gate)
                    {
                        done = d;
                        total = t;
                        reports++;
                    }
                }, () => RadixSort.Order(keys, keyWidth));
                double seconds;
                int heard;
                lock (Gate)
                {
                    watch.Stop();
                    seconds = watch.Elapsed.TotalSeconds;
                    heard = reports;
                    stage = "Checking the answer…";
                }

                string problem = SortCheck.Problem(keys, keyWidth, order);
                string text = "Sorted " + count.ToString("N0") + " " + keyWidth + "-byte keys in " + seconds.ToString("0.00") + " s (reporting on, so not a benchmark time), with "
                              + heard.ToString("N0") + " progress " + (heard == 1 ? "report" : "reports") + ". ";
                if (problem != null)
                    text += "But the answer is wrong: " + problem + ".";
                else if (heard == 0)
                    text += "The answer checks out, but RadixSort.Order never called SortProgress.Report, so the bar had nothing to follow.";
                else
                    text += "Checked: sorted, every key exactly once, and stable.";

                lock (Gate)
                {
                    done = total = Math.Max(total, 1);
                    summary = text;
                }
            }
            catch (NotImplementedException)
            {
                lock (Gate) error = "RadixSort.Order isn't written yet.";
            }
            catch (OutOfMemoryException)
            {
                lock (Gate) error = "The server ran out of memory making " + count.ToString("N0") + " keys.";
            }
            catch (Exception ex)
            {
                lock (Gate) error = "RadixSort.Order threw " + ex.GetType().Name + ": " + ex.Message;
            }
            finally
            {
                lock (Gate)
                {
                    running = false;
                    watch.Stop();
                }
            }
        }

        /// <summary>count keys of width bytes, random in every byte (so no pass gets skipped): one visitor per 10 keys, some far busier than others.</summary>
        private static byte[] RandomKeys(int count, int keyWidth, Random rng)
        {
            int visitors = Math.Max(1, count / 10);
            var pool = new byte[(long)visitors * keyWidth];
            rng.NextBytes(pool);
            var keys = new byte[(long)count * keyWidth];
            for (int i = 0; i < count; i++)
            {
                double u = rng.NextDouble();
                int who = (int)(u * u * visitors);
                Buffer.BlockCopy(pool, who * keyWidth, keys, i * keyWidth, keyWidth);
            }
            return keys;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Net;
using System.Net.Sockets;

namespace WebApplication1
{
    /// <summary>One address and everything it did, oldest first.</summary>
    public class VisitorPath
    {
        public string Ip { get; set; }
        public List<ActivityEvent> Events { get; set; }
        public ActivityEvent First { get { return Events[0]; } }
        public ActivityEvent Last { get { return Events[Events.Count - 1]; } }
    }

    /// <summary>How a list of keys got sorted, for the line under a panel.</summary>
    public class SortOutcome
    {
        public int[] Order { get; set; }
        public string Method { get; set; }       // "RadixSort.Order" or "OrderBy"
        public double Ms { get; set; }
        public int Width { get; set; }
        public string Problem { get; set; }      // why the radix sort wasn't used, or null when it was
        public SortOutcome ByTime { get; set; }  // for Group: the sort by time that came before this sort by address

        public bool UsedRadix { get { return Method == VisitorPaths.Radix; } }
    }

    /// <summary>
    /// The HW4 idea: once the activity log is in time order, a STABLE sort by IP address puts each
    /// visitor's events side by side and still in the order they happened - their path through the
    /// site. The log is appended in nearly, but not exactly, time order (see InTimeOrder), so Group
    /// runs RadixSort.Order twice: over the 8-byte timestamp, then over the address. This class
    /// turns timestamps and addresses into the byte keys the sort wants, checks what it returns,
    /// and falls back to OrderBy (also stable) whenever it gets one wrong.
    /// (GroupBy would group in O(n) too, with a hash table. The radix sort also leaves the
    /// addresses in numeric order and never hashes anything.)
    /// </summary>
    public static class VisitorPaths
    {
        public const string Radix = "RadixSort.Order";
        public const string Fallback = "OrderBy";

        /// <summary>A timestamp key: the UTC tick count, 8 bytes, most significant first.</summary>
        public const int TimeWidth = 8;

        // ---- Keys ----

        /// <summary>
        /// The bytes of an address, most significant first, written at keys[offset..]. Width 4 takes
        /// IPv4 only; width 16 takes both, with IPv4 written the IPv6 way (::ffff:a.b.c.d) so the two
        /// kinds sort together. Anything unreadable becomes all zeros and groups as one "unknown".
        /// </summary>
        public static void WriteKey(string ip, byte[] keys, int offset, int width)
        {
            IPAddress address;
            if (string.IsNullOrEmpty(ip) || !IPAddress.TryParse(ip.Trim(), out address))
            {
                Array.Clear(keys, offset, width);
                return;
            }
            if (width == 16 && address.AddressFamily == AddressFamily.InterNetwork)
                address = address.MapToIPv6();
            byte[] bytes = address.GetAddressBytes();
            if (bytes.Length != width)
            {
                Array.Clear(keys, offset, width);
                return;
            }
            Buffer.BlockCopy(bytes, 0, keys, offset, width);
        }

        /// <summary>4 when every address is IPv4 (4 radix passes), otherwise 16.</summary>
        public static int WidthFor(IEnumerable<string> ips)
        {
            foreach (string ip in ips)
            {
                IPAddress address;
                if (!string.IsNullOrEmpty(ip) && IPAddress.TryParse(ip.Trim(), out address)
                    && address.AddressFamily != AddressFamily.InterNetwork)
                    return 16;
            }
            return 4;
        }

        public static byte[] KeysFor(IList<string> ips, int width)
        {
            var keys = new byte[ips.Count * width];
            for (int i = 0; i < ips.Count; i++)
                WriteKey(ips[i], keys, i * width, width);
            return keys;
        }

        /// <summary>
        /// Keys for a sort by time: each event's tick count (100 ns units since year 1, never negative)
        /// as 8 bytes, most significant first, so that byte order is time order.
        /// </summary>
        public static byte[] TimeKeysFor(IList<ActivityEvent> events)
        {
            var keys = new byte[events.Count * TimeWidth];
            for (int i = 0; i < events.Count; i++)
            {
                ulong ticks = (ulong)events[i].At.Ticks;
                for (int d = 0; d < TimeWidth; d++)
                    keys[i * TimeWidth + d] = (byte)(ticks >> (56 - 8 * d));
            }
            return keys;
        }

        // ---- Sorting, with a safety net ----

        /// <summary>Sorts by key with RadixSort.Order, or with OrderBy when that isn't written yet or gets it wrong.</summary>
        public static SortOutcome OrderByKey(byte[] keys, int width)
        {
            string problem;
            var watch = Stopwatch.StartNew();
            try
            {
                int[] order = RadixSort.Order(keys, width);
                watch.Stop();
                problem = SortCheck.Problem(keys, width, order);
                if (problem == null)
                    return new SortOutcome { Order = order, Method = Radix, Ms = watch.Elapsed.TotalMilliseconds, Width = width };
            }
            catch (NotImplementedException)
            {
                problem = "RadixSort.Order isn't written yet";
            }
            catch (Exception ex)
            {
                problem = "RadixSort.Order threw " + ex.GetType().Name + ": " + ex.Message;
            }

            watch.Restart();
            int[] fallback = StableOrder(keys, width);
            watch.Stop();
            return new SortOutcome { Order = fallback, Method = Fallback, Ms = watch.Elapsed.TotalMilliseconds, Width = width, Problem = problem };
        }

        /// <summary>The comparison-sort answer: LINQ's OrderBy is documented as stable, O(n lg n).</summary>
        public static int[] StableOrder(byte[] keys, int width)
        {
            int n = width == 0 ? 0 : keys.Length / width;
            return Enumerable.Range(0, n).OrderBy(i => i, new KeyComparer(keys, width)).ToArray();
        }

        /// <summary>Compares two keys (by index) byte by byte, most significant first - numeric order for addresses.</summary>
        public class KeyComparer : IComparer<int>
        {
            private readonly byte[] keys;
            private readonly int width;

            public KeyComparer(byte[] keys, int width)
            {
                this.keys = keys;
                this.width = width;
            }

            public int Compare(int a, int b)
            {
                return SortCheck.CompareKeys(keys, width, a, b);
            }
        }

        // ---- Grouping ----

        /// <summary>
        /// The events in time order. The log is appended in nearly, but not exactly, time order: an
        /// event is stamped when its request starts and written when it finishes, so a slow audiobook
        /// download or a late click beacon lands a few lines after events that happened after it
        /// (8 of the first 572 lines on the live site). One radix sort over the 8-byte timestamp puts
        /// that right, and being stable it keeps the append order among events stamped the same instant.
        /// </summary>
        public static List<ActivityEvent> InTimeOrder(IList<ActivityEvent> events, out SortOutcome sort)
        {
            sort = OrderByKey(TimeKeysFor(events), TimeWidth);
            var ordered = new List<ActivityEvent>(events.Count);
            foreach (int i in sort.Order)
                ordered.Add(events[i]);
            return ordered;
        }

        /// <summary>
        /// One path per address: the events sorted by time, then - stably - by address. After the
        /// second sort one address's events are next to each other and still in time order, so a
        /// single walk that starts a new path whenever the key changes is all the grouping there is.
        /// <paramref name="sort"/> describes the sort by address; its ByTime is the sort by time.
        /// </summary>
        public static List<VisitorPath> Group(IList<ActivityEvent> events, out SortOutcome sort)
        {
            SortOutcome byTime;
            List<ActivityEvent> inTimeOrder = InTimeOrder(events, out byTime);

            var ips = inTimeOrder.Select(e => e.Ip).ToList();
            int width = WidthFor(ips);
            byte[] keys = KeysFor(ips, width);
            sort = OrderByKey(keys, width);
            sort.ByTime = byTime;

            var paths = new List<VisitorPath>();
            VisitorPath current = null;
            int previous = -1;
            foreach (int i in sort.Order)
            {
                if (current == null || SortCheck.CompareKeys(keys, width, previous, i) != 0)
                {
                    current = new VisitorPath { Ip = inTimeOrder[i].Ip ?? "unknown", Events = new List<ActivityEvent>() };
                    paths.Add(current);
                }
                current.Events.Add(inTimeOrder[i]);
                previous = i;
            }
            return paths;
        }

        /// <summary>Runs of the same step in a row become one step with a count: Home, Home, Home -> Home ×3.</summary>
        public static List<KeyValuePair<string, int>> Collapse(IEnumerable<string> labels)
        {
            var steps = new List<KeyValuePair<string, int>>();
            foreach (string label in labels)
            {
                if (steps.Count > 0 && steps[steps.Count - 1].Key == label)
                    steps[steps.Count - 1] = new KeyValuePair<string, int>(label, steps[steps.Count - 1].Value + 1);
                else
                    steps.Add(new KeyValuePair<string, int>(label, 1));
            }
            return steps;
        }

        /// <summary>"Grouped 1,234 events from 56 addresses with RadixSort.Order: 0.31 ms by time (8-byte keys), then 0.21 ms by address."</summary>
        public static string Describe(SortOutcome sort, int events, int addresses)
        {
            string text = "Grouped " + events.ToString("N0") + " events from " + addresses.ToString("N0")
                          + (addresses == 1 ? " address" : " addresses");
            string widthNote = sort.Width == 16 ? " (16-byte keys, some IPv6)" : "";
            if (sort.ByTime != null && sort.ByTime.Method == sort.Method)
                text += " with " + sort.Method + ": " + Milliseconds(sort.ByTime.Ms) + " by time (8-byte keys), then "
                        + Milliseconds(sort.Ms) + " by address" + widthNote + ".";
            else
                text += " in " + Milliseconds(sort.Ms) + " with " + sort.Method + widthNote + ".";
            if (sort.ByTime != null && sort.ByTime.Problem != null)
                text += " Sorting by time: " + sort.ByTime.Problem + ", so OrderBy stood in.";
            if (sort.Problem != null)
                text += " Sorting by address: " + sort.Problem + ", so OrderBy stood in.";
            return text;
        }

        public static string Milliseconds(double ms)
        {
            return ms < 0.01 ? "under 0.01 ms" : ms < 10 ? ms.ToString("0.00") + " ms" : ms.ToString("N0") + " ms";
        }

        // ---- Self-test ----

        /// <summary>
        /// Runs RadixSort.Order over the awkward cases (nothing, one key, all equal, already sorted,
        /// reversed, random, IPv6-width) and says whether it passes. Null message = all good.
        /// </summary>
        public static string SelfTest()
        {
            var rng = new Random(482);
            var cases = new List<KeyValuePair<string, byte[]>>();
            cases.Add(new KeyValuePair<string, byte[]>("no keys", new byte[0]));
            cases.Add(new KeyValuePair<string, byte[]>("one key", new byte[] { 198, 19, 0, 1 }));

            byte[] same = new byte[50 * 4];
            for (int i = 0; i < 50; i++) { same[i * 4] = 10; same[i * 4 + 3] = 7; }
            cases.Add(new KeyValuePair<string, byte[]>("50 equal keys", same));

            byte[] up = new byte[300 * 4], down = new byte[300 * 4];
            for (int i = 0; i < 300; i++)
            {
                WriteUInt((uint)i * 1000003u, up, i * 4);
                WriteUInt(uint.MaxValue - (uint)i * 1000003u, down, i * 4);
            }
            cases.Add(new KeyValuePair<string, byte[]>("already sorted", up));
            cases.Add(new KeyValuePair<string, byte[]>("reversed", down));

            byte[] random = new byte[2000 * 4];
            for (int i = 0; i < 2000; i++)
                WriteUInt((uint)rng.Next(0, 40), random, i * 4);       // lots of repeats, to test stability
            cases.Add(new KeyValuePair<string, byte[]>("2,000 random keys with repeats", random));

            foreach (var c in cases)
            {
                string problem = Try(c.Value, 4);
                if (problem != null)
                    return c.Key + ": " + problem;
            }

            // 8-byte keys, the way Group sorts by time: 400 timestamps a few seconds apart, shuffled a
            // little (the log's late lines), with some stamped the same instant.
            var stamped = new List<ActivityEvent>();
            DateTime t0 = new DateTime(2026, 10, 19, 12, 0, 0, DateTimeKind.Utc);
            for (int i = 0; i < 400; i++)
                stamped.Add(new ActivityEvent { At = t0.AddSeconds(i / 3 * 7 + rng.Next(-20, 21)) });
            string timeProblem = Try(TimeKeysFor(stamped), TimeWidth);
            if (timeProblem != null)
                return "400 timestamps (8-byte keys): " + timeProblem;

            byte[] wide = new byte[500 * 16];
            for (int i = 0; i < 500; i++)
            {
                wide[i * 16] = 0x20; wide[i * 16 + 1] = 0x01; wide[i * 16 + 2] = 0x0d; wide[i * 16 + 3] = 0xb8;
                wide[i * 16 + 15] = (byte)rng.Next(0, 20);
                wide[i * 16 + 8] = (byte)rng.Next(0, 3);
            }
            string wideProblem = Try(wide, 16);
            return wideProblem == null ? null : "500 IPv6-width keys: " + wideProblem;
        }

        private static string Try(byte[] keys, int width)
        {
            try
            {
                return SortCheck.Problem(keys, width, RadixSort.Order(keys, width));
            }
            catch (NotImplementedException)
            {
                return "not written yet";
            }
            catch (Exception ex)
            {
                return "threw " + ex.GetType().Name + ": " + ex.Message;
            }
        }

        public static void WriteUInt(uint value, byte[] keys, int offset)
        {
            keys[offset] = (byte)(value >> 24);
            keys[offset + 1] = (byte)(value >> 16);
            keys[offset + 2] = (byte)(value >> 8);
            keys[offset + 3] = (byte)value;
        }
    }

    /// <summary>Checks a sorted order the way the assignment asks: does the sort actually work?</summary>
    public static class SortCheck
    {
        public static int CompareKeys(byte[] keys, int width, int a, int b)
        {
            int pa = a * width, pb = b * width;
            for (int j = 0; j < width; j++)
            {
                int diff = keys[pa + j] - keys[pb + j];
                if (diff != 0)
                    return diff;
            }
            return 0;
        }

        /// <summary>
        /// Null when <paramref name="order"/> is a correct stable sort of the keys; otherwise what is
        /// wrong with it. Checks every index appears exactly once, the keys never go down, and equal
        /// keys kept their original order.
        /// </summary>
        public static string Problem(byte[] keys, int width, int[] order)
        {
            int n = keys.Length / width;
            if (order == null)
                return "returned null";
            if (order.Length != n)
                return "returned " + order.Length.ToString("N0") + " positions for " + n.ToString("N0") + " keys";

            var seen = new bool[n];
            for (int r = 0; r < n; r++)
            {
                int i = order[r];
                if (i < 0 || i >= n)
                    return "position " + r + " holds index " + i + ", which isn't a key";
                if (seen[i])
                    return "index " + i + " appears twice";
                seen[i] = true;
            }
            for (int r = 1; r < n; r++)
            {
                int c = CompareKeys(keys, width, order[r - 1], order[r]);
                if (c > 0)
                    return "positions " + (r - 1) + " and " + r + " are out of order";
                if (c == 0 && order[r - 1] > order[r])
                    return "equal keys at positions " + (r - 1) + " and " + r + " swapped their original order (not stable)";
            }
            return null;
        }

        /// <summary>How many neighbouring pairs of equal keys came out in the wrong original order - 0 for a stable sort.</summary>
        public static int StabilityBreaks(byte[] keys, int width, int[] order)
        {
            int breaks = 0;
            for (int r = 1; r < order.Length; r++)
                if (order[r - 1] > order[r] && CompareKeys(keys, width, order[r - 1], order[r]) == 0)
                    breaks++;
            return breaks;
        }
    }

    /// <summary>
    /// How RadixSort.Order tells the HW4 progress bar how far it has got (extra credit). Order keeps
    /// its signature; it just calls Report now and then:
    ///
    ///     // in the placement loop of pass p (0 for the first pass), walking j from n - 1 down to 0:
    ///     if (j % SortProgress.Every == 0)
    ///         SortProgress.Report((long)p * n + (n - j), (long)width * n);
    ///
    /// Only the untimed progress run (RadixProgressRun) listens. Everywhere else - the timed
    /// benchmark, the page, the dashboard - nobody is listening, and a report costs one check of a
    /// field every 65,536 elements, which doesn't show in the timings.
    /// </summary>
    public static class SortProgress
    {
        /// <summary>Report about this often (in elements), not on every element.</summary>
        public const int Every = 65536;

        // One per thread: the progress run sorts on its own thread, so a page request sorting
        // visitor paths at the same moment can't move the bar.
        [ThreadStatic] private static Action<long, long> listener;

        /// <summary>
        /// <paramref name="done"/> of <paramref name="total"/> units of work finished. Any unit works
        /// as long as it's consistent; elements placed (out of width × n) is the natural one.
        /// </summary>
        public static void Report(long done, long total)
        {
            Action<long, long> heard = listener;
            if (heard != null)
                heard(done, total);
        }

        /// <summary>Runs <paramref name="work"/> with <paramref name="onReport"/> hearing every Report made on this thread.</summary>
        public static T Listen<T>(Action<long, long> onReport, Func<T> work)
        {
            Action<long, long> before = listener;
            listener = onReport;
            try
            {
                return work();
            }
            finally
            {
                listener = before;
            }
        }
    }
}

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Web;
using System.Web.Caching;
using System.Web.Hosting;
using System.Web.Script.Serialization;

namespace WebApplication1
{
    /// <summary>
    /// Where the HW4 page keeps its own files: App_Data\LinearSort. App_Data is never served to
    /// browsers and is git-ignored, same as App_Data\Activity.
    /// </summary>
    public static class LinearSortFiles
    {
        public static string Dir()
        {
            string dir = HostingEnvironment.MapPath("~/App_Data/LinearSort");
            Directory.CreateDirectory(dir);
            return dir;
        }

        public static string PathOf(string name)
        {
            return Path.Combine(Dir(), name);
        }
    }

    /// <summary>
    /// Simulated traffic for the HW4 page: made-up visitors and bots walking the site's real pages,
    /// written in the activity log's own format (one ActivityEvent per JSON line) but to
    /// App_Data\LinearSort\demo.jsonl - never to App_Data\Activity, so the real dashboard and its
    /// 50 MB-a-day cap never see it. Simulated addresses come from 198.19.0.0/16, part of the range
    /// set aside for benchmark testing (RFC 2544), so they can't be anybody's real address.
    /// </summary>
    public static class DemoTraffic
    {
        public const int MaxEvents = 100000;
        private const string FileName = "demo.jsonl";
        private static readonly object Gate = new object();
        private static readonly JavaScriptSerializer Serializer = new JavaScriptSerializer();

        // Which page a visitor tends to go to next. Repeating a page in a list makes it likelier.
        private static readonly Dictionary<string, string[]> Next = new Dictionary<string, string[]>
        {
            { "homepage.aspx", new[] { "Public_ViewBooks.aspx", "Public_ViewBooks.aspx", "Public_ViewAudiobooks.aspx", "Public_ViewAudiobooks.aspx", "Public_Blog.aspx", "AboutMe.aspx", "Projects.aspx", "Zombie_Riddle.aspx" } },
            { "Public_ViewBooks.aspx", new[] { "ReadBook.aspx", "ReadBook.aspx", "ReadBook.aspx", "homepage.aspx", "Public_ViewAudiobooks.aspx" } },
            { "ReadBook.aspx", new[] { "Public_ViewBooks.aspx", "Public_ViewBooks.aspx", "ReadBook.aspx" } },
            { "Public_ViewAudiobooks.aspx", new[] { "ListenAudiobook.aspx", "ListenAudiobook.aspx", "ListenAudiobook.aspx", "homepage.aspx" } },
            { "ListenAudiobook.aspx", new[] { "Public_ViewAudiobooks.aspx", "Public_ViewAudiobooks.aspx", "ListenAudiobook.aspx" } },
            { "Public_Blog.aspx", new[] { "BlogPost.aspx", "BlogPost.aspx", "BlogPost.aspx", "homepage.aspx" } },
            { "BlogPost.aspx", new[] { "Public_Blog.aspx", "Public_Blog.aspx", "homepage.aspx" } },
            { "AboutMe.aspx", new[] { "Projects.aspx", "Projects.aspx", "homepage.aspx" } },
            { "Projects.aspx", new[] { "linearsort/default.aspx", "linearsort/default.aspx", "AboutMe.aspx", "homepage.aspx" } },
            { "Zombie_Riddle.aspx", new[] { "homepage.aspx", "Projects.aspx" } },
            { "linearsort/default.aspx", new[] { "Projects.aspx", "homepage.aspx" } }
        };

        private static readonly string[] Landing = { "homepage.aspx", "homepage.aspx", "homepage.aspx", "Public_Blog.aspx", "Projects.aspx", "linearsort/default.aspx" };
        private static readonly string[] Books = { "Jane Austen/Pride and Prejudice.epub", "Mary Shelley/Frankenstein.epub", "Herman Melville/Moby Dick.epub", "Lewis Carroll/Alices Adventures in Wonderland.epub", "Bram Stoker/Dracula.epub" };
        private static readonly string[] Audiobooks = { "Jules Verne/Around the World in 80 Days", "Arthur Conan Doyle/The Hound of the Baskervilles", "Mark Twain/Tom Sawyer" };

        /// <summary>
        /// Makes <paramref name="count"/> events spread over the past <paramref name="days"/> days,
        /// oldest first give or take - the same order the real log is in. A few heavy visitors and many light ones,
        /// like real traffic; about one visitor in seven is a bot that rattles through pages quickly,
        /// which comes to roughly a third of the events (the real log was 21 bot lines in 73).
        /// </summary>
        public static List<ActivityEvent> Generate(int count, int days, Random rng)
        {
            count = Math.Max(0, Math.Min(count, MaxEvents));
            int visitors = Math.Max(10, count / 12);
            DateTime end = DateTime.UtcNow;
            double spanSeconds = days * 86400.0;
            var events = new List<ActivityEvent>(count + 64);

            while (events.Count < count)
            {
                // u * u leans towards small numbers, so low-numbered visitors come back far more often.
                double u = rng.NextDouble();
                int v = (int)(u * u * visitors);
                bool bot = v % 7 == 3;
                int host = v + 1;       // 198.19.0.1 upwards; .0.0 reads like a network, not a visitor
                string ip = "198.19." + ((host >> 8) & 255) + "." + (host & 255);

                DateTime at = end.AddSeconds(-rng.NextDouble() * spanSeconds);
                string page = bot ? "homepage.aspx" : Landing[rng.Next(Landing.Length)];
                int steps = bot ? rng.Next(4, 16) : 1 + Geometric(rng, 0.28, 19);

                for (int s = 0; s < steps && events.Count < count && at <= end; s++)
                {
                    events.Add(Event(at, "view", page, ItemFor(page, rng), ip, v, bot));
                    if (!bot && page == "ReadBook.aspx" && rng.NextDouble() < 0.5)
                        events.Add(Event(at.AddSeconds(4), ActivityLog.BookRead, "BookFile.ashx", events[events.Count - 1].Item, ip, v, bot));
                    else if (!bot && page == "ListenAudiobook.aspx" && rng.NextDouble() < 0.6)
                        events.Add(Event(at.AddSeconds(6), ActivityLog.Listen, "AudiobookFile.ashx", events[events.Count - 1].Item, ip, v, bot));

                    at = at.AddSeconds(bot ? rng.Next(1, 4) : rng.Next(5, 120));
                    string[] choices = Next[page];
                    page = choices[rng.Next(choices.Length)];
                }
            }

            if (events.Count > count)
                events.RemoveRange(count, events.Count - count);
            // Sessions were made one at a time, so put them back in time order - roughly, like the
            // real log: a few events are left a little late, the way a slow download's line lands in
            // the real file after events that happened after it. Group sorts by time itself.
            events = events.OrderBy(e => e.At).ToList();
            for (int i = 0; i + 1 < events.Count; i += 40)
            {
                ActivityEvent late = events[i];
                events[i] = events[i + 1];
                events[i + 1] = late;
            }
            return events;
        }

        private static ActivityEvent Event(DateTime at, string kind, string page, string item, string ip, int visitor, bool bot)
        {
            return new ActivityEvent
            {
                At = at,
                Kind = kind,
                Page = page,
                Item = item,
                Status = 200,
                Audience = bot ? ActivityLog.Bot : ActivityLog.Visitor,
                Visitor = "sim-" + visitor,
                Ip = ip,
                Agent = bot ? "SimBot/1.0 (simulated)" : "Mozilla/5.0 (simulated visitor)"
            };
        }

        private static string ItemFor(string page, Random rng)
        {
            switch (page)
            {
                case "ReadBook.aspx": return Books[rng.Next(Books.Length)];
                case "ListenAudiobook.aspx": return Audiobooks[rng.Next(Audiobooks.Length)];
                case "BlogPost.aspx": return rng.Next(1, 6).ToString();
                default: return null;
            }
        }

        // How many extra pages a visitor looks at: each one has a `stop` chance of being their last.
        private static int Geometric(Random rng, double stop, int max)
        {
            int k = 0;
            while (k < max && rng.NextDouble() > stop)
                k++;
            return k;
        }

        // ---- The file ----

        /// <summary>Throws away the old simulated traffic and writes a fresh batch.</summary>
        public static void Replace(int count)
        {
            List<ActivityEvent> events = Generate(count, 7, new Random());
            string file = LinearSortFiles.PathOf(FileName);
            string temp = file + ".tmp";
            lock (Gate)
            {
                using (var writer = new StreamWriter(temp, false, new UTF8Encoding(false)))
                {
                    foreach (ActivityEvent e in events)
                        writer.WriteLine(Serializer.Serialize(e));
                }
                if (File.Exists(file))
                    File.Delete(file);
                File.Move(temp, file);
            }
        }

        public static void Clear()
        {
            lock (Gate)
            {
                string file = LinearSortFiles.PathOf(FileName);
                if (File.Exists(file))
                    File.Delete(file);
            }
        }

        /// <summary>The simulated events, oldest first. Cached until the file changes.</summary>
        public static List<ActivityEvent> Load()
        {
            var info = new FileInfo(LinearSortFiles.PathOf(FileName));
            if (!info.Exists)
                return new List<ActivityEvent>();

            string key = "LinearSort.Demo." + info.Length + "." + info.LastWriteTimeUtc.Ticks;
            var cached = HttpRuntime.Cache[key] as List<ActivityEvent>;
            if (cached != null)
                return cached;

            var list = new List<ActivityEvent>();
            lock (Gate)
            {
                foreach (string line in File.ReadLines(info.FullName))
                {
                    if (line.Length == 0)
                        continue;
                    try
                    {
                        var e = Serializer.Deserialize<ActivityEvent>(line);
                        if (e != null)
                            list.Add(e);
                    }
                    catch { /* a damaged line costs that line only */ }
                }
            }
            HttpRuntime.Cache.Insert(key, list, null, Cache.NoAbsoluteExpiration, TimeSpan.FromMinutes(30));
            return list;
        }
    }

    /// <summary>
    /// Everything the public HW4 page shows about traffic, built at most once a minute. Simulated
    /// traffic only: the site's real log is read by the admin dashboard (admin_activity.aspx), which
    /// groups it into paths with the same VisitorPaths.Group, and never by this public page.
    /// </summary>
    public class PublicActivity
    {
        public List<ActivityEvent> Events { get; private set; }     // the simulated traffic, as it lies in demo.jsonl
        public List<VisitorPath> Paths { get; private set; }
        public SortOutcome Sort { get; private set; }
        public double OrderByMs { get; private set; }
        public double ArraySortMs { get; private set; }
        public DateTime BuiltAt { get; private set; }

        private static readonly object Gate = new object();
        private const string CacheKey = "LinearSort.Public";

        public static PublicActivity Get()
        {
            var cached = HttpRuntime.Cache[CacheKey] as PublicActivity;
            if (cached != null)
                return cached;
            lock (Gate)
            {
                cached = HttpRuntime.Cache[CacheKey] as PublicActivity;
                if (cached != null)
                    return cached;
                PublicActivity built = Build();
                HttpRuntime.Cache.Insert(CacheKey, built, null, DateTime.UtcNow.AddMinutes(1), Cache.NoSlidingExpiration);
                return built;
            }
        }

        public static void Forget()
        {
            HttpRuntime.Cache.Remove(CacheKey);
        }

        private static PublicActivity Build()
        {
            List<ActivityEvent> events = DemoTraffic.Load();

            SortOutcome sort;
            List<VisitorPath> paths = VisitorPaths.Group(events, out sort);

            // The sort by address done the comparison-sort ways, for the line under the panel.
            byte[] keys = VisitorPaths.KeysFor(events.Select(e => e.Ip).ToList(), sort.Width);
            var watch = System.Diagnostics.Stopwatch.StartNew();
            VisitorPaths.StableOrder(keys, sort.Width);
            double orderByMs = watch.Elapsed.TotalMilliseconds;
            double arraySortMs = 0;
            if (sort.Width == 4)
            {
                uint[] numbers = new uint[events.Count];
                for (int i = 0; i < numbers.Length; i++)
                    numbers[i] = (uint)(keys[i * 4] << 24 | keys[i * 4 + 1] << 16 | keys[i * 4 + 2] << 8 | keys[i * 4 + 3]);
                int[] index = Enumerable.Range(0, numbers.Length).ToArray();
                watch.Restart();
                Array.Sort(numbers, index);
                arraySortMs = watch.Elapsed.TotalMilliseconds;
            }

            return new PublicActivity
            {
                Events = events,
                Paths = paths,
                Sort = sort,
                OrderByMs = orderByMs,
                ArraySortMs = arraySortMs,
                BuiltAt = DateTime.Now
            };
        }
    }
}