Virtual window

/**
 * Which rows of a long list to draw: those in view, and a few beyond so that a
 * scroll reveals rows already there. A million rows cost the same to show as
 * forty.
 *
 * Rows of one size need only arithmetic. Rows of differing sizes are answered
 * by a Fenwick tree over their sizes (see `algorithms/fenwick.ts`).
 *
 * A browser will not lay out an element beyond a certain height — some tens of
 * millions of pixels, differing by engine — and a list longer than that cannot
 * be scrolled to its end. So a list is never made taller than `SCROLL_LIMIT`:
 * past it, the scroll position is a proportion of the way through, and each
 * pixel scrolled moves through more than a pixel of the list.
 */
import { fenwickFind, fenwickPrefix } from "./fenwick.ts";

export interface VirtualWindow {
  /** The first row to draw, and one past the last. */
  readonly first: number;
  readonly end: number;
  /** Where the first drawn row starts, from the top of the list. */
  readonly offset: number;
  /** The size of the whole list. */
  readonly size: number;
}

/** The window over `count` rows that are each `rowSize` tall. */
export function fixedWindow(
  count: number,
  rowSize: number,
  scrollOffset: number,
  viewportSize: number,
  overscan = 4,
): VirtualWindow {
  const first = Math.max(Math.floor(scrollOffset / rowSize) - overscan, 0);
  const end = Math.min(Math.ceil((scrollOffset + viewportSize) / rowSize) + overscan, count);
  return { first: Math.min(first, end), end, offset: Math.min(first, end) * rowSize, size: count * rowSize };
}

/** The window over rows whose sizes are held in a Fenwick tree. */
export function variableWindow(
  sizes: Float64Array,
  scrollOffset: number,
  viewportSize: number,
  overscan = 4,
): VirtualWindow {
  const count = sizes.length - 1;
  const first = Math.max(fenwickFind(sizes, Math.max(scrollOffset, 0)) - overscan, 0);
  const end = Math.min(fenwickFind(sizes, Math.max(scrollOffset + viewportSize, 0)) + 1 + overscan, count);
  const start = Math.min(first, end);
  return { first: start, end, offset: fenwickPrefix(sizes, start), size: fenwickPrefix(sizes, count) };
}

/**
 * The scroll offset that brings a row into view by the least movement: unchanged
 * if it is in view, else just far enough to show it at the nearer edge.
 */
export function scrollToReveal(
  start: number,
  size: number,
  scrollOffset: number,
  viewportSize: number,
): number {
  if (start < scrollOffset) return start;
  if (start + size > scrollOffset + viewportSize) return start + size - viewportSize;
  return scrollOffset;
}

/**
 * No scrolling element is made taller than this: within every engine's limit,
 * the lowest of which — Firefox's — is a little under nine million pixels.
 */
export const SCROLL_LIMIT = 5_000_000;

/** The height to give a scrolling element for a list of `size`. */
export function scrollSize(size: number, limit = SCROLL_LIMIT): number {
  return Math.min(size, limit);
}

/**
 * How far through a list of `size` a scroll position is, where the scrolling
 * element is `scrollSize(size)` tall. The same number until the list passes the
 * limit; a proportion beyond it, so that the last pixel scrolled is the list's end.
 */
export function listOffset(
  scrollOffset: number,
  size: number,
  viewportSize: number,
  limit = SCROLL_LIMIT,
): number {
  if (size <= limit) return scrollOffset;
  const scrollable = limit - viewportSize;
  if (scrollable <= 0) return 0;
  return Math.min(Math.max(scrollOffset / scrollable, 0), 1) * (size - viewportSize);
}

/** The scroll position that shows `listOffset`: the inverse of the above. */
export function scrollOffsetFor(
  offset: number,
  size: number,
  viewportSize: number,
  limit = SCROLL_LIMIT,
): number {
  if (size <= limit) return offset;
  const scrollable = size - viewportSize;
  if (scrollable <= 0) return 0;
  return Math.min(Math.max(offset / scrollable, 0), 1) * (limit - viewportSize);
}