Alternative algorithm (from Twitter) #5
Description
Hi @mattrothenberg, as mentioned on Twitter, I started out with this lib as a foundation, but went with a different algorithm, this is how my version currently looks in case you want to borrow any of the approach. It's not a drop-in replacement, as i've stripped out some functionality I wasn't using, and there's some coupling to MUI, but may still be useful:
import {
useState,
useRef,
useLayoutEffect,
ReactNode,
ComponentProps,
} from 'react';
import useEffectEventShim from '../hooks/useEffectEvent';
import { useResizeDetector } from 'react-resize-detector';
import { Stack } from '@mui/material';
/**
* Returns a function that will schedule a layout effect to run on the next
* render.
*/
function useScheduleLayoutEffect() {
const [s, ss] = useState<object>();
const fns = useRef(new Map<string | number, () => void>());
useLayoutEffect(() => {
const fnCopy = Array.from(fns.current.values());
fns.current = new Map();
fnCopy.forEach((f) => f());
}, [s]);
return (id: string | number, cb: () => void) => {
fns.current.set(id, cb);
ss({});
};
}
export interface OverflowListProps<T> extends ComponentProps<typeof Stack> {
items: Array<T>;
itemRenderer: (item: T, numShown: number, index: number) => ReactNode;
overflowRenderer: (args: {
items: Array<T>;
overflownItems: Array<T>;
}) => ReactNode;
minVisibleItems?: number;
alwaysRenderOverflow?: boolean;
}
export default function OverflowList<T>({
items,
minVisibleItems = 0,
alwaysRenderOverflow = false,
overflowRenderer,
itemRenderer,
...stackProps
}: OverflowListProps<T>) {
const [numVisible, setNumVisible] = useState(items.length);
const hasHiddenItems = items.length > numVisible;
const schedule = useScheduleLayoutEffect();
const spacer = useRef<HTMLDivElement>(null);
useLayoutEffect(() => {
setNumVisible(items.length);
// eslint-disable-next-line react-hooks/exhaustive-deps
}, [JSON.stringify(items)]);
const maybeOverflow =
hasHiddenItems || alwaysRenderOverflow
? overflowRenderer({
items,
overflownItems: items.slice(numVisible),
})
: null;
const containerSize = useResizeDetector();
const bisect = useEffectEventShim(
(
low: number,
high: number,
path: Array<{ index: number; result: 'over' | 'under' }>
) => {
let mid = Math.floor(low + (high - low) / 2);
if (high - low === 1) {
if (path.find((p) => p.index === high)) {
mid = low;
} else {
mid = high;
}
}
if (path.find((p) => p.index === mid)) {
const pathEntry = path.findLast((p) => p.result === 'under');
if (pathEntry) {
setNumVisible(
pathEntry.index < minVisibleItems
? minVisibleItems
: pathEntry.index
);
}
return;
}
setNumVisible(mid < minVisibleItems ? minVisibleItems : mid);
schedule('recur', () => {
const spacerWidth = spacer.current?.getBoundingClientRect().width ?? 1;
if (spacerWidth > 1) {
path.push({ index: mid, result: 'under' });
bisect(mid, high, path);
} else if (spacerWidth < 1) {
path.push({ index: mid, result: 'over' });
bisect(low, mid, path);
}
});
}
);
useLayoutEffect(() => {
bisect(0, items.length, []);
// eslint-disable-next-line react-hooks/exhaustive-deps
}, [containerSize.width, JSON.stringify(items)]);
return (
<Stack
flexDirection="row"
flexWrap="nowrap"
width="100%"
minWidth={0}
ref={containerSize.ref}
{...stackProps}
>
{items.length > 0 ? (
<>
{items
.slice(0, numVisible)
.map((item, index) => itemRenderer(item, numVisible, index))}
{maybeOverflow}
<div
style={{ flexShrink: 1, width: 1, flexGrow: 1 }}
ref={spacer}
data-spacer
/>
</>
) : null}
</Stack>
);
}The logic itself is probably a bit messy, i've been grappling with getting this right, so this is just the first version that worked well. But the basic premise is to bisect the list, check if we're underflowing or overflowing, and recurse until we find the solution (with some gnarly edge case handling). It uses a scheduled layout effect trick to allow use to measure the layout after each recursion. Obviously, multiple sync layouts aren't great, but it's O(log n), so it should end up being tolerable fast.