Fleet  0.0.9
Inference in the LOT
PartialLZEnumeration.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include "SubtreeEnumeration.h"
4 
13 template<typename Grammar_t>
15  Grammar_t* grammar;
17 
18  // when we enumerate partial trees, skip ones with more than this may subtrees
19  size_t max_partial_enum = 1000;
20  size_t min_ref_size = 4; // don't reference pieces unless they have this many nodes (counting nulls!)
21 
22 public:
23  PartialLZEnumeration(Grammar_t* g) : grammar(g), st(grammar) {}
24 
32  size_t compute_possible_referents(const Node& root, const nonterminal_t nt) {
33  size_t cnt = 0;
34  std::set<Node> unique;
35  for(auto& n : root) {
36 
37  auto nx = st.count(n);
38  if(nx > max_partial_enum) continue; // don't spend all our time here
39  for(size_t i=0;i<nx;i++) {
40  auto x = st.toNode(i,root);
41 
42  if(x.nt() == nt and (not unique.contains(x)) and x.count_nonnull() > min_ref_size and (not x.is_null())) {
43  cnt++;
44  unique.insert(x);
45  //CERR "possible reference " TAB cnt TAB x.string() ENDL;
46  }
47  }
48  }
49  return cnt;
50  }
51 
52  Node get_referent(const Node& root, size_t cnt, const nonterminal_t nt) {
53  std::set<Node> unique;
54  for(auto& n : root) {
55 
56  auto nx = st.count(n);
57  if(nx > max_partial_enum) continue; // don't spend all our time here
58  for(size_t i=0;i<nx;i++) {
59  auto x = st.toNode(i,root);
60 
61  if(x.nt() == nt and (not unique.contains(x)) and x.count_nonnull() > min_ref_size and (not x.is_null())) {
62 
63  if(cnt == 0) {
64  return x;
65  }
66 
67  cnt--;
68  unique.insert(x);
69  //CERR "possible reference " TAB cnt TAB x.string() ENDL;
70  }
71  }
72  }
73  CERR root TAB cnt TAB nt ENDL;
74  assert(false && "*** You asked for a referent that was impossible!");
75  }
76 
83  [[nodiscard]] virtual Node toNode(IntegerizedStack& is, const nonterminal_t nt, Node& root) {
84 
85  // NOTE: These chunks can't have the partial ones first (as in FullLZEnumeration) because
86  // because the partial ones require more expansion after.
87 
88  // if we encode a terminal
89  enumerationidx_t numterm = this->grammar->count_terminals(nt);
90  if(is.get_value() < numterm) {
91  return this->grammar->makeNode(this->grammar->get_rule(nt, is.get_value())); // whatever terminal we wanted
92  }
93  is -= numterm;
94 
95  // otherwise it's either a reference to a prior node or not
96  auto possible_referents = compute_possible_referents(root, nt);
97  if(possible_referents > 0 and is.pop(2)==0) {
98  auto n = get_referent(root, is.pop(possible_referents), nt);
99 
100  // let's set this feature so we can see in debugging
101  //for(auto& x : n) { x.can_resample = false; }
102 
103  // and now we need to fill in the nodes
104  for(auto& x : n) {
105  if(x.is_null()) {
106  x.assign(toNode(is, x.parent->type(x.pi), root));
107  }
108  }
109 
110  assert(n.is_complete());
111  return n;
112  }
113  else {
114 
115  // otherwise we unpack the kids' encoding:
116  auto ri = is.pop(this->grammar->count_nonterminals(nt)); // this already includes the shift from all the nonterminals
117  Rule* r = this->grammar->get_rule(nt, ri+numterm); // shift index from terminals (because they are first!)
118  Node out = this->grammar->makeNode(r);
119  int i=0;
120  for(auto v : is.split(r->N)) {
121 
122  // we assume we get a null root when root starts out -- so in that case,
123  // out is the root for everything below.
124  if(root.is_null()) {
125  out.set_child(i, toNode(v, r->type(i), out) ) ;
126  }
127  else {
128  out.set_child(i, toNode(v, r->type(i), root) ) ;
129  }
130 
131  i++;
132  }
133 
134  assert(out.is_complete());
135  return out;
136  }
137  }
138 
139  // Required here or else we get z converted implicity to IntegerizedStack
140  [[nodiscard]] virtual Node toNode(enumerationidx_t z, const nonterminal_t nt, Node& root) {
141  IntegerizedStack is(z);
142  return toNode(is, nt, root);
143  }
144 
145  // Required here or else we get z converted implicity to IntegerizedStack
146  [[nodiscard]] virtual Node toNode(enumerationidx_t z, const nonterminal_t nt) {
147  // defaultly create a null node to pass in.
148  Node n;
149 
150  IntegerizedStack is(z);
151  return toNode(is, nt, n);
152  }
153 
154 
155 
156  [[nodiscard]] virtual enumerationidx_t toInteger(const Node& root, const Node& n) {
157  assert(0);
158  }
159 
160 };
161 
162 
value_t pop()
Definition: IntegerizedStack.h:82
Definition: Node.h:22
enumerationidx_t count(const Node &n)
How many partial subtrees are there?
Definition: SubtreeEnumeration.h:24
Definition: SubtreeEnumeration.h:13
#define TAB
Definition: IO.h:19
Enumerate subtrees of a given tree.
nonterminal_t type(size_t i) const
Definition: Rule.h:152
Definition: PartialLZEnumeration.h:14
Definition: Rule.h:21
value_t get_value() const
Definition: IntegerizedStack.h:124
std::vector< value_t > split(size_t n)
Split into n children – this is the same as looping and popping, but provides a nicer interface NOTE...
Definition: IntegerizedStack.h:114
virtual size_t count_terminals() const
Definition: BaseNode.h:388
virtual bool is_complete() const
Definition: Node.h:188
size_t N
Definition: Rule.h:29
bool is_null() const
Definition: Node.h:165
size_t compute_possible_referents(const Node &root, const nonterminal_t nt)
Compute the number of things in n which could be referenced Here, we will require references to prior...
Definition: PartialLZEnumeration.h:32
virtual Node toNode(IntegerizedStack &is, const nonterminal_t nt, Node &root)
Convert to a node, using root as the root – NOTE that when root is null, we use out as the root...
Definition: PartialLZEnumeration.h:83
void assign(Node &n)
Assign will set everything to n BUT it will not copy the parent pointer etc since we&#39;re assuming this...
Definition: Node.h:59
#define CERR
Definition: IO.h:23
unsigned short nonterminal_t
Definition: Nonterminal.h:4
void set_child(const size_t i, Node &n)
Definition: Node.h:88
#define ENDL
Definition: IO.h:21
virtual enumerationidx_t toInteger(const Node &root, const Node &n)
Definition: PartialLZEnumeration.h:156
virtual Node toNode(IntegerizedStack &is, const Node &frm)
Convert to the is&#39;th partial subtree of frm.
Definition: SubtreeEnumeration.h:46
size_t enumerationidx_t
Definition: IntegerizedStack.h:3
Definition: IntegerizedStack.h:12
PartialLZEnumeration(Grammar_t *g)
Definition: PartialLZEnumeration.h:23
virtual Node toNode(enumerationidx_t z, const nonterminal_t nt)
Definition: PartialLZEnumeration.h:146
virtual Node toNode(enumerationidx_t z, const nonterminal_t nt, Node &root)
Definition: PartialLZEnumeration.h:140
Node get_referent(const Node &root, size_t cnt, const nonterminal_t nt)
Definition: PartialLZEnumeration.h:52