using System;

using System.Collections.Generic;

using Avalonia;

using Avalonia.Media;

namespace SourceGit.Models

{

public record CommitGraphLayout(double StartY, double ClipWidth, double RowHeight);

public enum CommitGraphHighlighting

{

All = 0,

CurrentBranchOnly,

SelectedCommitsOnly,

CurrentBranchAndSelectedCommits,

}

public class CommitGraph

{

public static List<Pen> Pens { get; } = [];

public static void SetDefaultPens(double thickness = 2)

{

SetPens(s_defaultPenColors, thickness);

}

public static void SetPens(List<Color> colors, double thickness)

{

Pens.Clear();

foreach (var c in colors)

Pens.Add(new Pen(c.ToUInt32(), thickness));

s_penCount = colors.Count;

}

public class Path(int color, bool isHighlighted)

{

public List<Point> Points { get; } = [];

public int Color { get; } = color;

public bool IsHighlighted { get; } = isHighlighted;

public bool IsHoveredRelated { get; set; } = false;

public int StartCommitIndex { get; set; } = -1;

public int EndCommitIndex { get; set; } = -1;

}

public class Link

{

public Point Start;

public Point Control;

public Point End;

public int Color;

public bool IsHighlighted;

public int StartCommitIndex = -1;

public int EndCommitIndex = -1;

}

public enum DotType

{

Default,

Head,

Merge,

Filter,

}

public class Dot

{

public DotType Type;

public Point Center;

public int Color;

public bool IsHighlighted;

}

public List<Path> Paths { get; } = [];

public List<Link> Links { get; } = [];

public List<Dot> Dots { get; } = [];

/// <summary>

/// 为指定提交记录构建谱系掩码。

///

/// 返回的布尔数组与 _commits 按索引一一对应：

/// - true 代表该行记录属于计算得出的谱系范围。

/// - false 代表该行记录不在该谱系范围内。

///

/// 提交记录集合内的索引排布规则：

/// - 索引数值越小，对应提交记录越新（在历史列表中位置越靠上）。

/// - 索引数值越大，对应提交记录越旧（在历史列表中位置越靠下）。

///

/// 检索模式说明：

/// - ChildsOnly：向索引更小方向遍历，查找更新的后代提交记录。

/// - ParentsOnly：向索引更大方向遍历，查找更早的祖先提交记录。

/// - FullLineage：同时向两个方向进行遍历检索。

/// </summary>

public static bool[] GetCommitLineageFast(

List<Commit> commits,

Dictionary<string, Commit> map,

Commit commit,

CommitLineageSearchMethod method,

uint depth = 100,

int viewportTopIndex = -1,

int viewportBottomIndex = -1)

{

var active = new bool[commits.Count];

if (commit == null || method == Models.CommitLineageSearchMethod.None)

return active;

active[commit.Index] = true;

// First clamp by logical depth around the target commit.

int topLimit = Math.Max(0, commit.Index - (int)depth);

int bottomLimit = Math.Min(commits.Count - 1, commit.Index + (int)depth);

// Then optionally clamp by current viewport to reduce work for hover updates.

if (viewportTopIndex >= 0 && viewportBottomIndex >= viewportTopIndex)

{

topLimit = Math.Max(topLimit, viewportTopIndex);

bottomLimit = Math.Min(bottomLimit, viewportBottomIndex);

}

if (method == CommitLineageSearchMethod.ChildsOnly ||

method == CommitLineageSearchMethod.FullLineage ||

method == CommitLineageSearchMethod.FirstParentLineage)

{

// Descendant pass:

// Scan towards newer rows (smaller index). A commit is descendant-highlighted

// when any of its parents is already active.

for (int i = commit.Index - 1; i >= topLimit; i--)

{

if (method == CommitLineageSearchMethod.FirstParentLineage)

{

var pSha = commits[i].Parents.Count > 0 ? commits[i].Parents[0] : null;

if (pSha != null && map.TryGetValue(pSha, out var parent) &&

parent.Index < commits.Count && active[parent.Index])

{

active[i] = true;

}

}

else

{

foreach (var pSha in commits[i].Parents)

{

if (map.TryGetValue(pSha, out var parent) &&

parent.Index < commits.Count && active[parent.Index])

{

active[i] = true;

break;

}

}

}

}

}

if (method == CommitLineageSearchMethod.ParentsOnly ||

method == CommitLineageSearchMethod.FullLineage ||

method == CommitLineageSearchMethod.FirstParentLineage)

{

// Ancestor pass:

// Scan towards older rows (larger index). For each active commit,

// propagate highlight to all reachable parents in range.

for (int i = commit.Index; i <= bottomLimit; i++)

{

if (active[i])

{

if (method == CommitLineageSearchMethod.FirstParentLineage)

{

if (commits[i].Parents.Count > 0)

{

var pSha = commits[i].Parents[0];

if (map.TryGetValue(pSha, out var parent) && parent.Index <= bottomLimit)

{

active[parent.Index] = true;

}

}

}

else

{

foreach (var pSha in commits[i].Parents)

{

if (map.TryGetValue(pSha, out var parent) && parent.Index <= bottomLimit)

{

active[parent.Index] = true;

}

}

}

}

}

}

return active;

}

public static CommitGraph Generate(List<Commit> commits, bool recalculateMergeState,

bool firstParentOnlyEnabled, CommitGraphHighlighting highlighting,

bool[] selectedLineage)

{

const double unitWidth = 12;

const double halfWidth = 6;

const double unitHeight = 1;

const double halfHeight = 0.5;

var temp = new CommitGraph();

var unsolved = new List<PathHelper>();

var ended = new List<PathHelper>();

var offsetY = -halfHeight;

var colorPicker = new ColorPicker();

var merged = new HashSet<string>();

var commitMap = new Dictionary<string, int>();

for (int i = 0; i < commits.Count; i++)

{

commits[i].Index = i;

commitMap[commits[i].SHA] = i;

}

foreach (var commit in commits)

{

PathHelper major = null;

// Update merge state of this commit.

if (recalculateMergeState)

{

if (commit.IsMerged)

{

merged.Remove(commit.SHA);

foreach (var p in commit.Parents)

merged.Add(p);

}

else if (merged.Remove(commit.SHA))

{

commit.IsMerged = true;

foreach (var p in commit.Parents)

merged.Add(p);

}

}

// Calculate highlighted state of the commit itself

bool isCommitSelected = selectedLineage != null && commit.Index < selectedLineage.Length && selectedLineage[commit.Index];

var isHighlighted = false;

if (highlighting == CommitGraphHighlighting.All)

isHighlighted = true;

else if (highlighting == CommitGraphHighlighting.CurrentBranchOnly)

isHighlighted = commit.IsMerged;

else if (highlighting == CommitGraphHighlighting.SelectedCommitsOnly)

isHighlighted = isCommitSelected;

else

isHighlighted = commit.IsMerged || isCommitSelected;

commit.IsHighlightedInGraph = isHighlighted;

// Update current y offset

offsetY += unitHeight;

// Find first curves that links to this commit and marks others that links to this commit ended.

var offsetX = 4 - halfWidth;

var maxOffsetOld = unsolved.Count > 0 ? unsolved[^1].LastX : offsetX + unitWidth;

foreach (var l in unsolved)

{

if (l.Next.Equals(commit.SHA, StringComparison.Ordinal))

{

if (major == null)

{

offsetX += unitWidth;

major = l;

if (commit.Parents.Count > 0)

{

major.Next = commit.Parents[0];

major.Goto(offsetX, offsetY, halfHeight);

}

else

{

major.End(offsetX, offsetY, halfHeight);

major.Path.EndCommitIndex = commit.Index;

ended.Add(l);

}

}

else

{

l.End(major.LastX, offsetY, halfHeight);

l.Path.EndCommitIndex = commit.Index;

ended.Add(l);

}

}

else

{

offsetX += unitWidth;

l.Pass(offsetX, offsetY, halfHeight);

}

}

// Remove ended curves from unsolved

foreach (var l in ended)

{

colorPicker.Recycle(l.Path.Color);

unsolved.Remove(l);

}

ended.Clear();

// Determine highlighting for NEXT segments

bool nextIsHighlighted = false;

if (highlighting == CommitGraphHighlighting.All)

{

nextIsHighlighted = true;

}

else if (commit.Parents.Count > 0)

{

var pSha = commit.Parents[0];

var pIndex = commitMap.GetValueOrDefault(pSha, -1);

bool pIsSelected = pIndex >= 0 && selectedLineage != null && pIndex < selectedLineage.Length && selectedLineage[pIndex];

bool pIsMerged = recalculateMergeState ? merged.Contains(pSha) : (pIndex >= 0 && commits[pIndex].IsMerged);

if (highlighting == CommitGraphHighlighting.CurrentBranchOnly)

nextIsHighlighted = commit.IsMerged && pIsMerged;

else if (highlighting == CommitGraphHighlighting.SelectedCommitsOnly)

nextIsHighlighted = isCommitSelected && pIsSelected;

else

nextIsHighlighted = (commit.IsMerged && pIsMerged) || (isCommitSelected && pIsSelected);

}

// If no path found, create new curve for branch head

if (major == null)

{

offsetX += unitWidth;

if (commit.Parents.Count > 0)

{

major = new PathHelper(commit.Parents[0], nextIsHighlighted, colorPicker.Next(), new Point(offsetX, offsetY), commit.Index);

unsolved.Add(major);

temp.Paths.Add(major.Path);

}

}

else if (major != null && commit.Parents.Count > 0)

{

// Break at every commit to ensure path-aware highlight is precise.

major.Path.EndCommitIndex = commit.Index;

major.Replace(major.Path.Color, nextIsHighlighted, commit.Index);

temp.Paths.Add(major.Path);

}

if (major != null)

commit.PathIndex = temp.Paths.IndexOf(major.Path);

// Calculate link position of this commit.

var position = new Point(major?.LastX ?? offsetX, offsetY);

var dotColor = major?.Path.Color ?? 0;

temp.Dots.Add(new Dot() { Center = position, Color = dotColor, IsHighlighted = isHighlighted, Type = commit.IsCommitFilterHead ? DotType.Filter : (commit.IsCurrentHead ? DotType.Head : (commit.Parents.Count > 1 ? DotType.Merge : DotType.Default)) });

// Deal with other parents

if (!firstParentOnlyEnabled)

{

for (int j = 1; j < commit.Parents.Count; j++)

{

var pSha = commit.Parents[j];

var pIndex = commitMap.GetValueOrDefault(pSha, -1);

bool pIsSelected = pIndex >= 0 && selectedLineage != null && pIndex < selectedLineage.Length && selectedLineage[pIndex];

bool pIsMerged = recalculateMergeState ? merged.Contains(pSha) : (pIndex >= 0 && commits[pIndex].IsMerged);

bool linkIsHighlighted = false;

if (highlighting == CommitGraphHighlighting.All)

linkIsHighlighted = true;

else if (highlighting == CommitGraphHighlighting.CurrentBranchOnly)

linkIsHighlighted = commit.IsMerged && pIsMerged;

else if (highlighting == CommitGraphHighlighting.SelectedCommitsOnly)

linkIsHighlighted = isCommitSelected && pIsSelected;

else

linkIsHighlighted = (commit.IsMerged && pIsMerged) || (isCommitSelected && pIsSelected);

var parent = unsolved.Find(x => x.Next.Equals(pSha, StringComparison.Ordinal));

if (parent != null)

{

temp.Links.Add(new Link

{

Start = position,

End = new Point(parent.LastX, offsetY + halfHeight),

Control = new Point(parent.LastX, position.Y),

Color = parent.Path.Color,

IsHighlighted = linkIsHighlighted,

StartCommitIndex = commit.Index,

EndCommitIndex = pIndex,

});

}

else

{

offsetX += unitWidth;

var l = new PathHelper(pSha, linkIsHighlighted, colorPicker.Next(), position, new Point(offsetX, position.Y + halfHeight), commit.Index);

unsolved.Add(l);

temp.Paths.Add(l.Path);

}

}

}

commit.Color = dotColor;

commit.LeftMargin = Math.Max(offsetX, maxOffsetOld) + halfWidth + 2;

}

// Deal with curves haven't ended yet.

for (var i = 0; i < unsolved.Count; i++)

{

var path = unsolved[i];

var endY = (commits.Count - 0.5) * unitHeight;

if (path.Path.Points.Count == 1 && Math.Abs(path.Path.Points[0].Y - endY) < 0.0001)

continue;

path.End((i + 0.5) * unitWidth + 4, endY + halfHeight, halfHeight);

path.Path.EndCommitIndex = commits.Count - 1;

}

unsolved.Clear();

return temp;

}

private class ColorPicker

{

public int Next()

{

if (_colorsQueue.Count == 0)

{

for (var i = 0; i < s_penCount; i++)

_colorsQueue.Enqueue(i);

}

return _colorsQueue.Dequeue();

}

public void Recycle(int idx)

{

if (!_colorsQueue.Contains(idx))

_colorsQueue.Enqueue(idx);

}

private Queue<int> _colorsQueue = new Queue<int>();

}

private class PathHelper

{

public Path Path { get; private set; }

public string Next { get; set; }

public double LastX { get; private set; }

public bool IsHighlighted { get => Path.IsHighlighted; }

public PathHelper(string next, bool IsHighlighted, int color, Point start, int startCommitIndex)

{

Next = next;

LastX = start.X;

_lastY = start.Y;

Path = new Path(color, IsHighlighted);

Path.Points.Add(start);

Path.StartCommitIndex = startCommitIndex;

}

public PathHelper(string next, bool IsHighlighted, int color, Point start, Point to, int startCommitIndex)

{

Next = next;

LastX = to.X;

_lastY = to.Y;

Path = new Path(color, IsHighlighted);

Path.Points.Add(start);

Path.Points.Add(to);

Path.StartCommitIndex = startCommitIndex;

}

/// <summary>

/// A path that just passed this row.

/// </summary>

/// <param name="x"></param>

/// <param name="y"></param>

/// <param name="halfHeight"></param>

public void Pass(double x, double y, double halfHeight)

{

if (x > LastX)

{

Add(LastX, _lastY);

Add(x, y - halfHeight);

}

else if (x < LastX)

{

Add(LastX, y - halfHeight);

y += halfHeight;

Add(x, y);

}

LastX = x;

_lastY = y;

}

/// <summary>

/// A path that has commit in this row but not ended

/// </summary>

/// <param name="x"></param>

/// <param name="y"></param>

/// <param name="halfHeight"></param>

public void Goto(double x, double y, double halfHeight)

{

if (x > LastX)

{

Add(LastX, _lastY);

Add(x, y - halfHeight);

}

else if (x < LastX)

{

var minY = y - halfHeight;

if (minY > _lastY)

minY -= halfHeight;

Add(LastX, minY);

Add(x, y);

}

LastX = x;

_lastY = y;

}

/// <summary>

/// A path that has commit in this row and end.

/// </summary>

/// <param name="x"></param>

/// <param name="y"></param>

/// <param name="halfHeight"></param>

public void End(double x, double y, double halfHeight)

{

if (x > LastX)

{

Add(LastX, _lastY);

Add(x, y - halfHeight);

}

else if (x < LastX)

{

Add(LastX, y - halfHeight);

}

Add(x, y);

LastX = x;

_lastY = y;

}

/// <summary>

/// End the current path and create a new one from the end.

/// </summary>

public void Replace(int color, bool isHighlighted, int startCommitIndex)

{

Add(LastX, _lastY);

Path = new Path(color, isHighlighted);

Path.Points.Add(new Point(LastX, _lastY));

Path.StartCommitIndex = startCommitIndex;

_endY = 0;

}

/// <summary>

/// End the current path and create a new highlighted from the end.

/// </summary>

public void Highlight(int commitIndex)

{

Path.EndCommitIndex = commitIndex;

Replace(Path.Color, true, commitIndex);

}

private void Add(double x, double y)

{

if (_endY < y)

{

Path.Points.Add(new Point(x, y));

_endY = y;

}

}

private double _lastY = 0;

private double _endY = 0;

}

private static int s_penCount = 0;

private static readonly List<Color> s_defaultPenColors = [

Colors.Orange,

Colors.ForestGreen,

Colors.Turquoise,

Colors.Olive,

Colors.Magenta,

Colors.Red,

Colors.Khaki,

Colors.Lime,

Colors.RoyalBlue,

Colors.Teal,

];

}

}