platform/core-impl/src/com/intellij/openapi/editor/impl/IntervalTreeImpl.java

/*
 * Copyright 2000-2014 JetBrains s.r.o.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.intellij.openapi.editor.impl;

import com.intellij.openapi.editor.ex.DisposableIterator;
import com.intellij.openapi.util.Getter;
import com.intellij.openapi.util.Ref;
import com.intellij.openapi.util.TextRange;
import com.intellij.util.IncorrectOperationException;
import com.intellij.util.Processor;
import com.intellij.util.SmartList;
import com.intellij.util.WalkingState;
import com.intellij.util.concurrency.AtomicFieldUpdater;
import gnu.trove.TLongHashSet;
import org.jetbrains.annotations.NonNls;
import org.jetbrains.annotations.NotNull;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.ConcurrentModificationException;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * User: cdr
 */
public abstract class IntervalTreeImpl<T extends MutableInterval> extends RedBlackTree<T> implements IntervalTree<T> {
  private int keySize; // number of all intervals, counting all duplicates, some of them maybe gced
  protected final ReadWriteLock l = new ReentrantReadWriteLock();

  protected abstract int compareEqualStartIntervals(@NotNull IntervalNode<T> i1, @NotNull IntervalNode<T> i2);
  private final ReferenceQueue<T> myReferenceQueue = new ReferenceQueue<T>();
  private int deadReferenceCount;

  protected static class IntervalNode<E extends MutableInterval> extends RedBlackTree.Node<E> implements MutableInterval {
    private volatile int myStart;
    private volatile int myEnd;
    private static final int ATTACHED_TO_TREE_FLAG = COLOR_FLAG+1; // true if the node is inserted to the tree
    protected final List<Getter<E>> intervals;
    protected int maxEnd; // max of all intervalEnd()s among all children.
    protected int delta;  // delta of startOffset. getStartOffset() = myStartOffset + Sum of deltas up to root

    private volatile long cachedDeltaUpToRoot; // field (packed to long for atomicity) containing deltaUpToRoot, node modCount and allDeltasUpAreNull flag
    // fields are packed as following
    //  private int modCount; // if it equals to the com.intellij.openapi.editor.impl.RedBlackTree.modCount then deltaUpToRoot can be used, otherwise it is expired
    //  private int deltaUpToRoot; // sum of all deltas up to the root (including this node' delta). Has valid value only if modCount == IntervalTreeImpl.this.modCount
    //  private boolean allDeltasUpAreNull;  // true if all deltas up the tree (including this node) are 0. Has valid value only if modCount == IntervalTreeImpl.this.modCount

    private final IntervalTreeImpl<E> myIntervalTree;

    public IntervalNode(@NotNull IntervalTreeImpl<E> intervalTree, @NotNull E key, int start, int end) {
      // maxEnd == 0 so to not disrupt existing maxes
      myIntervalTree = intervalTree;
      myStart = start;
      myEnd = end;
      intervals = new SmartList<Getter<E>>(createGetter(key));
      setValid(true);
    }

    @Override
    public IntervalNode<E> getLeft() {
      return (IntervalNode<E>)left;
    }

    @Override
    public IntervalNode<E> getRight() {
      return (IntervalNode<E>)right;
    }

    @Override
    public IntervalNode<E> getParent() {
      return (IntervalNode<E>)parent;
    }

    @Override
    public boolean processAliveKeys(@NotNull Processor<? super E> processor) {
      //noinspection ForLoopReplaceableByForEach
      for (int i = 0; i < intervals.size(); i++) {
        Getter<E> interval = intervals.get(i);
        E key = interval.get();
        if (key != null && !processor.process(key)) return false;
      }
      return true;
    }

    @Override
    public boolean hasAliveKey(boolean purgeDead) {
      boolean hasAliveInterval = false;
      for (int i = intervals.size() - 1; i >= 0; i--) {
        Getter<E> interval = intervals.get(i);
        if (interval.get() != null) {
          hasAliveInterval = true;
          if (purgeDead) {
            continue;
          }
          else {
            break;
          }
        }
        if (purgeDead) {
          myIntervalTree.assertUnderWriteLock();
          removeIntervalInternal(i);
        }
      }
      return hasAliveInterval;
    }

    // removes interval and the node, if node became empty
    // returns true if node was removed
    private boolean removeInterval(@NotNull E key) {
      myIntervalTree.checkBelongsToTheTree(key, true);
      myIntervalTree.assertUnderWriteLock();
      for (int i = intervals.size() - 1; i >= 0; i--) {
        Getter<E> interval = intervals.get(i);
        E t = interval.get();
        if (t == key) {
          removeIntervalInternal(i);
          if (intervals.isEmpty()) {
            myIntervalTree.removeNode(this);
            return true;
          }
          return false;
        }
      }
      assert false: "interval not found: "+key +"; "+ intervals+"; isValid="+key.isValid();
      return false;
    }
    private boolean isAttachedToTree() {
      return isFlagSet(ATTACHED_TO_TREE_FLAG);
    }
    private void setAttachedToTree(boolean attached) {
      setFlag(ATTACHED_TO_TREE_FLAG, attached);
    }

    public void removeIntervalInternal(int i) {
      intervals.remove(i);
      if (isAttachedToTree()) {   // for detached node, do not update tree node count
        assert myIntervalTree.keySize > 0 : myIntervalTree.keySize;
        myIntervalTree.keySize--;
      }
    }

    public void addInterval(@NotNull E interval) {
      myIntervalTree.assertUnderWriteLock();
      intervals.add(createGetter(interval));
      if (isAttachedToTree()) { // for detached node, do not update tree node count
        myIntervalTree.keySize++;
        myIntervalTree.setNode(interval, this);
      }
    }

    protected Getter<E> createGetter(@NotNull E interval) {
      return new WeakReferencedGetter<E>(interval, myIntervalTree.myReferenceQueue);
    }

    private static class WeakReferencedGetter<T> extends WeakReference<T> implements Getter<T> {
      public WeakReferencedGetter(T referent, ReferenceQueue<? super T> q) {
        super(referent, q);
      }

      @NonNls
      @Override
      public String toString() {
        return "Ref: " + get();
      }
    }

    protected int computeDeltaUpToRoot() {
      restart:
      while (true) { // have to restart on failure to update cached offsets in case of concurrent modification
        if (!isValid()) return 0;
        int treeModCount = myIntervalTree.modCount;
        long packedOffsets = cachedDeltaUpToRoot;
        if (modCount(packedOffsets) == treeModCount) {
          return deltaUpToRoot(packedOffsets);
        }
        try {
          myIntervalTree.l.readLock().lock();

          IntervalNode<E> node = this;
          IntervalNode<E> treeRoot = myIntervalTree.getRoot();
          if (treeRoot == null) return delta; // someone modified the tree in the meantime
          int deltaUp = 0;
          boolean allDeltasAreNull = true;
          int height = 0;
          long path = 0; // path to this node from the root; 0 bit means we choose left subtree, 1 bit means we choose right subtree
          while (node != treeRoot) {
            long nodePackedOffsets = node.cachedDeltaUpToRoot;
            if (node.isValid() && modCount(nodePackedOffsets) == treeModCount) {
              deltaUp = deltaUpToRoot(nodePackedOffsets) - node.delta;
              allDeltasAreNull = allDeltasUpAreNull(nodePackedOffsets);
              break;
            }
            IntervalNode<E> parent = node.getParent();
            if (parent == null) {
              return deltaUp;  // can happen when remove node and explicitly set valid to true (e.g. in RangeMarkerTree)
            }
            path = (path << 1) |  (parent.getLeft() == node ? 0 : 1);
            node = parent;
            height++;
          }
          // path to this node fits to long
          assert height < 63 : height;

          // cache deltas in every node from the root down this
          while (true) {
            if (node.isValid()) {
              int nodeDelta = node.delta;
              deltaUp += nodeDelta;
              allDeltasAreNull &= nodeDelta == 0;
              if (!node.tryToSetCachedValues(deltaUp, allDeltasAreNull, treeModCount)) {
                continue restart;
              }
            }

            if (node == this) break;
            node = (path & 1) == 0 ? node.getLeft() : node.getRight();
            path >>= 1;
            if (node == null) return deltaUp; // can only happen in case of concurrently modification
          }

          assert deltaUp == 0 || !allDeltasAreNull;
          return deltaUp;
        }
        finally {
          myIntervalTree.l.readLock().unlock();
        }
      }
    }

    protected int changeDelta(int change) {
      if (change != 0) {
        setCachedValues(0, false, 0); // deltaUpToRoot is not valid anymore
        return delta += change;
      }
      return delta;
    }
    protected void clearDelta() {
      if (delta != 0) {
        setCachedValues(0, false, 0); // deltaUpToRoot is not valid anymore
        delta = 0;
      }
    }

    @Override
    public int setIntervalStart(int start) {
      return myStart = start;
    }

    @Override
    public int setIntervalEnd(int end) {
      return myEnd = end;
    }

    protected static final int VALID_FLAG = ATTACHED_TO_TREE_FLAG + 1;
    @Override
    public boolean isValid() {
      return isFlagSet(VALID_FLAG);
    }

    @Override
    public boolean setValid(boolean value) {
      setFlag(VALID_FLAG, value);
      return value;
    }

    @Override
    public int intervalStart() {
      return myStart;
    }

    @Override
    public int intervalEnd() {
      return myEnd;
    }

    public IntervalTreeImpl<E> getTree() {
      return myIntervalTree;
    }

    /**
     * packing/unpacking cachedDeltaUpToRoot field parts
     * Bits layout:
     * XXXXXXXXNMMMMMMMM where
     * XXXXXXXX - 31bit int containing cached delta up to root
     * N        - 1bit flag.  if set then all deltas up to root are null
     * MMMMMMMM - 32bit int containing this node modification count
     */
    private static final AtomicFieldUpdater<IntervalNode, Long> cachedDeltaUpdater = AtomicFieldUpdater.forLongFieldIn(IntervalNode.class);

    private void setCachedValues(int deltaUpToRoot, boolean allDeltaUpToRootAreNull, int modCount) {
      cachedDeltaUpToRoot = packValues(deltaUpToRoot, allDeltaUpToRootAreNull, modCount);
    }

    private static long packValues(long deltaUpToRoot, boolean allDeltaUpToRootAreNull, int modCount) {
      return deltaUpToRoot << 33 | (allDeltaUpToRootAreNull ? 0x100000000L : 0) | modCount;
    }

    private boolean tryToSetCachedValues(int deltaUpToRoot, boolean allDeltasUpAreNull, int treeModCount) {
      if (myIntervalTree.modCount != treeModCount) return false;
      long newValue = packValues(deltaUpToRoot, allDeltasUpAreNull, treeModCount);
      long oldValue = cachedDeltaUpToRoot;
      return cachedDeltaUpdater.compareAndSetLong(this, oldValue, newValue);
    }

    private static boolean allDeltasUpAreNull(long packedOffsets) {
      return ((packedOffsets >> 32) & 1) != 0;
    }
    private static int modCount(long packedOffsets) {
      return (int)packedOffsets;
    }
    private static int deltaUpToRoot(long packedOffsets) {
      return (int)(packedOffsets >> 33);
    }

    // finds previous in the in-order traversal
    IntervalNode<E> previous() {
      IntervalNode<E> left = getLeft();
      if (left != null) {
        while (left.getRight() != null) {
          left = left.getRight();
        }
        return left;
      }
      IntervalNode<E> parent = getParent();
      while (parent != null) {
        if (parent.getRight() == this) break;
        parent = parent.getParent();
      }
      return parent;
    }

    // finds next node in the in-order traversal
    IntervalNode<E> next() {
      IntervalNode<E> right = getRight();
      if (right != null) {
        while (right.getLeft() != null) {
          right = right.getLeft();
        }
        return right;
      }
      IntervalNode<E> parent = getParent();
      while (parent != null) {
        if (parent.getLeft() == this) break;
        parent = parent.getParent();
      }
      return parent;
    }

    @NonNls
    @Override
    public String toString() {
      return "Node: " + intervals;
    }
  }

  private void assertUnderWriteLock() {
    assert isAcquired(l.writeLock()) : l.writeLock();
  }
  private static boolean isAcquired(Lock l) {
    String s = l.toString();
    return s.contains("Locked by thread");
  }

  private void pushDeltaFromRoot(IntervalNode<T> node) {
    if (node != null) {
      long packedOffsets = node.cachedDeltaUpToRoot;
      if (IntervalNode.allDeltasUpAreNull(packedOffsets) && node.isValid() && IntervalNode.modCount(packedOffsets) == modCount) return;
      pushDeltaFromRoot(node.getParent());
      pushDelta(node);
    }
  }

  @NotNull
  protected abstract IntervalNode<T> createNewNode(@NotNull T key, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer);
  protected abstract IntervalNode<T> lookupNode(@NotNull T key);
  protected abstract void setNode(@NotNull T key, IntervalNode<T> node);

  private int compareNodes(@NotNull IntervalNode<T> i1, int delta1, @NotNull IntervalNode<T> i2, int delta2, @NotNull List<IntervalNode<T>> invalid) {
    if (!i2.hasAliveKey(false)) {
      invalid.add(i2); //gced
    }
    int start1 = i1.intervalStart() + delta1;
    int start2 = i2.intervalStart() + delta2;
    if (start1 != start2) return start1 - start2;
    return compareEqualStartIntervals(i1, i2);
  }

  protected IntervalNode<T> getRoot() {
    return (IntervalNode<T>)root;
  }

  @Override
  public boolean process(@NotNull Processor<? super T> processor) {
    try {
      l.readLock().lock();
      checkMax(true);
      return process(getRoot(), processor, modCount);
    }
    finally {
      l.readLock().unlock();
    }
  }

  private boolean process(final IntervalNode<T> root, final Processor<? super T> processor, final int modCountBefore) {
    if (root == null) return true;

    WalkingState.TreeGuide<IntervalNode<T>> guide = getGuide();
    return WalkingState.processAll(root, guide, new Processor<IntervalNode<T>>() {
      @Override
      public boolean process(IntervalNode<T> node) {
        if (!node.processAliveKeys(processor)) return false;
        if (modCount != modCountBefore) throw new ConcurrentModificationException();
        return true;
      }
    });
  }

  @Override
  public boolean processOverlappingWith(int start, int end, @NotNull Processor<? super T> processor) {
    try {
      l.readLock().lock();
      checkMax(true);
      return processOverlappingWith(getRoot(), start, end, processor, modCount, 0);
    }
    finally {
      l.readLock().unlock();
    }
  }

  private boolean processOverlappingWith(IntervalNode<T> root,
                                         int start,
                                         int end,
                                         Processor<? super T> processor,
                                         int modCountBefore,
                                         int deltaUpToRootExclusive) {
    if (root == null) {
      return true;
    }
    assert root.isValid();

    int delta = deltaUpToRootExclusive + root.delta;
    if (start > maxEndOf(root, deltaUpToRootExclusive)) {
      return true; // right of the rightmost interval in the subtree
    }

    if (!processOverlappingWith(root.getLeft(), start, end, processor, modCountBefore, delta)) return false;
    int myStartOffset = root.intervalStart() + delta;
    int myEndOffset = root.intervalEnd() + delta;
    boolean overlaps = Math.max(myStartOffset, start) <= Math.min(myEndOffset, end);
    if (overlaps) {
      if (!root.processAliveKeys(processor)) return false;
      if (modCount != modCountBefore) throw new ConcurrentModificationException();
    }

    if (end < myStartOffset) {
      return true; // left of the root, cant be in the right subtree
    }

    return processOverlappingWith(root.getRight(), start, end, processor, modCountBefore, delta);
  }

  public boolean processOverlappingWithOutside(int start, int end, @NotNull Processor<? super T> processor) {
    try {
      l.readLock().lock();
      checkMax(true);
      return processOverlappingWithOutside(getRoot(), start, end, processor, modCount, 0);
    }
    finally {
      l.readLock().unlock();
    }
  }
  private boolean processOverlappingWithOutside(IntervalNode<T> root,
                                                int start,
                                                int end,
                                                @NotNull Processor<? super T> processor,
                                                int modCountBefore,
                                                int deltaUpToRootExclusive) {
    if (root == null) {
      return true;
    }
    assert root.isValid();

    int delta = deltaUpToRootExclusive + root.delta;
    int rootMaxEnd = maxEndOf(root, deltaUpToRootExclusive);
    int rootStartOffset = root.intervalStart() + delta;
    int rootEndOffset = root.intervalEnd() + delta;

    if (!processOverlappingWithOutside(root.getLeft(), start, end, processor, modCountBefore, delta)) return false;

    boolean toProcess = rootStartOffset < start || rootEndOffset > end;
    if (toProcess) {
      if (!root.processAliveKeys(processor)) return false;
      if (modCount != modCountBefore) throw new ConcurrentModificationException();
    }

    if (rootStartOffset >= start && rootMaxEnd <= end) return true; // cant intersect outside

    return processOverlappingWithOutside(root.getRight(), start, end, processor, modCountBefore, delta);
  }


  @Override
  public boolean processContaining(int offset, @NotNull Processor<? super T> processor) {
    try {
      l.readLock().lock();
      checkMax(true);
      return processContaining(getRoot(), offset, processor, modCount, 0);
    }
    finally {
      l.readLock().unlock();
    }
  }
  private boolean processContaining(IntervalNode<T> root,
                                    int offset,
                                    Processor<? super T> processor,
                                    int modCountBefore,
                                    int deltaUpToRootExclusive) {
    if (root == null) {
      return true;
    }
    assert root.isValid();
    int delta = deltaUpToRootExclusive + root.delta;
    if (offset > maxEndOf(root, deltaUpToRootExclusive)) {
      return true; // right of the rightmost interval in the subtree
    }

    if (!processContaining(root.getLeft(), offset, processor, modCountBefore, delta)) return false;
    int myStartOffset = root.intervalStart() + delta;
    int myEndOffset = root.intervalEnd() + delta;
    boolean overlaps = myStartOffset <= offset && offset < myEndOffset;

    if (overlaps) {
      if (!root.processAliveKeys(processor)) return false;
      if (modCount != modCountBefore) throw new ConcurrentModificationException();
    }

    if (offset < myStartOffset) {
      return true; // left of the root, cant be in the right subtree
    }

    return processContaining(root.getRight(), offset, processor, modCountBefore, delta);
  }

  public interface PeekableIterator<T> extends DisposableIterator<T> {
    T peek();
    PeekableIterator EMPTY = new PeekableIterator() {
      @Override
      public Object peek() {
        return null;
      }

      @Override
      public void dispose() {

      }

      @Override
      public boolean hasNext() {
        return false;
      }

      @Override
      public Object next() {
        return null;
      }

      @Override
      public void remove() {
        throw new UnsupportedOperationException("remove");
      }
    };
  }

  @NotNull
  PeekableIterator<T> overlappingIterator(@NotNull final TextRangeInterval rangeInterval) {
    TextRange.assertProperRange(rangeInterval);

    l.readLock().lock();

    try {
      final int startOffset = rangeInterval.getStartOffset();
      final int endOffset = rangeInterval.getEndOffset();
      final IntervalNode<T> firstOverlap = findMinOverlappingWith(getRoot(), rangeInterval, modCount, 0);
      if (firstOverlap == null) {
        l.readLock().unlock();
        return PeekableIterator.EMPTY;
      }
      final int firstOverlapDelta = firstOverlap.computeDeltaUpToRoot();
      final int firstOverlapStart = firstOverlap.intervalStart() + firstOverlapDelta;
      final int modCountBefore = modCount;

      return new PeekableIterator<T>() {
        private IntervalNode<T> currentNode = firstOverlap;
        private int deltaUpToRootExclusive = firstOverlapDelta-firstOverlap.delta;
        private int indexInCurrentList = 0;
        private T current;

        @Override
        public boolean hasNext() {
          if (current != null) return true;
          if (currentNode == null) return false;

          if (modCount != modCountBefore) throw new ConcurrentModificationException();
          while (indexInCurrentList != currentNode.intervals.size()) {
            T t = currentNode.intervals.get(indexInCurrentList++).get();
            if (t != null) {
              current = t;
              return true;
            }
          }
          indexInCurrentList = 0;
          while (true) {
            currentNode = nextNode(currentNode);
            if (currentNode == null) {
              return false;
            }
            if (overlaps(currentNode, rangeInterval, deltaUpToRootExclusive)) {
              assert currentNode.intervalStart() + deltaUpToRootExclusive + currentNode.delta >= firstOverlapStart;
              indexInCurrentList = 0;
              while (indexInCurrentList != currentNode.intervals.size()) {
                T t = currentNode.intervals.get(indexInCurrentList++).get();
                if (t != null) {
                  current = t;
                  return true;
                }
              }
              indexInCurrentList = 0;
            }
          }
        }

        @Override
        public T next() {
          if (!hasNext()) throw new NoSuchElementException();
          T t = current;
          current = null;
          return t;
        }

        @Override
        public T peek() {
          if (!hasNext()) throw new NoSuchElementException();
          return current;
        }

        @Override
        public void remove() {
          throw new IncorrectOperationException();
        }

        @Override
        public void dispose() {
          l.readLock().unlock();
        }

        // next node in in-order traversal
        private IntervalNode<T> nextNode(@NotNull IntervalNode<T> root) {
          assert root.isValid() : root;
          int delta = deltaUpToRootExclusive + root.delta;
          int myMaxEnd = maxEndOf(root, deltaUpToRootExclusive);
          if (startOffset > myMaxEnd) return null; // tree changed

          // try to go right down
          IntervalNode<T> right = root.getRight();
          if (right != null) {
            int rightMaxEnd = maxEndOf(right, delta);
            if (startOffset <= rightMaxEnd) {
              int rightDelta = delta + right.delta;
              while (right.getLeft() != null && startOffset <= maxEndOf(right.getLeft(), rightDelta)) {
                right = right.getLeft();
                rightDelta += right.delta;
              }
              deltaUpToRootExclusive = rightDelta - right.delta;
              return right;
            }
          }

          // go up
          while (true) {
            IntervalNode<T> parent = root.getParent();
            if (parent == null) return null;
            if (parent.intervalStart() + deltaUpToRootExclusive > endOffset) return null; // can't move right
            deltaUpToRootExclusive -= parent.delta;

            if (parent.getLeft() == root) {
              return parent;
            }

            root = parent;
          }
        }
      };
    }
    catch (RuntimeException e) {
      l.readLock().unlock();
      throw e;
    }
    catch (Error e) {
      l.readLock().unlock();
      throw e;
    }
  }

  private boolean overlaps(IntervalNode<T> root, @NotNull TextRangeInterval rangeInterval, int deltaUpToRootExclusive) {
    if (root == null) return false;
    int delta = root.delta + deltaUpToRootExclusive;
    int start = root.intervalStart() + delta;
    int end = root.intervalEnd() + delta;
    return rangeInterval.intersects(start, end);
  }

  protected IntervalNode<T> findOrInsert(@NotNull IntervalNode<T> node) {
    assertUnderWriteLock();
    node.setRed();
    node.setParent(null);
    node.setValid(true);
    node.maxEnd = 0;
    node.clearDelta();
    node.setLeft(null);
    node.setRight(null);

    List<IntervalNode<T>> gced = new SmartList<IntervalNode<T>>();
    if (root == null) {
      root = node;
    }
    else {
      IntervalNode<T> current = getRoot();
      while (true) {
        pushDelta(current);
        int compResult = compareNodes(node, 0, current, 0, gced);
        if (compResult == 0) {
          return current;
        }
        if (compResult < 0) {
          if (current.getLeft() == null) {
            current.setLeft(node);
            break;
          }
          current = current.getLeft();
        }
        else /*if (compResult > 0)*/ {
          if (current.getRight() == null) {
            current.setRight(node);
            break;
          }
          current = current.getRight();
        }
      }
      node.setParent(current);
    }
    node.setCachedValues(0, true, modCount);
    correctMaxUp(node);
    onInsertNode();
    keySize += node.intervals.size();
    insertCase1(node);
    node.setAttachedToTree(true);
    verifyProperties();

    deleteNodes(gced);
    return node;
  }

  private void deleteNodes(@NotNull List<IntervalNode<T>> collectedAway) {
    if (collectedAway.isEmpty()) return;
    try {
      l.writeLock().lock();
      for (IntervalNode<T> node : collectedAway) {
        removeNode(node);
      }
    }
    finally {
      l.writeLock().unlock();
    }
  }

  public IntervalTreeImpl.IntervalNode<T> addInterval(@NotNull T interval, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
    try {
      l.writeLock().lock();
      checkMax(true);
      processReferenceQueue();
      modCount++;
      IntervalNode<T> newNode = createNewNode(interval, start, end, greedyToLeft, greedyToRight, layer);
      IntervalNode<T> insertedNode = findOrInsert(newNode);
      if (insertedNode == newNode) {
        setNode(interval, insertedNode);
      }
      else {
        // merged
        insertedNode.addInterval(interval);
      }
      checkMax(true);
      checkBelongsToTheTree(interval, true);
      return insertedNode;
    }
    finally {
      l.writeLock().unlock();
    }
  }

  // returns true if all markers are valid
  public boolean checkMax(boolean assertInvalid) {
    return VERIFY && doCheckMax(assertInvalid);
  }

  protected boolean doCheckMax(boolean assertInvalid) {
    try {
      l.readLock().lock();

      Ref<Boolean> allValid = new Ref<Boolean>(true);
      int[] keyCounter = new int[1];
      int[] nodeCounter = new int[1];
      TLongHashSet ids = new TLongHashSet(keySize);
      checkMax(getRoot(), 0, assertInvalid, allValid, keyCounter, nodeCounter, ids, true);
      if (assertInvalid) {
        assert nodeSize() == nodeCounter[0] : "node size: "+ nodeSize() +"; actual: "+nodeCounter[0];
        assert keySize == keyCounter[0] : "key size: "+ keySize +"; actual: "+keyCounter[0];
        assert keySize >= nodeSize() : keySize + "; "+nodeSize();
      }
      return allValid.get();
    }
    finally {
      l.readLock().unlock();
    }
  }

  private static class IntTrinity {
    private final int first;
    private final int second;
    private final int third;

    private IntTrinity(int first, int second, int third) {
      this.first = first;
      this.second = second;
      this.third = third;
    }
  }

  // returns real (minStart, maxStart, maxEnd)
  private IntTrinity checkMax(IntervalNode<T> root,
                                                    int deltaUpToRootExclusive,
                                                    boolean assertInvalid,
                                                    Ref<Boolean> allValid,
                                                    int[] keyCounter,
                                                    int[] nodeCounter,
                                                    TLongHashSet ids, boolean allDeltasUpAreNull) {
    if (root == null) return new IntTrinity(Integer.MAX_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE);
    long packedOffsets = root.cachedDeltaUpToRoot;
    if (IntervalNode.modCount(packedOffsets) == modCount) {
      assert IntervalNode.allDeltasUpAreNull(packedOffsets) == (root.delta == 0 && allDeltasUpAreNull);
      assert IntervalNode.deltaUpToRoot(packedOffsets) == root.delta + deltaUpToRootExclusive;
    }
    T liveInterval = null;
    for (int i = root.intervals.size() - 1; i >= 0; i--) {
      T t = root.intervals.get(i).get();
      if (t == null) continue;
      liveInterval = t;
      checkBelongsToTheTree(t, false);
      boolean added = ids.add(((RangeMarkerImpl)t).getId());
      assert added : t;
    }
    if (assertInvalid && liveInterval != null) {
      checkBelongsToTheTree(liveInterval, true);
    }

    keyCounter[0]+= root.intervals.size();
    nodeCounter[0]++;
    int delta = deltaUpToRootExclusive + (root.isValid() ? root.delta : 0);
    IntTrinity l = checkMax(root.getLeft(), delta, assertInvalid, allValid, keyCounter, nodeCounter, ids, root.delta == 0 && allDeltasUpAreNull);
    int minLeftStart = l.first;
    int maxLeftStart = l.second;
    int maxLeftEnd = l.third;
    IntTrinity r = checkMax(root.getRight(), delta, assertInvalid, allValid, keyCounter, nodeCounter, ids, root.delta == 0 && allDeltasUpAreNull);
    int maxRightEnd = r.third;
    int minRightStart = r.first;
    int maxRightStart = r.second;
    if (!root.isValid()) {
      allValid.set(false);
      if (assertInvalid) assert false : root;
      return new IntTrinity(Math.min(minLeftStart, minRightStart), Math.max(maxLeftStart, maxRightStart), Math.max(maxRightEnd, maxLeftEnd));
    }
    IntervalNode<T> parent = root.getParent();
    if (parent != null && assertInvalid && root.hasAliveKey(false)) {
      int c = compareNodes(root, delta, parent, delta - root.delta, new SmartList<IntervalNode<T>>());
      assert c != 0;
      assert c < 0 && parent.getLeft() == root || c > 0 && parent.getRight() == root;
    }
    assert delta + root.maxEnd == Math.max(maxLeftEnd, Math.max(maxRightEnd, delta + root.intervalEnd()));
    int myStartOffset = delta + root.intervalStart();
    assert maxLeftStart <= myStartOffset;
    assert minRightStart >= myStartOffset;
    assert myStartOffset >= 0;
    assert minLeftStart == Integer.MAX_VALUE || minLeftStart <= myStartOffset;
    assert maxRightStart == Integer.MIN_VALUE || maxRightStart >= myStartOffset;
    int minStart = Math.min(minLeftStart, myStartOffset);
    int maxStart = Math.max(myStartOffset, Math.max(maxLeftStart, maxRightStart));
    assert minStart <= maxStart;
    return new IntTrinity(minStart, maxStart, root.maxEnd + delta);
  }

  @Override
  protected Node<T> maximumNode(Node<T> n) {
    IntervalNode<T> root = (IntervalNode<T>)n;
    pushDelta(root.getParent());
    pushDelta(root);
    while (root.getRight() != null) {
      root = root.getRight();
      pushDelta(root);
    }
    return root;
  }

  protected void checkBelongsToTheTree(T interval, boolean assertInvalid) {
    IntervalNode<T> root = lookupNode(interval);
    if (root == null) return;
    assert root.getTree() == this : root.getTree() +"; this: "+this;
    if (!VERIFY) return;

    if (assertInvalid) {
      assert !root.intervals.isEmpty();
      boolean contains = false;
      for (int i = root.intervals.size() - 1; i >= 0; i--) {
        T key = root.intervals.get(i).get();
        if (key == null) continue;
        contains |= key == interval;
        IntervalNode<T> node = lookupNode(key);
        assert node == root : node;
        assert node.getTree() == this : node;
      }

      assert contains : root.intervals + "; " + interval;
    }

    IntervalNode<T> e = root;
    while (e.getParent() != null) e = e.getParent();
    assert e == getRoot(); // assert the node belongs to our tree
  }

  @Override
  public boolean removeInterval(@NotNull T interval) {
    if (!interval.isValid()) return false;
    try {
      l.writeLock().lock();
      modCount++;
      if (!interval.isValid()) return false;
      checkBelongsToTheTree(interval, true);
      checkMax(true);
      processReferenceQueue();

      IntervalNode<T> node = lookupNode(interval);
      if (node == null) return false;

      reportInvalidation(interval, "Explicit Dispose");

      node.removeInterval(interval);
      setNode(interval, null);

      checkMax(true);
      return true;
    }
    finally {
      l.writeLock().unlock();
    }
  }

  // run under write lock
  void removeNode(@NotNull IntervalNode<T> node) {
    deleteNode(node);
    IntervalNode<T> parent = node.getParent();
    correctMaxUp(parent);
  }

  @Override
  protected void deleteNode(@NotNull Node<T> n) {
    assertUnderWriteLock();
    IntervalNode<T> node = (IntervalNode<T>)n;
    pushDeltaFromRoot(node);
    assertAllDeltasAreNull(node);
    super.deleteNode(n);

    keySize -= node.intervals.size();
    assert keySize >= 0 : keySize;
    node.setAttachedToTree(false);
  }

  @Override
  public int size() {
    return keySize;
  }

  // returns true if all deltas involved are still 0
  protected boolean pushDelta(IntervalNode<T> root) {
    if (root == null || !root.isValid()) return true;
    IntervalNode<T> parent = root.getParent();
    assertAllDeltasAreNull(parent);
    int delta = root.delta;
    root.setCachedValues(0, true, 0);
    if (delta != 0) {
      root.setIntervalStart(root.intervalStart() + delta);
      root.setIntervalEnd(root.intervalEnd() + delta);
      root.maxEnd += delta;
      root.delta = 0;
      //noinspection NonShortCircuitBooleanExpression
      return
      incDelta(root.getLeft(), delta) &
      incDelta(root.getRight(), delta);
    }
    root.setCachedValues(0, true, modCount);
    return true;
  }

  // returns true if all deltas involved are still 0
  private boolean incDelta(IntervalNode<T> root, int delta) {
    if (root == null) return true;
    if (root.isValid()) {
      int newDelta = root.changeDelta(delta);
      return newDelta == 0;
    }
    else {
      //noinspection NonShortCircuitBooleanExpression
      return
      incDelta(root.getLeft(), delta) &
      incDelta(root.getRight(), delta);
    }
  }

  @Override
  protected IntervalNode<T> swapWithMaxPred(Node<T> root, Node<T> maxPred) {
    checkMax(false);
    IntervalNode<T> a = (IntervalNode<T>)root;
    IntervalNode<T> d = (IntervalNode<T>)maxPred;
    boolean acolor = a.isBlack();
    boolean dcolor = d.isBlack();
    assert !a.isValid() || a.delta == 0 : a.delta;
    for (IntervalNode<T> n = a.getLeft(); n != null; n = n.getRight()) {
      assert !n.isValid() || n.delta == 0 : n.delta;
    }
    swapNodes(a, d);

    // set range of the key to be deleted so it wont disrupt maxes
    a.setValid(false);
    //a.key.setIntervalStart(d.key.intervalStart());
    //a.key.setIntervalEnd(d.key.intervalEnd());

    //correctMaxUp(a);
    a.setColor(dcolor);
    d.setColor(acolor);
    correctMaxUp(a);

    checkMax(false);
    assert a.delta == 0 : a.delta;
    assert d.delta == 0 : d.delta;
    return a;
  }
  private void swapNodes(IntervalNode<T> n1, IntervalNode<T> n2) {
    IntervalNode<T> l1 = n1.getLeft();
    IntervalNode<T> r1 = n1.getRight();
    IntervalNode<T> p1 = n1.getParent();
    IntervalNode<T> l2 = n2.getLeft();
    IntervalNode<T> r2 = n2.getRight();
    IntervalNode<T> p2 = n2.getParent();

    if (p1 != null) {
      if (p1.getLeft() == n1) p1.setLeft(n2); else p1.setRight(n2);
    }
    else {
      root = n2;
    }
    if (p2 != null) {
      if (p2.getLeft() == n2) p2.setLeft(p2 == n1 ? l2 : n1); else p2.setRight(p2 == n1 ? r2 : n1);
    }
    else {
      root = n1;
    }
    n1.setParent(p2 == n1 ? n2 : p2);
    n2.setParent(p1);

    n1.setLeft(l2);
    n2.setLeft(l1 == n2 ? n1 : l1);
    if (l1 != null) l1.setParent(n2 == l1 ? p1 : n2);
    if (r1 != null) r1.setParent(n2);
    n1.setRight(r2);
    n2.setRight(r1);
    if (l2 != null) l2.setParent(n1);
    if (r2 != null) r2.setParent(n1);
  }

  // returns real max endOffset of all intervals below
  private int maxEndOf(IntervalNode<T> node, int deltaUpToRootExclusive) {
    if (node == null) {
      return 0;
    }
    if (node.isValid()) {
      return node.maxEnd + node.delta + deltaUpToRootExclusive;
    }
    // since node is invalid, ignore node.delta
    return Math.max(maxEndOf(node.getLeft(), deltaUpToRootExclusive), maxEndOf(node.getRight(), deltaUpToRootExclusive));
  }

  // max of n.left's maxend, n.right's maxend and its own interval endOffset
  protected void correctMax(@NotNull IntervalNode<T> node, int deltaUpToRoot) {
    if (!node.isValid()) return;
    int realMax = Math.max(Math.max(maxEndOf(node.getLeft(), deltaUpToRoot), maxEndOf(node.getRight(), deltaUpToRoot)),
                           deltaUpToRoot + node.intervalEnd());
    node.maxEnd = realMax - deltaUpToRoot;
  }

  private void correctMaxUp(IntervalNode<T> node) {
    int delta = node == null ? 0 : node.computeDeltaUpToRoot();
    assert delta == 0 : delta;
    while (node != null) {
      if (node.isValid()) {
        int d = node.delta;
        correctMax(node, delta);
        delta -= d;
      }
      node = node.getParent();
    }
    assert delta == 0 : delta;
  }

  @Override
  protected void rotateRight(Node<T> n) {
    checkMax(false);
    IntervalNode<T> node1 = (IntervalNode<T>)n;
    IntervalNode<T> node2 = node1.getLeft();
    IntervalNode<T> node3 = node1.getRight();

    IntervalNode<T> parent = node1.getParent();
    int deltaUp = parent == null ? 0 : parent.computeDeltaUpToRoot();
    pushDelta(node1);
    pushDelta(node2);
    pushDelta(node3);

    super.rotateRight(node1);

    if (node3 != null) {
      correctMax(node3, deltaUp);
    }
    correctMax(node1, deltaUp);
    correctMax(node2, deltaUp);
    assertAllDeltasAreNull(node1);
    assertAllDeltasAreNull(node2);
    assertAllDeltasAreNull(node3);
    checkMax(false);
  }

  @Override
  protected void rotateLeft(Node<T> n) {
    checkMax(false);
    IntervalNode<T> node1 = (IntervalNode<T>)n;
    IntervalNode<T> node2 = node1.getLeft();
    IntervalNode<T> node3 = node1.getRight();

    IntervalNode<T> parent = node1.getParent();
    int deltaUp = parent == null ? 0 : parent.computeDeltaUpToRoot();
    pushDelta(node1);
    pushDelta(node2);
    pushDelta(node3);
    checkMax(false);
    super.rotateLeft(node1);

    if (node2 != null) {
      correctMax(node2, deltaUp);
    }
    correctMax(node1, deltaUp);
    correctMax(node3, deltaUp);
    assertAllDeltasAreNull(node1);
    assertAllDeltasAreNull(node2);
    assertAllDeltasAreNull(node3);

    checkMax(false);
  }

  @Override
  protected void replaceNode(@NotNull Node<T> node, Node<T> child) {
    IntervalNode<T> myNode = (IntervalNode<T>)node;
    pushDelta(myNode);
    pushDelta((IntervalNode<T>)child);

    super.replaceNode(node, child);
    if (child != null && myNode.isValid()) {
      ((IntervalNode<T>)child).changeDelta(myNode.delta);
      //todo correct max up to root??
    }
  }

  private void assertAllDeltasAreNull(IntervalNode<T> node) {
    if (node == null) return;
    if (!node.isValid()) return;
    assert node.delta == 0;
    long packedOffsets = node.cachedDeltaUpToRoot;
    assert IntervalNode.modCount(packedOffsets) != modCount || IntervalNode.allDeltasUpAreNull(packedOffsets);
  }

  private IntervalNode<T> findMinOverlappingWith(IntervalNode<T> root, Interval interval, int modCountBefore, int deltaUpToRootExclusive) {
    if (root == null) {
      return null;
    }
    assert root.isValid();

    int delta = deltaUpToRootExclusive + root.delta;
    if (interval.intervalStart() > maxEndOf(root, deltaUpToRootExclusive)) {
      return null; // right of the rightmost interval in the subtree
    }

    IntervalNode<T> inLeft = findMinOverlappingWith(root.getLeft(), interval, modCountBefore, delta);
    if (inLeft != null) return inLeft;
    int myStartOffset = root.intervalStart() + delta;
    int myEndOffset = root.intervalEnd() + delta;
    boolean overlaps = Math.max(myStartOffset, interval.intervalStart()) <= Math.min(myEndOffset, interval.intervalEnd());
    if (overlaps) return root;
    if (modCount != modCountBefore) throw new ConcurrentModificationException();

    if (interval.intervalEnd() < myStartOffset) {
      return null; // left of the root, cant be in the right subtree
    }

    return findMinOverlappingWith(root.getRight(), interval, modCountBefore, delta);
  }

  public void changeData(T interval, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
    try {
      l.writeLock().lock();

      IntervalNode<T> node = lookupNode(interval);
      if (node == null) return;
      int before = size();
      boolean nodeRemoved = node.removeInterval(interval);
      assert nodeRemoved || !node.intervals.isEmpty();

      IntervalNode<T> insertedNode = addInterval(interval, start, end, greedyToLeft, greedyToRight, layer);
      assert node != insertedNode;

      int after = size();
      // can be gced
      assert before >= after : before +";" + after;
      checkBelongsToTheTree(interval, true);
      checkMax(true);
    }
    finally {
      l.writeLock().unlock();
    }
  }


  // called under write lock
  private void processReferenceQueue() {
    int dead = 0;
    while (myReferenceQueue.poll() != null) {
      dead++;
    }

    deadReferenceCount += dead;
    if (deadReferenceCount > Math.max(1, size() / 3)) {
      purgeDeadNodes();
      deadReferenceCount = 0;
    }
  }

  private void purgeDeadNodes() {
    assertUnderWriteLock();
    List<IntervalNode<T>> gced = new SmartList<IntervalNode<T>>();
    collectGced(getRoot(), gced);
    deleteNodes(gced);
    checkMax(true);
  }

  @Override
  public void clear() {
    process(new Processor<T>() {
      @Override
      public boolean process(T t) {
        reportInvalidation(t, "Clear all");
        return true;
      }
    });
    l.writeLock().lock();
    try {
      super.clear();
      keySize = 0;
    }
    finally {
      l.writeLock().unlock();
    }
  }

  private void collectGced(IntervalNode<T> root, List<IntervalNode<T>> gced) {
    if (root == null) return;
    if (!root.hasAliveKey(true)) gced.add(root);
    collectGced(root.getLeft(), gced);
    collectGced(root.getRight(), gced);
  }


  private void printSorted() { printSorted(getRoot());}
  private void printSorted(IntervalNode<T> root) {
    if (root == null) return;
    printSorted(root.getLeft());
    System.out.println(root);
    printSorted(root.getRight());
  }

  void reportInvalidation(T markerEx, @NonNls Object reason) {
  }

  private static class IntervalTreeGuide<T extends MutableInterval> implements WalkingState.TreeGuide<IntervalNode<T>> {
    @Override
    public IntervalNode<T> getNextSibling(@NotNull IntervalNode<T> element) {
      IntervalNode<T> parent = element.getParent();
      if (parent == null) return null;
      return parent.getLeft() == element ? parent.getRight() : null;
    }

    @Override
    public IntervalNode<T> getPrevSibling(@NotNull IntervalNode<T> element) {
      IntervalNode<T> parent = element.getParent();
      if (parent == null) return null;
      return parent.getRight() == element ? parent.getLeft() : null;
    }

    @Override
    public IntervalNode<T> getFirstChild(@NotNull IntervalNode<T> element) {
      IntervalNode<T> left = element.getLeft();
      return left == null ? element.getRight() : left;
    }

    @Override
    public IntervalNode<T> getParent(@NotNull IntervalNode<T> element) {
      return element.getParent();
    }
  }

  private static final IntervalTreeGuide INTERVAL_TREE_GUIDE_INSTANCE = new IntervalTreeGuide();
  private static <T extends MutableInterval> WalkingState.TreeGuide<IntervalNode<T>> getGuide() {
    //noinspection unchecked
    return (WalkingState.TreeGuide)INTERVAL_TREE_GUIDE_INSTANCE;
  }


  public int maxHeight() {
    return maxHeight(root);
  }

  private int maxHeight(Node<T> root) {
    return root == null ? 0 : 1 + Math.max(maxHeight(root.left), maxHeight(root.right));
  }
}