namespace AtlasUtility
{
    using UnityEditor;
    using UnityEngine;
    using UnityEditor.SceneManagement;

    using System;
    using System.IO;
    using System.Linq;
    using System.Text;
    using System.Reflection;
    using System.Collections.Generic;

    using Random = UnityEngine.Random;

    public class AtlasUtilityWindow : EditorWindow
    {
        protected class Box
        {
            public bool Valid
            {
                get
                {
                    if (Width > 0 && Height > 0)
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }
            }

            public Vector2 LowerLeft;
            public Vector2 UpperLeft
            {
                get { return LowerLeft + new Vector2(0, Height); }
            }
            public Vector2 LowerRight
            {
                get { return LowerLeft + new Vector2(Width, 0); }
            }
            public Vector2 UpperRight
            {
                get { return LowerLeft + new Vector2(Width, Height); }
            }

            public int Width;
            public int Height;

            public Box(int width, int height, Vector2 lowerLeft)
            {
                Width = width;
                Height = height;
                LowerLeft = lowerLeft;
            }


            public bool CanFill(TextureInfo textureInfo)
            {
                if (textureInfo.Width <= Width && textureInfo.Height <= Height)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
        }

        protected class JagBox
        {
            public class Pair
            {
                public int Low;
                public int High;

                public Pair(int low, int high)
                {
                    Low = low;
                    High = high;
                }
            }

            public bool Valid
            {
                get
                {
                    if (BoxList.Count == 0)
                    {
                        return false;
                    }
                    else
                    {
                        return true;
                    }
                }
            }

            public int Width
            {
                get { return (int) BoxList.MySum(box => box.Width); }
            }

            public Vector2 UpperRight;

            public List<Box> BoxList;

            public Dictionary<Pair, Pair> XCoordDic;
            public Dictionary<Pair, Pair> YCoordDic;

            public JagBox(List<Box> boxList)
            {
                BoxList = boxList;

                if (boxList.Count == 0)
                {
                    return;
                }

                UpperRight = boxList.Back(0).UpperRight;

                XCoordDic = new Dictionary<Pair, Pair>();
                YCoordDic = new Dictionary<Pair, Pair>();

                for (int i = 0; i < boxList.Count; i++)
                {
                    Pair xPair = new Pair((int) boxList[i].LowerLeft.x, (int) boxList[i].LowerRight.x);
                    Pair yPair = new Pair((int) boxList[i].LowerLeft.y, (int) boxList[i].UpperRight.y);

                    XCoordDic.Add(yPair, xPair);
                    YCoordDic.Add(xPair, yPair);
                }
            }


            public int GetBoxIndex(int x)
            {
                x = (int) UpperRight.x - x;

                List<Pair> xPairList = YCoordDic.Keys.ToList();

                for (int i = xPairList.Count - 1; i >= 0; i--)
                {
                    if (xPairList[i].Low <= x && x <= xPairList[i].High)
                    {
                        return i;
                    }
                }

                throw new Exception("An error occured");
            }

            public bool CanFill(TextureInfo textureInfo)
            {
                if (textureInfo.Width > Width)
                {
                    return false;
                }

                int boxIndex = GetBoxIndex(textureInfo.Width);
                int boxOffset = 0;

                reLoop:

                Box sliceBox = BoxList[boxIndex + boxOffset];

                for (int i = boxIndex + boxOffset; i < BoxList.Count + boxOffset; i++)
                {
                    if (BoxList[i].Height < textureInfo.Height)
                    {
                        if (boxIndex + boxOffset > 0)
                        {
                            boxOffset--;
                            
                            goto reLoop;
                        }
                        else
                        {
                            return false;
                        }
                    }
                }

                textureInfo.SliceBox = sliceBox;
                textureInfo.BoxOffset = boxOffset;

                return true;
            }

            public List<Box> VerticalSlice(TextureInfo textureInfo, int fillWidth, int fillHeight)
            {
                fillWidth = (int) (fillWidth - (BoxList.Back(-textureInfo.BoxOffset).UpperRight.x - textureInfo.SliceBox.UpperRight.x));

                int leftBoxWidth = textureInfo.SliceBox.Width - fillWidth;
                int leftBoxHeight = textureInfo.SliceBox.Height;
                Vector2 leftBoxLowerLeft = textureInfo.SliceBox.LowerLeft;

                Box leftBox = new Box(leftBoxWidth, leftBoxHeight, leftBoxLowerLeft);

                int downBoxWidth = fillWidth;
                int downBoxHeight = textureInfo.SliceBox.Height - fillHeight;
                Vector2 downBoxLowerLeft = textureInfo.SliceBox.LowerLeft + new Vector2(textureInfo.SliceBox.Width - fillWidth, 0);

                Box downBox = new Box(downBoxWidth, downBoxHeight, downBoxLowerLeft);

                return new List<Box>() {leftBox, downBox};
            }

            public List<Box> HorizontalSlice(TextureInfo textureInfo, int fillWidth, int fillHeight)
            {
                fillWidth = (int)(fillWidth - (BoxList.Back(-textureInfo.BoxOffset).UpperRight.x - textureInfo.SliceBox.UpperRight.x));

                int leftBoxWidth = textureInfo.SliceBox.Width - fillWidth;
                int leftBoxHeight = fillHeight;
                Vector2 leftBoxLowerLeft = textureInfo.SliceBox.LowerLeft + new Vector2(0, textureInfo.SliceBox.Height - fillHeight);

                Box leftBox = new Box(leftBoxWidth, leftBoxHeight, leftBoxLowerLeft);

                int downBoxWidth = textureInfo.SliceBox.Width;
                int downBoxHeight = textureInfo.SliceBox.Height - fillHeight;
                Vector2 downBoxLowerLeft = textureInfo.SliceBox.LowerLeft;

                Box downBox = new Box(downBoxWidth, downBoxHeight, downBoxLowerLeft);

                return new List<Box>() { leftBox, downBox };
            }

            public List<JagBox> Fill(TextureInfo textureInfo)
            {
                textureInfo.LowerLeft = BoxList.Back(-textureInfo.BoxOffset).UpperRight + new Vector2(-textureInfo.Width, -textureInfo.Height);


                int fillWidth = textureInfo.Width;
                int fillHeight = textureInfo.Height;

                bool verticalSlice = fillWidth > fillHeight;

                List<Box> childBoxList = verticalSlice ? VerticalSlice(textureInfo, fillWidth, fillHeight) : HorizontalSlice(textureInfo, fillWidth, fillHeight);

                List<Box> leftBoxList = new List<Box>();
                List<Box> downBoxList = new List<Box>();

                for (int i = 0; i < BoxList.IndexOf(textureInfo.SliceBox); i++)
                {
                    leftBoxList.Add(BoxList[i]);
                }

                if (childBoxList[0].Valid)
                {
                    leftBoxList.Add(childBoxList[0]);
                }

                if (childBoxList[1].Valid)
                {
                    downBoxList.Add(childBoxList[1]);
                }

                for (int i = BoxList.IndexOf(textureInfo.SliceBox) + 1; i < BoxList.Count + textureInfo.BoxOffset; i++)
                {
                    downBoxList.Add(new Box(BoxList[i].Width, BoxList[i].Height - fillHeight, BoxList[i].LowerLeft));
                }


                JagBox leftJagBox = new JagBox(leftBoxList);
                JagBox downJagBox = new JagBox(downBoxList);

                List<JagBox> jagBoxList = new List<JagBox>();

                if (downJagBox.Valid)
                {
                    jagBoxList.Add(downJagBox);
                }

                if (leftJagBox.Valid)
                {
                    jagBoxList.Add(leftJagBox);
                }

                return jagBoxList;
            }
        }

        protected class TextureInfo
        {
            public int Max
            {
                get
                {
                    if (Width > Height)
                    {
                        return Width;
                    }
                    else
                    {
                        return Height;
                    }
                }
            }
            public int Area
            {
                get { return Width*Height; }
            }
            public string Name
            {
                get { return Texture.name; }
            }

            public Rect Rect
            {
                get { return new Rect(LowerLeft.x + Padding, LowerLeft.y + Padding, Width - 2*Padding, Height - 2*Padding); }
            }
            public Vector2 LowerLeft;
            public Vector2 UpperLeft
            {
                get { return LowerLeft + new Vector2(0, Height); }
            }
            public Vector2 LowerRight
            {
                get { return LowerLeft + new Vector2(Width, 0); }
            }
            public Vector2 UpperRight
            {
                get { return LowerLeft + new Vector2(Width, Height); }
            }

            public Color[] Colors;
            public Vector4 Pivot;
            public Vector4 Border;

            public int BoxOffset;
            public Box SliceBox;

            public int Width;
            public int Height;
            public int RawWidth;
            public int RawHeight;
            public int Padding;
            public string GUID;

            public Texture2D Texture;

            public TextureInfo(int padding, Texture2D texture2D, int width, int height)
            {
                Width = width + padding*2;
                Height = height + padding*2;
                Padding = padding;
                Texture = texture2D;
            }

            public TextureInfo(int padding, Texture2D texture2D)
            {
                Initialize(padding, texture2D);
            }

            public void Initialize(int padding, Texture2D texture2D)
            {
                Texture = texture2D;

                string assetPath = AssetDatabase.GetAssetPath(texture2D);

                TextureImporter textureImporter = (TextureImporter)AssetImporter.GetAtPath(assetPath);

                Pivot = textureImporter.spritePivot;
                Border = textureImporter.spriteBorder;
                GUID = AssetDatabase.AssetPathToGUID(assetPath);

                RawWidth = Texture.width;
                RawHeight = Texture.height;

                object[] args = new object[2];

                MethodInfo methodInfo = typeof(TextureImporter).GetMethod("GetWidthAndHeight", BindingFlags.NonPublic | BindingFlags.Instance);

                methodInfo.Invoke(textureImporter, args);

                int originWidth = (int)args[0];
                int originHeight = (int)args[1];

                if (RawWidth < originWidth || RawHeight < originHeight)
                {
                    Debug.LogWarning($"Note {texture2D.name} was scaled down");
                }

                if (!textureImporter.isReadable)
                {
                    textureImporter.isReadable = true;

                    textureImporter.SaveAndReimport();
                }

                Colors = texture2D.GetPixels(0, 0, RawWidth, RawHeight);


                Width = RawWidth + padding * 2;
                Height = RawHeight + padding * 2;
                Padding = padding;
            }


            public static float max(TextureInfo textureInfo)
            {
                return textureInfo.Max;
            }

            public static bool SortByMax(TextureInfo a, TextureInfo b)
            {
                if (a.Max < b.Max)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }

            public static bool SortByWidth(TextureInfo a, TextureInfo b)
            {
                if (a.Width < b.Width)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
        }

        protected class Parameter
        {
            public int Padding;
            public int TextureSize;
            public string Path;
            public PackPlan PackPlan;
            public Texture2D SpriteSheet;

            public List<Texture2D> TextureList;
            public List<AtlasUtility.VirtualTexture> VirtualTextureList;
        }

        protected class Atlas
        {
            public int Width;
            public int Height;
            public string AssetBundleName;
            public string AssetBundleVariant;

            public List<TextureInfo> TextureInfoList;

            public void Create(int index, Parameter parameter)
            {
                SpriteMetaData[] spriteMetaDatas = new SpriteMetaData[TextureInfoList.Count];

                Color[] atlasColors = new Color[Width * Height];

                for (int i = 0; i < Height; i++)
                {
                    for (int j = 0; j < Width; j++)
                    {
                        atlasColors[i * Width + j] = new Color(0, 0, 0, 0);
                    }
                }

                for (int i = 0; i < TextureInfoList.Count; i++)
                {
                    TextureInfo textureInfo = TextureInfoList[i];

                    Vector2 lowerLeft = textureInfo.LowerLeft + new Vector2(parameter.Padding, parameter.Padding);

                    int width;
                    int height;

                    spriteMetaDatas[i].rect = textureInfo.Rect;
                    spriteMetaDatas[i].pivot = textureInfo.Pivot;
                    spriteMetaDatas[i].name = textureInfo.Name;
                    spriteMetaDatas[i].border = textureInfo.Border;
                    spriteMetaDatas[i].alignment = (int)SpriteAlignment.Custom;

                    width = textureInfo.Width - parameter.Padding * 2;
                    height = textureInfo.Height - parameter.Padding * 2;

                    for (int j = 0; j < height; j++)
                    {
                        for (int k = 0; k < width; k++)
                        {
                            int row = (int)lowerLeft.y + j;
                            int column = (int)lowerLeft.x + k;

                            atlasColors[row * Width + column] = textureInfo.Colors[j * width + k];
                        }
                    }
                }

                string path;

                if (index == 0)
                {
                    path = parameter.Path + ".png";
                }
                else
                {
                    path = $"{parameter.Path} ({index}).png";
                }

                if (File.Exists(path))
                {
                    TextureImporter importer = (TextureImporter)AssetImporter.GetAtPath(path);

                    AssetBundleName = importer.assetBundleName;
                    AssetBundleVariant = importer.assetBundleVariant;

                    AssetDatabase.DeleteAsset(path);

                    AssetDatabase.Refresh();
                }

                Texture2D texture2D = new Texture2D(Width, Height, TextureFormat.RGBA32, false);

                texture2D.SetPixels(0, 0, Width, Height, atlasColors);

                texture2D.Apply();

                File.WriteAllBytes(path, texture2D.EncodeToPNG());

                AssetDatabase.ImportAsset(path);


                TextureImporter textureImporter = (TextureImporter)AssetImporter.GetAtPath(path);

                if (!string.IsNullOrEmpty(AssetBundleName))
                {
                    textureImporter.assetBundleName = AssetBundleName;
                }

                if (!string.IsNullOrEmpty(AssetBundleVariant))
                {
                    textureImporter.assetBundleVariant = AssetBundleVariant;
                }

                textureImporter.spritesheet = spriteMetaDatas;
                textureImporter.maxTextureSize = Mathf.Max(Width, Height);
                textureImporter.isReadable = true;
                textureImporter.alphaIsTransparency = true;
                textureImporter.textureType = TextureImporterType.Sprite;
                textureImporter.spriteImportMode = SpriteImportMode.Multiple;

                textureImporter.SaveAndReimport();


                string atlasGUID = AssetDatabase.AssetPathToGUID(path);

                List<string> newAtlasReferenceList = new List<string>();
                List<string> newSourceReferenceList = new List<string>();

                for (int i = 0; i < spriteMetaDatas.Length; i++)
                {
                    newAtlasReferenceList.Add($"fileID: {21300000 + i * 2}, guid: {atlasGUID}");
                    newSourceReferenceList.Add($"fileID: {21300000}, guid: {TextureInfoList[i].GUID}");
                }

                List<string> fromReferenceList = new List<string>();
                List<string> toReferenceList = new List<string>();

                List<string> itemList = ReferenceTable.ReadAllLine();

                for (int i = 0; i < itemList.Count; i++)
                {
                    itemList[i] = itemList[i].TrimEnd((char)13);

                    string atlasReference = itemList[i].Split('|')[0];
                    string sourceReference = itemList[i].Split('|')[1];

                    for (int j = 0; j < newSourceReferenceList.Count; j++)
                    {
                        if (newSourceReferenceList[j] == sourceReference)
                        {
                            fromReferenceList.Add(atlasReference);
                            toReferenceList.Add(newAtlasReferenceList[j]);
                        }
                    }
                }

                for (int i = 0; i < newSourceReferenceList.Count; i++)
                {
                    fromReferenceList.Add(newSourceReferenceList[i]);
                    toReferenceList.Add(newAtlasReferenceList[i]);
                }

                List<string> newItemList = new List<string>();

                for (int i = 0; i < itemList.Count; i++)
                {
                    newItemList.Add(itemList[i]);
                }

                for (int i = 0; i < newAtlasReferenceList.Count; i++)
                {
                    newItemList.Add($"{newAtlasReferenceList[i]}|{newSourceReferenceList[i]}");
                }

                ReferenceTable.WriteAllLine(newItemList);
            }
        }

        #region Variable

        protected Vector2 ScrollPosition;
        protected GUIStyle TitleGuiStyle;

        protected int AntiCrush;
        protected AtlasUtility Script;
        protected SerializedObject SerializedObject;

        protected SerializedProperty PackSize;

        protected SerializedProperty PackPath;
        protected SerializedProperty PackName;
        protected SerializedProperty PackPadding;

        protected SerializedProperty SlicePath;
        protected SerializedProperty SlicePadding;

        protected SerializedProperty atlas;
        protected SerializedProperty Target;
        protected SerializedProperty TextureList;
        protected SerializedProperty SpriteSheet;
        protected SerializedProperty VirtualTextureList;

        protected SerializedProperty PackPlan;

        #endregion

        public void OnEnable()
        {
            Script = GetAtlasUtility();
            SerializedObject = new SerializedObject(Script);

            PackSize = SerializedObject.FindProperty("PackSize");

            PackPath = SerializedObject.FindProperty("PackPath");
            PackName = SerializedObject.FindProperty("PackName");

            SlicePath = SerializedObject.FindProperty("SlicePath");
            SlicePadding = SerializedObject.FindProperty("SlicePadding");

            atlas = SerializedObject.FindProperty("Atlas");
            Target = SerializedObject.FindProperty("Target");
            TextureList = SerializedObject.FindProperty("TextureList");
            SpriteSheet = SerializedObject.FindProperty("SpriteSheet");
            PackPadding = SerializedObject.FindProperty("PackPadding");
            VirtualTextureList = SerializedObject.FindProperty("VirtualTextureList");

            PackPlan = SerializedObject.FindProperty("PackPlan");

            TitleGuiStyle = new GUIStyle();
            TitleGuiStyle.fontSize = 20;
            TitleGuiStyle.alignment = TextAnchor.MiddleCenter;
            TitleGuiStyle.normal.textColor = new Color(0.75f, 0.75f, 0.75f, 1);
        }

        [MenuItem("DashGame/AtlasUtility")]
        public static void ShowWindow()
        {
            Type inspectorType = Type.GetType("UnityEditor.InspectorWindow,UnityEditor.dll");

            AtlasUtilityWindow window = GetWindow<AtlasUtilityWindow>(inspectorType);

            window.titleContent = new GUIContent("AtlasUtility");
            window.Show();
        }

        public static AtlasUtility GetAtlasUtility()
        {
            foreach (var path in Directory.GetFiles(Application.dataPath, "*SerializeObject.prefab", SearchOption.AllDirectories))
            {
                AtlasUtility atlasUtility = AssetDatabase.LoadAssetAtPath<GameObject>(path.GetRelativePath()).GetComponent<AtlasUtility>();

                if (atlasUtility != null)
                {
                    return atlasUtility;
                }
            }

            throw new Exception();
        }


        protected void Pack()
        {
            Parameter parameter = CreatePackParameter();

            List<TextureInfo> textureInfoList = GetTextureInfoList(parameter);

            if (textureInfoList.Count == 0)
            {
                throw new Exception("TextureList is empty");
            }

            EditorUtility.DisplayProgressBar("Packing", "Calculate layout", 0.5f);

            List<Atlas> atlasList = new List<Atlas>();

            while (true)
            {
                Box box = CreateBox(parameter, textureInfoList);

                textureInfoList = FillBox(box, parameter, textureInfoList, atlasList);

                if (textureInfoList.Count == 0)
                {
                    break;
                }
            }
            
            if (EditorUtility.DisplayDialog("AtlasUtility", $"{atlasList.Count} atlas will be created", "Go ahead", "Cancel"))
            {
                for (int i = 0; i < atlasList.Count; i++)
                {
                    EditorUtility.DisplayProgressBar("Packing", "Create atlas", (i + 1)/(float) atlasList.Count);

                    atlasList[i].Create(i, parameter);
                }
            }

            EndPack();
        }

        protected void EndPack()
        {
            EditorUtility.ClearProgressBar();
        }

        protected Parameter CreatePackParameter()
        {
            string directory = Script.PackPath.TrimEnd('/', '\\') + "/";

            if (directory.Length < 6 || directory.Substring(0, 6).ToLower() != "assets")
            {
                throw new Exception("PackPath must be inside the Assets folder");
            }

            if (!Directory.Exists(directory))
            {
                throw new Exception("directory doesn't exist");
            }

            if (string.IsNullOrEmpty(Script.PackName) || Script.PackName.Any(Path.GetInvalidFileNameChars().Contains))
            {
                throw new Exception("PackName is invalid");
            }

            if (Script.PackPadding < 0)
            {
                Script.PackPadding = 0;
            }

            if (Script.PackPlan == global::AtlasUtility.PackPlan.Fixed)
            {
                if (Script.PackSize <= 2)
                {
                    throw new Exception("Size of atlas must be equal or greater than 2");
                }

                if (!Mathf.IsPowerOfTwo(Script.PackSize))
                {
                    throw new Exception("Size of atlas must be power of 2");
                }
            }
            else if (Script.PackPlan == global::AtlasUtility.PackPlan.Smallest)
            {
                if (Script.PackSize <= 0)
                {
                    Script.PackSize = 8192;
                }
                else
                {
                    Script.PackSize = ExMath.PrevPOT(Script.PackSize);
                }
            }

            for (int i = 0; i < Script.TextureList.Count; i++)
            {
                for (int j = i+1; j < Script.TextureList.Count; j++)
                {
                    if (Script.TextureList[i].name == Script.TextureList[j].name)
                    {
                        Debug.LogWarning($"发现名字相同的图片 {Script.TextureList[i].name}");
                    }
                }
            }

            Parameter parameter = new Parameter
            {
                Path = directory + Script.PackName,
                PackPlan = Script.PackPlan,
                Padding = Script.PackPadding,
                TextureSize = Script.PackSize,
                TextureList = Script.TextureList,
                VirtualTextureList = Script.VirtualTextureList
            };

            return parameter;
        }

        protected List<TextureInfo> GetTextureInfoList(Parameter parameter)
        {
            List<TextureInfo> textureInfoList = new List<TextureInfo>();

            for (int i = 0; i < parameter.TextureList.Count; i++)
            {
                if (parameter.TextureList[i] != null)
                {
                    EditorUtility.DisplayProgressBar("Packing", "Read textures", (i + 1)/(float) parameter.TextureList.Count);

                    textureInfoList.Add(new TextureInfo(parameter.Padding, parameter.TextureList[i]));
                }
            }

            for (int i = 0; i < parameter.VirtualTextureList.Count; i++)
            {
                Texture2D texture = new Texture2D(parameter.VirtualTextureList[i].Width, parameter.VirtualTextureList[i].Height);
                texture.name = parameter.VirtualTextureList[i].Name;

                Color randomColor = new Color(Random.Range(0f, 1f), Random.Range(0f, 1f), Random.Range(0f, 1f), 1);

                for (int j = 0; j < parameter.VirtualTextureList[i].Width; j++)
                {
                    for (int k = 0; k < parameter.VirtualTextureList[i].Height; k++)
                    {
                        texture.SetPixel(j, k, randomColor);
                    }
                }

                texture.Apply();

                textureInfoList.Add(new TextureInfo(parameter.Padding, texture, parameter.VirtualTextureList[i].Width, parameter.VirtualTextureList[i].Height));
            }

            EditorUtility.ClearProgressBar();

            return textureInfoList;
        }

        protected Box CreateBox(Parameter parameter, List<TextureInfo> textureInfoList)
        {
            int maxTextureLength = (int) textureInfoList.MyMax(TextureInfo.max);

            if (maxTextureLength > parameter.TextureSize)
            {
                EndPack();

                throw new Exception("A texture's width or height is bigger than Size/MaxSize");
            }

            if (parameter.PackPlan == global::AtlasUtility.PackPlan.Fixed)
            {
                return new Box(parameter.TextureSize, parameter.TextureSize, new Vector2(0, 0));
            }
            else if (parameter.PackPlan == global::AtlasUtility.PackPlan.Smallest)
            {
                int totalArea = textureInfoList.Sum(debris => debris.Area);

                int length = ExMath.NextPOT(Mathf.Sqrt(totalArea));

                length = Mathf.Min(length, parameter.TextureSize);

                length = Mathf.Max(length, maxTextureLength);

                if (length* length/2f >= totalArea)
                {
                    return new Box(length, length/2, new Vector2(0, 0));
                }
                else
                {
                    return new Box(length, length, new Vector2(0, 0));
                }
            }
            else
            {
                throw new Exception();
            }
        }

        protected List<JagBox> CreateJagBox(List<Box> emptyBoxList)
        {
            List<JagBox> jagBoxList = new List<JagBox>();

            if (emptyBoxList.Count == 0)
            {
                return jagBoxList;
            }

            List<Box> boxList = new List<Box>() { emptyBoxList[0] };

            for (int i = 0; i < emptyBoxList.Count - 1; i++)
            {
                int x1 = (int)emptyBoxList[i].LowerRight.x;
                int x2 = (int)emptyBoxList[i + 1].LowerLeft.x;

                if (x1 == x2)
                {
                    boxList.Add(emptyBoxList[i + 1]);
                }
                else
                {
                    jagBoxList.Add(new JagBox(boxList));

                    boxList = new List<Box>();

                    boxList.Add(emptyBoxList[i + 1]);
                }
            }

            jagBoxList.Add(new JagBox(boxList));

            return jagBoxList;
        }

        protected List<TextureInfo> FillBox(Box box, Parameter parameter, List<TextureInfo> textureInfoList, List<Atlas> atlasList)
        {
            textureInfoList.MySort(TextureInfo.SortByWidth);

            while (true)
            {
                List<Box> emptyBoxList = new List<Box>();
                List<TextureInfo> atlasTextureInfoList = new List<TextureInfo>();
                List<TextureInfo> remainTexureInfoList = new List<TextureInfo>(textureInfoList);

                FillChildBox(box, remainTexureInfoList, atlasTextureInfoList, emptyBoxList);

                List<JagBox> jagBoxList = CreateJagBox(emptyBoxList);

                remainTexureInfoList.MySort(TextureInfo.SortByMax);

                FillJagBox(remainTexureInfoList, atlasTextureInfoList, jagBoxList);

                if (remainTexureInfoList.Count == 0)
                {
                    atlasList.Add(CreateAtlas(box, atlasTextureInfoList));

                    return remainTexureInfoList;
                }
                else
                {
                    if (box.Width > box.Height)
                    {
                        box = new Box(box.Height, box.Width, Vector2.zero);
                    }
                    else if (box.Height > box.Width)
                    {
                        box = new Box(box.Height, box.Height, Vector2.zero);
                    }
                    else if (box.Width == box.Height)
                    {
                        int newLength = ExMath.NextPOT(box.Width + 1);

                        if (newLength > parameter.TextureSize)
                        {
                            atlasList.Add(CreateAtlas(box, atlasTextureInfoList));

                            return remainTexureInfoList;
                        }
                        else
                        {
                            box = new Box(newLength, newLength/2, Vector2.zero);
                        }
                    }
                }
            }
        }

        protected void FillChildBox(Box box, List<TextureInfo> remainTextureInfoList, List<TextureInfo> atlasTextureInfoList, List<Box> emptyBoxList)
        {
            if (box.Valid)
            {
                for (int i = 0; i < remainTextureInfoList.Count; i++)
                {
                    if (box.CanFill(remainTextureInfoList[i]))
                    {
                        TextureInfo textureInfo = remainTextureInfoList[i];

                        remainTextureInfoList.Remove(textureInfo);

                        textureInfo.LowerLeft = box.LowerLeft;

                        atlasTextureInfoList.Add(textureInfo);


                        Vector2 lowerLeftUp = box.LowerLeft + new Vector2(0, textureInfo.Height);
                        Vector2 lowerLeftRight = box.LowerLeft + new Vector2(textureInfo.Width, 0);

                        Box upChildBox = new Box(textureInfo.Width, box.Height - textureInfo.Height, lowerLeftUp);
                        Box rightChildBox = new Box(box.Width - textureInfo.Width, box.Height, lowerLeftRight);
                        
                        FillChildBox(upChildBox, remainTextureInfoList, atlasTextureInfoList, emptyBoxList);
                        FillChildBox(rightChildBox, remainTextureInfoList, atlasTextureInfoList, emptyBoxList);

                        return;
                    }
                }

                emptyBoxList.Add(box);
            }
        }

        protected void FillJagBox(List<TextureInfo> remainTextureInfoList, List<TextureInfo> atlasTextureInfoList, List<JagBox> jagBoxList)
        {
            for (int i = 0; i < jagBoxList.Count; i++)
            {
                for (int j = 0; j < remainTextureInfoList.Count; j++)
                {
                    if (jagBoxList[i].CanFill(remainTextureInfoList[j]))
                    {
                        jagBoxList.AddRange(jagBoxList[i].Fill(remainTextureInfoList[j]));

                        atlasTextureInfoList.Add(remainTextureInfoList[j]);

                        remainTextureInfoList.Remove(remainTextureInfoList[j]);

                        break;
                    }
                }
            }
        }

        protected Atlas CreateAtlas(Box box, List<TextureInfo> textureInfoList)
        {
            Atlas atlas = new Atlas
            {
                Width = box.Width,
                Height = box.Height,
                TextureInfoList = textureInfoList,
            };

            return atlas;
        }


        protected void CollectDebugInfo()
        {
            Parameter parameter = CreateDebugParameter();

            List<TextureInfo> debrisList = GetTextureInfoList(parameter);

            StringBuilder stringBuilder = new StringBuilder();

            for (int i = 0; i < debrisList.Count; i++)
            {
                stringBuilder.AppendLine($"Width:{debrisList[i].Width} Height:{debrisList[i].Height} Pivot:{debrisList[i].Pivot} Border:{debrisList[i].Border}");
            }

            if (string.IsNullOrEmpty(stringBuilder.ToString()))
            {
                throw new Exception("TextureList is empty");
            }
            else
            {
                StreamWriter streamWriter = new StreamWriter(parameter.Path);

                streamWriter.WriteLine(Application.unityVersion);

                streamWriter.Write(stringBuilder.ToString());

                streamWriter.Close();

                AssetDatabase.ImportAsset(parameter.Path);
            }
        }

        protected Parameter CreateDebugParameter()
        {
            string directory = Script.PackPath.TrimEnd('/', '\\') + "/";

            if (directory.Length < 6 || directory.Substring(0, 6).ToLower() != "assets")
            {
                throw new Exception("PackPath must be inside the Assets folder");
            }

            if (!Directory.Exists(directory))
            {
                throw new Exception("directory doesn't exist");
            }

            Parameter parameter = new Parameter
            {
                Path = directory + "DebugInfo_" + Script.PackName + ".txt",
                TextureList = Script.TextureList,
                VirtualTextureList = Script.VirtualTextureList
            };

            return parameter;
        }


        protected void Slice()
        {
            Parameter parameter = CreateSliceParameter();

            string spriteSheetPath = AssetDatabase.GetAssetPath(parameter.SpriteSheet);

            TextureImporter textureImporter = (TextureImporter)AssetImporter.GetAtPath(spriteSheetPath);

            if (textureImporter.spritesheet.Length == 0)
            {
                throw new Exception("There is no child sprite");
            }

            if (!textureImporter.isReadable)
            {
                textureImporter.isReadable = true;
                textureImporter.SaveAndReimport();
            }

            for (int k = 0; k < textureImporter.spritesheet.Length; k++)
            {
                SpriteMetaData metaData = textureImporter.spritesheet[k];

                EditorUtility.DisplayProgressBar("Slicing", $"Create {metaData.name}", (k + 1)/(float) textureImporter.spritesheet.Length);

                int width = (int)metaData.rect.width + 2 * parameter.Padding;
                int height = (int)metaData.rect.height + 2 * parameter.Padding;

                Texture2D texture2D = new Texture2D(width, height, TextureFormat.RGBA32, false);

                Color[] atlasColors = parameter.SpriteSheet.GetPixels((int)metaData.rect.x, (int)metaData.rect.y, (int)metaData.rect.width, (int)metaData.rect.height);

                Color[] textureColors = new Color[width * height];

                for (int i = 0; i < height; i++)
                {
                    for (int j = 0; j < width; j++)
                    {
                        if (i < parameter.Padding || j < parameter.Padding || i >= height - parameter.Padding || j >= width - parameter.Padding)
                        {
                            textureColors[i * width + j] = new Color(0, 0, 0, 0);
                        }
                        else
                        {
                            int x = i - parameter.Padding;
                            int y = j - parameter.Padding;

                            textureColors[i * width + j] = atlasColors[x * (int)metaData.rect.width + y];
                        }
                    }
                }

                texture2D.SetPixels(textureColors);

                texture2D.Apply();

                string spritePath = (parameter.Path + metaData.name + ".png").GetUnRepeatFileName();

                File.WriteAllBytes(spritePath, texture2D.EncodeToPNG());

                AssetDatabase.ImportAsset(spritePath);


                TextureImporter importer = (TextureImporter)AssetImporter.GetAtPath(spritePath);

                TextureImporterSettings importerSetting = new TextureImporterSettings();

                importer.ReadTextureSettings(importerSetting);

                importerSetting.textureType = TextureImporterType.Sprite;
                importerSetting.spritePivot = metaData.pivot;
                importerSetting.spriteBorder = metaData.border;
                importerSetting.spriteAlignment = metaData.alignment;
                importerSetting.alphaIsTransparency = true;

                importer.SetTextureSettings(importerSetting);

                importer.isReadable = true;
                importer.name = metaData.name;
                importer.spriteImportMode = SpriteImportMode.Single;
                importer.maxTextureSize = ExMath.NextPOT(Mathf.Max(width, height));

                importer.SaveAndReimport();
            }

            EditorUtility.ClearProgressBar();
        }

        protected Parameter CreateSliceParameter()
        {
            string directory = Script.SlicePath.TrimEnd('/', '\\') + "/";

            if (!Directory.Exists(directory))
            {
                throw new Exception("directory doesn't exist");
            }

            if (Script.SlicePadding < 0)
            {
                Script.SlicePadding = 0;
            }

            if (Script.SpriteSheet == null)
            {
                throw new Exception("SpriteSheet is null");
            }

            Parameter parameter = new Parameter
            {
                Path = directory,
                Padding = Script.SlicePadding,
                SpriteSheet = Script.SpriteSheet
            };

            return parameter;
        }


        protected void GetSelectedPath(ref string value)
        {
            if (Selection.assetGUIDs.Length > 0)
            {
                string path = AssetDatabase.GUIDToAssetPath(Selection.assetGUIDs[0]);

                path = Path.GetDirectoryName(path);

                if (string.IsNullOrEmpty(path))
                {
                    value = "Assets";
                }
                else
                {
                    value = path;
                }
            }
        }


        public void OnGUI()
        {     
            SerializedObject.Update();
            
            ScrollPosition = EditorGUILayout.BeginScrollView(ScrollPosition);

            DrawPackArea();

            DrawSliceArea();

            DrawSearchReferenceArea();

            DrawSetReferenceArea();

            DrawDebugArea();

            SerializedObject.ApplyModifiedProperties();
        }

        public void DrawPackArea()
        {
            EditorGUILayout.LabelField("AtlasUtility", TitleGuiStyle, GUILayout.Height(30));

            EditorGUILayout.BeginHorizontal();

            EditorGUILayout.PropertyField(PackPath);

            if (GUILayout.Button("UseSelectedPath"))
            {
                GetSelectedPath(ref Script.PackPath);
            }

            EditorGUILayout.EndHorizontal();

            EditorGUILayout.PropertyField(PackName);
            EditorGUILayout.PropertyField(PackPlan, new GUIContent("Pack Plan"));

            if (Script.PackPlan == global::AtlasUtility.PackPlan.Fixed)
            {
                EditorGUILayout.PropertyField(PackSize, new GUIContent("Size"));
            }
            else if (Script.PackPlan == global::AtlasUtility.PackPlan.Smallest)
            {
                EditorGUILayout.PropertyField(PackSize, new GUIContent("Max Size"));
            }

            EditorGUILayout.Separator();

            EditorGUILayout.PropertyField(atlas);

            if (Script.Atlas != null)
            {
                List<string> childPathList = ReferenceManager.GetChildPathList(AssetDatabase.GetAssetPath(Script.Atlas));

                for (int i = 0; i < childPathList.Count; i++)
                {
                    Script.TextureList.Add(AssetDatabase.LoadAssetAtPath<Texture2D>(childPathList[i]));
                }

                Script.Atlas = null;
            }

            EditorGUILayout.PropertyField(PackPadding, new GUIContent("Padding"));
            EditorGUILayout.PropertyField(TextureList, true);

            if (GUILayout.Button("Pack", GUILayout.Height(30)))
            {
                Pack();
            }

            EditorGUILayout.Separator();
        }

        public void DrawSliceArea()
        {
            EditorGUILayout.Separator();

            EditorGUILayout.PropertyField(SlicePadding, new GUIContent("Padding"));

            EditorGUILayout.BeginHorizontal();

            EditorGUILayout.PropertyField(SlicePath);

            if (GUILayout.Button("UseSelectedPath"))
            {
                GetSelectedPath(ref Script.SlicePath);
            }

            EditorGUILayout.EndHorizontal();

            EditorGUILayout.PropertyField(SpriteSheet);

            if (GUILayout.Button("Slice", GUILayout.Height(30)))
            {
                Slice();
            }

            EditorGUILayout.Separator();
        }

        public void DrawSearchReferenceArea()
        {
            EditorGUILayout.Separator();

            EditorGUILayout.PropertyField(Target);

            if (GUILayout.Button("SearchReference", GUILayout.Height(30)))
            {
                ReferenceManager.FindReference(AssetDatabase.GetAssetPath(Script.Target));
            }

            EditorGUILayout.Separator();
        }

        public void DrawSetReferenceArea()
        {
            EditorGUILayout.Separator();

            if (GUILayout.Button("ChangeReference", GUILayout.Height(30)))
            {
                ReferenceManager.ChangeAllReference();
            }

            EditorGUILayout.Separator();

            EditorGUILayout.Separator();

            if (GUILayout.Button("ResetAllReference", GUILayout.Height(30)))
            {
                ReferenceManager.ResetAllReference();
            }

            EditorGUILayout.Separator();
        }

        public void DrawDebugArea()
        {
            EditorGUILayout.Separator();

            if (GUILayout.Button("CollectDebugInfo", GUILayout.Height(30)))
            {
                CollectDebugInfo();
            }

            EditorGUILayout.EndScrollView();
        }
    }
}