/* -*-C-*-
********************************************************************************
*
* File:         reduce.cpp
* Description:  Functions to reduce a TRIE into a DAWG
* Author:       Mark Seaman, OCR Technology
* Created:      Fri Oct 16 14:37:00 1987
* Modified:     Wed Jun 19 16:51:29 1991 (Mark Seaman) marks@hpgrlt
* Language:     C
* Package:      N/A
* Status:       Reusable Software Component
*
* (c) Copyright 1987, Hewlett-Packard Company, all rights reserved.
** Licensed under the Apache License, Version 2.0 (the "License");
** you may not use this file except in compliance with the License.
** You may obtain a copy of the License at
** http://www.apache.org/licenses/LICENSE-2.0
** Unless required by applicable law or agreed to in writing, software
** distributed under the License is distributed on an "AS IS" BASIS,
** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
** See the License for the specific language governing permissions and
** limitations under the License.
*
********************************************************************************
*/


/*
----------------------------------------------------------------------
                     I n c l u d e s
----------------------------------------------------------------------
*/

#include "reduce.h"

#include "makedawg.h"
#include "cutil.h"

#ifdef __UNIX__
#include <assert.h>
#endif

/*
----------------------------------------------------------------------
                     T y p e s
----------------------------------------------------------------------
*/


/*
----------------------------------------------------------------------
                     V a r i a b l e s
----------------------------------------------------------------------
*/

static inT32 debug_1 = 0;

/*
----------------------------------------------------------------------
                     M a c r o s
----------------------------------------------------------------------
*/


/*
----------------------------------------------------------------------
                     F u n c t i o n s
----------------------------------------------------------------------
*/

/**********************************************************************
* collapse_source_nodes
*
* A pair of edges has been found that can be reduced.  This function
* accomplishes that reduction by collapsing the two nodes into a
* single node.
**********************************************************************/

void collapse_source_nodes (EDGE_ARRAY dawg,
                            NODE_REF   source_node_1,
                            NODE_REF   source_node_2,
                            NODE_REF   dest_node,
                            inT32        max_num_edges,
                            inT32        reserved_edges) {
  inT32      num_links;
  EDGE_REF   edge;
  /*    NODE_REF   new_source_1; */

  num_links = num_forward_edges (dawg, source_node_2);

  /*   if (debug_1)
       printf ("Node = %d, Input 1 = %d, Input 2 = %6d, num_links = %d\n",
       dest_node, source_node_1, source_node_2, num_links);

       if (debug) {
       printf ("Node = %d, Input 1 = %d, Input 2 = %6d, num_links = %d\n",
       dest_node, source_node_1, source_node_2, num_links);
       print_dawg_node (dawg, source_node_1);
       print_dawg_node (dawg, source_node_2);
       new_line ();
       }
  */
  /* Remove forward links in   */
  edge = source_node_2;                       /* source_node_2 - dest_node */
  if (forward_edge (dawg, edge)) {
    do {
      remove_edge_linkage (dawg, dest_node, source_node_2,
                           BACKWARD_EDGE,
                           edge_letter (dawg, edge),
                           end_of_word (dawg, edge));
    } edge_loop (dawg, edge);
  }
  /* Fix backward links */
  edge = source_node_2;                          /* in source_node_2 */
  edge += num_forward_edges (dawg, source_node_2);
  if (backward_edge (dawg, edge)) {
    do {
      move_node_if_needed (dawg, &source_node_1,
                           max_num_edges, reserved_edges);

      add_edge_linkage (dawg, source_node_1, next_node (dawg, edge),
                        BACKWARD_EDGE,
                        edge_letter (dawg, edge),
                        end_of_word (dawg, edge));
      /* Node moved */
      relocate_edge (dawg, next_node (dawg, edge),
                     source_node_2, source_node_1);
    } edge_loop (dawg, edge);
  }
  delete_node (dawg, source_node_2);

  /*   if (debug) {
       printf ("Number of edges  source = %d, dest = %d\n",
       edges_in_node (dawg, new_source_1),
       edges_in_node (dawg, dest_node));
       print_int ("Number of edges = ", edges_in_node (dawg, dest_node));
       print_dawg_node (dawg, new_source_1);

       print_string ("_________________________________________");
       new_line ();
       }
  */
}


/**********************************************************************
* eliminate_redundant_edges
*
* Compare these two edges in this node to see if they point to two
* nodes that could be collapsed.  If they do, then perform the
* reduction and return TRUE.  If not, return FALSE.
**********************************************************************/

inT32 eliminate_redundant_edges (EDGE_ARRAY dawg,
                                 NODE_REF   node,
                                 EDGE_REF   edge_1,
                                 EDGE_REF   edge_2,
                                 inT32        max_num_edges,
                                 inT32        reserved_edges) {
  static inT32 elim_count = 0;
  static inT32 keep_count = 0;

  if (same_output (dawg,
                   next_node (dawg, edge_1),
                   next_node (dawg, edge_2))) {
    elim_count++;

    collapse_source_nodes (dawg,
                           next_node (dawg, edge_1),
                           next_node (dawg, edge_2),
                           node,
                           max_num_edges, reserved_edges);
    /*      if (debug_1) {
            printf ("Collapsing node %d\n", node);
            print_dawg_node (dawg, node);
            printf ("Candidate edges = %d, %d\n", edge_1, edge_2);
            printf ("Candidate nodes = %d, %d\n\n",
            next_node (dawg, edge_1), next_node (dawg, edge_2));
            new_line ();
            }
    */
    return (TRUE);
  }
  else {
    keep_count++;
  }
  return (FALSE);
}


/**********************************************************************
* letter_order
*
* Compare two edges to see which one of the letters is larger.
**********************************************************************/

inT32 letter_order (const void* edge1_ptr,
                    const void* edge2_ptr) {

  if (letter_of_edge(*((EDGE_RECORD*) edge1_ptr)) <
      letter_of_edge(*((EDGE_RECORD*) edge2_ptr)))
    return (-1);

  if (letter_of_edge(*((EDGE_RECORD*) edge1_ptr)) >
      letter_of_edge(*((EDGE_RECORD*) edge2_ptr)))
    return (1);

  return (0);
}


/*
  printf ("%c%c   %c%c  ",
  edge1.letter, (edge1.flags & WORD_END_FLAG ? '*' : ' '),
  edge2.letter, (edge2.flags & WORD_END_FLAG ? '*' : ' '));
  printf ("\n");
  printf ("+\n");
  printf ("-\n");
*/

void print_n_edges (EDGE_RECORD *edge1,
                    inT32         n) {
  EDGE_RECORD *edge;

  edge = edge1;
  while (n-- > 0) {
    printf ("%c ", letter_of_edge(edge[0]));
    edge++;
  }

  new_line ();
}

/**********************************************************************
* reduce_lettered_edges
*
* The edge parameter is pointing to the first edge in a group of edges
* in this node with a particular letter value.  Look through these edges
* to see if any of them can be collapsed.  If so do it.  When all edges
* with this letter have been reduced then return to the caller.
* If further reduction is possible with this same letter then the
* edge parameter is not incremented.  When no further reduction is
* possible then FALSE is returned.
**********************************************************************/

inT32 reduce_lettered_edges (EDGE_ARRAY  dawg,
                             EDGE_REF    *edge,
                             NODE_REF    node,
                             NODE_MARKER reduced_nodes,
                             inT32        max_num_edges,
                             inT32        reserved_edges) {
  EDGE_REF    edge_1;
  EDGE_REF    edge_2;
  inT32         fixed_one;
  inT32         did_something = FALSE;

  if (debug_1)
    printf ("reduce_lettered_edges (edge=" REFFORMAT ")\n", *edge);

  /* Loop for each back edge */
  edge_1 = *edge;
  while ((! last_edge (dawg, edge_1)) &&
         edge_letter (dawg, edge_1) == edge_letter (dawg, *edge)) {

    edge_2 = edge_1 + 1;                        /* Compare all back edges */
    do {

      if (edge_letter (dawg, edge_1) <  edge_letter (dawg, edge_2))
        break;

      if (debug_1) {
        printf (REFFORMAT " (%c), " REFFORMAT " (%c) ",
                edge_1, edge_letter (dawg, edge_1),
                edge_2, edge_letter (dawg, edge_2));
      }

      if (edge_2 != edge_1 &&
          edge_letter (dawg, edge_2) == edge_letter (dawg, edge_1) &&
          end_of_word (dawg, edge_2) == end_of_word (dawg, edge_1) &&
          eliminate_redundant_edges (dawg, node, edge_1, edge_2,
                                     max_num_edges, reserved_edges)) {
        reduced_nodes [next_node (dawg, edge_1)] = 0;
        fixed_one     = TRUE;
        did_something = TRUE;
      }
      else {
        if (debug_1) printf ("   .");
        fixed_one = FALSE;
      }
      if (debug_1) printf ("\n");

    } while (fixed_one ?
             edge_occupied (dawg, edge_2) :
             (! last_edge (dawg, edge_2++)));
    edge_1++;
  }

  if (! did_something) {
    if (last_edge (dawg, edge_1))
      return (FALSE);
    else
      *edge = edge_1;
  }
  return (TRUE);
}


/**********************************************************************
* reduce_node_input
*
* Eliminate any redundant edges from this node in the DAWG.
**********************************************************************/

void reduce_node_input (EDGE_ARRAY dawg,
                        NODE_REF   node,
                        NODE_MARKER reduced_nodes,
                        inT32        max_num_edges,
                        inT32        reserved_edges) {
  EDGE_REF   edge_1;
  inT32        forward_edges  = num_forward_edges (dawg, node);
  inT32        backward_edges = edges_in_node (dawg, node) - forward_edges;

  static inT32 num_nodes_reduced = 0;

  if (debug_1) {
    printf ("reduce_node_input (node=" REFFORMAT ")\n", node);
    print_dawg_node (dawg, node);
  }

  if (++num_nodes_reduced % 100 == 0) {
    printf ("%d nodes reduced\n", num_nodes_reduced);
    if (debug_1 && num_nodes_reduced % 1000 == 0) {
      write_full_dawg ("temp-save", dawg, max_num_edges);
    }
  }

  qsort ((void *) &edge_of (dawg, node + forward_edges),
         backward_edges,
         sizeof (EDGE_RECORD),
         letter_order);

  /*   if (debug_1) {
       printf ("__________________________\n");
       print_dawg_node (dawg, node);
       }
  */
  edge_1 = node + forward_edges;
  while (reduce_lettered_edges (dawg, &edge_1, node, reduced_nodes,
                                max_num_edges, reserved_edges));

  reduced_nodes [node] = 1;                      /* Mark as reduced */

  if (debug_1) {
    printf ("After reduction:\n");
    print_dawg_node (dawg, node);
  }

  edge_1 = node + num_forward_edges (dawg, node); /* Reduce next level */
  if (backward_edge (dawg, edge_1)) {
    do {
      if (next_node (dawg, edge_1) &&
          reduced_nodes [next_node (dawg, edge_1)] == 0)
        reduce_node_input (dawg, next_node (dawg, edge_1), reduced_nodes,
                           max_num_edges, reserved_edges);
    } edge_loop (dawg, edge_1);
  }
}


/**********************************************************************
* same_output
*
* Check to see if these two nodes have identical output.  If so then
* they can be collapsed into a single node.
**********************************************************************/

inT32 same_output (EDGE_ARRAY dawg,
                   NODE_REF   node1,
                   NODE_REF   node2) {
  if (debug_1) printf ("Edge nodes = " REFFORMAT " , " \
                     REFFORMAT " \n", node1, node2);

  if (num_forward_edges (dawg, node1) == 1  &&
      num_forward_edges (dawg, node2) == 1) {
    if (debug_1) printf ("   * ");
    return (TRUE);
  }
  else {
    if (debug_1) {
      printf ("   %d,%d \n",
              num_forward_edges (dawg, node1),
              num_forward_edges (dawg, node2));
      print_dawg_node (dawg, node1);
      print_dawg_node (dawg, node2);
    }

    return (FALSE);
  }
}


/**********************************************************************
* trie_to_dawg
*
* Change a Trie data structure into a DAWG by eliminating the redund
**********************************************************************/

void trie_to_dawg (EDGE_ARRAY dawg,
                   inT32        max_num_edges,
                   inT32        reserved_edges) {
  NODE_MARKER reduced_nodes;
  inT32         x;

  max_new_attempts = 100000;
  compact_dawg (dawg, max_num_edges, reserved_edges);

  reduced_nodes = (NODE_MARKER) malloc (max_num_edges);
  for (x=0; x<max_num_edges; x++) reduced_nodes [x] = 0;

  reduce_node_input (dawg, 0, reduced_nodes, max_num_edges, reserved_edges);

  free (reduced_nodes);
}