- /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, */
- /* "R_temp_ij = %s R_temp_ik = %s R_temp_kk = %s R_temp_kj = %s\n", */
- /* R_temp_ij, R_temp_ik, R_temp_kk, R_temp_kj); */
-
- // Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
- // as parentheses, so we can better compare the contents
- R_temp_ik = remove_parentheses (remove_epsilon (R_last[i][k]));
- R_temp_kk = remove_parentheses (remove_epsilon (R_last[k][k]));
- R_temp_kj = remove_parentheses (remove_epsilon (R_last[k][j]));
-
- clean_ik_kk_cmp = nullstrcmp (R_last[i][k], R_temp_kk);
- clean_kk_kj_cmp = nullstrcmp (R_temp_kk, R_last[k][j]);
-
- // construct R_cur_l (and, if necessary R_cur_r)
- if (NULL != R_last[i][j])
- {
- // Assign R_temp_ij to R_last[i][j] and remove epsilon as well
- // as parentheses, so we can better compare the contents
- R_temp_ij = remove_parentheses (remove_epsilon (R_last[i][j]));
-
- if (0 == strcmp (R_temp_ij, R_temp_ik) &&
- 0 == strcmp (R_temp_ik, R_temp_kk) &&
- 0 == strcmp (R_temp_kk, R_temp_kj))
- {
- if (0 == strlen (R_temp_ij))
- {
- R_cur_r = GNUNET_strdup ("");
- }
- // a|(e|a)a*(e|a) = a*
- // a|(e|a)(e|a)*(e|a) = a*
- // (e|a)|aa*a = a*
- // (e|a)|aa*(e|a) = a*
- // (e|a)|(e|a)a*a = a*
- // (e|a)|(e|a)a*(e|a) = a*
- // (e|a)|(e|a)(e|a)*(e|a) = a*
- else if ((0 == strncmp (R_last[i][j], "(|", 2)) ||
- (0 == strncmp (R_last[i][k], "(|", 2) &&
- 0 == strncmp (R_last[k][j], "(|", 2)))
- {
- if (GNUNET_YES == needs_parentheses (R_temp_ij))
- GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_ij);
- else
- GNUNET_asprintf (&R_cur_r, "%s*", R_temp_ij);
- }
- // a|aa*a = a+
- // a|(e|a)a*a = a+
- // a|aa*(e|a) = a+
- // a|(e|a)(e|a)*a = a+
- // a|a(e|a)*(e|a) = a+
- else
- {
- if (GNUNET_YES == needs_parentheses (R_temp_ij))
- GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_ij);
- else
- GNUNET_asprintf (&R_cur_r, "%s+", R_temp_ij);
- }
- }
- // a|ab*b = ab*
- else if (0 == ij_ik_cmp && 0 == clean_kk_kj_cmp &&
- 0 != clean_ik_kk_cmp)
- {
- if (strlen (R_last[k][k]) < 1)
- R_cur_r = GNUNET_strdup (R_last[i][j]);
- else if (GNUNET_YES == needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last[i][j], R_temp_kk);
- else
- GNUNET_asprintf (&R_cur_r, "%s%s*", R_last[i][j], R_last[k][k]);
-
- R_cur_l = NULL;
- }
- // a|bb*a = b*a
- else if (0 == ij_kj_cmp && 0 == clean_ik_kk_cmp &&
- 0 != clean_kk_kj_cmp)
- {
- if (strlen (R_last[k][k]) < 1)
- R_cur_r = GNUNET_strdup (R_last[k][j]);
- else if (GNUNET_YES == needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last[k][j]);
- else
- GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last[k][j]);
-
- R_cur_l = NULL;
- }
- // a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab*
- else if (0 == ij_ik_cmp && 0 == kk_kj_cmp &&
- !has_epsilon (R_last[i][j]) && has_epsilon (R_last[k][k]))
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last[i][j], R_temp_kk);
- else
- GNUNET_asprintf (&R_cur_r, "%s%s*", R_last[i][j], R_temp_kk);
-
- R_cur_l = NULL;
- }
- // a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a
- else if (0 == ij_kj_cmp && 0 == ik_kk_cmp &&
- !has_epsilon (R_last[i][j]) && has_epsilon (R_last[k][k]))
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last[i][j]);
- else
- GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last[i][j]);
-
- R_cur_l = NULL;
- }
- else
- {
- /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "NO SIMPLIFICATION\n"); */
- temp_a =
- (NULL == R_last[i][j]) ? NULL : GNUNET_strdup (R_last[i][j]);
- temp_a = remove_parentheses (temp_a);
- R_cur_l = temp_a;
- }
-
- GNUNET_free_non_null (R_temp_ij);
- }
- // we have no left side
- else
- {
- R_cur_l = NULL;
- }
-
- // construct R_cur_r, if not already constructed
- if (NULL == R_cur_r)
- {
- length = strlen (R_temp_kk) - strlen (R_last[i][k]);
-
- // a(ba)*bx = (ab)+x
- if (length > 0 && NULL != R_last[k][k] && 0 < strlen (R_last[k][k])
- && NULL != R_last[k][j] && 0 < strlen (R_last[k][j]) &&
- NULL != R_last[i][k] && 0 < strlen (R_last[i][k]) &&
- 0 == strkcmp (R_temp_kk, R_last[i][k], length) &&
- 0 == strncmp (R_temp_kk, R_last[k][j], length))
- {
- temp_a = GNUNET_malloc (length + 1);
- temp_b = GNUNET_malloc ((strlen (R_last[k][j]) - length) + 1);
-
- length_l = 0;
- length_r = 0;
-
- for (cnt = 0; cnt < strlen (R_last[k][j]); cnt++)
- {
- if (cnt < length)
- {
- temp_a[length_l] = R_last[k][j][cnt];
- length_l++;
- }
- else
- {
- temp_b[length_r] = R_last[k][j][cnt];
- length_r++;
- }
- }
- temp_a[length_l] = '\0';
- temp_b[length_r] = '\0';
-
- // e|(ab)+ = (ab)*
- if (NULL != R_cur_l && 0 == strlen (R_cur_l) &&
- 0 == strlen (temp_b))
- {
- GNUNET_asprintf (&R_cur_r, "(%s%s)*", R_last[i][k], temp_a);
- GNUNET_free (R_cur_l);
- R_cur_l = NULL;
- }
- else
- {
- GNUNET_asprintf (&R_cur_r, "(%s%s)+%s", R_last[i][k], temp_a,
- temp_b);
- }
- GNUNET_free (temp_a);
- GNUNET_free (temp_b);
- }
- else if (0 == strcmp (R_temp_ik, R_temp_kk) &&
- 0 == strcmp (R_temp_kk, R_temp_kj))
- {
- // (e|a)a*(e|a) = a*
- // (e|a)(e|a)*(e|a) = a*
- if (has_epsilon (R_last[i][k]) && has_epsilon (R_last[k][j]))
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_kk);
- else
- GNUNET_asprintf (&R_cur_r, "%s*", R_temp_kk);
- }
- // aa*a = a+a
- else if (0 == clean_ik_kk_cmp && 0 == clean_kk_kj_cmp &&
- !has_epsilon (R_last[i][k]))
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk);
- else
- GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk);
- }
- // (e|a)a*a = a+
- // aa*(e|a) = a+
- // a(e|a)*(e|a) = a+
- // (e|a)a*a = a+
- else
- {
- eps_check =
- (has_epsilon (R_last[i][k]) + has_epsilon (R_last[k][k]) +
- has_epsilon (R_last[k][j]));
-
- if (eps_check == 1)
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_kk);
- else
- GNUNET_asprintf (&R_cur_r, "%s+", R_temp_kk);
- }
- }
- }
- // aa*b = a+b
- // (e|a)(e|a)*b = a*b
- else if (0 == strcmp (R_temp_ik, R_temp_kk))
- {
- if (has_epsilon (R_last[i][k]))
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk,
- R_last[k][j]);
- else
- GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last[k][j]);
- }
- else
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk,
- R_last[k][j]);
- else
- GNUNET_asprintf (&R_cur_r, "%s+%s", R_temp_kk, R_last[k][j]);
- }
- }
- // ba*a = ba+
- // b(e|a)*(e|a) = ba*
- else if (0 == strcmp (R_temp_kk, R_temp_kj))
- {
- if (has_epsilon (R_last[k][j]))
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last[i][k],
- R_temp_kk);
- else
- GNUNET_asprintf (&R_cur_r, "%s%s*", R_last[i][k], R_temp_kk);
- }
- else
- {
- if (needs_parentheses (R_temp_kk))
- GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_last[i][k],
- R_temp_kk);
- else
- GNUNET_asprintf (&R_cur_r, "%s+%s", R_last[i][k], R_temp_kk);
- }
- }
- else
- {
- if (strlen (R_temp_kk) > 0)
- {
- if (needs_parentheses (R_temp_kk))
- {
- GNUNET_asprintf (&R_cur_r, "%s(%s)*%s", R_last[i][k],
- R_temp_kk, R_last[k][j]);
- }
- else
- {
- GNUNET_asprintf (&R_cur_r, "%s%s*%s", R_last[i][k], R_temp_kk,
- R_last[k][j]);
- }
- }
- else
- {
- GNUNET_asprintf (&R_cur_r, "%s%s", R_last[i][k], R_last[k][j]);
- }
- }
- }