java/com/google/gerrit/prettify/common/SparseFileContent.java

// 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.prettify.common;

import com.google.auto.value.AutoValue;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.ImmutableList;

/**
 * A class to store subset of a file's lines in a memory efficient way. Internally, it stores lines
 * as a list of ranges. Each range represents continuous set of lines and has information about line
 * numbers in original file (zero-based).
 *
 * <p>{@link SparseFileContent.Accessor} must be used to work with the stored content.
 */
@AutoValue
public abstract class SparseFileContent {
  abstract ImmutableList<Range> getRanges();

  public abstract int getSize();

  public static SparseFileContent create(ImmutableList<Range> ranges, int size) {
    return new AutoValue_SparseFileContent(ranges, size);
  }

  @VisibleForTesting
  public int getRangesCount() {
    return getRanges().size();
  }

  public Accessor createAccessor() {
    return new Accessor(this);
  }

  /**
   * Provide a methods to work with the content of a {@link SparseFileContent}.
   *
   * <p>The class hides internal representation of a {@link SparseFileContent} and provides
   * convenient way for accessing a content.
   */
  public static class Accessor {
    private final SparseFileContent content;
    private int currentRangeIdx;

    private Accessor(SparseFileContent content) {
      this.content = content;
    }

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

    public int getSize() {
      return content.getSize();
    }

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

    public int first() {
      return content.getRanges().isEmpty() ? getSize() : content.getRanges().get(0).getBase();
    }

    public int next(int idx) {
      // Most requests are sequential in nature, fetching the next
      // line from the current range, or the immediate next range.
      //
      ImmutableList<Range> ranges = content.getRanges();
      int high = ranges.size();
      if (currentRangeIdx < high) {
        Range cur = ranges.get(currentRangeIdx);
        if (cur.contains(idx + 1)) {
          return idx + 1;
        }

        if (++currentRangeIdx < high) {
          // Its not plus one, its the base of the next range.
          //
          return ranges.get(currentRangeIdx).getBase();
        }
      }

      // Binary search for the current value, since we know its a sorted list.
      //
      int low = 0;
      do {
        final int mid = (low + high) / 2;
        final Range cur = ranges.get(mid);

        if (cur.contains(idx)) {
          if (cur.contains(idx + 1)) {
            // Trivial plus one case above failed due to wrong currentRangeIdx.
            // Reset the cache so we don't miss in the future.
            //
            currentRangeIdx = mid;
            return idx + 1;
          }

          if (mid + 1 < ranges.size()) {
            // Its the base of the next range.
            currentRangeIdx = mid + 1;
            return ranges.get(currentRangeIdx).getBase();
          }

          // No more lines in the file.
          //
          return getSize();
        }

        if (idx < cur.getBase()) {
          high = mid;
        } else {
          low = mid + 1;
        }
      } while (low < high);

      return getSize();
    }

    private String getLine(int idx) {
      // Most requests are sequential in nature, fetching the next
      // line from the current range, or the next range.
      //
      ImmutableList<Range> ranges = content.getRanges();
      int high = ranges.size();
      if (currentRangeIdx < high) {
        Range cur = ranges.get(currentRangeIdx);
        if (cur.contains(idx)) {
          return cur.get(idx);
        }

        if (++currentRangeIdx < high) {
          final Range next = ranges.get(currentRangeIdx);
          if (next.contains(idx)) {
            return next.get(idx);
          }
        }
      }

      // Binary search for the range, since we know its a sorted list.
      //
      if (ranges.isEmpty()) {
        return null;
      }

      int low = 0;
      do {
        final int mid = (low + high) / 2;
        final Range cur = ranges.get(mid);
        if (cur.contains(idx)) {
          currentRangeIdx = mid;
          return cur.get(idx);
        }
        if (idx < cur.getBase()) {
          high = mid;
        } else {
          low = mid + 1;
        }
      } while (low < high);
      return null;
    }
  }

  @Override
  public final String toString() {
    final StringBuilder b = new StringBuilder();
    b.append("SparseFileContent[\n");
    for (Range r : getRanges()) {
      b.append("  ");
      b.append(r.toString());
      b.append('\n');
    }
    b.append("]");
    return b.toString();
  }

  @AutoValue
  abstract static class Range {
    static Range create(int base, ImmutableList<String> lines) {
      return new AutoValue_SparseFileContent_Range(base, lines);
    }

    abstract int getBase();

    abstract ImmutableList<String> getLines();

    private String get(int i) {
      return getLines().get(i - getBase());
    }

    private int end() {
      return getBase() + getLines().size();
    }

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

    @Override
    public final String toString() {
      // Usage of [ and ) is intentional to denote inclusive/exclusive range
      return "Range[" + getBase() + "," + end() + ")";
    }
  }
}