0

I have made part of an algorithm below where I need to use a queue, but in Java I can't modify the queue while iterating over it. I get a ConcurrentModificationException.

What I can I do about this? I've been thinking about this for several hours.

m, n = len(mat), len(mat[0])
visited = [[False] * n for row in range(m)]
q = deque()
destinations = set()

def should_visit(row, col):
    """Return true if (row,col) is a valid position not processed yet"""
    return 0 <= row < m and 0 <= col < n and \
           mat[row][col] != 'o' and not visited[row][col]

for r in range(m):
    for c in range(n):
        if mat[r][c] == 'r':
            q.append((r, c))
            visited[r][c] = True
        elif mat[r][c] == 'b':
            destinations.add((r, c))

dist = 1  # the level in breadth-first-search.
while q:
    for _ in range(len(q)):
        (r, c) = q.popleft()

        for (new_r, new_c) in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if should_visit(new_r, new_c):
                if (new_r, new_c) in destinations:
                    return dist
                q.append((new_r, new_c))
                visited[new_r][new_c] = True
    dist += 1
user17405569
  • 5
  • 2
  • https://stackoverflow.com/questions/602636/why-is-a-concurrentmodificationexception-thrown-and-how-to-debug-it – Ben Anderson Dec 15 '21 at 15:32
  • @BenAnderson But how do I addLast and removeFirst to the queue with this approach? – user17405569 Dec 15 '21 at 15:38
  • @user17405569 consider using an iterator maybe? – Ben Anderson Dec 15 '21 at 15:41
  • @rzwitserloot I've been told that my code gives that error. – user17405569 Dec 15 '21 at 15:41
  • @BenAnderson But how do I "removeFirst" and "addLast" with an iterator? – user17405569 Dec 15 '21 at 15:42
  • Actually, see the answer and other comments, I think I'm misunderstanding the situation – Ben Anderson Dec 15 '21 at 15:43
  • Oh, oops, there are 2 blocks of code in there. The first batch (the `for` loop) is broken. The second - the `while` loop is not. That while loop is pretty much how you'd do this. If you must loop, then instead of adding to `queue`, make a new list, add to that, then when you're done add all elements in the list to the queue. You have to not modify the list whilst iterating through it - that's one way to do that. – rzwitserloot Dec 15 '21 at 15:53

1 Answers1

1

You get that exception because you use foreach to loop over the queue. foreach's internal iterator will complain about the queue.removeFirst() call.

Using while (!queue.isEmpty()) { var cell = queue.removeFirst(); will work just fine. I don't believe that the foreach loop should even be there.

w_n
  • 345
  • 3
  • 7
  • Removing the for-each loop changes the output of the code completely and I'm not sure why. – user17405569 Dec 15 '21 at 15:46
  • I'm sure, since now you're missing a loop. If you need that loop, just copy the queue into a new queue and foreach loop over that. I can't go into detail on what your code output is supposed to be and what not. Also you shouldn't edit your post to reflect your code changes, this makes it hard for everyone to understand any answer. – w_n Dec 15 '21 at 15:51
  • Then what did you mean by ` don't believe that the foreach loop should even be there.`? – user17405569 Dec 15 '21 at 15:53
  • The meaning was that, from a glance, it made no sense to loop over the same queue with two loops. I can't tell if you need them both and one of them was obviously the source of your exception. – w_n Dec 15 '21 at 15:56