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

namespace RomanNumerals
{
    class Program
    {
        static void Main( string[] args )
        {
            //int => roman requires that the higher numerical values appear first
            List<NumeralEntry> numerals = new List<NumeralEntry>();
            numerals.Add(new NumeralEntry(1000,  "M"));
            //numerals.Add(new NumeralEntry( 999, "IM")); //non-standard roman numeral
            //numerals.Add(new NumeralEntry( 995, "VM")); //non-standard roman numeral
            //numerals.Add(new NumeralEntry( 990, "XM")); //non-standard roman numeral
            //numerals.Add(new NumeralEntry( 950, "LM")); //non-standard roman numeral
            numerals.Add(new NumeralEntry( 900, "CM"));
            numerals.Add(new NumeralEntry( 500,  "D"));
            //numerals.Add(new NumeralEntry( 499, "ID")); //non-standard roman numeral
            //numerals.Add(new NumeralEntry( 495, "VD")); //non-standard roman numeral
            //numerals.Add(new NumeralEntry( 490, "XD")); //non-standard roman numeral
            //numerals.Add(new NumeralEntry( 450, "LD")); //non-standard roman numeral
            numerals.Add(new NumeralEntry( 400, "CD"));
            numerals.Add(new NumeralEntry( 100,  "C"));
            //numerals.Add(new NumeralEntry(  99, "IC")); //non-standard roman numeral
            //numerals.Add(new NumeralEntry(  95, "VC")); //non-standard roman numeral
            numerals.Add(new NumeralEntry(  90, "XC"));
            numerals.Add(new NumeralEntry(  50,  "L"));
            //numerals.Add(new NumeralEntry(  49, "IL")); //non-standard roman numeral
            numerals.Add(new NumeralEntry(  45, "VL"));
            numerals.Add(new NumeralEntry(  40, "XL"));
            numerals.Add(new NumeralEntry(  10,  "X"));
            numerals.Add(new NumeralEntry(   9, "IX"));
            numerals.Add(new NumeralEntry(   5,  "V"));
            numerals.Add(new NumeralEntry(   4, "IV"));
            numerals.Add(new NumeralEntry(   1,  "I"));

            List<NumeralEntry> reverse = new List<NumeralEntry>(numerals);

            // roman => int requires that the longer strings appear first
            // (or at least the ones you want to match first appear first)
            reverse.Sort(( x, y ) => y.Numeral.CompareTo(x.Numeral));

            Console.WriteLine(ToNumerals(numerals, 1999));
            Console.WriteLine(ToNumerals(numerals, 2008));
            Console.WriteLine(ToNumerals(numerals, 1990));
            Console.WriteLine(ToNumerals(numerals, 1979));
            Console.WriteLine(ToNumerals(numerals, 4));
            Console.WriteLine(ToNumerals(numerals, 58));
            Console.WriteLine(ToNumerals(numerals, 2374));
            Console.WriteLine(ToNumerals(numerals, 2700));

            Console.WriteLine(ToNumerals(numerals, 1900));

            Console.WriteLine(ParseNumerals(reverse, "MCM"));
            Console.WriteLine(ParseNumerals(reverse, "MCMLXX"));
            Console.WriteLine(ParseNumerals(reverse, "IV"));
            Console.WriteLine(ParseNumerals(reverse, "CX"));

            Console.ReadKey();
        }

        private static string ToNumerals( IList<NumeralEntry> numerals, int value )
        {
            StringBuilder builder = new StringBuilder();
            int index = 0;

            while ( value > 0 )
            {
                while ( numerals[index].Value > value )
                {
                    index++;
                }

                value -= numerals[index].Value;
                builder.Append(numerals[index].Numeral);
            }

            string str = builder.ToString();
            return str;
        }

        private static int ParseNumerals( IList<NumeralEntry> numerals, string str )
        {
            int value = 0;

            for ( int i = 0; i < str.Length; )
            {
                bool found = false;
                for ( int j = 0; j < numerals.Count; j++ )
                {
                    if ( Matches(str, numerals[j].Numeral, i) )
                    {
                        i += numerals[j].Numeral.Length;
                        value += numerals[j].Value;
                        found = true;
                        break;
                    }
                }
                if ( !found )
                    throw new FormatException(string.Format("Invalid numeral {0}", str[i]));
            }

            return value;
        }

        private static bool Matches( string str, string numeral, int index )
        {
            return str.Substring(index).StartsWith(numeral, StringComparison.OrdinalIgnoreCase);
        }

        private class NumeralEntry
        {
            public readonly int Value;
            public readonly string Numeral;

            public NumeralEntry(int value, string numeral)
            {
                Value = value;
                Numeral = numeral;
            }
        }
    }
}