Deleting elements when iterating (iterator.Remove)

glenherb commented

2016-08-06 19:45:23 +00:00

(Migrated from github.com)

With go's map type, its safe to delete an element while iterating; does this same pattern hold for gods?

With go's `map` type, its safe to delete an element while iterating; does this same pattern hold for `gods`?

emirpasic commented

2016-08-06 23:35:23 +00:00

(Migrated from github.com)

Short answer: It's not safe.

Long answer: Because it's unsafe, we should find a way to guard against that if that's possible. For instance, Java would throw ConcurrentModificationException in that case. However, the iterator should provide a safe Remove() method. That might be tricky to implement in some structures, especially trees and structures using trees, where balancing takes place after deletion. That balancing logic would "shuffle" the elements around and a possible side effect would be duplicate iteration, i.e. iterating over an element that was already visited. However, for simpler structures, such as lists and stacks, this should be possible. Note that gods' HashMap doesn't even have an iterator, since Go randomizes the iteration.

Short answer: It's not safe. Long answer: Because it's unsafe, we should find a way to guard against that if that's possible. For instance, Java would throw ConcurrentModificationException in that case. However, the iterator should provide a safe Remove() method. That might be tricky to implement in some structures, especially trees and structures using trees, where balancing takes place after deletion. That balancing logic would "shuffle" the elements around and a possible side effect would be duplicate iteration, i.e. iterating over an element that was already visited. However, for simpler structures, such as lists and stacks, this should be possible. Note that gods' HashMap doesn't even have an iterator, since Go randomizes the iteration.

glenherb commented

2016-08-07 15:20:59 +00:00

(Migrated from github.com)

Would it be possible for an iterators Remove() to do a sort of "lazy delete" on a RBTree for instance? Which let the tree get a bit unbalanced and violate the RB properties, with the assumption that the next real remove/insert would start to repair it. I've know I've heard of some binary trees that only balance on inserts and never on remove, so it might be a good trade off if it doesn't add much/any complexity to the implementation

Would it be possible for an iterators `Remove()` to do a sort of "lazy delete" on a RBTree for instance? Which let the tree get a bit unbalanced and violate the RB properties, with the assumption that the next real remove/insert would start to repair it. I've know I've heard of some binary trees that only balance on inserts and never on remove, so it might be a good trade off if it doesn't add much/any complexity to the implementation

emirpasic commented

2016-08-10 11:39:47 +00:00

(Migrated from github.com)

Somehow I feel uneasy with the idea of violating the RB properties. Not that it doesn't make sense, it certainly does make sense when optimizing for a particular problem. However, I can not assume a particular problem and have to try to make this library as "generic" as possible for a wide range of problems.

After giving some thought, I realized that there might be a way of implementing the iterator.Remove() function without breaking the RB properties or the iteration. The idea is for the iterator to flag the current element as deleted. Also the iterator, in case of deletion, should store the deleted key, so that it can descend from the root and find (O(log n)) the next/previous element (bigger/less than that deleted key). That trade off (having to internally store extra information and search complexity after deletion) is probably worth the extra functionality.

I'll give that a try just to check that I haven't missed something and add that functionality then to all iterable structures (if possible).

Somehow I feel uneasy with the idea of violating the RB properties. Not that it doesn't make sense, it certainly does make sense when optimizing for a particular problem. However, I can not assume a particular problem and have to try to make this library as "generic" as possible for a wide range of problems. After giving some thought, I realized that there might be a way of implementing the iterator.Remove() function without breaking the RB properties or the iteration. The idea is for the iterator to flag the current element as deleted. Also the iterator, in case of deletion, should store the deleted key, so that it can descend from the root and find (O(log n)) the next/previous element (bigger/less than that deleted key). That trade off (having to internally store extra information and search complexity after deletion) is probably worth the extra functionality. I'll give that a try just to check that I haven't missed something and add that functionality then to all iterable structures (if possible).

raltnoeder commented

2017-07-15 10:50:34 +00:00

(Migrated from github.com)

Removing the element that the iterator has currently selected is actually not as tricky as it might seem, provided the iterators visit elements in-order (ascending or descending). While the tree does indeed shuffle elements or subtrees around while deleting, it always keeps the elements strictly ordered. Therefore, an iterator that visits elements in-order is guaranteed not to skip elements or visit elements twice. (That is also what Java's iterators do; they allow removal of the currently selected element, but throw ConcurrentModificationException if the tree is modified directly between calls of the iterator's methods)

One possibility is to keep a reference to the next element in the iterator's data structure. That way, the iterator can delete the current element, but still continue where it left off, and it also enables the iterator to tell whether the iteration is complete or not by just checking whether 'next' is a null reference. Initialization is to find the first (least or greatest value) element and store the reference in 'next'. Iteration is to copy 'next' to 'current', store the next element in 'next' and return 'current'. Deletion is to drop 'current' from the tree if 'current' is not a null reference and then set 'current' to null; iteration continues in-order as usual.

Removing the element that the iterator has currently selected is actually not as tricky as it might seem, provided the iterators visit elements in-order (ascending or descending). While the tree does indeed shuffle elements or subtrees around while deleting, it always keeps the elements strictly ordered. Therefore, an iterator that visits elements in-order is guaranteed not to skip elements or visit elements twice. (That is also what Java's iterators do; they allow removal of the currently selected element, but throw ConcurrentModificationException if the tree is modified directly between calls of the iterator's methods) One possibility is to keep a reference to the next element in the iterator's data structure. That way, the iterator can delete the current element, but still continue where it left off, and it also enables the iterator to tell whether the iteration is complete or not by just checking whether 'next' is a null reference. Initialization is to find the first (least or greatest value) element and store the reference in 'next'. Iteration is to copy 'next' to 'current', store the next element in 'next' and return 'current'. Deletion is to drop 'current' from the tree if 'current' is not a null reference and then set 'current' to null; iteration continues in-order as usual.

emirpasic commented

2020-03-31 18:52:22 +00:00

(Migrated from github.com)

Closing for now until I find more time to implement this

Rows
Columns

Deleting elements when iterating (iterator.Remove) #28