421 lines
17 KiB
C#
421 lines
17 KiB
C#
|
using Accord.Video.FFMPEG;
|
|||
|
|
using System;
|
|||
|
|
using System.Collections.Generic;
|
|||
|
|
using System.Diagnostics;
|
|||
|
|
using System.Drawing;
|
|||
|
|
using System.Drawing.Imaging;
|
|||
|
|
using System.IO;
|
|||
|
|
using System.Linq;
|
|||
|
|
using System.Text;
|
|||
|
|
using System.Threading.Tasks;
|
|||
|
|
|
|||
|
|
namespace SortingVisualization {
|
|||
|
|
public enum SetType {
|
|||
|
|
Ordererd,
|
|||
|
|
Reversed,
|
|||
|
|
Random,
|
|||
|
|
SingleError
|
|||
|
|
}
|
|||
|
|
public class DataSet {
|
|||
|
|
#region Props
|
|||
|
|
/// <summary>
|
|||
|
|
/// Gibt die Größe (Anzahl der zu sortierenden Werte) an.
|
|||
|
|
/// </summary>
|
|||
|
|
public int Size { get; private set; }
|
|||
|
|
/// <summary>
|
|||
|
|
/// Speichert das initale Datenset um verschiedene Algorithmen auf dasselbe Set anzuwenden (direkter Vergleich).
|
|||
|
|
/// </summary>
|
|||
|
|
private readonly int[] _InitialData;
|
|||
|
|
public int Seed { get; private set; }
|
|||
|
|
private int[] _Data;
|
|||
|
|
public int ReadOperations { get; private set; } = 0;
|
|||
|
|
public int WriteOperations { get; private set; } = 0;
|
|||
|
|
public int CompareOperations { get; private set; } = 0;
|
|||
|
|
public int SwapOperations { get; private set; } = 0;
|
|||
|
|
public long Ticks { get; private set; } = 0;
|
|||
|
|
public string SortingAlgorithm {
|
|||
|
|
get => _sortingAlgorithm;
|
|||
|
|
set {
|
|||
|
|
_sortingAlgorithm = value;
|
|||
|
|
if (!Directory.Exists(this.SortingAlgorithm)) {
|
|||
|
|
Directory.CreateDirectory(this.SortingAlgorithm);
|
|||
|
|
}
|
|||
|
|
_Directory = Path.Combine(this.SortingAlgorithm, DataSet.SetTypeToString(this.SetType));
|
|||
|
|
if (!Directory.Exists(_Directory)) {
|
|||
|
|
Directory.CreateDirectory(_Directory);
|
|||
|
|
}
|
|||
|
|
_Directory = Path.Combine(_Directory, this.Size.ToString());
|
|||
|
|
if (!Directory.Exists(_Directory)) {
|
|||
|
|
Directory.CreateDirectory(_Directory);
|
|||
|
|
}
|
|||
|
|
if (this.SetType == SetType.Random || this.SetType == SetType.SingleError) {
|
|||
|
|
_Directory = Path.Combine(_Directory, this.Seed.ToString());
|
|||
|
|
if (!Directory.Exists(_Directory)) {
|
|||
|
|
Directory.CreateDirectory(_Directory);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
if (!VideoRenderer.IsOpen) {
|
|||
|
|
VideoRenderer.Open(Path.Combine(_Directory, this.SortingAlgorithm + ".mkv"), 3000, 2000, new Accord.Math.Rational(60), VideoCodec.Default, int.MaxValue);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
private string _Directory = "uninitialized";
|
|||
|
|
private long _StartTime = 0;
|
|||
|
|
public SetType SetType { get; }
|
|||
|
|
private int _ExpectedFrameCount = 1;
|
|||
|
|
private bool _simulateMode;
|
|||
|
|
private int _frameSkipping = 0;
|
|||
|
|
private int _skippedFrames = 0;
|
|||
|
|
public bool SimulateMode {
|
|||
|
|
get => _simulateMode;
|
|||
|
|
set {
|
|||
|
|
if (value) {
|
|||
|
|
_ExpectedFrameCount = int.MaxValue;
|
|||
|
|
Console.WriteLine("Simulating {0} with {1} values (Set: {2} - Seed {3})...", this.SortingAlgorithm, this.Size, DataSet.SetTypeToString(this.SetType), this.Seed);
|
|||
|
|
} else {
|
|||
|
|
Console.WriteLine("Simulation ended! Results:\n\t{0} Reads\n\t{1} Writes\n\t{2} Comparisons\n\t{3} Swaps\n\t{4} Frames", this.ReadOperations, this.WriteOperations, this.CompareOperations, this.SwapOperations, this.FrameCount + this.Size);
|
|||
|
|
_ExpectedFrameCount = this.FrameCount + this.Size;
|
|||
|
|
this.ResetToInitial();
|
|||
|
|
_frameSkipping = _ExpectedFrameCount / 3600;
|
|||
|
|
Console.WriteLine("Drawing 1 in every {0} frames", _frameSkipping + 1);
|
|||
|
|
Console.SetOut(TextWriter.Null);
|
|||
|
|
}
|
|||
|
|
_simulateMode = value;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
#endregion
|
|||
|
|
#region Constructors
|
|||
|
|
public DataSet(int size, SetType type, int seed) {
|
|||
|
|
this.SetType = type;
|
|||
|
|
this.Seed = seed;
|
|||
|
|
this.Size = size;
|
|||
|
|
_InitialData = new int[size];
|
|||
|
|
var rnd = new Random(seed);
|
|||
|
|
switch (type) {
|
|||
|
|
case SetType.Ordererd:
|
|||
|
|
for (int i = 0; i < size; i++)
|
|||
|
|
_InitialData[i] = i + 1;
|
|||
|
|
break;
|
|||
|
|
case SetType.Reversed:
|
|||
|
|
for (int i = 0; i < size; i++)
|
|||
|
|
_InitialData[i] = size - i;
|
|||
|
|
break;
|
|||
|
|
case SetType.Random:
|
|||
|
|
for (int i = 0; i < size; i++) {
|
|||
|
|
int tmp;
|
|||
|
|
do {
|
|||
|
|
tmp = rnd.Next(1, size + 1); // TODO: Do this better!
|
|||
|
|
} while (_InitialData.Contains(tmp));
|
|||
|
|
_InitialData[i] = tmp;
|
|||
|
|
}
|
|||
|
|
break;
|
|||
|
|
case SetType.SingleError:
|
|||
|
|
for (int i = 1; i < size - 1; i++)
|
|||
|
|
_InitialData[i] = i + 1;
|
|||
|
|
_InitialData[0] = size;
|
|||
|
|
_InitialData[size - 1] = 1;
|
|||
|
|
break;
|
|||
|
|
default:
|
|||
|
|
throw new ArgumentException("Unhandled Enumeration type when initializing the dataset values!", "type");
|
|||
|
|
}
|
|||
|
|
_Data = new int[size];
|
|||
|
|
_InitialData.CopyTo(_Data, 0);
|
|||
|
|
_yScale = (double)_FrameHeight / (double)(this.Size);
|
|||
|
|
_xScale = (double)_FrameWidth / (double)(this.Size);
|
|||
|
|
_BarWidth = (int)Math.Ceiling(_xScale);
|
|||
|
|
}
|
|||
|
|
public DataSet(int size, SetType type) : this(size, type, Guid.NewGuid().GetHashCode()) { }
|
|||
|
|
public override string ToString() => $"{this.SortingAlgorithm} - {this.Size} Values - {DataSet.SetTypeToString(this.SetType)} Set - Seed {this.Seed}";
|
|||
|
|
#endregion
|
|||
|
|
#region Operations
|
|||
|
|
public static string SetTypeToString(SetType type) {
|
|||
|
|
switch (type) {
|
|||
|
|
case SetType.Ordererd:
|
|||
|
|
return "Ordered";
|
|||
|
|
case SetType.Reversed:
|
|||
|
|
return "Reversed";
|
|||
|
|
case SetType.Random:
|
|||
|
|
return "Random";
|
|||
|
|
case SetType.SingleError:
|
|||
|
|
return "SingleError";
|
|||
|
|
default:
|
|||
|
|
return "Unkown";
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
/// <summary>
|
|||
|
|
/// Gibt das Element des Datensets aus, das an (index + 1)-ter Stelle steht.
|
|||
|
|
/// </summary>
|
|||
|
|
/// <param name="index">Zugriffsindex, wirft einen Fehler, wenn der Index nicht gültig ist.</param>
|
|||
|
|
/// <returns>Kopie des Werts aus dem Datenset.</returns>
|
|||
|
|
private int this[int index] {
|
|||
|
|
get {
|
|||
|
|
this.ReadOperations++;
|
|||
|
|
return _Data[index];
|
|||
|
|
}
|
|||
|
|
set {
|
|||
|
|
this.WriteOperations++;
|
|||
|
|
_Data[index] = value;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
/// <summary>
|
|||
|
|
/// Reads the value at an index (same as this[index]) but generates a frame.
|
|||
|
|
/// </summary>
|
|||
|
|
/// <param name="index"></param>
|
|||
|
|
/// <returns></returns>
|
|||
|
|
public int ReadOperation(int index) {
|
|||
|
|
this.DrawReadFrame(index);
|
|||
|
|
return this[index];
|
|||
|
|
}
|
|||
|
|
public void WriteOperation(int index, int value) {
|
|||
|
|
this[index] = value;
|
|||
|
|
this.DrawWriteFrame(index);
|
|||
|
|
}
|
|||
|
|
private void Comparation(int left, int right) {
|
|||
|
|
this.CompareOperations++;
|
|||
|
|
this.DrawCompareFrame(left, right);
|
|||
|
|
}
|
|||
|
|
public bool GreaterThan(int left, int right) {
|
|||
|
|
this.Comparation(left, right);
|
|||
|
|
return (this[left] > this[right]);
|
|||
|
|
}
|
|||
|
|
public bool GreaterThanOrEqual(int left, int right) {
|
|||
|
|
this.Comparation(left, right);
|
|||
|
|
return (this[left] >= this[right]);
|
|||
|
|
}
|
|||
|
|
public bool LessThan(int left, int right) {
|
|||
|
|
this.Comparation(left, right);
|
|||
|
|
return (this[left] < this[right]);
|
|||
|
|
}
|
|||
|
|
public bool LessThanOrEqual(int left, int right) {
|
|||
|
|
this.Comparation(left, right);
|
|||
|
|
return (this[left] <= this[right]);
|
|||
|
|
}
|
|||
|
|
public bool Equal(int left, int right) {
|
|||
|
|
this.Comparation(left, right);
|
|||
|
|
return (this[left] == this[right]);
|
|||
|
|
}
|
|||
|
|
public bool Unequal(int left, int right) {
|
|||
|
|
this.Comparation(left, right);
|
|||
|
|
return (this[left] != this[right]);
|
|||
|
|
}
|
|||
|
|
public void Swap(int left, int right) {
|
|||
|
|
int tmp = this[left];
|
|||
|
|
this[left] = this[right];
|
|||
|
|
this[right] = tmp;
|
|||
|
|
this.SwapOperations++;
|
|||
|
|
this.DrawSwapFrame(left, right);
|
|||
|
|
}
|
|||
|
|
#endregion
|
|||
|
|
#region Timing
|
|||
|
|
public void StartTimer() => _StartTime = DateTime.Now.Ticks;
|
|||
|
|
public void StopTimer() => this.Ticks = DateTime.Now.Ticks - _StartTime;
|
|||
|
|
#endregion
|
|||
|
|
#region Visualizing
|
|||
|
|
public Brush BackgroundBrush = new SolidBrush(Color.Black);
|
|||
|
|
public Brush ReadColor = new SolidBrush(Color.Blue);
|
|||
|
|
public Brush WriteColor = new SolidBrush(Color.Magenta);
|
|||
|
|
public Brush CheckColor = new SolidBrush(Color.Green);
|
|||
|
|
public Brush BarColor = new SolidBrush(Color.White);
|
|||
|
|
public Brush CompareColor = new SolidBrush(Color.Red);
|
|||
|
|
public Brush SwapColor = new SolidBrush(Color.Yellow);
|
|||
|
|
private Bitmap _Frame = new Bitmap(_FrameWidth, _FrameHeight);
|
|||
|
|
private VideoFileWriter VideoRenderer = new VideoFileWriter();
|
|||
|
|
int _progress = 0;
|
|||
|
|
private int FrameCount {
|
|||
|
|
get => _FrameCount;
|
|||
|
|
set {
|
|||
|
|
if (!this.SimulateMode)
|
|||
|
|
VideoRenderer.WriteVideoFrame(_Frame);
|
|||
|
|
// _Frame.Save(Path.Combine(this.SortingAlgorithm, DataSet.SetTypeToString(this.SetType), $"Image{ _FrameCount.ToString("d6")}.png"), ImageFormat.Png);
|
|||
|
|
_FrameCount = value;
|
|||
|
|
int newprogress = (_FrameCount * 100) / _ExpectedFrameCount;
|
|||
|
|
if (newprogress > _progress) {
|
|||
|
|
_progress = newprogress;
|
|||
|
|
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) {
|
|||
|
|
AutoFlush = true
|
|||
|
|
});
|
|||
|
|
Console.Write("\rProgress: {0}% - {1} frames", newprogress, _FrameCount);
|
|||
|
|
Console.SetOut(TextWriter.Null);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
private static readonly int _FrameHeight = 2000;
|
|||
|
|
private static readonly int _FrameWidth = 3000;
|
|||
|
|
private readonly double _yScale = 1;
|
|||
|
|
private readonly double _xScale = 1;
|
|||
|
|
private readonly int _BarWidth = 1;
|
|||
|
|
private int _FrameCount = 0;
|
|||
|
|
private string _sortingAlgorithm = "DefaultAlgorithm";
|
|||
|
|
|
|||
|
|
private void DrawFrame() {
|
|||
|
|
this.ClearFrame();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void ClearFrame() {
|
|||
|
|
DrawRect(0, 0, _FrameWidth, _FrameHeight, ref this.BackgroundBrush);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void DrawRect(int x1, int y1, int w, int h, ref Brush brush) {
|
|||
|
|
int wn = w - 1;
|
|||
|
|
if (wn <= 0)
|
|||
|
|
wn = 1;
|
|||
|
|
int hn = h - 1;
|
|||
|
|
if (hn <= 0)
|
|||
|
|
hn = 1;
|
|||
|
|
using (var graphics = Graphics.FromImage(_Frame)) {
|
|||
|
|
graphics.FillRectangle(brush, x1, y1, wn, hn);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void DrawCompareFrame(int left, int right) {
|
|||
|
|
if (this.SimulateMode) {
|
|||
|
|
this.FrameCount++;
|
|||
|
|
} else {
|
|||
|
|
if (this.SkipFrame())
|
|||
|
|
return;
|
|||
|
|
DrawFrame();
|
|||
|
|
for (int i = 0; i < this.Size; i++) {
|
|||
|
|
int xpos = (int)(_xScale * i);
|
|||
|
|
int ypos = (int)(_yScale * this._Data[i]);
|
|||
|
|
if (i == left || i == right)
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.CompareColor);
|
|||
|
|
else
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.BarColor);
|
|||
|
|
}
|
|||
|
|
++this.FrameCount;
|
|||
|
|
//Console.WriteLine("Compare frame {0} was drawn",this.FrameCount);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void DrawReadFrame(int index) {
|
|||
|
|
DataSet dataSet = this;
|
|||
|
|
if (dataSet.SimulateMode) {
|
|||
|
|
this.FrameCount++;
|
|||
|
|
} else {
|
|||
|
|
if (this.SkipFrame())
|
|||
|
|
return;
|
|||
|
|
DrawFrame();
|
|||
|
|
for (int i = 0; i < this.Size; i++) {
|
|||
|
|
int xpos = (int)(_xScale * i);
|
|||
|
|
int ypos = (int)(_yScale * this._Data[i]);
|
|||
|
|
if (i == index)
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.ReadColor);
|
|||
|
|
else
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.BarColor);
|
|||
|
|
}
|
|||
|
|
++this.FrameCount;
|
|||
|
|
//Console.WriteLine("Read frame {0} was drawn", this.FrameCount);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void DrawWriteFrame(int index) {
|
|||
|
|
if (this.SimulateMode) {
|
|||
|
|
this.FrameCount++;
|
|||
|
|
} else {
|
|||
|
|
if (this.SkipFrame())
|
|||
|
|
return;
|
|||
|
|
DrawFrame();
|
|||
|
|
for (int i = 0; i < this.Size; i++) {
|
|||
|
|
int xpos = (int)(_xScale * i);
|
|||
|
|
int ypos = (int)(_yScale * this._Data[i]);
|
|||
|
|
if (i == index)
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.WriteColor);
|
|||
|
|
else
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.BarColor);
|
|||
|
|
}
|
|||
|
|
++this.FrameCount;
|
|||
|
|
//Console.WriteLine("Write frame {0} was drawn", this.FrameCount);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void DrawSwapFrame(int left, int right) {
|
|||
|
|
if (this.SimulateMode) {
|
|||
|
|
this.FrameCount++;
|
|||
|
|
} else {
|
|||
|
|
if (this.SkipFrame())
|
|||
|
|
return;
|
|||
|
|
DrawFrame();
|
|||
|
|
for (int i = 0; i < this.Size; i++) {
|
|||
|
|
int xpos = (int)(_xScale * i);
|
|||
|
|
int ypos = (int)(_yScale * this._Data[i]);
|
|||
|
|
if (i == left || i == right)
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.SwapColor);
|
|||
|
|
else
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.BarColor);
|
|||
|
|
}
|
|||
|
|
++this.FrameCount;
|
|||
|
|
//Console.WriteLine("Swap frame {0} was drawn", this.FrameCount);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private bool SkipFrame() {
|
|||
|
|
if (_skippedFrames++ < _frameSkipping) {
|
|||
|
|
++this._FrameCount; // Avoid automatic drawing trough property
|
|||
|
|
return true;
|
|||
|
|
} else {
|
|||
|
|
_skippedFrames = 0;
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
public void FinalizeVideo() {
|
|||
|
|
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) {
|
|||
|
|
AutoFlush = true
|
|||
|
|
});
|
|||
|
|
Console.WriteLine("\n\nFinalizing...");
|
|||
|
|
for (int i = 0; i < this.Size; i++) {
|
|||
|
|
int xpos = (int)(_xScale * i);
|
|||
|
|
int ypos = (int)(_yScale * this._Data[i]);
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.BarColor);
|
|||
|
|
}
|
|||
|
|
//if (!this.SkipFrame())
|
|||
|
|
++this.FrameCount;
|
|||
|
|
//Console.WriteLine("Finalizing Frame {0} was drawn", this.FrameCount);
|
|||
|
|
for (int d = 0; d < this.Size; d++) { // Add 1 checked bar per frame
|
|||
|
|
int xpos = (int)(_xScale * d);
|
|||
|
|
int ypos = (int)(_yScale * this._Data[d]);
|
|||
|
|
DrawRect(xpos, _FrameHeight - ypos, _BarWidth, ypos, ref this.CheckColor);
|
|||
|
|
//if (this.SkipFrame())
|
|||
|
|
// continue;
|
|||
|
|
++this.FrameCount;
|
|||
|
|
//Console.WriteLine("Finalizing Frame {0} was drawn", this.FrameCount);
|
|||
|
|
}
|
|||
|
|
Console.WriteLine("Encoding video from frames...");
|
|||
|
|
//var startInfo = new System.Diagnostics.ProcessStartInfo {
|
|||
|
|
// WorkingDirectory = _Directory,
|
|||
|
|
// WindowStyle = System.Diagnostics.ProcessWindowStyle.Normal,
|
|||
|
|
// FileName = "ffmpeg.exe",
|
|||
|
|
// Arguments = $"-r 60 -f image2 -s {_FrameWidth}x{_FrameHeight} -i Image%06d.png -vcodec libx264 -crf 25 -pix_fmt yuv420p {this.SortingAlgorithm}.mp4",
|
|||
|
|
// RedirectStandardInput = true,
|
|||
|
|
// UseShellExecute = false,
|
|||
|
|
// RedirectStandardOutput = true,
|
|||
|
|
// CreateNoWindow = false
|
|||
|
|
//};
|
|||
|
|
//Process.Start(startInfo);
|
|||
|
|
VideoRenderer.Close();
|
|||
|
|
VideoRenderer.Dispose();
|
|||
|
|
VideoRenderer = null;
|
|||
|
|
VideoRenderer = new VideoFileWriter();
|
|||
|
|
Console.WriteLine("Video encoded!");
|
|||
|
|
}
|
|||
|
|
#endregion
|
|||
|
|
#region Resetting
|
|||
|
|
public void ResetToInitial() {
|
|||
|
|
_Data = null;
|
|||
|
|
_Data = new int[this.Size];
|
|||
|
|
_InitialData.CopyTo(_Data, 0);
|
|||
|
|
_Frame?.Dispose();
|
|||
|
|
_Frame = null;
|
|||
|
|
_Frame = new Bitmap(_FrameWidth, _FrameHeight);
|
|||
|
|
this.ReadOperations = 0;
|
|||
|
|
this.WriteOperations = 0;
|
|||
|
|
this.CompareOperations = 0;
|
|||
|
|
this.Ticks = 0;
|
|||
|
|
this.FrameCount = 0;
|
|||
|
|
this._progress = 0;
|
|||
|
|
this._skippedFrames = 0;
|
|||
|
|
}
|
|||
|
|
#endregion
|
|||
|
|
}
|
|||
|
|
}
|