#define MAX_LENGTH 3

enum DigitUnit
{
    OneDigit = 1,
    TenDigit = 10,
    HundredDigit = 100,
    ThousandDigit = 1000,

    MaxDigit = 100000,
};

//Trie node
struct RomeTrieNode
{
    char Latin;
    int Value;
    int NoOfChild;
    struct RomeTrieNode* Next[MAX_LENGTH];
};


/*

Trie illustration:

Latin Letter(Roman Number, Integer Number, Node Index)

                I(I,1,0)
                │        
    ┌───────────┼───────────┐
    │           │           │
    │           │           │
    I(II,2,2)   V(IV,4,3)   X(IX,9,4)
    │
    │
    I(III,3,5)
    
    
    V(V,5,1)───I(VI,6,6)───I(VII,7,7)───I(VIII,8,8)

*/
//Tries for each digit
struct RomeTrieNode Ones[9] = 
{
	/* Node 0 */    {'I', 1, 3, {Ones+2,Ones+3,Ones+4}},
	/* Node 1 */    {'V', 5, 1, {Ones+6, 0, 0}},
	/* Node 2 */    {'I', 2, 1, {Ones+5, 0, 0}},
	/* Node 3 */    {'V', 4, 0, {0, 0, 0}},
	/* Node 4 */    {'X', 9, 0, {0, 0, 0}},
	/* Node 5 */    {'I', 3, 0, {0, 0, 0}},
	/* Node 6 */    {'I', 6, 1, {Ones+7, 0, 0}},
	/* Node 7 */    {'I', 7, 1, {Ones+8, 0, 0}},
	/* Node 8 */    {'I', 8, 0, {0, 0, 0}},
};
struct RomeTrieNode Tens[9] = 
{
	/* Node 0 */    {'X', 10, 3, {Tens+2,Tens+3,Tens+4}},
	/* Node 1 */    {'L', 50, 1, {Tens+6, 0, 0}},
	/* Node 2 */    {'X', 20, 1, {Tens+5, 0, 0}},
	/* Node 3 */    {'L', 40, 0, {0, 0, 0}},
	/* Node 4 */    {'C', 90, 0, {0, 0, 0}},
	/* Node 5 */    {'X', 30, 0, {0, 0, 0}},
	/* Node 6 */    {'X', 60, 1, {Tens+7, 0, 0}},
	/* Node 7 */    {'X', 70, 1, {Tens+8, 0, 0}},
	/* Node 8 */    {'X', 80, 0, {0, 0, 0}},
};struct RomeTrieNode Hundreds[9] = 
{
	/* Node 0 */    {'C', 100, 3, {Hundreds+2,Hundreds+3,Hundreds+4}},
	/* Node 1 */    {'D', 500, 1, {Hundreds+6, 0, 0}},
	/* Node 2 */    {'C', 200, 1, {Hundreds+5, 0, 0}},
	/* Node 3 */    {'D', 400, 0, {0, 0, 0}},
	/* Node 4 */    {'M', 900, 0, {0, 0, 0}},
	/* Node 5 */    {'C', 300, 0, {0, 0, 0}},
	/* Node 6 */    {'C', 600, 1, {Hundreds+7, 0, 0}},
	/* Node 7 */    {'C', 700, 1, {Hundreds+8, 0, 0}},
	/* Node 8 */    {'C', 800, 0, {0, 0, 0}},
};
struct RomeTrieNode  Thousands[9] = 
{
	/* Node 0 */    {'M', 1000, 1, {Thousands+1,0, 0}},
	/* Node 1 */    {'M', 2000, 1, {Thousands+2, 0, 0}},
	/* Node 2 */    {'M', 3000, 0, {0, 0, 0}},
};


//find the trie root base on the begin letter
//if the digit that already analyzed is less than than next digit,
//or the latin letter is not a valid roman letter,
//empty pointer would be returned
struct RomeTrieNode* FindBegin(char latin, DigitUnit* curDigit)
{
    DigitUnit nextDigit = MaxDigit;
    struct RomeTrieNode* head = 0;
    switch(latin)
    {
        case 'I': 
            nextDigit = OneDigit;
            head = Ones;
			break;
        case 'V': 
            nextDigit = OneDigit;
            head = Ones+1;
			break;
        case 'X': 
            nextDigit = TenDigit;
            head = Tens;
			break;
        case 'L': 
            nextDigit = TenDigit;
            head = Tens+1;
            break;
        case 'C': 
            nextDigit = HundredDigit;
            head =  Hundreds;
			break;
        case 'D': 
            nextDigit = HundredDigit;
            head =  Hundreds+1;
			break;
        case 'M': 
            nextDigit = ThousandDigit;
            head = Thousands;
			break;

        default: return 0;//invalid latin letter for roman number
    }

    //check if the order of latin letter is correct
    if (nextDigit < *curDigit)
    {
       *curDigit = nextDigit;//update current digit
       return head;
    }
	
	//else, the order of latin letter in roman number is misranged
    return 0;
}

int RomeToInteger(char* roman)
{
    //the string is empty
	if (*roman == '\0') return 0;

    int value = 0;
    struct RomeTrieNode* curNode = 0;
    struct RomeTrieNode* nextNode = 0;
    DigitUnit curDigit = MaxDigit;  
	
    //find the begin root for current digit
    curNode = FindBegin(*roman,&curDigit);
    //invalid latin letter for roman number,
    //or the order of latin letter is not correct
    if (!curNode) return 0;

	for(char* r = roman+1; *r; ++r)
    {
        nextNode = 0;
        //search for next on trie
        for (int i = 0; i < curNode->NoOfChild ; ++i)
            if (curNode->Next[i]->Latin == *r)
			{
				nextNode = curNode->Next[i];
				break;
			}

        if (!nextNode)
        {
            value += curNode->Value; //add up the value
			//a new begin digit
            curNode = FindBegin(*r, &curDigit);
            if (!curNode) return 0;
        }
		else
		{
			curNode = nextNode;
		}
    }

	value += curNode->Value; //add up the value
	
	return value;
}


int main(int argc, char** argv)
{
    char roman[10] ="MMXII";

    printf("%s: %d",roman, RomeToInteger(roman));

    return 0;
}