context: using DataStructures;
  using System.Collections.Generic;
  using System.IO;
  using System;
  using System.Linq;
  
  namespace Lexer {
  	
  	public enum PartitionClass {
  		Regular,
  		HorLine,
  		SquareRoot,
  	}
  
  	public class LexerMain {
  		public Dictionary<string,Segment> strokeSegmentDictionary; // **RZ: New stroke -> segment lookup.
  		
  		private ClassifyManager classifier; // = new ClassifyManager();
  
  		private const int Y_WRITING_LINE_THRESHOLD = 10; // default threshold for y-writing-line algorithm
  		
  		//public static Dictionary< string, SymbolClass > layoutClassMap;
  		
  		public Dictionary< string, QDC > adjProbClassifiers;
  		
  		// ****RZ: adding new constructor, to make use of segmentation pre-process.
  		// Note: chaining with pre-existing constructor.
  		public LexerMain(string adjDataFile, string classifyUrl, double probThreshold, string segmentFile,
  				List<Stroke> strokeList) : this(adjDataFile, classifyUrl, probThreshold)
  		{
  			strokeSegmentDictionary = new Dictionary<string, Segment>();
  
  			// Read in segmentation data, print to standard output.
  			if (!File.Exists(segmentFile)) throw new Exception("Segment data file does not exist: " + segmentFile);
  			StreamReader fin = new StreamReader( segmentFile );
  			//List <Segment> segments = new List<Segment>();
  			string line = null;
  			while ( (line = fin.ReadLine()) != null ) {
  				try {
  
  					Segment s = new Segment();
  					string[] line_data = line.Split( new char[] { ',' });
  					foreach (string sid in line_data) {
  
  						// Convert string to integer index; add corresponding stroke to segment.
  						int strokeIndex = Convert.ToInt32(sid);
  						s.strokes.Add( strokeList[strokeIndex] );
  
  						// Add (stroke (sid)/segment) pair to dictionary (hash table).
  						strokeSegmentDictionary.Add( sid, s);
  					}
  				} catch ( Exception ) { 
  					Console.Error.WriteLine("ERROR: reading segmentation data.");
  				}
  			}
  
  			// Sanity check.
  #if DEBUG
  			Console.WriteLine("Segment dictionary:");
  			foreach (KeyValuePair<string, Segment> pair in strokeSegmentDictionary) {
  				Console.WriteLine("{0}: {1}",pair.Key, pair.Value);
  				foreach (Stroke s in pair.Value.strokes) 
  					Console.WriteLine("  {0}", s.stroke_id);
  			}
  			Console.WriteLine("done.");
  #endif
  		}
  
  		public LexerMain( string adjDataFile, string classifyUrl, double probThreshold )
  		{
              classifier = new ClassifyManager(classifyUrl, probThreshold);
  
  			//layoutClassMap = inMap;
  			
  			adjProbClassifiers = new Dictionary< string, QDC >();
  			
  			// initialize QDCs
  			if ( !File.Exists( adjDataFile ) ) 
  				throw new Exception( "Adjacency data file does not exist: " + adjDataFile );
  			
  			StreamReader fin = new StreamReader( adjDataFile );
  			fin.ReadLine();
  			string line = null;
  			
  			List< Matrix > c_adj = new List< Matrix >();
  			List< Matrix > c_oth = new List< Matrix >();
  			
  			List<Matrix> c_sup = new List<Matrix>();
  			List<Matrix> c_sub = new List<Matrix>();
  			
  			List< Matrix > a_adj = new List< Matrix >();
  			List< Matrix > a_oth = new List< Matrix >();
  			
  			List<Matrix> a_sup = new List<Matrix>();
  			List<Matrix> a_sub = new List<Matrix>();			
  			
  			List< Matrix > c_adj_dash = new List<Matrix>();
  			List< Matrix > c_adj_oth = new List<Matrix>();
  			List< Matrix > a_adj_dash = new List<Matrix>();
  			List< Matrix > a_adj_oth = new List<Matrix>();
  			
  			while ( ( line = fin.ReadLine() ) != null ) 
  			{
  				try 
  				{
  					string[] line_data = line.Split( new char[] { ',' } );
  					string rel = line_data[ 1 ].Trim();
  					string ccl = line_data[ 0 ].Trim();
  					string pcl = line_data[ 4 ].Trim();
  					double top = double.Parse( line_data[ 5 ].Trim() );
  					double bot = double.Parse( line_data[ 6 ].Trim() );
  					double[,] vec = new double[,] { { top }, { bot } };
  					if ( pcl.Equals( "CENTERED" ) ) 
  					{
  						switch(rel)
  						{
  						case "Right":
  							
  							if ( ccl.Equals( "-" ) ) {
  								c_adj_dash.Add( new Matrix( vec ) );
  							} else {
  								c_adj_oth.Add( new Matrix( vec ) );	
  							}
  							
  							c_adj.Add( new Matrix( vec ) );
  							break;
  						case "SubScript":
  							c_sub.Add( new Matrix(vec));
  							goto case "Other";
  						case "SuperScript":
  							c_sup.Add( new Matrix(vec));
  							goto case "Other";
  						case "Other":
  							c_oth.Add( new Matrix(vec));
  							break;
  						}
  
  					} 
  					else if ( pcl.Equals( "ASCENDER" ) )
  					{
  						switch(rel)
  						{
  						case "Right":
  							
  							if ( ccl.Equals( "-" ) ) {
  								a_adj_dash.Add( new Matrix( vec ) );
  							} else {
  								a_adj_oth.Add( new Matrix( vec ) );	
  							}
  							
  							a_adj.Add( new Matrix( vec ) );
  							break;
  						case "SubScript":
  							a_sub.Add( new Matrix(vec));
  							goto case "Other";
  						case "SuperScript":
  							a_sup.Add( new Matrix(vec));
  							goto case "Other";
  						case "Other":
  							a_oth.Add( new Matrix(vec));
  							break;
  						}
  					}
  				} catch ( Exception ) { continue; }
  			}
  			fin.Close();
  
  						
  			adjProbClassifiers.Add( "Ascender", new QDC( new List< Matrix >[] { a_adj_dash, a_adj_oth, a_sup, a_sub }, new string[] { "adjacent-dash", "adj-non-dash", "super", "sub" } ) );
   			adjProbClassifiers.Add( "Centered", new QDC( new List< Matrix >[] { c_adj_dash, c_adj_oth, c_sup, c_sub }, new string[] { "adjacent-dash", "adj-non-dash", "super", "sub" } ) );
  			
  		}
  		
  		// NOTE: this assumes that all segments must contain the first stroke in the passed list.
  		public List<Segment> CreateSegmentsForStrokes( LBT lbt, List<Stroke> strokes_to_segment )
  		{
  			// Return empty list for an empty set of strokes.
  			if (strokes_to_segment.Count < 1)
  				return new List<Segment>();
  						
  			// Construct a list of candidate segments.
  			List< Segment > candidateSegments = new List<Segment>();
  
              // sort in draw-order
              strokes_to_segment.Sort( ( s1, s2 ) => int.Parse( s1.stroke_id ) - 
  					int.Parse( s2.stroke_id ) );
  
              Segment curSegment = new Segment();
              foreach ( Stroke s in strokes_to_segment ) {
  
                  // create new segment and add all previous strokes, followed by next one
                  Segment newSegment = new Segment();
                  foreach ( Stroke _s in curSegment.strokes ) newSegment.strokes.Add( _s );
                  newSegment.strokes.Add( s );
  
                  // make sure we don't violate constraint that two overlapping strokes must go together
                  bool overlapViolation = false;
                  foreach ( Stroke str in newSegment.strokes ) {
  
                      // if this stroke touches another and the other is not in the segment, don't consider
                      foreach ( Stroke _s in lbt.strokes ) {
                          if ( Stroke.Overlap( str, _s ) && !newSegment.strokes.Contains( _s ) ) {
                              overlapViolation = true;
                              break;
                          }
                      }
                      if ( overlapViolation ) break;
                  }
  
                  if ( !overlapViolation ) candidateSegments.Add( newSegment );
                  curSegment = newSegment; // keep track of current strokes in list
              }
  
  			
  			return candidateSegments;
  		}
  		
  		// Find leftmost symbol for a sub-expression.
  		// **No special handling for different symbol types; let parser try some n-best alternatives.
  		public List< LexerResult > Start( LBT tree, int k ) 
  		{
  			// Note: will require modification to accomodate indexed symbols (summations, etc.)
  			List< LexerResult > all_results = new List< LexerResult >();
  		
  			foreach ( LBT.LBTNode node in tree.root.children ) 
  			{
  				//Console.WriteLine("START Considering: {0}", node.stroke);
  				Stroke snc = node.stroke;
  				
  								
  				// **REMOVING**
  				//List< Stroke > strokes_to_segment = new List< Stroke >();
  				//strokes_to_segment.Add( snc );
  				//foreach ( Stroke s in tree.KNearestNeighbors( snc, k, LBT.DefaultKNNFilter ) ) 
  				//	strokes_to_segment.Add( s );
  				
  				// Construct a list of candidate segments, and classify each.
  				//List< Segment > candidateSegments = CreateSegmentsForStrokes( tree, strokes_to_segment );
  				List<Segment> candidateSegments = new List<Segment>();
  				candidateSegments.Add( strokeSegmentDictionary[snc.stroke_id] );
  				foreach (Segment seg in candidateSegments) 
  				{
  					LexerResult result = new LexerResult();
  					classifier.classify( seg );
  					//Console.WriteLine(seg); // DEBUG
  					seg.PopulateBB();
  					if ( seg.classification == null ) {
  						Console.Error.WriteLine("LexerResult.Start:: NO CLASSIFICATION RESULT");
  						continue;
  					}
  					
  					result.segment = seg;
  					result.lbt = UpdateLBT( seg, tree );
  					all_results.Add( result );
  				}
  			}
  			
  			return all_results;
  		}
  		
  		public List< LexerResult > Next( LBT lbt, Segment S_l, string layout_class, int k ) 
  		{
  			// **Converts descenders to centered symbols (writing-line "hack")
  			if ( S_l != null && ( S_l.classification[ 0 ].symbol == "y" 
  						|| S_l.classification[ 0 ].symbol == "\\tan"  // RZ - BUG?
  						|| S_l.classification[ 0 ].symbol == "\\log" ) ) {
  				layout_class = "Centered";
  				int[] new_lines = GetCenteredLines( S_l ); // manipulate bb-bottom
                  		S_l.bb.Top = new_lines[ 0 ];
                		S_l.bb.Bottom = new_lines[ 1 ];
  			}
  			
  			List< LexerResult > all_results = new List< LexerResult >();
  			
  			
  #if DEBUG
  			//Console.WriteLine("HOR ADJ, PREVIOUS SYMBOL: {0} ({1})",C_l,lc);
  #endif
  			switch (layout_class.ToUpper())
  			{	
  				case "ASCENDER":
  				case "CENTERED":
  				case "ROOT":  // WHICH
  				case "*SQRT": // ONE ??
  					// **REMOVING
  					// List< Stroke > strokes_to_segment = new List< Stroke >();
  					string n = LeftmostAdjacent( lbt, S_l, layout_class ); // DEBUG: use proper class.
  #if DEBUG
  					//Console.WriteLine(n == null ? "NOTHING FOUND" : string.Format("  Found stroke: {0}",n));
  #endif
  					if (n != null) {						
  						// **REMOVING
  						//strokes_to_segment.Add( lbt.strokes.Where( s => s.stroke_id.Equals( n ) ).First() );
  						//List< Stroke > N = lbt.KNearestNeighbors( lbt.strokes.Where( s => s.stroke_id.Equals( n ) ).First(), k, LBT.DefaultKNNFilter );
  						//foreach ( Stroke s in N ) strokes_to_segment.Add( s );
  					
  						//foreach ( Segment seg in CreateSegmentsForStrokes( lbt, strokes_to_segment ) ) {
  						List<Segment> candidateSegments = new List<Segment>();
  						candidateSegments.Add( strokeSegmentDictionary[n] );
  						foreach ( Segment seg in candidateSegments ) {
  							LexerResult result = new LexerResult();
  							classifier.classify( seg );
  							if ( seg.classification == null ) continue;
  							result.segment = seg;
  							result.lbt = UpdateLBT( seg, lbt );
  							result.adj = HorAdj(S_l, seg, layout_class);
  							all_results.Add( result );
  						}
  						return all_results;
  					
  					} else {
  						return new List<LexerResult>();
  					}
  				
  				case "NOSUPERSUB":
  				case "*FRAC": // ?????
  					// Start(), but remove symbols to the left
  					LBT lbt1 = new LBT( lbt.strokes, LBT.DefaultAdjacentCriterion );
  					if ( lbt.strokes != null ) {
  						foreach ( Stroke s in lbt.strokes ) {
  							if ( s.aabb.Left < S_l.bb.Right ) lbt1.PruneNode( s, LBT.DefaultAdjacentCriterion );
  						}
  					}
  #if DEBUG
  					Console.WriteLine( "[next] LAYOUT CLASS: {0}; calling Start()", layout_class.ToUpper() );
  #endif
  					return Start( lbt1, k );
  				
  				default:
  					return Start( lbt, k );
  			}
  		}
  		
  		/// <summary>
  		/// Finds the left-most adjacent symbol in the LBT, given the current symbol and its class.
  		/// </summary>
  		/// <param name="S_l">
  		/// The current symbol.
  		/// </param>
  		/// <param name="lbt">
  		/// The LBT for the remainder of the strokes.
  		/// </param>
  		/// <param name="lc">
  		/// The current segment's layout class.
  		/// </param>
  		/// <returns>
  		/// A <see cref="System.String"/>
  		/// </returns>
  		public string LeftmostAdjacent( LBT lbt, Segment S_l, string layout_class ) {
  			foreach ( Stroke s in lbt.strokes.OrderBy( s => s.aabb.Left ) ) {
  				Segment seg = new Segment(new List<Stroke>() { s }); // { strokes = new List< Stroke >() { s } };
  				//Console.WriteLine("Top: {0}",seg.bb.Top);
  
  				if (HorAdj(S_l, seg, layout_class))
  				    return s.stroke_id;
  			}
  			return null; // DEBUG
  		}
  		
  		/// <summary>
  		/// Probability of horizontal adjacency.
  		/// </summary>
  		/// <param name="S_l">
  		/// Current segment.
  		/// </param>
  		/// <param name="s">
  		/// Next segment.
  		/// </param>
  		/// <param name="lc">
  		/// Layout class of current segment.
  		/// </param>
  		public bool HorAdj( Segment S_l, Segment s, string layout_class ) {
  			
  			// ???? BUG ???  RZ: I do not understand why the BB goes out of scope if not created here.
  			s.PopulateBB();
  			
  			float norm_top = ( s.bb.Top - S_l.bb.Top ) / S_l.bb.Height;
  			float norm_bottom = ( s.bb.Bottom - S_l.bb.Top ) / S_l.bb.Height;
  
  			return isAdjacentStroke(norm_top, norm_bottom, layout_class);
  		}
  		
  		public bool isAdjacentStroke( float norm_top, float norm_bottom, string layout_class ) 
  		{
  			QDC classifier;
  			if (adjProbClassifiers.TryGetValue(layout_class, out classifier))
  			{
  				int index = classifier.classify(new Matrix(new double[,] { { norm_top }, { norm_bottom } }));
  				return index == 0 || index == 1;
  			}
  			return false;
  			
  		}
  		
  		private bool VerticalOverlap( float[] r_i, float[] r_k ) {
  			return !( r_i[ 0 ] > r_k[ 1 ] || r_k[ 0 ] > r_i[ 1 ] );
  		}
  		
          public int[] GetCenteredLines( Segment s ) {
  
              // projection frequency
              Dictionary<int, int> yc = new Dictionary<int, int>();
              int ymin = int.MaxValue;
  
              foreach ( Stroke _s in s.strokes ) {
                  for ( int i = 1; i < _s.points.Count; i++ ) {
                      int yprev = ( int ) _s.points[ i - 1 ].y;
                      int ycur = ( int ) _s.points[ i ].y;
  
                      if ( yprev < ymin ) ymin = yprev;
                      if ( ycur < ymin ) ymin = ycur; // this one might not be necessary
  
                      for ( int j = yprev; j <= ycur; j++ ) {
                          if ( !yc.ContainsKey( j ) ) {
                              yc.Add( j, 1 );
                          } else {
                              yc[ j ] = yc[ j ] + 1;
                          }
                      }
                  }
              }
  
              // difference
              Dictionary< int, int > diff = new Dictionary< int, int >();
  
gt:             float prevVal = -1;