001package org.cpsolver.ifs.assignment; 002 003import java.util.Collection; 004import java.util.HashMap; 005import java.util.HashSet; 006import java.util.LinkedHashMap; 007import java.util.Map; 008import java.util.Set; 009 010import org.cpsolver.ifs.assignment.context.InheritedAssignmentContextHolder; 011import org.cpsolver.ifs.model.Value; 012import org.cpsolver.ifs.model.Variable; 013import org.cpsolver.ifs.solution.Solution; 014 015 016/** 017 * Optimistic inherited assignment. This assignment does not expect the parent assignment to change 018 * much and it only remembers local changes made in this assignment. Use with caution. 019 * 020 * @see InheritedAssignment 021 * 022 * @version IFS 1.3 (Iterative Forward Search)<br> 023 * Copyright (C) 2014 Tomáš Müller<br> 024 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 025 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 026 * <br> 027 * This library is free software; you can redistribute it and/or modify 028 * it under the terms of the GNU Lesser General Public License as 029 * published by the Free Software Foundation; either version 3 of the 030 * License, or (at your option) any later version. <br> 031 * <br> 032 * This library is distributed in the hope that it will be useful, but 033 * WITHOUT ANY WARRANTY; without even the implied warranty of 034 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 035 * Lesser General Public License for more details. <br> 036 * <br> 037 * You should have received a copy of the GNU Lesser General Public 038 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 039 * @param <V> Variable 040 * @param <T> Value 041 **/ 042public class OptimisticInheritedAssignment<V extends Variable<V, T>, T extends Value<V, T>> extends AssignmentAbstract<V, T> implements InheritedAssignment<V, T> { 043 private Assignment<V, T> iParent; 044 private Map<V, T> iAssignments = new LinkedHashMap<V, T>(); 045 private Set<V> iDirty = new HashSet<V>(); 046 private Map<V, Long> iIteration = new HashMap<V, Long>(); 047 private long iVersion = -1; 048 049 public OptimisticInheritedAssignment(Solution<V, T> parent, int index) { 050 // super(new InheritedAssignmentContextHolder<V, T>(index, parent.getIteration()), index, parent); 051 super(new InheritedAssignmentContextHolder<V, T>(index, parent.getIteration())); 052 iParent = parent.getAssignment(); 053 iVersion = parent.getIteration(); 054 } 055 056 @Override 057 public long getIteration(V variable) { 058 Long it = iIteration.get(variable); 059 return (it != null ? it : iDirty.contains(variable) ? 0 : iParent.getIteration(variable)); 060 } 061 062 @Override 063 public Collection<V> assignedVariables() { 064 Set<V> variables = new HashSet<V>(iParent.assignedVariables()); 065 variables.removeAll(iDirty); 066 variables.addAll(iAssignments.keySet()); 067 return variables; 068 } 069 070 @Override 071 public Collection<T> assignedValues() { 072 Set<T> values = new HashSet<T>(); 073 for (T val: iParent.assignedValues()) { 074 if (val != null && !iDirty.contains(val.variable())) 075 values.add(val); 076 } 077 values.addAll(iAssignments.values()); 078 return values; 079 } 080 081 @Override 082 public int nrAssignedVariables() { 083 return iAssignments.size() + iParent.nrAssignedVariables() - iDirty.size(); 084 } 085 086 @Override 087 protected T getValueInternal(V variable) { 088 T value = (iAssignments.isEmpty() ? null : iAssignments.get(variable)); 089 return (value != null ? value : iDirty.contains(variable) ? null : iParent.getValue(variable)); 090 } 091 092 @Override 093 protected void setValueInternal(long iteration, V variable, T value) { 094 if (value == null) { 095 iAssignments.remove(variable); 096 iIteration.remove(variable); 097 if (iParent.getValue(variable) != null) 098 iDirty.add(variable); 099 } else { 100 iAssignments.put(variable, value); 101 if (iteration > 0) 102 iIteration.put(variable, iteration); 103 iDirty.remove(variable); 104 } 105 } 106 107 @Override 108 public Assignment<V, T> getParentAssignment() { 109 return iParent; 110 } 111 112 @Override 113 public long getVersion() { 114 return iVersion; 115 } 116}