Bug in delete

[Optiminer]

Found a bug in deletion of intervals. The problem is that it can happen that the parent of the 'nil' node gets set during deletion which then can lead to undesired effects during iteration.

Attaching a unit test case to reproduce the problem.

import java.util.Iterator;

import org.junit.Test;

import datastructures.IntervalSetTree;

public class IntervalSetTreeTest {

	private static class Entry implements datastructures.Interval {

		private final String name;
		private final int start;
		private final int end;

		public Entry(String name, int start, int end) {
			this.name = name;
			this.start = start;
			this.end = end;
		}

		@Override
		public int start() {
			return start;
		}

		@Override
		public int end() {
			return end;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + end;
			result = prime * result + ((name == null) ? 0 : name.hashCode());
			result = prime * result + start;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Entry other = (Entry) obj;
			if (end != other.end)
				return false;
			if (name == null) {
				if (other.name != null)
					return false;
			} else if (!name.equals(other.name))
				return false;
			if (start != other.start)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return name + ": [" + start + "," + end + "]";
		}
	}

	@Test
	public void insertDeleteIterateOverlappers() {
		IntervalSetTree<Entry> tree = new IntervalSetTree<>();
		tree.insert(new Entry("558", 5, 6));
		tree.insert(new Entry("562", 15, 17));
		tree.insert(new Entry("464", 14, 16));
		tree.insert(new Entry("466", 12, 13));
		tree.insert(new Entry("912", 10, 11));
		tree.insert(new Entry("18224", 1, 3));
		tree.insert(new Entry("18226", 7, 9));
		tree.insert(new Entry("20524", 2, 4));
		tree.delete(new Entry("18226", 7, 9));
		tree.insert(new Entry("18226", 7, 8));
		
		tree.delete(new Entry("558", 5, 6)); // this sets parent of 'nil'
		
		Iterator<Entry> it = tree.overlappers(new Entry("558", 5, 6));
		while(it.hasNext()) {
			it.next(); // boom
		}
	}

}