Para un proyecto en mi clase de Estructuras de datos, me encargaron crear un Árbol de rango tridimensional donde cada dimensión es un BST. Yo leoesta pregunta, pero es una pregunta de Android, y las causas de nuestros problemas parecen diferentes, y la única respuesta no fue aceptada.

Muro de código en breve. Lo siento.

Clases involucradas:

Point3D<T>: Clase genérica que contiene las coordenadas para el punto.T extends Comparable<T>yPoint3D lo extiende tambiénRangeTree<T>: Clase genérica que contiene la raíz del árbol completo y métodos para construir y buscar el árbol

Hay más clases que estas 2, pero no parecen estar involucradas en por qué obtengo una ConcurrentModificationException (enlace a CME) Esto es lo que obtengo cuando ejecuto mi controlador:

Read in 10 points //Number of points read in driver, this is okay
5//first median, 10 / 2
2//second median 5 / 2
first[0.082  0.791  0.832  , 0.366  0.136  0.009  ]//correct
second[0.138  0.968  0.391  , 0.414  0.785  0.883  , 0.546  0.044  0.133  ]//correct
merged[0.082  0.791  0.832  , 0.366  0.136  0.009  ]//not correct
first[0.082  0.791  0.832  , 0.366  0.136  0.009  ]//printed again. why?
2//secondHalf being sorted
first[0.415  0.64  0.099  , 0.513  0.612  0.466  ]//correct
second[0.091  0.719  0.772  , 0.199  0.999  0.086  , 0.896  0.835  0.86  ]//correct
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1231)
at java.util.ArrayList$SubList.size(ArrayList.java:1040)
at RangeTree.mergeList(RangeTree.java:189)
at RangeTree.sortAscending(RangeTree.java:175)
at RangeTree.sortAscending(RangeTree.java:173)
at RangeTree.build3DTree(RangeTree.java:126)
at RangeTree.build(RangeTree.java:11)
at Main.main(Main.java:35)

CuandoRangeTree.build se llama (Main.java:35), toma unList<Point3D<T>> y pasa eso aRangeTree.build3DTree(RangeTree.java:11) que también toma # dimensiones para construir, y un argumento que indica si elList ya está ordenado RangeTree.java:126 en ese método es la línea donde llamosortAscending enbuild3DTree.

sortAscending (es recursivo) hace lo que parece al comparar puntos en una determinada dimensión, comenzando conx(x = 0, y = 1, z = 2), si son iguales, verifica la siguiente dimensión, etc. Basado en lo anterior, claramente funciona bien, excepto por ese extraño error dondeLine 172 de alguna manera imprime dos veces. abajo esta elsortAscending código (todas las líneas de impresión son puramente para depuración):

private List<Point3D<T>> sortAscending(List<Point3D<T>> pointArr){

    if(pointArr.size() <= 3){//minimum sublist size is 3
        int median = findMedian(pointArr);
        Point3D<T> medianElement = pointArr.get(median);//retrieves coordinate to sort on
        int compareLeft = medianElement.compareTo(pointArr.get(median - 1));
        if(compareLeft < 0){//determine if median is less than element to its left. There will always be an element to the left
            pointArr.add(0, pointArr.remove(median));
            medianElement = pointArr.get(median);
        }
        try{//check median against element to its right. May not be valid if sublist is size 2
            int compareRight = medianElement.compareTo(pointArr.get(median + 1));
            if(compareRight > 0){
                Point3D<T> rightEnd = pointArr.get(median + 1);
                Point3D<T> leftEnd = pointArr.get(median - 1);
                if(rightEnd.compareTo(leftEnd) < 0)
                    pointArr.add(0, pointArr.remove(median + 1));
                else
                    pointArr.add(median, pointArr.remove(median + 1));
            }
        } catch (IndexOutOfBoundsException e){

        }
        return pointArr;
    }
    int median = findMedian(pointArr);//returns pointArr.size() / 2
    System.out.println(median);//for debugging
    List<Point3D<T>> firstHalf = sortAscending(pointArr.subList(0, median));
    System.out.println("first" + firstHalf); //prints twice, once when it should, and again after Line 176 prints
    List<Point3D<T>> secondHalf = sortAscending(pointArr.subList(median, pointArr.size()));//Line 173
    System.out.println("second" + secondHalf);//debugging
    List<Point3D<T>> merged = mergeList(firstHalf, secondHalf);//Line 175
    System.out.println("merged" + merged);//debugging
    return merged;//mergeList(firstHalf, secondHalf);
}

Entonces, la fuente final del CME parece estar enmergeList, y no se interrumpe hasta la llamada con la segunda mitad de los datos.mergeList (iterativo) toma dosList<Point3D<T>> y los fusiona en una lista que se ordena en orden ascendente y los devuelve. A saber, toma el primer argumento y lo modifica en la lista combinada y lo devuelve. Código:

private List<Point3D<T>> mergeList(List<Point3D<T>> firstList, List<Point3D<T>> secList){
    int sListSize = secList.size();
    int fListSize = firstList.size();//Line 188
    Point3D<T> firstListElement = firstList.get(fListSize - 1);
    Point3D<T> secListElement = secList.get(0);

    if(secListElement.compareTo(firstListElement) >= 0){//check to see if secList can be appended to end of firstList e.g. firstList = {1, 2} secList = {3, 4, 5}
        firstList.addAll(secList);
        return firstList;
    }

    secListElement = secList.get(secList.size() - 1);
    firstListElement = firstList.get(0);

    if(secListElement.compareTo(firstListElement) <= 0){//check to see if firstList can be appended to the end of secList e.g. secList = {1, 2} firstList = {3,4,5}
        secList.addAll(firstList);
        return secList;
    }

    for(int a = 0; a < secList.size(); a++){//take an element from secList and insert it into firstList
        secListElement = secList.get(a);
        int minIdx, maxIdx, median = findMedian(firstList);
        int mComp = secListElement.compareTo(firstList.get(median));//compare to the median of firstList to choose side to start from
        if(mComp < 0){
            minIdx = 0;
            maxIdx = median;
        }
        else if(mComp > 0){
            minIdx = median;
            maxIdx = firstList.size();
        }
        else{//if mComp is 0, insert it at median index
            firstList.add(median, secList.get(a));
            continue;
        }

        for(; minIdx < maxIdx; minIdx++){
            firstListElement = firstList.get(minIdx);
            int compare = secListElement.compareTo(firstListElement);
            if(compare <= 0){
                firstList.add(minIdx, secList.get(a));
                break;
            }
        }
    }
    return firstList;
}

Entonces, por alguna razón, el CME aparece cuando intento acceder al tamaño defirstList. No tengo idea de por qué ocurre esto. He rastreado manualmente mi código en cada paso con el conjunto de datos (publicado a continuación) y no puedo ver de dónde viene el CME. Datos:

10
0.366   0.136   0.009
0.082   0.791   0.832//beautiful 3D points
0.138   0.968   0.391
0.414   0.785   0.883
0.546   0.044   0.133
0.513   0.612   0.466
0.415   0.640   0.099
0.199   0.999   0.086
0.896   0.835   0.860
0.091   0.719   0.772
0.25 0.75 0.25 0.75 0.25 0.75//range queries. Code fails before we get to this
0.75 0.25 0.8 0.1 0.9 0.1
0.95 1.75 0.1 0.01 0.1 0.2
exit//no more queries