使用画图方法显示排序算法,使用策略模式

时间:2021-08-14 21:59:48
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace AnimatorPatterm
{
    static class StartSetGenerator
    {
        private static List<int> myList;
        public static IEnumerable<int> GetStartSet() 
        {
            const int n = 200; //how many values to generate
            if (myList == null)
            {
                List<int> list = new List<int>();
                Random rnd = new Random();

                List<int> range = new List<int>();
                for (int i = 0; i < n; i++)
                    range.Add(i);

                while (range.Count > 0)
                {
                     int item = range[rnd.Next(range.Count )];
                    list.Add(item);
                    range.Remove(item);
                }
                myList = list; 
            }
            return myList;
        }
    }

    class StrategyView<T> : Form where T : IComparable<T>
    {
        PictureBox pb;
        Func<IEnumerable<T>> Generator;

        public StrategyView(Func<IEnumerable<T>> generator)
        {
            this.Generator = generator;
            this.Text = "Sort Comparer"; 
            this.pb = new PictureBox();
            pb.Dock = DockStyle.Fill;
            pb.BackColor = Color.White;
            pb.BorderStyle = BorderStyle.Fixed3D;
            this.Controls.Add(pb);

            TableLayoutPanel p = new TableLayoutPanel();
            p.RowCount = 1;
            p.ColumnCount = 3;
            p.Dock = DockStyle.Top;
            this.Controls.Add(p);

            Button b = new Button();
            b.Name = "LargeItems";
            b.Click += new EventHandler(ButtonClick);
            b.Text = "Objects";
            p.Controls.Add(b);

            b = new Button();
            b.Name = "SmallItems";
            b.Click += new EventHandler(ButtonClick);
            b.Text = "Primitive";
            p.Controls.Add(b);

            b = new Button();
            b.Name = "ReversedList";
            b.Click += new EventHandler(ButtonClick);
            b.Text = "Reversed";
            p.Controls.Add(b);

            p.Height = b.Height + 4;
            this.DoubleBuffered = true;
            this.ResumeLayout(true);
        }

        public void DrawGraph(IEnumerable<T> list)
        {
            if (pb.Image == null)
                pb.Image = new Bitmap(pb.Width, pb.Height);
            Graphics g = Graphics.FromImage(pb.Image);
            g.Clear(Color.White);
            g.DrawRectangle(Pens.Blue, 19, 19, 202, 202);
            g.Dispose();
            Bitmap b = pb.Image as Bitmap;

            int listSize = list.Count();
            int x = 0;
            foreach (T item in list)
            {
                int? val = item as int?;
                if (!val.HasValue)
                    val = 0;

                b.SetPixel(x + 20, 20 + 200 - ((int)val), Color.Black);
                x++;
            }
            this.Refresh();
            Thread.Sleep(100);
            Application.DoEvents();
        }

        void ButtonClick(object sender, EventArgs e)
        {
            Button control = sender as Button;
            ISortStrategy<T> strategy = null;

            strategy = SelectStrategy(control.Name, strategy);

            IEnumerable<T> newList = Generator();
            DrawGraph(newList);
            if (strategy == null)
                return;

            strategy.UpdatedUI += new Action<IEnumerable<T>>(DrawGraph);
            strategy.Sort(newList);
        }

        private static ISortStrategy<T> SelectStrategy(string name, ISortStrategy<T> strategy)
        {
            switch (name)
            {
                case "LargeItems":
                    strategy = new MergeSorter<T>();
                    break;
                case "SmallItems":
                    strategy = new QuickSorter<T>();
                    break;
                case "ReversedList":
                    strategy = new MergeSorter<T>();
                    break;
            }
            return strategy;
        }
    }

    interface ISortStrategy<T> where T : IComparable<T>
    {
        event Action<IEnumerable<T>> UpdatedUI;
        void Sort(IEnumerable<T> input);
    }

    class MergeSorter<T> : ISortStrategy<T> where T : IComparable<T>
    {
        public event Action<IEnumerable<T>> UpdatedUI;
        List<T> aux;
        int opCount = 0;

        public void Sort(IEnumerable<T> input)
        {
            UpdatedUI(input);
            opCount++;
            List<T> sorteditems = new List<T>(input);
            aux = new List<T>(sorteditems.Count);
            for (int i = 0; i < sorteditems.Count; i++)
                aux.Add(default(T));
            MergeSort(ref sorteditems, 0, sorteditems.Count - 1);
            UpdatedUI(sorteditems);
        }

        private void Merge(ref List<T> a, int l, int m, int r)
        {
            int i;
            int j;
            for (i = m + 1; i > l; i--)
            {
                aux[i - 1] = a[i - 1];
                opCount++; 
            }
            for (j = m; j < r; j++)
            {
                aux[r + m - j] = a[j + 1];
                opCount++;
            }

            for (int k = l; k <= r; k++)
            {
                if (aux[j].CompareTo(aux[i]) == -1)
                    a[k] = aux[j--];
                else
                    a[k] = aux[i++];
                opCount++;
            }
        }

        private void MergeSort(ref List<T> a, int l, int r)
        {
            if (r <= l) return;
            int m = (r + l) / 2;
            MergeSort(ref a, l, m);

            if (opCount > 50)
            {
                UpdatedUI(a);
                opCount -= 50;
            }

            MergeSort(ref a, m+1, r);
            if (opCount > 50)
            {
                UpdatedUI(a);
                opCount -= 50; 
            }

            Merge(ref a , l,m,r);
           if (opCount > 50)
            {
                UpdatedUI(a);
                opCount -= 50; 
            }
        }

    }

    class QuickSorter<T> : ISortStrategy<T>
        where T : IComparable<T>
    {
        public event Action<IEnumerable<T>> UpdatedUI;

        int opCount = 0; 
        public void Sort(IEnumerable<T> input)
        {
            UpdatedUI(input);
            opCount++;
            List<T> sorteditems = new List<T>(input);

            QuickSort(ref sorteditems, 0, sorteditems.Count - 1);
            UpdatedUI(sorteditems);
        }

        private int Partition(ref List<T> a, int l, int r)
        {
            T tmp;
            int i = l - 1;
            int j = r;
            T v = a[r];
            for (; ; )
            {
                while (a[++i].CompareTo(v) == -1)
                {
                    opCount++;
                }
                while (j>=2 && v.CompareTo(a[--j]) == -1)
                {
                    opCount++;
                    //if(j==1)break ;//bug,因为恰当j=1,进入while循环时,就会出错!
                }
                if (i >= j) break;

                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;

                opCount++;
            }
            a[r] = a[i];
            a[i] = v;

            if (opCount > 50)
            {
                UpdatedUI(a);
                opCount -= 50;
            }
            return i;
        }

        private void QuickSort(ref List<T> a, int l, int r)
        {
            opCount++;
            if (r <= l) return;
            int i = Partition(ref a, l, r);
            QuickSort(ref a, l, i - 1);
            QuickSort(ref a, i + 1, r); 
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            //Application.EnableVisualStyles();
            //Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new StrategyView<int>(StartSetGenerator.GetStartSet));
        }
    }
}