// Copyright (C) 2009 The Android Open Source Project
//
// 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.google.gerrit.client.data;

import java.util.ArrayList;
import java.util.List;

public class SparseFileContent {
  protected List<Range> ranges;
  protected int size;
  protected boolean missingNewlineAtEnd;
  private transient int lastGetRange;

  public SparseFileContent() {
    ranges = new ArrayList<Range>();
  }

  public int size() {
    return size;
  }

  public void setSize(final int s) {
    size = s;
  }

  public boolean isMissingNewlineAtEnd() {
    return missingNewlineAtEnd;
  }

  public void setMissingNewlineAtEnd(final boolean missing) {
    missingNewlineAtEnd = missing;
  }

  public String get(final int idx) {
    final String line = getLine(idx);
    if (line == null) {
      throw new ArrayIndexOutOfBoundsException(idx);
    }
    return line;
  }

  public boolean contains(final int idx) {
    return getLine(idx) != null;
  }

  private String getLine(final int idx) {
    for (int i = lastGetRange; i < ranges.size(); i++) {
      final Range r = ranges.get(i);
      if (r.contains(idx)) {
        lastGetRange = i;
        return r.get(idx);
      }
    }
    if (lastGetRange != 0) {
      lastGetRange = 0;
      return getLine(idx);
    }
    return null;
  }

  public void addLine(final int i, final String content) {
    final Range r;
    if (!ranges.isEmpty() && i == last().end()) {
      r = last();
    } else {
      r = new Range(i);
      ranges.add(r);
    }
    r.lines.add(content);
  }

  private Range last() {
    return ranges.get(ranges.size() - 1);
  }

  static class Range {
    protected int base;
    protected List<String> lines;

    private Range(final int b) {
      base = b;
      lines = new ArrayList<String>();
    }

    protected Range() {
    }

    private String get(final int i) {
      return lines.get(i - base);
    }

    private int end() {
      return base + lines.size();
    }

    private boolean contains(final int i) {
      return base <= i && i < end();
    }
  }
}

@@ -822,16 +822,17 @@
 eAtEnd;%0A
+%0A
   privat
@@ -847,28 +847,31 @@
 ent int 
-lastGe
+curren
 tRange
+Idx
 ;%0A%0A  pub
@@ -1531,57 +1531,191 @@
     
-for (int i = lastGetRange; i %3C ranges.size(); i++
+// Most requests are sequential in nature, fetching the next%0A    // line from the current range, or the next range.%0A    //%0A    int high = ranges.size();%0A    if (currentRangeIdx %3C high
 ) %7B%0A
@@ -1720,28 +1720,24 @@
 %7B%0A      
-final 
 Range 
+cu
 r = rang
@@ -1743,17 +1743,31 @@
 ges.get(
-i
+currentRangeIdx
 );%0A     
@@ -1771,16 +1771,18 @@
     if (
+cu
 r.contai
@@ -1804,34 +1804,175 @@
     
-lastGetRange = i;%0A
+return cur.get(idx);%0A      %7D%0A%0A      if (++currentRangeIdx %3C high) %7B%0A        final Range next = ranges.get(currentRangeIdx);%0A        if (next.contains(idx)) %7B%0A 
         
 retu
@@ -1967,24 +1967,28 @@
         
+ 
 return 
-r
+next
 .get(idx
@@ -1992,26 +1992,30 @@
 idx);%0A      
-%7D%0A
+  %7D%0A  
     %7D%0A    if
@@ -2016,63 +2016,262 @@
     
-if (lastGetRange != 0) %7B%0A      lastGetRange = 0
+%7D%0A%0A    // Binary search for the range, since we know its a sorted list.%0A    //%0A    int low = 0;%0A    do %7B%0A      final int mid = (low + high) / 2;%0A      final Range cur = ranges.get(mid);%0A      if (cur.contains(idx)) %7B%0A        currentRangeIdx = mid
 ;%0A      
 retu
@@ -2270,34 +2270,144 @@
     
+ 
+ 
 return 
-getLine(idx);%0A    %7D
+cur.get(idx);%0A      %7D%0A      if (cur.base %3C idx)%0A        high = mid;%0A      else%0A        low = mid + 1;%0A    %7D while (low %3C high);
 %0A   

Use binary search when pulling lines from SparseFileContent