using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Codifica_aritmetica
{
    class Program
    {
        private static Dictionary<int, double> simboli = new Dictionary<int, double>();
        static void Main(string[] args)
        {
            // Aggiuge i simboli al mio dizionario. Ogni simbolo è associato alla sua propbabilità.
            simboli.Add(0, 0.9);
            simboli.Add(1, 0.1);

            Console.WriteLine("Inserisci la stringa da codificare secondo la codifica aritmetica:<");

            // Recupera la stringa da codificare da console.
            string stringa = Console.ReadLine();

            // Codifica la stringa.
            string intervalloDiCodifica = IntervalloCodificaAritmetica(stringa).ToString();

            // Stampa la codifica su schermo.
            Console.WriteLine("La stringa codifica è:");
            Console.WriteLine(intervalloDiCodifica);

            // Aspetta la pressione di un tasto per terminare il programma.
            Console.ReadKey();
        }

        private static double Cdf(double x)
        {
            // La cdf parte con probabilità zero.
            double probabilità = 0;

            // Il ciclo scorre tutti gli elementi inseriti nel dizionario dei simboli.
            //
            //         /|\
            //        1 |- - - - - - -°
            //      1/2 | - - °   !   |
            //  ________|_____|___!___|______\
            //          |     A   x   B      /
            //
            // Ad ogni passo del ciclo viene controllato se X è a sinistra o a destra di 'simbolo.key'.
            // Se è a destra incremento la probabilità di 'simbolo.key' del valore 'simbolo.value'.
            // Se è a sinistra allora ritorno la probabilità che ho calcolato fin'ora.
            // Dato che la cdf è continua a destra è < e non <=
            //
            // Utilizzando la figura soprastante mostro un esempio:
            // - La prima esecuzione del ciclo controllo la posizione di X rispetto al simbolo A.
            // - In questo caso X è a destra, quindi la cdf(x) vale almeno cdf(A),
            //   quindi aggiungo a 'probabilità' la probabilità del simbolo A ovvero 'simbolo.value'.
            // - Termina l'esecuzione della prima esecuzione del ciclo.
            // - La seconda esecuzione del ciclo controllo la posizione di X rispetto al simbolo B.
            // - In questo caso X è a sinistra rispetto a B: dato che la cdf è costante nell'intervallo [A,B)
            //   allora termino il ciclo e restituisco il valore di 'probabilità' precedentemente calcolato.
            foreach (var simbolo in simboli)
            {
                if (x < simbolo.Key)
                {
                    return probabilità;
                }
                else
                {
                    probabilità += simbolo.Value;
                }
            }

            // Se l'esecuzione raggiunge questo punto la probabilità deve essere 1. Se questo non fosse verificato,
            // la somma delle probabilità dei simboli non è uno, quindi probabilmente sono state inserite non corretamente.
            if (probabilità != 1)
            {
                Console.WriteLine("!!! I simboli non hanno somma delle probabilità uguale a 1 !!!");
            }
            return probabilità;
        }

        private static Intervallo IntervalloCodificaAritmetica(string stringa)
        {
            // Definisce l'intervallo di partenza. Variabile utilizzata anche per tener conto dell'intervallo precedente.
            Intervallo intervalloPrecedente = new Intervallo(0, 1);

            if (string.IsNullOrEmpty(stringa))
            {
                Console.WriteLine("La stringa non deve essere vuota.");

                // Risultato per indicare che si è verificato un errore.
                return new Intervallo(-1, -1);
            }

            int i = 0;
            double nuovoInizio = 0;
            double nuovaFine = 0;

            // Scorre la stringa dal primo carattere all'ultimo.
            for (i = 0; i < stringa.Length; i++)
            {
                // Converte l'ultimo carattere della stringa in un intero.
                int simbolo = stringa[i] - '0';

                // Controlla che il simbolo sia contenuto nel dizionario dei simboli.
                if (!simboli.ContainsKey(simbolo))
                {
                    Console.WriteLine("Il simbolo " + stringa[i] + " non è contenuto nel dizionario dei simboli.");

                    // Risultato per indicare che si è verificato un errore.
                    return new Intervallo(-1, -1);
                }

                // Applico l'algoritmo per calcolare i nuovi estremi dell'intervallo.
                nuovoInizio = intervalloPrecedente.Inizio + (intervalloPrecedente.Fine - intervalloPrecedente.Inizio) * Cdf(simbolo - 1);
                nuovaFine = intervalloPrecedente.Inizio + (intervalloPrecedente.Fine - intervalloPrecedente.Inizio) * Cdf(simbolo);

                // Salvo i risultati.
                intervalloPrecedente.Inizio = nuovoInizio;
                intervalloPrecedente.Fine = nuovaFine;
            }

            return intervalloPrecedente;
        }
    }

    // Rappresenta un intervallo [Inizio, Fine].
    public class Intervallo
    {
        public double Inizio { get; set; }
        public double Fine { get; set; }

        public Intervallo(double i, double f)
        {
            Inizio = i;
            Fine = f;
        }

        // Sovrascrive la funzione ToString fornita a tutti gli oggetti di C#.
        public override string ToString()
        {
            return "[" + Inizio + "," + Fine + "]";
        }
    }
}