1/*---------------------------------------------------------------------------*
2 *  astar.h  *
3 *                                                                           *
4 *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
5 *                                                                           *
6 *  Licensed under the Apache License, Version 2.0 (the 'License');          *
7 *  you may not use this file except in compliance with the License.         *
8 *                                                                           *
9 *  You may obtain a copy of the License at                                  *
10 *      http://www.apache.org/licenses/LICENSE-2.0                           *
11 *                                                                           *
12 *  Unless required by applicable law or agreed to in writing, software      *
13 *  distributed under the License is distributed on an 'AS IS' BASIS,        *
14 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
15 *  See the License for the specific language governing permissions and      *
16 *  limitations under the License.                                           *
17 *                                                                           *
18 *---------------------------------------------------------------------------*/
19
20#ifndef __ASTAR_H__
21#define __ASTAR_H__
22
23#include "search_network.h"
24#include "srec_sizes.h"
25#include "sizes.h"
26
27/*********************************************************************
28 *                                                                   *
29 * Word Graph for Astar                                              *
30 *                                                                   *
31 *********************************************************************/
32
33/* #define DEBUG_ASTAR 1 */
34
35/* an arc_token is used for the word graph, this implementation
36   removes the need for nodes, and allows arc_tokens to be
37   freed and re-used easily for dynamic grammar creation.
38   Why do away with nodes?  Nodes need a list of outgoing arcs,
39   or arc pointers.  Rather than store this arc list as an array,
40   we can store it as a linked list, for easy addition/removal.
41   Nodes are now just a pointer to the first arc in a linked list.
42   But further, why not just reference the "first_arc" instead of
43   a node?  That's what we're doing here.  The "end_node" is
44   really an arc, whose arc->first_next_arc is NULL.
45
46   This experimental implementation is working for the moment!
47*/
48
49/* VxWorks 5.4 does not support unnamed struct/union yet */
50/* here we use indices to link one arc token to the next */
51#define ARC_TOKEN_LNK(bAsE,iDx) ((arcID)iDx)
52#define ARC_TOKEN_PTR(bAsE,atp) (atp==MAXarcID?NULL:bAsE+atp)
53#define ARC_TOKEN_PTR2LNK(bAsE,atp) (atp==NULL?MAXarcID:(arcID)(atp-bAsE))
54#define ARC_TOKEN_IDX(bAsE,atp) (atp)
55#define ARC_TOKEN_NULL MAXarcID
56typedef arcID      arc_token_lnk;
57typedef struct arc_token_t
58{
59#ifdef DEBUG_ASTAR
60  char* label, debug[64];
61#endif
62  wordID  ilabel;                  /* input label */
63  labelID olabel;                  /* output label */
64  arc_token_lnk first_next_arc;
65  arc_token_lnk next_token_index;
66}
67arc_token;
68
69/**
70 * @todo document
71 */
72typedef struct partial_path_t
73{
74  wtokenID token_index;
75  wordID   word;           /* quick access to word (wta[token_index].word) */
76  bigcostdata costsofar;   /* quick access to total score, frwd+bkwd */
77  struct partial_path_t* next;
78  struct partial_path_t* first_prev_arc;
79  struct partial_path_t* linkl_prev_arc;
80  arc_token* arc_for_wtoken;
81  short refcount;
82  struct partial_path_t* hashlink;
83}
84partial_path;
85#define PARP_TERMINAL         ((partial_path*)-1)
86
87typedef struct
88{
89
90  partial_path* free_parp_list;
91  partial_path* partial_path_array;
92  int partial_path_array_size;
93
94  /* todo: replace these pointers with partial_path_token type things */
95  int max_active_paths;
96  int num_active_paths;
97  partial_path** active_paths;    /* partial paths, sorted by score */
98
99  int max_complete_paths;
100  int num_complete_paths;
101  partial_path** complete_paths;
102  int* complete_path_confidences;
103  partial_path* root_path;        /* root is the rightmost partial path
104           to be used for as root of a tree
105           for checking paths already visited */
106  costdata prune_delta;
107  void* pphash;
108}
109AstarStack;
110
111typedef struct srec_t srec;
112typedef srec* psrec;
113
114int astar_stack_do_backwards_search(psrec rec, int request_nbest_len);
115int astar_stack_prepare(AstarStack* stack, int request_nbest_len, psrec rec);
116int astar_stack_prepare_from_active_search(AstarStack* stack, int request_nbest_len, psrec rec);
117void astar_stack_clear(AstarStack* stack);
118int astar_stack_flag_word_tokens_used(AstarStack* stack, psrec rec);
119AstarStack* astar_stack_make(psrec rec, int max_nbest_len);
120int astar_stack_destroy(psrec rec);
121
122void free_partial_path(AstarStack* stack, partial_path* parp);
123void print_path(partial_path* parp, psrec rec, char* msg);
124
125arc_token* get_arc_for_word(arc_token* atoken, wordID word, void* context_void,
126                            wordID terminal_word);
127
128arc_token* get_arc_for_word_without_slot_annotation(arc_token* atoken, const char* word,
129    void* context_void, wordID terminal_word);
130
131#endif
132