Class Label

java.lang.Object
it.univr.di.labeledvalue.Label
All Implemented Interfaces:
Serializable, Comparable<Label>
public final class Label extends Object implements Comparable<Label>, Serializable
Represents an immutable propositional label in the CSTN/CSTNU framework.
A label is a (logic) conjunction of zero or more literals (Literal).
A label without literals is called empty label and it is represented graphically as Constants.EMPTY_LABEL.
A label is consistent when it does not contain opposite literals. A label L' subsumes a label L iff L' implies L (⊨ L' ⇒ L).
In other words, if L is a sub-label of L'.

Design assumptions Since in CSTN(U) project the memory footprint of a label is an important aspect, after some experiments, I have found that the best way to represent a label is to limit the possible propositions to the range [a-z,A-F] and to use two int for representing the state of literals composing a label: the two int are used in pair; each position of them is associated to a possible literal (position 0 to 'a',...,position 32 to 'F'); given a position, the two corresponding bits in the two long can represent all possible four states (Literal.ABSENT, Literal.STRAIGHT, Literal.NEGATED, Literal.UNKNOWN) of the literal associated to the position.
Using only 32 possible propositions, it is possible to cache the two int of a label as a long and, therefore, to cache the label for reusing it.

The following table represent execution times of some Label operations determined using different implementation of this class.

Execution time for some operations w.r.t the core data structure of the class.
Method TreeSet ObjectAVLTreeSet ObjectRBTreeSet byte array two int two long two int Immutable
Simple conjunction of '¬abcd' with '¬adefjs'='¬abcdefjs' (ms) 0.076961 0.066116 0.068798 0.001309 0.000299 0.000317 0.000529
Execution time for an extended conjunction of '¬abcd' with 'a¬c¬defjs'='¿ab¿c¿defjs' (ms) 0.07583 0.024099 0.014627 0.000843 0.000203 0.000235 0.000229
Execution time for checking if two (inconsistent) labels are consistent. Details '¬abcd' with 'a¬c¬defjs' (ms) 0.004016 0.001666 0.00166 0.00121 0.00075 0.00040 0.000122
Execution time for checking if two (consistent) labels are consistent. Details '¬abcd' with '¬abcd' (ms) 0.01946 0.004457 0.004099 0.000392 0.000558 0.000225 0.000089
Execution time for checking if a literal is present in a label (the literal is the last inserted) (ms) 5.48E-4 4.96E-4 5.01E-4 2.69E-4 5.03E-4 7.47E-4 4.46E-4
Execution time for checking if a literal is present in a label (the literal is not present) (ms) 6.48E-4 7.71E-4 5.96E-4 1.84E-4 3.07E-4 2.33E-4 2.14E-4
Execution time for get the literal in the label with the same proposition letter (the literal is present) (ms) 0.003272 1.83E-4 1.09E-4 1.27E-4 1.60E-4 1.32E-4 7.43E-5
Execution time for get the literal in the label with the same proposition letter (the literal is not present) (ms) 0.002569 1.68E-4 1.0E-4 1.04E-4 1.60E-4 1.30E-4 5.25E-5
All code for performance tests is in LabelTest class .
Version:
$Rev: 856 $
Author:
Roberto Posenato
See Also:

  • Field Details

    • LABEL_RE

      public static final String LABEL_RE
      Regular expression representing a Label. The re checks only that label chars are allowed.

    • NUMBER_OF_POSSIBLE_PROPOSITIONS

      public static final int NUMBER_OF_POSSIBLE_PROPOSITIONS
      Maximal number of possible proposition in a network.
      This limit cannot be changed without revising all this class code.
      See Also:

    • emptyLabel

      public static final Label emptyLabel
      A constant empty label to represent an empty label that cannot be modified.

    • labelValidator

      public static final org.netbeans.validation.api.Validator<String> labelValidator
      Validator for graphical interface

  • Method Details

    • allComponentsOfBaseGenerator

      @Nullable public static Label[] allComponentsOfBaseGenerator(char[] baseElements)
      A base is a set of same-length labels that are can be used to build any other greater-length label of the universe.
      The label components of a base can be built from a set of literals making all possible same-length combinations of such literals and their negations.
      Parameters:
      baseElements - an array of propositions.
      Returns:
      return all the components of the base built using literals of baseElements. Null if baseElements is null or empty.

    • parse

      @Nullable public static Label parse(String s)
      Parse a string representing a label and return an equivalent Label object if no errors are found, null otherwise.
      The regular expression syntax for a label is specified in LABEL_RE.
      Parameters:
      s - a String object.
      Returns:
      a Label object corresponding to the label string representation, null if the input string does not represent a label or is null.

    • valueOf

      public static Label valueOf(char proposition, char state)
      Parameters:
      proposition - the input proposition as chat
      state - its state. Possible values: Literal.ABSENT, Literal.NEGATED, Literal.STRAIGHT, or Literal.UNKNOWN.
      Returns:
      the label initialized with literal represented by the proposition and its state. If proposition is a char not allowed, a IllegalArgumentException is raised.

    • compareTo

      public int compareTo(@Nonnull Label label)
      Determines an order based on length of label. Same length labels are in lexicographical order based on the natural order of type Literal.
      Specified by:
      compareTo in interface Comparable<Label>

    • conjunction

      @Nullable public Label conjunction(Label label)
      Conjuncts label to this if this is consistent with label and returns the result without modifying this.
      Parameters:
      label - the label to conjoin
      Returns:
      a new label with the conjunction of this and label if they are consistent, null otherwise.
      null also if this or label contains unknown literals.

    • conjunction

      @Nullable public Label conjunction(Literal literal)
      Helper method for conjunction(char, char)
      Parameters:
      literal - a literal
      Returns:
      the new Label if literal has been added, null otherwise.

    • conjunction

      @Nullable public Label conjunction(char proposition, char propositionState)
      It returns a new label conjunction of proposition and this if this is consistent with proposition and its propositionState. If propositionState is Literal.ABSENT, the effect is reset the proposition in the new label.
      Parameters:
      proposition - the proposition to conjoin.
      propositionState - a possible state of the proposition: Literal.STRAIGHT, Literal.NEGATED or Literal.ABSENT.
      Returns:
      the new label if proposition can be conjuncted, null otherwise.

    • conjunctionExtended

      @Nonnull public Label conjunctionExtended(@Nonnull Label label)
      Create a new label that represents the conjunction of this and label using also Literal.UNKNOWN literals. A Literal.UNKNOWN literal represent the fact that in the two input labels a proposition letter is present as straight state in one label and in negated state in the other.
      For a detail about the conjunction of unknown literals, see conjunctionExtended(char, char).
      Parameters:
      label - the input label.
      Returns:
      a new label with the conjunction of this and label.
      this is not altered by this method.

    • conjunctionExtended

      @Nullable public Label conjunctionExtended(Literal literal)
      Helper method conjunctionExtended(char, char)
      Parameters:
      literal - a literal
      Returns:
      Label where literal has been added.

    • conjunctionExtended

      public Label conjunctionExtended(char proposition, char propositionState)
      It returns the conjunction of proposition to this. If proposition state literalState is opposite to the corresponding literal in this, the opposite literal in this is substituted with proposition but with unknown state. If proposition has unknown state, it is added to this as unknown. If propositionState is Literal.ABSENT, the effect is reset the proposition in the label.
      Parameters:
      proposition - the literal to conjoin.
      propositionState - a possible state of the proposition: Literal.STRAIGHT, Literal.NEGATED, Literal.UNKNOWN or Literal.ABSENT.
      Returns:
      this label.

    • contains

      public boolean contains(char proposition)
      Parameters:
      proposition - the proposition to check.
      Returns:
      true if this contains proposition in any state: straight, negated or unknown.

    • contains

      public boolean contains(Literal l)
      Parameters:
      l - the input literal
      Returns:
      true if the literal l is present into the label.

    • containsUnknown

      public boolean containsUnknown()
      Returns:
      true if the label contains one unknown literal at least.

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • getAllUnknown

      public char[] getAllUnknown()
      Returns:
      The array of propositions (char) that have unknown status in this label.

    • getLiterals

      public Literal[] getLiterals()
      Returns:
      An array containing a copy of literals in this label. The array may be empty.

    • getPropositions

      public char[] getPropositions()
      Returns:
      The array of proposition of present literals in this label in alphabetic order.

    • getState

      public char getState(char proposition)
      Parameters:
      proposition - the proposition to check.
      Returns:
      the state of the proposition in this label: straight, negated, unknown or absent.

    • getStateLiteralWithSameName

      public char getStateLiteralWithSameName(char c)
      Parameters:
      c - the name of literal
      Returns:
      the state of literal with name c if it is present, Literal.ABSENT otherwise.

    • getSubLabelIn

      public Label getSubLabelIn(Label label, boolean inCommon)
      Determines the sub label of this that is also present (not present) in label lab.
      Parameters:
      label - the label in which to find the common/uncommon sub-part.
      inCommon - true if the common sub-label is wanted, false if the sub-label present in this and not in lab is wanted.
      Returns:
      the sub label of this that is in common/not in common (if inCommon is true/false) with lab. The label returned is a new object that shares only literals with this or with from. If there is no common part, an empty label is returned.

    • getSubLabelIn

      public Label getSubLabelIn(Label label, boolean inCommon, boolean strict)
      Determines the sub label of this that is also present (not present) in label lab.

      When the common sub label is required (inCommon true), if strict is true, then the common sub label is as expected: it contains only the literals of this also present into lab.
      Otherwise, when strict is false, the common part contains also each literal that has the opposite or the unknown counterpart in lab. For example, is this='a¬b¿cd' and lab='bc¿d', the not strict common part is '¿b¿c¿d'.

      Parameters:
      label - the label in which to find the common/uncommon sub-part.
      inCommon - true if the common sub-label is wanted, false if the sub-label present in this and not in lab is wanted.
      strict - if the common part should contain only the same literals in both labels.
      Returns:
      the sub label of this that is in common/not in common (if inCommon is true/false) with lab. The label returned is a new object that shares only literals with this or with from. If there is no common part, an empty label is returned.

    • getUniqueDifferentLiteral

      @Nullable public Literal getUniqueDifferentLiteral(Label label)
      Finds and returns the unique different literal between this and lab if it exists. If label this and lab differs in more than one literal, it returns null.
      If this and lab contain a common proposition but in one its state is unknown and in other is straight or negated, it returns null;
      Parameters:
      label - a nor null neither empty label.
      Returns:
      the unique literal of 'this' that has its opposite in lab.
      null, if there is no literal of such kind or there are two or more literals of this kind or this/label is empty or null.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • isConsistentWith

      public boolean isConsistentWith(Label label)
      A label L1 is consistent with a label L2 if L1 ∧ L2 is satisfiable.
      L1 subsumes L2 implies L1 is consistent with L2 but not vice versa.
      If L1 contains an unknown literal ¿p, and L2 contains p/¬p, then the conjunction L1 ∧ L2 is not defined while ¿p subsumes p/¬p is true.
      In order to consider also labels with unknown literals, this method considers the conjunctionExtended(Label): L1 ★ L2, where ¿p are used for represent the conjunction of opposite literals p and ¬p or literals like ¿p and p/¬p.
      Now, it holds ¿p ★ p = ¿p is satisfiable.
      Parameters:
      label - the label to check
      Returns:
      true if the label is consistent with this label.

    • isConsistentWith

      public boolean isConsistentWith(Literal lit)
      Parameters:
      lit - the input literal
      Returns:
      true if lit is consistent with this label.

    • isEmpty

      public boolean isEmpty()
      Returns:
      true if the label contains no literal.

    • negation

      public Literal[] negation()
      Since a label is a conjunction of literals, its negation is a disjunction of negative literals (i.e., not a label).
      The negation operator returns a set of all negative literals of this label.
      Bear in mind that the complement of a literal with unknown state is a null object.
      Returns:
      the array of all negative literal of this as an array. If this is empty, returns an empty array.;

    • remove

      public Label remove(char proposition)
      Returns a new label that is a copy of this without proposition if it is present. Removing a proposition means to remove all literal of the given proposition.
      Parameters:
      proposition - the proposition to remove.
      Returns:
      the new label.

    • remove

      public Label remove(Label inputLabel)
      Returns a new label copy of this where all literals with names in inputLabel are removed.
      Parameters:
      inputLabel - names of literals to remove.
      Returns:
      the new label.

    • remove

      public Label remove(Literal literal)
      Returns a new label that is a copy of this where literal is removed if it is present. If label contains '¬p' and input literal is 'p', then the method returns a copy of this.
      Parameters:
      literal - the literal to remove
      Returns:
      the new label.

    • size

      public int size()
      Returns:
      the number of literals of the label.

    • subsumes

      public boolean subsumes(Label label)
      A label L1 subsumes (entails) a label L2 if L1 ⊨ L2.
      In other words, L1 subsumes L2 if L1 contains all literals of L2 when both they have no unknown literals.
      An unknown literal ¿p represents the fact that the value of p is not known. Therefore, if ¿p is true, then p can be true or ¬p can be true.
      If p is true or false, then ¿p is false. The same for ¬p.
      Therefore, it holds that ¿p subsumes p, ¿p subsumes ¬p, and ¿p subsumes ¿p, while p NOT subsumes ¿p and ¬p NOT subsumes ¿p.
      Parameters:
      label - the label to check
      Returns:
      true if this subsumes label.

    • toLogicalExpr

      public String toLogicalExpr(boolean negate, String not, String and, String or)
      Return a string representing the label as logical expression using logical 'not', 'and', and 'or'. String representations of operators can be given as parameters. A label 'P¬A' is represented as "P and not A". If negate is true, then 'P¬A' is represented as negated: "not P or A".
      Parameters:
      negate - negate the label before the conversion. Be careful!
      not - string representing not. If null, it is assumed "!"
      and - representing not. If null, it is assumed "&"
      or - representing not. If null, it is assumed " | "
      Returns:
      empty string if label is null or empty, the string representation as logical expression otherwise.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • isConsistentWith

      boolean isConsistentWith(byte literalIndex, char literalState)
      A literal l is consistent with a label if the last one does not contain ¬l.
      Parameters:
      literalIndex - the index of the literal
      literalState - its state
      Returns:
      true if the literal is consistent with this label.