1 files changed, 55 insertions, 57 deletions

diff --git a/platform/platform-api/src/com/intellij/openapi/editor/highlighter/FragmentedEditorHighlighter.java b/platform/platform-api/src/com/intellij/openapi/editor/highlighter/FragmentedEditorHighlighter.java
index d3f7d9f13f8c..13b2c43faa7b 100644
--- a/platform/platform-api/src/com/intellij/openapi/editor/highlighter/FragmentedEditorHighlighter.java
+++ b/platform/platform-api/src/com/intellij/openapi/editor/highlighter/FragmentedEditorHighlighter.java
@@ -16,8 +16,6 @@
 package com.intellij.openapi.editor.highlighter;
 
 import com.intellij.openapi.editor.Document;
-import com.intellij.openapi.editor.HighlighterColors;
-import com.intellij.openapi.editor.colors.EditorColorsManager;
 import com.intellij.openapi.editor.colors.EditorColorsScheme;
 import com.intellij.openapi.editor.event.DocumentEvent;
 import com.intellij.openapi.editor.markup.TextAttributes;
@@ -25,9 +23,10 @@ import com.intellij.openapi.util.TextRange;
 import com.intellij.psi.tree.IElementType;
 import org.jetbrains.annotations.NotNull;
 
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
-import java.util.Map;
-import java.util.TreeMap;
 
 /**
  * Created by IntelliJ IDEA.
@@ -36,10 +35,9 @@ import java.util.TreeMap;
  * Time: 12:52 PM
  */
 public class FragmentedEditorHighlighter implements EditorHighlighter {
-  private final TreeMap<Integer, Element> myPieces;
+  private final List<Element> myPieces;
   private final Document myDocument;
   private final int myAdditionalOffset;
-  private TextAttributes myUsualAttributes;
   private final boolean myMergeByTextAttributes;
 
   public FragmentedEditorHighlighter(HighlighterIterator sourceIterator, List<TextRange> ranges) {
@@ -52,50 +50,72 @@ public class FragmentedEditorHighlighter implements EditorHighlighter {
                                      boolean mergeByTextAttributes) {
     myMergeByTextAttributes = mergeByTextAttributes;
     myDocument = sourceIterator.getDocument();
-    myPieces = new TreeMap<Integer, Element>();
+    myPieces = new ArrayList<Element>();
     myAdditionalOffset = additionalOffset;
     translate(sourceIterator, ranges);
   }
 
   private void translate(HighlighterIterator iterator, List<TextRange> ranges) {
-    if (iterator.atEnd()) return;
     int offset = 0;
-    for (TextRange range : ranges) {
-      while (range.getStartOffset() > iterator.getStart()) {
+    int index = 0;
+
+    while (!iterator.atEnd() && index < ranges.size()) {
+      TextRange range = ranges.get(index);
+
+      if (range.getStartOffset() >= iterator.getEnd()) {
         iterator.advance();
-        if (iterator.atEnd()) return;
+        continue;
       }
-      while (range.getEndOffset() >= iterator.getEnd()) {
-        int relativeStart = iterator.getStart() - range.getStartOffset();
+
+      if (range.getEndOffset() >= iterator.getStart()) {
+        int relativeStart = Math.max(iterator.getStart() - range.getStartOffset(), 0);
+        int relativeEnd = Math.min(iterator.getEnd() - range.getStartOffset(), range.getLength() + 1);
         boolean merged = false;
-        if (myMergeByTextAttributes && ! myPieces.isEmpty()) {
-          final Integer first = myPieces.descendingKeySet().first();
-          final Element element = myPieces.get(first);
-          if (element.getEnd() >= offset + relativeStart && myPieces.get(first).getAttributes().equals(iterator.getTextAttributes())) {
-            // merge
+        if (myMergeByTextAttributes && !myPieces.isEmpty()) {
+          Element element = myPieces.get(myPieces.size() - 1);
+          if (element.getEnd() >= offset + relativeStart &&
+              element.getAttributes().equals(iterator.getTextAttributes()) &&
+              element.getElementType().equals(iterator.getTokenType())) {
             merged = true;
-            myPieces.put(element.getStart(), new Element(element.getStart(),
-                                                         offset + (iterator.getEnd() - range.getStartOffset()), iterator.getTokenType(),
-                                                         iterator.getTextAttributes()));
+            myPieces.add(new Element(element.getStart(),
+                                     offset + relativeEnd,
+                                     iterator.getTokenType(),
+                                     iterator.getTextAttributes()));
           }
         }
-        if (! merged) {
-          myPieces.put(offset + relativeStart, new Element(offset + relativeStart,
-                                                           offset + (iterator.getEnd() - range.getStartOffset()), iterator.getTokenType(),
-                                                           iterator.getTextAttributes()));
+        if (!merged) {
+          myPieces.add(new Element(offset + relativeStart,
+                                   offset + relativeEnd,
+                                   iterator.getTokenType(),
+                                   iterator.getTextAttributes()));
         }
-        iterator.advance();
-        if (iterator.atEnd()) return;
       }
-      offset += range.getLength() + 1 + myAdditionalOffset;  // myAdditionalOffset because of extra line - for shoene separators
+
+      if (range.getEndOffset() < iterator.getEnd()) {
+        offset += range.getLength() + 1 + myAdditionalOffset;  // myAdditionalOffset because of extra line - for shoene separators
+        int lastEnd = myPieces.isEmpty() ? -1 : myPieces.get(myPieces.size() - 1).getEnd();
+        myPieces.add(new Element(Math.max(offset - 1 - myAdditionalOffset, lastEnd), offset, null, TextAttributes.ERASE_MARKER));
+        index++;
+        continue;
+      }
+
+      iterator.advance();
     }
   }
 
   @NotNull
   @Override
   public HighlighterIterator createIterator(int startOffset) {
-    Map.Entry<Integer, Element> entry = myPieces.ceilingEntry(startOffset);
-    return new ProxyIterator(myDocument, entry == null ? -1 : entry.getKey());
+    int index = Collections.binarySearch(myPieces, new Element(startOffset, 0, null, null), new Comparator<Element>() {
+      @Override
+      public int compare(Element o1, Element o2) {
+        return o1.getStart() - o2.getStart();
+      }
+    });
+    // index: (-insertion point - 1), where insertionPoint is the index of the first element greater than the key
+    // and we need index of the first element that is less or equal (floorElement)
+    if (index < 0) index = Math.max(-index - 2, 0);
+    return new ProxyIterator(myDocument, index);
   }
 
   @Override
@@ -149,27 +169,21 @@ public class FragmentedEditorHighlighter implements EditorHighlighter {
 
     @Override
     public void advance() {
-      if (myIdx == myPieces.lastKey() || myIdx == -1) {
-        myIdx = -1;
-        return;
+      if (myIdx < myPieces.size()) {
+        myIdx++;
       }
-      Map.Entry<Integer, Element> entry = myPieces.tailMap(myIdx, false).firstEntry();
-      myIdx = entry.getKey();
     }
 
     @Override
     public void retreat() {
-      if (myIdx == myPieces.firstKey() || myIdx == -1) {
-        myIdx = -1;
-        return;
+      if (myIdx > -1) {
+        myIdx--;
       }
-      Map.Entry<Integer, Element> entry = myPieces.headMap(myIdx, false).lastEntry();
-      myIdx = entry.getKey();
     }
 
     @Override
     public boolean atEnd() {
-      return myIdx < 0;
+      return myIdx < 0 || myIdx >= myPieces.size();
     }
 
     @Override
@@ -178,22 +192,6 @@ public class FragmentedEditorHighlighter implements EditorHighlighter {
     }
   }
 
-  private boolean isUsualAttributes(final TextAttributes ta) {
-    if (myUsualAttributes == null) {
-      final EditorColorsManager manager = EditorColorsManager.getInstance();
-      final EditorColorsScheme[] schemes = manager.getAllSchemes();
-      EditorColorsScheme defaultScheme = schemes[0];
-      for (EditorColorsScheme scheme : schemes) {
-        if (manager.isDefaultScheme(scheme)) {
-          defaultScheme = scheme;
-          break;
-        }
-      }
-      myUsualAttributes = defaultScheme.getAttributes(HighlighterColors.TEXT);
-    }
-    return myUsualAttributes.equals(ta);
-  }
-  
   private static class Element {
     private final int myStart;
     private final int myEnd;