Class Label
- All Implemented Interfaces:
Serializable
,Comparable<Label>
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.
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 |
- Version:
- $Rev: 993 $
- Author:
- Roberto Posenato
- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final Label
A constant empty label to represent an empty label that cannot be modified.static final String
Regular expression representing a Label.static final org.netbeans.validation.api.Validator
<String> Validator for a graphical interfacestatic final int
Maximal number of possible propositions in a network. -
Method Summary
Modifier and TypeMethodDescriptionstatic 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.int
Determines an order based on the length of the label.conjunction
(char proposition, char propositionState) It returns a new label conjunction ofproposition
andthis
ifthis
is consistent withproposition
and itspropositionState
.conjunction
(Label label) Conjunctslabel
tothis
ifthis
is consistent withlabel
and returns the result without modifyingthis
.conjunction
(Literal literal) Helper method forconjunction(char, char)
conjunctionExtended
(char proposition, char propositionState) It returns the conjunction ofproposition
tothis
.conjunctionExtended
(Label label) Create a new label that represents the conjunction ofthis
andlabel
using alsoLiteral.UNKNOWN
literals.conjunctionExtended
(Literal literal) Helper methodconjunctionExtended(char, char)
boolean
contains
(char proposition) boolean
boolean
boolean
char[]
Literal[]
char[]
char
getState
(char proposition) char
getStateLiteralWithSameName
(char c) getSubLabelIn
(Label label, boolean inCommon) Determines the sub label ofthis
that is also present (not present) in labellab
.getSubLabelIn
(Label label, boolean inCommon, boolean strict) Determines the sub label ofthis
that is also present (not present) in labellab
.getUniqueDifferentLiteral
(Label label) Finds and returns the unique different literal betweenthis
andlab
if it exists.int
hashCode()
(package private) boolean
isConsistentWith
(byte literalIndex, char literalState) A literal l is consistent with a label if the last one does not contain ¬l.boolean
isConsistentWith
(Label label) A label L1 is consistent with a label L2 if L1 ∧ L2 is satisfiable.boolean
isConsistentWith
(Literal lit) boolean
isEmpty()
Literal[]
negation()
Since a label is a conjunction of literals, its negation is a disjunction of negative literals (i.e., not a label).static Label
Parse a string representing a label and return an equivalent Label object if no errors are found; otherwise, it is null.remove
(char proposition) Returns a new label that is a copy ofthis
withoutproposition
if it is present.Returns a new label copy ofthis
where all literals with names in inputLabel are removed.Returns a new label that is a copy ofthis
whereliteral
is removed if it is present.int
size()
boolean
A label L1 subsumes (entails) a label L2 ifL1 ⊨ L2
.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'.toString()
static Label
valueOf
(char proposition, char state)
-
Field Details
-
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_PROPOSITIONSMaximal number of possible propositions in a network.
This limit cannot be changed without revising the entire class code.- See Also:
-
emptyLabel
A constant empty label to represent an empty label that cannot be modified. -
labelValidator
Validator for a graphical interface
-
-
Method Details
-
allComponentsOfBaseGenerator
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
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
- aString
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
- Parameters:
proposition
- the input proposition as chatstate
- its state. Possible values:Literal.ABSENT
,Literal.NEGATED
,Literal.STRAIGHT
, orLiteral.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
Determines an order based on the length of the label. Same-length labels are in lexicographical order based on the natural order of typeLiteral
.- Specified by:
compareTo
in interfaceComparable<Label>
-
conjunction
Conjunctslabel
tothis
ifthis
is consistent withlabel
and returns the result without modifyingthis
.- Parameters:
label
- the label to conjoin- Returns:
- a new label with the conjunction of
this
andlabel
if they are consistent, null otherwise. It returns null also ifthis
orlabel
contains unknown literals.
-
conjunction
Helper method forconjunction(char, char)
- Parameters:
literal
- a literal- Returns:
- the new Label if a literal has been added; otherwise, it is null.
-
conjunction
It returns a new label conjunction ofproposition
andthis
ifthis
is consistent withproposition
and itspropositionState
. If propositionState isLiteral.ABSENT
, the effect is to reset theproposition
in the new label.- Parameters:
proposition
- the proposition to conjoin.propositionState
- a possible state of the proposition:Literal.STRAIGHT
,Literal.NEGATED
orLiteral.ABSENT
.- Returns:
- the new label if the proposition can be conjuncted; otherwise, it is null.
-
conjunctionExtended
Create a new label that represents the conjunction ofthis
andlabel
using alsoLiteral.UNKNOWN
literals. ALiteral.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
andlabel
.this
is not altered by this method.
-
conjunctionExtended
Helper methodconjunctionExtended(char, char)
- Parameters:
literal
- a literal- Returns:
- Label where literal has been added.
-
conjunctionExtended
It returns the conjunction ofproposition
tothis
. Ifproposition
stateliteralState
is opposite to the corresponding literal inthis
, the opposite literal inthis
is substituted withproposition
but with unknown state. Ifproposition
has the unknown state, it is added tothis
as unknown. If propositionState isLiteral.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
orLiteral.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
- 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
-
getAllUnknown
public char[] getAllUnknown()- Returns:
- The array of propositions (char) that have an unknown status on this label.
-
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
Determines the sub label ofthis
that is also present (not present) in labellab
.- 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 inthis
and not inlab
is wanted.- Returns:
- the sub-label of
this
that is in common/not in common (if inCommon is true/false) withlab
. 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
Determines the sub label ofthis
that is also present (not present) in labellab
.When the common sublabel is required (
inCommon
true), ifstrict
is true, then the common sublabel is as expected: it contains only the literals ofthis
also present inlab
.Otherwise, when
strict
is false, the common part also contains each literal that has the opposite or the unknown counterpart inlab
. 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 inthis
and not inlab
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) withlab
. 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
Finds and returns the unique different literal betweenthis
andlab
if it exists. If labelthis
andlab
differ in more than one literal, it returns null.If
this
andlab
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() -
isConsistentWith
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
- 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
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
Returns a new label that is a copy ofthis
withoutproposition
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
Returns a new label copy ofthis
where all literals with names in inputLabel are removed.- Parameters:
inputLabel
- names of literals to remove.- Returns:
- the new label.
-
remove
Returns a new label that is a copy ofthis
whereliteral
is removed if it is present. If label contains '¬p' and input literal is 'p', then the method returns a copy ofthis
.- Parameters:
literal
- the literal to remove- Returns:
- the new label.
-
size
public int size()- Returns:
- the number of the label literals.
-
subsumes
A label L1 subsumes (entails) a label L2 ifL1 ⊨ 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
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
-
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 literalliteralState
- its state- Returns:
- true if the literal is consistent with this label.
-