How user-functors can be declared

allows users to define functors themselves. Existing set or graph modules can be reused, if an appropriate functor declaration is given, and the module meets several requirements.

User-functors are declared on the level of XGRS in a DECLARE-statement:

A feature term is a term, augmented with attribute names [AKPG97]. A functor may define a new instance of a SolGraphFunctor or SolSetFunctor, as already defined above. For a functor declaration, the following attributes have to be supplied:

name: Ident

This is the name of the functor.

SetName: Ident

If it is a graph functor, this is name of the set of the nodes and target nodes. Otherwise not used.

NeighborSetName: Ident

If it is a graph functor, this is name of the neighbor sets. Otherwise not used.

RepresentantName: Ident

If it is a functor for explicit graphs, this is the name of the representant node (HGRAPH: NODE, SGRAPH: SNODE, BIPUNI: BIPNODE) Default is none. For other functors, this may be left out.

TargetType: Ident

In Java does not support functors (generic templates). Hence all functors are defined over Object. This identifier specifies for a more finer type to which the functor should refer, i.e. the type-checking of is improved.

IsHomogeneous: boolean

Is a graph homogeneous or bipartite?

IsBidirectional: boolean

Is the graph unidirectional or bidirectional?

HasExplicitEdges: boolean

Does the graph provide explicit edge objects? Otherwise it is probably implemented by pointers or indices.

IsExplicitGraph: boolean

Is the graph explicitly represented, i.e. are neighbors reachable only via a central graph structure? Otherwise it is embedded, i.e. neighbors are directly reachable via a neigbor set embedded into a graph node.

IsPolySet: boolean

Is a neighbor set parametrizable with a set functor or not?

IsOrdered: boolean

For a graph functor this means whether neighbor sets are ordered or not; for a set functor this means whether it is a list functor.

IsUnionOptimizable: boolean

Indicates whether the neighbor sets have linear time for the union/intersection operation (e.g. bitset implementations).

IsElementTestOptimizable: boolean

Indicates whether the neighbor sets have better than linear element test cost.

CheapCopyingPossible: boolean

This flag tells whether it is possible to copy an instance of the functor without allocating a new one, but overwriting an old one with new values. E.g. the BIT_SET functor provides that. Otherwise the copy function is used which allocates a new set.

NeighborSetUsesEmbeddedFields: boolean

Tells whether a set functor or a neighbor set functor of a graph functor is embedded.

ProvidesNOTLoop: boolean

Tells whether the functor has a NOT_LOOP macro which traverses over all objects in the graph which are NOT in the neighbor set.

ProvidesDirectFixpointCheck: boolean

Tells whether the functor insert/delete/addedge/deledge functions return a boolean value if they changed something. If that is the case, OPTIMIX can apply direct fixpoint checking.

UsesEndMarker: boolean

AST/CG lists require an end marker given to loops and access functions. Thus OPTIMIX must generate appropriate parameters for the calls.

LoopKind

Supported loop iteration method. There are IntegerLoop and MacroLoop. MacroLoop requires a macro for a loop, usually in the form

All standard sollib functors and the fSDL functors provide macro loops.

IntegerLoop which enumerates a neighbor set with an integer loop. For each such loop an iterator integer is generated.

For booleans specify one of the identifiers TRUE, true or FALSE, false.

Consider the following example which specifies a set functor, implemented as bitsets:

Such a functor declaration has to be accompanied with an implementation for the graph, set, or list module. Depending on certain attributes, this module must provide different interface functions. If a user wants to reuse an existing implementation, he may write a macro mapping header which maps the required interface functions to his own implementation.

Section 7.3 documents the core functions which must exist for all user-functor modules. Compare also the documentation on the sollib-library.