Не без проблем я смог преобразовать следующий фрагмент из рекурсии в итерацию.
(благодаря этот ответ btw)
Рекурсия:
private static Bin Find(Bin bin, int w, int h)
{
if (bin.Used)
return Find(bin.Right, w, h) ?? Find(bin.Down, w, h);
if (w <= bin.W && h <= bin.H)
return bin;
return null;
}
Итерация:
private static Bin Find(Bin bin, int w, int h)
{
var stack = new Stack<Bin>(new[] {bin});
while (stack.Any())
{
var pop = stack.Pop();
if (pop.Used)
{
stack.Push(pop.Down);
stack.Push(pop.Right);
continue;
}
if (w <= pop.W && h <= pop.H)
return pop;
}
return null;
}
Теперь есть кое-что, чего я не понимаю, почему это волшебным образом работает?
Потому что, когда вы смотрите на оригинальную реализацию:
- пока используется bin, продолжайте примерять
Right bin - иначе продолжайте примерять
Down bin
Во время итерации я пу sh оба листа, Right и Down выталкиваются / обрабатываются последовательно, но все равно работает.
Вопрос:
Мой код не совсем правильный, но потому что как эта структура данных работает в любом случае?
Или мое преобразование в итерацию действительно соответствует исходной рекурсии?
Ссылка:
Вот полный алгоритм на случай, если вы захотите взглянуть на него.
using System;
using System.Collections.Generic;
using System.Linq;
using JetBrains.Annotations;
namespace ABCD
{
public static class BinPacker
{
public static void Fit([NotNull] Size[] sizes)
{
if (sizes == null)
throw new ArgumentNullException(nameof(sizes));
var root = new Bin
{
X = 0,
Y = 0,
W = sizes.Length > 0 ? sizes[0].W : 0,
H = sizes.Length > 0 ? sizes[0].H : 0
};
var rects = new Rect[sizes.Length];
for (var i = 0; i < sizes.Length; i++)
{
var s = sizes[i];
var w = s.W;
var h = s.H;
var n = Find(root, w, h);
n = n != null ? Split(n, w, h) : Grow(ref root, w, h);
rects[i] = new Rect(n.X, n.Y, w, h);
}
}
private static Bin Find(Bin bin, int w, int h)
{
if (bin.Used)
return Find(bin.Right, w, h) ?? Find(bin.Down, w, h);
if (w <= bin.W && h <= bin.H)
return bin;
return null;
}
private static Bin Split(Bin bin, int w, int h)
{
bin.Used = true;
bin.Down = new Bin
{
X = bin.X,
Y = bin.Y + h,
W = bin.W,
H = bin.H - h
};
bin.Right = new Bin
{
X = bin.X + w,
Y = bin.Y,
W = bin.W - w,
H = h
};
return bin;
}
private static Bin Grow([NotNull] ref Bin bin, int w, int h)
{
if (bin == null)
throw new ArgumentNullException(nameof(bin));
var canGrowR = h <= bin.H;
var canGrowD = w <= bin.W;
var letGrowR = canGrowR && bin.H >= bin.W + w;
var letGrowD = canGrowD && bin.W >= bin.H + h;
if (letGrowR)
return GrowRight(ref bin, w, h);
if (letGrowD)
return GrowDown(ref bin, w, h);
if (canGrowR)
return GrowRight(ref bin, w, h);
if (canGrowD)
return GrowDown(ref bin, w, h);
return null;
}
private static Bin GrowDown([NotNull] ref Bin bin, int w, int h)
{
if (bin == null)
throw new ArgumentNullException(nameof(bin));
bin = new Bin
{
X = 0,
Y = 0,
W = bin.W,
H = bin.H + h,
Used = true,
Down = new Bin
{
X = 0,
Y = bin.H,
W = bin.W,
H = h
},
Right = bin
};
var find = Find(bin, w, h);
return Split(find, w, h);
}
private static Bin GrowRight([NotNull] ref Bin root, int w, int h)
{
if (root == null)
throw new ArgumentNullException(nameof(root));
root = new Bin
{
X = 0,
Y = 0,
W = root.W + w,
H = root.H,
Used = true,
Down = root,
Right = new Bin
{
X = root.W,
Y = 0,
W = w,
H = root.H
}
};
var node = Find(root, w, h);
return Split(node, w, h);
}
}
internal sealed class Bin
{
public int X { get; set; }
public int Y { get; set; }
public int W { get; set; }
public int H { get; set; }
public bool Used { get; set; }
public Bin Down { get; set; }
public Bin Right { get; set; }
public override string ToString()
{
return $"{nameof(X)}: {X}, {nameof(Y)}: {Y}, {nameof(W)}: {W}, {nameof(H)}: {H}, {nameof(Used)}: {Used}";
}
}
[PublicAPI]
public struct Size : IEquatable<Size>
{
public readonly int W, H;
public Size(int w, int h)
{
W = w;
H = h;
}
public override string ToString()
{
return $"{nameof(W)}: {W}, {nameof(H)}: {H}";
}
public bool Equals(Size other)
{
return W == other.W && H == other.H;
}
public override bool Equals(object obj)
{
return obj is Size other && Equals(other);
}
public override int GetHashCode()
{
unchecked
{
return (W * 397) ^ H;
}
}
public static bool operator ==(Size left, Size right)
{
return left.Equals(right);
}
public static bool operator !=(Size left, Size right)
{
return !left.Equals(right);
}
}
[PublicAPI]
public struct Rect : IEquatable<Rect>
{
public readonly int X, Y, W, H;
public Rect(int x, int y, int w, int h)
{
X = x;
Y = y;
W = w;
H = h;
}
public override string ToString()
{
return $"{nameof(X)}: {X}, {nameof(Y)}: {Y}, {nameof(W)}: {W}, {nameof(H)}: {H}";
}
public bool Equals(Rect other)
{
return X == other.X && Y == other.Y && W == other.W && H == other.H;
}
public override bool Equals(object obj)
{
return obj is Rect other && Equals(other);
}
public override int GetHashCode()
{
unchecked
{
var hashCode = X;
hashCode = (hashCode * 397) ^ Y;
hashCode = (hashCode * 397) ^ W;
hashCode = (hashCode * 397) ^ H;
return hashCode;
}
}
public static bool operator ==(Rect left, Rect right)
{
return left.Equals(right);
}
public static bool operator !=(Rect left, Rect right)
{
return !left.Equals(right);
}
}
}