Class LabeledALabelIntTreeMap

java.lang.Object
it.univr.di.labeledvalue.LabeledALabelIntTreeMap
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
LabeledALabelIntTreeMap.LabeledALabelIntTreeMapView
public class LabeledALabelIntTreeMap extends Object implements Serializable
Allows to manage conjoin-upper-case values that are also associated to propositional labels.
Labeled values are grouped by alphabetic labels ALabel. Each group of labeled values is represented as LabeledIntTreeMap.
Therefore, such a class realizes the map ALabel-->LabeledIntTreeMap.

Be careful!
Since lower-case value are singular for each edge, it not convenient to represent it as LabeledALabelIntTreeMap.
A specialized class has been developed to represent such values: LabeledLowerCaseValue.

At the start of this implementation, I made some experiments for evaluating if it is better to use a Object2ObjectRBTreeMap or a ObjectArrayMap for representing the internal map. In October 2017, I verified that even with medium-size network, some edges can contain around 5000 labeled UC values. So, I tested the two implementations again considering up to 10000 labeled UC values. It resulted that up to 1000 values, the two implementations show still almost equivalent performance, BUT when the keys are ≥5000, to retrieve the keys from ObjectArrayMap requires more than ONE hour, while it requires almost ~96 ms using Object2ObjectRBTreeMap! Details using Object2ObjectRBTreeMap: 

 Time to retrieve 50 elements using entrySet(): ---
 Time to retrieve 50 elements using aLabelSet(): 0.012000000000000004ms

 Time to retrieve 100 elements using entrySet(): ---
 Time to retrieve 100 elements using aLabelSet(): 0.006000000000000003ms

 Time to retrieve 1000 elements using entrySet(): 0.045ms
 Time to retrieve 1000 elements using aLabelSet(): 0.034ms
 The difference is 0.025000000000000015 ms. It is better to use: aLabelSet() approach.

 Time to retrieve 5000 elements using entrySet(): 0.9623700000000001ms
 Time to retrieve 5000 elements using aLabelSet(): 0.352ms
 The difference is 0.6139400000000002 ms. It is better to use: aLabelSet() approach.

 Time to retrieve 10000 elements using entrySet(): --
 Time to retrieve 10000 elements using aLabelSet(): 1.292ms
Considering then, RB Tree instead of RB Tree: 
 Time to retrieve 50 elements using aLabelSet(): 0.012000000000000002ms

 Time to retrieve 100 elements using aLabelSet(): 0.007ms

 Time to retrieve 1000 elements using entrySet(): ---
 Time to retrieve 1000 elements using aLabelSet(): 0.038ms
 The difference is 0.025000000000000015 ms. It is better to use: aLabelSet() approach.

 Time to retrieve 5000 elements using entrySet(): ---
 Time to retrieve 5000 elements using aLabelSet(): 0.388ms
 The difference is 0.6139400000000002 ms. It is better to use: aLabelSet() approach.

 Time to retrieve 10000 elements using entrySet(): --
 Time to retrieve 10000 elements using aLabelSet(): 1.314ms
All code for testing is in LabeledALabelIntTreeMapTest class (not public available).
Version:
$Rev: 851 $
Author:
Roberto Posenato
See Also:

  • Field Details

    • labelCharsRE

      static final String labelCharsRE
      Keyword \w because it is necessary to accept also node names!

    • patternLabelCharsRE

      static final Pattern patternLabelCharsRE
      Matcher for RE

    • map

      it.unimi.dsi.fastutil.objects.Object2ObjectRBTreeMap<ALabel,LabeledIntMap> map
      Data structure.
      1. A Upper/Lower Case value is a pair (nodeName, value) where nodeName is a name of a node and can be written either in all UPPER case or in all lower case. Such kind of constraint has been introduced by Morris Muscettola 2005.
      2. A labeled Upper/Lower Case value is a pair (nodeName, (proposition_label, value)), where proposition_label represents scenario where value holds. Such kind of constraint has been introduced by Hunsberger, Combi, and Posenato in 2012.
      3. Each proposition_label is a conjunction of literals, i.e., of type Label.
      4. Since there may be more pairs with the same 'nodeName', a labeled Upper/Lower Case value is as a map of (nodeName, LabeledIntMap).
        See LabeledIntMap.
      5. In 2017-10, nodeName has been substituted by Alabel. ALabel represent the name of a node or a conjunction of node names.
        Such modification has been introduced because CSTNU DC checking algorithm requires such kind of values.

  • Constructor Details

  • Method Details

    • parse

      @Nullable public static LabeledALabelIntTreeMap parse(String arg, ALabelAlphabet alphabet, Class<? extends LabeledIntMap> labeledValueMapImple)
      Parse a string representing a LabeledValueTreeMap and return an object containing the labeled values represented by the string.
      The format of the string is given by the method toString(). For historical reasons, the method is capable to parse two different map format:"{[(&lang;label&rang;, &lang;Alabel&rang;, &lang;value&rang;) ]*} or "{[(&lang;Alabel&rang;, &lang;value&rang;, &lang;label&rang;) ]*}", where [a]* is a meta constructor for saying zero o more 'a'.
      Parameters:
      arg - a String object.
      alphabet - the alphabet to use to code the labels
      labeledValueMapImple - the class used for storing labeled values. If null, it is LabeledIntMapSupplier.DEFAULT_LABELEDINTMAP_CLASS.
      Returns:
      a LabeledPairMap object if args represents a valid map, null otherwise.

    • mergeTriple

      public boolean mergeTriple(Label newLabel, ALabel newAlabel, int newValue, boolean force)
      Merges a label case value (p,l,i).

      The value is insert if there is not a labeled value in the set with label (l,p) or it is present with a value higher than i.

      The method can remove or modify other labeled values of the set in order to minimize the labeled values present guaranteeing that no info is lost.

      Parameters:
      newLabel - a Label object.
      newAlabel - a case name.
      newValue - the new value.
      force - true if the value has to be stored without label optimization.
      Returns:
      true if the triple is stored, false otherwise.

    • alreadyRepresents

      public boolean alreadyRepresents(Label newLabel, ALabel newAlabel, int newValue)
      Parameters:
      newLabel - it must be not null
      newAlabel - it must be not null
      newValue - the new value
      Returns:
      true if the current map can represent the value. In positive case, an add of the element does not change the map. If returns false, then the adding of the value to the map would modify the map.

    • aLabelSet

      public it.unimi.dsi.fastutil.objects.ObjectSet<ALabel> aLabelSet()
      Returns:
      a set of all a-labels present into this map. The set is not modified if the map is modified after set creation.

    • remove

      public int remove(Label l, ALabel p)
      Parameters:
      l - a Label object.
      p - a ALabel object.
      Returns:
      the old value if it exists, Constants.INT_NULL otherwise.

    • clear

      public void clear()

    • getMinValue

      public it.unimi.dsi.fastutil.objects.Object2ObjectMap.Entry<Label,it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<ALabel>> getMinValue()
      Returns:
      the minimal value of this map in the format (Label, (ALabel, int)).
      If the map is null, returns the entry (Label.emptyLabel, (ALabel.emptyLabel, Constants.INT_NULL)).

    • size

      public final int size()
      Returns:
      the number of elements of the map.

    • getMinValueConsistentWith

      public int getMinValueConsistentWith(Label l, ALabel p)
      Returns the value associated to (l, p) if it exists, otherwise the minimal value among all labels consistent with (l, p).
      Parameters:
      l - if it is null, Constants.INT_NULL is returned.
      p - if it is null, Constants.INT_NULL is returned.
      Returns:
      the value associated to the (l, p) if it exists or the minimal value among values associated to labels consistent by l. If no labels are subsumed by l, Constants.INT_NULL is returned.

    • getMinValue

      public it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<Label> getMinValue(@Nonnull ALabel p)
      Returns a copy of the entry containing the min value associated to a-label p.
      Parameters:
      p - a non-null ALabel
      Returns:
      a copy of the entry containing the min value associated to a-label p if it exists, null otherwise.

    • getValue

      public int getValue(Label l, ALabel p)
      Parameters:
      l - a Label object.
      p - a ALabel representing the upper/lower case label (node label).
      Returns:
      the value associate to the key (label, p) if it exits, Constants.INT_NULL otherwise.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

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

    • toString

      public String toString()
      Returns a string representing the content of the map, i.e., "{[⟨entry⟩ ]*}", where each ⟨entry⟩ is written by entryAsString(Label, int, ALabel).
      Overrides:
      toString in class Object

    • entryAsString

      public static String entryAsString(Label label, int value, ALabel nodeName)
      Utility.
      Parameters:
      label - the input label
      value - the input value
      nodeName - this name is printed as it is. This method is necessary for saving the values of the map in a file.
      Returns:
      the canonical representation of the triple (as stated in ICAPS/ICAART papers), i.e. Constants.OPEN_PAIRAlabel, value, labelConstants.CLOSE_PAIR

    • isEmpty

      public final boolean isEmpty()
      Returns:
      true if the map does not contain any labeled value.

    • labelSet

      public it.unimi.dsi.fastutil.objects.ObjectSet<Label> labelSet()
      Returns:
      a set of all labels present into this map. The set is not modified if the map is modified after set creation.

    • labelSet

      public it.unimi.dsi.fastutil.objects.ObjectSet<Label> labelSet(ALabel alpha)
      Parameters:
      alpha - A-label of the wanted labeled value map.
      Returns:
      a set of labels present into the map associated to alpha A-label; empty set if there is no such a map.

    • entrySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<Label>> entrySet(ALabel alpha)
      Important The returned set is a view on the map. Don't modify the entries on this set and don't modify the map using methods like putTriple(Label, ALabel, int) (with 2nd parameter = alpha) during the scan of this set, otherwise the correctness of this set is not guaranteed.
      Parameters:
      alpha - A-label of the wanted labeled value map.
      Returns:
      a set of entries present into the map associated to alpha A-label; empty set if there is no such a map.

    • entrySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.fastutil.objects.Object2ObjectMap.Entry<ALabel,it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<Label>>> entrySet()
      Important The returned set is a view on the map. Don't modify the entries on this set and don't modify the map using methods like putTriple(Label, ALabel, int) (with 2nd parameter = alpha) during the scan of this set, otherwise the correctness of this set is not guaranteed.
      Returns:
      a set of all entries present into the map associated; empty set if there is no such a map.

    • mergeTriple

      public boolean mergeTriple(Label l, ALabel p, int i)
      Parameters:
      l - the Label object.
      p - the String object.
      i - the value to merge.
      Returns:
      see mergeTriple(Label, ALabel, int, boolean)
      See Also:

    • mergeTriple

      public boolean mergeTriple(String label, ALabel p, int i)
      Wrapper method. It calls mergeTriple(label, p, i, false);
      Parameters:
      label - a String object.
      p - a String object.
      i - the new value.
      Returns:
      see mergeTriple(String, ALabel, int, boolean)
      See Also:

    • mergeTriple

      public boolean mergeTriple(String label, ALabel p, int i, boolean force)
      Wrapper method of mergeTriple(Label, ALabel, int, boolean).
      'label' parameter is converted to a Label before calling mergeTriple(Label, ALabel, int, boolean).
      Parameters:
      label - a String object.
      p - a String object.
      i - the new value.
      force - true if the value has to be stored without label optimization.
      Returns:
      true if the triple is stored, false otherwise.

    • putTriple

      public boolean putTriple(Label l, ALabel p, int i)
      Put the triple (p,l,i) into the map. If the triple is already present, it is overwritten.
      Parameters:
      l - a Label object.
      p - a String object.
      i - the new value to add.
      Returns:
      true if the valued has been added.

    • remove

      public boolean remove(ALabel aleph)
      Parameters:
      aleph - aleph the id of the wanted labeled values map.
      Returns:
      true if the map associated to aleph is removed, false otherwise.

    • unmodifiable

      public LabeledALabelIntTreeMap.LabeledALabelIntTreeMapView unmodifiable()
      Returns:
      a read-only view of this object.

    • unmodifiable

      public LabeledIntMap unmodifiable(@Nonnull ALabel aleph)
      Parameters:
      aleph - the id of the wanted labeled values map.
      Returns:
      a read-only view of the sub map if it exits, an empty map otherwise.