Package it.univr.di.labeledvalue

Class LabeledIntTreeMap

java.lang.Object
it.univr.di.labeledvalue.AbstractLabeledIntMap
it.univr.di.labeledvalue.LabeledIntTreeMap
All Implemented Interfaces:
LabeledIntMap, Serializable
Direct Known Subclasses:
LabeledIntTreeMap.LabeledIntTreeMapView, LabeledIntTreeSimpleMap
public class LabeledIntTreeMap extends AbstractLabeledIntMap
Simple implementation of LabeledIntMap interface.

An experimental result on 2016-01-13 showed that using base there is a small improvement in the performance.

Execution time (ms) for some operations w.r.t the core data structure of the class (Object2IntMap).
Operation Using AVL or RB Tree (ms) Using OpenHash (ms) Using fastUtil.Array (ms)
Create 1st map 0.236499088 0.15073823 0.140981928
min value 0.004523044 0.005419635 0.007725364
Retrieve value 0.000697368 0.000216167E 0.000172576
Simplification ~1.275382 ~1.221648 ~0.328194
All code for performance tests is in LabeledIntTreeMapTest class (not public available).
Version:
$Rev: 851 $
Author:
Roberto Posenato
See Also:

  • Field Details

    • base

      char[] base
      Set of propositions forming a base for the labels of the map.

    • mainInt2SetMap

      it.unimi.dsi.fastutil.ints.Int2ObjectArrayMap<it.unimi.dsi.fastutil.objects.Object2IntMap<Label>> mainInt2SetMap
      Design choice: the set of labeled values of this map is organized as a collection of sets each containing labels of the same length. This allows the label minimization task to be performed in a more systematic and efficient way. The efficiency has been proved comparing this implementation with one in which the map has been realized with a standard map and the minimization task determines the same length labels every time it needs it.

  • Constructor Details

    • LabeledIntTreeMap

      LabeledIntTreeMap(LabeledIntMap lvm, boolean optimize)
      Constructor to clone the structure. For optimization issue, this method clone only LabeledIntTreeMap object.
      Parameters:
      lvm - the LabeledValueTreeMap to clone. If lvm is null, this will be an empty map.
      optimize - true for having the label shortest as possible, false otherwise. For example, the set {(0, ¬C), (1, C)} is represented as {(0, ⊡), (1, C)} if this parameter is true.

    • LabeledIntTreeMap

      LabeledIntTreeMap(LabeledIntMap lvm)
      Constructor to clone the structure. For optimization issue, this method clone only LabeledIntTreeMap object.
      Parameters:
      lvm - the LabeledValueTreeMap to clone. If lvm is null, this will be an empty map.

    • LabeledIntTreeMap

      LabeledIntTreeMap(boolean optimize)
      Necessary constructor for the factory. The internal structure is built and empty.
      Parameters:
      optimize - true for having the label shortest as possible, false otherwise. For example, the set {(0, ¬C), (1, C)} is represented as {(0, ⊡), (1, C)} if this parameter is true.

    • LabeledIntTreeMap

      LabeledIntTreeMap()
      Necessary constructor for the factory. The internal structure is built and empty.

  • Method Details

    • alreadyRepresents

      public boolean alreadyRepresents(Label newLabel, int newValue)
      Parameters:
      newLabel - a Label object.
      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()
      Description copied from interface: LabeledIntMap
      Remove all entries of the map.
      See Also:

    • entrySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<Label>> entrySet()
      The set of all entries of the map. The set can be a view of the map, so any modification of the map can be reflected on the returned entrySet.
      In other word, don't modify the map during the use of this returned set.
      This method returns a copy of the view of the map. Any modification of the map IS NOT propagated to the return set.
      In other word, it is possible to iterate on this map for modifying the original map without worried to lost any element.
      Up to 1000 items in the map it is better to use this method instead of keySet() and get(Label) .
      With 1000 or more items, it is better to use keySet() approach.
      Returns:
      The set of all entries of the map.
      See Also:

    • entrySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<Label>> entrySet(@Nonnull it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.fastutil.objects.Object2IntMap.Entry<Label>> setToReuse)
      Description copied from interface: LabeledIntMap
      The set of all entries of the map. The set can be a view of the map, so any modification of the map can be reflected on the returned entrySet().
      In other word, don't modify the map during the use of this returned set.
      Parameters:
      setToReuse - a ObjectSet object.
      Returns:
      The set of all entries of the map.
      See Also:

    • get

      public int get(Label l)
      Parameters:
      l - an Label object.
      Returns:
      the value associated to l if it exists, Constants.INT_NULL otherwise.

    • getMaxValue

      public int getMaxValue()
      Returns:
      the maximum int value present in the set if the set is not empty; Constants.INT_NULL otherwise.

    • getMinValue

      public int getMinValue()
      Returns:
      the minimum int value present in the set if the set is not empty; Constants.INT_NULL otherwise.

    • getMinValueSubsumedBy

      public int getMinValueSubsumedBy(Label l)
      Description copied from interface: LabeledIntMap
      Returns the minimal value among those associated to labels subsumed by l if it exists, Constants.INT_NULL otherwise.
      Parameters:
      l - If it is null, Constants.INT_NULL is returned.
      Returns:
      minimal value among those associated to labels subsumed by l if it exists, Constants.INT_NULL otherwise.

    • keySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<Label> keySet()
      Description copied from interface: LabeledIntMap
      A copy of all labels in the map. The set must not be connected with the map.
      Returns:
      a copy of all labels in the map.

    • keySet

      public it.unimi.dsi.fastutil.objects.ObjectSet<Label> keySet(it.unimi.dsi.fastutil.objects.ObjectSet<Label> setToReuse)
      Parameters:
      setToReuse - a set to be reused for filling with the copy of labels
      Returns:
      a copy of all labels in the map. The set must not be connected with the map.

    • newInstance

      public LabeledIntTreeMap newInstance()
      Description copied from interface: LabeledIntMap
      Factory
      Returns:
      an object of type LabeledIntMap.

    • newInstance

      public LabeledIntTreeMap newInstance(boolean optimize)
      Description copied from interface: LabeledIntMap
      Factory
      Parameters:
      optimize - true for having the label shortest as possible, false otherwise. For example, the set {(0, ¬C), (1, C)} is represented as {(0, ⊡), (1, C)} if this parameter is true.
      Returns:
      an object of type LabeledIntMap.

    • newInstance

      public LabeledIntTreeMap newInstance(LabeledIntMap lim)
      Description copied from interface: LabeledIntMap
      Factory
      Parameters:
      lim - an object to clone.
      Returns:
      an object of type LabeledIntMap.

    • newInstance

      public LabeledIntTreeMap newInstance(LabeledIntMap lim, boolean optimize)
      Description copied from interface: LabeledIntMap
      Factory
      Parameters:
      lim - an object to clone.
      optimize - true for having the label shortest as possible, false otherwise. For example, the set {(0, ¬C), (1, C)} is represented as {(0, ⊡), (1, C)} if this parameter is true.
      Returns:
      an object of type LabeledIntMap.

    • put

      public boolean put(Label newLabel, int newValue)
      Put a label with value i if label l is not null and there is not a labeled value in the set with label l or it is present but with a value higher than l.

      Not mandatory: 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. Adds the pair ⟨l,i⟩.
      Moreover, tries to eliminate all labels that are redundant.
      IMPORTANT!
      This version of the method is very redundant but simple to check!

      Parameters:
      newLabel - a not null label.
      newValue - a not Constants.INT_NULL value.
      Returns:
      true if (l,i) has been inserted. Since an insertion can remove more than one redundant labeled values, it is nonsensical to return "the old value" as expected from a classical put method.

    • putForcibly

      public void putForcibly(@Nonnull Label l, int i)
      Description copied from interface: LabeledIntMap
      Put the labeled value without any control. It is dangerous, but it can help in some cases.
      Parameters:
      l - a Label object.
      i - the new value. If it is Constants#INT_NULL, the method does nothing.

    • remove

      public int remove(Label l)
      Description copied from interface: LabeledIntMap
      Remove the label l from the map. If the l is not present, it does nothing.
      Parameters:
      l - a not null label.
      Returns:
      the previous value associated with l, or Constants.INT_NULL if there was no mapping for l.
      See Also:

    • unmodifiable

      public LabeledIntTreeMap.LabeledIntTreeMapView unmodifiable()
      Returns:
      a read-only view of this.

    • values

      public it.unimi.dsi.fastutil.ints.IntSet values()
      Returns:
      the set of all integer present in the map as an ordered list.