using System;

using System.Linq;

using System.Collections.Generic;

public class Program

{

    public sealed class Picker<T> 

    {

        private const int MaxRetries = 2;

        private const int CleanupTriggerDenominator = 4;

        public int Samples { get; set; }

        public int Scanned { get; set; }

​

        private readonly Random random = new();

        private List<T> items = new();

        private List<double> weights = new();

        private List<double> weightCumulations = new();

        private int pickedCount = 0;

        private List<bool> picked = new();

​

        public Picker(IEnumerable<(T Item, double Weight)> pairs)

        {

            var cumulation = 0.0;

            foreach(var (item, weight) in pairs)

            {

                cumulation += weight;

                items.Add(item);

                weights.Add(weight);

                weightCumulations.Add(cumulation);

                picked.Add(false);

            }

        }

​

        public T Pick()

        {

            var i = GetRandomIndex();

            var count = 0;

            while (picked[i])

            {

                if (++count == MaxRetries || pickedCount > items.Count / CleanupTriggerDenominator) {

                    Cleanup();

                }

                i = GetRandomIndex();

            }

            picked[i] = true;

            pickedCount++;

            return items[i];

        }

​

        private int GetRandomIndex() 

        {

            Samples++;

            var r = random.NextDouble() * weightCumulations[^1];

            var i = weightCumulations.BinarySearch(r);

            if (i < 0) {

                return ~i;

            } else {

                return i;

            }

        }

​

        private void Cleanup()

        {

            var newItems = new List<T>();

            var newWeights = new List<double>();

            var newWeightCumulations = new List<double>();

            var newPicked = new List<bool>();

​

            var cumulation = 0.0;

            for(var i=0; i<items.Count; i++) {

                Scanned++;

                var item = items[i];

                var weight = weights[i];

                cumulation += weight;

                newItems.Add(item);

                newWeights.Add(weight);

                newWeightCumulations.Add(cumulation);

                newPicked.Add(false);

            }

            items = newItems;

            weights = newWeights;

            weightCumulations = newWeightCumulations;

            picked = newPicked;

            pickedCount = 0;

        }

    }

    public static void Main()

    {

        var picker = new Picker<int>(Enumerable.Range(0, 100).Select(x => (x, 1.0)));

        for(var i=0; i < 100; i++) {

            picker.Pick();

        }

        Console.WriteLine("GetRandomIndex: {0}", picker.Samples);

        Console.WriteLine("Scanned: {0}", picker.Scanned);

    }

}