text:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using Microsoft.Msagl.Core.DataStructures;
using Microsoft.Msagl.Core.Geometry;
using Microsoft.Msagl.Core.Geometry.Curves;
using Microsoft.Msagl.Core.Layout;
using Microsoft.Msagl.Core.ProjectionSolver;
using Microsoft.Msagl.DebugHelpers;
using Microsoft.Msagl.Routing.Visibility;

namespace Microsoft.Msagl.Routing.Rectilinear.Nudging {
    /// <summary>
    /// following paper "Orthogonal Connector Routing" which is included in the project
    /// </summary>
#if TEST_MSAGL
    public
#else
        internal
#endif
    class Nudger {

        bool HasGroups {
            get { return (null != HierarchyOfGroups) && (HierarchyOfGroups.Count > 0); }
        }

        Dictionary<AxisEdge, Polyline> axisEdgesToObstaclesTheyOriginatedFrom;

        List<Path> Paths { get; set; }

        IEnumerable<Polyline> Obstacles { get; set; }
        internal VisibilityGraph PathVisibilityGraph { get; set; }

        /// <summary>
        ///  "nudge" paths to decrease the number of intersections and stores the results inside WidePaths of "paths"
        /// </summary>
        /// <param name="paths">paths through the graph</param>
        /// <param name="cornerFitRad">two parallel paths should be separated by this distance if it is feasible</param>
        /// <param name="obstacles">polygonal convex obstacles organized in a tree; the obstacles here are padded original obstacles</param>
        /// <param name="ancestorsSets"></param>
        /// <returns></returns>
        internal Nudger(IEnumerable<Path> paths, double cornerFitRad, IEnumerable<Polyline> obstacles,
            Dictionary<Shape, Set<Shape>> ancestorsSets) {
            AncestorsSets = ancestorsSets;
            HierarchyOfGroups = RectangleNode<Shape>.CreateRectangleNodeOnEnumeration(
                    ancestorsSets.Keys.Where(shape => shape.IsGroup).Select(group => new RectangleNode<Shape>(group, group.BoundingBox)));
            Obstacles = obstacles;
            EdgeSeparation = 2 * cornerFitRad;
            Paths = new List<Path>(paths);
            HierarchyOfObstacles =
                RectangleNode<Polyline>.CreateRectangleNodeOnEnumeration(
                    obstacles.Select(p => new RectangleNode<Polyline>(p, p.BoundingBox)));
            MapPathsToTheirObstacles();
        }

        Dictionary<Shape, Set<Shape>> AncestorsSets { get; set; }

        void MapPathsToTheirObstacles() {
            PathToObstacles = new Dictionary<Path, Tuple<Polyline, Polyline>>();
            foreach (var path in Paths)
                MapPathToItsObstacles(path);
        }

        void MapPathToItsObstacles(Path path) {
            var startNode = HierarchyOfObstacles.FirstHitNode(path.PathPoints.First(),ObstacleTest);
            var endNode = HierarchyOfObstacles.FirstHitNode(path.PathPoints.Last(), ObstacleTest);
            if ((null != startNode) && (null != endNode)) {
                PathToObstacles[path] = new Tuple<Polyline, Polyline>(startNode.UserData, endNode.UserData);
            }
        }

        static HitTestBehavior ObstacleTest(Point pnt, Polyline polyline) {
            return (Curve.PointRelativeToCurveLocation(pnt, polyline) !=
                                                   PointLocation.Outside)
                                                      ? HitTestBehavior.Stop
                                                      : HitTestBehavior.Continue;
        }
        /// <summary>
        ///
        /// </summary>
        protected RectangleNode<Polyline> HierarchyOfObstacles { get; set; }
        /// <summary>
        ///
        /// </summary>
        protected RectangleNode<Shape> HierarchyOfGroups { get; set; }

        internal void Calculate(Directions direction, bool mergePaths) {
            NudgingDirection = direction;
            PathRefiner.RefinePaths(Paths, mergePaths);
           // ShowPathsDebug(Paths);
            GetPathOrdersAndPathGraph();
            MapAxisEdgesToTheirObstacles();
            DrawPaths();
            //ShowPathsDebug(Paths);
        }

        void MapAxisEdgesToTheirObstacles() {
            axisEdgesToObstaclesTheyOriginatedFrom = new Dictionary<AxisEdge, Polyline>();
            foreach (var path in Paths)
                MapPathEndAxisEdgesToTheirObstacles(path);

            //The assignment above was too greedy. An edge belonging to interiour edges of some path can be marked by mistake.
            foreach (var path in Paths)
                UmmapPathInteriourFromStrangerObstacles(path);
        }

        void UmmapPathInteriourFromStrangerObstacles(Path path) {
            var firstUnmappedEdge = FindFirstUnmappedEdge(path);
            if(firstUnmappedEdge==null) return;
            var lastUnmappedEdge = FindLastUnmappedEdge(path);
            for (var edge = firstUnmappedEdge; edge != null && edge != lastUnmappedEdge; edge = edge.Next)
                axisEdgesToObstaclesTheyOriginatedFrom.Remove(edge.AxisEdge);
        }

        PathEdge FindLastUnmappedEdge(Path path) {
            for (var edge = path.LastEdge; edge != null; edge = edge.Prev)
                if (edge.AxisEdge.Direction != NudgingDirection)
                    return edge;
            return null;
        }

        PathEdge FindFirstUnmappedEdge(Path path) {
            for (var edge = path.FirstEdge; edge != null; edge = edge.Next)
                if (edge.AxisEdge.Direction != NudgingDirection)
                    return edge;
            return null;
        }

        void MapPathEndAxisEdgesToTheirObstacles(Path path) {
            Tuple<Polyline, Polyline> coupleOfObstacles;
            if (PathToObstacles.TryGetValue(path, out coupleOfObstacles)) {
                ProcessThePathStartToMapAxisEdgesToTheirObstacles(path, coupleOfObstacles.Item1);
                ProcessThePathEndToMapAxisEdgesToTheirObstacles(path, coupleOfObstacles.Item2);
            }
        }

        void ProcessThePathEndToMapAxisEdgesToTheirObstacles(Path path, Polyline endPolyline) {
            for (var edge = path.LastEdge;
                 edge != null && CompassVector.DirectionsAreParallel(edge.Direction, NudgingDirection);
                 edge = edge.Prev)
                axisEdgesToObstaclesTheyOriginatedFrom[edge.AxisEdge] = endPolyline;
        }

        void ProcessThePathStartToMapAxisEdgesToTheirObstacles(Path path, Polyline startPolyline) {
            for (var edge = path.FirstEdge;
                 edge != null && CompassVector.DirectionsAreParallel(edge.Direction, NudgingDirection);
                 edge = edge.Next)
                axisEdgesToObstaclesTheyOriginatedFrom[edge.AxisEdge] = startPolyline;
            //possible bug here because an edge might ignore two obstacles if it connects them
        }

        void GetPathOrdersAndPathGraph() {
            var combinatorialNudger = new CombinatorialNudger(Paths);
            PathOrders = combinatorialNudger.GetOrder();
            PathVisibilityGraph = combinatorialNudger.PathVisibilityGraph;
        }

        /*
                [Conditional("DEBUG")]
                void CheckPathsForSwitchbacks() {
                    foreach(var p in Paths)
                        CheckForSwitchbacks(p.PathPoints.ToArray());
                }
        */

        Directions NudgingDirection { get; set; }

        #region debugging
#if TEST_MSAGL
        static internal ICurve[] GetCurvesForShow(IEnumerable<Path> paths, IEnumerable<Polyline> obstacles) {
            var ret = new List<ICurve>();
            foreach (var path in paths) {
                var poly = new Polyline();
                foreach (var point in path.PathPoints)
                    poly.AddPoint(point);
                ret.Add(poly);
            }
            ret.AddRange(obstacles.Cast<ICurve>());
            return ret.ToArray();
        }
#endif
        #endregion
        void DrawPaths() {
            SetWidthsOfArrowheads();
            CreateLongestNudgedSegments();
            FindFreeSpaceInDirection(PathVisibilityGraph.Edges.Cast<AxisEdge>());
            MoveLongestSegsIdealPositionsInsideFeasibleIntervals();
            PositionShiftedEdges();
        }

        void SetWidthsOfArrowheads() {
            foreach (Path edgePath in Paths)
                SetWidthsOfArrowheadsForEdge(edgePath);
        }

        static void SetWidthsOfArrowheadsForEdge(Path path) {
            var edgeGeom = path.EdgeGeometry;
            if (edgeGeom.TargetArrowhead != null) {
                PathEdge pathEdge = path.LastEdge;
                pathEdge.Width = Math.Max(edgeGeom.TargetArrowhead.Width, pathEdge.Width);
            }
            if (edgeGeom.SourceArrowhead != null) {
                PathEdge pathEdge = path.FirstEdge;
                pathEdge.Width = Math.Max(edgeGeom.SourceArrowhead.Width, pathEdge.Width);
            }
        }

        internal double EdgeSeparation { get; set; }

        void PositionShiftedEdges() {
            //we are using 2*cornerFitRadius for the minimal edge separation
            Solver = new UniformOneDimensionalSolver(EdgeSeparation);
            foreach (var segment in LongestNudgedSegs)
                CreateVariablesOfLongestSegment(segment);
            CreateConstraintsOfTheOrder();
            CreateConstraintsBetweenLongestSegments();
            Solver.Solve();
            ShiftPathEdges();
        }

        void MoveLongestSegsIdealPositionsInsideFeasibleIntervals() {
            foreach (var seg in LongestNudgedSegs)
                MoveLongestSegIdealPositionsInsideFeasibleInterval(seg);
        }

        static void MoveLongestSegIdealPositionsInsideFeasibleInterval(LongestNudgedSegment seg) {
            if (seg.IsFixed) return;
            var leftBound = seg.GetLeftBound();
            var rightBound = seg.GetRightBound();
            if (seg.IdealPosition < leftBound)
                seg.IdealPosition=leftBound;
            else if( seg.IdealPosition> rightBound)
                seg.IdealPosition=rightBound;
        }

        void ShiftPathEdges() {
            foreach (var path in Paths)
                path.PathPoints = GetShiftedPoints(path).ToArray();
        }

        IEnumerable<Point> GetShiftedPoints(Path path) {
            return RemoveSwitchbacksAndMiddlePoints(GetShiftedPointsSimple(path));
        }
        /// <summary>
        /// sometimes we have very small mistakes in the positions that have to be fixed
        /// </summary>
        /// <returns></returns>
        static Point Rectilinearise(Point a, Point b) {
#if SHARPKIT //https://code.google.com/p/sharpkit/issues/detail?id=369 there are no structs in js
            b = b.Clone();
#endif
            if (a.X != b.X && a.Y != b.Y) {
                var dx = Math.Abs(a.X - b.X);
                var dy = Math.Abs(a.Y - b.Y);
                if (dx < dy)
                    b.X = a.X;
                else
                    b.Y = a.Y;
            }
            return b;
        }

        IEnumerable<Point> GetShiftedPointsSimple(Path path) {
            var edge = path.FirstEdge;
            yield return ShiftedPoint(edge.Source, edge.LongestNudgedSegment);
            foreach (var e in path.PathEdges)
                yield return ShiftedEdgePositionOfTarget(e);
        }

        Point ShiftedEdgePositionOfTarget(PathEdge e) {
            return e.LongestNudgedSegment != null || e.Next == null
                       ? ShiftedPoint(e.Target, e.LongestNudgedSegment)
                       : ShiftedPoint(e.Next.Source, e.Next.LongestNudgedSegment);
        }

        Point ShiftedPoint(Point point, LongestNudgedSegment segment) {
            if (segment == null)
                return point;
            var t = Solver.GetVariablePosition(segment.Id);
            return NudgingDirection == Directions.North ? new Point(t, point.Y) : new Point(point.X, -t);
        }

        #region debug
#if TEST_MSAGL
        internal static void ShowPathsFromPoints(IEnumerable<Path> paths, IEnumerable<Polyline> enumerable) {
            var dd = new List<DebugCurve>();
            if (enumerable != null)
                dd.AddRange(GetObstacleBoundaries(enumerable, "grey"));
            int i = 0;
            foreach (var p in paths)
                dd.AddRange(PathDebugCurvesFromPoints(p, DebugCurve.Colors[Math.Min(DebugCurve.Colors.Length, i++)]));
            LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(dd);
        }

        static IEnumerable<DebugCurve> PathDebugCurvesFromPoints(Path path, string color) {
            const double startWidth = 0.01;
            const double endWidth = 3;

            var pts = path.PathPoints.ToArray();
            double delta = (endWidth - startWidth) / (pts.Length - 1);
            for (int i = 0; i < pts.Length - 1; i++)
                yield return new DebugCurve(startWidth + delta * i, color, new LineSegment(pts[i], pts[i + 1]));
        }

          internal static void ShowParamPaths( Point s, Point e, params Path[] paths ) {
              ShowOrderedPaths(null,paths,s,e);
          }

        //         ReSharper disable UnusedMember.Local
        internal static void ShowOrderedPaths(IEnumerable<Polyline> obstacles, IEnumerable<Path> paths, Point s, Point e) {
            //           ReSharper restore UnusedMember.Local
            string[] colors = { "red", "green", "blue", "violet", "rose", "black" };

            const double startWidth = 0.001;
            const double endWidth = 0.1;
            var dd = new List<DebugCurve>();
            if (obstacles != null)
                dd.AddRange(GetObstacleBoundaries(obstacles, "grey"));
            int i = 0;
            foreach (var path in paths)
                dd.AddRange(GetTestPathAsDebugCurve(startWidth, endWidth, colors[Math.Min(colors.Length - 1, i++)], path));

            var ell = new DebugCurve(1, "black", new Ellipse(0.01, 0.01, s));
            dd.Add(ell);
            dd.Add(new DebugCurve(1, "black", new Ellipse(0.02, 0.02, e)));
            LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(dd.Concat(GetObstacleBoundaries(obstacles, "lightblue")));
        }

        static IEnumerable<DebugCurve> GetTestPathAsDebugCurve(double startWidth, double endWidth, string color, Path path) {
            if (path.PathEdges.Count() > 0) {
                int count = path.PathEdges.Count();

                double deltaW = count > 1 ? (endWidth - startWidth)/(count - 1) : 1;
                    //if count ==1 the value of deltaW does not matter
                int i = 0;
                foreach (var e in path.PathEdges)
                    yield return
                        new DebugCurve(150, startWidth + deltaW*(i++), color, new LineSegment(e.Source, e.Target));
            }else {
                int count = path.PathPoints.Count();
                var pts = path.PathPoints.ToArray();

                var deltaW = count > 1 ? (endWidth - startWidth) / (count - 1) : 1;
                //if count ==1 the value of deltaW does not matter
                for (int i = 0; i < count - 1;i++ )
                    yield return new DebugCurve(150, startWidth+deltaW*i, color, new LineSegment(pts[i], pts[i+1]));
            }
        }

        internal static IEnumerable<DebugCurve> GetTestEdgePathAsDebugCurves(double startWidth, double endWidth, string color, Path path) {
            int count = path.PathPoints.Count();

            double deltaW = count > 1 ? (endWidth - startWidth) / (count - 1) : 1; //if count ==1 the value of deltaW does not matter
            var points = path.PathPoints.ToArray();
            for (int i = 0; i < points.Length - 1; i++)
                yield return new DebugCurve(125, startWidth + deltaW * i, color, new LineSegment(points[i], points[i + 1]));
        }

        [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        static IEnumerable<DebugCurve> GetEdgePathFromPathEdgesAsDebugCurves(double startWidth, double endWidth, string color, Path path) {
            var points = path.PathPoints.ToArray();

            int count = points.Length;

            double deltaW = count > 1 ? (endWidth - startWidth) / (count - 1) : 1; //if count ==1 the value of deltaW does not matter
            for (int i = 0; i < points.Length - 1; i++)
                yield return new DebugCurve(120, startWidth + deltaW * i, color, new LineSegment(points[i], points[i + 1]));
        }
         // ReSharper disable UnusedMember.Local

        static internal void ShowEdgePaths(IEnumerable<Polyline> obstacles, IEnumerable<Path> edgePaths) {
            // ReSharper restore UnusedMember.Local
            List<DebugCurve> debCurves = GetDebCurvesOfPaths(obstacles, edgePaths);

            LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(debCurves);
        }

        internal static List<DebugCurve> GetDebCurvesOfPaths(IEnumerable<Polyline> enumerable, IEnumerable<Path> edgePaths) {
            var debCurves = GetObstacleBoundaries(enumerable, "black");
            int i = 0;

            foreach (var edgePath in edgePaths)
                debCurves.AddRange(GetTestEdgePathAsDebugCurves(0.2, 4, DebugCurve.Colors[(i++) % DebugCurve.Colors.Length], edgePath));
            return debCurves;
        }

        internal static void ShowPathsInLoop(IEnumerable<Polyline> enumerable, IEnumerable<Path> edgePaths, Point point) {
            foreach (var edgePath in edgePaths.Where(path=>(path.PathPoints.First()-point).Length<1 ||(path.PathPoints.Last()-point).Length<1 )) {
                var debCurves = GetObstacleBoundaries(enumerable, "black");
                debCurves.AddRange(GetTestEdgePathAsDebugCurves(0.1, 4, "red", edgePath));
                LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(debCurves);
            }
        }

        // ReSharper disable UnusedMember.Local
        [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        void ShowLongSegsWithIdealPositions(Directions dir) {
            // ReSharper restore UnusedMember.Local
            var debCurves = GetObstacleBoundaries(Obstacles, "black");
            int i = 0;

            debCurves.AddRange(LongestNudgedSegs.Select(ls => DebugCurveOfLongSeg(ls, DebugCurve.Colors[i++ % DebugCurve.Colors.Length], dir)));

            DebugCurveCollection.WriteToFile(debCurves, "c:/tmp/longSegs");

            LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(debCurves);
        }

        static DebugCurve DebugCurveOfLongSeg(LongestNudgedSegment ls, string s, Directions dir) {
            return new DebugCurve(1, s, LineSegOfLongestSeg(ls, dir));
        }

        static ICurve LineSegOfLongestSeg(LongestNudgedSegment ls, Directions dir) {
            var projectionToDir = dir == Directions.East ? (PointProjection)(p => p.X) : (p => p.Y);
            var min = Double.PositiveInfinity;
            var max = Double.NegativeInfinity;
            foreach (var edge in ls.Edges) {
                UpdateMinMaxWithPoint(ref min, ref max, projectionToDir, edge.Source);
                UpdateMinMaxWithPoint(ref min, ref max, projectionToDir, edge.Target);
            }
            return dir == Directions.East
                       ? new LineSegment(min, -ls.IdealPosition, max, -ls.IdealPosition)
                       : new LineSegment(ls.IdealPosition, min, ls.IdealPosition, max);
        }

        static void UpdateMinMaxWithPoint(ref double min, ref double max, PointProjection projectionToDir, Point point) {
            double p = projectionToDir(point);
            if (min > p)
                min = p;
            if (max < p)
                max = p;
        }

        // ReSharper disable UnusedMember.Local
        [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        void ShowPathsDebug(IEnumerable<Path> edgePaths) {
            var debCurves = GetObstacleBoundaries(Obstacles, "black");
            int i = 0;

            foreach (var edgePath in edgePaths)
                debCurves.AddRange(GetEdgePathFromPathEdgesAsDebugCurves(0.01, 0.4, DebugCurve.Colors[(i++) % DebugCurve.Colors.Length], edgePath));

            LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(debCurves);
        }

        [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        static IEnumerable<DebugCurve> PathDebugCurves(Path path, string color) {
            var d = path.PathEdges.Select(e => new DebugCurve(70, 0.5, color, new LineSegment(e.Source, e.Target)));
            return d.Concat(MarkPathVerts(path));
        }

        [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        private static IEnumerable<DebugCurve> MarkPathVerts(Path path) {
            bool first = true;
            var p = new Point();
            foreach (var p0 in path.PathPoints) {
                if (first) {
                    yield return new DebugCurve(200, 1, "violet", CurveFactory.CreateDiamond(5, 5, p0));
                    first = false;
                } else
                    yield return new DebugCurve(100, 0.5, "brown", CurveFactory.CreateEllipse(1.5, 1.5, p0));
                p = p0;
            }
            yield return new DebugCurve(200, 1, "green", CurveFactory.CreateDiamond(3, 3, p));
        }

        static internal IEnumerable<DebugCurve> PathDebugCurvesFromPoint(Path path) {
            var l = new List<Point>(path.PathPoints);
            for (int i = 0; i < l.Count - 1; i++)
                yield return new DebugCurve(4, "red", new LineSegment(l[i], l[i + 1]));
        }
        //
        // ReSharper disable UnusedMember.Local
        //        void ShowEdgesOfEdgePath(Path path){
        // ReSharper restore UnusedMember.Local
        //            string[] colors = {"red", "brown", "purple"};
        //            const double w0 = 1;
        //            const double w1 = 3;
        //            double dw = (w1 - w0)/path.OrientedSubpaths.Count;
        //            int i = 0;
        //            var dc = new List<DebugCurve>();
        //            foreach (var s in path.OrientedSubpaths){
        //                dc.AddRange(SubpathDebugCurves(w0 + dw*i, colors[Math.Min(i++, colors.Length - 1)], s));
        //            }
        //            LayoutAlgorithmSettings.ShowDebugCurves(dc.ToArray());
        //        }
        //
        //        static IEnumerable<DebugCurve> SubpathDebugCurves(double w, string color, OrientedSubpath subpath){
        //            return subpath.LinkedPath.Select(e => new DebugCurve(w, color, new LineSegment(e.Source.Point, e.Target.Point)));
        //        }

        static internal List<DebugCurve> GetObstacleBoundaries(IEnumerable<Polyline> obstacles, string color) {
            var debugCurves = new List<DebugCurve>();
            if (obstacles != null)
                debugCurves.AddRange(obstacles.Select(poly => new DebugCurve(50, 0.3, color, poly)));
            return debugCurves;
        }
#endif
        #endregion

        void CreateConstraintsBetweenLongestSegments() {
            foreach (var segment in LongestNudgedSegs)
                CreateConstraintsBetweenLongestSegmentsForSegment(segment);
        }

        void CreateConstraintsBetweenLongestSegmentsForSegment(LongestNudgedSegment segment) {
            var rightNeighbors = new Set<LongestNudgedSegment>();
            foreach (var pathEdge in segment.Edges) {
                var axisEdge = pathEdge.AxisEdge;
                if (axisEdge != null)
                    foreach (var rightNeiAxisEdge in axisEdge.RightNeighbors)
                        foreach (var longSeg in rightNeiAxisEdge.LongestNudgedSegments)
                            rightNeighbors.Insert(longSeg);
            }

            foreach (var seg in rightNeighbors)
                ConstraintTwoLongestSegs(segment, seg);

        }

        void CreateConstraintsOfTheOrder() {
            foreach (var kv in PathOrders)
                if (ParallelToDirection(kv.Key, NudgingDirection))
                    CreateConstraintsOfThePathOrder(kv.Value);
        }

        static bool ParallelToDirection(VisibilityEdge edge, Directions direction) {
            switch (direction) {
                case Directions.North:
                case Directions.South:
                    return ApproximateComparer.Close(edge.SourcePoint.X, edge.TargetPoint.X);
                default:
                    return ApproximateComparer.Close(edge.SourcePoint.Y, edge.TargetPoint.Y);
            }
        }

        void CreateConstraintsOfThePathOrder(IEnumerable<PathEdge> pathOrder) {
            PathEdge prevEdge = null;

            foreach (var pathEdge in pathOrder.Where(p => p.LongestNudgedSegment != null)) {
                if (prevEdge != null)
                    ConstraintTwoLongestSegs(prevEdge.LongestNudgedSegment, pathEdge.LongestNudgedSegment);
                prevEdge = pathEdge;
            }
        }

        void ConstraintTwoLongestSegs(LongestNudgedSegment prevSeg, LongestNudgedSegment seg) {
            if (!prevSeg.IsFixed || !seg.IsFixed)
                Solver.AddConstraint(prevSeg.Id, seg.Id);
        }

        UniformOneDimensionalSolver Solver { get; set; }

        void CreateVariablesOfLongestSegment(LongestNudgedSegment segment) {
            if (!segment.IsFixed) {
                var leftBound = segment.GetLeftBound();
                var rightBound = segment.GetRightBound();
                if (leftBound >= rightBound) {//don't move the segment from the way it was generated
                    Solver.AddFixedVariable(segment.Id, SegmentPosition(segment, NudgingDirection));
                    segment.IsFixed = true;
                } else {
                    Solver.AddVariable(segment.Id, SegmentPosition(segment, NudgingDirection), segment.IdealPosition, segment.Width);
         //           Debug.Assert(leftBound + Curve.DistanceEpsilon < rightBound); //this assert does not hold for overlaps
                    if (leftBound != Double.NegativeInfinity)
                        Solver.SetLowBound(leftBound, segment.Id);
                    if (rightBound != Double.PositiveInfinity)
                        Solver.SetUpperBound(segment.Id, rightBound);
                }
            } else
                Solver.AddFixedVariable(segment.Id, SegmentPosition(segment, NudgingDirection));
        }

        static double SegmentPosition(SegmentBase segment, Directions direction) {
            return direction == Directions.North ? segment.Start.X : -segment.Start.Y;
        }

#if TEST_MSAGL
        // ReSharper disable UnusedMember.Local
        [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        void ShowSegmentBounds(LongestNudgedSegment segment) {
            // ReSharper restore UnusedMember.Local
            var dd = GetObstacleBoundaries(Obstacles, "black");
            var segtop = segment.Edges.Max(e => Math.Max(e.Source.Y, e.Target.Y));
            var segbottom = segment.Edges.Min(e => Math.Min(e.Source.Y, e.Target.Y));
            var segx = segment.Start.X;
            var seg = new DebugCurve(80, 1, "brown", new LineSegment(new Point(segx, segbottom), new Point(segx, segtop)));

            var leftbound = new DebugCurve(80, 1.0, "red", new LineSegment(new Point(segment.GetLeftBound(), segbottom),
                                                                           new Point(segment.GetLeftBound(), segtop)));
            var rightbound = new DebugCurve(80, 1, "green", new LineSegment(new Point(segment.GetRightBound(), segbottom),
                            new Point(segment.GetRightBound(), segtop)));
            LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(dd.Concat(new[] { seg, leftbound, rightbound }));
        }
        // ReSharper disable UnusedMember.Local
        [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
        void ShowSegment(LongestNudgedSegment segment) {
            // ReSharper restore UnusedMember.Local
            var dd = GetObstacleBoundaries(Obstacles, "black");
            var segtop = segment.Edges.Max(e => Math.Max(e.Source.Y, e.Target.Y));
            var segbottom = segment.Edges.Min(e => Math.Min(e.Source.Y, e.Target.Y));
            var segx = segment.Start.X;
            var seg = new DebugCurve(80, 1, "brown", new LineSegment(new Point(segx, segbottom), new Point(segx, segtop)));

            LayoutAlgorithmSettings.ShowDebugCurvesEnumeration(dd.Concat(new[] { seg }));

        }
#endif

        List<LongestNudgedSegment> LongestNudgedSegs { get; set; }

        Dictionary<AxisEdge, List<PathEdge>> PathOrders { get; set; }
        /// <summary>
        /// maps each path to the pair of obstacles; the first element of the pair is
        /// where the path starts and the second where the path ends
        /// </summary>
        Dictionary<Path, Tuple<Polyline, Polyline>> PathToObstacles { get; set; }

        void FindFreeSpaceInDirection(IEnumerable<AxisEdge> axisEdges) {
            BoundAxisEdgesByRectsKnownInAdvance();
            var freeSpaceFinder = new FreeSpaceFinder(NudgingDirection, Obstacles,
                                                      axisEdgesToObstaclesTheyOriginatedFrom, PathOrders, axisEdges);
            freeSpaceFinder.FindFreeSpace();
        }

        void BoundAxisEdgesByRectsKnownInAdvance() {
            foreach (var path in Paths) {
                if (HasGroups)
                    BoundPathByMinCommonAncestors(path);
                BoundAxisEdgesAdjacentToSourceAndTargetOnEdge(path);
            }
        }

        void BoundPathByMinCommonAncestors(Path path) {
            foreach (var rect in GetMinCommonAncestors(path.EdgeGeometry).Select(sh => sh.BoundingBox))
                foreach (
                    var edge in
                        path.PathEdges.Select(e => e.AxisEdge).Where(
                            axisEdge => axisEdge.Direction == NudgingDirection)
                    )
                    BoundAxisEdgeByRect(rect, edge);
        }

        IEnumerable<Shape> GetMinCommonAncestors(EdgeGeometry edgeGeometry) {
            if (PortToShapes == null)
                PortToShapes = MapPortsToShapes(AncestorsSets.Keys);
            var commonAncestors = AncestorsForPort(edgeGeometry.SourcePort)*
                                  AncestorsForPort(edgeGeometry.TargetPort);
            return commonAncestors.Where(anc => !anc.Children.Any(child=>commonAncestors.Contains(child)));
        }
        /// <summary>
        ///
        /// </summary>
        protected Dictionary<Port, Shape> PortToShapes { get; private set; }

        Set<Shape> AncestorsForPort(Port port) {
            Shape shape;
            if (PortToShapes.TryGetValue(port, out shape)) {
                return AncestorsSets[shape];
            }

            // This is a FreePort or Waypoint; return all spatial parents.
            return new Set<Shape>(HierarchyOfGroups.AllHitItems(new Rectangle(port.Location, port.Location), null));
        }

        void BoundAxisEdgeAdjacentToObstaclePort(Port port, AxisEdge axisEdge) {
            if (port is WaypointPort || (port.Curve == null && port.PortEntry == null))
                BoundAxisByPoint(port.Location, axisEdge);
            else if (port.PortEntry == null) {
                if (port.Curve.BoundingBox.Contains(port.Location))
                    BoundAxisEdgeByRect(port.Curve.BoundingBox, axisEdge);
            } else {
                var portEntry = port.PortEntry as PortEntryOnCurve;
                if (portEntry != null) {
                    Rectangle rect;
                    if (FindPortEntryRectCrossingAxisEdge(portEntry, axisEdge, out rect))
                        BoundAxisEdgeByRect(rect, axisEdge);
                }
            }
        }

        void BoundAxisByPoint(Point point, AxisEdge axisEdge) {
            if (axisEdge != null && axisEdge.Direction == NudgingDirection)
                if (NudgingDirection == Directions.North) {
                    axisEdge.BoundFromLeft(point.X);
                    axisEdge.BoundFromRight(point.X);
                } else {
                    axisEdge.BoundFromLeft(-point.Y);
                    axisEdge.BoundFromRight(-point.Y);
                }
        }

        static bool FindPortEntryRectCrossingAxisEdge(PortEntryOnCurve portEntry, AxisEdge axisEdge, out Rectangle rect) {
            var ar = new Rectangle(axisEdge.SourcePoint, axisEdge.TargetPoint);
            foreach (Rectangle r in portEntry.AllowedRectangles) {
                if(r.Intersects(ar)) {
                    rect = r;
                    return true;
                }
            }
            rect = Rectangle.CreateAnEmptyBox();
            return false;
        }

        void BoundAxisEdgesAdjacentToSourceAndTargetOnEdge(Path path) {
            BoundAxisEdgeAdjacentToObstaclePort(path.EdgeGeometry.SourcePort, path.FirstEdge.AxisEdge);
            BoundAxisEdgeAdjacentToObstaclePort(path.EdgeGeometry.TargetPort, path.LastEdge.AxisEdge);
        }

        void BoundAxisEdgeByRect(Rectangle rectangle, AxisEdge axisEdge) {
            if (axisEdge != null && axisEdge.Direction == NudgingDirection)
                if (NudgingDirection == Directions.North) {
                    axisEdge.BoundFromLeft(rectangle.Left);
                    axisEdge.BoundFromRight(rectangle.Right);
                } else {
                    axisEdge.BoundFromLeft(-rectangle.Top);
                    axisEdge.BoundFromRight(-rectangle.Bottom);
                }
        }

        void CreateLongestNudgedSegments() {
            var projectionToPerp =
                NudgingDirection == Directions.East ? (PointProjection)FreeSpaceFinder.MinusY : FreeSpaceFinder.X;

            LongestNudgedSegs = new List<LongestNudgedSegment>();
            foreach (var path in Paths)
                CreateLongestNudgedSegmentsForPath(path, projectionToPerp);

        }

        void CreateLongestNudgedSegmentsForPath(Path path, PointProjection projectionToPerp) {
            //ShowEdgesOfEdgePath(path);
            GoOverPathAndCreateLongSegs(path);
            CalculateIdealPositionsForLongestSegs(path, projectionToPerp);
        }

        static void CalculateIdealPositionsForLongestSegs(Path path, PointProjection projectionToPerp) {
            LongestNudgedSegment currentLongSeg = null;
            LongestNudgedSegment ret = null;
            double prevOffset = projectionToPerp(path.Start);
            foreach (var edge in path.PathEdges) {
                if (edge.LongestNudgedSegment != null) {
                    currentLongSeg = edge.LongestNudgedSegment;
                    if (ret != null) {
                        double t;
                        SetIdealPositionForSeg(ret, t = projectionToPerp(ret.Start), prevOffset,
                                               projectionToPerp(currentLongSeg.Start));
                        prevOffset = t;
                        ret = null;
                    }
                } else if (currentLongSeg != null) {
                    ret = currentLongSeg;
                    currentLongSeg = null;
                }
            }
            if (ret != null)
                SetIdealPositionForSeg(ret, projectionToPerp(ret.Start), prevOffset, projectionToPerp(path.End));
            else if (currentLongSeg != null)
                currentLongSeg.IdealPosition = projectionToPerp(currentLongSeg.Start);
        }

        static void SetIdealPositionForSeg(LongestNudgedSegment segment, double segPosition, double offset0, double offset1) {
            var max = Math.Max(offset0, offset1);
            var min = Math.Min(offset0, offset1);
            if (min + ApproximateComparer.DistanceEpsilon < segPosition)
                if (segPosition < max)
                    segment.IdealPosition = 0.5 * (max + min);
                else
                    segment.IdealPosition = max;
            else
                segment.IdealPosition = min;

        }

        void GoOverPathAndCreateLongSegs(Path path) {
            LongestNudgedSegment currentLongestSeg = null;

            var oppositeDir = CompassVector.OppositeDir(NudgingDirection);

            foreach (var edge in path.PathEdges) {
                var edgeDir = edge.Direction;
                if (edgeDir == NudgingDirection || edgeDir == oppositeDir) {
                    if (currentLongestSeg == null)
#if SHARPKIT //https://code.google.com/p/sharpkit/issues/detail?id=368
                    {
                        edge.LongestNudgedSegment = currentLongestSeg = new LongestNudgedSegment(LongestNudgedSegs.Count);
                        LongestNudgedSegs.Add(edge.LongestNudgedSegment);
                    }
#else
                        LongestNudgedSegs.Add(
                            edge.LongestNudgedSegment =
                            currentLongestSeg = new LongestNudgedSegment(LongestNudgedSegs.Count));
#endif
                    else
                        edge.LongestNudgedSegment = currentLongestSeg;

                    if (edge.IsFixed)
                        currentLongestSeg.IsFixed = true;
                } else {
                    //the edge is perpendicular to "direction"
                    edge.LongestNudgedSegment = null;
                    currentLongestSeg = null;
                }
            }
        }

        static IEnumerable<Point> BuildPolylineForPath(Path path) {
#if SHARPKIT //https://code.google.com/p/sharpkit/issues/detail?id=369
            var points = path.PathPoints.Select(p=>p.Clone()).ToArray();
#else
            var points = path.PathPoints.ToArray();
#endif
            ExtendPolylineToPorts(ref points, path);
            for(int i=0;i<points.Length-1;i++)
                Debug.Assert(CompassVector.IsPureDirection(points[i], points[i+1]));

            return points;
        }

        static void ExtendPolylineToPorts(ref Point[] points, Path path) {
            ExtendPolylineToSourcePort(ref points, path.EdgeGeometry.SourcePort.Location);
            ExtendPolylineToTargetPort(ref points, path.EdgeGeometry.TargetPort.Location);

            // In some overlapped cases where the source or target vertex used for the path
            // coincides with the target or source port location, we can end up with a single-point
            // path.  In that case, we just force a straightline path.
            if (points.Length < 2) {
                points = new Point[2];
                points[0] = path.EdgeGeometry.SourcePort.Location;
                points[1] = path.EdgeGeometry.TargetPort.Location;
            }
        }

        static void ExtendPolylineToTargetPort(ref Point[] points, Point location) {
            int n = points.Length - 1;
            var dir = CompassVector.VectorDirection(points[n - 1], points[n]);
            if (ProjectionsAreClose(points[n-1], dir, location)) {
                //it might be that the last point on polyline is at the port already
                //then we just drop the last point
                points = points.Take(n).ToArray();
                return;
            }
            if (dir == Directions.East || dir == Directions.West)
                points[n].X = location.X;
            else
                points[n].Y = location.Y;
        }

        static bool ProjectionsAreClose(Point a, Directions dir, Point b) {
            if (dir == Directions.East || dir == Directions.West)
                return ApproximateComparer.Close(a.X, b.X);
            return ApproximateComparer.Close(a.Y, b.Y);
        }

        static void ExtendPolylineToSourcePort(ref Point[] points, Point location) {
            var dir = CompassVector.VectorDirection(points[0], points[1]);
            if (ProjectionsAreClose(points[1], dir, location)) {
                //it might be that the second point on polyline is at the port already
                //then we just drop the first point
                points = points.Skip(1).ToArray();
                return;
            }
            if (dir == Directions.East || dir == Directions.West)
                points[0].X = location.X;
            else
                points[0].Y = location.Y;
        }

        static IEnumerable<Point> RemoveSwitchbacksAndMiddlePoints(IEnumerable<Point> points) {
            var en = points.GetEnumerator();
            en.MoveNext();
            var a = en.Current;
            yield return a;
            en.MoveNext();
            var b = en.Current;
            var prevDir = (b - a).CompassDirection;

            while (en.MoveNext()) {
                var dir = (en.Current - b).CompassDirection;
                if (dir == prevDir || CompassVector.OppositeDir(dir) == prevDir || dir == Directions.None) //we continue walking along the same straight line, maybe going backwards!
                    b = en.Current;
                else {
                    if (!ApproximateComparer.Close(a, b)) {//make sure that we are not returning the same point twice
                        yield return a=Rectilinearise(a, b);
                    }
                    b = en.Current;
                    prevDir = dir;
                }
            }
            if (!ApproximateComparer.Close(a, b))
                yield return Rectilinearise(a,b);
        }

        /// <summary>
        /// this function defines the final path coordinates
        /// </summary>
        /// <param name="paths">the set of paths, point sequences</param>
        /// <param name="cornerFitRadius">the radius of the arc inscribed into the path corners</param>
        /// <param name="paddedObstacles">an enumeration of padded obstacles</param>
        /// <param name="ancestorsSets"></param>
        /// <param name="removeStaircases"></param>
        /// <returns>the mapping of the path to its modified path</returns>
        internal static void NudgePaths(IEnumerable<Path> paths, double cornerFitRadius, IEnumerable<Polyline> paddedObstacles, Dictionary<Shape, Set<Shape>> ancestorsSets, bool removeStaircases) {
            if (!paths.Any())
                return;
            var nudger = new Nudger(paths, cornerFitRadius, paddedObstacles, ancestorsSets);
            nudger.Calculate(Directions.North, true);
            nudger.Calculate(Directions.East, false);
            nudger.Calculate(Directions.North, false);
            if (removeStaircases)
                nudger.RemoveStaircases();
            foreach (var path in paths)
                path.EdgeGeometry.Curve = new Polyline(BuildPolylineForPath(path));
        }

        void RemoveStaircases() {
            StaircaseRemover.RemoveStaircases(Paths, HierarchyOfObstacles);

        }
        /*
        void RemoveStaircasesFromPath(Path path) {

            var points = (Point[]) path.PathPoints;
            if (points.Length <= 4) return;
            int i = FindStaircase(points);
            if (i == -1) return;
            var linkedList = new LinkedList<Point>(points);
            var node = linkedList.First;
            for(int j=0;j<i;j++)
                node = node.Next; //getting to the i-th node

            RemoveStaircaseOnNode(node);
            node = node.Next;
            while(true) {
                node = FindStaircaseAfterNode(node);
                if (node == null) break;
                RemoveStaircaseOnNode(node);
                node = node.Next;
            }
        }

        LinkedListNode<Point> FindStaircaseAfterNode(LinkedListNode<Point> n) {
            do {
                var nn = n.Next;
                var nnn = nn.Next;
                var nnnn = nnn.Next;
                if (nnn.Next == null)
                    return null;
                if (IsStaircase(n.Value, nn.Value, nnn.Value, nnnn.Value))
                    return n;
                n = nn;
            } while (true);
        }

        bool IsStaircase(Point a, Point b, Point c, Point d) {

            return false;
        }

        void RemoveStaircaseOnNode(LinkedListNode<Point> node) {
            throw new NotImplementedException();
        }

        int FindStaircase(Point[] points) {
            throw new NotImplementedException();
        }
         */

        internal static Dictionary<Port, Shape> MapPortsToShapes(IEnumerable<Shape> listOfShapes) {
            var portToShapes = new Dictionary<Port, Shape>();
            foreach (Shape shape in listOfShapes)
                foreach (Port port in shape.Ports)
                    portToShapes[port] = shape;
            return portToShapes;
        }
    }
}


text:
struct ImGui_ImplDX12_RenderBuffers
{
    ID3D12Resource*     IndexBuffer;
    ID3D12Resource*     VertexBuffer;
    int                 IndexBufferSize;
    int                 VertexBufferSize;
};

struct ImGui_ImplDX12_Data
{
    ID3D12Device*                   pd3dDevice;
    ID3D12RootSignature*            pRootSignature;
    ID3D12PipelineState*            pPipelineState;
    DXGI_FORMAT                     RTVFormat;
    ID3D12Resource*                 pFontTextureResource;
    D3D12_CPU_DESCRIPTOR_HANDLE     hFontSrvCpuDescHandle;
    D3D12_GPU_DESCRIPTOR_HANDLE     hFontSrvGpuDescHandle;

    ImGui_ImplDX12_RenderBuffers*   pFrameResources;
    UINT                            numFramesInFlight;
    UINT                            frameIndex;

    ImGui_ImplDX12_Data()           { memset((void*)this, 0, sizeof(*this)); frameIndex = UINT_MAX; }
};

struct VERTEX_CONSTANT_BUFFER_DX12
{
    float   mvp[4][4];
};

// Backend data stored in io.BackendRendererUserData to allow support for multiple Dear ImGui contexts
// It is STRONGLY preferred that you use docking branch with multi-viewports (== single Dear ImGui context + multiple windows) instead of multiple Dear ImGui contexts.
static ImGui_ImplDX12_Data* ImGui_ImplDX12_GetBackendData()
{
    return ImGui::GetCurrentContext() ? (ImGui_ImplDX12_Data*)ImGui::GetIO().BackendRendererUserData : nullptr;
}

// Functions
static void ImGui_ImplDX12_SetupRenderState(ImDrawData* draw_data, ID3D12GraphicsCommandList* ctx, ImGui_ImplDX12_RenderBuffers* fr)
{
    ImGui_ImplDX12_Data* bd = ImGui_ImplDX12_GetBackendData();

    // Setup orthographic projection matrix into our constant buffer
    // Our visible imgui space lies from draw_data->DisplayPos (top left) to draw_data->DisplayPos+data_data->DisplaySize (bottom right).
    VERTEX_CONSTANT_BUFFER_DX12 vertex_constant_buffer;
    {
        float L = draw_data->DisplayPos.x;
        float R = draw_data->DisplayPos.x + draw_data->DisplaySize.x;
        float T = draw_data->DisplayPos.y;
        float B = draw_data->DisplayPos.y + draw_data->DisplaySize.y;
        float mvp[4][4] =
        {
            { 2.0f/(R-L),   0.0f,           0.0f,       0.0f },
            { 0.0f,         2.0f/(T-B),     0.0f,       0.0f },
            { 0.0f,         0.0f,           0.5f,       0.0f },
            { (R+L)/(L-R),  (T+B)/(B-T),    0.5f,       1.0f },
        };
        memcpy(&vertex_constant_buffer.mvp, mvp, sizeof(mvp));
    }

    // Setup viewport
    D3D12_VIEWPORT vp;
    memset(&vp, 0, sizeof(D3D12_VIEWPORT));
    vp.Width = draw_data->DisplaySize.x;
    vp.Height = draw_data->DisplaySize.y;
    vp.MinDepth = 0.0f;
    vp.MaxDepth = 1.0f;
    vp.TopLeftX = vp.TopLeftY = 0.0f;
    ctx->RSSetViewports(1, &vp);

    // Bind shader and vertex buffers
    unsigned int stride = sizeof(ImDrawVert);
    unsigned int offset = 0;
    D3D12_VERTEX_BUFFER_VIEW vbv;
    memset(&vbv, 0, sizeof(D3D12_VERTEX_BUFFER_VIEW));
    vbv.BufferLocation = fr->VertexBuffer->GetGPUVirtualAddress() + offset;
    vbv.SizeInBytes = fr->VertexBufferSize * stride;
    vbv.StrideInBytes = stride;
    ctx->IASetVertexBuffers(0, 1, &vbv);
    D3D12_INDEX_BUFFER_VIEW ibv;
    memset(&ibv, 0, sizeof(D3D12_INDEX_BUFFER_VIEW));
    ibv.BufferLocation = fr->IndexBuffer->GetGPUVirtualAddress();
    ibv.SizeInBytes = fr->IndexBufferSize * sizeof(ImDrawIdx);
    ibv.Format = sizeof(ImDrawIdx) == 2 ? DXGI_FORMAT_R16_UINT : DXGI_FORMAT_R32_UINT;
    ctx->IASetIndexBuffer(&ibv);
    ctx->IASetPrimitiveTopology(D3D_PRIMITIVE_TOPOLOGY_TRIANGLELIST);
    ctx->SetPipelineState(bd->pPipelineState);
    ctx->SetGraphicsRootSignature(bd->pRootSignature);
    ctx->SetGraphicsRoot32BitConstants(0, 16, &vertex_constant_buffer, 0);

    // Setup blend factor
    const float blend_factor[4] = { 0.f, 0.f, 0.f, 0.f };
    ctx->OMSetBlendFactor(blend_factor);
}

template<typename T>
static inline void SafeRelease(T*& res)
{
    if (res)
        res->Release();
    res = nullptr;
}

// Render function
void ImGui_ImplDX12_RenderDrawData(ImDrawData* draw_data, ID3D12GraphicsCommandList* ctx)
{
    // Avoid rendering when minimized
    if (draw_data->DisplaySize.x <= 0.0f || draw_data->DisplaySize.y <= 0.0f)
        return;

    // FIXME: I'm assuming that this only gets called once per frame!
    // If not, we can't just re-allocate the IB or VB, we'll have to do a proper allocator.
    ImGui_ImplDX12_Data* bd = ImGui_ImplDX12_GetBackendData();
    bd->frameIndex = bd->frameIndex + 1;
    ImGui_ImplDX12_RenderBuffers* fr = &bd->pFrameResources[bd->frameIndex % bd->numFramesInFlight];

    // Create and grow vertex/index buffers if needed
    if (fr->VertexBuffer == nullptr || fr->VertexBufferSize < draw_data->TotalVtxCount)
    {
        SafeRelease(fr->VertexBuffer);
        fr->VertexBufferSize = draw_data->TotalVtxCount + 5000;
        D3D12_HEAP_PROPERTIES props;
        memset(&props, 0, sizeof(D3D12_HEAP_PROPERTIES));
        props.Type = D3D12_HEAP_TYPE_UPLOAD;
        props.CPUPageProperty = D3D12_CPU_PAGE_PROPERTY_UNKNOWN;
        props.MemoryPoolPreference = D3D12_MEMORY_POOL_UNKNOWN;
        D3D12_RESOURCE_DESC desc;
        memset(&desc, 0, sizeof(D3D12_RESOURCE_DESC));
        desc.Dimension = D3D12_RESOURCE_DIMENSION_BUFFER;
        desc.Width = fr->VertexBufferSize * sizeof(ImDrawVert);
        desc.Height = 1;
        desc.DepthOrArraySize = 1;
        desc.MipLevels = 1;
        desc.Format = DXGI_FORMAT_UNKNOWN;
        desc.SampleDesc.Count = 1;
        desc.Layout = D3D12_TEXTURE_LAYOUT_ROW_MAJOR;
        desc.Flags = D3D12_RESOURCE_FLAG_NONE;
        if (bd->pd3dDevice->CreateCommittedResource(&props, D3D12_HEAP_FLAG_NONE, &desc, D3D12_RESOURCE_STATE_GENERIC_READ, nullptr, IID_PPV_ARGS(&fr->VertexBuffer)) < 0)
            return;
    }
    if (fr->IndexBuffer == nullptr || fr->IndexBufferSize < draw_data->TotalIdxCount)
    {
        SafeRelease(fr->IndexBuffer);
        fr->IndexBufferSize = draw_data->TotalIdxCount + 10000;
        D3D12_HEAP_PROPERTIES props;
        memset(&props, 0, sizeof(D3D12_HEAP_PROPERTIES));
        props.Type = D3D12_HEAP_TYPE_UPLOAD;
        props.CPUPageProperty = D3D12_CPU_PAGE_PROPERTY_UNKNOWN;
        props.MemoryPoolPreference = D3D12_MEMORY_POOL_UNKNOWN;
        D3D12_RESOURCE_DESC desc;
        memset(&desc, 0, sizeof(D3D12_RESOURCE_DESC));
        desc.Dimension = D3D12_RESOURCE_DIMENSION_BUFFER;
        desc.Width = fr->IndexBufferSize * sizeof(ImDrawIdx);
        desc.Height = 1;
        desc.DepthOrArraySize = 1;
        desc.MipLevels = 1;
        desc.Format = DXGI_FORMAT_UNKNOWN;
        desc.SampleDesc.Count = 1;
        desc.Layout = D3D12_TEXTURE_LAYOUT_ROW_MAJOR;
        desc.Flags = D3D12_RESOURCE_FLAG_NONE;
        if (bd->pd3dDevice->CreateCommittedResource(&props, D3D12_HEAP_FLAG_NONE, &desc, D3D12_RESOURCE_STATE_GENERIC_READ, nullptr, IID_PPV_ARGS(&fr->IndexBuffer)) < 0)
            return;
    }

    // Upload vertex/index data into a single contiguous GPU buffer
    void* vtx_resource, *idx_resource;
    D3D12_RANGE range;
    memset(&range, 0, sizeof(D3D12_RANGE));
    if (fr->VertexBuffer->Map(0, &range, &vtx_resource) != S_OK)
        return;
    if (fr->IndexBuffer->Map(0, &range, &idx_resource) != S_OK)
        return;
    ImDrawVert* vtx_dst = (ImDrawVert*)vtx_resource;
    ImDrawIdx* idx_dst = (ImDrawIdx*)idx_resource;
    for (int n = 0; n < draw_data->CmdListsCount; n++)
    {
        const ImDrawList* cmd_list = draw_data->CmdLists[n];
        memcpy(vtx_dst, cmd_list->VtxBuffer.Data, cmd_list->VtxBuffer.Size * sizeof(ImDrawVert));
        memcpy(idx_dst, cmd_list->IdxBuffer.Data, cmd_list->IdxBuffer.Size * sizeof(ImDrawIdx));
        vtx_dst += cmd_list->VtxBuffer.Size;
        idx_dst += cmd_list->IdxBuffer.Size;
    }
    fr->VertexBuffer->Unmap(0, &range);
    fr->IndexBuffer->Unmap(0, &range);

    // Setup desired DX state
    ImGui_ImplDX12_SetupRenderState(draw_data, ctx, fr);

    // Render command lists
    // (Because we merged all buffers into a single one, we maintain our own offset into them)
    int global_vtx_offset = 0;
    int global_idx_offset = 0;
    ImVec2 clip_off = draw_data->DisplayPos;
    for (int n = 0; n < draw_data->CmdListsCount; n++)
    {
        const ImDrawList* cmd_list = draw_data->CmdLists[n];
        for (int cmd_i = 0; cmd_i < cmd_list->CmdBuffer.Size; cmd_i++)
        {
            const ImDrawCmd* pcmd = &cmd_list->CmdBuffer[cmd_i];
            if (pcmd->UserCallback != nullptr)
            {
                // User callback, registered via ImDrawList::AddCallback()
                // (ImDrawCallback_ResetRenderState is a special callback value used by the user to request the renderer to reset render state.)
                if (pcmd->UserCallback == ImDrawCallback_ResetRenderState)
                    ImGui_ImplDX12_SetupRenderState(draw_data, ctx, fr);
                else
                    pcmd->UserCallback(cmd_list, pcmd);
            }
            else
            {
                // Project scissor/clipping rectangles into framebuffer space
                ImVec2 clip_min(pcmd->ClipRect.x - clip_off.x, pcmd->ClipRect.y - clip_off.y);
                ImVec2 clip_max(pcmd->ClipRect.z - clip_off.x, pcmd->ClipRect.w - clip_off.y);
                if (clip_max.x <= clip_min.x || clip_max.y <= clip_min.y)
                    continue;

                // Apply Scissor/clipping rectangle, Bind texture, Draw
                const D3D12_RECT r = { (LONG)clip_min.x, (LONG)clip_min.y, (LONG)clip_max.x, (LONG)clip_max.y };
                D3D12_GPU_DESCRIPTOR_HANDLE texture_handle = {};
                texture_handle.ptr = (UINT64)pcmd->GetTexID();
                ctx->SetGraphicsRootDescriptorTable(1, texture_handle);
                ctx->RSSetScissorRects(1, &r);
                ctx->DrawIndexedInstanced(pcmd->ElemCount, 1, pcmd->IdxOffset + global_idx_offset, pcmd->VtxOffset + global_vtx_offset, 0);
            }
        }
        global_idx_offset += cmd_list->IdxBuffer.Size;
        global_vtx_offset += cmd_list->VtxBuffer.Size;
    }
}

static void ImGui_ImplDX12_CreateFontsTexture()
{
    // Build texture atlas
    ImGuiIO& io = ImGui::GetIO();
    ImGui_ImplDX12_Data* bd = ImGui_ImplDX12_GetBackendData();
    unsigned char* pixels;
    int width, height;
    io.Fonts->GetTexDataAsRGBA32(&pixels, &width, &height);

    // Upload texture to graphics system
    {
        D3D12_HEAP_PROPERTIES props;
        memset(&props, 0, sizeof(D3D12_HEAP_PROPERTIES));
        props.Type = D3D12_HEAP_TYPE_DEFAULT;
        props.CPUPageProperty = D3D12_CPU_PAGE_PROPERTY_UNKNOWN;
        props.MemoryPoolPreference = D3D12_MEMORY_POOL_UNKNOWN;

        D3D12_RESOURCE_DESC desc;
        ZeroMemory(&desc, sizeof(desc));
        desc.Dimension = D3D12_RESOURCE_DIMENSION_TEXTURE2D;
        desc.Alignment = 0;
        desc.Width = width;
        desc.Height = height;
        desc.DepthOrArraySize = 1;
        desc.MipLevels = 1;
        desc.Format = DXGI_FORMAT_R8G8B8A8_UNORM;
        desc.SampleDesc.Count = 1;
        desc.SampleDesc.Quality = 0;
        desc.Layout = D3D12_TEXTURE_LAYOUT_UNKNOWN;
        desc.Flags = D3D12_RESOURCE_FLAG_NONE;

        ID3D12Resource* pTexture = nullptr;
        bd->pd3dDevice->CreateCommittedResource(&props, D3D12_HEAP_FLAG_NONE, &desc,
            D3D12_RESOURCE_STATE_COPY_DEST, nullptr, IID_PPV_ARGS(&pTexture));

        UINT uploadPitch = (width * 4 + D3D12_TEXTURE_DATA_PITCH_ALIGNMENT - 1u) & ~(D3D12_TEXTURE_DATA_PITCH_ALIGNMENT - 1u);
        UINT uploadSize = height * uploadPitch;
        desc.Dimension = D3D12_RESOURCE_DIMENSION_BUFFER;
        desc.Alignment = 0;
        desc.Width = uploadSize;
        desc.Height = 1;
        desc.DepthOrArraySize = 1;
        desc.MipLevels = 1;
        desc.Format = DXGI_FORMAT_UNKNOWN;
        desc.SampleDesc.Count = 1;
        desc.SampleDesc.Quality = 0;
        desc.Layout = D3D12_TEXTURE_LAYOUT_ROW_MAJOR;
        desc.Flags = D3D12_RESOURCE_FLAG_NONE;

        props.Type = D3D12_HEAP_TYPE_UPLOAD;
        props.CPUPageProperty = D3D12_CPU_PAGE_PROPERTY_UNKNOWN;
        props.MemoryPoolPreference = D3D12_MEMORY_POOL_UNKNOWN;

        ID3D12Resource* uploadBuffer = nullptr;
        HRESULT hr = bd->pd3dDevice->CreateCommittedResource(&props, D3D12_HEAP_FLAG_NONE, &desc,
            D3D12_RESOURCE_STATE_GENERIC_READ, nullptr, IID_PPV_ARGS(&uploadBuffer));
        IM_ASSERT(SUCCEEDED(hr));

        void* mapped = nullptr;
        D3D12_RANGE range = { 0, uploadSize };
        hr = uploadBuffer->Map(0, &range, &mapped);
        IM_ASSERT(SUCCEEDED(hr));
        for (int y = 0; y < height; y++)
            memcpy((void*) ((uintptr_t) mapped + y * uploadPitch), pixels + y * width * 4, width * 4);
        uploadBuffer->Unmap(0, &range);

        D3D12_TEXTURE_COPY_LOCATION srcLocation = {};
        srcLocation.pResource = uploadBuffer;
        srcLocation.Type = D3D12_TEXTURE_COPY_TYPE_PLACED_FOOTPRINT;
        srcLocation.PlacedFootprint.Footprint.Format = DXGI_FORMAT_R8G8B8A8_UNORM;
        srcLocation.PlacedFootprint.Footprint.Width = width;
        srcLocation.PlacedFootprint.Footprint.Height = height;
        srcLocation.PlacedFootprint.Footprint.Depth = 1;
        srcLocation.PlacedFootprint.Footprint.RowPitch = uploadPitch;

        D3D12_TEXTURE_COPY_LOCATION dstLocation = {};
        dstLocation.pResource = pTexture;
        dstLocation.Type = D3D12_TEXTURE_COPY_TYPE_SUBRESOURCE_INDEX;
        dstLocation.SubresourceIndex = 0;

        D3D12_RESOURCE_BARRIER barrier = {};
        barrier.Type = D3D12_RESOURCE_BARRIER_TYPE_TRANSITION;
        barrier.Flags = D3D12_RESOURCE_BARRIER_FLAG_NONE;
        barrier.Transition.pResource   = pTexture;
        barrier.Transition.Subresource = D3D12_RESOURCE_BARRIER_ALL_SUBRESOURCES;
        barrier.Transition.StateBefore = D3D12_RESOURCE_STATE_COPY_DEST;
        barrier.Transition.StateAfter  = D3D12_RESOURCE_STATE_PIXEL_SHADER_RESOURCE;

        ID3D12Fence* fence = nullptr;
        hr = bd->pd3dDevice->CreateFence(0, D3D12_FENCE_FLAG_NONE, IID_PPV_ARGS(&fence));
        IM_ASSERT(SUCCEEDED(hr));

        HANDLE event = CreateEvent(0, 0, 0, 0);
        IM_ASSERT(event != nullptr);

        D3D12_COMMAND_QUEUE_DESC queueDesc = {};
        queueDesc.Type     = D3D12_COMMAND_LIST_TYPE_DIRECT;
        queueDesc.Flags    = D3D12_COMMAND_QUEUE_FLAG_NONE;
        queueDesc.NodeMask = 1;

        ID3D12CommandQueue* cmdQueue = nullptr;
        hr = bd->pd3dDevice->CreateCommandQueue(&queueDesc, IID_PPV_ARGS(&cmdQueue));
        IM_ASSERT(SUCCEEDED(hr));

        ID3D12CommandAllocator* cmdAlloc = nullptr;
        hr = bd->pd3dDevice->CreateCommandAllocator(D3D12_COMMAND_LIST_TYPE_DIRECT, IID_PPV_ARGS(&cmdAlloc));
        IM_ASSERT(SUCCEEDED(hr));

        ID3D12GraphicsCommandList* cmdList = nullptr;
        hr = bd->pd3dDevice->CreateCommandList(0, D3D12_COMMAND_LIST_TYPE_DIRECT, cmdAlloc, nullptr, IID_PPV_ARGS(&cmdList));
        IM_ASSERT(SUCCEEDED(hr));

        cmdList->CopyTextureRegion(&dstLocation, 0, 0, 0, &srcLocation, nullptr);
        cmdList->ResourceBarrier(1, &barrier);

        hr = cmdList->Close();
        IM_ASSERT(SUCCEEDED(hr));

        cmdQueue->ExecuteCommandLists(1, (ID3D12CommandList* const*)&cmdList);
        hr = cmdQueue->Signal(fence, 1);
        IM_ASSERT(SUCCEEDED(hr));

        fence->SetEventOnCompletion(1, event);
        WaitForSingleObject(event, INFINITE);

        cmdList->Release();
        cmdAlloc->Release();
        cmdQueue->Release();
        CloseHandle(event);
        fence->Release();
        uploadBuffer->Release();

        // Create texture view
        D3D12_SHADER_RESOURCE_VIEW_DESC srvDesc;
        ZeroMemory(&srvDesc, sizeof(srvDesc));
        srvDesc.Format = DXGI_FORMAT_R8G8B8A8_UNORM;
        srvDesc.ViewDimension = D3D12_SRV_DIMENSION_TEXTURE2D;
        srvDesc.Texture2D.MipLevels = desc.MipLevels;
        srvDesc.Texture2D.MostDetailedMip = 0;
        srvDesc.Shader4ComponentMapping = D3D12_DEFAULT_SHADER_4_COMPONENT_MAPPING;
        bd->pd3dDevice->CreateShaderResourceView(pTexture, &srvDesc, bd->hFontSrvCpuDescHandle);
        SafeRelease(bd->pFontTextureResource);
        bd->pFontTextureResource = pTexture;
    }

    // Store our identifier
    // READ THIS IF THE STATIC_ASSERT() TRIGGERS:
    // - Important: to compile on 32-bit systems, this backend requires code to be compiled with '#define ImTextureID ImU64'.
    // - This is because we need ImTextureID to carry a 64-bit value and by default ImTextureID is defined as void*.
    // [Solution 1] IDE/msbuild: in "Properties/C++/Preprocessor Definitions" add 'ImTextureID=ImU64' (this is what we do in the 'example_win32_direct12/example_win32_direct12.vcxproj' project file)
    // [Solution 2] IDE/msbuild: in "Properties/C++/Preprocessor Definitions" add 'IMGUI_USER_CONFIG="my_imgui_config.h"' and inside 'my_imgui_config.h' add '#define ImTextureID ImU64' and as many other options as you like.
    // [Solution 3] IDE/msbuild: edit imconfig.h and add '#define ImTextureID ImU64' (prefer solution 2 to create your own config file!)
    // [Solution 4] command-line: add '/D ImTextureID=ImU64' to your cl.exe command-line (this is what we do in the example_win32_direct12/build_win32.bat file)
    static_assert(sizeof(ImTextureID) >= sizeof(bd->hFontSrvGpuDescHandle.ptr), "Can't pack descriptor handle into TexID, 32-bit not supported yet.");
    io.Fonts->SetTexID((ImTextureID)bd->hFontSrvGpuDescHandle.ptr);
}

bool    ImGui_ImplDX12_CreateDeviceObjects()
{
    ImGui_ImplDX12_Data* bd = ImGui_ImplDX12_GetBackendData();
    if (!bd || !bd->pd3dDevice)
        return false;
    if (bd->pPipelineState)
        ImGui_ImplDX12_InvalidateDeviceObjects();

    // Create the root signature
    {
        D3D12_DESCRIPTOR_RANGE descRange = {};
        descRange.RangeType = D3D12_DESCRIPTOR_RANGE_TYPE_SRV;
        descRange.NumDescriptors = 1;
        descRange.BaseShaderRegister = 0;
        descRange.RegisterSpace = 0;
        descRange.OffsetInDescriptorsFromTableStart = 0;

        D3D12_ROOT_PARAMETER param[2] = {};

        param[0].ParameterType = D3D12_ROOT_PARAMETER_TYPE_32BIT_CONSTANTS;
        param[0].Constants.ShaderRegister = 0;
        param[0].Constants.RegisterSpace = 0;
        param[0].Constants.Num32BitValues = 16;
        param[0].ShaderVisibility = D3D12_SHADER_VISIBILITY_VERTEX;

        param[1].ParameterType = D3D12_ROOT_PARAMETER_TYPE_DESCRIPTOR_TABLE;
        param[1].DescriptorTable.NumDescriptorRanges = 1;
        param[1].DescriptorTable.pDescriptorRanges = &descRange;
        param[1].ShaderVisibility = D3D12_SHADER_VISIBILITY_PIXEL;

        // Bilinear sampling is required by default. Set 'io.Fonts->Flags |= ImFontAtlasFlags_NoBakedLines' or 'style.AntiAliasedLinesUseTex = false' to allow point/nearest sampling.
        D3D12_STATIC_SAMPLER_DESC staticSampler = {};
        staticSampler.Filter = D3D12_FILTER_MIN_MAG_MIP_LINEAR;
        staticSampler.AddressU = D3D12_TEXTURE_ADDRESS_MODE_WRAP;
        staticSampler.AddressV = D3D12_TEXTURE_ADDRESS_MODE_WRAP;
        staticSampler.AddressW = D3D12_TEXTURE_ADDRESS_MODE_WRAP;
        staticSampler.MipLODBias = 0.f;
        staticSampler.MaxAnisotropy = 0;
        staticSampler.ComparisonFunc = D3D12_COMPARISON_FUNC_ALWAYS;
        staticSampler.BorderColor = D3D12_STATIC_BORDER_COLOR_TRANSPARENT_BLACK;
        staticSampler.MinLOD = 0.f;
        staticSampler.MaxLOD = 0.f;
        staticSampler.ShaderRegister = 0;
        staticSampler.RegisterSpace = 0;
        staticSampler.ShaderVisibility = D3D12_SHADER_VISIBILITY_PIXEL;

        D3D12_ROOT_SIGNATURE_DESC desc = {};
        desc.NumParameters = _countof(param);
        desc.pParameters = param;
        desc.NumStaticSamplers = 1;
        desc.pStaticSamplers = &staticSampler;
        desc.Flags =
            D3D12_ROOT_SIGNATURE_FLAG_ALLOW_INPUT_ASSEMBLER_INPUT_LAYOUT |
            D3D12_ROOT_SIGNATURE_FLAG_DENY_HULL_SHADER_ROOT_ACCESS |
            D3D12_ROOT_SIGNATURE_FLAG_DENY_DOMAIN_SHADER_ROOT_ACCESS |
            D3D12_ROOT_SIGNATURE_FLAG_DENY_GEOMETRY_SHADER_ROOT_ACCESS;

        // Load d3d12.dll and D3D12SerializeRootSignature() function address dynamically to facilitate using with D3D12On7.
        // See if any version of d3d12.dll is already loaded in the process. If so, give preference to that.
        static HINSTANCE d3d12_dll = ::GetModuleHandleA("d3d12.dll");
        if (d3d12_dll == nullptr)
        {
            // Attempt to load d3d12.dll from local directories. This will only succeed if
            // (1) the current OS is Windows 7, and
            // (2) there exists a version of d3d12.dll for Windows 7 (D3D12On7) in one of the following directories.
            // See https://github.com/ocornut/imgui/pull/3696 for details.
            const char* localD3d12Paths[] = { ".\\d3d12.dll", ".\\d3d12on7\\d3d12.dll", ".\\12on7\\d3d12.dll" }; // A. current directory, B. used by some games, C. used in Microsoft D3D12On7 sample
            for (int i = 0; i < IM_ARRAYSIZE(localD3d12Paths); i++)
                if ((d3d12_dll = ::LoadLibraryA(localD3d12Paths[i])) != nullptr)
                    break;

            // If failed, we are on Windows >= 10.
            if (d3d12_dll == nullptr)
                d3d12_dll = ::LoadLibraryA("d3d12.dll");

            if (d3d12_dll == nullptr)
                return false;
        }

        PFN_D3D12_SERIALIZE_ROOT_SIGNATURE D3D12SerializeRootSignatureFn = (PFN_D3D12_SERIALIZE_ROOT_SIGNATURE)::GetProcAddress(d3d12_dll, "D3D12SerializeRootSignature");
        if (D3D12SerializeRootSignatureFn == nullptr)
            return false;

        ID3DBlob* blob = nullptr;
        if (D3D12SerializeRootSignatureFn(&desc, D3D_ROOT_SIGNATURE_VERSION_1, &blob, nullptr) != S_OK)
            return false;

        bd->pd3dDevice->CreateRootSignature(0, blob->GetBufferPointer(), blob->GetBufferSize(), IID_PPV_ARGS(&bd->pRootSignature));
        blob->Release();
    }

    // By using D3DCompile() from <d3dcompiler.h> / d3dcompiler.lib, we introduce a dependency to a given version of d3dcompiler_XX.dll (see D3DCOMPILER_DLL_A)
    // If you would like to use this DX12 sample code but remove this dependency you can:
    //  1) compile once, save the compiled shader blobs into a file or source code and assign them to psoDesc.VS/PS [preferred solution]
    //  2) use code to detect any version of the DLL and grab a pointer to D3DCompile from the DLL.
    // See https://github.com/ocornut/imgui/pull/638 for sources and details.

    D3D12_GRAPHICS_PIPELINE_STATE_DESC psoDesc;
    memset(&psoDesc, 0, sizeof(D3D12_GRAPHICS_PIPELINE_STATE_DESC));
    psoDesc.NodeMask = 1;
    psoDesc.PrimitiveTopologyType = D3D12_PRIMITIVE_TOPOLOGY_TYPE_TRIANGLE;
    psoDesc.pRootSignature = bd->pRootSignature;
    psoDesc.SampleMask = UINT_MAX;
    psoDesc.NumRenderTargets = 1;
    psoDesc.RTVFormats[0] = bd->RTVFormat;
    psoDesc.SampleDesc.Count = 1;
    psoDesc.Flags = D3D12_PIPELINE_STATE_FLAG_NONE;

    ID3DBlob* vertexShaderBlob;
    ID3DBlob* pixelShaderBlob;

    // Create the vertex shader
    {
        static const char* vertexShader =
            "cbuffer vertexBuffer : register(b0) \
            {\
              float4x4 ProjectionMatrix; \
            };\
            struct VS_INPUT\
            {\
              float2 pos : POSITION;\
              float4 col : COLOR0;\
              float2 uv  : TEXCOORD0;\
            };\
            \
            struct PS_INPUT\
            {\
              float4 pos : SV_POSITION;\
              float4 col : COLOR0;\
              float2 uv  : TEXCOORD0;\
            };\
            \
            PS_INPUT main(VS_INPUT input)\
            {\
              PS_INPUT output;\
              output.pos = mul( ProjectionMatrix, float4(input.pos.xy, 0.f, 1.f));\
              output.col = input.col;\
              output.uv  = input.uv;\
              return output;\
            }";

        if (FAILED(D3DCompile(vertexShader, strlen(vertexShader), nullptr, nullptr, nullptr, "main", "vs_5_0", 0, 0, &vertexShaderBlob, nullptr)))
            return false; // NB: Pass ID3DBlob* pErrorBlob to D3DCompile() to get error showing in (const char*)pErrorBlob->GetBufferPointer(). Make sure to Release() the blob!
        psoDesc.VS = { vertexShaderBlob->GetBufferPointer(), vertexShaderBlob->GetBufferSize() };

        // Create the input layout
        static D3D12_INPUT_ELEMENT_DESC local_layout[] =
        {
            { "POSITION", 0, DXGI_FORMAT_R32G32_FLOAT,   0, (UINT)IM_OFFSETOF(ImDrawVert, pos), D3D12_INPUT_CLASSIFICATION_PER_VERTEX_DATA, 0 },
            { "TEXCOORD", 0, DXGI_FORMAT_R32G32_FLOAT,   0, (UINT)IM_OFFSETOF(ImDrawVert, uv),  D3D12_INPUT_CLASSIFICATION_PER_VERTEX_DATA, 0 },
            { "COLOR",    0, DXGI_FORMAT_R8G8B8A8_UNORM, 0, (UINT)IM_OFFSETOF(ImDrawVert, col), D3D12_INPUT_CLASSIFICATION_PER_VERTEX_DATA, 0 },
        };
        psoDesc.InputLayout = { local_layout, 3 };
    }

    // Create the pixel shader
    {
        static const char* pixelShader =
            "struct PS_INPUT\
            {\
              float4 pos : SV_POSITION;\
              float4 col : COLOR0;\
              float2 uv  : TEXCOORD0;\
            };\
            SamplerState sampler0 : register(s0);\
            Texture2D texture0 : register(t0);\
            \
            float4 main(PS_INPUT input) : SV_Target\
            {\
              float4 out_col = input.col * texture0.Sample(sampler0, input.uv); \
              return out_col; \
            }";

        if (FAILED(D3DCompile(pixelShader, strlen(pixelShader), nullptr, nullptr, nullptr, "main", "ps_5_0", 0, 0, &pixelShaderBlob, nullptr)))
        {
            vertexShaderBlob->Release();
            return false; // NB: Pass ID3DBlob* pErrorBlob to D3DCompile() to get error showing in (const char*)pErrorBlob->GetBufferPointer(). Make sure to Release() the blob!
        }
        psoDesc.PS = { pixelShaderBlob->GetBufferPointer(), pixelShaderBlob->GetBufferSize() };
    }

    // Create the blending setup
    {
        D3D12_BLEND_DESC& desc = psoDesc.BlendState;
        desc.AlphaToCoverageEnable = false;
        desc.RenderTarget[0].BlendEnable = true;
        desc.RenderTarget[0].SrcBlend = D3D12_BLEND_SRC_ALPHA;
        desc.RenderTarget[0].DestBlend = D3D12_BLEND_INV_SRC_ALPHA;
        desc.RenderTarget[0].BlendOp = D3D12_BLEND_OP_ADD;
        desc.RenderTarget[0].SrcBlendAlpha = D3D12_BLEND_ONE;
        desc.RenderTarget[0].DestBlendAlpha = D3D12_BLEND_INV_SRC_ALPHA;
        desc.RenderTarget[0].BlendOpAlpha = D3D12_BLEND_OP_ADD;
        desc.RenderTarget[0].RenderTargetWriteMask = D3D12_COLOR_WRITE_ENABLE_ALL;
    }

    // Create the rasterizer state
    {
        D3D12_RASTERIZER_DESC& desc = psoDesc.RasterizerState;
        desc.FillMode = D3D12_FILL_MODE_SOLID;
        desc.CullMode = D3D12_CULL_MODE_NONE;
        desc.FrontCounterClockwise = FALSE;
        desc.DepthBias = D3D12_DEFAULT_DEPTH_BIAS;
        desc.DepthBiasClamp = D3D12_DEFAULT_DEPTH_BIAS_CLAMP;
        desc.SlopeScaledDepthBias = D3D12_DEFAULT_SLOPE_SCALED_DEPTH_BIAS;
        desc.DepthClipEnable = true;
        desc.MultisampleEnable = FALSE;
        desc.AntialiasedLineEnable = FALSE;
        desc.ForcedSampleCount = 0;
        desc.ConservativeRaster = D3D12_CONSERVATIVE_RASTERIZATION_MODE_OFF;
    }

    // Create depth-stencil State
    {
        D3D12_DEPTH_STENCIL_DESC& desc = psoDesc.DepthStencilState;
        desc.DepthEnable = false;
        desc.DepthWriteMask = D3D12_DEPTH_WRITE_MASK_ALL;
        desc.DepthFunc = D3D12_COMPARISON_FUNC_ALWAYS;
        desc.StencilEnable = false;
        desc.FrontFace.StencilFailOp = desc.FrontFace.StencilDepthFailOp = desc.FrontFace.StencilPassOp = D3D12_STENCIL_OP_KEEP;
        desc.FrontFace.StencilFunc = D3D12_COMPARISON_FUNC_ALWAYS;
        desc.BackFace = desc.FrontFace;
    }

    HRESULT result_pipeline_state = bd->pd3dDevice->CreateGraphicsPipelineState(&psoDesc, IID_PPV_ARGS(&bd->pPipelineState));
    vertexShaderBlob->Release();
    pixelShaderBlob->Release();
    if (result_pipeline_state != S_OK)
        return false;

    ImGui_ImplDX12_CreateFontsTexture();

    return true;
}

void    ImGui_ImplDX12_InvalidateDeviceObjects()
{
    ImGui_ImplDX12_Data* bd = ImGui_ImplDX12_GetBackendData();
    if (!bd || !bd->pd3dDevice)
        return;
    ImGuiIO& io = ImGui::GetIO();

    SafeRelease(bd->pRootSignature);
    SafeRelease(bd->pPipelineState);
    SafeRelease(bd->pFontTextureResource);
    io.Fonts->SetTexID(0); // We copied bd->pFontTextureView to io.Fonts->TexID so let's clear that as well.

    for (UINT i = 0; i < bd->numFramesInFlight; i++)
    {
        ImGui_ImplDX12_RenderBuffers* fr = &bd->pFrameResources[i];
        SafeRelease(fr->IndexBuffer);
        SafeRelease(fr->VertexBuffer);
    }
}

bool ImGui_ImplDX12_Init(ID3D12Device* device, int num_frames_in_flight, DXGI_FORMAT rtv_format, ID3D12DescriptorHeap* cbv_srv_heap,
                         D3D12_CPU_DESCRIPTOR_HANDLE font_srv_cpu_desc_handle, D3D12_GPU_DESCRIPTOR_HANDLE font_srv_gpu_desc_handle)
{
    ImGuiIO& io = ImGui::GetIO();
    IM_ASSERT(io.BackendRendererUserData == nullptr && "Already initialized a renderer backend!");

    // Setup backend capabilities flags
    ImGui_ImplDX12_Data* bd = IM_NEW(ImGui_ImplDX12_Data)();
    io.BackendRendererUserData = (void*)bd;
    io.BackendRendererName = "imgui_impl_dx12";
    io.BackendFlags |= ImGuiBackendFlags_RendererHasVtxOffset;  // We can honor the ImDrawCmd::VtxOffset field, allowing for large meshes.

    bd->pd3dDevice = device;
    bd->RTVFormat = rtv_format;
    bd->hFontSrvCpuDescHandle = font_srv_cpu_desc_handle;
    bd->hFontSrvGpuDescHandle = font_srv_gpu_desc_handle;
    bd->pFrameResources = new ImGui_ImplDX12_RenderBuffers[num_frames_in_flight];
    bd->numFramesInFlight = num_frames_in_flight;
    bd->frameIndex = UINT_MAX;
    IM_UNUSED(cbv_srv_heap); // Unused in master branch (will be used by multi-viewports)

    // Create buffers with a default size (they will later be grown as needed)
    for (int i = 0; i < num_frames_in_flight; i++)
    {
        ImGui_ImplDX12_RenderBuffers* fr = &bd->pFrameResources[i];
        fr->IndexBuffer = nullptr;
        fr->VertexBuffer = nullptr;
        fr->IndexBufferSize = 10000;
        fr->VertexBufferSize = 5000;
    }

    return true;
}

void ImGui_ImplDX12_Shutdown()
{
    ImGui_ImplDX12_Data* bd = ImGui_ImplDX12_GetBackendData();
    IM_ASSERT(bd != nullptr && "No renderer backend to shutdown, or already shutdown?");
    ImGuiIO& io = ImGui::GetIO();

    ImGui_ImplDX12_InvalidateDeviceObjects();
    delete[] bd->pFrameResources;
    io.BackendRendererName = nullptr;
    io.BackendRendererUserData = nullptr;
    IM_DELETE(bd);
}

void ImGui_ImplDX12_NewFrame()
{
    ImGui_ImplDX12_Data* bd = ImGui_ImplDX12_GetBackendData();
    IM_ASSERT(bd != nullptr && "Did you call ImGui_ImplDX12_Init()?");

    if (!bd->pPipelineState)
        ImGui_ImplDX12_CreateDeviceObjects();
}

redpajama_set_name: RedPajamaGithub


text:
declare module "quasar/lang/*" {
  // We know "quasar" will exists at runtime, we can safely ignore the TS error
  // @ts-ignore
  import { QuasarLanguage } from "quasar";
  const lang: QuasarLanguage;
  export default lang;
}


text:
/*
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/** @jsx h */
import { h } from 'preact';
import classNames from 'classnames';

import './style.scss';
import Align from '../../components/Align';
import ButtonClose from '../../components/ButtonClose';

export default function Overlay({ children, onClose, opaque }) {
  return (
    <div
      className={classNames('overlay', opaque && 'mod-opaque')}
      onClick={onClose}
    >
      {onClose && (
        <Align type="top-right">
          <ButtonClose onClick={onClose} />
        </Align>
      )}
      <div className="overlay-text">
        {children}
      </div>
    </div>
  );
}


text:
package com.hubspot.singularity.data;

import static java.nio.charset.StandardCharsets.UTF_8;

import com.codahale.metrics.MetricRegistry;
import com.google.inject.Inject;
import com.google.inject.Singleton;
import com.hubspot.singularity.SingularityEmailType;
import com.hubspot.singularity.SingularityRequest;
import com.hubspot.singularity.config.SingularityConfiguration;
import com.hubspot.singularity.data.transcoders.StringTranscoder;
import java.util.List;
import java.util.Optional;
import org.apache.curator.framework.CuratorFramework;
import org.apache.curator.utils.ZKPaths;
import org.apache.zookeeper.data.Stat;

@Singleton
public class MetadataManager extends CuratorManager {
  private static final String ROOT_PATH = "/metadata";
  private static final String ZK_DATA_VERSION_PATH = ZKPaths.makePath(
    ROOT_PATH,
    "ZK_DATA_VERSION"
  );
  private static final String MAIL_HISTORY_PATH = ROOT_PATH + "/mails";
  private static final String MAIL_HISTORY_RECORDS_KEY = "timestamps";
  private static final String MAIL_IN_COOLDOWN_MARKER_KEY = "COOLDOWN_ACTIVE";

  @Inject
  public MetadataManager(
    CuratorFramework curator,
    SingularityConfiguration configuration,
    MetricRegistry metricRegistry
  ) {
    super(curator, configuration, metricRegistry);
  }

  private String getMailRecordPathForRequest(String requestId) {
    return ZKPaths.makePath(MAIL_HISTORY_PATH, requestId);
  }

  private String getMailRecordPathForRequestAndType(String requestId, String emailType) {
    return ZKPaths.makePath(getMailRecordPathForRequest(requestId), emailType);
  }

  private String getMailRecordTimestampPath(String requestId, String emailType) {
    return ZKPaths.makePath(
      getMailRecordPathForRequestAndType(requestId, emailType),
      MAIL_HISTORY_RECORDS_KEY
    );
  }

  private String getMailRecordCooldownPath(String requestId, String emailType) {
    return ZKPaths.makePath(
      getMailRecordPathForRequestAndType(requestId, emailType),
      MAIL_IN_COOLDOWN_MARKER_KEY
    );
  }

  private String getMailRecordPathForRequestAndTypeAndTime(
    String requestId,
    String emailType,
    String mailRecordTimestamp
  ) {
    return ZKPaths.makePath(
      getMailRecordTimestampPath(requestId, emailType),
      mailRecordTimestamp
    );
  }

  public Optional<String> getZkDataVersion() {
    return getStringData(ZK_DATA_VERSION_PATH);
  }

  public void setZkDataVersion(String newVersion) {
    save(ZK_DATA_VERSION_PATH, Optional.of(newVersion.getBytes(UTF_8)));
  }

  public void saveMailRecord(SingularityRequest request, SingularityEmailType emailType) {
    create(
      getMailRecordPathForRequestAndTypeAndTime(
        request.getId(),
        emailType.name(),
        Long.toString(System.currentTimeMillis())
      )
    );
  }

  public List<String> getMailRecords(String requestId, String emailType) {
    return getChildren(getMailRecordTimestampPath(requestId, emailType));
  }

  public List<String> getRequestsWithMailRecords() {
    return getChildren(MAIL_HISTORY_PATH);
  }

  public List<String> getEmailTypesWithMailRecords(String requestId) {
    return getChildren(getMailRecordPathForRequest(requestId));
  }

  public Optional<String> getMailCooldownMarker(String requestId, String emailType) {
    return getData(
      getMailRecordCooldownPath(requestId, emailType),
      StringTranscoder.INSTANCE
    );
  }

  public void cooldownMail(String requestId, String emailType) {
    create(
      getMailRecordCooldownPath(requestId, emailType),
      Long.toString(System.currentTimeMillis()),
      StringTranscoder.INSTANCE
    );
  }

  public void removeMailCooldown(String requestId, String emailType) {
    delete(getMailRecordCooldownPath(requestId, emailType));
  }

  public void deleteMailRecord(
    String requestId,
    String emailType,
    String mailRecordTimestamp
  ) {
    delete(
      getMailRecordPathForRequestAndTypeAndTime(requestId, emailType, mailRecordTimestamp)
    );
  }

  public void purgeStaleRequests(List<String> activeRequestIds, long deleteBeforeTime) {
    final List<String> requestIds = getChildren(MAIL_HISTORY_PATH);
    for (String requestId : requestIds) {
      if (!activeRequestIds.contains(requestId)) {
        String path = getMailRecordPathForRequest(requestId);
        Optional<Stat> maybeStat = checkExists(
          ZKPaths.makePath(path, SingularityEmailType.REQUEST_REMOVED.name())
        );
        if (maybeStat.isPresent() && maybeStat.get().getMtime() < deleteBeforeTime) {
          delete(path);
        }
      }
    }
  }
}


text:
package de.cosmocode.issuetracker.activecollab;

import org.codehaus.jackson.JsonNode;

import de.cosmocode.issuetracker.IssueTracker;
import de.cosmocode.issuetracker.IssueTrackerException;

/**
 * Default {@link ActiveCollabIssue} implementation.
 *
 * @author Tobias Sarnowski
 */
final class DefaultActiveCollabIssue implements ActiveCollabIssue {

    private final DefaultActiveCollab ac;
    private String id;
    private String title;
    private String description;
    private int visibility;
    private int milestoneId;
    private int parentId;

    DefaultActiveCollabIssue(DefaultActiveCollab ac, JsonNode json) {
        this.ac = ac;
        this.id = Integer.toString(json.get("id").getIntValue());
    }

    @Override
    public String getId() {
        return id;
    }

    @Override
    public IssueTracker getIssueTracker() {
        return ac;
    }

    @Override
    public String getTitle() {
        return title;
    }

    @Override
    public void setTitle(String title) {
        throw new UnsupportedOperationException();
    }

    @Override
    public String getDescription() {
        return description;
    }

    @Override
    public void setDescription(String description) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void update() throws IssueTrackerException {
        ac.updateIssue(this);
    }

    @Override
    public int getVisibility() {
        return visibility;
    }

    @Override
    public void setVisibility(int visibility) {
        this.visibility = visibility;
    }

    @Override
    public int getMilestoneId() {
        return milestoneId;
    }

    @Override
    public void setMilestoneId(int milestoneId) {
        this.milestoneId = milestoneId;
    }

    @Override
    public int getParentId() {
        return parentId;
    }

    @Override
    public void setParentId(int parentId) {
        this.parentId = parentId;
    }

    @Override
    public String toString() {
        return "ActiveCollabIssue [ac=" + ac + ", id=" + id + "]";
    }

}


text:
ACCEPTED

#### According to
The Catalogue of Life, 3rd January 2011

#### Published in
Atti Soc. Veneto-Trent. Sci. Nat. 10(1): 183 (1886)

#### Original name
Phoma samaricola Sacc., 1884

### Remarks
null


text:
package gui.components;

import javax.swing.JTextField;
import javax.swing.text.PlainDocument;

public class JDoubleTextField extends JTextField{

	/**
	 *
	 */
	private static final long serialVersionUID = 1L;

	public JDoubleTextField(){

		super();
		PlainDocument doc = new PlainDocument();
		doc.setDocumentFilter(new NumberFilter());
		setDocument(doc);

	}

}


text:
package com.LSH.client.DataType;

import java.io.Serializable;

/**
 * Created by @author AlNat on 01.12.2016.
 * Licensed by Apache License, Version 2.0
 *
 * Класс обертка для сообщения между клиентом и сервером
 * для передачи данных об управляемом сворачивании ссылки
 */
public class PutLinkData implements Serializable {

    /* Геттеры и сеттеры */
    public String getOriginalLink() {
        return originalLink;
    }

    public void setOriginalLink(String originalLink) {
        this.originalLink = originalLink;
    }

    public String getShortLink() {
        return shortLink;
    }

    public String getTtl() {
        return ttl;
    }

    public Integer getMaxVisits() {
        return maxVisits;
    }

    public String getBrowser() {
        return browser;
    }

    public void setBrowser(String browser) {
        this.browser = browser;
    }

    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public String getPassword() {
        return password;
    }

    public void setPassword(String password) {
        this.password = password;
    }

    public String getUserLogin() {
        return userLogin;
    }

    public void setUserLogin(String userLogin) {
        this.userLogin = userLogin;
    }

    /* Данные */
    private String originalLink; // Оригинальный линк
    private String shortLink; // Короткая ссылка - мнемоническая
    private String ttl; // Время жизни ссылки
    private Integer maxVisits; // Максимальное кол-во визитов
    private String browser;  // user-agent пользователя
    private String ip; // IP адрес пользователя
    private String password; // Пароль на ссылку
    private String userLogin; // Логин пользователя

    /* Конструкторы */
    PutLinkData() {
        originalLink = "";
    }

    public PutLinkData(String originalLink) {
        this.originalLink = originalLink;
        shortLink = "NULL"; // Кодовое слово
        ttl = "1 week"; // Неделю по дефолту
        maxVisits = 0; // Бесконечное по дефолту
    }

    public PutLinkData(String originalLink, String ttl, Integer maxVisits) {
        this.originalLink = originalLink;
        shortLink = "NULL"; // Кодовое слово
        this.ttl = ttl;
        this.maxVisits = maxVisits;
    }

    public PutLinkData(String originalLink, String ttl, Integer maxVisits, String shortLink) {
        this.originalLink = originalLink;
        this.shortLink = shortLink;
        this.ttl = ttl;
        this.maxVisits = maxVisits;
    }

    @Override
    public String toString () {
        return "{originalLink = " + originalLink +
                "; shortLink = " + shortLink +
                "; ttl = " + ttl +
                "; maxVisits = " + maxVisits +
                "; IP = " + ip +
                "; browser = " + browser +
                "; Password(MD5) = " + password +
                "; Login = " + userLogin +
                "}";
    }

}


text:
from twisted.application.service import ServiceMaker

Spark = ServiceMaker(
        "Sparked",
        "sparked.tap",
        "Sparked application launcher",
        "sparked")


text:
package cn.ezandroid.ezfilter.render.particle;

import android.content.Context;
import android.graphics.Color;
import android.opengl.GLES20;

import org.jetbrains.annotations.NotNull;

import cn.ezandroid.lib.ezfilter.core.FilterRender;
import cn.ezandroid.lib.ezfilter.core.util.BitmapUtil;
import cn.ezandroid.lib.ezfilter.core.util.Path;
import cn.ezandroid.ezfilter.R;
import cn.ezandroid.ezfilter.render.particle.util.Geometry;

/**
 * 粒子效果滤镜
 *
 * @author like
 * @date 2018-05-15
 */
public class ParticleRender extends FilterRender {

    private ParticleShaderProgram mParticleShaderProgram;
    private ParticleSystem mParticleSystem;
    private ParticleShooter mParticleShooter;

    private int mTexture;

    private final Context mContext;

    private boolean mIsPause = true;

    public interface IParticleTimeController {

        float getCurrentTime();
    }

    private final IParticleTimeController mTimeController;

    public ParticleRender(Context context, @NotNull IParticleTimeController controller) {
        mContext = context;
        mTimeController = controller;
    }

    @Override
    protected void initGLContext() {
        super.initGLContext();

        mParticleSystem = new ParticleSystem(10000);

        mParticleShaderProgram = new ParticleShaderProgram(mContext);

        mParticleShooter = new ParticleShooter(new Geometry.Point(0, 0, 0), 10,
                new Geometry.Vector(0.0f, 0.2f, 0.0f), 360, 1f,
                16, 4, 32, 4,
                0, 10, 360, 10,
                Color.argb(255, 255, 0, 0), Color.argb(0, 0, 0, 0),
                Color.argb(255, 0, 0, 255), Color.argb(0, 0, 0, 0),
                1f,
                2);

        mTexture = BitmapUtil.bindBitmap(BitmapUtil.loadBitmap(mContext, Path.DRAWABLE.wrap(String.valueOf(R.drawable.texture))));
    }

    public void setPosition(Geometry.Point position) {
        if (mParticleShooter != null) {
            mParticleShooter.setPosition(position);
        }
    }

    public void start() {
        mIsPause = false;
    }

    public void pause() {
        mIsPause = true;
    }

    @Override
    protected void onDraw() {
        super.onDraw();

        // 开启混合
        GLES20.glEnable(GLES20.GL_BLEND);
        GLES20.glBlendFunc(GLES20.GL_ONE, GLES20.GL_ONE_MINUS_SRC_ALPHA);

        mParticleShaderProgram.useProgram(); // 切换到粒子效果渲染程序

        if (!mIsPause) {
            mParticleShooter.addParticles(mParticleSystem, mTimeController.getCurrentTime());
        }

        mParticleShaderProgram.setUniforms(mTimeController.getCurrentTime(), mTexture, 2);

        mParticleSystem.bindData(mParticleShaderProgram);
        mParticleSystem.draw();

        GLES20.glDisable(GLES20.GL_BLEND);
    }
}


text:
<?php
include('inc_info.php');
include('inc_criterions_checklist.php');


text:
.passwords_email, .passwords_reset {
    background: #F7F7F7;
}


text:
package jiconfont.examples.javafx;

import java.io.InputStream;
import javafx.application.Application;
import javafx.scene.Scene;
import javafx.scene.layout.Background;
import javafx.scene.layout.BackgroundFill;
import javafx.scene.layout.StackPane;
import javafx.scene.paint.Color;
import javafx.stage.Stage;
import jiconfont.DefaultIconCode;
import jiconfont.IconFont;
import jiconfont.javafx.IconFontFX;
import jiconfont.javafx.IconNode;

public class Example7 extends Application {

    @Override
    public void start(Stage stage) {
        StackPane root = new StackPane();
        root.setBackground(new Background(new BackgroundFill(Color.WHITE, null, null)));

        // Register my custom IconFont
        IconFontFX.register(new IconFont() {
            @Override
            public String getFontFamily() {
                return "Entypo";
            }

            @Override
            public InputStream getFontInputStream() {
                return Example7.class.getResourceAsStream("/entypo.ttf");
            }
        });

        IconNode iconNode = new IconNode();
        iconNode.setIconCode(new DefaultIconCode("Entypo", '\uE70C'));

        root.getChildren().add(iconNode);
        Scene scene = new Scene(root, 300, 300);
        scene.getStylesheets().add("style.css");
        stage.setTitle("jIconFont - JavaFX - Catalog");
        stage.setScene(scene);
        stage.show();
        stage.centerOnScreen();

    }

    public static void main(String[] args) {
        launch(args);
    }
}