#ifndef _FILE_OFFSET_BITS
#define _FILE_OFFSET_BITS 64
#endif
#include <assert.h>
#include <ctype.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include "minivhd/cwalk.h"
/**
 * We try to default to a different path style depending on the operating
 * system. So this should detect whether we should use windows or unix paths.
 */
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
static enum cwk_path_style path_style = CWK_STYLE_WINDOWS;
#else
static enum cwk_path_style path_style = CWK_STYLE_UNIX;
#endif

/**
 * This is a list of separators used in different styles. Windows can read
 * multiple separators, but it generally outputs just a backslash. The output
 * will always use the first character for the output.
 */
static const char *separators[] = {[CWK_STYLE_WINDOWS] = "\\/", [CWK_STYLE_UNIX] = "/"};

/**
 * A joined path represents multiple path strings which are concatenated, but
 * not (necessarily) stored in contiguous memory. The joined path allows to
 * iterate over the segments as if it was one piece of path.
 */
struct cwk_segment_joined {
        struct cwk_segment segment;
        const char **paths;
        size_t path_index;
};

static size_t cwk_path_output_sized(char *buffer, size_t buffer_size, size_t position, const char *str, size_t length) {
        size_t amount_written;

        // First we determine the amount which we can write to the buffer. There are
        // three cases. In the first case we have enough to store the whole string in
        // it. In the second one we can only store a part of it, and in the third we
        // have no space left.
        if (buffer_size > position + length) {
                amount_written = length;
        } else if (buffer_size > position) {
                amount_written = buffer_size - position;
        } else {
                amount_written = 0;
        }

        // If we actually want to write out something we will do that here. We will
        // always append a '\0', this way we are guaranteed to have a valid string at
        // all times.
        if (amount_written > 0) {
                memmove(&buffer[position], str, amount_written);
        }

        // Return the theoretical length which would have been written when everything
        // would have fit in the buffer.
        return length;
}

static size_t cwk_path_output_current(char *buffer, size_t buffer_size, size_t position) {
        // We output a "current" directory, which is a single character. This
        // character is currently not style dependant.
        return cwk_path_output_sized(buffer, buffer_size, position, ".", 1);
}

static size_t cwk_path_output_back(char *buffer, size_t buffer_size, size_t position) {
        // We output a "back" directory, which ahs two characters. This
        // character is currently not style dependant.
        return cwk_path_output_sized(buffer, buffer_size, position, "..", 2);
}

static size_t cwk_path_output_separator(char *buffer, size_t buffer_size, size_t position) {
        // We output a separator, which is a single character.
        return cwk_path_output_sized(buffer, buffer_size, position, separators[path_style], 1);
}

static size_t cwk_path_output_dot(char *buffer, size_t buffer_size, size_t position) {
        // We output a dot, which is a single character. This is used for extensions.
        return cwk_path_output_sized(buffer, buffer_size, position, ".", 1);
}

static size_t cwk_path_output(char *buffer, size_t buffer_size, size_t position, const char *str) {
        size_t length;

        // This just does a sized output internally, but first measuring the
        // null-terminated string.
        length = strlen(str);
        return cwk_path_output_sized(buffer, buffer_size, position, str, length);
}

static void cwk_path_terminate_output(char *buffer, size_t buffer_size, size_t pos) {
        if (buffer_size > 0) {
                if (pos >= buffer_size) {
                        buffer[buffer_size - 1] = '\0';
                } else {
                        buffer[pos] = '\0';
                }
        }
}

static bool cwk_path_is_string_equal(const char *first, const char *second, size_t n) {
        // If the path style is UNIX, we will compare case sensitively. This can be
        // done easily using strncmp.
        if (path_style == CWK_STYLE_UNIX) {
                return strncmp(first, second, n) == 0;
        }

        // However, if this is windows we will have to compare case insensitively.
        // Since there is no standard method to do that we will have to do it on our
        // own.
        while (*first && *second && n > 0) {
                // We can consider the string to be not equal if the two lowercase
                // characters are not equal.
                if (tolower(*first++) != tolower(*second++)) {
                        return false;
                }

                --n;
        }

        // We can consider the string to be equal if we either reached n == 0 or both
        // cursors point to a null character.
        return n == 0 || (*first == '\0' && *second == '\0');
}

static const char *cwk_path_find_next_stop(const char *c) {
        // We just move forward until we find a '\0' or a separator, which will be our
        // next "stop".
        while (*c != '\0' && !cwk_path_is_separator(c)) {
                ++c;
        }

        // Return the pointer of the next stop.
        return c;
}

static const char *cwk_path_find_previous_stop(const char *begin, const char *c) {
        // We just move back until we find a separator or reach the beginning of the
        // path, which will be our previous "stop".
        while (c > begin && !cwk_path_is_separator(c)) {
                --c;
        }

        // Return the pointer to the previous stop. We have to return the first
        // character after the separator, not on the separator itself.
        if (cwk_path_is_separator(c)) {
                return c + 1;
        } else {
                return c;
        }
}

static bool cwk_path_get_first_segment_without_root(const char *path, const char *segments, struct cwk_segment *segment) {
        // Let's remember the path. We will move the path pointer afterwards, that's
        // why this has to be done first.
        segment->path = path;
        segment->segments = segments;

        // Now let's check whether this is an empty string. An empty string has no
        // segment it could use.
        if (*segments == '\0') {
                return false;
        }

        // If the string starts with separators, we will jump over those. If there is
        // only a slash and a '\0' after it, we can't determine the first segment
        // since there is none.
        while (cwk_path_is_separator(segments)) {
                ++segments;
                if (*segments == '\0') {
                        return false;
                }
        }

        // So this is the beginning of our segment.
        segment->begin = segments;

        // Now let's determine the end of the segment, which we do by moving the path
        // pointer further until we find a separator.
        segments = cwk_path_find_next_stop(segments);

        // And finally, calculate the size of the segment by subtracting the position
        // from the end.
        segment->size = segments - segment->begin;
        segment->end = segments;

        // Tell the caller that we found a segment.
        return true;
}

static bool cwk_path_get_last_segment_without_root(const char *path, struct cwk_segment *segment) {
        // Now this is fairly similar to the normal algorithm, however, it will assume
        // that there is no root in the path. So we grab the first segment at this
        // position, assuming there is no root.
        if (!cwk_path_get_first_segment_without_root(path, path, segment)) {
                return false;
        }

        // Now we find our last segment. The segment struct of the caller
        // will contain the last segment, since the function we call here will not
        // change the segment struct when it reaches the end.
        while (cwk_path_get_next_segment(segment)) {
                // We just loop until there is no other segment left.
        }

        return true;
}

static bool cwk_path_get_first_segment_joined(const char **paths, struct cwk_segment_joined *sj) {
        bool result;

        // Prepare the first segment. We position the joined segment on the first path
        // and assign the path array to the struct.
        sj->path_index = 0;
        sj->paths = paths;

        // We loop through all paths until we find one which has a segment. The result
        // is stored in a variable, so we can let the caller know whether we found one
        // or not.
        result = false;
        while (paths[sj->path_index] != NULL &&
               (result = cwk_path_get_first_segment(paths[sj->path_index], &sj->segment)) == false) {
                ++sj->path_index;
        }

        return result;
}

static bool cwk_path_get_next_segment_joined(struct cwk_segment_joined *sj) {
        bool result;

        if (sj->paths[sj->path_index] == NULL) {
                // We reached already the end of all paths, so there is no other segment
                // left.
                return false;
        } else if (cwk_path_get_next_segment(&sj->segment)) {
                // There was another segment on the current path, so we are good to
                // continue.
                return true;
        }

        // We try to move to the next path which has a segment available. We must at
        // least move one further since the current path reached the end.
        result = false;

        do {
                ++sj->path_index;

                // And we obviously have to stop this loop if there are no more paths left.
                if (sj->paths[sj->path_index] == NULL) {
                        break;
                }

                // Grab the first segment of the next path and determine whether this path
                // has anything useful in it. There is one more thing we have to consider
                // here - for the first time we do this we want to skip the root, but
                // afterwards we will consider that to be part of the segments.
                result = cwk_path_get_first_segment_without_root(sj->paths[sj->path_index], sj->paths[sj->path_index],
                                                                 &sj->segment);

        } while (!result);

        // Finally, report the result back to the caller.
        return result;
}

static bool cwk_path_get_previous_segment_joined(struct cwk_segment_joined *sj) {
        bool result;

        if (*sj->paths == NULL) {
                // It's possible that there is no initialized segment available in the
                // struct since there are no paths. In that case we can return false, since
                // there is no previous segment.
                return false;
        } else if (cwk_path_get_previous_segment(&sj->segment)) {
                // Now we try to get the previous segment from the current path. If we can
                // do that successfully, we can let the caller know that we found one.
                return true;
        }

        result = false;

        do {
                // We are done once we reached index 0. In that case there are no more
                // segments left.
                if (sj->path_index == 0) {
                        break;
                }

                // There is another path which we have to inspect. So we decrease the path
                // index.
                --sj->path_index;

                // If this is the first path we will have to consider that this path might
                // include a root, otherwise we just treat is as a segment.
                if (sj->path_index == 0) {
                        result = cwk_path_get_last_segment(sj->paths[sj->path_index], &sj->segment);
                } else {
                        result = cwk_path_get_last_segment_without_root(sj->paths[sj->path_index], &sj->segment);
                }

        } while (!result);

        return result;
}

static bool cwk_path_segment_back_will_be_removed(struct cwk_segment_joined *sj) {
        enum cwk_segment_type type;
        int counter;

        // We are handling back segments here. We must verify how many back segments
        // and how many normal segments come before this one to decide whether we keep
        // or remove it.

        // The counter determines how many normal segments are our current segment,
        // which will popped off before us. If the counter goes above zero it means
        // that our segment will be popped as well.
        counter = 0;

        // We loop over all previous segments until we either reach the beginning,
        // which means our segment will not be dropped or the counter goes above zero.
        while (cwk_path_get_previous_segment_joined(sj)) {

                // Now grab the type. The type determines whether we will increase or
                // decrease the counter. We don't handle a CWK_CURRENT frame here since it
                // has no influence.
                type = cwk_path_get_segment_type(&sj->segment);
                if (type == CWK_NORMAL) {
                        // This is a normal segment. The normal segment will increase the counter
                        // since it neutralizes one back segment. If we go above zero we can
                        // return immediately.
                        ++counter;
                        if (counter > 0) {
                                return true;
                        }
                } else if (type == CWK_BACK) {
                        // A CWK_BACK segment will reduce the counter by one. We can not remove a
                        // back segment as long we are not above zero since we don't have the
                        // opposite normal segment which we would remove.
                        --counter;
                }
        }

        // We never got a count larger than zero, so we will keep this segment alive.
        return false;
}

static bool cwk_path_segment_normal_will_be_removed(struct cwk_segment_joined *sj) {
        enum cwk_segment_type type;
        int counter;

        // The counter determines how many segments are above our current segment,
        // which will popped off before us. If the counter goes below zero it means
        // that our segment will be popped as well.
        counter = 0;

        // We loop over all following segments until we either reach the end, which
        // means our segment will not be dropped or the counter goes below zero.
        while (cwk_path_get_next_segment_joined(sj)) {

                // First, grab the type. The type determines whether we will increase or
                // decrease the counter. We don't handle a CWK_CURRENT frame here since it
                // has no influence.
                type = cwk_path_get_segment_type(&sj->segment);
                if (type == CWK_NORMAL) {
                        // This is a normal segment. The normal segment will increase the counter
                        // since it will be removed by a "../" before us.
                        ++counter;
                } else if (type == CWK_BACK) {
                        // A CWK_BACK segment will reduce the counter by one. If we are below zero
                        // we can return immediately.
                        --counter;
                        if (counter < 0) {
                                return true;
                        }
                }
        }

        // We never got a negative count, so we will keep this segment alive.
        return false;
}

static bool cwk_path_segment_will_be_removed(const struct cwk_segment_joined *sj, bool absolute) {
        enum cwk_segment_type type;
        struct cwk_segment_joined sjc;

        // We copy the joined path so we don't need to modify it.
        sjc = *sj;

        // First we check whether this is a CWK_CURRENT or CWK_BACK segment, since
        // those will always be dropped.
        type = cwk_path_get_segment_type(&sj->segment);
        if (type == CWK_CURRENT) {
                return true;
        } else if (type == CWK_BACK && absolute) {
                return true;
        } else if (type == CWK_BACK) {
                return cwk_path_segment_back_will_be_removed(&sjc);
        } else {
                return cwk_path_segment_normal_will_be_removed(&sjc);
        }
}

static bool cwk_path_segment_joined_skip_invisible(struct cwk_segment_joined *sj, bool absolute) {
        while (cwk_path_segment_will_be_removed(sj, absolute)) {
                if (!cwk_path_get_next_segment_joined(sj)) {
                        return false;
                }
        }

        return true;
}

static void cwk_path_get_root_windows(const char *path, size_t *length) {
        const char *c;
        bool is_device_path;

        // A device path is a path which starts with "\\." or "\\?". A device path can
        // be a UNC path as well, in which case it will take up one more segment.
        is_device_path = false;

        // We can not determine the root if this is an empty string. So we set the
        // root to NULL and the length to zero and cancel the whole thing.
        c = path;
        *length = 0;
        if (!*c) {
                return;
        }

        // Now we have to verify whether this is a windows network path (UNC), which
        // we will consider our root.
        if (cwk_path_is_separator(c)) {
                ++c;

                // Check whether the path starts with a single back slash, which means this
                // is not a network path - just a normal path starting with a backslash.
                if (!cwk_path_is_separator(c)) {
                        // Okay, this is not a network path but we still use the backslash as a
                        // root.
                        ++(*length);
                        return;
                }

                // Yes, this is a network or device path. Skip the previous separator. Now
                // we need to determine whether this is a device path. We might advance one
                // character here if the server name starts with a '?' or a '.', but that's
                // fine since we will search for a separator afterwards anyway.
                ++c;
                is_device_path = (*c == '?' || *c == '.') && cwk_path_is_separator(++c);
                if (is_device_path) {
                        // That's a device path, and the root must be either "\\.\" or "\\?\"
                        // which is 4 characters long. (at least that's how Windows
                        // GetFullPathName behaves.)
                        *length = 4;
                        return;
                }

                // We will grab anything up to the next stop. The next top might be a '\0'
                // or another separator. That will be the server name.
                c = cwk_path_find_next_stop(c);

                // If this is a separator and not the end of a string we wil have to include
                // it. However, if this is a '\0' we must not skip it.
                while (cwk_path_is_separator(c)) {
                        ++c;
                }

                // We are now skipping the shared folder name, which will end after the
                // next stop.
                c = cwk_path_find_next_stop(c);

                // Then there might be a separator at the end. We will include that as well,
                // it will mark the path as absolute.
                if (cwk_path_is_separator(c)) {
                        ++c;
                }

                // Finally, calculate the size of the root.
                *length = c - path;
                return;
        }

        // Move to the next and check whether this is a colon.
        if (*++c == ':') {
                *length = 2;

                // Now check whether this is a backslash (or slash). If it is not, we could
                // assume that the next character is a '\0' if it is a valid path. However,
                // we will not assume that - since ':' is not valid in a path it must be a
                // mistake by the caller than. We will try to understand it anyway.
                if (cwk_path_is_separator(++c)) {
                        *length = 3;
                }
        }
}

static void cwk_path_get_root_unix(const char *path, size_t *length) {
        // The slash of the unix path represents the root. There is no root if there
        // is no slash.
        if (cwk_path_is_separator(path)) {
                *length = 1;
        } else {
                *length = 0;
        }
}

static bool cwk_path_is_root_absolute(const char *path, size_t length) {
        // This is definitely not absolute if there is no root.
        if (length == 0) {
                return false;
        }

        // If there is a separator at the end of the root, we can safely consider this
        // to be an absolute path.
        return cwk_path_is_separator(&path[length - 1]);
}

static size_t cwk_path_join_and_normalize_multiple(const char **paths, char *buffer, size_t buffer_size) {
        size_t pos;
        bool absolute, has_segment_output;
        struct cwk_segment_joined sj;

        // We initialize the position after the root, which should get us started.
        cwk_path_get_root(paths[0], &pos);

        // Determine whether the path is absolute or not. We need that to determine
        // later on whether we can remove superfluous "../" or not.
        absolute = cwk_path_is_root_absolute(paths[0], pos);

        // First copy the root to the output. We will not modify the root.
        cwk_path_output_sized(buffer, buffer_size, 0, paths[0], pos);

        // So we just grab the first segment. If there is no segment we will always
        // output a "/", since we currently only support absolute paths here.
        if (!cwk_path_get_first_segment_joined(paths, &sj)) {
                goto done;
        }

        // Let's assume that we don't have any segment output for now. We will toggle
        // this flag once there is some output.
        has_segment_output = false;

        do {
                // Check whether we have to drop this segment because of resolving a
                // relative path or because it is a CWK_CURRENT segment.
                if (cwk_path_segment_will_be_removed(&sj, absolute)) {
                        continue;
                }

                // Remember that we have segment output, so we can handle the trailing slash
                // later on. This is necessary since we might have segments but they are all
                // removed.
                has_segment_output = true;

                // Write out the segment but keep in mind that we need to follow the
                // buffer size limitations. That's why we use the path output functions
                // here.
                pos += cwk_path_output_sized(buffer, buffer_size, pos, sj.segment.begin, sj.segment.size);
                pos += cwk_path_output_separator(buffer, buffer_size, pos);
        } while (cwk_path_get_next_segment_joined(&sj));

        // Remove the trailing slash, but only if we have segment output. We don't
        // want to remove anything from the root.
        if (has_segment_output) {
                --pos;
        } else if (pos == 0) {
                // This may happen if the path is absolute and all segments have been
                // removed. We can not have an empty output - and empty output means we stay
                // in the current directory. So we will output a ".".
                assert(absolute == false);
                pos += cwk_path_output_current(buffer, buffer_size, pos);
        }

        // We must append a '\0' in any case, unless the buffer size is zero. If the
        // buffer size is zero, which means we can not.
done:
        cwk_path_terminate_output(buffer, buffer_size, pos);

        // And finally let our caller know about the total size of the normalized
        // path.
        return pos;
}

size_t cwk_path_get_absolute(const char *base, const char *path, char *buffer, size_t buffer_size) {
        size_t i;
        const char *paths[4];

        // The basename should be an absolute path if the caller is using the API
        // correctly. However, he might not and in that case we will append a fake
        // root at the beginning.
        if (cwk_path_is_absolute(base)) {
                i = 0;
        } else {
                paths[0] = "/";
                i = 1;
        }

        if (cwk_path_is_absolute(path)) {
                // If the submitted path is not relative the base path becomes irrelevant.
                // We will only normalize the submitted path instead.
                paths[i++] = path;
                paths[i] = NULL;
        } else {
                // Otherwise we append the relative path to the base path and normalize it.
                // The result will be a new absolute path.
                paths[i++] = base;
                paths[i++] = path;
                paths[i] = NULL;
        }

        // Finally join everything together and normalize it.
        return cwk_path_join_and_normalize_multiple(paths, buffer, buffer_size);
}

static void cwk_path_skip_segments_until_diverge(struct cwk_segment_joined *bsj, struct cwk_segment_joined *osj, bool absolute,
                                                 bool *base_available, bool *other_available) {
        // Now looping over all segments until they start to diverge. A path may
        // diverge if two segments are not equal or if one path reaches the end.
        do {

                // Check whether there is anything available after we skip everything which
                // is invisible. We do that for both paths, since we want to let the caller
                // know which path has some trailing segments after they diverge.
                *base_available = cwk_path_segment_joined_skip_invisible(bsj, absolute);
                *other_available = cwk_path_segment_joined_skip_invisible(osj, absolute);

                // We are done if one or both of those paths reached the end. They either
                // diverge or both reached the end - but in both cases we can not continue
                // here.
                if (!*base_available || !*other_available) {
                        break;
                }

                // Compare the content of both segments. We are done if they are not equal,
                // since they diverge.
                if (!cwk_path_is_string_equal(bsj->segment.begin, osj->segment.begin, bsj->segment.size)) {
                        break;
                }

                // We keep going until one of those segments reached the end. The next
                // segment might be invisible, but we will check for that in the beginning
                // of the loop once again.
                *base_available = cwk_path_get_next_segment_joined(bsj);
                *other_available = cwk_path_get_next_segment_joined(osj);
        } while (*base_available && *other_available);
}

size_t cwk_path_get_relative(const char *base_directory, const char *path, char *buffer, size_t buffer_size) {
        size_t pos, base_root_length, path_root_length;
        bool absolute, base_available, other_available, has_output;
        const char *base_paths[2], *other_paths[2];
        struct cwk_segment_joined bsj, osj;

        pos = 0;

        // First we compare the roots of those two paths. If the roots are not equal
        // we can't continue, since there is no way to get a relative path from
        // different roots.
        cwk_path_get_root(base_directory, &base_root_length);
        cwk_path_get_root(path, &path_root_length);
        if (!cwk_path_is_string_equal(base_directory, path, base_root_length)) {
                return pos;
        }

        // Verify whether this is an absolute path. We need to know that since we can
        // remove all back-segments if it is.
        absolute = cwk_path_is_root_absolute(base_directory, base_root_length);

        // Initialize our joined segments. This will allow us to use the internal
        // functions to skip until diverge and invisible. We only have one path in
        // them though.
        base_paths[0] = base_directory;
        base_paths[1] = NULL;
        other_paths[0] = path;
        other_paths[1] = NULL;
        cwk_path_get_first_segment_joined(base_paths, &bsj);
        cwk_path_get_first_segment_joined(other_paths, &osj);

        // Okay, now we skip until the segments diverge. We don't have anything to do
        // with the segments which are equal.
        cwk_path_skip_segments_until_diverge(&bsj, &osj, absolute, &base_available, &other_available);

        // Assume there is no output until we have got some. We will need this
        // information later on to remove trailing slashes or alternatively output a
        // current-segment.
        has_output = false;

        // So if we still have some segments left in the base path we will now output
        // a back segment for all of them.
        if (base_available) {
                do {
                        // Skip any invisible segment. We don't care about those and we don't need
                        // to navigate back because of them.
                        if (!cwk_path_segment_joined_skip_invisible(&bsj, absolute)) {
                                break;
                        }

                        // Toggle the flag if we have output. We need to remember that, since we
                        // want to remove the trailing slash.
                        has_output = true;

                        // Output the back segment and a separator. No need to worry about the
                        // superfluous segment since it will be removed later on.
                        pos += cwk_path_output_back(buffer, buffer_size, pos);
                        pos += cwk_path_output_separator(buffer, buffer_size, pos);
                } while (cwk_path_get_next_segment_joined(&bsj));
        }

        // And if we have some segments available of the target path we will output
        // all of those.
        if (other_available) {
                do {
                        // Again, skip any invisible segments since we don't need to navigate into
                        // them.
                        if (!cwk_path_segment_joined_skip_invisible(&osj, absolute)) {
                                break;
                        }

                        // Toggle the flag if we have output. We need to remember that, since we
                        // want to remove the trailing slash.
                        has_output = true;

                        // Output the current segment and a separator. No need to worry about the
                        // superfluous segment since it will be removed later on.
                        pos += cwk_path_output_sized(buffer, buffer_size, pos, osj.segment.begin, osj.segment.size);
                        pos += cwk_path_output_separator(buffer, buffer_size, pos);
                } while (cwk_path_get_next_segment_joined(&osj));
        }

        // If we have some output by now we will have to remove the trailing slash. We
        // simply do that by moving back one character. The terminate output function
        // will then place the '\0' on this position. Otherwise, if there is no
        // output, we will have to output a "current directory", since the target path
        // points to the base path.
        if (has_output) {
                --pos;
        } else {
                pos += cwk_path_output_current(buffer, buffer_size, pos);
        }

        // Finally, we can terminate the output - which means we place a '\0' at the
        // current position or at the end of the buffer.
        cwk_path_terminate_output(buffer, buffer_size, pos);

        return pos;
}

size_t cwk_path_join(const char *path_a, const char *path_b, char *buffer, size_t buffer_size) {
        const char *paths[3];

        // This is simple. We will just create an array with the two paths which we
        // wish to join.
        paths[0] = path_a;
        paths[1] = path_b;
        paths[2] = NULL;

        // And then call the join and normalize function which will do the hard work
        // for us.
        return cwk_path_join_and_normalize_multiple(paths, buffer, buffer_size);
}

size_t cwk_path_join_multiple(const char **paths, char *buffer, size_t buffer_size) {
        // We can just call the internal join and normalize function for this one,
        // since it will handle everything.
        return cwk_path_join_and_normalize_multiple(paths, buffer, buffer_size);
}

void cwk_path_get_root(const char *path, size_t *length) {
        // We use a different implementation here based on the configuration of the
        // library.
        if (path_style == CWK_STYLE_WINDOWS) {
                cwk_path_get_root_windows(path, length);
        } else {
                cwk_path_get_root_unix(path, length);
        }
}

size_t cwk_path_change_root(const char *path, const char *new_root, char *buffer, size_t buffer_size) {
        const char *tail;
        size_t root_length, path_length, tail_length, new_root_length, new_path_size;

        // First we need to determine the actual size of the root which we will
        // change.
        cwk_path_get_root(path, &root_length);

        // Now we determine the sizes of the new root and the path. We need that to
        // determine the size of the part after the root (the tail).
        new_root_length = strlen(new_root);
        path_length = strlen(path);

        // Okay, now we calculate the position of the tail and the length of it.
        tail = path + root_length;
        tail_length = path_length - root_length;

        // We first output the tail and then the new root, that's because the source
        // path and the buffer may be overlapping. This way the root will not
        // overwrite the tail.
        cwk_path_output_sized(buffer, buffer_size, new_root_length, tail, tail_length);
        cwk_path_output_sized(buffer, buffer_size, 0, new_root, new_root_length);

        // Finally we calculate the size o the new path and terminate the output with
        // a '\0'.
        new_path_size = tail_length + new_root_length;
        cwk_path_terminate_output(buffer, buffer_size, new_path_size);

        return new_path_size;
}

bool cwk_path_is_absolute(const char *path) {
        size_t length;

        // We grab the root of the path. This root does not include the first
        // separator of a path.
        cwk_path_get_root(path, &length);

        // Now we can determine whether the root is absolute or not.
        return cwk_path_is_root_absolute(path, length);
}

bool cwk_path_is_relative(const char *path) {
        // The path is relative if it is not absolute.
        return !cwk_path_is_absolute(path);
}

void cwk_path_get_basename(const char *path, const char **basename, size_t *length) {
        struct cwk_segment segment;

        // We get the last segment of the path. The last segment will contain the
        // basename if there is any. If there are no segments we will set the basename
        // to NULL and the length to 0.
        if (!cwk_path_get_last_segment(path, &segment)) {
                *basename = NULL;
                *length = 0;
                return;
        }

        // Now we can just output the segment contents, since that's our basename.
        // There might be trailing separators after the basename, but the size does
        // not include those.
        *basename = segment.begin;
        *length = segment.size;
}

size_t cwk_path_change_basename(const char *path, const char *new_basename, char *buffer, size_t buffer_size) {
        struct cwk_segment segment;
        size_t pos, root_size, new_basename_size;

        // First we try to get the last segment. We may only have a root without any
        // segments, in which case we will create one.
        if (!cwk_path_get_last_segment(path, &segment)) {

                // So there is no segment in this path. First we grab the root and output
                // that. We are not going to modify the root in any way.
                cwk_path_get_root(path, &root_size);
                pos = cwk_path_output_sized(buffer, buffer_size, 0, path, root_size);

                // We have to trim the separators from the beginning of the new basename.
                // This is quite easy to do.
                while (cwk_path_is_separator(new_basename)) {
                        ++new_basename;
                }

                // Now we measure the length of the new basename, this is a two step
                // process. First we find the '\0' character at the end of the string.
                new_basename_size = 0;
                while (new_basename[new_basename_size]) {
                        ++new_basename_size;
                }

                // And then we trim the separators at the end of the basename until we reach
                // the first valid character.
                while (new_basename_size > 0 && cwk_path_is_separator(&new_basename[new_basename_size - 1])) {
                        --new_basename_size;
                }

                // Now we will output the new basename after the root.
                pos += cwk_path_output_sized(buffer, buffer_size, pos, new_basename, new_basename_size);

                // And finally terminate the output and return the total size of the path.
                cwk_path_terminate_output(buffer, buffer_size, pos);
                return pos;
        }

        // If there is a last segment we can just forward this call, which is fairly
        // easy.
        return cwk_path_change_segment(&segment, new_basename, buffer, buffer_size);
}

void cwk_path_get_dirname(const char *path, size_t *length) {
        struct cwk_segment segment;

        // We get the last segment of the path. The last segment will contain the
        // basename if there is any. If there are no segments we will set the length
        // to 0.
        if (!cwk_path_get_last_segment(path, &segment)) {
                *length = 0;
                return;
        }

        // We can now return the length from the beginning of the string up to the
        // beginning of the last segment.
        *length = segment.begin - path;
}

bool cwk_path_get_extension(const char *path, const char **extension, size_t *length) {
        struct cwk_segment segment;
        const char *c;

        // We get the last segment of the path. The last segment will contain the
        // extension if there is any.
        if (!cwk_path_get_last_segment(path, &segment)) {
                return false;
        }

        // Now we search for a dot within the segment. If there is a dot, we consider
        // the rest of the segment the extension. We do this from the end towards the
        // beginning, since we want to find the last dot.
        for (c = segment.end; c >= segment.begin; --c) {
                if (*c == '.') {
                        // Okay, we found an extension. We can stop looking now.
                        *extension = c;
                        *length = segment.end - c;
                        return true;
                }
        }

        // We couldn't find any extension.
        return false;
}

bool cwk_path_has_extension(const char *path) {
        const char *extension;
        size_t length;

        // We just wrap the get_extension call which will then do the work for us.
        return cwk_path_get_extension(path, &extension, &length);
}

size_t cwk_path_change_extension(const char *path, const char *new_extension, char *buffer, size_t buffer_size) {
        struct cwk_segment segment;
        const char *c, *old_extension;
        size_t pos, root_size, trail_size, new_extension_size;

        // First we try to get the last segment. We may only have a root without any
        // segments, in which case we will create one.
        if (!cwk_path_get_last_segment(path, &segment)) {

                // So there is no segment in this path. First we grab the root and output
                // that. We are not going to modify the root in any way. If there is no
                // root, this will end up with a root size 0, and nothing will be written.
                cwk_path_get_root(path, &root_size);
                pos = cwk_path_output_sized(buffer, buffer_size, 0, path, root_size);

                // Add a dot if the submitted value doesn't have any.
                if (*new_extension != '.') {
                        pos += cwk_path_output_dot(buffer, buffer_size, pos);
                }

                // And finally terminate the output and return the total size of the path.
                pos += cwk_path_output(buffer, buffer_size, pos, new_extension);
                cwk_path_terminate_output(buffer, buffer_size, pos);
                return pos;
        }

        // Now we seek the old extension in the last segment, which we will replace
        // with the new one. If there is no old extension, it will point to the end of
        // the segment.
        old_extension = segment.end;
        for (c = segment.begin; c < segment.end; ++c) {
                if (*c == '.') {
                        old_extension = c;
                }
        }

        pos = cwk_path_output_sized(buffer, buffer_size, 0, segment.path, old_extension - segment.path);

        // If the new extension starts with a dot, we will skip that dot. We always
        // output exactly one dot before the extension. If the extension contains
        // multiple dots, we will output those as part of the extension.
        if (*new_extension == '.') {
                ++new_extension;
        }

        // We calculate the size of the new extension, including the dot, in order to
        // output the trail - which is any part of the path coming after the
        // extension. We must output this first, since the buffer may overlap with the
        // submitted path - and it would be overridden by longer extensions.
        new_extension_size = strlen(new_extension) + 1;
        trail_size = cwk_path_output(buffer, buffer_size, pos + new_extension_size, segment.end);

        // Finally we output the dot and the new extension. The new extension itself
        // doesn't contain the dot anymore, so we must output that first.
        pos += cwk_path_output_dot(buffer, buffer_size, pos);
        pos += cwk_path_output(buffer, buffer_size, pos, new_extension);

        // Now we terminate the output with a null-terminating character, but before
        // we do that we must add the size of the trail to the position which we
        // output before.
        pos += trail_size;
        cwk_path_terminate_output(buffer, buffer_size, pos);

        // And the position is our output size now.
        return pos;
}

size_t cwk_path_normalize(const char *path, char *buffer, size_t buffer_size) {
        const char *paths[2];

        // Now we initialize the paths which we will normalize. Since this function
        // only supports submitting a single path, we will only add that one.
        paths[0] = path;
        paths[1] = NULL;

        return cwk_path_join_and_normalize_multiple(paths, buffer, buffer_size);
}

size_t cwk_path_get_intersection(const char *path_base, const char *path_other) {
        bool absolute;
        size_t base_root_length, other_root_length;
        const char *end;
        const char *paths_base[2], *paths_other[2];
        struct cwk_segment_joined base, other;

        // We first compare the two roots. We just return zero if they are not equal.
        // This will also happen to return zero if the paths are mixed relative and
        // absolute.
        cwk_path_get_root(path_base, &base_root_length);
        cwk_path_get_root(path_other, &other_root_length);
        if (!cwk_path_is_string_equal(path_base, path_other, base_root_length)) {
                return 0;
        }

        // Configure our paths. We just have a single path in here for now.
        paths_base[0] = path_base;
        paths_base[1] = NULL;
        paths_other[0] = path_other;
        paths_other[1] = NULL;

        // So we get the first segment of both paths. If one of those paths don't have
        // any segment, we will return 0.
        if (!cwk_path_get_first_segment_joined(paths_base, &base) || !cwk_path_get_first_segment_joined(paths_other, &other)) {
                return base_root_length;
        }

        // We now determine whether the path is absolute or not. This is required
        // because if will ignore removed segments, and this behaves differently if
        // the path is absolute. However, we only need to check the base path because
        // we are guaranteed that both paths are either relative or absolute.
        absolute = cwk_path_is_root_absolute(path_base, base_root_length);

        // We must keep track of the end of the previous segment. Initially, this is
        // set to the beginning of the path. This means that 0 is returned if the
        // first segment is not equal.
        end = path_base + base_root_length;

        // Now we loop over both segments until one of them reaches the end or their
        // contents are not equal.
        do {
                // We skip all segments which will be removed in each path, since we want to
                // know about the true path.
                if (!cwk_path_segment_joined_skip_invisible(&base, absolute) ||
                    !cwk_path_segment_joined_skip_invisible(&other, absolute)) {
                        break;
                }

                if (!cwk_path_is_string_equal(base.segment.begin, other.segment.begin, base.segment.size)) {
                        // So the content of those two segments are not equal. We will return the
                        // size up to the beginning.
                        return end - path_base;
                }

                // Remember the end of the previous segment before we go to the next one.
                end = base.segment.end;
        } while (cwk_path_get_next_segment_joined(&base) && cwk_path_get_next_segment_joined(&other));

        // Now we calculate the length up to the last point where our paths pointed to
        // the same place.
        return end - path_base;
}

bool cwk_path_get_first_segment(const char *path, struct cwk_segment *segment) {
        size_t length;
        const char *segments;

        // We skip the root since that's not part of the first segment. The root is
        // treated as a separate entity.
        cwk_path_get_root(path, &length);
        segments = path + length;

        // Now, after we skipped the root we can continue and find the actual segment
        // content.
        return cwk_path_get_first_segment_without_root(path, segments, segment);
}

bool cwk_path_get_last_segment(const char *path, struct cwk_segment *segment) {
        // We first grab the first segment. This might be our last segment as well,
        // but we don't know yet. There is no last segment if there is no first
        // segment, so we return false in that case.
        if (!cwk_path_get_first_segment(path, segment)) {
                return false;
        }

        // Now we find our last segment. The segment struct of the caller
        // will contain the last segment, since the function we call here will not
        // change the segment struct when it reaches the end.
        while (cwk_path_get_next_segment(segment)) {
                // We just loop until there is no other segment left.
        }

        return true;
}

bool cwk_path_get_next_segment(struct cwk_segment *segment) {
        const char *c;

        // First we jump to the end of the previous segment. The first character must
        // be either a '\0' or a separator.
        c = segment->begin + segment->size;
        if (*c == '\0') {
                return false;
        }

        // Now we skip all separator until we reach something else. We are not yet
        // guaranteed to have a segment, since the string could just end afterwards.
        assert(cwk_path_is_separator(c));
        do {
                ++c;
        } while (cwk_path_is_separator(c));

        // If the string ends here, we can safely assume that there is no other
        // segment after this one.
        if (*c == '\0') {
                return false;
        }

        // Now we are safe to assume there is a segment. We store the beginning of
        // this segment in the segment struct of the caller.
        segment->begin = c;

        // And now determine the size of this segment, and store it in the struct of
        // the caller as well.
        c = cwk_path_find_next_stop(c);
        segment->end = c;
        segment->size = c - segment->begin;

        // Tell the caller that we found a segment.
        return true;
}

bool cwk_path_get_previous_segment(struct cwk_segment *segment) {
        const char *c;

        // The current position might point to the first character of the path, which
        // means there are no previous segments available.
        c = segment->begin;
        if (c <= segment->segments) {
                return false;
        }

        // We move towards the beginning of the path until we either reached the
        // beginning or the character is no separator anymore.
        do {
                --c;
                if (c <= segment->segments) {
                        // So we reached the beginning here and there is no segment. So we return
                        // false and don't change the segment structure submitted by the caller.
                        return false;
                }
        } while (cwk_path_is_separator(c));

        // We are guaranteed now that there is another segment, since we moved before
        // the previous separator and did not reach the segment path beginning.
        segment->end = c + 1;
        segment->begin = cwk_path_find_previous_stop(segment->segments, c);
        segment->size = segment->end - segment->begin;

        return true;
}

enum cwk_segment_type cwk_path_get_segment_type(const struct cwk_segment *segment) {
        // We just make a string comparison with the segment contents and return the
        // appropriate type.
        if (strncmp(segment->begin, ".", segment->size) == 0) {
                return CWK_CURRENT;
        } else if (strncmp(segment->begin, "..", segment->size) == 0) {
                return CWK_BACK;
        }

        return CWK_NORMAL;
}

bool cwk_path_is_separator(const char *str) {
        const char *c;

        // We loop over all characters in the read symbols.
        c = separators[path_style];
        while (*c) {
                if (*c == *str) {
                        return true;
                }

                ++c;
        }

        return false;
}

size_t cwk_path_change_segment(struct cwk_segment *segment, const char *value, char *buffer, size_t buffer_size) {
        size_t pos, value_size, tail_size;

        // First we have to output the head, which is the whole string up to the
        // beginning of the segment. This part of the path will just stay the same.
        pos = cwk_path_output_sized(buffer, buffer_size, 0, segment->path, segment->begin - segment->path);

        // In order to trip the submitted value, we will skip any separator at the
        // beginning of it and behave as if it was never there.
        while (cwk_path_is_separator(value)) {
                ++value;
        }

        // Now we determine the length of the value. In order to do that we first
        // locate the '\0'.
        value_size = 0;
        while (value[value_size]) {
                ++value_size;
        }

        // Since we trim separators at the beginning and in the end of the value we
        // have to subtract from the size until there are either no more characters
        // left or the last character is no separator.
        while (value_size > 0 && cwk_path_is_separator(&value[value_size - 1])) {
                --value_size;
        }

        // We also have to determine the tail size, which is the part of the string
        // following the current segment. This part will not change.
        tail_size = strlen(segment->end);

        // Now we output the tail. We have to do that, because if the buffer and the
        // source are overlapping we would override the tail if the value is
        // increasing in length.
        cwk_path_output_sized(buffer, buffer_size, pos + value_size, segment->end, tail_size);

        // Finally we can output the value in the middle of the head and the tail,
        // where we have enough space to fit the whole trimmed value.
        pos += cwk_path_output_sized(buffer, buffer_size, pos, value, value_size);

        // Now we add the tail size to the current position and terminate the output -
        // basically, ensure that there is a '\0' at the end of the buffer.
        pos += tail_size;
        cwk_path_terminate_output(buffer, buffer_size, pos);

        // And now tell the caller how long the whole path would be.
        return pos;
}

enum cwk_path_style cwk_path_guess_style(const char *path) {
        const char *c;
        size_t root_length;
        struct cwk_segment segment;

        // First we determine the root. Only windows roots can be longer than a single
        // slash, so if we can determine that it starts with something like "C:", we
        // know that this is a windows path.
        cwk_path_get_root_windows(path, &root_length);
        if (root_length > 1) {
                return CWK_STYLE_WINDOWS;
        }

        // Next we check for slashes. Windows uses backslashes, while unix uses
        // forward slashes. Windows actually supports both, but our best guess is to
        // assume windows with backslashes and unix with forward slashes.
        for (c = path; *c; ++c) {
                if (*c == *separators[CWK_STYLE_UNIX]) {
                        return CWK_STYLE_UNIX;
                } else if (*c == *separators[CWK_STYLE_WINDOWS]) {
                        return CWK_STYLE_WINDOWS;
                }
        }

        // This path does not have any slashes. We grab the last segment (which
        // actually must be the first one), and determine whether the segment starts
        // with a dot. A dot is a hidden folder or file in the UNIX world, in that
        // case we assume the path to have UNIX style.
        if (!cwk_path_get_last_segment(path, &segment)) {
                // We couldn't find any segments, so we default to a UNIX path style since
                // there is no way to make any assumptions.
                return CWK_STYLE_UNIX;
        }

        if (*segment.begin == '.') {
                return CWK_STYLE_UNIX;
        }

        // And finally we check whether the last segment contains a dot. If it
        // contains a dot, that might be an extension. Windows is more likely to have
        // file names with extensions, so our guess would be windows.
        for (c = segment.begin; *c; ++c) {
                if (*c == '.') {
                        return CWK_STYLE_WINDOWS;
                }
        }

        // All our checks failed, so we will return a default value which is currently
        // UNIX.
        return CWK_STYLE_UNIX;
}

void cwk_path_set_style(enum cwk_path_style style) {
        // We can just set the global path style variable and then the behaviour for
        // all functions will change accordingly.
        assert(style == CWK_STYLE_UNIX || style == CWK_STYLE_WINDOWS);
        path_style = style;
}

enum cwk_path_style cwk_path_get_style(void) {
        // Simply return the path style which we store in a global variable.
        return path_style;
}
