;;;-*- Mode: Lisp; Package: XLE -*- (in-package :XLE) #||/* (c) 2002-2004 by the Palo Alto Research Center. All rights reserved */ /* (c) 1996-2001 by the Xerox Corporation. All rights reserved */ #ifndef SOLUTIONS_H #define SOLUTIONS_H /* ------------------------------------------------------------------------ */ /* The data structures in this file are used to build solutions to the */ /* nogood databases that are distributed across the subtree graphs of a */ /* chart. The basic idea is to build internal solutions to each subtree */ /* graph, and then to put those solutions into equivalence classes based on */ /* the restricted set of contexts that a consumer has imported. These */ /* restricted solutions are then used by the consuming graph to build its */ /* internal solutions, and so on. Restricted solutions are stored on the */ /* edge graph, since they are the interface to consuming graphs. */ /* ------------------------------------------------------------------------ */ ||# ;;struct RestrictionSet { /* a particular set of contexts that a consumer has */ ;; /* imported. The solutions computed will be */ ;; /* relative to the set of contexts that the */ ;; /* consumer imported. The solutions are cached in */ ;; /* restriction sets in case another consumer */ ;; /* happened to import the same set of contexts. */ (ff:def-foreign-type RestrictionSet (:struct ;; Clause *restriction; /* the set of contexts imported by the consumer */ (restriction :unsigned-long) ;; Clause *pushed; /* the set of pushed contexts. */ (pushed :unsigned-long); OBSOLETE! ;; Graph *mother; /* the first mother of the RestrictionSet */ (mother :unsigned-long) ;; unsigned int debugging:1; /* For debugging pushed solutions. */ (debugging (:bit 1)); OBSOLETE! ;; unsigned int open:1; /* Could more contexts be pushed later? */ (open (:bit 1)); OBSOLETE! ;; unsigned int all:1; /* Does the solutions include good and bad */ ;; /* solutions? (The grammer writer may want to look */ ;; /* at bad solutions.) */ (all (:bit 1)) ;; unsigned int goods_done:1; /* Have the good solutions already been ;; computed? */ (goods_done (:bit 1)) ;; unsigned int intermediate:1; /* Is this an intermediate solution? */ (intermediate (:bit 1)); OBSOLETE! ;; unsigned int partial_open:1; /* If intermediate, whether the partial ;; was open. */ (partial_open (:bit 1)); OBSOLETE! ;; unsigned int complete_open:1; /* If intermediate, whether the complete ;; was open. */ (complete_open (:bit 1)); OBSOLETE! ;; unsigned int indexed: 1; /* Whether index is a SolutionIndex or a ;; RestrictedSolution. */ (indexed (:bit 1)) ;; Clause *partial_pushed; /* If intermediate, the contexts pushed to ;; the partial daughter. */ (partial_pushed :unsigned-long); OBSOLETE! ;; Clause *complete_pushed; /* If intermediate, the contexts pushed to ;; the complete daughter. */ (complete_pushed :unsigned-long); OBSOLETE! ;; Clause *pushed_choices; /* If intermediate, the local pushed choices. */ (pushed_choices :unsigned-long); OBSOLETE! ;; RestrictedSolution *solutions; /* a threaded list of solutions to the */ ;; /* restriction. In the worst case there */ ;; /* can be O(2^N) solutions if there are N */ ;; /* contexts in the restriction. This */ ;; /* corresponds to one solution for every */ ;; /* possible combination of the presence or */ ;; /* absense of a context. */ (solutions :unsigned-long) ;; RestrictedSolution *last_solution; /* So that we can append efficiently. */ (last_solution :unsigned-long) ;; int solution_count; /* number of solutions */ (solution_count :int) ;; void *index; /* Index for solutions */ (index :unsigned-long) ;; RestrictionSet *next; /* the next restriction set in the edge graph's */ ;; /* list */ )) ;;}; #||/* ------------------------------------------------------------------------ */ struct SolutionIndex { unsigned int offset: 25; /* The offset of the first difference in the restriction. */ unsigned int indexed1: 1; /* =1 if index1 is a SolutionIndex. */ /* =0 if index1 is a RestrictedSolution. */ unsigned int indexed2: 1; /* =1 if index2 is a SolutionIndex. */ /* =0 if index2 is a RestrictedSolution. */ void *index1; /* the index to use if the offset clause is enabled. */ void *index2; /* the index to use if the offset clause is disabled. */ }; /* ------------------------------------------------------------------------ */ struct RestrictedSolution { /* a particular solution to a particular */ /* restriction. The restriction is implicitly */ /* given by the RestrictionSet that this */ /* solution belongs to. */ Clause *restriction; /* the set of contexts imported by the consumer */ char *bitvector; /* A bit vector indexed by the restriction that */ /* indicates which clauses are included in this */ /* solution. For instance, if the restriction */ /* is a:1, b:1, and (a:2 & b:1), then the bit */ /* vector might be 011, to indicate that b:1 and */ /* (a:2 & b:1) together make a solution. */ InternalSolutionsList *map; /* a list of internal solutions that evaluate */ /* to clauses. The internal solutions cannot */ /* be threaded, since they may be shared by */ /* the restricted solutions of different */ /* restriction sets. For any particular */ /* restriction set, all of the internal */ /* solutions must be a member of the map of */ /* exactly one restricted solution. Each */ /* internal solution appears once in each */ /* restriction set. */ RestrictedSolution *next; /* the next restricted solution */ /* for debugging/display purposes */ RestrictedSolution *consumer; /* the restricted solution that is the */ /* 'mother' of this solution in a DNF */ /* solution (used by fstructure-extract.c) */ RestrictedSolution *original; /* the original, non-dnf solution. */ RestrictionSet *refined; /* Refined versions of this solution */ Disjunction *disjunction; /* used by extract_chart_graph to enable it */ /* to create new disjunctions over the set */ /* of alternative internal solutions. */ float count; /* the number of solutions included in this */ /* solution. We use float because the */ /* number of suboptimals can exceed 2^32. */ int key; /* "hash" key */ int size : 20; /* Number of bits in the bitvector. */ unsigned short in_tree : 1; /* a temporary mark to indicate that this */ /* solution is in the c-structure tree that */ /* you are trying to extract solutions */ /* for. */ unsigned short mark : 1; /* a temporary mark. */ unsigned short bad : 2; /* This solution is bad in some way. */ /* bad = 2 means more than one way. */ unsigned short inconsistent : 1;/* This solution is inconsistent (used to */ /* display inconsistent solutions to the */ /* grammar writer). */ unsigned short incomplete : 1; /* This solution is incomplete (used to */ /* display incomplete solutions to the */ /* grammar writer). */ unsigned short unoptimal : 1; /* This solution is unoptimal. */ unsigned short dnf : 1; /* part of a DNF solution. If this is true, then */ /* "next" is interpreted as the non-DNF solution */ /* that this solution came from */ unsigned short locked : 1; /* This solution was locked by the user */ OTCount *OTmarks; /* The optimal Optimality Theory marks for this solution. */ void *gen_strings_fsm; /* should be NETptr type but don't routinely include the c-fsm headers */ }; struct SolutionList { RestrictedSolution *item; /* the first item of the list */ SolutionList *next; /* the rest of the list (terminated by */ /* NULL) */ }; /* ------------------------------------------------------------------------ */ struct InternalSolution { Graph *graph; /* the graph that this solution was */ /* extracted from (always a subtree graph) */ Clause *local_choices; /* the local choices needed to make the */ /* solution true. */ RestrictedSolution *partial; /* the solution from the partial daughter */ /* needed to make this solution true */ RestrictedSolution *complete; /* the solution from the complete daughter */ /* needed to make this solution true */ Clause *context; /* used by extract_chart_graph to assign a */ /* context to every internal solution. */ InternalSolution *original; /* the original, non-dnf solution. */ unsigned int mark : 31; /* a count field used by chart_extract.c. */ unsigned int only_old_choices : 1; /* Used by generate_test_sentences */ }; struct InternalSolutionsList { /* a list of internal solutions. The */ /* internal solutions cannot be threaded */ /* because they will appear in multiple */ /* restriction sets. */ InternalSolution *item; /* the first item of the list */ InternalSolutionsList *next; /* the rest of the list (terminated by */ /* NULL) */ }; /* --------------------------------------------------------------------- */ /* `internal_solution' to `restricted_solution' in the constraint space */ /* is like `subtree' to `edge' in the chart (phrasal) space. */ /* Indeed, the structure the following data objects encode is a "shadow" */ /* of the chart parser data structures. */ /* --------------------------------------------------------------------- */ extern /*const*/ RestrictedSolution *Empty_Solution; #endif ||#