Investigating Myers' diff algorithm: Part 1 of 2

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Diagnostics;

using DiffCommon;

namespace DiffControls
{
	partial class GridControl : Control
	{

		//-----------------------------------------------------------------------------------------------

		static readonly Color cMesh = Color.FromArgb( unchecked( ( int ) 0xFF636363 ) );
		static readonly Color cKEven = Color.FromArgb( unchecked( ( int ) 0xFF848400 ) );
		static readonly Color cKOdd = Color.FromArgb( unchecked( ( int ) 0xFF846300 ) );
		static readonly Color cDiagonal = Color.White;
		static readonly Color cIdeal = Color.Magenta;
		static readonly Color cBounds = Color.FromArgb( unchecked( ( int ) 0xFF848484 ) );
		static readonly Color cSnakeForward = Color.FromArgb( unchecked( ( int ) 0xFF0000FF ) );
		static readonly Color cSnakeReverse = Color.FromArgb( unchecked( ( int ) 0xFF00C600 ) );
		static readonly Color cContourForward = Color.FromArgb( unchecked( ( int ) 0xFF80B0FF ) );
		static readonly Color cContourReverse = Color.FromArgb( unchecked( ( int ) 0xFF42C6A5 ) );
		static readonly Color cSolution = Color.Red;
		static readonly Color cSolutionMiddle = Color.Pink;

		//-----------------------------------------------------------------------------------------------

		char[] _A, _B;
		int _LenA, _LenB, _Delta;

		const int GRID_SQUARE = 100;
		const float GRID_SQUARE_F = GRID_SQUARE;

		float _OffsetA, _OffsetB;
		public float OffsetA { get { return _OffsetA; } set { _OffsetA = Math.Min( Math.Max( value, 1 - ViewportRectangleExact.Width ), _LenA - 1 ); Invalidate(); } }
		public float OffsetB { get { return _OffsetB; } set { _OffsetB = Math.Min( Math.Max( value, 1 - ViewportRectangleExact.Height ), _LenB - 1 ); Invalidate(); } }
		public PointF Offset { get { return new PointF( OffsetA, OffsetB ); } set { OffsetA = value.X; OffsetB = value.Y; } }

		float _Zoom = 1;
		int _ZoomExponent = 0;

		bool _DrawIdeal = false;
		public bool DrawIdeal { get { return _DrawIdeal; } set { _DrawIdeal = value; Invalidate(); } }

		bool _DrawDiagonals = false;
		public bool DrawDiagonals { get { return _DrawDiagonals; } set { _DrawDiagonals = value; Invalidate(); } }

		bool _DrawSolution = false;
		public bool DrawSolution { get { return _DrawSolution; } set { _DrawSolution = value; Invalidate(); } }

		bool _DrawEvenK = false;
		public bool DrawEvenK { get { return _DrawEvenK; } set { _DrawEvenK = value; Invalidate(); } }

		bool _DrawOddK = false;
		public bool DrawOddK { get { return _DrawOddK; } set { _DrawOddK = value; Invalidate(); } }

		bool _DrawStats = false;
		public bool DrawStats { get { return _DrawStats; } set { _DrawStats = value; Invalidate(); } }

		//-----------------------------------------------------------------------------------------------

		ResultType _ResultType = ResultType.None;
		public ResultType ResultType { get { return _ResultType; } set { _ResultType = value; Invalidate(); } }

		ResultBag _ResultBag = null;

		IList<Snake> Solution
		{
			get
			{
				if ( _ResultBag == null ) return null;

				switch ( _ResultType )
				{
					case ResultType.Forward: return _ResultBag.Forward.Snakes;
					case ResultType.Reverse: return _ResultBag.Reverse.Snakes;
					case ResultType.Linear: return _ResultBag.Linear.Snakes;

					case ResultType.None:
					default: return null;
				}
			}
		}

		IList<V> ForwardVs
		{
			get
			{
				if ( _ResultBag == null ) return null;

				switch ( _ResultType )
				{
					case ResultType.Forward: return _ResultBag.Forward.ForwardVs;
					case ResultType.Reverse: return _ResultBag.Reverse.ForwardVs;
					case ResultType.Linear: return _ResultBag.Linear.ForwardVs;

					case ResultType.None:
					default: return null;
				}
			}
		}

		IList<V> ReverseVs
		{
			get
			{
				if ( _ResultBag == null ) return null;

				switch ( _ResultType )
				{
					case ResultType.Forward: return _ResultBag.Forward.ReverseVs;
					case ResultType.Reverse: return _ResultBag.Reverse.ReverseVs;
					case ResultType.Linear: return _ResultBag.Linear.ReverseVs;

					case ResultType.None:
					default: return null;
				}
			}
		}

		bool Forward
		{
			get
			{
				if ( _ResultBag == null ) return false;

				switch ( _ResultType )
				{
					case ResultType.Forward: return true;
					case ResultType.Reverse: return false;
					case ResultType.Linear: return true;

					case ResultType.None:
					default: return false;
				}
			}
		}

		int Delta
		{
			get
			{
				if ( _ResultBag == null ) return 0;

				switch ( _ResultType )
				{
					case ResultType.Forward: return 0;
					case ResultType.Reverse: return _Delta;
					case ResultType.Linear: return 0;

					case ResultType.None:
					default: return 0;
				}
			}
		}

		//-----------------------------------------------------------------------------------------------

		public GridControl()
		{
			InitializeComponent();

			_LenA = _LenB = 1;

			BackColor = Color.Black;
			DoubleBuffered = true;

			SetStyle(
				ControlStyles.OptimizedDoubleBuffer |
				ControlStyles.AllPaintingInWmPaint |
				ControlStyles.UserPaint |
				ControlStyles.ResizeRedraw |
				ControlStyles.Selectable |
				0, true );

			//Padding = new Padding( 100 );
			Margin = new Padding( 20 );
			MinimumSize = new Size( 256, 256 );

			MouseDown += new MouseEventHandler( HandlesMouseDown );
			MouseMove += new MouseEventHandler( HandlesMouseMove );
			MouseUp += new MouseEventHandler( HandlesMouseUp );
			MouseDoubleClick += new MouseEventHandler( HandlesMouseDoubleClick );
		}

		//-----------------------------------------------------------------------------------------------

		public void SetResults( ResultBag bag )
		{
			_ResultBag = bag;

			SetText( bag.A, bag.B );
		}

		void SetText( char[] a, char[] b )
		{
			_A = a;
			_B = b;

			_LenA = _A.Length;
			_LenB = _B.Length;
			_Delta = _LenA - _LenB;

			CalcZoom();

			CentreOnIndex( new PointF( _LenA / 2f, _LenB / 2f ) );

			Invalidate();
		}

		//-----------------------------------------------------------------------------------------------
		// Properties controlled by GridUserControl

		public int Zoom
		{
			//get { return _ZoomExponent; }
			set
			{
				if ( value < 0 ) value = 0;
				if ( value > 1000 ) value = 1000;

				_ZoomExponent = value;

				CalcZoom();

				Invalidate();
			}
		}


		//-----------------------------------------------------------------------------------------------
		// OnSizeChanged

		protected override void OnSizeChanged( EventArgs e )
		{
			base.OnSizeChanged( e );

			_WindowRectangleStale = true;

			CalcZoom();

			Invalidate();
		}

		//-----------------------------------------------------------------------------------------------
		// Mouse

		bool _MouseDragging = false;
		PointF _MouseCentreIndex;
		PointF _MouseOffset;
		State _MouseCurrentState;

		void HandlesMouseDown( object sender, MouseEventArgs e )
		{
			//Debug.WriteLine( "Mouse DOWN " + e.Location );

			Focus();

			if ( _MouseDragging ) return;

			_MouseDragging = true;

			_MouseCentreIndex = CalcIndexExact( e.Location );
			_MouseOffset = Offset;
			_MouseCurrentState = CurrentState;
		}

		void HandlesMouseMove( object sender, MouseEventArgs e )
		{
			using ( var g = CreateGraphics() ) PaintMouse( g, e.Location );

			if ( !_MouseDragging ) return;

			//Debug.WriteLine( "Mouse DRAG " + e.Location );

			var nowIndex = CalcIndexExact( e.Location.X, e.Location.Y, ref _MouseCurrentState );

			Offset = new PointF( _MouseOffset.X + _MouseCentreIndex.X - nowIndex.X, _MouseOffset.Y + _MouseCentreIndex.Y - nowIndex.Y );
		}

		void HandlesMouseUp( object sender, MouseEventArgs e )
		{
			//Debug.WriteLine( "Mouse UP " + e.Location );

			_MouseDragging = false;
		}

		void HandlesMouseDoubleClick( object sender, MouseEventArgs e )
		{
			//Debug.WriteLine( "Mouse DOUBLECLICK " + e.Location );

			var m = CalcMiddleIndexExact();
			var o = CalcIndexExact( e.Location );
			Offset = new PointF( OffsetA + o.X - m.X, OffsetB + o.Y - m.Y );
		}

		//-----------------------------------------------------------------------------------------------
		// Coeffs

		float ZoomFit
		{
			get
			{
				var wr = WindowRectangle;

				var drawRectangleX = GRID_SQUARE_F * Math.Max( _LenA, 1 );
				var drawRectangleY = GRID_SQUARE_F * Math.Max( _LenB, 1 );

				var fitX = wr.Width / drawRectangleX;
				var fitY = wr.Height / drawRectangleY;

				var fit = Math.Min( fitX, fitY );

				return fit;
			}
		}

		float ZoomMin { get { return ZoomFit / 5f; } }
		float ZoomMax { get { return 1f; } } // log( 1 ) = 0

		void CalcZoom()
		{
			var zoomMin = ZoomMin;

			var mOld = CalcMiddleIndexExact(); // save mid

			if ( zoomMin == 0 ) _Zoom = 1;
			else
			{
				var zoomOrder = Math.Log10( zoomMin );
				var zoomSlider = 1f - ( _ZoomExponent / 1000f ); // 0..1
				var zoomLog = zoomOrder * zoomSlider;
				var zoom = Math.Pow( 10, zoomLog );

				_Zoom = ( float ) Math.Min( Math.Max( zoom, zoomMin ), ZoomMax );
			}

			//var mNow = CalcMiddleIndexExact();

			//Offset = new PointF( OffsetA + mOld.X - mNow.X, OffsetB + mOld.Y - mNow.Y );

			CentreOnIndex( mOld );
		}

		void CentreOnIndex( PointF index )
		{
			var m = CalcMiddleIndexExact();

			Offset = new PointF( OffsetA + index.X - m.X, OffsetB + index.Y - m.Y );
		}

		public int CalcZoomSlider( float zoom )
		{
			var zoomMin = ZoomMin;

			zoom = Math.Min( Math.Max( zoom, zoomMin ), ZoomMax );

			var slider = 1000 * ( 1 - ( Math.Log( zoom ) / Math.Log( zoomMin ) ) );

			return ( int ) Math.Min( Math.Max( slider, 0 ), 1000 );
		}

		public int ZoomSliderFit { get { return CalcZoomSlider( ZoomFit / 2f ); } }

		Point CalcScreen( Point p )
		{
			return CalcScreen( p.X, p.Y );
		}

		Point CalcScreen( PointF p )
		{
			return CalcScreen( p.X, p.Y );
		}

		Point CalcScreen( float x, float y )
		{
			var wr = WindowRectangle;

			return new Point( wr.Left + ( int ) ( ( x - OffsetA ) * GRID_SQUARE_F * _Zoom ), wr.Top + ( int ) ( ( y - OffsetB ) * GRID_SQUARE_F * _Zoom ) );
		}

		Rectangle CalcScreen( Rectangle r )
		{
			return CalcScreen( r.Left, r.Top, r.Right, r.Bottom );
		}

		Rectangle CalcScreen( RectangleF r )
		{
			return CalcScreen( r.Left, r.Top, r.Right, r.Bottom );
		}

		Rectangle CalcScreen( float l, float t, float r, float b )
		{
			var tl = CalcScreen( l, t );
			var br = CalcScreen( r, b );

			return new Rectangle( tl.X, tl.Y, br.X - tl.X, br.Y - tl.Y );
		}

		Rectangle ViewportRectangle
		{
			get
			{
				var vre = ViewportRectangleExact;

				int l = ( int ) vre.Left - 1;
				int t = ( int ) vre.Top - 1;
				int r = ( int ) vre.Right + 1;
				int b = ( int ) vre.Bottom + 1;

				//if ( l < 0 ) l = 0; if ( r > _LenA ) r = _LenA;
				//if ( t < 0 ) t = 0; if ( b > _LenB ) b = _LenB;

				//Debug.WriteLine( "wr.r:" + WindowRectangle.Right + " vre.r:" + vre.Right + " vr.r:" + r + " screen:" + CalcScreen( r, 0 ).X );

				return new Rectangle( l, t, r - l, b - t );
			}
		}

		RectangleF ViewportRectangleExact // solve CalcScreen
		{
			get
			{
				var wr = WindowRectangle;

				var w = wr.Width / ( GRID_SQUARE_F * _Zoom );
				var h = wr.Height / ( GRID_SQUARE_F * _Zoom );

				//if ( w < 0 ) w = 0; if ( w > _LenA ) w = _LenA;
				//if ( h < 0 ) h = 0; if ( h > _LenB ) h = _LenB;

				//Debug.WriteLine( "wr.r:" + wr.Right + " vre.r:" + w + " screen:" + CalcScreen( w, 0 ).X );

				return new RectangleF( OffsetA, OffsetB, w, h );
			}
		}

		Point CalcIndex( Point p )
		{
			return CalcIndex( p.X, p.Y );
		}

		Point CalcIndex( PointF p )
		{
			return CalcIndex( p.X, p.Y );
		}

		Point CalcIndex( float x, float y )
		{
			var ie = CalcIndexExact( x, y );

			return new Point( ( int ) ( ie.X + 0.5 ), ( int ) ( ie.Y + 0.5 ) );
		}

		PointF CalcIndexExact( Point p )
		{
			return CalcIndexExact( p.X, p.Y );
		}

		PointF CalcIndexExact( PointF p )
		{
			return CalcIndexExact( p.X, p.Y );
		}

		PointF CalcIndexExact( float x, float y )
		{
			var a = ( ( x - Margin.Left ) / ( GRID_SQUARE_F * _Zoom ) ) + OffsetA;
			var b = ( ( y - Margin.Top ) / ( GRID_SQUARE_F * _Zoom ) ) + OffsetB;

			return new PointF( a, b );
		}

		PointF CalcMiddleIndexExact()
		{
			var cr = ClientRectangle;

			return CalcIndexExact(
				( cr.Width - Margin.Horizontal ) / 2f + Margin.Left,
				( cr.Height - Margin.Vertical ) / 2f + Margin.Top );
		}

		PointF CalcIndexExact( float x, float y, ref State state )
		{
			//var wr = WindowRectangle;

			var a = ( ( x - Margin.Left ) / ( GRID_SQUARE_F * state.Zoom ) ) + state.OffsetA;
			var b = ( ( y - Margin.Top ) / ( GRID_SQUARE_F * state.Zoom ) ) + state.OffsetB;

			return new PointF( a, b );
		}

		State CurrentState { get { return new State( _Zoom, _OffsetA, _OffsetB ); } }
		struct State
		{
			float _Zoom, _OffsetA, _OffsetB;

			public float Zoom { get { return _Zoom; } }
			public float OffsetA { get { return _OffsetA; } }
			public float OffsetB { get { return _OffsetB; } }

			public State( float zoom, float offsetA, float offsetB )
			{
				_Zoom = zoom;
				_OffsetA = offsetA;
				_OffsetB = offsetB;
			}
		}

		Rectangle _WindowRectangle = new Rectangle();
		bool _WindowRectangleStale = true;
		Rectangle WindowRectangle
		{
			get
			{
				if ( _WindowRectangleStale )
				{
					var c = ClientRectangle;

					int l = Margin.Left;
					int t = Margin.Top;
					int w = c.Width - Margin.Horizontal;
					int h = c.Height - Margin.Vertical;

					_WindowRectangle = new Rectangle( l, t, w, h );

					_WindowRectangleStale = false;
				}

				return _WindowRectangle;
			}
		}

		//-----------------------------------------------------------------------------------------------
		// OnPaint options

		SnakeOptions _SnakeOptions = SnakeOptions.Off;
		public SnakeOptions SnakeOptions
		{
			get { return _SnakeOptions; }
			set
			{
				_SnakeOptions = value;

				Invalidate();
			}
		}

		ContourOptions _ContourOptions = ContourOptions.Off;
		public ContourOptions ContourOptions
		{
			get { return _ContourOptions; }
			set
			{
				_ContourOptions = value;

				Invalidate();
			}
		}

		//-----------------------------------------------------------------------------------------------
		// OnPaint

		protected override void OnPaintBackground( PaintEventArgs pevent )
		{
			//base.OnPaintBackground( pevent );
		}

		protected override void OnPaint( PaintEventArgs pe )
		{
			//base.OnPaint( pe );

			var wr = WindowRectangle;
			var wrOuter = WindowRectangle; wrOuter.Width += 1; wrOuter.Height += 1;

			//var vr = ViewportRectangle; var vrs = CalcScreen( vr );
			//var vre = ViewportRectangleExact; var vres = CalcScreen( vre );

			var g = pe.Graphics;

			//g.DrawRectangle( Pens.Pink, wrOuter );

			g.SetClip( wrOuter );

			// constants
			var z = CalcScreen( 0, 0 );
			var defaultTextSize = g.MeasureString( "M", SystemFonts.DefaultFont );
			int meshStep = ( int ) Math.Pow( 10, ( int ) -Math.Log10( _Zoom ) ); if ( meshStep < 1 ) meshStep = 1;

			PaintMesh( g, wr, z, defaultTextSize, meshStep );
			PaintKLines( g, defaultTextSize, meshStep );
			PaintDiagonals( g, meshStep );
			PaintIdeal( g, z );
			PaintBounds( g, wr, z );

			PaintSnakes( g );
			PaintContours( g, defaultTextSize );
			PaintSolution( g );
			PaintSolutionMiddle( g );

			if ( _DrawStats )
			{
				g.DrawString( "Zoom: " + _Zoom, SystemFonts.DefaultFont, Brushes.White, new PointF( 100, 100 ) );
				g.DrawString( "Grid: " + meshStep, SystemFonts.DefaultFont, Brushes.White, new PointF( 100, 150 ) );
				g.DrawString( "Offset: ( " + OffsetA.ToString( "N1" ) + ", " + OffsetB.ToString( "N1" ) + " )", SystemFonts.DefaultFont, Brushes.White, new PointF( 100, 200 ) );
				PaintMouse( g, MousePosition );
			}
		}

		void PaintMesh( Graphics g, Rectangle wr, Point z, SizeF defaultTextSize, int meshStep )
		{
			int dx = meshStep, dy = meshStep;

			var aOffset = new SizeF( defaultTextSize.Width / 2, defaultTextSize.Height * 1.5f );
			var bOffset = new SizeF( defaultTextSize.Width * 1.5f, defaultTextSize.Height / 2 );

			using ( var pen = new Pen( cMesh ) )
			{
				for ( int x = 0 ; x <= _LenA ; x += dx )
				{
					var p = CalcScreen( x, _LenB );
					if ( p.X < wr.Left ) continue;
					if ( p.X > wr.Right ) break;
					g.DrawLine( pen, p.X, Math.Max( z.Y, wr.Top ), p.X, Math.Min( p.Y, wr.Bottom ) );
					if ( _A != null && x > 0 ) g.DrawString( _A[ x - 1 ].ToString(), SystemFonts.DefaultFont, Brushes.White, p.X - aOffset.Width, z.Y - aOffset.Height );
				}

				for ( int y = 0 ; y <= _LenB ; y += dy )
				{
					var p = CalcScreen( _LenA, y );
					if ( p.Y < wr.Top ) continue;
					if ( p.Y > wr.Bottom ) break;
					g.DrawLine( pen, Math.Max( z.X, wr.Left ), p.Y, Math.Min( p.X, wr.Right ), p.Y );
					if ( _B != null && y > 0 ) g.DrawString( _B[ y - 1 ].ToString(), SystemFonts.DefaultFont, Brushes.White, z.X - bOffset.Width, p.Y - bOffset.Height );
				}
			}
		}

		void PaintKLines( Graphics g, SizeF defaultTextSize, int meshStep )
		{
			if ( meshStep != 1 ) return;
			if ( !_DrawEvenK && !_DrawOddK ) return;

			int D = _LenA + _LenB;
			bool clipTopLeft = !( ResultType == ResultType.Reverse );
			bool clipBottomRight = !( ResultType == ResultType.Forward );

			if ( ResultType != ResultType.Linear || 1 == 1 )
				PaintKLinesCore( g, D, Delta, clipTopLeft, clipBottomRight, false, false );
			else
			{
				PaintKLinesCore( g, D, 0, true, false, true, true );
				PaintKLinesCore( g, D, _Delta, false, true, true, false );
			}
		}

		void PaintKLinesCore( Graphics g, int D, int delta, bool clipTopLeft, bool clipBottomRight, bool clipCentre, bool forward )
		{
			using ( Pen pEven = new Pen( cKEven ) )
			using ( Pen pOdd = new Pen( cKOdd ) )
			using ( Brush bEven = new SolidBrush( cKEven ) )
			using ( Brush bOdd = new SolidBrush( cKOdd ) )
				for ( int k = -D + delta ; k <= D + delta ; k++ )
				{
					float x = clipTopLeft ? ( k <= 0 ? 0 : k ) : ( k / +2f );
					float y = clipTopLeft ? ( k > 0 ? 0 : -k ) : ( k / -2f );
					var xy = CalcScreen( x, y );

					float u = clipBottomRight ? ( k >= _LenA - _LenB ? _LenA : _LenB + k ) : ( D + k ) / 2f;
					float v = clipBottomRight ? ( k <= _LenA - _LenB ? _LenB : _LenA - k ) : ( D - k ) / 2f;
					var uv = CalcScreen( u, v );

					if ( u < x ) continue;

					int kd = k - delta;

					if ( kd % 2 == 0 )
					{
						if ( _DrawEvenK )
						{
							g.DrawLine( pEven, xy, uv );
							g.DrawString( kd.ToString(), SystemFonts.DefaultFont, bEven, uv );
						}
					}
					else
					{
						if ( _DrawOddK )
						{
							g.DrawLine( pOdd, xy, uv );
							g.DrawString( kd.ToString(), SystemFonts.DefaultFont, bOdd, uv );
						}
					}
				}
		}

		void PaintDiagonals( Graphics g, int meshStep )
		{
			if ( !_DrawDiagonals || meshStep != 1 ) return;

			using ( var pen = new Pen( cDiagonal ) )
				for ( int x = 0 ; x < _LenA ; x++ )
					for ( int y = 0 ; y < _LenB ; y++ )
						if ( _A[ x ] == _B[ y ] )
						{
							var xy = CalcScreen( x, y );
							var uv = CalcScreen( x + 1, y + 1 );
							g.DrawLine( pen, xy, uv );
						}
		}

		void PaintIdeal( Graphics g, Point z )
		{
			if ( !_DrawIdeal ) return;

			using ( var pen = new Pen( cIdeal ) )
				g.DrawLine( pen, z, CalcScreen( _LenA, _LenB ) );
		}

		void PaintBounds( Graphics g, Rectangle wr, Point z )
		{
			using ( var pen = new Pen( cBounds ) )
			{
				var min = CalcScreen( 0, 0 );
				var max = CalcScreen( _LenA, _LenB );
				g.DrawLine( pen, min.X, Math.Max( z.Y, wr.Top ), min.X, Math.Min( max.Y, wr.Bottom ) ); // left
				g.DrawLine( pen, Math.Max( z.X, wr.Left ), min.Y, Math.Min( max.X, wr.Right ), min.Y ); // top
				g.DrawLine( pen, max.X, Math.Max( z.Y, wr.Top ), max.X, Math.Min( max.Y, wr.Bottom ) ); // right
				g.DrawLine( pen, Math.Max( z.X, wr.Left ), max.Y, Math.Min( max.X, wr.Right ), max.Y ); // bottom
			}
		}

		void PaintSnakes( Graphics g )
		{
			if ( _SnakeOptions == null || !_SnakeOptions.Show ) return;

			PaintSnakes( g, true, ForwardVs );
			PaintSnakes( g, false, ReverseVs );
		}

		void PaintSnakes( Graphics g, bool forward, IList<V> vs )
		{
			if ( vs == null ) return;

			int delta = ( forward ? 0 : _Delta );

			Snake snake = new Snake( forward, delta );

			var c = forward ? cSnakeForward : cSnakeReverse;

			using ( Pen pen = new Pen( c ) )
			using ( Brush br = new SolidBrush( c ) )
				for ( int d = _SnakeOptions.Start ; d < vs.Count && d <= _SnakeOptions.End ; d += _SnakeOptions.Step )
				{
					var V = vs[ d ];

					for ( int k = -d ; k <= d ; k += 2 )
					{
						var s = snake.Calculate( V, k + delta, d, _A, 0, _LenA, _B, 0, _LenB );

						PaintSnake( g, pen, br, true, s );
					}
				}
		}

		void PaintContours( Graphics g, SizeF ts )
		{
			if ( _ContourOptions == null || !_ContourOptions.Show ) return;

			PaintContours( g, ts, true, ForwardVs );
			PaintContours( g, ts, false, ReverseVs );
		}

		void PaintContours( Graphics g, SizeF ts, bool forward, IList<V> vs )
		{
			if ( vs == null ) return;

			int delta = ( forward ? 0 : _Delta );

			int dx = ( int ) ts.Width;
			int dy = ( int ) ts.Height;

			var linkOffset = new Size( dx / 2, -dy / 2 );
			var textOffsetA = new Size( -dx - ( dx / 2 ), dy / 2 );
			var textOffsetB = new Size( dx / 2 + 3, -dy );

			Snake snake = new Snake( forward, delta );

			var c = ( forward ? cContourForward : cContourReverse );

			using ( Pen pen = new Pen( c ) )
			using ( Brush br = new SolidBrush( c ) )
				for ( int d = _ContourOptions.Start ; d < vs.Count && d <= _ContourOptions.End ; d += _ContourOptions.Step )
				{
					var V = vs[ d ];

					Point prev = new Point();
					for ( int k = -d ; k <= d ; k += 2 )
					{
						Point end = CalcScreen( snake.Calculate( V, k + delta, d, _A, 0, _LenA, _B, 0, _LenB ).EndPoint );

						if ( k == -d )
						{
							g.DrawLine( pen, end - linkOffset, end );
							g.DrawString( d.ToString(), SystemFonts.DefaultFont, br, end + textOffsetA );
						}

						if ( k > -d )
							g.DrawLine( pen, prev, end );

						if ( k == d )
						{
							g.DrawLine( pen, end, end + linkOffset );
							g.DrawString( d.ToString(), SystemFonts.DefaultFont, br, end + textOffsetB );
						}

						prev = end;
					}
				}
		}

		void PaintSolution( Graphics g )
		{
			if ( !_DrawSolution ) return;

			PaintSolution( g, false );
		}

		void PaintSolutionMiddle( Graphics g )
		{
			if ( _SnakeOptions == null || !_SnakeOptions.Show ) return;

			PaintSolution( g, true );
		}

		void PaintSolution( Graphics g, bool middle )
		{
			var solution = Solution;
			if ( solution == null ) return;

			var c = middle ? cSolutionMiddle : cSolution;

			using ( var p = new Pen( c ) )
			using ( var b = new SolidBrush( c ) )
				foreach ( var s in solution )
				{
					if ( middle )
					{
						if ( !s.IsMiddle ) continue;
						if ( s.D < _SnakeOptions.Start || s.D > _SnakeOptions.End ) continue;
					}

					PaintSnake( g, p, b, true, s );
				}
		}

		void PaintMouse( Graphics g, Point mouse )
		{
			if ( _A == null || _B == null ) return;
			if ( !_DrawStats ) return;

			var m = CalcIndex( mouse );

			using ( var bmp = new Bitmap( 250, 20 ) )
			{
				using ( var gbmp = Graphics.FromImage( bmp ) )
				{
					gbmp.Clear( Color.Black );
					gbmp.DrawString( String.Format( "Mouse: ( {0:N0} {1} ,  {2:N0} {3} )",
						m.X, ( m.X <= 0 || m.X > _A.Length ? '□' : _A[ m.X - 1 ] == '\n' ? '¬' : _A[ m.X - 1 ] ),
						m.Y, ( m.Y <= 0 || m.Y > _B.Length ? '□' : _B[ m.Y - 1 ] == '\n' ? '¬' : _B[ m.Y - 1 ] ) ),
						SystemFonts.DefaultFont, Brushes.White, 0, 0 );
				}

				g.DrawImage( bmp, 0, 0 );
			}
		}

		void PaintSnake( Graphics g, Pen p, Brush b, bool fillDot, Snake s )
		{
			Point start = CalcScreen( s.StartPoint );

			if ( s.ADeleted == 0 && s.BInserted == 0 )
			{
				if ( s.IsForward && s.XStart == 0 && s.YStart == 0 ) start = CalcScreen( s.XStart, s.YStart - 1 );
				if ( !s.IsForward && s.XStart == _LenA && s.YStart == _LenB ) start = CalcScreen( s.XStart, s.YStart + 1 );
			}

			var mid = CalcScreen( s.MidPoint );

			g.DrawLine( p, start, mid );

			if ( fillDot )
				g.FillEllipse( b, start.X - 2, start.Y - 2, 5, 5 );
			else
				g.DrawEllipse( p, start.X - 2, start.Y - 2, 5, 5 );

			if ( s.DiagonalLength == 0 )
			{
				PaintArrow( g, p, b, s.ADeleted > 0 ? 0 : 2, s.IsForward, mid );
			}
			else
			{
				var end = CalcScreen( s.EndPoint );

				g.DrawLine( p, mid, end );

				PaintArrow( g, p, b, 1, s.IsForward, end );
			}
		}

		// dir: 0 = horizontal, 1 = diagonal, 2 = vertical
		void PaintArrow( Graphics g, Pen pen, Brush br, int dir, bool forward, Point p )
		{
			const int dx = 10, dy = 4; // horizontal

			switch ( dir )
			{
				case 0: // horizontal
					{
						if ( forward )
							g.FillPolygon( br, new Point[] { new Point( p.X - dx, p.Y - dy ), p, new Point( p.X - dx, p.Y + dy ) } );
						else
							g.FillPolygon( br, new Point[] { new Point( p.X + dx, p.Y - dy ), p, new Point( p.X + dx, p.Y + dy ) } );
					}
					break;

				case 1: // diagonal
					{
						const int a = 4, b = 9;

						if ( forward )
							g.FillPolygon( br, new Point[] { new Point( p.X - b, p.Y - a ), p, new Point( p.X - a, p.Y - b ) } );
						else
							g.FillPolygon( br, new Point[] { new Point( p.X + b, p.Y + a ), p, new Point( p.X + a, p.Y + b ) } );
					}
					break;

				case 2: // vertical
					{
						if ( forward )
							g.FillPolygon( br, new Point[] { new Point( p.X - dy, p.Y - dx ), p, new Point( p.X + dy, p.Y - dx ) } );
						else
							g.FillPolygon( br, new Point[] { new Point( p.X - dy, p.Y + dx ), p, new Point( p.X + dy, p.Y + dx ) } );
					}
					break;
			}
		}

		//-----------------------------------------------------------------------------------------------

	}

	//-----------------------------------------------------------------------------------------------

}