d288d7cbe9a665a0841e85c7006a9f7409fa5177
[idea/community.git] / platform / core-impl / src / com / intellij / openapi / editor / impl / IntervalTreeImpl.java
1 /*
2  * Copyright 2000-2010 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.openapi.editor.impl;
17
18 import com.intellij.openapi.editor.ex.DisposableIterator;
19 import com.intellij.openapi.util.Getter;
20 import com.intellij.openapi.util.ProperTextRange;
21 import com.intellij.openapi.util.Ref;
22 import com.intellij.openapi.util.Trinity;
23 import com.intellij.util.IncorrectOperationException;
24 import com.intellij.util.Processor;
25 import com.intellij.util.SmartList;
26 import com.intellij.util.WalkingState;
27 import com.intellij.util.concurrency.AtomicFieldUpdater;
28 import gnu.trove.TLongHashSet;
29 import org.jetbrains.annotations.NonNls;
30 import org.jetbrains.annotations.NotNull;
31
32 import java.lang.ref.ReferenceQueue;
33 import java.lang.ref.WeakReference;
34 import java.util.ConcurrentModificationException;
35 import java.util.List;
36 import java.util.NoSuchElementException;
37 import java.util.concurrent.locks.Lock;
38 import java.util.concurrent.locks.ReadWriteLock;
39 import java.util.concurrent.locks.ReentrantReadWriteLock;
40
41 /**
42  * User: cdr
43  */
44 public abstract class IntervalTreeImpl<T extends MutableInterval> extends RedBlackTree<T> implements IntervalTree<T> {
45   private int keySize; // number of all intervals, counting all duplicates, some of them maybe gced
46   protected final ReadWriteLock l = new ReentrantReadWriteLock();
47
48   protected abstract int compareEqualStartIntervals(@NotNull IntervalNode<T> i1, @NotNull IntervalNode<T> i2);
49   private final ReferenceQueue<T> myReferenceQueue = new ReferenceQueue<T>();
50   private int deadReferenceCount;
51
52   protected static class IntervalNode<E extends MutableInterval> extends RedBlackTree.Node<E> implements MutableInterval {
53     private volatile int myStart;
54     private volatile int myEnd;
55     private volatile boolean isValid = true;
56     protected final List<Getter<E>> intervals;
57     protected int maxEnd; // max of all intervalEnd()s among all children.
58     protected int delta;  // delta of startOffset. getStartOffset() = myStartOffset + Sum of deltas up to root
59
60     private volatile long cachedDeltaUpToRoot; // field (packed to long for atomicity) containing deltaUpToRoot, node modCount and allDeltasUpAreNull flag
61     private final IntervalTreeImpl<E> myIntervalTree;
62
63     public IntervalNode(IntervalTreeImpl<E> intervalTree, @NotNull E key, int start, int end) {
64       // maxEnd == 0 so to not disrupt existing maxes
65       myIntervalTree = intervalTree;
66       myStart = start;
67       myEnd = end;
68       intervals = new SmartList<Getter<E>>(createGetter(key));
69     }
70
71     @Override
72     public IntervalNode<E> getLeft() {
73       return (IntervalNode<E>)left;
74     }
75
76     @Override
77     public IntervalNode<E> getRight() {
78       return (IntervalNode<E>)right;
79     }
80
81     @Override
82     public IntervalNode<E> getParent() {
83       return (IntervalNode<E>)parent;
84     }
85
86     @Override
87     public boolean processAliveKeys(@NotNull Processor<? super E> processor) {
88       //noinspection ForLoopReplaceableByForEach
89       for (int i = 0; i < intervals.size(); i++) {
90         Getter<E> interval = intervals.get(i);
91         E key = interval.get();
92         if (key != null && !processor.process(key)) return false;
93       }
94       return true;
95     }
96
97     @Override
98     public boolean hasAliveKey(boolean purgeDead) {
99       boolean hasAliveInterval = false;
100       for (int i = intervals.size() - 1; i >= 0; i--) {
101         Getter<E> interval = intervals.get(i);
102         if (interval.get() != null) {
103           hasAliveInterval = true;
104           if (purgeDead) {
105             continue;
106           }
107           else {
108             break;
109           }
110         }
111         if (purgeDead) {
112           myIntervalTree.assertUnderWriteLock();
113           removeIntervalInternal(i);
114         }
115       }
116       return hasAliveInterval;
117     }
118
119     // removes interval and the node, if node became empty
120     // returns true if node was removed
121     private boolean removeInterval(@NotNull E key) {
122       myIntervalTree.checkBelongsToTheTree(key, true);
123       myIntervalTree.assertUnderWriteLock();
124       for (int i = intervals.size() - 1; i >= 0; i--) {
125         Getter<E> interval = intervals.get(i);
126         E t = interval.get();
127         if (t == key) {
128           removeIntervalInternal(i);
129           if (intervals.isEmpty()) {
130             myIntervalTree.removeNode(this);
131             return true;
132           }
133           return false;
134         }
135       }
136       assert false: "interval not found: "+key +"; "+ intervals;
137       return false;
138     }
139
140     public void removeIntervalInternal(int i) {
141       intervals.remove(i);
142       assert myIntervalTree.keySize > 0 : myIntervalTree.keySize;
143       myIntervalTree.keySize--;
144     }
145
146     public void addInterval(@NotNull E interval) {
147       myIntervalTree.assertUnderWriteLock();
148       intervals.add(createGetter(interval));
149       myIntervalTree.keySize++;
150       myIntervalTree.setNode(interval, this);
151     }
152
153     protected Getter<E> createGetter(@NotNull E interval) {
154       return new WeakReferencedGetter<E>(interval, myIntervalTree.myReferenceQueue);
155     }
156
157     private static class WeakReferencedGetter<T> extends WeakReference<T> implements Getter<T> {
158       public WeakReferencedGetter(T referent, ReferenceQueue<? super T> q) {
159         super(referent, q);
160       }
161
162       @NonNls
163       @Override
164       public String toString() {
165         return "Ref: " + get();
166       }
167     }
168
169     protected int computeDeltaUpToRoot() {
170       return computeDeltaUpToRoot(new NodeCachedOffsets());
171     }
172     protected int computeDeltaUpToRoot(NodeCachedOffsets cached) {
173       restart:
174       while (true) { // have to restart on failure to update cached offsets in case of concurrent modification
175         if (!isValid()) return 0;
176         int treeModCount = myIntervalTree.modCount;
177         unpackCachedValuesTo(cached);
178         if (cached.modCount == treeModCount) {
179           return cached.deltaUpToRoot;
180         }
181         try {
182           myIntervalTree.l.readLock().lock();
183
184           IntervalNode<E> node = this;
185           IntervalNode<E> treeRoot = myIntervalTree.getRoot();
186           if (treeRoot == null) return delta; // someone modified the tree in the meantime
187           int deltaUp = 0;
188           boolean allDeltasAreNull = true;
189           int height = 0;
190           long path = 0; // path to this node from the root; 0 bit means we choose left subtree, 1 bit means we choose right subtree
191           while (node != treeRoot) {
192             node.unpackCachedValuesTo(cached);
193             if (node.isValid() && cached.modCount == treeModCount) {
194               deltaUp = cached.deltaUpToRoot - node.delta;
195               allDeltasAreNull = cached.allDeltasUpAreNull;
196               break;
197             }
198             IntervalNode<E> parent = node.getParent();
199             if (parent == null) {
200               return deltaUp;  // can happen when remove node and explicitly set valid to true (e.g. in RangeMarkerTree)
201             }
202             path = (path << 1) |  (parent.getLeft() == node ? 0 : 1);
203             node = parent;
204             height++;
205           }
206           // path to this node fits to long
207           assert height < 63 : height;
208
209           // cache deltas in every node from the root down this
210           while (true) {
211             if (node.isValid()) {
212               int nodeDelta = node.delta;
213               deltaUp += nodeDelta;
214               allDeltasAreNull &= nodeDelta == 0;
215               if (!node.tryToSetCachedValues(deltaUp, allDeltasAreNull, treeModCount)) {
216                 continue restart;
217               }
218             }
219
220             if (node == this) break;
221             node = (path & 1) == 0 ? node.getLeft() : node.getRight();
222             path >>= 1;
223             if (node == null) return deltaUp; // can only happen in case of concurrently modification
224           }
225
226           assert deltaUp == 0 || !allDeltasAreNull;
227           return deltaUp;
228         }
229         finally {
230           myIntervalTree.l.readLock().unlock();
231         }
232       }
233     }
234
235     protected int changeDelta(int change) {
236       if (change != 0) {
237         setCachedValues(0, false, 0); // deltaUpToRoot is not valid anymore
238         return delta += change;
239       }
240       return delta;
241     }
242     protected void clearDelta() {
243       if (delta != 0) {
244         setCachedValues(0, false, 0); // deltaUpToRoot is not valid anymore
245         delta = 0;
246       }
247     }
248
249     @Override
250     public int setIntervalStart(int start) {
251       return myStart = start;
252     }
253
254     @Override
255     public int setIntervalEnd(int end) {
256       return myEnd = end;
257     }
258
259     @Override
260     public boolean isValid() {
261       return isValid;
262     }
263
264     @Override
265     public boolean setValid(boolean value) {
266       return isValid = value;
267     }
268
269     @Override
270     public int intervalStart() {
271       return myStart;
272     }
273
274     @Override
275     public int intervalEnd() {
276       return myEnd;
277     }
278
279     public IntervalTreeImpl<E> getTree() {
280       return myIntervalTree;
281     }
282
283     /**
284      *     packing/unpacking cachedDeltaUpToRoot field parts
285      *     Bits layout:
286      *     XXXXXXXXNMMMMMMMM where
287      *     XXXXXXXX - 31bit int containing cached delta up to root
288      *     N        - 1bit flag.  if set then all deltas up to root are null
289      *     MMMMMMMM - 32bit int containing this node modification count
290      */
291     private static AtomicFieldUpdater<IntervalNode, Long> cachedDeltaUpdater = AtomicFieldUpdater.forLongField(IntervalNode.class);
292
293     private void setCachedValues(int deltaUpToRoot, boolean allDeltaUpToRootAreNull, int modCount) {
294       cachedDeltaUpToRoot = packValues(deltaUpToRoot, allDeltaUpToRootAreNull, modCount);
295     }
296
297     private static long packValues(long deltaUpToRoot, boolean allDeltaUpToRootAreNull, int modCount) {
298       return deltaUpToRoot << 33 | (allDeltaUpToRootAreNull ? 0x100000000L : 0) | modCount;
299     }
300
301     private boolean tryToSetCachedValues(int deltaUpToRoot, boolean allDeltasUpAreNull, int treeModCount) {
302       if (myIntervalTree.modCount != treeModCount) return false;
303       long newValue = packValues(deltaUpToRoot, allDeltasUpAreNull, treeModCount);
304       long oldValue = cachedDeltaUpToRoot;
305       return cachedDeltaUpdater.compareAndSetLong(this, oldValue, newValue);
306     }
307
308     public void unpackCachedValuesTo(NodeCachedOffsets t) {
309       long value = cachedDeltaUpToRoot;
310       t.deltaUpToRoot = (int)(value >> 33);
311       t.modCount = (int)value;
312       t.allDeltasUpAreNull = ((value >> 32) & 1) != 0;
313     }
314
315     @NonNls
316     @Override
317     public String toString() {
318       return "Node: " + intervals;
319     }
320   }
321
322   static class NodeCachedOffsets {
323     private int modCount; // if it equals to the com.intellij.openapi.editor.impl.RedBlackTree.modCount then deltaUpToRoot can be used, otherwise it is expired
324     private int deltaUpToRoot; // sum of all deltas up to the root (including this node' delta). Has valid value only if modCount == IntervalTreeImpl.this.modCount
325     private boolean allDeltasUpAreNull;  // true if all deltas up the tree (including this node) are 0. Has valid value only if modCount == IntervalTreeImpl.this.modCount
326   }
327
328   private void assertUnderWriteLock() {
329     assert isAcquired(l.writeLock()) : l.writeLock();
330   }
331   private static boolean isAcquired(Lock l) {
332     String s = l.toString();
333     return s.contains("Locked by thread");
334   }
335
336   private void pushDeltaFromRoot(IntervalNode<T> node, NodeCachedOffsets cached) {
337     if (node != null) {
338       node.unpackCachedValuesTo(cached);
339       if (cached.allDeltasUpAreNull && node.isValid() && cached.modCount == modCount) return;
340       pushDeltaFromRoot(node.getParent(), cached);
341       pushDelta(node, cached);
342     }
343   }
344
345   @NotNull
346   protected abstract IntervalNode<T> createNewNode(@NotNull T key, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer);
347   protected abstract IntervalNode<T> lookupNode(@NotNull T key);
348   protected abstract void setNode(@NotNull T key, IntervalNode<T> node);
349
350   private int compareNodes(@NotNull IntervalNode<T> i1, int delta1, @NotNull IntervalNode<T> i2, int delta2, @NotNull List<IntervalNode<T>> invalid) {
351     if (!i2.hasAliveKey(false)) {
352       invalid.add(i2); //gced
353     }
354     int start1 = i1.intervalStart() + delta1;
355     int start2 = i2.intervalStart() + delta2;
356     if (start1 != start2) return start1 - start2;
357     return compareEqualStartIntervals(i1, i2);
358   }
359
360   protected IntervalNode<T> getRoot() {
361     return (IntervalNode<T>)root;
362   }
363
364   @Override
365   public boolean process(@NotNull Processor<? super T> processor) {
366     try {
367       l.readLock().lock();
368       checkMax(true);
369       return process(getRoot(), processor, modCount);
370     }
371     finally {
372       l.readLock().unlock();
373     }
374   }
375
376   private boolean process(final IntervalNode<T> root, final Processor<? super T> processor, final int modCountBefore) {
377     if (root == null) return true;
378
379     WalkingState.TreeGuide<IntervalNode<T>> guide = getGuide();
380     return WalkingState.processAll(root, guide, new Processor<IntervalNode<T>>() {
381       @Override
382       public boolean process(IntervalNode<T> node) {
383         if (!node.processAliveKeys(processor)) return false;
384         if (modCount != modCountBefore) throw new ConcurrentModificationException();
385         return true;
386       }
387     });
388   }
389
390   @Override
391   public boolean processOverlappingWith(int start, int end, @NotNull Processor<? super T> processor) {
392     try {
393       l.readLock().lock();
394       checkMax(true);
395       return processOverlappingWith(getRoot(), start, end, processor, modCount, 0);
396     }
397     finally {
398       l.readLock().unlock();
399     }
400   }
401
402   private boolean processOverlappingWith(IntervalNode<T> root,
403                                          int start,
404                                          int end,
405                                          Processor<? super T> processor,
406                                          int modCountBefore,
407                                          int deltaUpToRootExclusive) {
408     if (root == null) {
409       return true;
410     }
411     assert root.isValid();
412
413     int delta = deltaUpToRootExclusive + root.delta;
414     if (start > maxEndOf(root, deltaUpToRootExclusive)) {
415       return true; // right of the rightmost interval in the subtree
416     }
417
418     if (!processOverlappingWith(root.getLeft(), start, end, processor, modCountBefore, delta)) return false;
419     int myStartOffset = root.intervalStart() + delta;
420     int myEndOffset = root.intervalEnd() + delta;
421     boolean overlaps = Math.max(myStartOffset, start) <= Math.min(myEndOffset, end);
422     if (overlaps) {
423       if (!root.processAliveKeys(processor)) return false;
424       if (modCount != modCountBefore) throw new ConcurrentModificationException();
425     }
426
427     if (end < myStartOffset) {
428       return true; // left of the root, cant be in the right subtree
429     }
430
431     return processOverlappingWith(root.getRight(), start, end, processor, modCountBefore, delta);
432   }
433
434   public boolean processOverlappingWithOutside(int start, int end, @NotNull Processor<? super T> processor) {
435     try {
436       l.readLock().lock();
437       checkMax(true);
438       return processOverlappingWithOutside(getRoot(), start, end, processor, modCount, 0);
439     }
440     finally {
441       l.readLock().unlock();
442     }
443   }
444   private boolean processOverlappingWithOutside(IntervalNode<T> root,
445                                                 int start,
446                                                 int end,
447                                                 @NotNull Processor<? super T> processor,
448                                                 int modCountBefore,
449                                                 int deltaUpToRootExclusive) {
450     if (root == null) {
451       return true;
452     }
453     assert root.isValid();
454
455     int delta = deltaUpToRootExclusive + root.delta;
456     int rootMaxEnd = maxEndOf(root, deltaUpToRootExclusive);
457     int rootStartOffset = root.intervalStart() + delta;
458     int rootEndOffset = root.intervalEnd() + delta;
459
460     if (!processOverlappingWithOutside(root.getLeft(), start, end, processor, modCountBefore, delta)) return false;
461
462     boolean toProcess = rootStartOffset < start || rootEndOffset > end;
463     if (toProcess) {
464       if (!root.processAliveKeys(processor)) return false;
465       if (modCount != modCountBefore) throw new ConcurrentModificationException();
466     }
467
468     if (rootStartOffset >= start && rootMaxEnd <= end) return true; // cant intersect outside
469
470     return processOverlappingWithOutside(root.getRight(), start, end, processor, modCountBefore, delta);
471   }
472
473
474   @Override
475   public boolean processContaining(int offset, @NotNull Processor<? super T> processor) {
476     try {
477       l.readLock().lock();
478       checkMax(true);
479       return processContaining(getRoot(), offset, processor, modCount, 0);
480     }
481     finally {
482       l.readLock().unlock();
483     }
484   }
485   private boolean processContaining(IntervalNode<T> root,
486                                     int offset,
487                                     Processor<? super T> processor,
488                                     int modCountBefore,
489                                     int deltaUpToRootExclusive) {
490     if (root == null) {
491       return true;
492     }
493     assert root.isValid();
494     int delta = deltaUpToRootExclusive + root.delta;
495     if (offset > maxEndOf(root, deltaUpToRootExclusive)) {
496       return true; // right of the rightmost interval in the subtree
497     }
498
499     if (!processContaining(root.getLeft(), offset, processor, modCountBefore, delta)) return false;
500     int myStartOffset = root.intervalStart() + delta;
501     int myEndOffset = root.intervalEnd() + delta;
502     boolean overlaps = myStartOffset <= offset && offset < myEndOffset;
503
504     if (overlaps) {
505       if (!root.processAliveKeys(processor)) return false;
506       if (modCount != modCountBefore) throw new ConcurrentModificationException();
507     }
508
509     if (offset < myStartOffset) {
510       return true; // left of the root, cant be in the right subtree
511     }
512
513     return processContaining(root.getRight(), offset, processor, modCountBefore, delta);
514   }
515
516   @NotNull
517   DisposableIterator<T> overlappingIterator(final int startOffset, final int endOffset) {
518     ProperTextRange.assertProperRange(startOffset, endOffset, "");
519
520     l.readLock().lock();
521
522     try {
523       final IntervalNode<T> firstOverlap = findMinOverlappingWith(getRoot(), new TextRangeInterval(startOffset, endOffset), modCount, 0);
524       if (firstOverlap == null) {
525         l.readLock().unlock();
526         return DisposableIterator.EMPTY;
527       }
528       final int firstOverlapDelta = firstOverlap.computeDeltaUpToRoot();
529       final int firstOverlapStart = firstOverlap.intervalStart() + firstOverlapDelta;
530       final int modCountBefore = modCount;
531
532       return new DisposableIterator<T>() {
533         private IntervalNode<T> currentNode = firstOverlap;
534         private int deltaUpToRootExclusive = firstOverlapDelta-firstOverlap.delta;
535         private int indexInCurrentList = 0;
536         private T current;
537
538         @Override
539         public boolean hasNext() {
540           if (current != null) return true;
541           if (currentNode == null) return false;
542
543           if (modCount != modCountBefore) throw new ConcurrentModificationException();
544           while (indexInCurrentList != currentNode.intervals.size()) {
545             T t = currentNode.intervals.get(indexInCurrentList++).get();
546             if (t != null) {
547               current = t;
548               return true;
549             }
550           }
551           indexInCurrentList = 0;
552           while (true) {
553             currentNode = nextNode(currentNode);
554             if (currentNode == null) {
555               return false;
556             }
557             if (overlaps(currentNode, startOffset, endOffset, deltaUpToRootExclusive)) {
558               assert currentNode.intervalStart() + deltaUpToRootExclusive + currentNode.delta >= firstOverlapStart;
559               indexInCurrentList = 0;
560               while (indexInCurrentList != currentNode.intervals.size()) {
561                 T t = currentNode.intervals.get(indexInCurrentList++).get();
562                 if (t != null) {
563                   current = t;
564                   return true;
565                 }
566               }
567               indexInCurrentList = 0;
568             }
569           }
570         }
571
572         @Override
573         public T next() {
574           if (!hasNext()) throw new NoSuchElementException();
575           T t = current;
576           current = null;
577           return t;
578         }
579
580         @Override
581         public void remove() {
582           throw new IncorrectOperationException();
583         }
584
585         @Override
586         public void dispose() {
587           l.readLock().unlock();
588         }
589
590         // next node in in-order traversal
591         private IntervalNode<T> nextNode(@NotNull IntervalNode<T> root) {
592           assert root.isValid() : root;
593           int delta = deltaUpToRootExclusive + root.delta;
594           int myMaxEnd = maxEndOf(root, deltaUpToRootExclusive);
595           if (startOffset > myMaxEnd) return null; // tree changed
596
597           // try to go right down
598           IntervalNode<T> right = root.getRight();
599           if (right != null) {
600             int rightMaxEnd = maxEndOf(right, delta);
601             if (startOffset <= rightMaxEnd) {
602               int rightDelta = delta + right.delta;
603               while (right.getLeft() != null && startOffset <= maxEndOf(right.getLeft(), rightDelta)) {
604                 right = right.getLeft();
605                 rightDelta += right.delta;
606               }
607               deltaUpToRootExclusive = rightDelta - right.delta;
608               return right;
609             }
610           }
611
612           // go up
613           while (true) {
614             IntervalNode<T> parent = root.getParent();
615             if (parent == null) return null;
616             if (parent.intervalStart() + deltaUpToRootExclusive > endOffset) return null; // can't move right
617             deltaUpToRootExclusive -= parent.delta;
618
619             if (parent.getLeft() == root) {
620               return parent;
621             }
622
623             root = parent;
624           }
625         }
626       };
627     }
628     catch (RuntimeException e) {
629       l.readLock().unlock();
630       throw e;
631     }
632     catch (Error e) {
633       l.readLock().unlock();
634       throw e;
635     }
636   }
637
638   private boolean overlaps(IntervalNode<T> root, int startOffset, int endOffset, int deltaUpToRootExclusive) {
639     if (root == null) return false;
640     int delta = root.delta + deltaUpToRootExclusive;
641     int start = root.intervalStart() + delta;
642     int end = root.intervalEnd() + delta;
643     return Math.max(start, startOffset) <= Math.min(end, endOffset);
644   }
645
646   // finds previous in the in-order traversal
647   private IntervalNode<T> previous(@NotNull IntervalNode<T> node) {
648     IntervalNode<T> left = node.getLeft();
649     if (left != null) {
650       while (left.getRight() != null) {
651         left = left.getRight();
652       }
653       return left;
654     }
655     IntervalNode<T> parent = node.getParent();
656     while (parent != null) {
657       if (parent.getRight() == node) break;
658       node = parent;
659       parent = parent.getParent();
660     }
661     return parent;
662   }
663
664   protected IntervalNode<T> findOrInsert(@NotNull IntervalNode<T> node) {
665     assertUnderWriteLock();
666     node.color = Color.RED;
667     node.setParent(null);
668     node.setValid(true);
669     node.maxEnd = 0;
670     node.clearDelta();
671     node.setLeft(null);
672     node.setRight(null);
673
674     List<IntervalNode<T>> gced = new SmartList<IntervalNode<T>>();
675     NodeCachedOffsets cached = new NodeCachedOffsets();
676     if (root == null) {
677       root = node;
678     }
679     else {
680       IntervalNode<T> current = getRoot();
681       while (true) {
682         pushDelta(current, cached);
683         int compResult = compareNodes(node, 0, current, 0, gced);
684         if (compResult == 0) {
685           return current;
686         }
687         if (compResult < 0) {
688           if (current.getLeft() == null) {
689             current.setLeft(node);
690             break;
691           }
692           current = current.getLeft();
693         }
694         else /*if (compResult > 0)*/ {
695           if (current.getRight() == null) {
696             current.setRight(node);
697             break;
698           }
699           current = current.getRight();
700         }
701       }
702       node.setParent(current);
703     }
704     node.setCachedValues(0, true, modCount);
705     correctMaxUp(node, cached);
706     onInsertNode();
707     keySize += node.intervals.size();
708     insertCase1(node);
709     verifyProperties();
710
711     deleteNodes(gced);
712     return node;
713   }
714
715   private void deleteNodes(@NotNull List<IntervalNode<T>> collectedAway) {
716     if (collectedAway.isEmpty()) return;
717     try {
718       l.writeLock().lock();
719       for (IntervalNode<T> node : collectedAway) {
720         removeNode(node);
721       }
722     }
723     finally {
724       l.writeLock().unlock();
725     }
726   }
727
728   public IntervalTreeImpl.IntervalNode<T> addInterval(@NotNull T interval, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
729     try {
730       l.writeLock().lock();
731       checkMax(true);
732       processReferenceQueue();
733       modCount++;
734       IntervalNode<T> newNode = createNewNode(interval, start, end, greedyToLeft, greedyToRight, layer);
735       IntervalNode<T> insertedNode = findOrInsert(newNode);
736       if (insertedNode == newNode) {
737         setNode(interval, insertedNode);
738       }
739       else {
740         // merged
741         insertedNode.addInterval(interval);
742       }
743       checkMax(true);
744       checkBelongsToTheTree(interval, true);
745       return insertedNode;
746     }
747     finally {
748       l.writeLock().unlock();
749     }
750   }
751
752   // returns true if all markers are valid
753   public boolean checkMax(boolean assertInvalid) {
754     if (!VERIFY) return false;
755
756     try {
757       l.readLock().lock();
758
759       Ref<Boolean> allValid = new Ref<Boolean>(true);
760       int[] keyCounter = new int[1];
761       int[] nodeCounter = new int[1];
762       TLongHashSet ids = new TLongHashSet(keySize);
763       checkMax(getRoot(), 0, assertInvalid, allValid, keyCounter, nodeCounter, ids, true);
764       if (assertInvalid) {
765         assert nodeSize() == nodeCounter[0] : "node size: "+ nodeSize() +"; actual: "+nodeCounter[0];
766         assert keySize == keyCounter[0] : "key size: "+ keySize +"; actual: "+keyCounter[0];
767         assert keySize >= nodeSize() : keySize + "; "+nodeSize();
768       }
769       return allValid.get();
770     }
771     finally {
772       l.readLock().unlock();
773     }
774   }
775
776   // returns real (minStart, maxStart, maxEnd)
777   private Trinity<Integer,Integer,Integer> checkMax(IntervalNode<T> root,
778                                                     int deltaUpToRootExclusive,
779                                                     boolean assertInvalid,
780                                                     Ref<Boolean> allValid,
781                                                     int[] keyCounter,
782                                                     int[] nodeCounter,
783                                                     TLongHashSet ids, boolean allDeltasUpAreNull) {
784     if (root == null) return Trinity.create(Integer.MAX_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE);
785     NodeCachedOffsets cached = new NodeCachedOffsets();
786     root.unpackCachedValuesTo(cached);
787     if (cached.modCount == modCount) {
788       assert cached.allDeltasUpAreNull == (root.delta == 0 && allDeltasUpAreNull);
789       assert cached.deltaUpToRoot == root.delta + deltaUpToRootExclusive;
790     }
791     T liveInterval = null;
792     for (int i = root.intervals.size() - 1; i >= 0; i--) {
793       T t = root.intervals.get(i).get();
794       if (t == null) continue;
795       liveInterval = t;
796       checkBelongsToTheTree(t, false);
797       boolean added = ids.add(((RangeMarkerImpl)t).getId());
798       assert added : t;
799     }
800     if (assertInvalid && liveInterval != null) {
801       checkBelongsToTheTree(liveInterval, true);
802     }
803
804     keyCounter[0]+= root.intervals.size();
805     nodeCounter[0]++;
806     int delta = deltaUpToRootExclusive + (root.isValid() ? root.delta : 0);
807     Trinity<Integer, Integer, Integer> l = checkMax(root.getLeft(), delta, assertInvalid, allValid, keyCounter, nodeCounter, ids, root.delta == 0 && allDeltasUpAreNull);
808     int minLeftStart = l.first;
809     int maxLeftStart = l.second;
810     int maxLeftEnd = l.third;
811     Trinity<Integer, Integer, Integer> r = checkMax(root.getRight(), delta, assertInvalid, allValid, keyCounter, nodeCounter, ids, root.delta == 0 && allDeltasUpAreNull);
812     int maxRightEnd = r.third;
813     int minRightStart = r.first;
814     int maxRightStart = r.second;
815     if (!root.isValid()) {
816       allValid.set(false);
817       if (assertInvalid) assert false : root;
818       return Trinity.create(Math.min(minLeftStart, minRightStart), Math.max(maxLeftStart, maxRightStart), Math.max(maxRightEnd, maxLeftEnd));
819     }
820     IntervalNode<T> parent = root.getParent();
821     if (parent != null && assertInvalid && root.hasAliveKey(false)) {
822       int c = compareNodes(root, delta, parent, delta - root.delta, new SmartList<IntervalNode<T>>());
823       assert c != 0;
824       assert c < 0 && parent.getLeft() == root || c > 0 && parent.getRight() == root;
825     }
826     assert delta + root.maxEnd == Math.max(maxLeftEnd, Math.max(maxRightEnd, delta + root.intervalEnd()));
827     int myStartOffset = delta + root.intervalStart();
828     assert maxLeftStart <= myStartOffset;
829     assert minRightStart >= myStartOffset;
830     assert myStartOffset >= 0;
831     assert minLeftStart == Integer.MAX_VALUE || minLeftStart <= myStartOffset;
832     assert maxRightStart == Integer.MIN_VALUE || maxRightStart >= myStartOffset;
833     int minStart = Math.min(minLeftStart, myStartOffset);
834     int maxStart = Math.max(myStartOffset, Math.max(maxLeftStart, maxRightStart));
835     assert minStart <= maxStart;
836     return Trinity.create(minStart, maxStart, root.maxEnd + delta);
837   }
838
839   @Override
840   protected Node<T> maximumNode(Node<T> n) {
841     IntervalNode<T> root = (IntervalNode<T>)n;
842     NodeCachedOffsets cached = new NodeCachedOffsets();
843     pushDelta(root.getParent(), cached);
844     pushDelta(root, cached);
845     while (root.getRight() != null) {
846       root = root.getRight();
847       pushDelta(root, cached);
848     }
849     return root;
850   }
851
852   protected void checkBelongsToTheTree(T interval, boolean assertInvalid) {
853     IntervalNode<T> root = lookupNode(interval);
854     if (root == null) return;
855     assert root.getTree() == this : root.getTree() +"; this: "+this;
856     if (!VERIFY) return;
857
858     if (assertInvalid) {
859       assert !root.intervals.isEmpty();
860       boolean contains = false;
861       for (int i = root.intervals.size() - 1; i >= 0; i--) {
862         T key = root.intervals.get(i).get();
863         if (key == null) continue;
864         contains |= key == interval;
865         IntervalNode<T> node = lookupNode(key);
866         assert node == root : node;
867         assert node.getTree() == this : node;
868       }
869
870       assert contains : root.intervals + "; " + interval;
871     }
872
873     IntervalNode<T> e = root;
874     while (e.getParent() != null) e = e.getParent();
875     assert e == getRoot(); // assert the node belongs to our tree
876   }
877
878   @Override
879   public boolean removeInterval(@NotNull T interval) {
880     if (!interval.isValid()) return false;
881     try {
882       l.writeLock().lock();
883       modCount++;
884       if (!interval.isValid()) return false;
885       checkBelongsToTheTree(interval, true);
886       checkMax(true);
887       processReferenceQueue();
888
889       IntervalNode<T> node = lookupNode(interval);
890       if (node == null) return false;
891
892       reportInvalidation(interval, "Explicit Dispose");
893
894       node.removeInterval(interval);
895       setNode(interval, null);
896
897       checkMax(true);
898       return true;
899     }
900     finally {
901       l.writeLock().unlock();
902     }
903   }
904
905   // run under write lock
906   void removeNode(@NotNull IntervalNode<T> node) {
907     deleteNode(node);
908     IntervalNode<T> parent = node.getParent();
909     correctMaxUp(parent, new NodeCachedOffsets());
910   }
911
912   @Override
913   protected void deleteNode(@NotNull Node<T> n) {
914     assertUnderWriteLock();
915     IntervalNode<T> node = (IntervalNode<T>)n;
916     NodeCachedOffsets cached = new NodeCachedOffsets();
917     pushDeltaFromRoot(node, cached);
918     assertAllDeltasAreNull(node, cached);
919     super.deleteNode(n);
920
921     keySize -= node.intervals.size();
922     assert keySize >= 0 : keySize;
923   }
924
925   @Override
926   public int size() {
927     return keySize;
928   }
929
930   // returns true if all deltas involved are still 0
931   protected boolean pushDelta(IntervalNode<T> root, NodeCachedOffsets cached) {
932     if (root == null || !root.isValid()) return true;
933     IntervalNode<T> parent = root.getParent();
934     assertAllDeltasAreNull(parent, cached);
935     int delta = root.delta;
936     root.setCachedValues(0, true, 0);
937     if (delta != 0) {
938       root.setIntervalStart(root.intervalStart() + delta);
939       root.setIntervalEnd(root.intervalEnd() + delta);
940       root.maxEnd += delta;
941       root.delta = 0;
942       //noinspection NonShortCircuitBooleanExpression
943       return
944       incDelta(root.getLeft(), delta) &
945       incDelta(root.getRight(), delta);
946     }
947     root.setCachedValues(0, true, modCount);
948     return true;
949   }
950
951   // returns true if all deltas involved are still 0
952   private boolean incDelta(IntervalNode<T> root, int delta) {
953     if (root == null) return true;
954     if (root.isValid()) {
955       int newDelta = root.changeDelta(delta);
956       return newDelta == 0;
957     }
958     else {
959       //noinspection NonShortCircuitBooleanExpression
960       return
961       incDelta(root.getLeft(), delta) &
962       incDelta(root.getRight(), delta);
963     }
964   }
965
966   @Override
967   protected IntervalNode<T> swapWithMaxPred(Node<T> root, Node<T> maxPred) {
968     checkMax(false);
969     IntervalNode<T> a = (IntervalNode<T>)root;
970     IntervalNode<T> d = (IntervalNode<T>)maxPred;
971     Color acolor = a.color;
972     Color dcolor = d.color;
973     assert !a.isValid() || a.delta == 0 : a.delta;
974     for (IntervalNode<T> n = a.getLeft(); n != null; n = n.getRight()) {
975       assert !n.isValid() || n.delta == 0 : n.delta;
976     }
977     swapNodes(a, d);
978
979     // set range of the key to be deleted so it wont disrupt maxes
980     a.setValid(false);
981     //a.key.setIntervalStart(d.key.intervalStart());
982     //a.key.setIntervalEnd(d.key.intervalEnd());
983
984     //correctMaxUp(a);
985     a.color = dcolor;
986     d.color = acolor;
987     correctMaxUp(a, new NodeCachedOffsets());
988
989     checkMax(false);
990     assert a.delta == 0 : a.delta;
991     assert d.delta == 0 : d.delta;
992     return a;
993   }
994   private void swapNodes(IntervalNode<T> n1, IntervalNode<T> n2) {
995     IntervalNode<T> l1 = n1.getLeft();
996     IntervalNode<T> r1 = n1.getRight();
997     IntervalNode<T> p1 = n1.getParent();
998     IntervalNode<T> l2 = n2.getLeft();
999     IntervalNode<T> r2 = n2.getRight();
1000     IntervalNode<T> p2 = n2.getParent();
1001
1002     if (p1 != null) {
1003       if (p1.getLeft() == n1) p1.setLeft(n2); else p1.setRight(n2);
1004     }
1005     else {
1006       root = n2;
1007     }
1008     if (p2 != null) {
1009       if (p2.getLeft() == n2) p2.setLeft(p2 == n1 ? l2 : n1); else p2.setRight(p2 == n1 ? r2 : n1);
1010     }
1011     else {
1012       root = n1;
1013     }
1014     n1.setParent(p2 == n1 ? n2 : p2);
1015     n2.setParent(p1);
1016
1017     n1.setLeft(l2);
1018     n2.setLeft(l1 == n2 ? n1 : l1);
1019     if (l1 != null) l1.setParent(n2 == l1 ? p1 : n2);
1020     if (r1 != null) r1.setParent(n2);
1021     n1.setRight(r2);
1022     n2.setRight(r1);
1023     if (l2 != null) l2.setParent(n1);
1024     if (r2 != null) r2.setParent(n1);
1025   }
1026
1027   // returns real max endOffset of all intervals below
1028   private int maxEndOf(IntervalNode<T> node, int deltaUpToRootExclusive) {
1029     if (node == null) {
1030       return 0;
1031     }
1032     if (node.isValid()) {
1033       return node.maxEnd + node.delta + deltaUpToRootExclusive;
1034     }
1035     // since node is invalid, ignore node.delta
1036     return Math.max(maxEndOf(node.getLeft(), deltaUpToRootExclusive), maxEndOf(node.getRight(), deltaUpToRootExclusive));
1037   }
1038
1039   // max of n.left's maxend, n.right's maxend and its own interval endOffset
1040   protected void correctMax(@NotNull IntervalNode<T> node, int deltaUpToRoot) {
1041     if (!node.isValid()) return;
1042     int realMax = Math.max(Math.max(maxEndOf(node.getLeft(), deltaUpToRoot), maxEndOf(node.getRight(), deltaUpToRoot)),
1043                            deltaUpToRoot + node.intervalEnd());
1044     node.maxEnd = realMax - deltaUpToRoot;
1045   }
1046
1047   private void correctMaxUp(IntervalNode<T> node, NodeCachedOffsets cached) {
1048     int delta = node == null ? 0 : node.computeDeltaUpToRoot(cached);
1049     assert delta == 0 : delta;
1050     while (node != null) {
1051       if (node.isValid()) {
1052         int d = node.delta;
1053         correctMax(node, delta);
1054         delta -= d;
1055       }
1056       node = node.getParent();
1057     }
1058     assert delta == 0 : delta;
1059   }
1060
1061   @Override
1062   protected void rotateRight(Node<T> n) {
1063     checkMax(false);
1064     IntervalNode<T> node1 = (IntervalNode<T>)n;
1065     IntervalNode<T> node2 = node1.getLeft();
1066     IntervalNode<T> node3 = node1.getRight();
1067
1068     NodeCachedOffsets cached = new NodeCachedOffsets();
1069     IntervalNode<T> parent = node1.getParent();
1070     int deltaUp = parent == null ? 0 : parent.computeDeltaUpToRoot(cached);
1071     pushDelta(node1, cached);
1072     pushDelta(node2, cached);
1073     pushDelta(node3, cached);
1074
1075     super.rotateRight(node1);
1076
1077     if (node3 != null) {
1078       correctMax(node3, deltaUp);
1079     }
1080     correctMax(node1, deltaUp);
1081     correctMax(node2, deltaUp);
1082     assertAllDeltasAreNull(node1, cached);
1083     assertAllDeltasAreNull(node2, cached);
1084     assertAllDeltasAreNull(node3, cached);
1085     checkMax(false);
1086   }
1087
1088   @Override
1089   protected void rotateLeft(Node<T> n) {
1090     checkMax(false);
1091     IntervalNode<T> node1 = (IntervalNode<T>)n;
1092     IntervalNode<T> node2 = node1.getLeft();
1093     IntervalNode<T> node3 = node1.getRight();
1094
1095     NodeCachedOffsets cached = new NodeCachedOffsets();
1096     IntervalNode<T> parent = node1.getParent();
1097     int deltaUp = parent == null ? 0 : parent.computeDeltaUpToRoot(cached);
1098     pushDelta(node1, cached);
1099     pushDelta(node2, cached);
1100     pushDelta(node3, cached);
1101     checkMax(false);
1102     super.rotateLeft(node1);
1103
1104     if (node2 != null) {
1105       correctMax(node2, deltaUp);
1106     }
1107     correctMax(node1, deltaUp);
1108     correctMax(node3, deltaUp);
1109     assertAllDeltasAreNull(node1, cached);
1110     assertAllDeltasAreNull(node2, cached);
1111     assertAllDeltasAreNull(node3, cached);
1112
1113     checkMax(false);
1114   }
1115
1116   @Override
1117   protected void replaceNode(@NotNull Node<T> node, Node<T> child) {
1118     IntervalNode<T> myNode = (IntervalNode<T>)node;
1119     NodeCachedOffsets cached = new NodeCachedOffsets();
1120     pushDelta(myNode, cached);
1121     pushDelta((IntervalNode<T>)child, cached);
1122
1123     super.replaceNode(node, child);
1124     if (child != null && myNode.isValid()) {
1125       ((IntervalNode<T>)child).changeDelta(myNode.delta);
1126       //todo correct max up to root??
1127     }
1128   }
1129
1130   private void assertAllDeltasAreNull(IntervalNode<T> node, NodeCachedOffsets cached) {
1131     if (node == null) return;
1132     if (!node.isValid()) return;
1133     assert node.delta == 0;
1134     node.unpackCachedValuesTo(cached);
1135     assert cached.modCount != modCount || cached.allDeltasUpAreNull;
1136   }
1137
1138   private IntervalNode<T> findMinOverlappingWith(IntervalNode<T> root, Interval interval, int modCountBefore, int deltaUpToRootExclusive) {
1139     if (root == null) {
1140       return null;
1141     }
1142     assert root.isValid();
1143
1144     int delta = deltaUpToRootExclusive + root.delta;
1145     if (interval.intervalStart() > maxEndOf(root, deltaUpToRootExclusive)) {
1146       return null; // right of the rightmost interval in the subtree
1147     }
1148
1149     IntervalNode<T> inLeft = findMinOverlappingWith(root.getLeft(), interval, modCountBefore, delta);
1150     if (inLeft != null) return inLeft;
1151     int myStartOffset = root.intervalStart() + delta;
1152     int myEndOffset = root.intervalEnd() + delta;
1153     boolean overlaps = Math.max(myStartOffset, interval.intervalStart()) <= Math.min(myEndOffset, interval.intervalEnd());
1154     if (overlaps) return root;
1155     if (modCount != modCountBefore) throw new ConcurrentModificationException();
1156
1157     if (interval.intervalEnd() < myStartOffset) {
1158       return null; // left of the root, cant be in the right subtree
1159     }
1160
1161     return findMinOverlappingWith(root.getRight(), interval, modCountBefore, delta);
1162   }
1163
1164   public void changeData(T interval, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
1165     try {
1166       l.writeLock().lock();
1167
1168       IntervalNode<T> node = lookupNode(interval);
1169       if (node == null) return;
1170       int before = size();
1171       boolean nodeRemoved = node.removeInterval(interval);
1172       assert nodeRemoved || !node.intervals.isEmpty();
1173
1174       IntervalNode<T> insertedNode = addInterval(interval, start, end, greedyToLeft, greedyToRight, layer);
1175       assert node != insertedNode;
1176
1177       int after = size();
1178       // can be gced
1179       assert before >= after : before +";" + after;
1180       checkBelongsToTheTree(interval, true);
1181       checkMax(true);
1182     }
1183     finally {
1184       l.writeLock().unlock();
1185     }
1186   }
1187
1188
1189   // called under write lock
1190   private void processReferenceQueue() {
1191     int dead = 0;
1192     while (myReferenceQueue.poll() != null) {
1193       dead++;
1194     }
1195
1196     deadReferenceCount += dead;
1197     if (deadReferenceCount > Math.max(1, size() / 3)) {
1198       purgeDeadNodes();
1199       deadReferenceCount = 0;
1200     }
1201   }
1202
1203   private void purgeDeadNodes() {
1204     assertUnderWriteLock();
1205     List<IntervalNode<T>> gced = new SmartList<IntervalNode<T>>();
1206     collectGced(getRoot(), gced);
1207     deleteNodes(gced);
1208     checkMax(true);
1209   }
1210
1211   @Override
1212   public void clear() {
1213     process(new Processor<T>() {
1214       @Override
1215       public boolean process(T t) {
1216         reportInvalidation(t, "Clear all");
1217         return true;
1218       }
1219     });
1220     l.writeLock().lock();
1221     try {
1222       super.clear();
1223       keySize = 0;
1224     }
1225     finally {
1226       l.writeLock().unlock();
1227     }
1228   }
1229
1230   private void collectGced(IntervalNode<T> root, List<IntervalNode<T>> gced) {
1231     if (root == null) return;
1232     if (!root.hasAliveKey(true)) gced.add(root);
1233     collectGced(root.getLeft(), gced);
1234     collectGced(root.getRight(), gced);
1235   }
1236
1237
1238   private void printSorted() { printSorted(getRoot());}
1239   private void printSorted(IntervalNode<T> root) {
1240     if (root == null) return;
1241     printSorted(root.getLeft());
1242     System.out.println(root);
1243     printSorted(root.getRight());
1244   }
1245
1246   void reportInvalidation(T markerEx, @NonNls Object reason) {
1247   }
1248
1249   private static class IntervalTreeGuide<T extends MutableInterval> implements WalkingState.TreeGuide<IntervalNode<T>> {
1250     @Override
1251     public IntervalNode<T> getNextSibling(@NotNull IntervalNode<T> element) {
1252       IntervalNode<T> parent = element.getParent();
1253       if (parent == null) return null;
1254       return parent.getLeft() == element ? parent.getRight() : null;
1255     }
1256
1257     @Override
1258     public IntervalNode<T> getPrevSibling(@NotNull IntervalNode<T> element) {
1259       IntervalNode<T> parent = element.getParent();
1260       if (parent == null) return null;
1261       return parent.getRight() == element ? parent.getLeft() : null;
1262     }
1263
1264     @Override
1265     public IntervalNode<T> getFirstChild(@NotNull IntervalNode<T> element) {
1266       IntervalNode<T> left = element.getLeft();
1267       return left == null ? element.getRight() : left;
1268     }
1269
1270     @Override
1271     public IntervalNode<T> getParent(@NotNull IntervalNode<T> element) {
1272       return element.getParent();
1273     }
1274   }
1275
1276   private static final IntervalTreeGuide INTERVAL_TREE_GUIDE_INSTANCE = new IntervalTreeGuide();
1277   private static <T extends MutableInterval> WalkingState.TreeGuide<IntervalNode<T>> getGuide() {
1278     //noinspection unchecked
1279     return (WalkingState.TreeGuide)INTERVAL_TREE_GUIDE_INSTANCE;
1280   }
1281
1282
1283   public int maxHeight() {
1284     return maxHeight(root);
1285   }
1286
1287   private int maxHeight(Node<T> root) {
1288     return root == null ? 0 : 1 + Math.max(maxHeight(root.left), maxHeight(root.right));
1289   }
1290 }