removeAll, кажется, влияет на его аргумент - PullRequest
Новая
       16

removeAll, кажется, влияет на его аргумент

1 голос
/ 19 января 2011

Я написал общий класс Partition (раздел - это разделение набора на непересекающиеся подмножества, называемые частями).Внутренне это Map<T,Integer> и Map<Integer,Set<T>>, где целые числа являются метками частей.Например, partition.getLabel(T t) дает метку части, в которой находится t, а partition.move(T t, Integer label) перемещает t в раздел, помеченный меткой (внутри он обновляет обе карты).

Но мой метод перемещения коллекции объектов в новую деталь не работает.Похоже, что 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]
*/

Ответы [ 2 ]

0 голосов
/ 19 января 2011

Ваш код очень запутанный, но, насколько я понимаю, oldPart и things на самом деле один и тот же объект.Set.removeAll() определенно не влияет на его аргумент, если он не является тем же объектом, к которому он был вызван: 

public boolean removeAll(Collection<?> c) {
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

Обновление:

Простой способ устранить этоэто использовать копию things в методе moveAll().Действительно, такая копия уже существует. 

T arbitraryThing = new ArrayList<T>(things).get(0);

Эта строка создает, но затем мгновенно отбрасывает копию things.Поэтому я бы предложил заменить его на: 

ArrayList<T> thingsToRemove = new ArrayList<T>(things)
T arbitraryThing = thingsToRemove.get(0);

И в остальной части метода заменить все ссылки на things на thingsToRemove.

0 голосов
/ 19 января 2011

Используя мой отладчик, я устанавливаю точку останова перед removeAll, и я вижу (как я подозревал), что oldPart и вещи в одной коллекции, поэтому удаление всех элементов очищает эту коллекцию.

...