prop-src/graphrep.pcc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 // This file implements data structure mapping for graph nodes and edges.
   4 //
   5 ///////////////////////////////////////////////////////////////////////////////
   6 #include "graphedges.ph"
   7
   8 ///////////////////////////////////////////////////////////////////////////////
   9 //
  10 //  Instantiate the nodes and edges datatypes
  11 //
  12 ///////////////////////////////////////////////////////////////////////////////
  13 instantiate datatype List<NodeDef *>, List<EdgeDef *>;
  14
  15 ///////////////////////////////////////////////////////////////////////////////
  16 //
  17 //  Constructors for all edge classes
  18 //
  19 ///////////////////////////////////////////////////////////////////////////////
  20 MapEdge::MapEdge(GraphTypeDef * G,
  21                  Id id, NodeDef* a, NodeDef* b, GraphIndexing i, LabTys attribs)
  22   : EdgeDef(G,id,a,b,i,attribs) {}
  23
  24 MultiMapEdge::MultiMapEdge
  25     (GraphTypeDef * G,
  26      Id id, NodeDef* a, NodeDef* b, GraphIndexing i, LabTys attribs)
  27   : EdgeDef(G,id,a,b,i,attribs) {}
  28
  29 BijectionEdge::BijectionEdge
  30     (GraphTypeDef * G,
  31      Id id, NodeDef* a, NodeDef* b, GraphIndexing i, LabTys attribs)
  32   : MapEdge(G,id,a,b,i,attribs) {}
  33
  34 EquivRelationEdge::EquivRelationEdge
  35     (GraphTypeDef * G,
  36      Id id, NodeDef* a, NodeDef* b, GraphIndexing i, LabTys attribs)
  37   : MapEdge(G,id,a,b,i,attribs) {}
  38
  39 ///////////////////////////////////////////////////////////////////////////////
  40 //
  41 //  Method to computing the proper representation for a node
  42 //
  43 ///////////////////////////////////////////////////////////////////////////////
  44 void NodeDef::choose_representation()
  45 {
  46 }
  47
  48 ///////////////////////////////////////////////////////////////////////////////
  49 //
  50 //  Methods to computing the proper representation for an edge
  51 //
  52 ///////////////////////////////////////////////////////////////////////////////
  53 void EdgeDef::choose_representation()
  54 {  // If we have f(x) or f{x} then we also have 'x in dom f' for free
  55    if (ops & (IMAGEgop | IMAGESETgop))
  56       ops |= INDOMgop;
  57    if (ops & INDOMgop)
  58       ops |= INgop; // x in f
  59 }
  60
  61 void MapEdge::choose_representation()
  62 {  ops |= IMAGEgop;       // f(x)
  63    ops |= DOMgop;         // dom f
  64    ops |= RANgop;         // ran f
  65    ops |= DOMSIZEgop;     // #dom f
  66    ops |= RANSIZEgop;     // #ran f
  67    ops |= UPDATEIMAGEgop; // f(x) := y
  68    ops |= SIZEgop;        // # f
  69    Super::choose_representation();
  70 }
  71
  72 void MultiMapEdge::choose_representation()
  73 {  ops |= IMAGESETgop;    // f{x}
  74    ops |= DOMgop;         // dom f
  75    ops |= DOMSIZEgop;     // #dom f
  76    ops |= RANSIZEgop;     // #ran f
  77    ops |= UPDATEIMAGEgop; // f{x} with := y
  78    ops |= SIZEgop;        // # f
  79    Super::choose_representation();
  80 }
  81
  82 void BijectionEdge::choose_representation()
  83 {
  84    Super::choose_representation();
  85 }
  86
  87 void EquivRelationEdge::choose_representation()
  88 {
  89    Super::choose_representation();
  90 }
  91
  92 ///////////////////////////////////////////////////////////////////////////////
  93 //
  94 //  Generic method to generate forward declarations for a node object
  95 //
  96 ///////////////////////////////////////////////////////////////////////////////
  97 void NodeDef::generate_forward_decls (CodeGen& C)
  98 {
  99    C.pr("%^class %s_%s_node;", graph()->class_name, node_name);
 100 }
 101
 102 ///////////////////////////////////////////////////////////////////////////////
 103 //
 104 //  Generic method to generate representation for a node object class.
 105 //
 106 ///////////////////////////////////////////////////////////////////////////////
 107 void NodeDef::generate_representation (CodeGen& C)
 108 {  C.pr("\n"
 109         "%^%/"
 110         "%^//"
 111         "%^//  Representation of node %s::%s(%T)"
 112         "%^//"
 113         "%^%/",
 114         graph()->class_name, node_name, node_type
 115        );
 116
 117    C.pr("%^class %s_%s_node {%+"
 118            "%^// no copy constructor or assignment"
 119            "%^%s_%s_node(const %s_%s_node&);"
 120            "%^void operator = (const %s_%s_node&);"
 121            "%^%T the_label;"
 122         "%-%^public:%+"
 123           "%^%T label() const { return the_label; }"
 124           "%^operator %T () const { return the_label; }"
 125           "%^friend class %s;",
 126         graph()->class_name, node_name,
 127         graph()->class_name, node_name, graph()->class_name, node_name,
 128         graph()->class_name, node_name,
 129         node_type, node_type, node_type, graph()->class_name
 130        );
 131
 132    for_each (EdgeDef *, e, graph()->edge_defs)
 133    {  e->generate_node_representation(C,this);
 134    }
 135
 136    C.pr("%-%^public:%+"
 137            "%^%s_%s_node();"
 138            "%^~%s_%s_node();"
 139         "%-%^};",
 140         graph()->class_name, node_name,
 141         graph()->class_name, node_name
 142        );
 143
 144    C.pr("\n\n");
 145 }
 146
 147 ///////////////////////////////////////////////////////////////////////////////
 148 //
 149 //  Generic method to generate interface for a node object
 150 //
 151 ///////////////////////////////////////////////////////////////////////////////
 152 void NodeDef::generate_interface (CodeGen& C)
 153 {  C.pr("%-%^public:%+"
 154         "%^%/"
 155         "%^//"
 156         "%^// Interface to node %s(%T)"
 157         "%^//"
 158         "%^%/",
 159         node_name, node_type
 160    );
 161
 162    if (node_type == NOty)
 163    {
 164       C.pr("%^// Create a new node; the new node is unique."
 165            "%^// The new node is now attached to the graph."
 166            "%^virtual %s create_%s();",
 167            node_name, node_name
 168           );
 169    } else
 170    {
 171       C.pr("%-%^protected:%+"
 172            "%^// HashTable< %T, %s, %s< %T >, %s< %T > > %s_table;"
 173            "%-%^public:%+",
 174            node_type, node_name, hash_fun, node_type,
 175            eq_fun, node_type, node_name
 176           );
 177
 178       C.pr("%^// Create a new node, or lookup an existing node."
 179            "%^// The node is now attached to the graph."
 180            "%^virtual %s create_%s(%T);"
 181            "%^\n"
 182            "%^// Lookup a node by its label."
 183            "%^// Returns nil if no such node exists."
 184            "%^%s lookup_%s(%T) const;"
 185            "%^\n"
 186            "%^// Does a node of a certain label exists?"
 187            "%^Bool has_%s(%T l) const { return lookup_%s(l) != 0; }"
 188            "%^\n"
 189            "%^// Insert a new node into the graph by label."
 190            "%^// A no-op if the graph with the label already exists"
 191            "%^%s insert_%s(%T l) { return create_%s(l); }"
 192            "%^\n"
 193            "%^// Remove a node by label."
 194            "%^// Returns true if the graph is changed."
 195            "%^Bool remove_%s(%T l) { return remove(lookup_%s(l)); }",
 196            node_name, node_name, node_type,
 197            node_name, node_name, node_type,
 198            node_name, node_type, node_name,
 199            node_name, node_name, node_type, node_name,
 200            node_name, node_type, node_name
 201          );
 202    }
 203
 204    C.pr("%^\n"
 205         "%^// Insert a node into the graph."
 206         "%^// Returns true if the graph is changed."
 207         "%^virtual Bool insert(%s);"
 208         "%^\n"
 209         "%^// Remove a node from the graph."
 210         "%^// The node is destroyed."
 211         "%^// Returns true if the graph is changed."
 212         "%^virtual Bool remove(%s);",
 213         node_name, node_name
 214        );
 215 }
 216
 217 ///////////////////////////////////////////////////////////////////////////////
 218 //
 219 //  Generic method to generate the implementation for a node object
 220 //
 221 ///////////////////////////////////////////////////////////////////////////////
 222 void NodeDef::generate_implementation (CodeGen& C)
 223 {  C.pr("%^%/"
 224         "%^// Implementation of node %s::%s(%T)"
 225         "%^%/",
 226         graph()->class_name, node_name, node_type
 227        );
 228 }
 229
 230 ///////////////////////////////////////////////////////////////////////////////
 231 //
 232 //  Generic method to generate representation for an edge within a node
 233 //
 234 ///////////////////////////////////////////////////////////////////////////////
 235 void EdgeDef::generate_node_representation (CodeGen& C, NodeDef * n)
 236 {  if (n != domain_type && n != range_type) return;
 237    C.pr("%^struct {%+");
 238    if (n == domain_type) generate_dom_rep(C);
 239    if (n == range_type)  generate_ran_rep(C);
 240    C.pr("%-%^} %s;",edge_name);
 241 }
 242
 243 ///////////////////////////////////////////////////////////////////////////////
 244 //
 245 //  Generic method to generate representation for an edge within the graph
 246 //
 247 ///////////////////////////////////////////////////////////////////////////////
 248 void EdgeDef::generate_edge_representation (CodeGen& C)
 249 {  generate_edge_rep(C);
 250 }
 251
 252 ///////////////////////////////////////////////////////////////////////////////
 253 //
 254 //  Generic method to generate representation for an edge within the graph
 255 //
 256 ///////////////////////////////////////////////////////////////////////////////
 257 void EdgeDef::generate_edge_rep (CodeGen& C)
 258 {  if (ops & SIZEgop)    C.pr("%^int count;              // number of edges ");
 259    if (ops & DOMgop)     C.pr("%^GraphType::Link domset; // the domain");
 260    if (ops & DOMSIZEgop) C.pr("%^int dom_count;          // size of domain");
 261    if (ops & RANgop)     C.pr("%^GraphType::Link ranset; // the range");
 262    if (ops & RANSIZEgop) C.pr("%^int ran_count;          // size of range");
 263 }
 264
 265 ///////////////////////////////////////////////////////////////////////////////
 266 //
 267 //  Methods to compute the representation
 268 //
 269 ///////////////////////////////////////////////////////////////////////////////
 270 void EdgeDef::generate_dom_rep(CodeGen& C)
 271 {
 272    if (ops & DOMgop) C.pr("%^GraphType::Link dom_link;");
 273 }
 274
 275 void EdgeDef::generate_ran_rep(CodeGen& C)
 276 {
 277    if (ops & RANgop)
 278       C.pr("%^GraphType::Link ran_link;"
 279            "%^int ran_count;");
 280 }
 281
 282 void MapEdge::generate_dom_rep(CodeGen& C)
 283 {  Super::generate_dom_rep(C);
 284    if (ops & IMAGEgop)
 285       C.pr("%^%s_%s_node * image;", graph->class_name, range_type->name());
 286 }
 287
 288 void MapEdge::generate_ran_rep(CodeGen& C)
 289 {  Super::generate_ran_rep(C);
 290 }
 291
 292 void MultiMapEdge::generate_dom_rep(CodeGen& C)
 293 {  Super::generate_dom_rep(C);
 294    if (ops & IMAGESETgop) C.pr("%^GraphType::Link image;");
 295 }
 296
 297 void MultiMapEdge::generate_ran_rep(CodeGen& C)
 298 {  Super::generate_ran_rep(C);
 299 }
 300
 301 void BijectionEdge::generate_dom_rep(CodeGen& C)
 302 {  Super::generate_dom_rep(C);
 303 }
 304
 305 void BijectionEdge::generate_ran_rep(CodeGen& C)
 306 {  Super::generate_ran_rep(C);
 307 }
 308
 309 void EquivRelationEdge::generate_dom_rep(CodeGen& C)
 310 {  Super::generate_dom_rep(C);
 311 }
 312
 313 void EquivRelationEdge::generate_ran_rep(CodeGen& C)
 314 {  Super::generate_ran_rep(C);
 315 }
 316
 317 ///////////////////////////////////////////////////////////////////////////////
 318 //
 319 //  Generic methods to generate the interface of an edge
 320 //
 321 ///////////////////////////////////////////////////////////////////////////////
 322 void EdgeDef::generate_interface (CodeGen& C)
 323 {
 324    if (domain_type == 0 || range_type == 0) return;
 325
 326    //
 327    // Encapsulate all methods to manipulate this edge into an edge record
 328    //
 329    C.pr("%^class %s_record {"
 330         "%^protected:%+"
 331         "%^friend class %s;",
 332         edge_name, graph->class_name);
 333    generate_edge_representation(C);  // how to represent this edge
 334    C.pr("%-%^public:%+");
 335    generate_interf(C);               // the methods
 336    C.pr("%-%^} %s;"
 337         "%^", edge_name);
 338 }
 339
 340 ///////////////////////////////////////////////////////////////////////////////
 341 //
 342 //  Methods to generate the interface of an edge
 343 //
 344 ///////////////////////////////////////////////////////////////////////////////
 345 void EdgeDef::generate_interf (CodeGen& C)
 346 {
 347    if (ops & DOMgop)     gen_dom(C);          // dom f
 348    if (ops & RANgop)     gen_ran(C);          // ran f
 349    if (ops & INDOMgop)   gen_in_dom(C);       // x in dom f
 350    if (ops & INRANgop)   gen_in_ran(C);       // x in ran f
 351    if (ops & INgop)      gen_in(C);           // x in f
 352    if (ops & SIZEgop)    gen_size(C);         // size of relation
 353    if (ops & DOMSIZEgop) gen_dom_size(C);     // size of domain
 354    if (ops & RANSIZEgop) gen_ran_size(C);     // size of range
 355    if (ops & (IMAGEgop | IMAGESETgop)) gen_image(C); // f(x) or f{x}
 356    if (ops & UPDATEIMAGEgop) gen_update_image(C); // f(x) := y or f{x} with := y
 357 }
 358
 359 void MapEdge::generate_interf(CodeGen& C)
 360 {  Super::generate_interf(C);
 361 }
 362
 363 void MultiMapEdge::generate_interf(CodeGen& C)
 364 {  Super::generate_interf(C);
 365 }
 366
 367 void BijectionEdge::generate_interf(CodeGen& C)
 368 {  Super::generate_interf(C);
 369 }
 370
 371 void EquivRelationEdge::generate_interf(CodeGen& C)
 372 {  Super::generate_interf(C);
 373 }
 374
 375 ///////////////////////////////////////////////////////////////////////////////
 376 //
 377 //  Generic methods to generate the implementation of an edge
 378 //
 379 ///////////////////////////////////////////////////////////////////////////////
 380 void EdgeDef::generate_implementation (CodeGen& C)
 381 {
 382    generate_impl(C);
 383 }
 384
 385 ///////////////////////////////////////////////////////////////////////////////
 386 //
 387 //  Methods to generate the implementation
 388 //
 389 ///////////////////////////////////////////////////////////////////////////////
 390 void EdgeDef::generate_impl(CodeGen& C)
 391 {
 392 }
 393
 394 void MapEdge::generate_impl(CodeGen& C)
 395 {  Super::generate_impl(C);
 396 }
 397
 398 void MultiMapEdge::generate_impl(CodeGen& C)
 399 {  Super::generate_impl(C);
 400 }
 401
 402 void BijectionEdge::generate_impl(CodeGen& C)
 403 {  Super::generate_impl(C);
 404 }
 405
 406 void EquivRelationEdge::generate_impl(CodeGen& C)
 407 {  Super::generate_impl(C);
 408 }