srec/include/astar.h

/*---------------------------------------------------------------------------*
 *  astar.h  *
 *                                                                           *
 *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
 *                                                                           *
 *  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.                                           *
 *                                                                           *
 *---------------------------------------------------------------------------*/

#ifndef __ASTAR_H__
#define __ASTAR_H__

#include "search_network.h"
#include "srec_sizes.h"
#include "sizes.h"

/*********************************************************************
 *                                                                   *
 * Word Graph for Astar                                              *
 *                                                                   *
 *********************************************************************/

/* #define DEBUG_ASTAR 1 */

/* an arc_token is used for the word graph, this implementation
   removes the need for nodes, and allows arc_tokens to be
   freed and re-used easily for dynamic grammar creation.
   Why do away with nodes?  Nodes need a list of outgoing arcs,
   or arc pointers.  Rather than store this arc list as an array,
   we can store it as a linked list, for easy addition/removal.
   Nodes are now just a pointer to the first arc in a linked list.
   But further, why not just reference the "first_arc" instead of
   a node?  That's what we're doing here.  The "end_node" is
   really an arc, whose arc->first_next_arc is NULL.

   This experimental implementation is working for the moment!
*/

/* VxWorks 5.4 does not support unnamed struct/union yet */
/* here we use indices to link one arc token to the next */
#define ARC_TOKEN_LNK(bAsE,iDx) ((arcID)iDx)
#define ARC_TOKEN_PTR(bAsE,atp) (atp==MAXarcID?NULL:bAsE+atp)
#define ARC_TOKEN_PTR2LNK(bAsE,atp) (atp==NULL?MAXarcID:(arcID)(atp-bAsE))
#define ARC_TOKEN_IDX(bAsE,atp) (atp)
#define ARC_TOKEN_NULL MAXarcID
typedef arcID      arc_token_lnk;
typedef struct arc_token_t
{
#ifdef DEBUG_ASTAR
  char* label, debug[64];
#endif
  wordID  ilabel;                  /* input label */
  labelID olabel;                  /* output label */
  arc_token_lnk first_next_arc;
  arc_token_lnk next_token_index;
}
arc_token;

/**
 * @todo document
 */
typedef struct partial_path_t
{
  wtokenID token_index;
  wordID   word;           /* quick access to word (wta[token_index].word) */
  bigcostdata costsofar;   /* quick access to total score, frwd+bkwd */
  struct partial_path_t* next;
  struct partial_path_t* first_prev_arc;
  struct partial_path_t* linkl_prev_arc;
  arc_token* arc_for_wtoken;
  short refcount;
  struct partial_path_t* hashlink;
}
partial_path;
#define PARP_TERMINAL         ((partial_path*)-1)

typedef struct
{

  partial_path* free_parp_list;
  partial_path* partial_path_array;
  int partial_path_array_size;
  
  /* todo: replace these pointers with partial_path_token type things */
  int max_active_paths;
  int num_active_paths;
  partial_path** active_paths;    /* partial paths, sorted by score */
  
  int max_complete_paths;
  int num_complete_paths;
  partial_path** complete_paths;
  int* complete_path_confidences;
  partial_path* root_path;        /* root is the rightmost partial path
           to be used for as root of a tree
           for checking paths already visited */
  costdata prune_delta;
  void* pphash;
}
AstarStack;

typedef struct srec_t srec;
typedef srec* psrec;

int astar_stack_do_backwards_search(psrec rec, int request_nbest_len);
int astar_stack_prepare(AstarStack* stack, int request_nbest_len, psrec rec);
int astar_stack_prepare_from_active_search(AstarStack* stack, int request_nbest_len, psrec rec);
void astar_stack_clear(AstarStack* stack);
int astar_stack_flag_word_tokens_used(AstarStack* stack, psrec rec);
AstarStack* astar_stack_make(psrec rec, int max_nbest_len);
int astar_stack_destroy(psrec rec);

void free_partial_path(AstarStack* stack, partial_path* parp);
void print_path(partial_path* parp, psrec rec, char* msg);

arc_token* get_arc_for_word(arc_token* atoken, wordID word, void* context_void,
                            wordID terminal_word);
                            
arc_token* get_arc_for_word_without_slot_annotation(arc_token* atoken, const char* word,
    void* context_void, wordID terminal_word);
    
#endif