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 to manage conjoin-upper-case values that are also associated to propositional labels. Labeled values (Label) 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 TreeMap. A specialized class has been developed to represent such values: LabeledLowerCaseValue.

At first time, I made some experiments for evaluating if it is better to use a Object2ObjectRBTreeMap or a ObjectArrayMap for representing the internal map. The below table shows that for very small network, the two implementation are almost equivalent. So, ObjectArrayMap was chosen. *

Execution time (ms) for some operations w.r.t the core data structure of the class.
Operation Using Object2ObjectRBTreeMap (ms) Using ObjectArrayMap (ms)
Create 1st map 0.370336085 0.314329559
min value 0.017957532 0.014711536
Retrieve value 0.001397098 0.000600641
Simplification ~0.183388 ~0.120013

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 implementation again considering up to 10000 labeled UC values. It resulted that up to 1000 values, the two implementation show still almost equivalent performance, BUT when the keys are 5000, using ObjectArrayMap retrieve the keys requires more than ONE hour, while using Object2ObjectRBTreeMap it requires almost 96. ms!!! Details using Object2ObjectRBTreeMap: 

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

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

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

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

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

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

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

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

 Time to retrieve 10000 elements using entrySet(): --
 Time to retrieve 10000 elements using keySet(): 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

      protected 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.
      6. Since the introduction of ALabel, we suggest to use two @{link LabeledALabelIntTreeMap. One to represent the upper-case values. The other for lower-case ones.

    • labeledValueMapImpl

      Class<? extends LabeledIntMap> labeledValueMapImpl
      Labeled value class used in the class.

  • Constructor Details

    • LabeledALabelIntTreeMap

      public LabeledALabelIntTreeMap(LabeledALabelIntTreeMap lvm, Class<? extends LabeledIntMap> labeledValueMapImple)
      Constructor to clone the structure. All internal maps will be independent of lvm ones while elements of maps will be shared. The motivation is that usually a Label inside a map is managed as read-only.
      Parameters:
      lvm - the map to clone. If null, 'this' will be an empty map.
      labeledValueMapImple - the class used for storing labeled values. If null, it is LabeledIntMapSupplier.DEFAULT_LABELEDINTMAP_CLASS.

    • LabeledALabelIntTreeMap

      public LabeledALabelIntTreeMap(Class<? extends LabeledIntMap> labeledValueMapImple)
      Simple constructor. The internal structure is built and empty.
      Parameters:
      labeledValueMapImple - the class used for storing labeled values. If null, it is LabeledIntMapSupplier.DEFAULT_LABELEDINTMAP_CLASS.

  • Method Details

    • entryAsString

      public static String entryAsString(Label label, int value, ALabel nodeName)

      entryAsString.

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

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

    • clear

      public void clear()

    • equals

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

    • get

      public final LabeledIntMap get(ALabel alabel)
      Parameters:
      alabel - the input label
      Returns:
      the value to which the specified key is mapped, or null if this map contains no mapping for the key

    • 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 not considering upper/lower case label (node label). If the map is null, returns the entry (Label.emptyLabel, (ALabel.emptyLabel, Constants.INT_NULL)).

    • 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 or empty, 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.

    • 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

    • isEmpty

      public final boolean isEmpty()

      isEmpty.

      Returns:
      true if the map does not contain any labeled value.

    • keySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<ALabel> keySet()
      Returns:
      a set view of all a-labels present into this map.

    • labelSet

      public it.unimi.dsi.fastutil.objects.ObjectSet<Label> labelSet()

      labelSet.

      Returns:
      a set of all labels present into this map.

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

    • mergeTriple

      public boolean mergeTriple(Label l, ALabel p, int i)

      mergeTriple.

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

    • put

      public LabeledIntMap put(ALabel alabel, LabeledIntMap labeledValueMap)
      Put a map associate to key alabel. Possible previous map will be replaced.
      Parameters:
      alabel - the input label
      labeledValueMap - its map
      Returns:
      the old map if one was associated to alabel, null 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 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)

      remove.

      Parameters:
      aleph - a ALabel object.
      Returns:
      true if removed, false otherwise.

    • size

      public final int size()

      size.

      Returns:
      the number of elements of the map.

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