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