/**
 * Convert a roman numeral into equivalent decimal number
 * If the number is invalid numeral or out of range (1-1000)
 * return 0
 * Also check: http://codepad.org/2LG4SbjJ
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* #define const */

int rtoimap[128] = {0};     /* Roman to indices */

enum /* ERomanIntLetters */ {
  I = 0, V,X,L,C,M,D,
  TOTAL_ROMAN_INT_TYPE
};

/**
 * Idea is, tree has many children
 * Each children correspond to one next roman numeral
 */
struct tree_node {
  int value;
  struct tree_node *children[TOTAL_ROMAN_INT_TYPE];
};

struct tree_node *head;

/* Export */
int toDecimal(char *rn);

/* Locals */
static void init_roman(void);
static struct tree_node *getTreeNode(void);
static void freeTreeNode(struct tree_node *h);
static void registerNumber(int n, char *h, char *t, char *u);
static void clean_roman(void);

/**
 * Register a roman numeral into tree for fast search
 *
 * @param [in] n Number
 * @param [in] h, t, u Roman numeral string is formed by concatenating these strings
 */
static void registerNumber(int n, char *h, char *t, char *u) {
  struct tree_node *cur = head;
  char *rns[] = {h, t, u, 0};
  char **prns = rns;
  if(!n || !h || !t || !u || !cur) return;
  while(*prns) {
    char *s = *prns;
    while(*s != '\0') {
      const int index = rtoimap[*s];
      assert(-1 != index);
      if(NULL == cur->children[index]) cur->children[index] = getTreeNode();
      cur = cur->children[index];
      ++s;
    }
    ++prns;
  }
  assert(NULL != cur);
  cur->value = n;
}

/**
 * Get a new tree node
 * This node is initialized to zero value and all children are initialized to NULL
 *
 * @return New node
 * @warning Caller should free the memory of node by calling free
 */
static struct tree_node *getTreeNode(void) {
  int i;
  struct tree_node *ret = malloc( sizeof(struct tree_node) );
  ret->value = 0;
  for(i = 0; i < TOTAL_ROMAN_INT_TYPE; ++i) ret->children[i] = NULL;
  return ret;
}

/**
 * Delete a tree node
 * Recursively delete all children of a node by freeing their memory
 *
 * @param [in] h Head node to release
 */
static void freeTreeNode(struct tree_node *h) {
  int i;
  for(i = 0; i < TOTAL_ROMAN_INT_TYPE; ++i) {
    struct tree_node *c = h->children[i];
    if(c) freeTreeNode(c);
    free(c);
  }
}

/**
 * Inititalize roman lookup tree
 */
static void init_roman(void) {
  int n, h, t, u;
  char *units   [] = {"", "I", "II", "III", "IV",
                          "V", "VI", "VII", "VIII", "IX"};
  char *tens    [] = {"", "X", "XX", "XXX", "XL",
                          "L", "LX", "LXX", "LXXX", "XC"};
  char *hundreds[] = {"", "C", "CC", "CCC", "CD",
                          "D", "DC", "DCC", "DCCC", "CM"};

  for(n = 0; n < 128; ++n) rtoimap[n] = -1;
  rtoimap['I'] = I;
  rtoimap['V'] = V;
  rtoimap['X'] = X;
  rtoimap['L'] = L;
  rtoimap['C'] = C;
  rtoimap['M'] = M;
  rtoimap['D'] = D;

  head = getTreeNode();

  for(n = 0, h = 0; h < 10; ++h)
  for(t = 0; t < 10; ++t)
  for(u = 0; u < 10; ++u)
  {
    registerNumber(n++, hundreds[h], tens[t], units[u]);
  }
  registerNumber(n, "M", tens[0], units[0]); /* Hack */
/* #define INCLUDE_EXTENDED_LIST */
#ifdef INCLUDE_EXTENDED_LIST
  registerNumber(4, hundreds[0], tens[0], "IIII"); /* Found on the dial pads of clocks */
#endif
}

/**
 * Cleanup roman lookup tree
 */
static void clean_roman(void) {
  freeTreeNode(head);
  free(head);
  head = NULL;
}

/**
 * Convert a string to roman decimal
 *
 * @param [in] rn_string Roman numeral string to convert
 * @return Equivalent decimal number
 */
int toDecimal(char *rn_string) {
  char *rn = rn_string;
  struct tree_node *cur = head;
  if(!rn || !cur) return 0;
  while(*rn != '\0') {
    const int index = rtoimap[*rn++];
    if(-1 == index) cur = NULL;
    else cur = cur->children[index];
    if(!cur) {
      cur = head;
      break;
    }
  }
  printf("%s: %d\n", rn_string, cur->value);
  return cur->value;
}

/**
 * Entry point of the program (For unit testing)
 *
 * @param [in] argc Command line argument count
 * @param [in] argv Command line argument vector
 * @return Program status
 */
int main(int argc, char *const *argv) {
  init_roman();
  if(argc > 1) {
    int i;
    for(i = 1; i < argc; ++i) toDecimal(argv[i]);
  } else { // dummy run
    toDecimal("Mohit");
    toDecimal("IX");
    toDecimal("X");
    toDecimal("IXI");
    toDecimal("XL");
    toDecimal("IIII");
    toDecimal("");
    toDecimal(NULL);
    toDecimal("DCCCLXXXVIII"); /* Big length */
    toDecimal("CMXCIII");
    toDecimal("CMXCIX");
    toDecimal("M");
    toDecimal("MI");
    toDecimal("MIB"); /* Men in black */
  }
  clean_roman();
  return 0;
}

Mohit: 0
IX: 9
X: 10
IXI: 0
XL: 40
IIII: 0
: 0
DCCCLXXXVIII: 888
CMXCIII: 993
CMXCIX: 999
M: 1000
MI: 0
MIB: 0