Package dev.roanh.gmark.lang.cpq

Class QueryGraphCPQ.OptionSet

java.lang.Object
dev.roanh.gmark.lang.cpq.QueryGraphCPQ.OptionSet
Enclosing class:
QueryGraphCPQ
private static final class QueryGraphCPQ.OptionSet extends Object
Represents a set of possible mappings for attributes that were processed in the past, but will not be seen again in future tree nodes. These mappings are essentially part of complete homomorphism mappings for the graph, but are not relevant to the homomorphism finding algorithm anymore. Furthermore, this set automatically filters any elements that are added, keeping only the smallest candidates. Note that since the added elements represent attributes that are never seen again we are free to map them in any way we like without affecting the correct of the of the algorithm, so we will only keep those candidates that map to the fewest distinct targets. The row essentially tracks all the still relevant attributes, while past attributes are tracked by this option set.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final BitSet
    base
    A bit set with the components in the match for the row this option set belongs to set to true.
    private int
    cost
    The current cost of the lowest cost attribute mappings in options.
    private final List<BitSet>
    options
    All smallest past attribute mappings for this option set.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    OptionSet(QueryGraphCPQ.Row row)
    Constructs a new empty option set for the given row.

  • Method Summary

    Modifier and Type
    Method
    Description
    private void
    add(BitSet maps)
    Adds a new attribute mapping to this option set.
    private void
    addAll(BitSet prefix, List<QueryGraphCPQ.OptionSet> toAdd)
    Adds new mappings to the option set as constructed from the given prefix and list of option sets to join with.
    private void
    addAll(List<QueryGraphCPQ.OptionSet> toAdd, int offset, BitSet workSet)
    Adds new mappings to the option set as constructed from the given prefix and list of option sets to join with.
    private void
    addDirect(BitSet maps)
    Adds a new attribute mapping to this option set.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • options

      private final List<BitSet> options
      All smallest past attribute mappings for this option set. Note that while each candidate consists of only query graph components, these are actually mapping from an attribute to this component. However, we do not actually ever need to use left hand side attribute of the map, so we do not store it.

    • base

      private final BitSet base
      A bit set with the components in the match for the row this option set belongs to set to true. The row this option set belongs to.

    • cost

      private int cost
      The current cost of the lowest cost attribute mappings in options. This cost is the number of distinct mapping targets.

  • Constructor Details

    • OptionSet

      private OptionSet(QueryGraphCPQ.Row row)
      Constructs a new empty option set for the given row.
      Parameters:
      row - The row to create an option set for.
      See Also:

  • Method Details

    • addAll

      private void addAll(BitSet prefix, List<QueryGraphCPQ.OptionSet> toAdd)
      Adds new mappings to the option set as constructed from the given prefix and list of option sets to join with. This will attempt to add a new entry for each unique combination of attribute mappings in the given list of option sets, essentially computing a Cartesian product. The given prefix targets are added to every candidate generated in this manner.
      Parameters:
      prefix - The prefix mapping targets to add to every candidate encoded as a bit set.
      toAdd - The option sets to compute combinations of.

    • addAll

      private void addAll(List<QueryGraphCPQ.OptionSet> toAdd, int offset, BitSet workSet)
      Adds new mappings to the option set as constructed from the given prefix and list of option sets to join with. This will attempt to add a new entry for each unique combination of attribute mappings in the given list of option sets, essentially computing a Cartesian product. The work set indicates the components picked so far and the offset indicates the next option set to pick from.
      Parameters:
      toAdd - The option sets to compute combinations of.
      offset - The next option set to pick from.
      workSet - The current set of picked components encoded as a bit set.

    • addDirect

      private void addDirect(BitSet maps)
      Adds a new attribute mapping to this option set. However, if this mapping has a higher cost than the current options it is discarded. Conversely, if it has a lower cost all current options are discarded instead. The cost is computed as the number of distinct mapping targets when combined with the mappings at the the row for this option set.
      Parameters:
      maps - The new mapping to add (complete with the row mapping targets).
      See Also:

    • add

      private void add(BitSet maps)
      Adds a new attribute mapping to this option set. However, if this mapping has a higher cost than the current options it is discarded. Conversely, if it has a lower cost all current options are discarded instead. The cost is computed as the number of distinct mapping targets when combined with the mappings at the the row for this option set.
      Parameters:
      maps - The new mapping to add (without the row mapping targets).

    • toString

      public String toString()
      Overrides:
      toString in class Object