title: Cache Implemented Using an Array - ArrayIndexOutOfBoundsException (Java)
body: <p>I simulate a web cache replacement algorithm. I have N objects of type Request available for caching and L requests for those objects that arrive to the cache in a serial fashion. </p>
  
  <p>Request objects are distinguished by their int field reqID (a numeric ID from 0 up to N-1). I have override equals to be able to compare Request objects.</p>
  
  <p>I implement a cache using an array - a simple, plain, static array.</p>
  
  <p>The cache is filled with objects of type Request and has a max size M:</p>
  
  <pre><code>/** Max cache size */
  private int M;
  
  /** Cache */
  private Request[] cache = new Request[M];
  </code></pre>
  
  <p>I have insertions, evictions and replacements of objects in the cache. </p>
  
  <p>I have also a sliding window of the last K requests implemented as an ArrayDeque:</p>
  
  <pre><code>/** Max window size */
  private int K;
  
  /** Window */
  private Deque&lt;Request&gt; window = new ArrayDeque&lt;Request&gt;(K);
  </code></pre>
  
  <p>Values M and K are initialized at the constructor and set at main().</p>
  
  <p>I keep the score (request count in a sliding window of last K requests) of the objects in a HashMap:</p>
  
  <pre><code>/** Map of reqID (K) - Score (V) */
  Map&lt;Integer, Integer&gt; score;
  </code></pre>
  
  <p>I keep the cache ordered in terms of the score of the cached items, with the highest score being at the left end and the lowest score being at the right end.</p>
  
  <p>Due to the fact that when I have a cache hit for an item its score is increased by 1 while when I have a request for an item dropped from the window the score of that item is decreased by 1, in those cases I might have cache reordering with the relevant item exchanging position in the cache with the next item at its left or right, respectively. Therefore, I should be able to know the index of each (random) item in the cache at any given time. For that purpose, I use an integer field called counter and a HashMap called positions:</p>
  
  <pre><code>/** Counter = position in the cache */
  private int counter;
  
  /** Map of ReqID (K) - Counter (V) */
  private Map&lt;Integer, Integer&gt; positions;
  </code></pre>
  
  <p>Finally, I use an inCache map in order to avoid the "for loop" in lookup operation:</p>
  
  <pre><code>/** Map with boolean flags to check whether an item (ReqID) is in cache or not */
  private Map&lt;Integer, Boolean&gt; inCache;
  </code></pre>
  
  <p>and an isMoreThanOne flag to avoid calling the getter for the current cache size when this size is large:</p>
  
  <pre><code>/** Flag for more than 1 items in cache */
  private boolean isMoreThanOne;
  </code></pre>
  
  <p>The reason is that, since my cache is a vanilla array and not an ArrayList, it does not have a size() method, and length field is the fixed capacity given, not the current cache size. Therefore, in order to get the current cache size, I should do the following (please take a look since I am not 100% if it is correct):</p>
  
  <pre><code>/**
   * Getter for current cache size
   * @return  Current cache size
   */
  public int getCacheSize() {
  
      // temp counter
  int count = 0;
  
  // scan the cache
  for(int i = 0; i &lt; this.cache.length; i++) {
  
      // as long as the items are not null
      if(this.cache[i] != null) {
  
          // increase the counter by 1
      count += 1;
  
      }
  
      // when the first null item found
      else {
  
          // jump out of the loop
      break;
  
      }
  
  }
  
  // return the current cache size (counter)
  return count;
  }
  </code></pre>
  
  <p>After that long but neccessary introduction, here is the code of cache insertion where I get an ArrayIndexOutOfBoundsException:</p>
  
  <pre><code>/**
   * Cache insertion operation
   * @param request   The requested item that is inserted into the cache
   */
  public void doCacheInsert(Request request) {
  
      // if this is the first item inserted into the cache
  if(getCacheSize() == 0) {
  
      // set counter
      counter = M-1;
  
      // insert item at index counter
      this.cache[counter] = request;    // HERE I HAVE THE MESSAGE
  
      // put position index into positions list
      this.positions.put(request.reqID, counter);
  
  }
  
  // if this is not the first item inserted into the cache
  else {
  
      //if the cache has not reached its max size
      if(getCacheSize() != this.cacheWindowLFU.length) {
  
          // decrease counter by 1
      counter -= 1;
  
      // insert item at index counter
      this.cache[counter] = request;
  
      // put position index into positions list
      this.positions.put(request.reqID, counter);
  
      // set isMoreThanOne flag
      isMoreThanOne = true;
  
      }
  
      // if the cache has reached its max size
      else {
  
          // reset counter to M-1
      counter = M-1;
  
      // insert item at index counter
      this.cache[counter] = request;
  
      }
  
  }
  
  // activate flag for item in inCache map
  this.inCache.put(request.reqID, true);
  
  }
  </code></pre>
  
  <p>I get the message almost right at the beginning of this method, at the 1st if block at the line:</p>
  
  <pre><code>// insert item at index counter
  this.cache[counter] = request;
  </code></pre>
  
  <p>... and I really don't know why!</p>
  
  <p>EDIT: Here is my constructor:</p>
  
  <pre><code>/**
   * Constructor
   * @param M Max cache size
   * @param K Max window size
   * @param N Number of items
  */
  public Algorithm(int M, int K, int N) {
  
      // initialize max cache size and max window size
  this.M = M;
  this.K = K;
  
  // initialize counter
  counter = 0;
  
  // initialize isMoreThanOne flag
  isMoreThanOne = false;
  
  // allocate inCache, winFreqs, and positions maps
  inCache     = new HashMap&lt;Integer, Boolean&gt;(N);
  scores          = new HashMap&lt;Integer, Integer&gt;(N);
  positions   = new HashMap&lt;Integer, Integer&gt;(N);
  
  }
  </code></pre>
  
  <p>And here is the relevant part of main() which is inside Main class:</p>
  
  <pre><code>// stuff..... (e.g. # of sim runs etc.)
  
  // number of items
  int numItems = 20;
  
  // number of requests
  int numR = 40;
  
  // maximum cache size
  int M = 5;
  
  // maximum window size
  int K = 3;
  
  // stuff...... (e.g. generation of requests, start of statistics etc.)
  
  // instantianate object of type Algorithm
  Algorithm alg = new Algorithm(M, K, numItems);
  
  // stuff..... (e.g. lookup, insertion, replacement, # of hits, hit rate etc.)    
  </code></pre>