Yet Another Custom Formatter

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

using Framework.Exceptions;
using Framework.Formatting;

namespace Framework
{
	public sealed class ObjectFormatter
	{
		#region Static
		/// <summary>
		/// Holds a list of parsed elements for a given string template.
		/// </summary>
		static readonly Dictionary<string, IObjectFormatterElement[]> TemplateCache = new Dictionary<string, IObjectFormatterElement[]>();

		/// <summary>
		/// Uses the TemplateParser to break the template string
		/// into a number of elements.
		/// 
		/// Since strings are immutable, so will the parsed elements
		/// so we store them in a Dictionary (unless told not to)
		/// </summary>
		/// <param name="template">The template string to parse.</param>
		/// <param name="noCache">True to not cache the elements.</param>
		/// <returns></returns>
		static IObjectFormatterElement[] GetTemplateElements(string template, bool noCache = false)
		{
			Guard.NotNull(template, "template");

			IObjectFormatterElement[] result;

			if (!TemplateCache.TryGetValue(template, out result))
			{
				result = TemplateParser.Parse(template);

				if (!noCache)
				{
					TemplateCache[template] = result;
				}
			}

			return result;
		}
		#endregion Static

		/// <summary>
		/// A list of elements parsed from the original string template.
		/// </summary>
		readonly IObjectFormatterElement[] elements;

		/// <summary>
		/// An IFormatProvider used when formatting strings. May be null.
		/// </summary>
		readonly IFormatProvider formatProvider;

		/// <summary>
		/// Global boolean flag which is used by the GlobalDependency option.
		/// </summary>
		readonly bool globalDependency;

		/// <summary>
		/// A Dictionary naming objects which a template string can use as
		/// an alternate target by using '#&lt;name&gt;' as a prefix to the
		/// member path.
		/// The target will be null if it cannot be found.
		/// </summary>
		readonly Dictionary<string, object> namedTargets;

		/// <summary>
		/// A list of objects which a template string can use as an
		/// alternate target by using '#&lt;index&gt;' as a prefix to the 
		/// member path. '#0' refers to the original target and the
		/// so '#1' refers to the first additional target.
		/// The target will be null if the index is outside the range.
		/// </summary>
		readonly object[] additionalTargets;

		/// <summary>
		/// The main formatter for this ObjectFormatter.
		/// </summary>
		readonly Formatter formatter;

		/// <summary>
		/// The main list formatter for this ObjectFormatter.
		/// </summary>
		ListFormatter listFormatter;

		/// <summary>
		/// Contructor to create ObjectFormatter.
		/// </summary>
		/// <param name="template">The string containing the formatting template.</param>
		/// <param name="formatProvider">The IFormatProvider to use with the Format option. Null by default.</param>
		/// <param name="globalDependency">The global boolean used by the Global Dependency. False by default.</param>
		/// <param name="namedTargets">Dictionary of named </param>
		/// <param name="additionalTargets"></param>
		public ObjectFormatter(string template, IFormatProvider formatProvider = null, bool globalDependency = false, Dictionary<string, object> namedTargets = null, params object[] additionalTargets)
		{
			this.formatProvider = formatProvider ?? Thread.CurrentThread.CurrentCulture;
			this.globalDependency = globalDependency;
			this.namedTargets = namedTargets;
			this.additionalTargets = additionalTargets;

			// Get the elements for the template
			elements = GetTemplateElements(template);

			// Pre-create the main formatter
			formatter = new Formatter(this);
		}

		/// <summary>
		/// Formats a target object.
		/// </summary>
		/// <param name="target">The object to format.</param>
		/// <param name="maximumLength">The maximum length of the formatted string.
		/// Default is 0 and will not truncate the result.</param>
		/// <returns>The formatted string.</returns>
		public string Format(object target, int maximumLength = 0)
		{
			return formatter.Format(target, maximumLength);
		}

		/// <summary>
		/// Formats a list of items.
		/// The formatting will be applied to each object in the source list.
		/// A string array of the same size as the source list is returned.
		/// There will be no nulls in the return value - any nulls or expression
		/// resulting in null will be replaced with String.Empty.
		/// </summary>
		/// <param name="targets">The list of objects to format.</param>
		/// <param name="maximumLength">The maximum length of the resulting string. 0=any length.</param>
		/// <returns>A string array of formatted values.</returns>
		public string[] FormatList(IList targets, int maximumLength = 0)
		{
			// Create a list formatter if we don't already have one.
			if (listFormatter == null)
			{
				listFormatter = new ListFormatter(this);
			}

			return listFormatter.FormatList(targets, maximumLength);
		}

		#region FormatterBase
		abstract class FormatterBase
		{
			public ObjectFormatter Owner { get; private set; }

			protected FormatterBase(ObjectFormatter owner)
			{
				Owner = owner;
			}

			/// <summary>
			/// Attempts to convert a value to an Int32.
			/// Returns the specified default value if the conversion fails.
			/// </summary>
			/// <param name="value">The value to convert.</param>
			/// <param name="defaultValue">The Int32 to use if a conversion fails.</param>
			/// <returns>An Int32 converted from the value or the specified default value.</returns>
			protected static int GetNumber(string value, int defaultValue)
			{
				try
				{
					if (string.IsNullOrEmpty(value)) return defaultValue;

					return Convert.ToInt32(value);
				}
				catch
				{
					return defaultValue;
				}
			}
		}
		#endregion FormatterBase

		#region Formatter
		class Formatter: FormatterBase
		{
			/// <summary>
			/// A list of elements parsed from the original string template.
			/// </summary>
			protected readonly IObjectFormatterElement[] elements;

			/// <summary>
			/// The target object to which the template is applied.
			/// </summary>
			object target;

			/// <summary>
			/// A separator string obtained from the previous element which is only used as and when a 
			/// future element results in a non-empty string.
			/// </summary>
			string pendingSeparator;

			/// <summary>
			/// Flag to determine whether the expressions processed so
			/// far have return any results.
			/// Used by the Blank Dependency option.
			/// </summary>
			bool isBlank;

			/// <summary>
			/// Provides an MRU cache of the most recently used member paths
			/// to speed up finding a GenericGetter
			/// </summary>
			readonly LocalMemberPathCache localMemberPathCache = new LocalMemberPathCache(6);

			StringBuilder buffer;

			Dictionary<MemberExpression, MemberListFormatter> memberListFormatterCache;

			public Formatter(ObjectFormatter owner): base(owner)
			{
				elements = owner.elements;
			}

			protected Formatter(Expression element, ObjectFormatter owner): base(owner)
			{
				elements = new[] { element };
			}

			/// <summary>
			/// Evaluates the member expression and produces a formatted string.
			/// 
			/// Step 1: Any specified dependencies are evaluated.
			/// 
			///   The dependency options are DependencyOption ('d') / GlobalDependencyOption ('D') / BlankDependencyOption ('b').
			///   If any fail, then String.Empty is immediately returned.
			/// 
			/// Step 2: The value to format is obtained.
			/// 
			///   This is most likely a property on the target object but could be the target itself;
			///   an alternate source object or any combination.
			///   DBNull is converted to a null;
			///   DataRow/DataRowView will use the member path to obtain a column value.
			/// 
			/// Step 3: The value is converted into a string.
			/// 
			///   A null value will take the value specified by the NullOption ('n'); or
			/// 
			///   An IEnumerable value (except a string value!) will be converted to a 
			///   separated string using these options:
			///     ListSeparatorOption ('l') to separate list items (default is ",")
			///     ListLastSeparatorOption ('L') to specify an alternate separator for the 
			///     last list item (default is null which will use the ListSeparatorOption)
			///     FormatOption('f') to format each list item (default is null)
			///     MaximumWidthOption('i') to specify the maximum length of each item's string (default is unlimited)
			///     SortSourceItemsOption('S') to sort the values prior to formatting (default is no sorting)
			///     SortTargetStringsOption('s') to sort the formatted strings (default is no sorting); or
			/// 
			///   Conditional formatting will be applied if specified; or
			/// 
			///   A zero value will take ZeroOption ('z') value if specified; or
			/// 
			///   Formatting will be applied if the Format ('f') or FullFormat ('F') options are specified; or
			/// 
			///   ToString() will be called.
			/// 
			///   If the formatted string is empty at this point, it is immediately returned.
			/// 
			/// Step 4: Trimming
			/// 
			///   Unless the TrimOption is specifically switched off ('t-') the string value will
			///   trimmed and, if Empty, will be returned immediately.
			/// 
			/// Step 5: Post-format processing is applied to the string.
			/// 
			///   It will be cased according to any CaseOption ('c') or CapitaliseOption ('C');
			///   It will be truncated if the MaximumWidthOption ('w') is specified;
			/// 
			/// Step 6. The string is combined with (optional) separator/prefix/suffix
			///   
			///   A leading separator may be specified in the expression; also a trailing separator from
			///   an earlier expression (a pending separator) may override it if it longer.
			///   A prefix and suffix may also be specified and are used to surround the string which
			///   is now known to be not-empty.
			/// 
			///   Where the SingularOption ('p') and/or PluralOption ('P') is/are specified in the expression:
			///     The value is first checked to see if it is considered Singular (ie. an Int32 1).
			/// 
			///     Where both the SingularOption and PluralOption are specified, one or the other
			///     (depending on the Singular determination) will be appended to any specified suffix.
			/// 
			///     Where only one of the SingularOption and PluralOptions are specified, then one or
			///     the other (depending on the Singular determination) will *replace* any suffix.
			/// 
			///   One special case exists where the value is non-Singular and the PluralOption is specified
			///   but without an expression and no SingularOption is specified. In this case, an 's' is
			///   appended to any suffix.
			/// 
			///   NB. Conditional Formatting can achieve the same effects as the Singular/Plural options but they
			///   are kept for backward compatibility.
			///   (e.g. "$Count' item':P$" or "$Count;item;items$")
			/// 
			/// 
			///   Any specified trailing separator is retained as a pending separator for any following expressions.
			/// 
			///   The final string is built as 'separator + prefix + stringValue + suffix' and returned.
			/// </summary>
			/// <param name="expression">The MemberExpression to evaluate.</param>
			/// <returns>A formatted string.</returns>
			protected virtual string ProcessMemberExpression(MemberExpression expression)
			{
				// Return immediately if any conditional expression fails
				if (expression.HasNonListDependencies)
				{
					if (expression.ContainsDependencyOption && !EvaluateDependencyExpression(expression)) return string.Empty;
					if (expression.ContainsGlobalDependencyOption && !EvaluateGlobalDependencyExpression(expression)) return string.Empty;
					if (expression.ContainsBlankReplacementOption && !EvaluateBlankReplacementDependencyExpression(expression)) return string.Empty;
				}

				// Get the target value
				object value = expression.IsSelf
				               	? target
				               	: expression.IsAlternateSource
				               	  	? GetCustomValue(expression.Name)
				               	  	: localMemberPathCache.GetValue(target, expression.Name);

				// DBNull is considered null
				if (value == DBNull.Value) value = null;

				string stringValue;

				// Replace null with NullOption expression
				if (value == null)
				{
					stringValue = ProcessElement(expression.NullOption);
				}

				// Process member list
				else if (!(value is string) && value is IEnumerable)
				{
					MemberListFormatter memberListFormatter;

					if (memberListFormatterCache == null)
					{
						memberListFormatterCache = new Dictionary<MemberExpression, MemberListFormatter>();
					}

					if (!memberListFormatterCache.TryGetValue(expression, out memberListFormatter))
					{
						memberListFormatter = new MemberListFormatter(this, expression);

						memberListFormatterCache[expression] = memberListFormatter;
					}

					stringValue = memberListFormatter.Build((IEnumerable) value);
				}

				// Use conditional formatting
				else if (expression.ConditionalFormattingEvaluator != null)
				{
					var conditionalFormatElement = expression.ConditionalFormattingEvaluator.GetConditionalFormatElement(value);

					if (conditionalFormatElement != null)
					{
						stringValue = ProcessElement(conditionalFormatElement.Expression);

						if (stringValue.Contains("@"))
						{
							stringValue = stringValue.Replace("@", FormatValue(value, expression));
						}
					}
					else
					{
						stringValue = string.Empty;
					}
				}

				// Look for a Zero Option
				else if (expression.ContainsZeroOption && IsZeroValue(value))
				{
					stringValue = ProcessElement(expression.ZeroExpression);
				}

				// Format using the f and F options
				else
				{
					stringValue = FormatValue(value, expression);
				}


				// Trim as required
				if (expression.ShouldTrim)
				{
					stringValue = stringValue.Trim();
				}

				// TODO: Should there be an EmptyReplacement option here??

				// Quick return if empty
				if (stringValue.Length == 0) return stringValue;

				// Case appropriately
				if (expression.ContainsCaseOption)
				{
					stringValue = expression.IsCaseOptionOn ? stringValue.ToUpper() : stringValue.ToLower();
				}
				else if (expression.ContainsCapitaliseOption)
				{
					stringValue = StringHelper.ToTitleCase(stringValue, !expression.IsCapitalizeOptionOn);
				}

				// Truncate if required
				if (expression.ContainsMaximumWidthOption)
				{
					var maximumLength = GetNumber(ProcessElement(expression.MaximumWidthExpression), 0);

					if (maximumLength != 0)
					{
						stringValue = stringValue.Substring(0, maximumLength);
					}
				}


				// Calculate any separator to use
				var separator = pendingSeparator != null || !isBlank ? ProcessElement(expression.LeadingSeparator) : string.Empty;

				if (pendingSeparator != null && pendingSeparator.Length > separator.Length)
				{
					separator = pendingSeparator;
				}

				// Get the prefix
				var prefix = ProcessElement(expression.Prefix);
				string suffix;

				var singularExpression = expression.SingularExpression;
				var pluralExpression = expression.PluralExpression;

				// Calculate the suffix to use (depends on the single and plural expressions)
				if (singularExpression == null && pluralExpression == null)
				{
					suffix = ProcessElement(expression.Suffix);
				}
				else
				{
					if (IsSingularValue(value))
					{
						suffix = (pluralExpression == null ? string.Empty : ProcessElement(expression.Suffix)) + ProcessElement(singularExpression);
					}
					else
					{
						var plural = ProcessElement(pluralExpression);

						// Check for special case when Plural option present but not specified
						// and no singular expression present
						// Assume that suffix is singular version and add an 's'
						if (plural.Length == 0 && singularExpression == null)
						{
							suffix = ProcessElement(expression.Suffix) + "s";
						}
						else
						{
							suffix = (singularExpression == null ? string.Empty : ProcessElement(expression.Suffix)) + plural;
						}
					}
				}

				// Concatenate but only if there are things to concatenate
				if (separator.Length + prefix.Length + suffix.Length != 0)
				{
					stringValue = separator + prefix + stringValue + suffix;
				}

				// Update the pending separator
				pendingSeparator = ProcessElement(expression.TrailingSeparator);

				// Return the final result
				return stringValue;
			}

			/// <summary>
			/// Finds a value to process based on its name (which would have started
			/// with a '#').
			/// 
			/// This may be from a named custom value (also ends with a '#'); or it
			/// could be from an alternative target.
			/// If the name evaluates to a numeric expression then it will be used as
			/// an indexer into the AdditionalTargets list. Otherwise the name will
			/// be used as a look up key in the NamedTargets Dictionary.
			/// 
			/// Null is returned if a value cannot be found.
			/// </summary>
			/// <param name="name">The name indicating where the custom value is to be obtained.</param>
			/// <returns>The custom value found (may be null).</returns>
			protected virtual object GetCustomValue(string name)
			{
				object alternateTarget = null;
				string alternateTargetSource;

				var dotIndex = name.IndexOf('.', 1);
				if (dotIndex == -1)
				{
					alternateTargetSource = name.Substring(1);
					name = string.Empty;
				}
				else
				{
					alternateTargetSource = name.Substring(1, dotIndex - 1);
					name = name.Substring(dotIndex + 1);
				}

				if (alternateTargetSource.Length > 0)
				{
					int additionalTargetIndex;

					if (int.TryParse(alternateTargetSource, out additionalTargetIndex))
					{
						alternateTarget = GetAdditionalTargetValue(additionalTargetIndex);
					}
					else if (Owner.namedTargets != null && Owner.namedTargets.ContainsKey(alternateTargetSource))
					{
						alternateTarget = Owner.namedTargets[alternateTargetSource];
					}
				}

				return localMemberPathCache.GetValue(alternateTarget, name);
			}

			/// <summary>
			/// Applies each element from the template to the target object and 
			/// produces a formatted string.
			/// </summary>
			/// <param name="target">The target object.</param>
			/// <param name="maximumLength">The maximum length allowed. Zero means any length.</param>
			/// <returns>A non-null formatted string.</returns>
			public string Format(object target, int maximumLength = 0)
			{
				string result;

				try
				{
					this.target = target;
					pendingSeparator = null;
					isBlank = true;

					// If there is only one element, process it directly
					// to save creating a StringBuilder
					if (elements.Length == 1)
					{
						result = ProcessElement(elements[0]);

						if (maximumLength > 0 && result.Length > maximumLength)
						{
							result = result.Substring(0, maximumLength);
						}
					}
					else
					{
						// Create a buffer if we don't already have one
						if (buffer == null) buffer = new StringBuilder();

						string firstStringValue = null;

						// Process each element
						foreach (var element in elements)
						{
							var elementResult = ProcessElement(element);
							if (elementResult.Length == 0) continue;

							buffer.Append(elementResult);

							// Keep a reference to the first string created
							if (firstStringValue == null)
							{
								firstStringValue = elementResult;
							}

							// No point continuing if we are going to trim anyway
							if (maximumLength != 0 && buffer.Length >= maximumLength) break;

							// Need to set this for the benefit of the Blank Replacement dependency
							isBlank = false;
						}

						// Use empty if nothing was produced
						if (firstStringValue == null)
						{
							result = string.Empty;
						}
						// May as well extract an already trimmed-to-size string
						// if a maximum length was set.
						else if (maximumLength > 0 && buffer.Length > maximumLength)
						{
							result = buffer.ToString(0, maximumLength);
						}
						// Just use the first string if that is all that was produced
						else if (buffer.Length == firstStringValue.Length)
						{
							result = firstStringValue;
						}
						// Just get the whole string from the builder
						else
						{
							result = buffer.ToString();
						}

						// Clear the buffer (but keep it for future use - no need to recreate it)
						buffer.Length = 0;
					}
				}
				finally
				{
					this.target = null;
					pendingSeparator = null;
					isBlank = true;
				}

				return result;
			}

			/// <summary>
			/// Formats a value according to the 'f' and 'F' options specified.
			/// </summary>
			/// <param name="target">The object to format.</param>
			/// <param name="expression">The MemberExpression with the format options.</param>
			/// <returns></returns>
			string FormatValue(object target, MemberExpression expression)
			{
				if (expression.ContainsFullFormatOption)
				{
					return ProcessElementNested(expression.FullFormatOption, target);
				}

				string format = ProcessElement(expression.FormatExpression);

				return StringHelper.GetFormattedString(target, Owner.formatProvider, format);
			}

			/// <summary>
			/// Finds the additional target at the specified index.
			/// 
			/// Will return null if the index is out of range.
			/// </summary>
			/// <param name="index">The index to lookup.</param>
			/// <returns>The additional target or null.</returns>
			object GetAdditionalTargetValue(int index)
			{
				if (index < 0 || index > Owner.additionalTargets.Length) return null;

				return index == 0 ? target : Owner.additionalTargets[index - 1];
			}

			/// <summary>
			/// Formats a value (similar to FormatValue(...)) but uses another
			/// Formatter class to ensure that variables such as blank and
			/// pending separator are kept separate.
			/// Used by the FullFormatOption which contains a full member
			/// expression of its own.
			/// </summary>
			/// <param name="formatterElement">The element to process.</param>
			/// <param name="target">The target on which to apply the expression.</param>
			/// <returns></returns>
			string ProcessElementNested(Expression formatterElement, object target)
			{
				if (formatterElement == null) return string.Empty;

				if (formatterElement is StringLiteral) return formatterElement.ToString();

				return new Formatter(formatterElement, Owner).Format(target);
			}

			/// <summary>
			/// Returns a formatted string from the element or an empty string.
			/// </summary>
			/// <param name="formatterElement">The element to use.</param>
			/// <returns>A non-null formatted string.</returns>
			internal string ProcessElement(IObjectFormatterElement formatterElement)
			{
				if (formatterElement == null) return string.Empty;

				if (formatterElement is MemberExpression) return ProcessMemberExpression((MemberExpression) formatterElement);

				if (formatterElement is StringLiteral) return formatterElement.ToString();

				if (formatterElement is CompositeExpression)
				{
					//TODO: Should we cache this StringBuilder too?
					var compositeOuput = new StringBuilder();

					foreach (var subElement in ((CompositeExpression) formatterElement).Expressions)
					{
						compositeOuput.Append(ProcessElement(subElement));
					}

					return compositeOuput.ToString();
				}

				throw new CodeShouldBeUnreachableException();
			}

			/// <summary>
			/// Checks an expression to see if there is a dependency option and, if so,
			/// determines whether the dependency is satisfied.
			/// 
			/// If the option is On then the dependency option parameter must have non-zero length and be 
			/// "True" or not "False" to satisfy the dependency.
			/// 
			/// If the option is Off then the dependency option parameter must be zero length or be "False"
			/// or not "True" to satisfy the dependency.
			/// </summary>
			/// <param name="memberExpression">The expression to check.</param>
			/// <returns>true if there is no dependency option or the dependency option is satisfied; false otherwise.</returns>
			bool EvaluateDependencyExpression(MemberExpression memberExpression)
			{
				var dependencyOptionParameter = memberExpression.DependencyOptionParameter;
				if (dependencyOptionParameter == null) return true;

				var dependencyValue = ProcessElement(dependencyOptionParameter);

				if (memberExpression.IsDependencyOptionOn)
				{
					return dependencyValue.Length != 0 && (dependencyValue == "True" || dependencyValue != "False");
				}

				return dependencyValue.Length == 0 || (dependencyValue == "False" || dependencyValue != "True");
			}

			/// <summary>
			/// Checks an expression to see if it contains a Global Dependency option and
			/// whether it meets that dependency if present.
			/// 
			/// Will return true if the dependency is not present
			/// </summary>
			/// <param name="memberExpression">The expression to check.</param>
			/// <returns>The result of the dependency.</returns>
			bool EvaluateGlobalDependencyExpression(MemberExpression memberExpression)
			{
				return !memberExpression.ContainsGlobalDependencyOption ||
						 (memberExpression.IsGlobalDependencyOptionOn ? Owner.globalDependency : !Owner.globalDependency);
			}

			/// <summary>
			/// Checks an expression to see if it contains a Blank Replacement Dependency option
			/// and whether it meets that dependency if present.
			/// </summary>
			/// <param name="memberExpression">The expression to check.</param>
			/// <returns>The result of the dependency.</returns>
			bool EvaluateBlankReplacementDependencyExpression(MemberExpression memberExpression)
			{
				return !memberExpression.ContainsBlankReplacementOption || isBlank;
			}

			/// <summary>
			/// Checks whether a value can be considered a singular (ie not plural) value.
			/// Used when different expressions are supplied for singular/plural results.
			/// </summary>
			/// <param name="value">The value to check.</param>
			/// <returns>true if the value can be converted to a 1; false otherwise.</returns>
			static bool IsSingularValue(object value)
			{
				try
				{
					//TODO: Can NumberState be used here?
					return Convert.ToInt32(value) == 1;
				}
				catch
				{
					return false;
				}
			}

			/// <summary>
			/// Checks whether a value is zero.
			/// </summary>
			/// <param name="value">The value to check.</param>
			/// <returns>true if the value can be converted to a 0; false otherwise.</returns>
			static bool IsZeroValue(object value)
			{
				try
				{
					//TODO: Can NumberState be used here?
					return Convert.ToInt32(value) == 0;
				}
				catch
				{
					return false;
				}
			}

		}
		#endregion Formatter

		#region List Formatter
		class ListFormatter: Formatter
		{
			/// <summary>
			/// Returns the index of the item within the current context list. (1-based)
			/// Null if not in a list.
			/// If the FormatList method is resolving duplicate items then it returns
			/// the index of the item within its duplicate set; otherwise the same as
			/// #ListPosition.
			/// </summary>
			const string CustomListContextIndex = "#";

			/// <summary>
			/// Returns the index of the item within the list being formatted. (0-based)
			/// Null if not in a list.
			/// </summary>
			const string CustomListIndex = "#ListIndex#";

			/// <summary>
			/// Returns the position of the item within the list being formatted. (1-based)
			/// Null if not in a list.
			/// </summary>
			const string CustomListPosition = "#ListPosition#";

			/// <summary>
			/// A list of elements that are Unique Dependencies.
			/// </summary>
			readonly MemberExpression[] uniqueDependencyExpressions;

			/// <summary>
			/// Flag set internally by the FormatList method so that non-unique rows that
			/// are be reevaluated will be able to specify an additional field/fields to make
			/// the result unique.
			/// </summary>
			int activeUniqueDependencyIndex = -1;

			/// <summary>
			/// Used internally by the FormatList method to hold the current list index
			/// so that it may be used in member expressions.
			/// This is the absolute index of the list being formatted.
			/// </summary>
			int listIndex = -1;

			/// <summary>
			/// Used internally by the FormatList method to hold the current unique list index
			/// so that it may be used in member expressions.
			/// This is the index within the set of duplicate items.
			/// </summary>
			int uniqueListIndex = -1;

			/// <summary>
			/// Used internally by the FormatList method to hold the current unique list count
			/// so that it may be used in member expressions.
			/// </summary>
			int uniqueListCount = -1;

			public ListFormatter(ObjectFormatter owner): base(owner)
			{
				uniqueDependencyExpressions = GetUniqueDependencyExpressions();
			}

			public ListFormatter(Expression element, ObjectFormatter owner): base(element, owner)
			{
				uniqueDependencyExpressions = GetUniqueDependencyExpressions();
			}

			/// <summary>
			/// Creates an array of those member expressions with unique dependency options.
			/// </summary>
			/// <returns>An array.</returns>
			MemberExpression[] GetUniqueDependencyExpressions()
			{
				return elements.OfType<MemberExpression>()
					.Where(me => me.ContainsUniqueDependencyOption || me.ContainsWeakUniqueDependencyOption)
					.ToArray();
			}

			/// <summary>
			/// Validates the arguments and then calls FormatListCore.
			/// </summary>
			/// <param name="targets">The collection of target object on which to apply the template.</param>
			/// <param name="maximumLength">The maximum length of each item. Zero means any length.</param>
			/// <returns>A string[] containing the formatted strings for each target object.</returns>
			public string[] FormatList(IList targets, int maximumLength = 0)
			{
				Guard.NotNull(targets, "targets");
				Guard.ValidArgumentRange(maximumLength >= 0, "maximumLength");

				return FormatListCore(targets, maximumLength);
			}

			/// <summary>
			/// Applies the template to a collection of target objects and returns a same-sized array of
			/// formatted strings.
			/// </summary>
			/// <param name="targets">The collection of target object on which to apply the template.</param>
			/// <param name="maximumLength">The maximum length of each item. Zero means any length.</param>
			/// <returns>A string[] containing the formatted strings for each target object.</returns>
			public string[] FormatListCore(IList targets, int maximumLength)
			{
				// Build a list for the results
				var result = new string[targets.Count];

				try
				{
					// Go through each item in the source list
					for (var i = 0; i < result.Length; i++)
					{
						// Update the field
						listIndex = i;

						// Format the item
						result[i] = Format(targets[i], maximumLength);
					}

					// Check if any of the elements had a UniqueDependencyOption
					if (uniqueDependencyExpressions.Length != 0)
					{
						// They did so use them to make the list unique if necessary
						ApplyUniqueDependencyExpressions(targets, maximumLength, result);
					}

				}
				finally
				{
					// Reset the field
					listIndex = -1;
				}

				return result;
			}

			/// <summary>
			/// Override to check any UniqueDependency before continuing processing.
			/// </summary>
			/// <param name="expression">The MemberExpression to process.</param>
			/// <returns>The formatted string.</returns>
			protected override string ProcessMemberExpression(MemberExpression expression)
			{
				// If we are processing a list, we need to check the Unique
				if (listIndex != -1 && !EvaluateUniqueDependencyExpression(expression)) return string.Empty;

				return base.ProcessMemberExpression(expression);
			}

			/// <summary>
			/// Override to check if the member name is a CustomList items.
			/// </summary>
			/// <param name="name">The name to process.</param>
			/// <returns>The value to process.</returns>
			protected override object GetCustomValue(string name)
			{
				switch (name)
				{
					case CustomListContextIndex: // #
						if (activeUniqueDependencyIndex != -1)
						{
							// Fancy way of calculating how many digits the largest number has.
							var placeCount = (int) Math.Ceiling(Math.Log10(uniqueListCount));

							return (uniqueListIndex + 1).ToString("D" + placeCount);
						}

						return listIndex + 1;

					case CustomListPosition: // #ListPosition# (1-based)
						return listIndex + 1;

					case CustomListIndex: // #ListIndex# (0-based)
						return listIndex;

					default:
						return base.GetCustomValue(name);
				}
			}

			/// <summary>
			/// Evaluates an expression to see whether it contains a UniqueDependencyOption
			/// or a WeakUniqueDependencyOption and, if it does, whether it is currently active.
			/// </summary>
			/// <param name="memberExpression">The expression to check.</param>
			/// <returns>True if neither of the dependency options are present (ie the dependency
			/// is implicit met) or one is present and it is currently active (ie the dependency
			/// is explicitly met)
			/// </returns>
			bool EvaluateUniqueDependencyExpression(MemberExpression memberExpression)
			{
				switch (memberExpression.UniqueDependencyOrWeakDependencyName)
				{
					case ObjectFormatterOptions.UniqueDependencyOption:
						return IsUniqueDependencyExpressionActive(memberExpression, true);

					case ObjectFormatterOptions.WeakUniqueDependencyOption:
						return IsUniqueDependencyExpressionActive(memberExpression, false);

					default:
						return true;
				}
			}

			/// <summary>
			/// Indicates whether the specified expression is currently active.
			/// For Strong Dependencies, will return True if it matches the currently active
			/// unique dependency or any of the preceeding unique dependencies.
			/// For Weak Dependencies, will return True if it is the currently active
			/// unique dependency.
			/// </summary>
			/// <param name="memberExpression">The expression to check.</param>
			/// <param name="isStrongDependency">True if the dependency is Strong.</param>
			/// <returns>True if the expression is active; False otherwise.</returns>
			bool IsUniqueDependencyExpressionActive(MemberExpression memberExpression, bool isStrongDependency)
			{
				if (activeUniqueDependencyIndex == -1) return false;

				if (isStrongDependency)
				{
					// Use if located within the list of already active dependencies 
					for (var i = 0; i < activeUniqueDependencyIndex; i++)
					{
						if (uniqueDependencyExpressions[i] == memberExpression) return true;
					}
				}

				return uniqueDependencyExpressions[activeUniqueDependencyIndex] == memberExpression;
			}

			/// <summary>
			/// Attempts to make the list of formatted results unique by using any Unique Dependencies
			/// in the template and reformatting duplicates.
			/// 
			/// It does not guarantee uniqueness unless the final Unique Dependency is one of the
			/// CustomListXXX options.
			/// </summary>
			/// <param name="targets">The list of targets being formatted.</param>
			/// <param name="maximumLength">The maximum length of the formatted result (0=No limit).</param>
			/// <param name="result">The list of formatted output strings.</param>
			void ApplyUniqueDependencyExpressions(IList targets, int maximumLength, string[] result)
			{
				// Look for duplicate strings
				var duplicateSets = StringHelper.FindDuplicateStringsIndexesCore(result);

				// Quick return if nothing to do
				if (duplicateSets.Count == 0) return;

				try
				{
					// Start at the first unique dependency
					activeUniqueDependencyIndex = 0;

					do
					{
						// Get the current unique dependency
						var activeUniqueDependencyExpression = uniqueDependencyExpressions[activeUniqueDependencyIndex];

						// Make a note if it is weak
						var isWeak = activeUniqueDependencyExpression.ContainsWeakUniqueDependencyOption;

						// Get an array of the duplicates strings
						var duplicateStrings = duplicateSets.Keys.ToArray();

						// Go through each of the duplicate strings
						for (var i = 0; i < duplicateStrings.Length; i++)
						{
							// Get the string
							var duplicateString = duplicateStrings[i];

							// and the list of indexes where it occurs
							var duplicateIndexes = duplicateSets[duplicateString];
							uniqueListCount = duplicateIndexes.Count;

							// Go through each occurence
							for (var j = 0; j < uniqueListCount; j++)
							{
								// Find the duplicate index from the original list
								var duplicateIndex = duplicateIndexes[j];

								// and make it available as a field
								listIndex = duplicateIndex;

								// Also make the index within the current duplicate
								// set available as a field
								uniqueListIndex = j;

								// Reformat the list item occurence now that the unique expressions are active
								result[duplicateIndex] = Format(targets[duplicateIndex], maximumLength);
							}

							// If the current unique dependency is weak, we recheck the subset of
							// items just updated to see if there are still duplicates
							if (isWeak && StringHelper.FindDuplicateStringsIndexesCore(StringHelper.GetSubset(result, duplicateIndexes)).Count > 0)
							{
								// There are still duplicates; find out if this weak unique dependency is list or group scoped
								var isListWeak = activeUniqueDependencyExpression.IsUniqueWeakDependencyOptionOn;

								// Revert back the current set; and all previous sets if the weak dependency is list-based
								for (var k = (isListWeak ? 0 : i); k <= i; k++)
								{
									var reversionString = duplicateStrings[k];

									foreach (var duplicateIndex in duplicateSets[reversionString])
									{
										result[duplicateIndex] = reversionString;
									}
								}

								// The weak dependency is list-based, and since we have just reverted 
								// one group, the whole list cannot be made unique so no point in trying 
								// the next duplicate group - break out of the loop and try another 
								// unique dependency.
								if (isListWeak) break;
							}
						}

						// Move to the next unique dependency
						activeUniqueDependencyIndex++;

						// Quit if there are no more to process
						if (activeUniqueDependencyIndex == uniqueDependencyExpressions.Length) break;

						// Update the duplicate sets
						duplicateSets = StringHelper.FindDuplicateStringsIndexesCore(result);

					// Repeat until no duplicates remain
					} while (duplicateSets.Count > 0);
				}
				finally
				{
					// Reset all the fields
					uniqueListIndex = -1;
					uniqueListCount = -1;
					activeUniqueDependencyIndex = -1;
				}
			}
		}
		#endregion List Formatter

		#region Member List Formatter
		class MemberListFormatter: FormatterBase
		{
			// Immutable properties from the MemberExpression
			readonly string separator;
			readonly string lastSeparator;
			readonly int maximumItemLength;
			readonly Expression formatOption;
			readonly bool isSimpleFormat;
			readonly SortType sourceItemSort;
			readonly SortType targetStringSort;

			// Caches the last list formatter to save having to recreate it
			ListFormatter listFormatter;

			// For simple lists with a common type, we cache the associated
			// getter to save having to look it up again.
			Type lastCommonType;
			GenericGetter lastCommonGetter;

			enum SortType
			{
				None,
				Ascending,
				Descending
			}

			public MemberListFormatter(Formatter formatter, MemberExpression expression): base(formatter.Owner)
			{
				// Precalculate all the stuff that won't change
				separator = StringHelper.GetNotNullOrEmpty(formatter.ProcessElement(expression.ListSeparatorExpression), ",");
				lastSeparator = StringHelper.GetNotEmpty(formatter.ProcessElement(expression.ListLastSeparatorExpression));
				maximumItemLength = GetNumber(formatter.ProcessElement(expression.ListItemWidthExpression), 0);
				formatOption = expression.FormatExpression;
				isSimpleFormat = formatOption == null || formatOption is StringLiteral;
				sourceItemSort = !expression.ContainsSortSourceItemsOption
				                 	? SortType.None
				                 	: expression.IsSortSourceItemsOptionOn
				                 	  	? SortType.Ascending
				                 	  	: SortType.Descending;
				targetStringSort = !expression.ContainsSortTargetStringOption
				                 	? SortType.None
				                 	: expression.IsSortTargetStringOptionOn
				                 	  	? SortType.Ascending
				                 	  	: SortType.Descending;

			}

			/// <summary>
			/// Build a list of values into a single string which is
			/// sorted/separated/truncated as the options dictate.
			/// </summary>
			/// <param name="values"></param>
			/// <returns></returns>
			public string Build(IEnumerable values)
			{
				// If no sorting is required and the items don't need special formatting
				// we don't need to build a list here, just pass it directly to BuildList
				// which accepts an enumerable input
				if (isSimpleFormat && sourceItemSort == SortType.None && targetStringSort == SortType.None)
				{
					return StringHelper.BuildList(values, separator, lastSeparator, formatOption == null ? null : formatOption.ToString(), null, null, Owner.formatProvider, maximumItemLength);
				}

				// If the source was already an IList and we are not planning to sort
				// we try to preserve the original list but if a sort is required
				// we must create a list anyway
				IList cleanValues = values is IList && sourceItemSort == SortType.None
				                    	? RemoveNulls((IList) values)
				                    	: RemoveNulls(values);

				// Quick return if nothing to do
				if (cleanValues.Count == 0) return string.Empty;

				// We now have an IList which has been cleansed of all nulls
				// so sort it if required
				if (sourceItemSort != SortType.None)
				{
					SortSourceItems((List<object>) cleanValues);
				}

				// If we couldn't call BuildList before only because of the source sort
				// we can now
				if (isSimpleFormat && targetStringSort == SortType.None)
				{
					return StringHelper.BuildList(cleanValues, separator, lastSeparator, formatOption == null ? null : formatOption.ToString(), null, null, Owner.formatProvider, maximumItemLength);
				}

				// For simple member path format expressions,
				// We can do it here if there is a common type
				// for the list items
				string[] targetStrings = TrySimpleMemberPathList(cleanValues);

				// If not processed, do the normal thing
				if (targetStrings == null)
				{
					if (listFormatter == null)
					{
						if (formatOption == null)
						{
							listFormatter = new ListFormatter(new ObjectFormatter("$.$"));
						}
						else if (formatOption is StringLiteral)
						{
							listFormatter = new ListFormatter(new ObjectFormatter("$.:f='" + formatOption + "'$"));
						}
						else
						{
							listFormatter = new ListFormatter(formatOption, Owner);
						}
					}

					// Let the ListFormatter do the work
					targetStrings = listFormatter.FormatListCore(cleanValues, maximumItemLength);

					// Ensure that any string.Empty returned by the ListFormatter are removed
					targetStrings = StringHelper.GetNotNullOrEmpty(targetStrings);
				}
				else
				{
					if (targetStringSort == SortType.None)
					{
						return StringHelper.JoinCore(targetStrings, separator, lastSeparator);
					}
				}

				// Sort the strings if required
				if (targetStringSort != SortType.None)
				{
					SortTargetStrings(targetStrings);
				}

				// Combine into one string with the appropriate separator(s)
				return StringHelper.JoinCore(targetStrings, separator, lastSeparator);
			}

			/// <summary>
			/// Optimization to format certain lists without having to create a list formatter.
			/// (The list must already have had any nulls removed).
			/// 
			/// - The list must contain items all the same type and a a GenericGetter must be
			/// available for that type. Will return null if not the case.
			/// - The expression must be a simple member path.
			/// </summary>
			/// <param name="cleanValues">A list of non-null objects.</param>
			/// <returns>A formatted string array.</returns>
			string[] TrySimpleMemberPathList(IList cleanValues)
			{
				var simpleExpression = formatOption as MemberExpression;
				if (simpleExpression == null || !simpleExpression.IsSimpleMemberPath) return null;

				GenericGetter commonGetter = FindCommonGetter(cleanValues, ((MemberExpression) formatOption).Name);
				if (commonGetter == null) return null;

				var targetStrings = new List<string>(cleanValues.Count);
				var format = simpleExpression.FormatExpression == null ? null : simpleExpression.FormatExpression.ToString();
				var formatProvider = Owner.formatProvider;

				for (var i = 0; i < cleanValues.Count; i++)
				{
					var value = commonGetter(cleanValues[i]);
					if (value == null) continue;

					var formattedValue = StringHelper.GetFormattedString(value, formatProvider, format);
					if (string.IsNullOrEmpty(formattedValue)) continue;

					targetStrings.Add(formattedValue);
				}

				return targetStrings.ToArray();
			}

			/// <summary>
			/// Checks that the contents of a list are all of the same type and
			/// that a GenericGetter is available for the memberPath.
			/// 
			/// Caches the last common type used with the associated Getter to
			/// save having to look it up again.
			/// </summary>
			/// <param name="list">The list of (non-null) items to check.</param>
			/// <param name="memberPath">The member path.</param>
			/// <returns>A GenericGetter to use or null.</returns>
			GenericGetter FindCommonGetter(IList list, string memberPath)
			{
				Type commonType = list[0].GetType();

				for(var i = 1; i < list.Count; i++)
				{
					if (list[i].GetType() != commonType) return null;
				}

				if (commonType == lastCommonType) return lastCommonGetter;

				GenericGetter result = MemberPathCache.GetAccessor(commonType, memberPath);

				lastCommonType = commonType;
				lastCommonGetter = result;

				return result;
			}

			/// <summary>
			/// Sorts the resulting target strings.
			/// </summary>
			/// <param name="values">The target strings to sort.</param>
			void SortTargetStrings(string[] values)
			{
				try
				{
					Array.Sort(values);

					// Put in reverse order if sorting descending
					if (targetStringSort == SortType.Descending)
					{
						Array.Reverse(values);
					}
				}
				catch {}
			}

			/// <summary>
			/// Sorts the source items.
			/// </summary>
			/// <param name="values">The source items to sort.</param>
			void SortSourceItems(List<object> values)
			{
				try
				{
					//TODO: Is there a better way than this?
					//TODO: Can we implement sorting on an addition field?
					// e.g. Sort a class by a date property and then produce a list
					// from other properties?
					values.Sort();

					// Put in reverse order if sorting descending
					if (sourceItemSort == SortType.Descending)
					{
						values.Reverse();
					}
				}
				catch {}
			}

			/// <summary>
			/// Builds a list of items from an IEnumerable source
			/// ensuring that null items are skipped.
			/// </summary>
			/// <param name="values">The IEnumerable source.</param>
			/// <returns>A List of non-null objects</returns>
			static List<object> RemoveNulls(IEnumerable values)
			{
				var result = new List<object>();

				foreach(var value in values)
				{
					if (value == null) continue;

					result.Add(value);
				}

				return result;
			}

			/// <summary>
			/// Builds a list of items from an IList source
			/// ensuring that null items are skipped.
			/// 
			/// Where the source list is null-free, then it
			/// is returned directly to save duplicating the
			/// list.
			/// </summary>
			/// <param name="values">The IList to check for nulls.</param>
			/// <returns>The original source IList if no nulls found, or a List containing the non-null items.</returns>
			static IList RemoveNulls(IList values)
			{
				var hasNull = false;

				foreach (var value in values)
				{
					if (value == null)
					{
						hasNull = true;
						break;
					}
				}

				if (!hasNull) return values;

				var result = new List<object>(values.Count - 1);

				foreach(var value in values)
				{
					if (value == null) continue;

					result.Add(value);
				}

				return result;
			}

		}
		#endregion Member List Formatter
	}
}