platform/util/src/com/intellij/util/containers/CharArrayQueue.java

   1 /*
   2  * Copyright 2000-2013 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 org.jetbrains.annotations.NotNull;
  19
  20 /**
  21  * A single threaded, resizable, circular char queue backed by an array.
  22  *
  23  * @author Sergey Simonchik
  24  */
  25 public class CharArrayQueue {
  26
  27   private char[] myArray;
  28   private int mySize;
  29   private int myTail;
  30   private int myHead;
  31
  32   public CharArrayQueue(int initialCapacity) {
  33     myArray = new char[initialCapacity];
  34     mySize = 0;
  35     myTail = 0;
  36     myHead = 0;
  37   }
  38
  39   public void add(char c) {
  40     resizeIfNeeded(mySize + 1);
  41     doAdd(c);
  42   }
  43
  44   public void addAll(char[] buffer) {
  45     resizeIfNeeded(mySize + buffer.length);
  46     for (char c : buffer) {
  47       doAdd(c);
  48     }
  49   }
  50
  51   public void add(@NotNull String str) {
  52     resizeIfNeeded(mySize + str.length());
  53     for (int i = 0; i < str.length(); i++) {
  54       doAdd(str.charAt(i));
  55     }
  56   }
  57
  58   private void doAdd(char c) {
  59     myArray[myTail] = c;
  60     myTail++;
  61     if (myTail >= myArray.length) {
  62       myTail = 0;
  63     }
  64     mySize++;
  65   }
  66
  67   public int poll() {
  68     if (mySize == 0) {
  69       return -1;
  70     }
  71     char res = myArray[myHead];
  72     myHead++;
  73     if (myHead >= myArray.length) {
  74       myHead = 0;
  75     }
  76     mySize--;
  77     return res;
  78   }
  79
  80   public boolean isEmpty() {
  81     return mySize == 0;
  82   }
  83
  84   public int size() {
  85     return mySize;
  86   }
  87
  88   private void resizeIfNeeded(int newSize) {
  89     int len = myArray.length;
  90     if (newSize > len) {
  91       char[] newArray = new char[Math.max(len << 1, newSize)];
  92       if (myHead < myTail) {
  93         System.arraycopy(myArray, myHead, newArray, 0, myTail - myHead);
  94       }
  95       else {
  96         System.arraycopy(myArray, myHead, newArray, 0, len - myHead);
  97         System.arraycopy(myArray, 0, newArray, len - myHead, myTail);
  98       }
  99       myArray = newArray;
 100       myHead = 0;
 101       myTail = mySize;
 102     }
 103   }
 104
 105 }