1

For a project in my Data Structures class I have been tasked with creating a 3-Dimensional Range Tree where each dimension is a BST. I read this question, but it's an Android question, and the causes of our issues seem different, and the only answer was not accepted.

Wall of code coming shortly. Sorry.

Classes Involved:

  • Point3D<T>: Generic class containing the coordinates for the point. T extends Comparable<T>, and Point3D extends it as well
  • RangeTree<T>: Generic class containing the root for the entire tree and methods to build and search the tree

There are more classes than these 2, but they don't seem to be involved in why I'm getting a ConcurrentModificationException (link to CME). This is what I get when I run my driver:

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)

When RangeTree.build is called(Main.java:35), it takes a List<Point3D<T>> and passes that to RangeTree.build3DTree(RangeTree.java:11) which also takes # dimensions left to build, and an argument indicating whether or not the List is already sorted. RangeTree.java:126 in that method is the line where I call sortAscending in build3DTree.

sortAscending (it is recursive) does what it sounds like by comparing points on a certain dimension, starting with x(x = 0, y = 1, z = 2), if they are equal, it checks the next dimension, etc. Based on the above, it clearly works fine, except for that weird glitch where Line 172 somehow prints twice. Below is the sortAscending code (all print lines are purely for debugging):

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);
}

So, the final source of the CME seems to be in mergeList, and doesn't break until the call with the second half of the data. mergeList (iterative) takes two List<Point3D<T>> and merges them into one list that is sorted in ascending order, and returns it. Namely, it takes the first argument and modifies it into the merged list and returns it. Code:

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;
}

So for some reason the CME comes when I try to access the size of firstList. I have no idea why this occurring. I've hand-traced my code going through each step with the data set (posted below) and I can't see where the CME is coming from. Data:

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
Community
  • 1
  • 1
Ungeheuer
  • 1,393
  • 3
  • 17
  • 32
  • And just for the record: consider reading "Clean Code" by Robert Martin. Your code isn't that horrible; but it is also not really great to read. Many subtle things that could be improved ... and typically easy-to-read code makes it also easier to spot bugs ... – GhostCat Mar 28 '17 at 07:43
  • Where's your main function? – muzzlator Mar 28 '17 at 07:43
  • @GhostCat That's what I figured it should be based on Documentation. But when I drew it all out, the recursive sorting calls terminate and the lists they return aren't touched until merging time. Further, the first half of the data merges without exception (obviously it doesn't merge correctly), the second half breaks when I access the size of a list that is no longer being altered, nor being iterated. – Ungeheuer Mar 28 '17 at 07:43
  • Your stack trace says: at RangeTree.build(RangeTree.java:11) at Main.main(Main.java:35) so we should see what happens here :) – muzzlator Mar 28 '17 at 07:44
  • @muzzlator In my driver, but it is irrelevant. The line in the driver where the stacktrace originates is the build() method in RangeTree, which traces down the methods I've posted. – Ungeheuer Mar 28 '17 at 07:45
  • @muzzlator RangeTree.java:11 called RangeTree.build3DTree, and line 126 in that method calls `sortAscending`. Perhaps I should explicitly state this in the problem. I was trying to avoid posting a truckload of code. – Ungeheuer Mar 28 '17 at 07:47
  • @Ungeheuer Hm sure, I missed the calls to your functions in that stacktrace so I assumed the problem was higher up. Anyway looks like Ghostcat has got this – muzzlator Mar 28 '17 at 07:52

2 Answers2

2

The problem is that the function List#subList doesn't return a copy of the list that you're allowed to modify. You'll want to make a mutable copy of these lists. Not entirely sure why the concurrent check is only being done in size() but have a look at ConcurrentModificationException thrown by sublist for a discussion

Edit: Possible reason why the check only happens in size(): You're allowed changes that don't mess the structure of the sublist, for example swap operations with Collections.swap. They must only put the check in size() to allow these "structure-preserving" operations to be implemented without immediately crashing and so your call to add() might have been left alone.

Edit 2: One way of fixing this up might be to always pass in the original list as it is, and use indices to define sublist ranges for your recursion

Community
  • 1
  • 1
muzzlator
  • 742
  • 4
  • 10
  • That would likely explain why the first merging attempt didn't work, the subList can't be edited structurally. I didn't realize that was the case from reading the the List API. I'll have a go at it. – Ungeheuer Mar 28 '17 at 14:34
0

I would classify this problem as an excess of mutability, you start working on a list, then make views of this list, the add elements to one of the view, then merge, all within recursion. This is a recipe for bugs.

I think it would be possible to debug and solve your issue but it would not solve the main problem, which is recursive functions with side effects.

I would change both sort and merge to work with immutable arguments, don't change input lists, create new ones.

minus
  • 2,646
  • 15
  • 18