我编写了一个通用的 Partition 类(分区是将集合划分为不相交的子集,称为部分)。在内部,这是 aMap<T,Integer>
和 a Map<Integer,Set<T>>
,其中整数是零件的标签。例如partition.getLabel(T t)
给出 t 所在部分的标签,并将partition.move(T t, Integer label)
t 移动到由标签标记的分区(在内部,它更新两个 Map)。
但是我将对象集合移动到新部分的方法不起作用。似乎 Set.removeAll() 正在影响它的论点。我认为问题类似于 ConcurrentModificationException,但我无法解决。抱歉,代码比较长,但我已经标记了问题所在(大约一半),底部的输出应该清楚问题是什么 - 最后分区处于非法状态。
import java.util.*;
public class Partition<T> {
private Map<T,Integer> objToLabel = new HashMap<T,Integer>();
private Map<Integer,Set<T>> labelToObjs =
new HashMap<Integer,Set<T>>();
private List<Integer> unusedLabels;
private int size; // = number of elements
public Partition(Collection<T> objects) {
size = objects.size();
unusedLabels = new ArrayList<Integer>();
for (int i = 1; i < size; i++)
unusedLabels.add(i);
// Put all the objects in part 0.
Set<T> part = new HashSet<T>(objects);
for (T t : objects)
objToLabel.put(t,0);
labelToObjs.put(0,part);
}
public Integer getLabel(T t) {
return objToLabel.get(t);
}
public Set<T> getPart(Integer label) {
return labelToObjs.get(label);
}
public Set<T> getPart(T t) {
return getPart(getLabel(t));
}
public Integer newPart(T t) {
// Move t to a new part.
Integer newLabel = unusedLabels.remove(0);
labelToObjs.put(newLabel,new HashSet<T>());
move(t, newLabel);
return newLabel;
}
public Integer newPart(Collection<T> things) {
// Move things to a new part. (This assumes that
// they are all in the same part to start with.)
Integer newLabel = unusedLabels.remove(0);
labelToObjs.put(newLabel,new HashSet<T>());
moveAll(things, newLabel);
return newLabel;
}
public void move(T t, Integer label) {
// Move t to the part "label".
Integer oldLabel = getLabel(t);
getPart(oldLabel).remove(t);
if (getPart(oldLabel).isEmpty()) // if the old part is
labelToObjs.remove(oldLabel); // empty, remove it
getPart(label).add(t);
objToLabel.put(t,label);
}
public void moveAll(Collection<T> things, Integer label) {
// Move all the things from their current part to label.
// (This assumes all the things are in the same part.)
if (things.size()==0) return;
T arbitraryThing = new ArrayList<T>(things).get(0);
Set<T> oldPart = getPart(arbitraryThing);
// THIS IS WHERE IT SEEMS TO GO WRONG //////////////////////////
System.out.println(" oldPart = " + oldPart);
System.out.println(" things = " + things);
System.out.println("Now doing oldPart.removeAll(things) ...");
oldPart.removeAll(things);
System.out.println(" oldPart = " + oldPart);
System.out.println(" things = " + things);
if (oldPart.isEmpty())
labelToObjs.remove(objToLabel.get(arbitraryThing));
for (T t : things)
objToLabel.put(t,label);
getPart(label).addAll(things);
}
public String toString() {
StringBuilder result = new StringBuilder();
result.append("\nPARTITION OF " + size + " ELEMENTS INTO " +
labelToObjs.size() + " PART");
result.append((labelToObjs.size()==1 ? "" : "S") + "\n");
for (Map.Entry<Integer,Set<T>> mapEntry :
labelToObjs.entrySet()) {
result.append("PART " + mapEntry.getKey() + ": ");
result.append(mapEntry.getValue() + "\n");
}
return result.toString();
}
public static void main(String[] args) {
List<String> strings =
Arrays.asList("zero one two three".split(" "));
Partition<String> p = new Partition<String>(strings);
p.newPart(strings.get(3)); // move "three" to a new part
System.out.println(p);
System.out.println("Now moving all of three's part to the " +
"same part as zero.\n");
Collection<String> oldPart = p.getPart(strings.get(3));
//oldPart = Arrays.asList(new String[]{"three"}); // works fine!
p.moveAll(oldPart, p.getLabel(strings.get(0)));
System.out.println(p);
}
}
/* OUTPUT
PARTITION OF 4 ELEMENTS INTO 2 PARTS
PART 0: [two, one, zero]
PART 1: [three]
Now moving all of three's part to the same part as zero.
oldPart = [three]
things = [three]
Now doing oldPart.removeAll(things) ...
oldPart = []
things = []
PARTITION OF 4 ELEMENTS INTO 1 PART
PART 0: [two, one, zero]
*/