[5f4d9c3] | 1 | #ifndef _SGRAPH_HH |
---|
| 2 | #define _SGRAPH_HH |
---|
| 3 | |
---|
| 4 | #include <stdio.h> |
---|
| 5 | |
---|
| 6 | #include <list> |
---|
| 7 | #include <vector> |
---|
| 8 | #include <bitset> |
---|
| 9 | |
---|
| 10 | #include "const.hh" |
---|
[e7de6cc] | 11 | #include "mgraph.hh" |
---|
[5f4d9c3] | 12 | #include "thesymbols.hh" |
---|
[e7de6cc] | 13 | #include "boubble.hh" |
---|
[5f4d9c3] | 14 | |
---|
| 15 | |
---|
[e7de6cc] | 16 | using namespace std; |
---|
[5f4d9c3] | 17 | |
---|
[e7de6cc] | 18 | //==================================================================================================== |
---|
| 19 | // CLASS Arc |
---|
| 20 | //==================================================================================================== |
---|
[5f4d9c3] | 21 | struct Arc |
---|
| 22 | { |
---|
| 23 | int dst; |
---|
| 24 | Role role; |
---|
[e7de6cc] | 25 | int headanc; |
---|
| 26 | int depanc; |
---|
[5f4d9c3] | 27 | |
---|
[e7de6cc] | 28 | Arc(int d, Role r, int ha, int da) : dst(d), role(r), headanc(ha), depanc(da) {}; |
---|
| 29 | }; |
---|
[5f4d9c3] | 30 | |
---|
[e7de6cc] | 31 | //==================================================================================================== |
---|
| 32 | // CLASS NodeProp |
---|
| 33 | //==================================================================================================== |
---|
[5f4d9c3] | 34 | |
---|
| 35 | struct NodeProp |
---|
| 36 | { |
---|
[e7de6cc] | 37 | NodeProp(); |
---|
| 38 | NodeProp(const NodeProp& p); |
---|
| 39 | ~NodeProp(); |
---|
| 40 | |
---|
| 41 | bool operator==(const NodeProp& p); |
---|
| 42 | NodeProp& operator=(const NodeProp& p); |
---|
| 43 | |
---|
| 44 | void clear_boubbles(); |
---|
| 45 | void merge_boubbles(list<Boubble*> new_boubbles); |
---|
[5f4d9c3] | 46 | |
---|
[e7de6cc] | 47 | void copy(const NodeProp& p); |
---|
| 48 | void clear(); |
---|
[5f4d9c3] | 49 | |
---|
[e7de6cc] | 50 | RoleSet required; |
---|
| 51 | RoleSet forbidden; |
---|
| 52 | RoleSet attached; |
---|
[5f4d9c3] | 53 | |
---|
[e7de6cc] | 54 | bool init_attached; |
---|
| 55 | bool fin_attached; |
---|
| 56 | |
---|
| 57 | FlagSet flags; |
---|
| 58 | |
---|
| 59 | list<Boubble*> boubbles; |
---|
[5f4d9c3] | 60 | }; |
---|
| 61 | |
---|
[e7de6cc] | 62 | //---------------------------------------------------------------------------------------------------- |
---|
| 63 | |
---|
| 64 | inline |
---|
| 65 | bool NodeProp::operator==(const NodeProp& p) |
---|
| 66 | { |
---|
| 67 | if(required != p.required) return false; |
---|
| 68 | if(forbidden != p.forbidden) return false; |
---|
| 69 | if(attached != p.attached) return false; |
---|
| 70 | if(flags != p.flags) return false; |
---|
| 71 | if(init_attached != p.init_attached) return false; |
---|
| 72 | if(fin_attached != p.fin_attached) return false; |
---|
| 73 | |
---|
| 74 | list<Boubble*>::const_iterator b1 = p.boubbles.begin(); |
---|
| 75 | for(list<Boubble*>::const_iterator b = boubbles.begin(); b != boubbles.end(); b++) |
---|
| 76 | { |
---|
| 77 | if(b1 == p.boubbles.end()) |
---|
| 78 | return false; |
---|
| 79 | if(!(**b == **b1)) |
---|
| 80 | return false; |
---|
| 81 | } |
---|
| 82 | if(b1 != p.boubbles.end()) |
---|
| 83 | return false; |
---|
| 84 | |
---|
| 85 | return true; |
---|
| 86 | } |
---|
| 87 | |
---|
| 88 | //---------------------------------------------------------------------------------------------------- |
---|
| 89 | |
---|
| 90 | inline |
---|
| 91 | void NodeProp::clear_boubbles() |
---|
| 92 | { |
---|
| 93 | for(list<Boubble*>::iterator b = boubbles.begin(); b!=boubbles.end(); b++) |
---|
| 94 | delete *b; |
---|
| 95 | boubbles.clear(); |
---|
| 96 | } |
---|
| 97 | |
---|
| 98 | //---------------------------------------------------------------------------------------------------- |
---|
| 99 | |
---|
| 100 | inline |
---|
| 101 | void NodeProp::merge_boubbles(list<Boubble*> new_boubbles) |
---|
| 102 | { |
---|
| 103 | boubbles.merge(new_boubbles); |
---|
| 104 | } |
---|
| 105 | |
---|
| 106 | //---------------------------------------------------------------------------------------------------- |
---|
| 107 | |
---|
| 108 | inline |
---|
| 109 | void NodeProp::copy(const NodeProp& p) |
---|
| 110 | { |
---|
| 111 | required=p.required; |
---|
| 112 | forbidden=p.forbidden; |
---|
| 113 | attached=p.attached; |
---|
| 114 | flags=p.flags; |
---|
| 115 | init_attached=p.init_attached; |
---|
| 116 | fin_attached=p.fin_attached; |
---|
| 117 | for(list<Boubble*>::const_iterator b = p.boubbles.begin(); b!=p.boubbles.end(); b++) |
---|
| 118 | boubbles.push_back(new Boubble(**b)); |
---|
| 119 | } |
---|
| 120 | |
---|
| 121 | //---------------------------------------------------------------------------------------------------- |
---|
| 122 | |
---|
| 123 | inline |
---|
| 124 | NodeProp::~NodeProp() |
---|
| 125 | { |
---|
| 126 | clear_boubbles(); |
---|
| 127 | } |
---|
| 128 | //---------------------------------------------------------------------------------------------------- |
---|
| 129 | |
---|
| 130 | inline |
---|
| 131 | NodeProp::NodeProp() |
---|
| 132 | { |
---|
| 133 | clear(); |
---|
| 134 | } |
---|
| 135 | |
---|
| 136 | //---------------------------------------------------------------------------------------------------- |
---|
| 137 | |
---|
| 138 | inline |
---|
| 139 | NodeProp::NodeProp(const NodeProp& p) |
---|
| 140 | { |
---|
| 141 | copy(p); |
---|
| 142 | } |
---|
| 143 | |
---|
| 144 | //---------------------------------------------------------------------------------------------------- |
---|
| 145 | |
---|
| 146 | inline |
---|
| 147 | NodeProp& NodeProp::operator=(const NodeProp& p) |
---|
| 148 | { |
---|
| 149 | clear(); |
---|
| 150 | copy(p); |
---|
| 151 | return *this; |
---|
| 152 | } |
---|
| 153 | |
---|
| 154 | //---------------------------------------------------------------------------------------------------- |
---|
| 155 | |
---|
| 156 | inline |
---|
| 157 | void NodeProp::clear() |
---|
| 158 | { |
---|
| 159 | required.reset(); |
---|
| 160 | forbidden.reset(); |
---|
| 161 | attached.reset(); |
---|
| 162 | init_attached=false; |
---|
| 163 | fin_attached=false; |
---|
| 164 | clear_boubbles(); |
---|
| 165 | } |
---|
| 166 | |
---|
| 167 | //==================================================================================================== |
---|
| 168 | // CLASS SNode |
---|
| 169 | //==================================================================================================== |
---|
[5f4d9c3] | 170 | |
---|
| 171 | struct SNode |
---|
| 172 | { |
---|
| 173 | |
---|
[e7de6cc] | 174 | int mnode; |
---|
[5f4d9c3] | 175 | |
---|
| 176 | NodeProp prop; |
---|
| 177 | |
---|
| 178 | bitset<MAXNODES> LV; |
---|
| 179 | bitset<MAXNODES> LH; |
---|
| 180 | bitset<MAXNODES> LD; |
---|
| 181 | bool in_LH; |
---|
| 182 | |
---|
| 183 | vector<Arc> heads; |
---|
| 184 | vector<Arc> deps; |
---|
| 185 | |
---|
[e7de6cc] | 186 | void clear(); |
---|
| 187 | bool saturated(); |
---|
[5f4d9c3] | 188 | }; |
---|
| 189 | |
---|
[e7de6cc] | 190 | //---------------------------------------------------------------------------------------------------- |
---|
| 191 | inline |
---|
| 192 | void SNode::clear() |
---|
| 193 | { prop.clear(), LV.reset(), LD.reset(), LH.reset(), heads.clear(), deps.clear(); } |
---|
| 194 | //---------------------------------------------------------------------------------------------------- |
---|
| 195 | inline |
---|
| 196 | bool SNode::saturated() |
---|
| 197 | { return prop.required.none(); } |
---|
[5f4d9c3] | 198 | |
---|
[e7de6cc] | 199 | //==================================================================================================== |
---|
| 200 | // SGraph CLASS |
---|
| 201 | //==================================================================================================== |
---|
[5f4d9c3] | 202 | |
---|
| 203 | class SGraph |
---|
| 204 | { |
---|
| 205 | public: |
---|
| 206 | |
---|
[e7de6cc] | 207 | enum Output { HEADS=1, DEPS=2, SETS=4, CONSTRAINTS=8, BOUBBLES=16 }; |
---|
[5f4d9c3] | 208 | |
---|
[e7de6cc] | 209 | SGraph(MGraph& mg) : mgraph(mg) { clear(); } |
---|
[5f4d9c3] | 210 | |
---|
[e7de6cc] | 211 | SNode& operator[](const int i) { return nodes[i]; } |
---|
[5f4d9c3] | 212 | |
---|
[e7de6cc] | 213 | void clear() { nodes.clear(); } |
---|
| 214 | int add_base_snode(int mnodeind); |
---|
| 215 | int clone(int ancind, NodeProp newprop); |
---|
[5f4d9c3] | 216 | void update_left(int headind, int depind); |
---|
| 217 | void update_right(int headind, int depind); |
---|
| 218 | bool visible(int left, int right); |
---|
| 219 | bool saturated(int node); |
---|
| 220 | |
---|
[e7de6cc] | 221 | Cat cat(int i) const { return mgraph[nodes[i].mnode].cat; } |
---|
| 222 | char* form(int i) const { return mgraph[nodes[i].mnode].form; } |
---|
[5f4d9c3] | 223 | |
---|
| 224 | int print_node(FILE* f, int n, unsigned int info); |
---|
[e7de6cc] | 225 | int print_node_debug(FILE* f, const char* pref, int n, int anc); |
---|
[5f4d9c3] | 226 | |
---|
| 227 | void print_arc(FILE* f, int left, int right, Role role, int dir); // 0 - left, 1 - right |
---|
| 228 | |
---|
[e7de6cc] | 229 | //private: |
---|
| 230 | |
---|
| 231 | int size() {return nodes.size(); } |
---|
| 232 | |
---|
| 233 | private: |
---|
| 234 | |
---|
| 235 | MGraph& mgraph; |
---|
| 236 | |
---|
| 237 | vector<SNode> nodes; |
---|
| 238 | |
---|
| 239 | int lastnodeind() { return nodes.size()-1; } |
---|
| 240 | SNode& makenewnode() { nodes.push_back(SNode()); nodes.back().clear(); return nodes.back(); } |
---|
| 241 | |
---|
| 242 | int sprint_node(char* buf, int n, int anc, unsigned int info); |
---|
| 243 | int sprint_node_debug(char* buf, const char* pref, int n, int anc); |
---|
[5f4d9c3] | 244 | }; |
---|
| 245 | |
---|
[e7de6cc] | 246 | //---------------------------------------------------------------------------------------------------- |
---|
[5f4d9c3] | 247 | |
---|
| 248 | inline bool SGraph::visible(int left, int right) |
---|
| 249 | { |
---|
| 250 | return nodes[right].LV[left]; |
---|
| 251 | } |
---|
| 252 | |
---|
[e7de6cc] | 253 | //---------------------------------------------------------------------------------------------------- |
---|
| 254 | |
---|
[5f4d9c3] | 255 | inline bool SGraph::saturated(int node) |
---|
| 256 | { |
---|
| 257 | return nodes[node].saturated(); |
---|
| 258 | } |
---|
| 259 | |
---|
[e7de6cc] | 260 | //---------------------------------------------------------------------------------------------------- |
---|
| 261 | |
---|
[5f4d9c3] | 262 | #endif |
---|