* 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. * * *
| 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).
*
* @author Roberto Posenato
* @version $Id: $Id
*/
public class LabeledALabelIntTreeMap implements Serializable {
/**
* A read-only view of an object
*
* @author posenato
*/
public static class LabeledALabelIntTreeMapView extends LabeledALabelIntTreeMap {
/**
*
*/
private static final long serialVersionUID = 1L;
/**
* @param inputMap
*/
public LabeledALabelIntTreeMapView(LabeledALabelIntTreeMap inputMap) {
this.map = inputMap.map;
}
@Override
/**
* Object Read-only. It does nothing.
*/
public boolean mergeTriple(Label l, ALabel p, int i) {
return false;
}
@Override
/**
* Object Read-only. It does nothing.
*/
public boolean mergeTriple(Label newLabel, ALabel newAlabel, int newValue, boolean force) {
return false;
}
@Override
/**
* Object Read-only. It does nothing.
*/
public boolean mergeTriple(String label, ALabel p, int i) {
return false;
}
@Override
/**
* Object Read-only. It does nothing.
*/
public boolean mergeTriple(String label, ALabel p, int i, boolean force) {
return false;
}
@Override
/**
* Object Read-only. It does nothing.
*/
public LabeledIntTreeMap put(ALabel alabel, LabeledIntMap labeledValueMap) {
return null;
}
@Override
/**
* Object Read-only. It does nothing.
*/
public boolean putTriple(Label l, ALabel p, int i) {
return false;
}
@Override
/**
* Object Read-only. It does nothing.
*/
public int remove(Label l, ALabel p) {
return Constants.INT_NULL;
}
}
/**
* Keyword \w because it is necessary to accept also node names!
*/
static final String labelCharsRE = ALabelAlphabet.ALETTER + ALabel.ALABEL_SEPARATORstring + ",\\-" + Constants.NOT + Constants.EMPTY_LABEL
+ Constants.INFINITY_SYMBOLstring + Constants.UNKNOWNstring + Constants.EMPTY_UPPER_CASE_LABELstring + Literal.PROPOSITIONS;
/**
* Matcher for RE
*/
static final Pattern patternlabelCharsRE = Pattern.compile("\\{[\\(" + labelCharsRE + "\\) ]*\\}");
/**
* logger
*/
private static final Logger LOG = Logger.getLogger("LabeledALabelIntTreeMap");
/**
*
*/
private static final long serialVersionUID = 2L;
/**
* @param label
* @param value
* @param nodeName this name is printed as it is. This method is necessary for saving the values of the map in a file.
* @return the canonical representation of the triple (as stated in ICAPS/ICAART papers), i.e.
* {@link Constants#OPEN_PAIR}Alabel, value, label{@link Constants#CLOSE_PAIR}
*/
static final public String entryAsString(Label label, int value, ALabel nodeName) {
StringBuffer s = new StringBuffer();
s.append(Constants.OPEN_PAIR);
s.append(nodeName);
s.append(", ");
s.append(Constants.formatInt(value));
s.append(", ");
s.append(label);
s.append(Constants.CLOSE_PAIR);
return s.toString();
}
/**
* 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 {@link #toString()}.
* For historical reasons, the method is capable to parse two different map
* format:"{[(⟨label⟩, ⟨Alabel⟩, ⟨value⟩) ]*}
* or "{[(⟨Alabel⟩, ⟨value⟩, ⟨label⟩) ]*}", where [a]* is a meta constructor for saying zero o more 'a'.
*
* @param arg a {@link java.lang.String} object.
* @param alphabet
* @return a LabeledPairMap object if args represents a valid map, null otherwise.
*/
public static LabeledALabelIntTreeMap parse(String arg, ALabelAlphabet alphabet) {
// final Pattern splitterNode = Pattern.compile("〈|; ");
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("Begin parse: " + arg);
}
}
if ((arg == null) || (arg.length() < 3))
return null;
if (!patternlabelCharsRE.matcher(arg).matches())
return null;
final LabeledALabelIntTreeMap newMap = new LabeledALabelIntTreeMap();
arg = arg.replaceAll("[{}]", "");
// arg = arg.substring(1, arg.length() - 2);
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("Before split: '" + arg + "'");
}
}
final Pattern splitterEntry = Pattern.compile("\\)|\\(");
final String[] entryThreesome = splitterEntry.split(arg);
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("EntryThreesome: " + Arrays.toString(entryThreesome));
}
}
final Pattern splitterTriple = Pattern.compile(", ");
if (alphabet == null)
alphabet = new ALabelAlphabet();
int j;
String labelStr, aLabelStr, valueStr;
for (final String s : entryThreesome) {
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("s: '" + s + "'");
}
}
if (s.length() > 1) {// s can be empty or a space.
final String[] triple = splitterTriple.split(s);
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("triple: " + Arrays.toString(triple));
}
}
Label l = Label.parse(triple[2]);
if (l == null) {
// probably it is the old format
labelStr = triple[0];
aLabelStr = triple[1];
valueStr = triple[2];
} else {
// new format
aLabelStr = triple[0];
valueStr = triple[1];
labelStr = triple[2];
}
if (l == null)
l = Label.parse(labelStr);
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("Label: " + l);
}
}
if (valueStr.equals("-" + Constants.INFINITY_SYMBOLstring))
j = Constants.INT_NEG_INFINITE;
else
j = Integer.parseInt(valueStr);
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("Value: " + j);
}
}
// LabeledNode is represented as " 〈; {}; Obs: null〉 "
// final String nodePart = labLitInt[1];//splitterNode.split(labLitInt[1]);
// System.out.println(aLabelStr);
final ALabel node = ALabel.parse(aLabelStr, alphabet);
if (Debug.ON) {
if (LOG.isLoggable(Level.FINEST)) {
LabeledALabelIntTreeMap.LOG.finest("LabeledNode: " + node);
}
}
newMap.mergeTriple(l, node, j, false);
}
}
return newMap;
}
/**
* Data structure.
*
* - 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.
*
- A labeled Upper/Lower Case value is a pair (nodeName, (plabel, value)), where plabel
* represents scenario where value holds.
* Such kind of constraint has been introduced by Hunsbergher, Combi, and Posenato in 2012.
*
- Each plabel is a conjunction of literals, i.e., of type {@link Label}.
* - Since there may be more pairs with the same 'nodeName', a labeled Upper/Lower Case value is as a map of (nodeName, LabeledIntMap). See
* {@link LabeledIntMap}.
*
- 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.
*
- Since the introduction of ALabel, we suggest to use two @{link {@link LabeledALabelIntTreeMap}. One to represent the upper-case values.
* The other for lower-case ones.
*
*/
protected Object2ObjectRBTreeMap map;// ObjectArrayMap is not suitable when the map is greater than 1000 values!
/**
* Number of elements
*/
private int count;
/**
* Simple constructor. The internal structure is built and empty.
*/
public LabeledALabelIntTreeMap() {
this.map = new Object2ObjectRBTreeMap<>();
this.count = 0;
}
/**
* Constructor to clone the structure.
* All internal maps will be independent from lvm ones while elements of maps will be shared.
* The motivation is that usually a Label inside a map is managed as read-only.
*
* @param lvm the map to clone. If null, 'this' will be a empty map.
*/
public LabeledALabelIntTreeMap(final LabeledALabelIntTreeMap lvm) {
this();
if (lvm == null)
return;
for (final ALabel alabel : lvm.keySet()) {
final LabeledIntTreeMap map1 = new LabeledIntTreeMap(lvm.get(alabel));
this.map.put(alabel, map1);
this.count += map1.size();
}
}
/**
* @return a set view of this map. In particular, it returns a set of (ALabel, LabeledIntTreeMap) objects.
* Be careful: returned LabeledIntTreeMap(s) are not a copy but the maps inside this object.
* THIS METHOD HAS NOT A GOOD PERFORMANCE
* public ObjectSet> entrySet() {
* return this.map.entrySet();
* }
*/
/**
* @param newLabel it must be not null
* @param newAlabel it must be not null
* @param newValue
* @return 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.
*/
public boolean alreadyRepresents(final Label newLabel, final ALabel newAlabel, final int newValue) {
final LabeledIntTreeMap map1 = this.map.get(newAlabel);
if (map1 != null && map1.alreadyRepresents(newLabel, newValue))
return true;
/**
* Check if there is already a value in the map having shorter ALabel that can represent the new value.
*/
final int newALabelSize = newAlabel.size();
for (ALabel otherALabel : this.keySet()) {
if (newALabelSize <= otherALabel.size() || !newAlabel.contains(otherALabel))
continue;
LabeledIntTreeMap labeledValuesOfOtherALabel = this.get(otherALabel);
if (labeledValuesOfOtherALabel.alreadyRepresents(newLabel, newValue)) {
// a smaller conjuncted upper case value map already contains the input value
return true;
}
}
return false;
}
/**
*
*/
public void clear() {
this.map.clear();
this.count = 0;
}
/** {@inheritDoc} */
@Override
public boolean equals(final Object o) {
if (o == this)
return true;
if (!(o instanceof LabeledALabelIntTreeMap))
return false;
final LabeledALabelIntTreeMap lvm = (LabeledALabelIntTreeMap) o;
return this.map.equals(lvm.map);// this equals checks the size... so NO empty pair (key, {}) cannot be stored!
}
/**
* @param alabel
* @return the value to which the specified key is mapped, or null if this map contains no mapping for the key
*/
public final LabeledIntTreeMap get(final ALabel alabel) {
return this.map.get(alabel);
}
/**
* @return the minimal value of this map not considering upper/lower case label (node label), {@link Constants#INT_NULL} if the map is empty.
*/
public Object2ObjectMap.Entry> getMinValue() {
if (this.size() == 0)
return new AbstractObject2ObjectMap.BasicEntry<>(Label.emptyLabel, new BasicEntry<>(ALabel.emptyLabel, Constants.INT_NULL));
int min = Integer.MAX_VALUE;
int v = min;
Entry