platform/platform-impl/src/com/intellij/openapi/editor/impl/FoldRegionsTree.java - platform/tools/idea - Git at Google

 /*
  * 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.Document;
 import com.intellij.openapi.editor.FoldRegion;
 import com.intellij.openapi.editor.RangeMarker;
 import com.intellij.openapi.util.TextRange;
 import com.intellij.util.ArrayUtil;
 import com.intellij.util.containers.ContainerUtil;
 import org.jetbrains.annotations.NotNull;
 import org.jetbrains.annotations.Nullable;

 import java.util.*;

 /**
 * User: cdr
 */
 abstract class FoldRegionsTree {

   @SuppressWarnings("UseOfArchaicSystemPropertyAccessors")
   public static final boolean DEBUG = Boolean.getBoolean("idea.editor.debug.folding");

   private FoldRegion[] myCachedVisible;
   private FoldRegion[] myCachedTopLevelRegions;
   private int[] myCachedEndOffsets;
   private int[] myCachedStartOffsets;
   private int[] myCachedFoldedLines;
   int myCachedLastIndex = -1;

   //sorted using RangeMarker.BY_START_OFFSET comparator
   //i.e., first by start offset, then, if start offsets are equal, by end offset
   private ArrayList<FoldRegion> myRegions = ContainerUtil.newArrayList();

   private static final Comparator<FoldRegion> BY_END_OFFSET = new Comparator<FoldRegion>() {
     @Override
     public int compare(FoldRegion r1, FoldRegion r2) {
       int end1 = r1.getEndOffset();
       int end2 = r2.getEndOffset();
       if (end1 < end2) return -1;
       if (end1 > end2) return 1;
       return 0;
     }
   };
   private static final Comparator<? super FoldRegion> BY_END_OFFSET_REVERSE = Collections.reverseOrder(BY_END_OFFSET);

   void clear() {
     myCachedVisible = null;
     myCachedTopLevelRegions = null;
     myCachedEndOffsets = null;
     myCachedStartOffsets = null;
     myCachedFoldedLines = null;

     if (myRegions != null) {
       for (FoldRegion region : myRegions) {
         region.dispose();
       }
     }

     myRegions = new ArrayList<FoldRegion>();
   }

   private boolean isFoldingEnabledAndUpToDate() {
     return isFoldingEnabled() && myCachedVisible != null;
   }

   protected abstract boolean isFoldingEnabled();

   protected abstract boolean isBatchFoldingProcessing();

   void rebuild() {
     ArrayList<FoldRegion> topLevels = new ArrayList<FoldRegion>(myRegions.size() / 2);
     ArrayList<FoldRegion> visible = new ArrayList<FoldRegion>(myRegions.size());
     ArrayList<FoldRegion> allValid = new ArrayList<FoldRegion>(myRegions.size());
     FoldRegion[] regions = toFoldArray(myRegions);
     FoldRegion currentCollapsed = null;
     for (FoldRegion region : regions) {
       if (!region.isValid()) {
         continue;
       }

       allValid.add(region);

       if (!region.isExpanded()) {
         removeRegionsWithSameStartOffset(visible, region);
         removeRegionsWithSameStartOffset(topLevels, region);
       }

       if (currentCollapsed == null || !contains(currentCollapsed, region)) {
         visible.add(region);
         if (!region.isExpanded()) {
           currentCollapsed = region;
           topLevels.add(region);
         }
       }
     }

     if (allValid.size() < myRegions.size()) {
       myRegions = allValid;
     }

     myCachedTopLevelRegions = toFoldArray(topLevels);
     myCachedVisible = toFoldArray(visible);

     Arrays.sort(myCachedTopLevelRegions, BY_END_OFFSET);
     Arrays.sort(myCachedVisible, BY_END_OFFSET_REVERSE);

     updateCachedOffsets();
   }

   private static void removeRegionsWithSameStartOffset(List<FoldRegion> regions, FoldRegion region) {
     for (int i = regions.size() - 1; i >= 0 ; i--) {
       if (regions.get(i).getStartOffset() == region.getStartOffset()) {
         regions.remove(i);
       }
       else {
         break;
       }
     }
   }

   @NotNull
   private static FoldRegion[] toFoldArray(@NotNull List<FoldRegion> topLevels) {
     return topLevels.isEmpty() ? FoldRegion.EMPTY_ARRAY : topLevels.toArray(new FoldRegion[topLevels.size()]);
   }

   void updateCachedOffsets() {
     if (!isFoldingEnabled()) {
       return;
     }
     if (myCachedVisible == null) {
       rebuild();
       return;
     }

     for (FoldRegion foldRegion : myCachedVisible) {
       if (!foldRegion.isValid()) {
         rebuild();
         return;
       }
     }

     int length = myCachedTopLevelRegions.length;
     if (myCachedEndOffsets == null || myCachedEndOffsets.length != length) {
       if (length != 0) {
         myCachedEndOffsets = new int[length];
         myCachedStartOffsets = new int[length];
         myCachedFoldedLines = new int[length];
       }
       else {
         myCachedEndOffsets = ArrayUtil.EMPTY_INT_ARRAY;
         myCachedStartOffsets = ArrayUtil.EMPTY_INT_ARRAY;
         myCachedFoldedLines = ArrayUtil.EMPTY_INT_ARRAY;
       }
     }

     int sum = 0;
     for (int i = 0; i < length; i++) {
       FoldRegion region = myCachedTopLevelRegions[i];
       myCachedStartOffsets[i] = region.getStartOffset();
       myCachedEndOffsets[i] = region.getEndOffset() - 1;
       Document document = region.getDocument();
       sum += document.getLineNumber(region.getEndOffset()) - document.getLineNumber(region.getStartOffset());
       myCachedFoldedLines[i] = sum;
     }
   }

   boolean addRegion(FoldRegion range) {
     // During batchProcessing elements are inserted in ascending order,
     // binary search find acceptable insertion place first time
     boolean canUseCachedValue = false;
     if (isBatchFoldingProcessing() && myCachedLastIndex >= 0 && myCachedLastIndex < myRegions.size()) {
       FoldRegion lastRegion = myRegions.get(myCachedLastIndex);
       if (RangeMarker.BY_START_OFFSET.compare(lastRegion, range) < 0) {
         canUseCachedValue = myCachedLastIndex == (myRegions.size() - 1)
                             || RangeMarker.BY_START_OFFSET.compare(range, myRegions.get(myCachedLastIndex + 1)) <= 0;
       }
     }
     int index = canUseCachedValue ? myCachedLastIndex + 1 : Collections.binarySearch(myRegions, range, RangeMarker.BY_START_OFFSET);
     if (index < 0) index = -index - 1;

     if (index < myRegions.size()) {
       FoldRegion foldRegion = myRegions.get(index);
       if (TextRange.areSegmentsEqual(foldRegion, range)) {
         return false;
       }
     }

     for (int i = index - 1; i >=0; --i) {
       final FoldRegion region = myRegions.get(i);
       if (region.getEndOffset() < range.getStartOffset()) break;
       if (region.isValid() && intersects(region, range)) {
         return false;
       }
     }

     for (int i = index; i < myRegions.size(); i++) {
       final FoldRegion region = myRegions.get(i);
       if (region.getStartOffset() > range.getEndOffset()) break;
       if (region.isValid() && intersects(region, range)) {
         return false;
       }
     }

     myRegions.add(myCachedLastIndex = index,range);
     return true;
   }

   @Nullable
   FoldRegion fetchOutermost(int offset) {
     if (!isFoldingEnabledAndUpToDate()) return null;

     final int[] starts = myCachedStartOffsets;
     final int[] ends = myCachedEndOffsets;
     if (starts == null || ends == null) {
       return null;
     }

     int start = 0;
     int end = ends.length - 1;

     while (start <= end) {
       int i = (start + end) / 2;
       if (offset < starts[i]) {
         end = i - 1;
       } else if (offset > ends[i]) {
         start = i + 1;
       }
       else {
         // We encountered situation when cached data is inconsistent. It's not clear what produced that, so, the following was done:
         //     1. Corresponding check was added and cached data is rebuilt in case of inconsistency;
         //     2. Debug asserts are activated if dedicated flag is on (it's off by default);
         if (myCachedStartOffsets[i] != myCachedTopLevelRegions[i].getStartOffset()) {
           if (DEBUG) {
             assert false :
               "inconsistent cached fold data detected. Start offsets: " + Arrays.toString(myCachedStartOffsets)
               + ", end offsets: " + Arrays.toString(myCachedEndOffsets) + ", top regions: " + Arrays.toString(myCachedTopLevelRegions)
               + ", visible regions: " + Arrays.toString(myCachedVisible);
           }
           rebuild();
           return fetchOutermost(offset);
         }
         return myCachedTopLevelRegions[i];
       }
     }

     return null;
   }

   FoldRegion[] fetchVisible() {
     if (!isFoldingEnabledAndUpToDate()) return FoldRegion.EMPTY_ARRAY;
     return myCachedVisible;
   }

   @Nullable
   FoldRegion[] fetchTopLevel() {
     if (!isFoldingEnabledAndUpToDate()) return null;
     return myCachedTopLevelRegions;
   }

   private static boolean contains(FoldRegion outer, FoldRegion inner) {
     return outer.getStartOffset() <= inner.getStartOffset() && outer.getEndOffset() >= inner.getEndOffset();
   }

   private static boolean intersects(FoldRegion r1, FoldRegion r2) {
     final int s1 = r1.getStartOffset();
     final int s2 = r2.getStartOffset();
     final int e1 = r1.getEndOffset();
     final int e2 = r2.getEndOffset();
     return s1 < s2 && s2 < e1 && e1 < e2 || s2 < s1 && s1 < e2 && e2 < e1;
   }

   static boolean contains(FoldRegion region, int offset) {
     return region.getStartOffset() < offset && region.getEndOffset() > offset;
   }

   public FoldRegion[] fetchCollapsedAt(int offset) {
     if (!isFoldingEnabledAndUpToDate()) return FoldRegion.EMPTY_ARRAY;
     ArrayList<FoldRegion> allCollapsed = new ArrayList<FoldRegion>();
     for (FoldRegion region : myRegions) {
       if (!region.isExpanded() && contains(region, offset)) {
         allCollapsed.add(region);
       }
     }

     return toFoldArray(allCollapsed);
   }

   boolean intersectsRegion(int startOffset, int endOffset) {
     if (!isFoldingEnabled()) return true;
     for (FoldRegion region : myRegions) {
       boolean contains1 = contains(region, startOffset);
       boolean contains2 = contains(region, endOffset);
       if (contains1 != contains2) {
         return true;
       }
     }
     return false;
   }

   FoldRegion[] fetchAllRegions() {
     if (!isFoldingEnabledAndUpToDate()) return FoldRegion.EMPTY_ARRAY;

     return toFoldArray(myRegions);
   }

   void removeRegion(FoldRegion range) {
     myRegions.remove(range);
   }

   int getFoldedLinesCountBefore(int offset) {
     int idx = getLastTopLevelIndexBefore(offset);
     if (idx == -1) return 0;
     return myCachedFoldedLines[idx];
   }

   public int getLastTopLevelIndexBefore(int offset) {
     int[] endOffsets = myCachedEndOffsets;
     if (!isFoldingEnabledAndUpToDate() || endOffsets == null) return -1;

     int start = 0;
     int end = endOffsets.length - 1;

     while (start <= end) {
       int i = (start + end) / 2;
       if (offset < endOffsets[i]) {
         end = i - 1;
       } else if (offset > endOffsets[i]) {
         start = i + 1;
       }
       else {
         return i;
       }
     }

     return end;
   }
 }
	/*
	* 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.Document;
	import com.intellij.openapi.editor.FoldRegion;
	import com.intellij.openapi.editor.RangeMarker;
	import com.intellij.openapi.util.TextRange;
	import com.intellij.util.ArrayUtil;
	import com.intellij.util.containers.ContainerUtil;
	import org.jetbrains.annotations.NotNull;
	import org.jetbrains.annotations.Nullable;

	import java.util.*;

	/**
	* User: cdr
	*/
	abstract class FoldRegionsTree {

	@SuppressWarnings("UseOfArchaicSystemPropertyAccessors")
	public static final boolean DEBUG = Boolean.getBoolean("idea.editor.debug.folding");

	private FoldRegion[] myCachedVisible;
	private FoldRegion[] myCachedTopLevelRegions;
	private int[] myCachedEndOffsets;
	private int[] myCachedStartOffsets;
	private int[] myCachedFoldedLines;
	int myCachedLastIndex = -1;

	//sorted using RangeMarker.BY_START_OFFSET comparator
	//i.e., first by start offset, then, if start offsets are equal, by end offset
	private ArrayList<FoldRegion> myRegions = ContainerUtil.newArrayList();

	private static final Comparator<FoldRegion> BY_END_OFFSET = new Comparator<FoldRegion>() {
	@Override
	public int compare(FoldRegion r1, FoldRegion r2) {
	int end1 = r1.getEndOffset();
	int end2 = r2.getEndOffset();
	if (end1 < end2) return -1;
	if (end1 > end2) return 1;
	return 0;
	}
	};
	private static final Comparator<? super FoldRegion> BY_END_OFFSET_REVERSE = Collections.reverseOrder(BY_END_OFFSET);

	void clear() {
	myCachedVisible = null;
	myCachedTopLevelRegions = null;
	myCachedEndOffsets = null;
	myCachedStartOffsets = null;
	myCachedFoldedLines = null;

	if (myRegions != null) {
	for (FoldRegion region : myRegions) {
	region.dispose();
	}
	}

	myRegions = new ArrayList<FoldRegion>();
	}

	private boolean isFoldingEnabledAndUpToDate() {
	return isFoldingEnabled() && myCachedVisible != null;
	}

	protected abstract boolean isFoldingEnabled();

	protected abstract boolean isBatchFoldingProcessing();

	void rebuild() {
	ArrayList<FoldRegion> topLevels = new ArrayList<FoldRegion>(myRegions.size() / 2);
	ArrayList<FoldRegion> visible = new ArrayList<FoldRegion>(myRegions.size());
	ArrayList<FoldRegion> allValid = new ArrayList<FoldRegion>(myRegions.size());
	FoldRegion[] regions = toFoldArray(myRegions);
	FoldRegion currentCollapsed = null;
	for (FoldRegion region : regions) {
	if (!region.isValid()) {
	continue;
	}

	allValid.add(region);

	if (!region.isExpanded()) {
	removeRegionsWithSameStartOffset(visible, region);
	removeRegionsWithSameStartOffset(topLevels, region);
	}

	if (currentCollapsed == null \|\| !contains(currentCollapsed, region)) {
	visible.add(region);
	if (!region.isExpanded()) {
	currentCollapsed = region;
	topLevels.add(region);
	}
	}
	}

	if (allValid.size() < myRegions.size()) {
	myRegions = allValid;
	}

	myCachedTopLevelRegions = toFoldArray(topLevels);
	myCachedVisible = toFoldArray(visible);

	Arrays.sort(myCachedTopLevelRegions, BY_END_OFFSET);
	Arrays.sort(myCachedVisible, BY_END_OFFSET_REVERSE);

	updateCachedOffsets();
	}

	private static void removeRegionsWithSameStartOffset(List<FoldRegion> regions, FoldRegion region) {
	for (int i = regions.size() - 1; i >= 0 ; i--) {
	if (regions.get(i).getStartOffset() == region.getStartOffset()) {
	regions.remove(i);
	}
	else {
	break;
	}
	}
	}

	@NotNull
	private static FoldRegion[] toFoldArray(@NotNull List<FoldRegion> topLevels) {
	return topLevels.isEmpty() ? FoldRegion.EMPTY_ARRAY : topLevels.toArray(new FoldRegion[topLevels.size()]);
	}

	void updateCachedOffsets() {
	if (!isFoldingEnabled()) {
	return;
	}
	if (myCachedVisible == null) {
	rebuild();
	return;
	}

	for (FoldRegion foldRegion : myCachedVisible) {
	if (!foldRegion.isValid()) {
	rebuild();
	return;
	}
	}

	int length = myCachedTopLevelRegions.length;
	if (myCachedEndOffsets == null \|\| myCachedEndOffsets.length != length) {
	if (length != 0) {
	myCachedEndOffsets = new int[length];
	myCachedStartOffsets = new int[length];
	myCachedFoldedLines = new int[length];
	}
	else {
	myCachedEndOffsets = ArrayUtil.EMPTY_INT_ARRAY;
	myCachedStartOffsets = ArrayUtil.EMPTY_INT_ARRAY;
	myCachedFoldedLines = ArrayUtil.EMPTY_INT_ARRAY;
	}
	}

	int sum = 0;
	for (int i = 0; i < length; i++) {
	FoldRegion region = myCachedTopLevelRegions[i];
	myCachedStartOffsets[i] = region.getStartOffset();
	myCachedEndOffsets[i] = region.getEndOffset() - 1;
	Document document = region.getDocument();
	sum += document.getLineNumber(region.getEndOffset()) - document.getLineNumber(region.getStartOffset());
	myCachedFoldedLines[i] = sum;
	}
	}

	boolean addRegion(FoldRegion range) {
	// During batchProcessing elements are inserted in ascending order,
	// binary search find acceptable insertion place first time
	boolean canUseCachedValue = false;
	if (isBatchFoldingProcessing() && myCachedLastIndex >= 0 && myCachedLastIndex < myRegions.size()) {
	FoldRegion lastRegion = myRegions.get(myCachedLastIndex);
	if (RangeMarker.BY_START_OFFSET.compare(lastRegion, range) < 0) {
	canUseCachedValue = myCachedLastIndex == (myRegions.size() - 1)
	\|\| RangeMarker.BY_START_OFFSET.compare(range, myRegions.get(myCachedLastIndex + 1)) <= 0;
	}
	}
	int index = canUseCachedValue ? myCachedLastIndex + 1 : Collections.binarySearch(myRegions, range, RangeMarker.BY_START_OFFSET);
	if (index < 0) index = -index - 1;

	if (index < myRegions.size()) {
	FoldRegion foldRegion = myRegions.get(index);
	if (TextRange.areSegmentsEqual(foldRegion, range)) {
	return false;
	}
	}

	for (int i = index - 1; i >=0; --i) {
	final FoldRegion region = myRegions.get(i);
	if (region.getEndOffset() < range.getStartOffset()) break;
	if (region.isValid() && intersects(region, range)) {
	return false;
	}
	}

	for (int i = index; i < myRegions.size(); i++) {
	final FoldRegion region = myRegions.get(i);
	if (region.getStartOffset() > range.getEndOffset()) break;
	if (region.isValid() && intersects(region, range)) {
	return false;
	}
	}

	myRegions.add(myCachedLastIndex = index,range);
	return true;
	}

	@Nullable
	FoldRegion fetchOutermost(int offset) {
	if (!isFoldingEnabledAndUpToDate()) return null;

	final int[] starts = myCachedStartOffsets;
	final int[] ends = myCachedEndOffsets;
	if (starts == null \|\| ends == null) {
	return null;
	}

	int start = 0;
	int end = ends.length - 1;

	while (start <= end) {
	int i = (start + end) / 2;
	if (offset < starts[i]) {
	end = i - 1;
	} else if (offset > ends[i]) {
	start = i + 1;
	}
	else {
	// We encountered situation when cached data is inconsistent. It's not clear what produced that, so, the following was done:
	// 1. Corresponding check was added and cached data is rebuilt in case of inconsistency;
	// 2. Debug asserts are activated if dedicated flag is on (it's off by default);
	if (myCachedStartOffsets[i] != myCachedTopLevelRegions[i].getStartOffset()) {
	if (DEBUG) {
	assert false :
	"inconsistent cached fold data detected. Start offsets: " + Arrays.toString(myCachedStartOffsets)
	+ ", end offsets: " + Arrays.toString(myCachedEndOffsets) + ", top regions: " + Arrays.toString(myCachedTopLevelRegions)
	+ ", visible regions: " + Arrays.toString(myCachedVisible);
	}
	rebuild();
	return fetchOutermost(offset);
	}
	return myCachedTopLevelRegions[i];
	}
	}

	return null;
	}

	FoldRegion[] fetchVisible() {
	if (!isFoldingEnabledAndUpToDate()) return FoldRegion.EMPTY_ARRAY;
	return myCachedVisible;
	}

	@Nullable
	FoldRegion[] fetchTopLevel() {
	if (!isFoldingEnabledAndUpToDate()) return null;
	return myCachedTopLevelRegions;
	}

	private static boolean contains(FoldRegion outer, FoldRegion inner) {
	return outer.getStartOffset() <= inner.getStartOffset() && outer.getEndOffset() >= inner.getEndOffset();
	}

	private static boolean intersects(FoldRegion r1, FoldRegion r2) {
	final int s1 = r1.getStartOffset();
	final int s2 = r2.getStartOffset();
	final int e1 = r1.getEndOffset();
	final int e2 = r2.getEndOffset();
	return s1 < s2 && s2 < e1 && e1 < e2 \|\| s2 < s1 && s1 < e2 && e2 < e1;
	}

	static boolean contains(FoldRegion region, int offset) {
	return region.getStartOffset() < offset && region.getEndOffset() > offset;
	}

	public FoldRegion[] fetchCollapsedAt(int offset) {
	if (!isFoldingEnabledAndUpToDate()) return FoldRegion.EMPTY_ARRAY;
	ArrayList<FoldRegion> allCollapsed = new ArrayList<FoldRegion>();
	for (FoldRegion region : myRegions) {
	if (!region.isExpanded() && contains(region, offset)) {
	allCollapsed.add(region);
	}
	}

	return toFoldArray(allCollapsed);
	}

	boolean intersectsRegion(int startOffset, int endOffset) {
	if (!isFoldingEnabled()) return true;
	for (FoldRegion region : myRegions) {
	boolean contains1 = contains(region, startOffset);
	boolean contains2 = contains(region, endOffset);
	if (contains1 != contains2) {
	return true;
	}
	}
	return false;
	}

	FoldRegion[] fetchAllRegions() {
	if (!isFoldingEnabledAndUpToDate()) return FoldRegion.EMPTY_ARRAY;

	return toFoldArray(myRegions);
	}

	void removeRegion(FoldRegion range) {
	myRegions.remove(range);
	}

	int getFoldedLinesCountBefore(int offset) {
	int idx = getLastTopLevelIndexBefore(offset);
	if (idx == -1) return 0;
	return myCachedFoldedLines[idx];
	}

	public int getLastTopLevelIndexBefore(int offset) {
	int[] endOffsets = myCachedEndOffsets;
	if (!isFoldingEnabledAndUpToDate() \|\| endOffsets == null) return -1;

	int start = 0;
	int end = endOffsets.length - 1;

	while (start <= end) {
	int i = (start + end) / 2;
	if (offset < endOffsets[i]) {
	end = i - 1;
	} else if (offset > endOffsets[i]) {
	start = i + 1;
	}
	else {
	return i;
	}
	}

	return end;
	}
	}