// Copyright 2011 Google Inc. All Rights Reserved.
//
// 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.hughes.util;

import java.util.AbstractList;
import java.util.List;
import java.util.RandomAccess;

public class CachingList<T> extends AbstractList<T> implements RandomAccess {

    private final List<T> list;
    private final ChunkedList<T> chunked;
    private final int size;

    private final LRUCacheMap<Integer, T> cache;

    public CachingList(final List<T> list, final int cacheSize) {
        this.list = list;
        // Use chunked interface if available and chunk size is
        // reasonable. Limits are pure guesswork.
        if (list instanceof ChunkedList &&
                ((ChunkedList<T>)list).getMaxChunkSize() > 1 &&
                ((ChunkedList<T>)list).getMaxChunkSize() < cacheSize / 16) {
            chunked = (ChunkedList<T>)list;
        } else {
            chunked = null;
        }
        size = list.size();
        cache = new LRUCacheMap<Integer, T>(cacheSize);
    }

    public static <T> CachingList<T> create(final List<T> list, final int cacheSize) {
        return new CachingList<T>(list, cacheSize);
    }

    public static <T> CachingList<T> createFullyCached(final List<T> list) {
        return new CachingList<T>(list, list.size());
    }

    @Override
    public T get(int i) {
        T t = cache.get(i);
        if (t == null) {
            if (chunked != null) {
                int start = chunked.getChunkStart(i);
                List<T> chunk = chunked.getChunk(start);
                for (int idx = 0; idx < chunk.size(); ++idx) {
                    cache.put(start + idx, chunk.get(idx));
                }
                t = chunk.get(i - start);
            } else {
                t = list.get(i);
                cache.put(i, t);
            }
        }
        return t;
    }

    @Override
    public int size() {
        return size;
    }

}

@@ -919,24 +919,82 @@
 nt size;%0D%0A%0D%0A
+    private final LRUCacheMap%3CInteger, T%3E prefetchCache;%0D%0A
     private 
@@ -1471,24 +1471,164 @@
 t%3CT%3E)list;%0D%0A
+            assert 2 * chunked.getMaxChunkSize() %3C cacheSize / 4;%0D%0A            prefetchCache = new LRUCacheMap%3CInteger, T%3E(cacheSize / 4);%0D%0A
         %7D el
@@ -1662,16 +1662,51 @@
  null;%0D%0A
+            prefetchCache = null;%0D%0A
         
@@ -2220,32 +2220,113 @@
 ked != null) %7B%0D%0A
+                t = prefetchCache.get(i);%0D%0A                if (t == null) %7B%0D%0A    
                 
@@ -2360,24 +2360,28 @@
 kStart(i);%0D%0A
+    
             
@@ -2442,16 +2442,20 @@
         
+   
+ 
 for (int
@@ -2506,33 +2506,45 @@
                 
-c
+    prefetchC
 ache.put(start +
@@ -2575,35 +2575,43 @@
                 
+   
+ 
 %7D%0D%0A
+    
                 
@@ -2629,32 +2629,51 @@
 et(i - start);%0D%0A
+                %7D%0D%0A
             %7D el
@@ -2708,32 +2708,43 @@
 st.get(i);%0D%0A    
+        %7D%0D%0A
             cach
@@ -2753,39 +2753,24 @@
 put(i, t);%0D%0A
-            %7D%0D%0A
         %7D%0D%0A 

Make caching 2-stage.