#pragma region CPL License
/*
Nuclex Native Framework
Copyright (C) 2002-2013 Nuclex Development Labs

This library is free software; you can redistribute it and/or
modify it under the terms of the IBM Common Public License as
published by the IBM Corporation; either version 1.0 of the
License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
IBM Common Public License for more details.

You should have received a copy of the IBM Common Public
License along with this library
*/
#pragma endregion // CPL License

#ifndef NUCLEX_STORAGE_FILESYSTEM_PATHHELPER_H
#define NUCLEX_STORAGE_FILESYSTEM_PATHHELPER_H

#include "Nuclex/Storage/Config.h"

#include <string>
#include <cassert>

namespace Nuclex { namespace Storage { namespace FileSystem {

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

  /// <summary>Contains helper methods for working with paths</summary>
  /// <typeparam name="TPathFormat">
  ///   A class describing the platform dependent path format that will be used
  /// </typeparam>
  /// <remarks>
  ///   <para>
  ///     We make some assumptions in this generalization. One assumption is that
  ///     path separators will always consist of 1 ascii character. No UTF-8 characters
  ///     and no multi-character path separators.
  ///   </para>
  ///   <para>
  ///     There are some assumptions we must not make however. Here's a list of things
  ///     that should be taken into account when extending this class:
  ///     <list>
  ///       <item>
  ///          <description>
  ///            Not all platforms have a current working directory. WinRT (Microsoft's new
  ///            Win32 API replacement) does not have one, for example.
  ///          </description>
  ///       </item>
  ///       <item>
  ///          <description>
  ///            Platforms may have multiple valid path separators. Windows prefers the
  ///            backward slash, but most of the time also understands the forward slash.
  ///          </description>
  ///       </item>
  ///       <item>
  ///          <description>
  ///            Not all platforms have a drive letter. Linux simply has a topmost directory
  ///            that maps to some file system and any other file systems (stored on another
  ///            hard drive or a ram disk, for example) can be mapped into directories.
  ///          </description>
  ///       </item>
  ///     </list>
  ///   </para>
  /// </remarks>
  template<typename TPathFormat>
  class PathHelper {

    /// <summary>Determines if the specified character is a path separator</summary>
    /// <param name="character">Character that will be checked for being a path separator</param>
    /// <returns>True if the specified character is a path separator</returns>
    public: static bool IsPathSeparator(char character) {
      return TPathFormat::IsPathSeparator(character);
    }

    /// <summary>Determines whether the specified path ends with a slash</summary>
    /// <param name="path">Path that will be checked for ending with a slash</param>
    /// <returns>True if the path ends with a slash</returns>
    public: static bool HasTrailingPathSeparator(const std::string &path) {
      std::size_t length = path.length();
      if(length > 0) {
        return TPathFormat::IsPathSeparator(path[length - 1]);
      } else {
        return false;
      }
    }

    /// <summary>Removes the trailing slash from a path</summary>
    /// <param name="path">Path from which the trailing slash will be removed</param>
    public: static void RemoveTrailingPathSeparator(std::string &path) {
      std::size_t length = path.length();
      if(length > 0) {
        if(TPathFormat::IsPathSeparator(path[length - 1])) {
          path.resize(length - 1);
        }
      }
    }

    /// <summary>Adds the trailing slash to a path</summary>
    /// <param name="path">Path to which the trailing slash will be added</param>
    public: static void AddTrailingPathSeparator(std::string &path) {
      std::size_t length = path.length();
      if(length > 0) {
        if(!TPathFormat::IsPathSeparator(path[length - 1])) {
          static const char pathSeparatorChars[] = { TPathFormat::PathSeparator, '\0' };
          path.append(pathSeparatorChars, 1);
        }
      }
    }

    /// <summary>Combines a directory with a file name</summary>
    /// <param name="directory">Directory that will be combined</param>
    /// <param name="filename">File name that will be appended to the directory</param>
    /// <returns>The full path of the file</returns>
    public: static std::string CombinePaths(
      const std::string &directory, const std::string &filename
    ) {
      if(TPathFormat::IsAbsolutePath(filename)) {
        return filename;
      } else if(HasTrailingPathSeparator(directory)) {
        return directory + filename;
      } else {
        return directory + TPathFormat::PathSeparator + filename;
      }
    }

    /// <summary>Determines if the specified path is an absolute path</summary>
    /// <param name="path">Path that will be checked</param>
    /// <returns>True if the specified path was an absolute path</returns>
    public: static bool IsAbsolutePath(const std::string &path) {
      return TPathFormat::IsAbsolutePath(path);
    }

    /// <summary>Extracts the last element from a path</summary>
    /// <param name="path">Path from which the last element will be extracted</param>
    /// <returns>The last element of the specified path</returns>
    public: static std::string GetLastPathElement(const std::string &path) {
      std::size_t length = path.length();

      // If the path ends with a path separator, cut it off so that the last element
      // from a path like "/tmp/xyz/" becomes "xyz".
      if(TPathFormat::IsPathSeparator(path[length - 1])) {
        --length;
      }

      // Reverse scan the path for the last separator
      for(std::size_t index = length - 1; index > 0; --index) {
        if(TPathFormat::IsPathSeparator(path[index])) {
          ++index; // Skip the path separator we just found
          return path.substr(index, length - index);
        }
      }

      return path.substr(0, length);
    }

    /// <summary>Removes the last element from a path</summary>
    /// <param name="path">Path from which the last element will be removed</param>
    /// <returns>The specified path minus its last element</returns>
    public: static std::string RemoveLastElement(const std::string &path) {
      std::size_t length = path.length();

      // If the path ends with a path separator, cut it off so that the last element
      // from a path like "/tmp/xyz/" becomes "xyz".
      if(TPathFormat::IsPathSeparator(path[length - 1])) {
        --length;
      }

      // Reverse scan the path for the last separator
      for(std::size_t index = length - 1; index > 0; --index) {
        if(TPathFormat::IsPathSeparator(path[index])) {
          return path.substr(0, index);
        }
      }

      return std::string();
    }

    /// <summary>Turns a relative path into an absolute one</summary>
    /// <param name="basePath">
    ///   Path starting from which the relative path will be resolved
    /// </param>
    /// <param name="relativePath">Relative path that will be resolved</param>
    /// <returns>The absolute path the relative path pointed to</returns>
    public: static std::string MakeAbsolute(
      const std::string &basePath, const std::string &relativePath
    ) {
      std::size_t relativePathLength = relativePath.length();

      // If the relative path is empty, the base path becomes the absolute path
      if(relativePathLength < 1) {
        return basePath;
      }

      // If the relative path starts with a path separator, the user wants
      // to go to the root directory.
      if(TPathFormat::IsPathSeparator(relativePath[0])) {
        std::size_t prefixLength = TPathFormat::GetAbsolutePathPrefixLength(basePath);
        return unwindRelativePath(basePath.substr(0, prefixLength), relativePath.substr(1));
      }

      // The relative path might actually contain an absolute path. In that case,
      // we will discard the base path and return the relative path
      std::size_t prefixLength = TPathFormat::GetAbsolutePathPrefixLength(relativePath);
      if(prefixLength > 0) {

        // If relativePath contains a drive letter, it may be that the path begins
        // at the current working directory (if it is on that drive) or from the root.
        // On non-Windows systems the check will always returns false.
        if(TPathFormat::ContainsDriveLetter(relativePath)) {
          return unwindPathWithDriveLetter(basePath, relativePath);
        }

        // Call unwind in any case so that a relative path like "/tmp/../home/" will be
        // unwound into "/home/".
        return unwindRelativePath(
          relativePath.substr(0, prefixLength), relativePath.substr(prefixLength)
        );

      } // if relative path is absolute

      // The relative path was really relative and didn't contain a drive letter either,
      // so resolve it normally starting from the base path
      return unwindRelativePath(basePath, relativePath);
    }

    /// <summary>Unwinds a relative path pointing to another drive letter</summary>
    /// <param name="basePath">
    ///   Path starting from which the relative path will be resolved
    /// </param>
    /// <param name="relativePath">Relative path that will be resolved</param>
    /// <returns>The absolute path the relative path pointed to</returns>
    /// <remarks>
    ///   This method will only be used on systems that have drive letters (only Windows
    ///   at the time I write this).
    /// </remarks>
    private: static std::string unwindPathWithDriveLetter(
      const std::string &basePath, const std::string &relativePath
    ) {
      using namespace std;

      std::size_t relativePathLength = relativePath.length();
      assert((relativePathLength > 1) && "Relative path has to be at least 2 characters long");

      // If it starts with a drive letter and a path separator it's an absolute path already
      if(relativePathLength > 2) {
        if(TPathFormat::IsPathSeparator(relativePath[2])) {
          return relativePath;
        }
      }

      // Otherwise, if it's on a different drive than the base directory and we need to
      // either start from the root or the current working directory
      if(basePath[0] != relativePath[0]) {

        // If the process' current working basePath is on the drive specified
        // by the relative path, unwind it relative to the working basePath
        if(TPathFormat::HasCurrentWorkingDirectory) {
          std::string workingDirectory = TPathFormat::GetCurrentWorkingDirectory();
          if(workingDirectory.length() > 1) {
            if(workingDirectory[0] == relativePath[0]) {
              return unwindRelativePath(workingDirectory, relativePath.substr(2));
            }
          }
        }

        // The relative path specifies a drive that neither is the reference location
        // nor the current working directory. Start from the root directory on that drive.
        return unwindRelativePath(
          relativePath.substr(0, 2) + TPathFormat::PathSeparator, relativePath.substr(2)
        );

      }

      // The relativ path specifies the same drive as the reference location, so start
      // from the relative path
      return unwindRelativePath(basePath, relativePath.substr(2));
    }

    /// <summary>Unwinds the directory chain of a relative path</summary>
    /// <param name="start">Absolute starting directory to begin unwinding in</param>
    /// <param name="relative">Relative path that will be unwound</param>
    /// <returns>The absolute path the unwinded relative path ended up in</returns>
    /// <remarks>
    ///   If you call this with "c:\test" and "..\data\mooh\..\test" or will return
    ///   "c:\data\test" - basically it removes the ".." and "." in any path. It supports
    ///   any number of dots, so "/tmp/my/invalid/dir/...." would turn into "/tmp".
    /// </remarks>
    private: static std::string unwindRelativePath(
      const std::string &start, const std::string &relative
    ) {
      if(relative.length() == 0) {
        return start;
      }

      // Make sure the start path is valid. This method should be called with start being
      // an absolute path, but that's not a requirement.
      std::string unwound(start);
      if(unwound.length() == 0) {
        unwound = TPathFormat::PathSeparator;
      } else {
        char lastChar = unwound[unwound.length() - 1];
        if(!TPathFormat::IsPathSeparator(lastChar)) {
          unwound += TPathFormat::PathSeparator;
        }
      }

      std::size_t rootPrefixLength = TPathFormat::GetAbsolutePathPrefixLength(unwound);

      // Process the relative path element by element, each time appending the element
      // or going upwards in the path built so far if dots are specified.
      std::size_t startIndex = 0;
      bool terminate = false;
      while(!terminate) {
        std::size_t endIndex;
        for(endIndex = startIndex; endIndex < relative.length(); ++endIndex) {
          if(TPathFormat::IsPathSeparator(relative[endIndex])) {
            break;
          }
        }
        if(endIndex == relative.length()) {
          terminate = true;
        }

        // If this element consists of dots only, it means we need to go upwards
        // in the directory structure. Otherwise, it's a directory or file name.
        std::size_t dotCount = 0;
        for(std::size_t index = startIndex; index < endIndex; ++index) {
          if(relative[index] == '.') {
            ++dotCount;
          } else {
            dotCount = std::string::npos;
            break;
          }
        }

        // Is this a normal path element that needs to be appended?
        if(dotCount == std::string::npos) {
          unwound += relative.substr(startIndex, endIndex - startIndex);
          if(!terminate) {
            unwound += TPathFormat::PathSeparator;
          }
        } else { // Nope, we need to go upwards

          // Locate the point at which we need to cut off the path we built so far
          if(unwound.length() > 0) {
            std::size_t cutOffIndex = unwound.length() - 1;
            for(; cutOffIndex > rootPrefixLength; --cutOffIndex) {
              if(TPathFormat::IsPathSeparator(unwound[cutOffIndex])) {
                --cutOffIndex;
                break;
              }
            }
            while(dotCount > 1) {
              --dotCount;

              // If we're already at the root directory level, discard all dots
              // and stay at this level -- there is no further going up!
              if(cutOffIndex == rootPrefixLength) {
                break;
              }

              for(; cutOffIndex > rootPrefixLength; --cutOffIndex) {
                if(TPathFormat::IsPathSeparator(unwound[cutOffIndex])) {
                  --cutOffIndex;
                  break;
                }
              }
            }

            // Unless there was nothing to cut off (zero or one dots), cut the unwound path off,
            // walking upwards in the directory hierarchy.
            if(cutOffIndex != std::string::npos) {
              unwound = unwound.substr(0, cutOffIndex + 1);
            }
          }

        }

        startIndex = endIndex + 1;
      }

      return unwound;
    }

  };

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

}}} // namespace Nuclex::Storage::FileSystem

#endif // NUCLEX_STORAGE_FILESYSTEM_PATHHELPER_H