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