// PathEx.cs: path processing functionality beyond what System.IO.Path offers.
using System;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace PathEx
{
	/// <summary>
	/// Provides path processing functionality beyond what System.IO.Path offers.
	/// </summary>
	/// <remarks>
	/// Here are a couple of things System.IO.Path doesn't offer:
	///
	/// <code>
	/// PathEx.RemoveLastPath("/Windows/calc.exe") // = "/Windows"
	/// PathEx.RemoveLastPath("/Windows/calc.exe/") // = "/Windows"
	///
	/// PathEx.GetRelativePath("/Windows/System32", "/Windows/calc.exe") // = "../calc.exe"
	/// 
	/// PathEx.IsPathSeparator('\\') // = true
	/// PathEx.IsPathSeparator('/') // = true
	/// PathEx.IsPathSeparator('Q') // = false
	///
	/// PathEx.CollapsePath("//A/../B/./C") // = "//B/C"
	/// </code></remarks>
	public class PathEx
	{
		/// <summary>Returns c == '\\' || c == '/'.
		/// </summary>
		public static bool IsPathSeparator(char c)
			{ return c == '\\' || c == '/'; }
		
		/// <summary>
		/// Determines how much of the beginning of the path string 
		/// represents a drive, volume, protocol, or domain name, and returns
		/// it, including trailing slashes.  If the path does not appear to be
		/// an absolute path, then an empty string (not null) is returned.
		/// </summary>
		/// <param name="includeDomain">If this is true, then the return value 
		/// includes the computer or domain name; if false, then the return 
		/// value includes only the drive or protocol specification and the
		/// initial slash(es).
		/// <param name="wantTrailingSlash">If true, then the trailing slash on 
		/// a computer or domain name is included; otherwise, it is omitted.
		/// This parameter does not apply if if includeDomain is false.</param>
		/// </param>
		/// <remarks>
		/// This function assumes that the path is well-formed.  In other
		/// words, you can expect garbage-in-garbage-out.  The includeDomain
		/// parameter has an effect only if the function believes that the
		/// path includes a computer or domain name, which is indicated by
		/// the presence of more than one slash.  For example, in
		/// "file://A/B", there are two slashes, so A is assumed to be
		/// the "volume name".  On the other hand, in "C:/A/B", there is only
		/// one slash, so A is considered to be a folder name.  See the 
		/// examples below for the consequences of this interpretation.
		/// <p>Examples (where includeDomain and wantTrailingSlash are true 
		/// unless said otherwise):</p>
		/// <code>
		/// \Test                             => \
		/// \\ComputerName                    => \\ComputerName
		/// \\ComputerName                    => \\ (if !includeDomain)
		/// \\ComputerName\Test               => \\ComputerName\
		/// C:\Windows                        => C:\
		/// http://www.google.com/index.html  => http://www.google.com/
		/// http://www.google.com/index.html  => http://www.google.com (if !wantTrailingSlash)
		/// file:///C:/Windows                => file:///C:/
		/// file:///C:/Windows                => file:///C:/ (if !wantTrailingSlash)
		/// file:///C:/Windows                => file:///    (if !includeDomain)
		/// C:D:E                             => C:
		/// C:D/E                             => C:
		/// file///C:/Windows                 => (returns String.Empty)
		/// Relative/Path                     => (returns String.Empty)
		/// Hello                             => (returns String.Empty)
		/// </code>
		/// </remarks>
		public static string GetDriveOrDomain (string path, bool includeDomain, bool wantTrailingSlash)
		{
			return path.Substring(0, GetDriveOrDomainLen (path, includeDomain, wantTrailingSlash));
		}
		/// <summary>Behaves like <see cref="GetDriveOrDomain"/>, except that
		/// this function returns the length of the drive or volume string
		/// rather than the string itself.
		/// </summary>
		/// <param name="wantTrailingSlash">If true, then the trailing slash on 
		/// a computer or domain name is included; otherwise, it is omitted.
		/// This parameter does not apply if if includeDomain is false.</param>
		/// <returns>The number of characters at the beginning of the path
		/// which represent the drive or volume name</returns>
		public static int GetDriveOrDomainLen (string path, bool includeDomain, bool wantTrailingSlash)
		{
			int slashes = -1;
			int i;

			for (i = 0; ; i++) {
				if (i == path.Length) {
					// There are no colons or slashes found, so there is NO 
					// drive/protocol/domain in it.
					return 0;
				}
				if (path[i] == ':')
					break;
				if (IsPathSeparator(path[i])) {
					if (i == 0) {
						slashes++;
						break;
					} else
						return 0; // Relative path detected
				}
			}
			do {
				if (++i == path.Length) return i;
				slashes++;
			} while (IsPathSeparator(path[i]));

			if (slashes > 1 && includeDomain) {
				// Multiple slashes indicates a domain (or volume) name.

				// Find out where the name of the volume/domain ends.
				do
					if (++i == path.Length) return i;
				while (!IsPathSeparator(path[i]));
				
				if (wantTrailingSlash)
					++i;
			}
			return i;
		}
		
		/// <summary>Removes the last path component.  Returns the same
		/// string if the path string ends in multiple slashes.  Also, if 
		/// stopAtColon is true, returns the same path if the final path
		/// component ends in a colon (e.g. X/Y/Z: or C:\)
		/// </summary>
		/// <remarks>
		/// Equivalent to path.Substring(0, FindBeginningOfLastPath(path)).
		/// Examples (assuming stopAtColon is true):
		/// <code>
		/// C:\                                 => C:\
		/// C:\                                 => (empty string if !stopAtColon)
		/// http://                             => http://
		/// test//                              => test//
		/// test/                               => (empty string)
		/// http://www.google.ca                => http://
		/// http://www.google.ca/               => http://
		/// http://www.google.ca/index.html     => http://www.google.ca/
		/// C:\Test                             => C:\
		/// C:\A\B                              => C:\A\
		/// C:\A\B\                             => C:\A\
		/// </code></remarks>
		public static string RemoveLastPath (string path, bool stopAtColon)
		{
			return path.Substring(0, FindBeginningOfLastPath(path, stopAtColon));
		}
		public static string RemoveLastPath (string path)
		{
			return path.Substring(0, FindBeginningOfLastPath(path, false));
		}
		
		/// <summary>
		/// Equivalent to FindBeginningOfPriorPath(path, path.Length).
		/// </summary>
		public static int FindBeginningOfLastPath (string path, bool stopAtColon)
		{
			return FindBeginningOfPriorPath(path, path.Length, stopAtColon);
		}

		public static int FindBeginningOfPriorPath (string path, int startAt, bool stopAtColon)
		{
			int i = startAt - 1;
			if (i < 0 || (path[i] == ':' && stopAtColon))
				return startAt;
			if (IsPathSeparator(path[i])) {
				i--;
				if (i < 0 || IsPathSeparator(path[i]) 
					|| (path[i] == ':' && stopAtColon))
					return startAt;
			}
			for (i--; i >= 0 && !IsPathSeparator(path[i]); i--) { }
			return i + 1;
		}
		
//		private static bool BeginningsMatch(string s1, string s2, int len)
//			{ return string.Compare(s1, 0, s2, 0, len, true) == 0; }

		protected static char GetPathSeparator(string path)
		{
			for (int i = 0; i < path.Length; i++)
				if (IsPathSeparator(path[i])) return path[i];
			return Path.PathSeparator;
		}
		protected static bool AreEqual(char c1, char c2, bool caseSensitive)
		{
			if (c1 == c2)
				return true;
			if (caseSensitive)
				return false;
			if (c1 >= 'a' && c1 <= 'z')
				return c1 - ('a' - 'A') == c2;
			else
				return false;
		}

		/// <summary>Converts an absolute path to a relative path, given
		/// a starting path.  In a sense, "from" is "subtracted" from "to".
		/// Combining, a.k.a. "adding" the return value to <i>from</i> should 
		/// yield <i>to</i>.
		/// </summary>
		/// <param name="from">Path from which to start.</param>
		/// <param name="to">Destination path</param>
		/// <param name="requireSameRootFolder">If this is true, then 'from' 
		/// and 'to' must have the same root folder in order to successfully
		/// generate a relative path between them.  If a relative path cannot
		/// be generated, then 'to' itself is returned.
		/// If this is false, then a relative path is generated even if 'from'
		/// and 'to' have different root folders.
		/// </param>
		/// <param name="allowRelativePaths">If this is true, and 'from' and
		/// 'to' are relative paths, then GetRelativePath attempts to find
		/// a relative path between them.  If allowRelativePaths is false,
		/// and 'from' and 'to' are relative paths, then GetRelativePath simply
		/// returns 'to' unchanged.
		/// </param>
		/// <returns>The path that gets you from 'from' to 'to'.</returns>
		/// <remarks>In order for this function to work reliably, 'from' and
		/// 'to' must use the same path separator character.  In other words,
		/// they both must use a backslash to separate paths or else they both 
		/// must use a forward slash.
		/// </remarks>
		/// <example><code>
		/// Examples might not be perfect.
		/// 
		/// value of 'from'  value of 'to'  return value
		/// ---------------  -------------  ------------
		/// A:\B\C\D         A:\B\C\D       (empty string)
		/// A:\B\C\D         A:\B\C\D\E     E
		/// A:\B\C\D         A:\B\C         ..
		/// A:\B\C\D         A:\            ..\..\..   (if requireSameRootFolder)
		/// A:\B\C\D         A:\            A:\        (if !requireSameRootFolder)
		/// A/B/C            A/B/D          A/B/D      (if !allowRelativePaths)
		/// A/B/C            A/B/D          ../D       (if allowRelativePaths)
		/// A:\B\C\D         \B\C\E         \B\C\E
		/// \B\C\D           \B\C\E         ..\E
		/// \B\C\D           \B\C\D\E\      E\
		/// \B\C\D           \B\C\E\        ..\E\
		/// \B\C             \D\E\          C:\D\E\    (if requireSameRootFolder)
		/// \B\C             \D\E\          ..\..\D\E\ (if !requireSameRootFolder)
		/// http://W/X       http://Y/Z     http://Y/Z
		/// http://W/X       http://W/Y     http://W/Y (if requireSameRootFolder)
		/// http://W/X       http://W/Y     ../Y       (if !requireSameRootFolder)
		/// </code></example>
		public static string GetRelativePath (string from, string to, bool requireSameRootFolder, bool allowRelativePaths, bool caseSensitive)
		{
			int driveEndsAt = GetDriveOrDomainLen(from, true, true);
			int driveEndsAt2 = GetDriveOrDomainLen(to, true, true);
			if (driveEndsAt != driveEndsAt2 || (driveEndsAt == 0 && !allowRelativePaths))
				return to; // Two different domains (no relative path exists),
					// or one of the paths is relative (relative path is unknown)
			
			char separator = GetPathSeparator(from);
			
			int difStart = 0; // The beginning of the difference(s)

			// Find out where they first diverge.
			for (int i = 0; ; i++) {
				if (i == from.Length) {
					if (i == to.Length) {
						// The strings are equal!
						return string.Empty;
					} else {
						if (IsPathSeparator(to[i]))
							difStart = i + 1;
						break;
					}
				}
				if (i == to.Length) {
					if (IsPathSeparator(from[i]))
						difStart = i + 1;
					break;
				}
				if (!AreEqual(from[i], to[i], caseSensitive))
					break;
				if (IsPathSeparator(from[i]))
					difStart = i + 1;
			}
			if (difStart < driveEndsAt)
				return to; // Two different domains (no relative path exists)
			if (requireSameRootFolder && difStart == driveEndsAt)
				return to; // Two different root folders

			StringBuilder relPath = new StringBuilder();

			// At this point we know that we're going to make a relative path.
			// This is a two-step process: 
			// (1) add ..'s until all the excess parts of 'from' are gone
			bool foundOne = true;
			for (int i = difStart; i < from.Length; i++) {
				if (foundOne) {
					foundOne = false;
					relPath.Append("..");
					relPath.Append(separator);
				}
				if (IsPathSeparator(from[i]))
					foundOne = true;
			}
			
			// (2) add the end of 'to'
			if (difStart < to.Length)
				relPath.Append(to, difStart, to.Length - difStart);

			return relPath.ToString();
		}

		/// <summary>Adds path2 on the end of path1 in a similar manner to 
		/// Path.Combine(), with the exception that path components of 
		/// "." and ".." are removed.
		/// </summary>
		public static string Combine(string path1, string path2) {
			return CollapsePath(Path.Combine(path1, path2));
		}
		
		/// <summary>
		/// Removes path components named "." and "..".  Since ".." represents
		/// "going back to the parent folder", when a ".." is discovered, both
		/// it and the immediately prior component in the string are deleted.
		/// </summary>
		/// <example><code>
		/// Input                Output
		/// -----                ------
		/// C:\Test              C:\Test
		/// \Hello\..            \
		/// \Hello\..\           \
		/// Hello\..             (empty string)
		/// Hello\.              Hello\
		/// A\.\B\.\C\           A\B\C\
		/// A\..\B\C             B\C
		/// \\A\..\B\C           \\B\C
		/// http://test/..       http://
		/// </code></example>
		public static string CollapsePath(string path)
		{
			int pathStart = GetDriveOrDomainLen(path, false, true);
			
			// Begin at the end.
			int i = path.Length;
			while (i > pathStart) {
				int newI = FindBeginningOfPriorPath(path, i, false);
				bool reachedLimit = false;
				Debug.Assert (newI >= pathStart);
				if (newI == i) // Unable to proceed further backward
					reachedLimit = true;
				i = newI;
				if (path[i] == '.') {
					if (i + 1 < path.Length) {
						if (IsPathSeparator(path[i + 1]))
							path = path.Remove(i, 2);
						else if (path[i + 1] == '.') {
							// Found "..".
							if (reachedLimit)
								break; // Unable to proceed further.

							// Confirm that it is a complete path component.
							int endI = i + 2;
							if (endI < path.Length) {
								if (IsPathSeparator(path[endI]))
									endI++;
								else
									continue;
							}

							int priorI = FindBeginningOfPriorPath(path, i, false);
							if (priorI == i) // Unable to proceed further.
								return path;
							
							path = path.Remove(priorI, endI - priorI);
							i = priorI;
						}
					} else
						path = path.Remove(i, 1);
				}
				if (reachedLimit)
					break;
			}
			return path;
		}
		private PathEx() {}

	}
	public class PathExTest
	{
		protected class OneTest {
			public OneTest(string In, string _Out) { Path1 = In; Out = _Out; }
			public OneTest(string In, string _Out, bool flag1) { Path1 = In; Out = _Out; Flag1 = flag1; }
			public OneTest(string In, string _Out, bool flag1, bool flag2) { Path1 = In; Out = _Out; Flag1 = flag1; Flag2 = flag2; }
			public OneTest(string path1, string path2, string _Out) { Path1 = path1; Path2 = path2; Out = _Out; }
			public OneTest(string path1, string path2, string _Out, bool flag1) { Path1 = path1; Path2 = path2; Out = _Out; Flag1 = flag1; }
			public OneTest(string path1, string path2, string _Out, bool flag1, bool flag2) { Path1 = path1; Path2 = path2; Out = _Out; Flag1 = flag1; Flag2 = flag2; }
			public OneTest(string path1, string path2, string _Out, string _Out2) { Path1 = path1; Path2 = path2; Out = _Out; Out2 = _Out2; }
			public OneTest(string path1, string path2, string _Out, string _Out2, bool flag1) { Path1 = path1; Path2 = path2; Out = _Out; Out2 = _Out2; Flag1 = flag1; }
			public string Path { get { return Path1; } }
			public string Path1;
			public string Path2;
			public string Out;
			public string Out2;
			public bool Flag1;
			public bool Flag2;
		}
		
		protected static OneTest[] testsGetRelPath = new OneTest[]
		{   //  path1, path2, if !requireSameRootFolder, if requireSameRootFolder, allowRelativePaths
			new OneTest(@"A:\B\C\D",     @"A:\B\C\D",    @"",           @"",        false),
			new OneTest(@"A:\B\C\D",     @"A:\B\C\D\E",  @"E",          @"E",       false),
			new OneTest(@"A:\B\C\D",     @"A:\B\C",      @"..\",        @"..\",     false),
			new OneTest(@"A:\B\C\D",     @"A:\",         @"..\..\..\",  @"A:\",     false),
			new OneTest(@"A:\B\C\D\",    @"A:\",         @"..\..\..\",  @"A:\",      true),
			new OneTest(@"A:\B\C\D\",    @"A:",          @"A:",         @"A:",       true),
			new OneTest(@"A/B/C",        @"A/B/D",       @"A/B/D",      @"A/B/D",   false),
			new OneTest(@"A/B/C/",       @"A/B/D/",      @"../D/",      @"../D/",    true),
			new OneTest(@"A:\B\C\D",     @"\B\C\E",      @"\B\C\E",     @"\B\C\E",  false),
			new OneTest(@"\B\C\D",       @"\B\C\E",      @"..\E",       @"..\E",    false),
			new OneTest(@"\B\C\D",       @"\B\C\D\E\",   @"E\",         @"E\",      false),
			new OneTest(@"\B\C\D",       @"\B\C\E\",     @"..\E\",      @"..\E\",   false),
			new OneTest(@"\B\C",         @"\D\E\",       @"..\..\D\E\", @"\D\E\",   false),
			new OneTest(@"http://W/X",   @"http://Y/Z",  @"http://Y/Z", @"http://Y/Z", false),
			new OneTest(@"http://W/X",   @"http://W/Y",  @"../Y",       @"http://W/Y", false),
		};

		protected static OneTest[] testsGetDriveOrDomain = new OneTest[]
		{ // input, output, includeDomain, wantTrailingSlash
			new OneTest(@"Hello",                             @"",            true, true),
			new OneTest(@"\Test",                             @"\",           true, true),
			new OneTest(@"\\ComputerName",                    @"\\ComputerName", true, true),
			new OneTest(@"\\ComputerName",                    @"\\",          false, true),
			new OneTest(@"\\ComputerName",                    @"\\",          false, false),
			new OneTest(@"\\ComputerName\Test",               @"\\ComputerName\", true, true),
			new OneTest(@"C:\Windows",                        @"C:\",         true, true),
			new OneTest(@"http://www.google.com/index.html",  @"http://www.google.com/", true, true),
			new OneTest(@"http://www.google.com/index.html",  @"http://www.google.com", true, false),
			new OneTest(@"file:///C:/Windows",                @"file:///C:/", true, true),
			new OneTest(@"file:///C:/Windows",                @"file:///C:",  true, false),
			new OneTest(@"file:///C:/Windows",                @"file:///",    false, true),
			new OneTest(@"file:///C:/Windows",                @"file:///",    false, false),
			new OneTest(@"C:D:E",                             @"C:",          true, true),
			new OneTest(@"C:D/E",                             @"C:",          true, true),
			new OneTest(@"file///C:/Windows",                 @"",            true, true),
			new OneTest(@"Relative/Path",                     @"",            true, true),
		};

		protected static OneTest[] testsRemoveLastPath = new OneTest[]
		{
			new OneTest(@"C:\",                              @"C:\", true),
			new OneTest(@"C:\",                              @"", false),
			new OneTest(@"Alpha/Beta:/",                     @"Alpha/Beta:/", true),
			new OneTest(@"Alpha/Beta:/",                     @"Alpha/", false),
			new OneTest(@"http://",                          @"http://", true),
			new OneTest(@"test//",                           @"test//", true),
			new OneTest(@"test/",                            @"", true),
			new OneTest(@"http://www.google.ca",             @"http://", true),
			new OneTest(@"http://www.google.ca/",            @"http://", true),
			new OneTest(@"http://www.google.ca/index.html",  @"http://www.google.ca/", true),
			new OneTest(@"C:\Test",                          @"C:\", true),
			new OneTest(@"C:\A\B",                           @"C:\A\", true),
			new OneTest(@"C:\A\B\",                          @"C:\A\", true),
		};
		
		protected static OneTest[] testsCollapsePath = new OneTest[]
		{
			new OneTest(@"C:\Test",               @"C:\Test"),
			new OneTest(@"\Hello\..",             @"\"),
			new OneTest(@"\Hello\..\",            @"\"),
			new OneTest(@"Hello\..",              @""),
			new OneTest(@"Hello\.",               @"Hello\"),
			new OneTest(@"A\.\B\.\C\",            @"A\B\C\"),
			new OneTest(@"A\..\B\C",              @"B\C"),
			new OneTest(@"\\A\..\B\C",            @"\\B\C"),
			new OneTest(@"http://test/..",        @"http://"),
		};

		public static void DoTests()
		{
			int i;
			string result;
			OneTest t;

			for (i = 0; i < testsGetDriveOrDomain.Length; i++) {
				t = testsGetDriveOrDomain[i];
				result = PathEx.GetDriveOrDomain (t.Path1, t.Flag1, t.Flag2);
				Debug.Assert (result == t.Out);
			}
			
			for (i = 0; i < testsGetRelPath.Length; i++) {
				t = testsGetRelPath[i];
				
				result = PathEx.GetRelativePath (t.Path1, t.Path2, 
					false, t.Flag1, false);
				Debug.Assert (result == t.Out);
				
				result = PathEx.GetRelativePath (t.Path1, t.Path2, 
					true, t.Flag1, false);
				Debug.Assert (result == t.Out2);
			}
			
			for (i = 0; i < testsRemoveLastPath.Length; i++) {
				t = testsRemoveLastPath[i];
				result = PathEx.RemoveLastPath(t.Path1, t.Flag1);
				Debug.Assert (result == t.Out);
			}
			
			for (i = 0; i < testsCollapsePath.Length; i++) {
				t = testsCollapsePath[i];
				result = PathEx.CollapsePath (t.Path1);
				Debug.Assert (result == t.Out);
			}
		}
	}
}