Package it.univr.di.labeledvalue

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 represents execution times of some Label operations determined using different implementations 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 getting 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 getting 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: 993 $
Author:
Roberto Posenato
See Also:

  • Field Details

    • LABEL_RE

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

    • NUMBER_OF_POSSIBLE_PROPOSITIONS

      public static final int NUMBER_OF_POSSIBLE_PROPOSITIONS
      Maximal number of possible propositions in a network.
      This limit cannot be changed without revising the entire 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 a graphical interface

  • Method Details

    • allComponentsOfBaseGenerator

      @Nullable public static Label[] allComponentsOfBaseGenerator(char[] baseElements)
      A base is a set of labels of the same length that can be used to build any other label of greater length in 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; otherwise, it is null.

      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 the literal represented by the proposition and its state. If the proposition is a not allowed character, an IllegalArgumentException is raised.

    • compareTo

      public int compareTo(@Nonnull Label label)
      Determines an order based on the length of the 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. It returns 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 a literal has been added; otherwise, it is null.

    • 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 to 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 the proposition can be conjuncted; otherwise, it is null.

    • 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 represents the fact that in the two input labels, a proposition letter is present as the straight state in one label and the 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 the unknown state, it is added to this as unknown. If propositionState is Literal.ABSENT, the effect is to 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 a 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 at least one unknown literal.

    • equals

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

    • getAllUnknown

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

    • getLiterals

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

    • getPropositions

      public char[] getPropositions()
      Returns:
      The array of propositions 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 the 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 - is the label on which to find the common/uncommon subpart.
      inCommon - true if the common sub-label is wanted, false if the sub-label is 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 sublabel is required (inCommon true), if strict is true, then the common sublabel is as expected: it contains only the literals of this also present in lab.

      Otherwise, when strict is false, the common part also contains each literal that has the opposite or the unknown counterpart in lab. For example, if this is this='a¬b¿cd' and lab='bc¿d', the not strictly common part is '¿b¿c¿d'.

      Parameters:
      label - is the label on which to find the common/uncommon subpart.
      inCommon - true if the common sub-label is wanted, false if the sublabel present in this and not in lab is wanted.
      strict - if the common part should contain only the same literals on both labels.
      Returns:
      the sublabel 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 differ 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 the other is straight or negated, it returns null;

      Parameters:
      label - a non-null, non-empty label.
      Returns:
      the unique literal of 'this' that has its opposite in lab. It returns 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.

      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 the unknown state is a null object.

      Returns:
      the array of all negative literals of this as an array. If this is empty, it 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 removing all literals 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 the label literals.

    • 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 the label.

    • toLogicalExpr

      public String toLogicalExpr(boolean negate, String not, String and, String or)
      Return a string representing the label as a 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 the label is null or empty, the string representation as a 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.