Package it.univr.di.labeledvalue

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 managing conjoined upper-case values that are also associated with 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 values are singular for each edge, it is not convenient to represent them as LabeledALabelIntTreeMap.

A specialized class has been developed to represent such values: LabeledLowerCaseValue.

At the start of this implementation, I did some experiments to evaluate whether it is better to use an Object2ObjectRBTreeMap or an ObjectArrayMap to represent the internal map.

In October 2017, I verified that even with the medium-sized 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 publicly available).
Version:
$Rev: 993 $
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. An Upper/Lower Case value is a pair (nodeName, value) where nodeName is the name of a node and can be written either in all UPPER case or in all lower case. Morris & Muscettola 2005 have introduced such a constraint.
      2. A labeled Upper/Lower Case value is a pair (nodeName, (proposition_label, value)), where proposition_label represents a scenario where the value holds. Such a constraint was 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 represented as a map of (nodeName, LabeledIntMap).
        See LabeledIntMap.
      5. In 2017-10, `nodeName` was substituted by ALabel. ALabel represents the name of a node or a conjunction of node names.
        Such a modification has been introduced because the CSTNU DC checking algorithm requires such values.

  • Constructor Details

  • Method Details

    • 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

    • 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 formats:"{[(&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.

    • aLabelSet

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

    • alreadyRepresents

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

    • clear

      public void clear()

    • entrySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<Label>> entrySet(ALabel alpha)
      The returned set is a view of 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 - ALabel of the wanted labeled value map.
      Returns:
      a set of entries present in the map associated with `alpha` ALabel; an empty set if there is no such 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 of 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 in the map associated; an empty set if there is no such map.

    • equals

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

    • 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)).

    • 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 with ALabel p.
      Parameters:
      p - a non-null ALabel
      Returns:
      a copy of the entry containing the min value associated with ALabel p if it exists, null otherwise.

    • getMinValueConsistentWith

      public int getMinValueConsistentWith(Label l, ALabel p)
      Returns the value associated with (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 with the (l, p) if it exists or the minimal value among values associated with labels consistent with l. If no labels are subsumed by l, Constants.INT_NULL is returned.

    • 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 associated with the key (label, p) if it exists, Constants.INT_NULL otherwise.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • 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 in 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 - ALabel of the wanted labeled value map.
      Returns:
      a set of labels present in the map associated with `alpha` ALabel; an empty set if there is no such map.

    • mergeTriple

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

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

      The method can remove or modify other labeled values of the set 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.

    • 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 value has been added.

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

    • remove

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

    • size

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

    • 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

    • 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 exists; otherwise, it is an empty map.