platform/util/src/com/intellij/util/containers/CircularCharBuffer.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.util.containers;
  17
  18 import com.intellij.util.ArrayUtil;
  19 import org.jetbrains.annotations.NotNull;
  20
  21 /**
  22  * A single threaded, resizable, circular char queue backed by an array.
  23  */
  24 public class CircularCharBuffer {
  25
  26   private char[] myArray;
  27   private final int myMaxCapacity;
  28   private int mySize;
  29   private int myTail;
  30   private int myHead;
  31
  32   public CircularCharBuffer(int initialCapacity) {
  33     this(initialCapacity, -1);
  34   }
  35
  36   public CircularCharBuffer(int initialCapacity, int maxCapacity) {
  37     assert maxCapacity < 0 || initialCapacity <= maxCapacity;
  38     myArray = new char[initialCapacity];
  39     myMaxCapacity = maxCapacity;
  40     mySize = 0;
  41     myTail = 0;
  42     myHead = 0;
  43   }
  44
  45   public void add(char c) {
  46     resizeIfNeeded(mySize + 1);
  47     doAdd(c);
  48   }
  49
  50   public void add(char[] buffer) {
  51     resizeIfNeeded(mySize + buffer.length);
  52     for (char c : buffer) {
  53       doAdd(c);
  54     }
  55   }
  56
  57   public void add(@NotNull String str) {
  58     resizeIfNeeded(mySize + str.length());
  59     for (int i = 0; i < str.length(); i++) {
  60       doAdd(str.charAt(i));
  61     }
  62   }
  63
  64   private void doAdd(char c) {
  65     myArray[myTail] = c;
  66     myTail++;
  67     int length = myArray.length;
  68     if (myTail >= length) {
  69       myTail = 0;
  70     }
  71     mySize++;
  72     if (mySize > length) {
  73       doPoll();
  74     }
  75   }
  76
  77   public int poll() {
  78     return doPoll();
  79   }
  80
  81   public int doPoll() {
  82     if (mySize == 0) {
  83       return -1;
  84     }
  85     char res = myArray[myHead];
  86     myHead++;
  87     if (myHead >= myArray.length) {
  88       myHead = 0;
  89     }
  90     mySize--;
  91     return res;
  92   }
  93
  94   @NotNull
  95   public String getText() {
  96     normalize();
  97     return new String(myArray, 0, mySize);
  98   }
  99
 100   public boolean isEmpty() {
 101     return mySize == 0;
 102   }
 103
 104   public int size() {
 105     return mySize;
 106   }
 107
 108   private boolean resizeIfNeeded(int newSize) {
 109     int length = myArray.length;
 110     if (newSize <= length) {
 111       return true;
 112     }
 113     if (myMaxCapacity > -1 && length == myMaxCapacity) {
 114       return false;
 115     }
 116     normalize();
 117     int newLength = Math.max(length << 1, newSize);
 118     if (myMaxCapacity > -1) {
 119       newLength = Math.min(myMaxCapacity, newLength);
 120     }
 121     char[] newArray = new char[newLength];
 122     System.arraycopy(myArray, myHead, newArray, 0, mySize);
 123     myArray = newArray;
 124     myTail = mySize % newArray.length;
 125     return true;
 126   }
 127
 128   /**
 129    * Updates internal data to make sure {@code myHead} points to zero index of {@code myArray}.
 130    * As a result of this operation there will be no visible changes to clients.
 131    */
 132   private void normalize() {
 133     if (myHead == 0) {
 134       return;
 135     }
 136     int length = myArray.length;
 137     if (myHead < myTail) {
 138       moveSubArrayLeft(myArray, myHead, mySize, myHead);
 139     }
 140     else {
 141       int headSize = myTail;
 142       int tailSize = length - myHead;
 143       reverseSubArray(myArray, 0, headSize);
 144       reverseSubArray(myArray, length - tailSize, tailSize);
 145       reverseSubArray(myArray, 0, length);
 146       moveSubArrayLeft(myArray, length - headSize, headSize, length - headSize - tailSize);
 147     }
 148     myHead = 0;
 149     myTail = mySize % length;
 150   }
 151
 152   private static void moveSubArrayLeft(char[] array, int startInd, int length, int moveLeftCount) {
 153     //noinspection ManualArrayCopy
 154     for (int i = startInd; i < startInd + length; i++) {
 155       array[i - moveLeftCount] = array[i];
 156     }
 157   }
 158
 159   private static void reverseSubArray(char[] array, int startInd, int length) {
 160     for (int i = 0; i < length / 2; i++) {
 161       ArrayUtil.swap(array, startInd + i, startInd + length - 1 - i);
 162     }
 163   }
 164 }