awesome-uiwidgets/AwesomeUIWidgets/Assets/Packages/SGrid/render/sliver_staggered_grid.cs

using System.Collections.Generic;
using System.Linq;
using Unity.UIWidgets.external;
using Unity.UIWidgets.foundation;
using Unity.UIWidgets.painting;
using Unity.UIWidgets.rendering;
using Unity.UIWidgets.ui;
using Unity.UIWidgets.widgets;
using UnityEngine;

public static class GridUtil
{
    public delegate StaggeredTile IndexedStaggeredTileBuilder(int index);

    internal const float _epsilon = 0.0001f;

    internal static bool _nearEqual(float d1, float d2)
    {
        return (d1 - d2).abs() < _epsilon;
    }
}

public class StaggeredGridConfiguration
{
    public StaggeredGridConfiguration(
        int crossAxisCount,
        GridUtil.IndexedStaggeredTileBuilder staggeredTileBuilder,
        float cellExtent,
        float mainAxisSpacing,
        float crossAxisSpacing,
        bool reverseCrossAxis,
        int? staggeredTileCount,
        int mainAxisOffsetsCacheSize = 3
    )
    {
        D.assert(crossAxisCount > 0);
        D.assert(cellExtent >= 0);
        D.assert(mainAxisSpacing >= 0);
        D.assert(crossAxisSpacing >= 0);
        D.assert(mainAxisOffsetsCacheSize > 0);
        this.crossAxisCount = crossAxisCount;
        this.staggeredTileBuilder = staggeredTileBuilder;
        this.cellExtent = cellExtent;
        this.mainAxisSpacing = mainAxisSpacing;
        this.crossAxisSpacing = crossAxisSpacing;
        this.reverseCrossAxis = reverseCrossAxis;
        this.staggeredTileCount = staggeredTileCount;
        this.mainAxisOffsetsCacheSize = mainAxisOffsetsCacheSize;
        cellStride = cellExtent + crossAxisSpacing;
    }

    public readonly int crossAxisCount;

    public readonly float cellExtent;

    public readonly float mainAxisSpacing;

    public readonly float crossAxisSpacing;

    public readonly GridUtil.IndexedStaggeredTileBuilder staggeredTileBuilder;

    public readonly int? staggeredTileCount;

    public readonly bool reverseCrossAxis;

    public readonly float cellStride;

    public readonly int mainAxisOffsetsCacheSize;

    public List<float> generateMainAxisOffsets()
    {
        return Enumerable.Repeat(0.0f, crossAxisCount).ToList();
    }

    public StaggeredTile getStaggeredTile(int index)
    {
        StaggeredTile tile = null;
        if (staggeredTileCount == null || index < staggeredTileCount)
        {
            // There is maybe a tile for this index.
            tile = _normalizeStaggeredTile(staggeredTileBuilder(index));
        }

        return tile;
    }

    float _getStaggeredTileMainAxisExtent(StaggeredTile tile)
    {
        if (tile.mainAxisCellCount != null)
        {
            return (float) (tile.mainAxisExtent ??
                            (tile.mainAxisCellCount * cellExtent) +
                            (tile.mainAxisCellCount - 1) * mainAxisSpacing);
        }

        return 0;
    }

    StaggeredTile _normalizeStaggeredTile(StaggeredTile staggeredTile)
    {
        if (staggeredTile == null)
        {
            return null;
        }
        else
        {
            var crossAxisCellCount =
                staggeredTile.crossAxisCellCount.clamp(0, crossAxisCount);
            if (staggeredTile.fitContent)
            {
                return StaggeredTile.fit(crossAxisCellCount);
            }
            else
            {
                return StaggeredTile.extent(
                    crossAxisCellCount, _getStaggeredTileMainAxisExtent(staggeredTile));
            }
        }
    }
}

internal class _Block
{
    internal _Block(
        int index,
        int crossAxisCount,
        float minOffset,
        float maxOffset
    )
    {
        this.index = index;
        this.crossAxisCount = crossAxisCount;
        this.minOffset = minOffset;
        this.maxOffset = maxOffset;
    }

    public readonly int index;
    public readonly int crossAxisCount;
    public readonly float minOffset;
    public readonly float maxOffset;
}

public class SliverStaggeredGridGeometry
{
    public SliverStaggeredGridGeometry(
        float scrollOffset,
        float crossAxisOffset,
        float? mainAxisExtent,
        float crossAxisExtent,
        int crossAxisCellCount,
        int blockIndex
    )
    {
        this.scrollOffset = scrollOffset;
        this.crossAxisOffset = crossAxisOffset;
        this.mainAxisExtent = mainAxisExtent;
        this.crossAxisExtent = crossAxisExtent;
        this.crossAxisCellCount = crossAxisCellCount;
        this.blockIndex = blockIndex;
    }

    public readonly float scrollOffset;

    public readonly float crossAxisOffset;

    public readonly float? mainAxisExtent;

    public readonly float crossAxisExtent;

    public readonly int crossAxisCellCount;

    public readonly int blockIndex;

    public bool hasTrailingScrollOffset
    {
        get { return mainAxisExtent != null; }
    }

    public float trailingScrollOffset
    {
        get { return scrollOffset + (mainAxisExtent ?? 0); }
    }

    public SliverStaggeredGridGeometry copyWith(
        float? scrollOffset = null,
        float? crossAxisOffset = null,
        float? mainAxisExtent = null,
        float? crossAxisExtent = null,
        int? crossAxisCellCount = null,
        int? blockIndex = null
    )
    {
        return new SliverStaggeredGridGeometry(
            scrollOffset: scrollOffset ?? this.scrollOffset,
            crossAxisOffset: crossAxisOffset ?? this.crossAxisOffset,
            mainAxisExtent: mainAxisExtent ?? this.mainAxisExtent,
            crossAxisExtent: crossAxisExtent ?? this.crossAxisExtent,
            crossAxisCellCount: crossAxisCellCount ?? this.crossAxisCellCount,
            blockIndex: blockIndex ?? this.blockIndex
        );
    }

    public BoxConstraints getBoxConstraints(SliverConstraints constraints)
    {
        return constraints.asBoxConstraints(
            minExtent: mainAxisExtent ?? 0.0f,
            maxExtent: mainAxisExtent ?? float.PositiveInfinity,
            crossAxisExtent: crossAxisExtent
        );
    }

    public override string ToString()
    {
        return "SliverStaggeredGridGeometry(" +
               $"scrollOffset: {scrollOffset}, " +
               $"crossAxisOffset: {crossAxisOffset}, " +
               $"mainAxisExtent: {mainAxisExtent}, " +
               $"crossAxisExtent: {crossAxisExtent}, " +
               $"crossAxisCellCount: {crossAxisCellCount}, " +
               $"startIndex: {blockIndex})";
    }
}

public class RenderSliverStaggeredGrid : RenderSliverVariableSizeBoxAdaptor
{
    public RenderSliverStaggeredGrid(
        RenderSliverVariableSizeBoxChildManager childManager,
        SliverStaggeredGridDelegate gridDelegate
    ) : base(childManager: childManager)
    {
        _gridDelegate = gridDelegate;
        _pageSizeToViewportOffsets = new Dictionary<int, SplayTree<int, _ViewportOffsets>>();
    }

    public override void setupParentData(RenderObject child)
    {
        if (!(child.parentData is SliverVariableSizeBoxAdaptorParentData))
        {
            var data = new SliverVariableSizeBoxAdaptorParentData();

            // By default we will keep it true.
            //data.keepAlive = true;
            child.parentData = data;
        }
    }

    public SliverStaggeredGridDelegate gridDelegate
    {
        get { return _gridDelegate; }
        set
        {
            if (_gridDelegate == value)
            {
                return;
            }

            if (value.GetType() != _gridDelegate.GetType() ||
                value.shouldRelayout(_gridDelegate))
            {
                markNeedsLayout();
            }

            _gridDelegate = value;
        }
    }

    SliverStaggeredGridDelegate _gridDelegate;

    // modified by siyao for uiwidgets
    readonly Dictionary<int, SplayTree<int, _ViewportOffsets>> _pageSizeToViewportOffsets;

    protected override void performLayout()
    {
        childManager.didStartLayout();
        childManager.setDidUnderflow(false);

        float scrollOffset =
            constraints.scrollOffset + constraints.cacheOrigin;
        D.assert(scrollOffset >= 0.0);
        float remainingExtent = constraints.remainingCacheExtent;
        D.assert(remainingExtent >= 0.0);
        float targetEndScrollOffset = scrollOffset + remainingExtent;

        bool reachedEnd = false;
        float trailingScrollOffset = 0;
        float leadingScrollOffset = float.PositiveInfinity;
        bool visible = false;
        int firstIndex = 0;
        int lastIndex = 0;

        var configuration = _gridDelegate.getConfiguration(constraints);

        var pageSize = configuration.mainAxisOffsetsCacheSize *
                       constraints.viewportMainAxisExtent;
        if (pageSize == 0.0f)
        {
            geometry = SliverGeometry.zero;
            childManager.didFinishLayout();
            return;
        }

        var pageIndex = (int) (scrollOffset / pageSize);
        D.assert(pageIndex >= 0);

        // modified by siyao for uiwidgets
        var viewportOffsets = _pageSizeToViewportOffsets.putIfAbsent(
            configuration.crossAxisCount, () => new SplayTree<int, _ViewportOffsets>());
        Debug.Log($"page size {pageSize} update: {_pageSizeToViewportOffsets.Count}");

        _ViewportOffsets viewportOffset;
        if (viewportOffsets.isEmpty())
        {
            viewportOffset =
                new _ViewportOffsets(configuration.generateMainAxisOffsets(), pageSize);
            viewportOffsets[0] = viewportOffset;
        }
        else
        {
            var smallestKey = viewportOffsets.lastKeyBefore(pageIndex + 1);
            viewportOffset = viewportOffsets[smallestKey];
        }

        // A staggered grid always have to layout the child from the zero-index based one to the last visible.
        var mainAxisOffsets = viewportOffset.mainAxisOffsets.ToList();
        var visibleIndices = new HashSet<int>();

        // Iterate through all children while they can be visible.
        for (var index = viewportOffset.firstChildIndex;
            mainAxisOffsets.Any((o) => o <= targetEndScrollOffset);
            index++)
        {
            SliverStaggeredGridGeometry geometry =
                getSliverStaggeredGeometry(index, configuration, mainAxisOffsets);
            if (geometry == null)
            {
                // There are either no children, or we are past the end of all our children.
                reachedEnd = true;
                break;
            }

            bool hasTrailingScrollOffset = geometry.hasTrailingScrollOffset;
            RenderBox child = null;
            if (!hasTrailingScrollOffset)
            {
                // Layout the child to compute its tailingScrollOffset.
                var constraints =
                    BoxConstraints.tightFor(width: geometry.crossAxisExtent);
                child = addAndLayoutChild(index, constraints, parentUsesSize: true);
                geometry = geometry.copyWith(mainAxisExtent: paintExtentOf(child));
            }

            if (!visible &&
                targetEndScrollOffset >= geometry.scrollOffset &&
                scrollOffset <= geometry.trailingScrollOffset)
            {
                visible = true;
                leadingScrollOffset = geometry.scrollOffset;
                firstIndex = index;
            }

            if (visible && hasTrailingScrollOffset)
            {
                child =
                    addAndLayoutChild(index, geometry.getBoxConstraints(constraints));
            }

            if (child != null)
            {
                var childParentData =
                    child.parentData as SliverVariableSizeBoxAdaptorParentData;
                childParentData.layoutOffset = geometry.scrollOffset;
                childParentData.crossAxisOffset = geometry.crossAxisOffset;
                D.assert(childParentData.index == index);
            }

            if (visible && indices.Contains(index))
            {
                visibleIndices.Add(index);
            }

            if (geometry.trailingScrollOffset >=
                viewportOffset?.trailingScrollOffset)
            {
                var nextPageIndex = viewportOffset.pageIndex + 1;
                var nextViewportOffset = new _ViewportOffsets(
                    mainAxisOffsets,
                    (nextPageIndex + 1) * pageSize,
                    nextPageIndex,
                    index
                );
                viewportOffsets[nextPageIndex] = nextViewportOffset;
                viewportOffset = nextViewportOffset;
            }

            float endOffset =
                geometry.trailingScrollOffset + configuration.mainAxisSpacing;
            for (var i = 0; i < geometry.crossAxisCellCount; i++)
            {
                mainAxisOffsets[i + geometry.blockIndex] = endOffset;
            }

            trailingScrollOffset = mainAxisOffsets.Aggregate((acc, x) => acc + x);
            lastIndex = index;
        }

        collectGarbage(visibleIndices);

        if (!visible)
        {
            if (scrollOffset > viewportOffset.trailingScrollOffset)
            {
                // We are outside the bounds, we have to correct the scroll.
                var viewportOffsetScrollOffset = pageSize * viewportOffset.pageIndex;
                var correction = viewportOffsetScrollOffset - scrollOffset;
                geometry = new SliverGeometry(
                    scrollOffsetCorrection: correction
                );
            }
            else
            {
                geometry = SliverGeometry.zero;
                childManager.didFinishLayout();
            }

            return;
        }

        float estimatedMaxScrollOffset;
        if (reachedEnd)
        {
            estimatedMaxScrollOffset = trailingScrollOffset;
        }
        else
        {
            estimatedMaxScrollOffset = childManager.estimateMaxScrollOffset(
                constraints,
                firstIndex: firstIndex,
                lastIndex: lastIndex,
                leadingScrollOffset: leadingScrollOffset,
                trailingScrollOffset: trailingScrollOffset
            );
            D.assert(estimatedMaxScrollOffset >=
                     trailingScrollOffset - leadingScrollOffset);
        }

        float paintExtent = calculatePaintOffset(
            constraints,
            from: leadingScrollOffset,
            to: trailingScrollOffset
        );
        float cacheExtent = calculateCacheOffset(
            constraints,
            from: leadingScrollOffset,
            to: trailingScrollOffset
        );

        geometry = new SliverGeometry(
            scrollExtent: estimatedMaxScrollOffset,
            paintExtent: paintExtent,
            cacheExtent: cacheExtent,
            maxPaintExtent: estimatedMaxScrollOffset,
            // Conservative to avoid flickering away the clip during scroll.
            hasVisualOverflow: trailingScrollOffset > targetEndScrollOffset ||
                               constraints.scrollOffset > 0.0f
        );

        // We may have started the layout while scrolled to the end, which would not
        // expose a child.
        if (estimatedMaxScrollOffset == trailingScrollOffset)
        {
            childManager.setDidUnderflow(true);
        }

        childManager.didFinishLayout();
    }

    static SliverStaggeredGridGeometry getSliverStaggeredGeometry(int index,
        StaggeredGridConfiguration configuration, List<float> offsets)
    {
        var tile = configuration.getStaggeredTile(index);
        if (tile == null)
        {
            return null;
        }

        var block = _findFirstAvailableBlockWithCrossAxisCount(
            tile.crossAxisCellCount, offsets);

        var scrollOffset = block.minOffset;
        var blockIndex = block.index;
        if (configuration.reverseCrossAxis)
        {
            blockIndex =
                configuration.crossAxisCount - tile.crossAxisCellCount - blockIndex;
        }

        var crossAxisOffset = blockIndex * configuration.cellStride;
        var geometry = new SliverStaggeredGridGeometry(
            scrollOffset: scrollOffset,
            crossAxisOffset: crossAxisOffset,
            mainAxisExtent: tile.mainAxisExtent,
            crossAxisExtent: configuration.cellStride * tile.crossAxisCellCount -
                             configuration.crossAxisSpacing,
            crossAxisCellCount: tile.crossAxisCellCount,
            blockIndex: block.index
        );
        return geometry;
    }

    static _Block _findFirstAvailableBlockWithCrossAxisCount(
        int crossAxisCount, List<float> offsets)
    {
        return _findFirstAvailableBlockWithCrossAxisCountAndOffsets(
            crossAxisCount, new List<float>(offsets));
    }

    static _Block _findFirstAvailableBlockWithCrossAxisCountAndOffsets(
        int crossAxisCount, List<float> offsets)
    {
        var block = _findFirstAvailableBlock(offsets);
        if (block.crossAxisCount < crossAxisCount)
        {
            // Not enough space for the specified cross axis count.
            // We have to fill this block and try again.
            for (var i = 0; i < block.crossAxisCount; ++i)
            {
                offsets[i + block.index] = block.maxOffset;
            }

            return _findFirstAvailableBlockWithCrossAxisCountAndOffsets(
                crossAxisCount, offsets);
        }
        else
        {
            return block;
        }
    }

    static _Block _findFirstAvailableBlock(List<float> offsets)
    {
        int index = 0;
        float minBlockOffset = float.PositiveInfinity;
        float maxBlockOffset = float.PositiveInfinity;
        int crossAxisCount = 1;
        bool contiguous = false;

        // We have to use the GridUtil._nearEqual function because of floating-point arithmetic.
        // Ex: 0.1 + 0.2 = 0.30000000000000004 and not 0.3.

        for (var i = index; i < offsets.Count; ++i)
        {
            var offset = offsets[i];
            if (offset < minBlockOffset && !GridUtil._nearEqual(offset, minBlockOffset))
            {
                index = i;
                maxBlockOffset = minBlockOffset;
                minBlockOffset = offset;
                crossAxisCount = 1;
                contiguous = true;
            }
            else if (GridUtil._nearEqual(offset, minBlockOffset) && contiguous)
            {
                crossAxisCount++;
            }
            else if (offset < maxBlockOffset &&
                     offset > minBlockOffset &&
                     !GridUtil._nearEqual(offset, minBlockOffset))
            {
                contiguous = false;
                maxBlockOffset = offset;
            }
            else
            {
                contiguous = false;
            }
        }

        return new _Block(index, crossAxisCount, minBlockOffset, maxBlockOffset);
    }
}

internal class _ViewportOffsets
{
    internal _ViewportOffsets(
        List<float> mainAxisOffsets,
        float trailingScrollOffset,
        int pageIndex = 0,
        int firstChildIndex = 0
    )
    {
        this.trailingScrollOffset = trailingScrollOffset;
        this.pageIndex = pageIndex;
        this.firstChildIndex = firstChildIndex;
        this.mainAxisOffsets = mainAxisOffsets.ToList();
    }

    public readonly int pageIndex;

    public readonly int firstChildIndex;

    public readonly float trailingScrollOffset;

    public readonly List<float> mainAxisOffsets;

    public override string ToString() =>
        $"[{pageIndex}-{trailingScrollOffset}] ({firstChildIndex}, {mainAxisOffsets})";
}

public abstract class SliverStaggeredGridDelegate
{
    public SliverStaggeredGridDelegate(
        GridUtil.IndexedStaggeredTileBuilder staggeredTileBuilder = null,
        float mainAxisSpacing = 0,
        float crossAxisSpacing = 0,
        int? staggeredTileCount = null
    )
    {
        D.assert(mainAxisSpacing >= 0);
        D.assert(crossAxisSpacing >= 0);
        this.staggeredTileBuilder = staggeredTileBuilder;
        this.mainAxisSpacing = mainAxisSpacing;
        this.crossAxisSpacing = crossAxisSpacing;
        this.staggeredTileCount = staggeredTileCount;
    }

    public readonly float mainAxisSpacing;

    public readonly float crossAxisSpacing;

    public readonly GridUtil.IndexedStaggeredTileBuilder staggeredTileBuilder;

    public readonly int? staggeredTileCount;

    public virtual bool _debugAssertIsValid()
    {
        D.assert(mainAxisSpacing >= 0);
        D.assert(crossAxisSpacing >= 0);
        return true;
    }

    public abstract StaggeredGridConfiguration getConfiguration(SliverConstraints constraints);

    public virtual bool shouldRelayout(SliverStaggeredGridDelegate oldDelegate)
    {
        return oldDelegate.mainAxisSpacing != mainAxisSpacing ||
               oldDelegate.crossAxisSpacing != crossAxisSpacing ||
               oldDelegate.staggeredTileCount != staggeredTileCount ||
               oldDelegate.staggeredTileBuilder != staggeredTileBuilder;
    }
}

public class SliverStaggeredGridDelegateWithFixedCrossAxisCount : SliverStaggeredGridDelegate
{
    public SliverStaggeredGridDelegateWithFixedCrossAxisCount(
        int crossAxisCount,
        GridUtil.IndexedStaggeredTileBuilder staggeredTileBuilder,
        float mainAxisSpacing = 0,
        float crossAxisSpacing = 0,
        int? staggeredTileCount = null
    ) : base(
        staggeredTileBuilder: staggeredTileBuilder,
        mainAxisSpacing: mainAxisSpacing,
        crossAxisSpacing: crossAxisSpacing,
        staggeredTileCount: staggeredTileCount
    )
    {
        D.assert(crossAxisCount > 0);
        this.crossAxisCount = crossAxisCount;
    }

    public readonly int crossAxisCount;

    public override bool _debugAssertIsValid()
    {
        D.assert(crossAxisCount > 0);
        return base._debugAssertIsValid();
    }

    public override StaggeredGridConfiguration getConfiguration(SliverConstraints constraints)
    {
        D.assert(_debugAssertIsValid());
        float usableCrossAxisExtent =
            constraints.crossAxisExtent - crossAxisSpacing * (crossAxisCount - 1);
        float cellExtent = usableCrossAxisExtent / crossAxisCount;
        return new StaggeredGridConfiguration(
            crossAxisCount: crossAxisCount,
            staggeredTileBuilder: staggeredTileBuilder,
            staggeredTileCount: staggeredTileCount,
            cellExtent: cellExtent,
            mainAxisSpacing: mainAxisSpacing,
            crossAxisSpacing: crossAxisSpacing,
            reverseCrossAxis: AxisUtils.axisDirectionIsReversed(constraints.crossAxisDirection)
        );
    }

    public override bool shouldRelayout(SliverStaggeredGridDelegate oldDelegate)
    {
        return oldDelegate is SliverStaggeredGridDelegateWithFixedCrossAxisCount sliverOldDelegate
               && sliverOldDelegate.crossAxisCount != crossAxisCount ||
               base.shouldRelayout(oldDelegate);
    }
}

class SliverStaggeredGridDelegateWithMaxCrossAxisExtent : SliverStaggeredGridDelegate
{
    public SliverStaggeredGridDelegateWithMaxCrossAxisExtent(
        float maxCrossAxisExtent,
        GridUtil.IndexedStaggeredTileBuilder staggeredTileBuilder,
        float mainAxisSpacing = 0,
        float crossAxisSpacing = 0,
        int? staggeredTileCount = null
    ) : base(
        staggeredTileBuilder: staggeredTileBuilder,
        mainAxisSpacing: mainAxisSpacing,
        crossAxisSpacing: crossAxisSpacing,
        staggeredTileCount: staggeredTileCount
    )
    {
        D.assert(maxCrossAxisExtent > 0);
        this.maxCrossAxisExtent = maxCrossAxisExtent;
    }

    public float maxCrossAxisExtent;

    public override bool _debugAssertIsValid()
    {
        D.assert(maxCrossAxisExtent >= 0);
        return base._debugAssertIsValid();
    }

    public override StaggeredGridConfiguration getConfiguration(SliverConstraints constraints)
    {
        D.assert(_debugAssertIsValid());
        int crossAxisCount =
            ((constraints.crossAxisExtent + crossAxisSpacing) /
             (maxCrossAxisExtent + crossAxisSpacing))
            .ceil();

        float usableCrossAxisExtent =
            constraints.crossAxisExtent - crossAxisSpacing * (crossAxisCount - 1);

        float cellExtent = usableCrossAxisExtent / crossAxisCount;
        return new StaggeredGridConfiguration(
            crossAxisCount: crossAxisCount,
            staggeredTileBuilder: staggeredTileBuilder,
            staggeredTileCount: staggeredTileCount,
            cellExtent: cellExtent,
            mainAxisSpacing: mainAxisSpacing,
            crossAxisSpacing: crossAxisSpacing,
            reverseCrossAxis: AxisUtils.axisDirectionIsReversed(constraints.crossAxisDirection)
        );
    }

    public override bool shouldRelayout(SliverStaggeredGridDelegate oldDelegate)
    {
        return oldDelegate is SliverStaggeredGridDelegateWithMaxCrossAxisExtent delegateWithMaxCross &&
               delegateWithMaxCross.maxCrossAxisExtent != maxCrossAxisExtent ||
               base.shouldRelayout(oldDelegate);
    }
}