NatSort.hpp

/*
	The MIT License (MIT)
	Copyright (c) 2016 Gagan Kumar(scopeInfinity)
	Complete License at https://raw.githubusercontent.com/scopeInfinity/NaturalSort/master/LICENSE.md
*/

/**********************************************************************
Calling Methods :
	//For Natural Sorting
	void SI::natural::sort(Container<String>);
	void SI::natural::sort(IteratorBegin<String>,IteratorEnd<String>);
	void SI::natural::sort<String,CArraySize>(CArray<String>);
	//For Natural Comparision
	bool SI::natural::compare<String>(String lhs,String rhs);
	bool SI::natural::compare<String>(char *const lhs,char *const rhs);
	Here we can have
		std::vector<std::string> 	as Container<String>
		String 						as std::string
		CArray<String>				as std::string[CArraySize]
***********************************************************************/
#ifndef SI_sort_HPP
#define SI_sort_HPP
#include <cctype>
#include <algorithm>
#include <vector>


namespace SI
{
	namespace natural
	{
		namespace detail
		{
			/********** Compare Two Character CaseInsensitive ********/
			template<typename ElementType>
			bool natural_less(const ElementType& lhs, const ElementType& rhs)
			{
				if (tolower(lhs) < tolower(rhs))
					return true;
				return false;
			}

			template<typename ElementType>
			bool is_not_digit(const ElementType& x)
			{
				return !isdigit(x);
			}

			/********** Compare Two Iterators CaseInsensitive ********/
			template<typename ElementType, typename Iterator>
			struct comp_over_iterator
			{
				int operator()(const Iterator& lhs, const Iterator& rhs) const
				{
					if (natural_less<ElementType>(*lhs, *rhs))
						return -1;
					if (natural_less<ElementType>(*rhs, *lhs))
						return +1;
					return 0;
				}
			};

			/****************************************************
			Comparing two SubString from (Begin,End Iterator each)
			with only digits.
			Usage :
				int compare_number()(\
				FirstNumberBeginIterator,FirstNumberEndIterator,isFirstNumberFractionalPart\
				SecondNumberBeginIterator,SecondNumberEndIterator,isSecondNumberFractionalPart\
				);
			Returns :
				-1  - Number1  <   Number2
				 0  - Number1  ==  Number2
				 1  - Number1  >   Number2
			***************************************************/


			template<typename ValueType, typename Iterator>
			struct compare_number
			{
			private:
				//If Number is Itself fractional Part
				int fractional(Iterator lhsBegin, Iterator lhsEnd, Iterator rhsBegin, Iterator rhsEnd)
				{
					while (lhsBegin < lhsEnd && rhsBegin < rhsEnd)
					{
						int local_compare = comp_over_iterator<ValueType, Iterator>()(lhsBegin, rhsBegin);
						if (local_compare != 0)
							return local_compare;
						lhsBegin++;
						rhsBegin++;
					}
					while (lhsBegin < lhsEnd && *lhsBegin == '0') lhsBegin++;
					while (rhsBegin < rhsEnd && *rhsBegin == '0') rhsBegin++;
					if (lhsBegin == lhsEnd && rhsBegin != rhsEnd)
						return -1;
					else if (lhsBegin != lhsEnd && rhsBegin == rhsEnd)
						return +1;
					else //lhsBegin==lhsEnd && rhsBegin==rhsEnd
						return 0;
				}
				int non_fractional(Iterator lhsBegin, Iterator lhsEnd, Iterator rhsBegin, Iterator rhsEnd)
				{
					//Skip Inital Zero's
					while (lhsBegin < lhsEnd && *lhsBegin == '0') lhsBegin++;
					while (rhsBegin < rhsEnd && *rhsBegin == '0') rhsBegin++;

					//Comparing By Length of Both String
					if (lhsEnd - lhsBegin < rhsEnd - rhsBegin)
						return -1;
					if (lhsEnd - lhsBegin > rhsEnd - rhsBegin)
						return +1;

					//Equal In length
					while (lhsBegin < lhsEnd)
					{
						int local_compare = comp_over_iterator<ValueType, Iterator>()(lhsBegin, rhsBegin);
						if (local_compare != 0)
							return local_compare;
						lhsBegin++;
						rhsBegin++;
					}
					return 0;
				}


			public:
				int operator()(\
					Iterator lhsBegin, Iterator lhsEnd, bool isFractionalPart1, \
					Iterator rhsBegin, Iterator rhsEnd, bool isFractionalPart2)
				{
					if (isFractionalPart1 && !isFractionalPart2)
						return true;	//0<num1<1 && num2>=1
					if (!isFractionalPart1 && isFractionalPart2)
						return false;	//0<num2<1 && num1>=1

					//isFractionPart1 == isFactionalPart2
					if (isFractionalPart1)
						return fractional(lhsBegin, lhsEnd, rhsBegin, rhsEnd);
					else
						return non_fractional(lhsBegin, lhsEnd, rhsBegin, rhsEnd);
				}
			};





		}// namespace detail

		/***********************************************************************
		Natural Comparision of Two String using both's (Begin and End Iterator)
		Returns :
			-1  - String1  <   String2
			 0  - String1  ==  String2
			 1  - String1  >   String2
		Suffix 1 represents for components of 1st String
		Suffix 2 represents for components of 2nd String
		************************************************************************/

		template<typename ElementType, typename Iterator>
		bool _compare(\
			const Iterator& lhsBegin, const Iterator& lhsEnd, \
			const Iterator& rhsBegin, const Iterator& rhsEnd)
		{
			Iterator current1 = lhsBegin, current2 = rhsBegin;

			//Flag for Space Found Check
			bool flag_found_space1 = false, flag_found_space2 = false;


			while (current1 != lhsEnd && current2 != rhsEnd)
			{
				//Ignore More than One Continous Space

				/******************************************
				For HandlingComparision Like
					Hello   9
					Hello  10
					Hello 123
				******************************************/
				while (flag_found_space1 && current1 != lhsEnd && *current1 == ' ') current1++;
				flag_found_space1 = false;
				if (*current1 == ' ') flag_found_space1 = true;

				while (flag_found_space2 && current2 != rhsEnd && *current2 == ' ') current2++;
				flag_found_space2 = false;
				if (*current2 == ' ') flag_found_space2 = true;


				if (!isdigit(*current1) || !isdigit(*current2))
				{
					// Normal comparision if any of character is non digit character
					if (detail::natural_less<ElementType>(*current1, *current2))
						return true;
					if (detail::natural_less<ElementType>(*current2, *current1))
						return false;
					current1++;
					current2++;
				}
				else
				{
					/*********************************
					Capture Numeric Part of Both String
					and then using it to compare Both
					***********************************/
					Iterator last_nondigit1 = std::find_if(current1, lhsEnd, detail::is_not_digit<ElementType>);
					Iterator last_nondigit2 = std::find_if(current2, rhsEnd, detail::is_not_digit<ElementType>);

					int result = detail::compare_number<ElementType, Iterator>()(\
						current1, last_nondigit1, (current1 > lhsBegin && *(current1 - 1) == '.'), \
						current2, last_nondigit2, (current2 > rhsBegin && *(current2 - 1) == '.'));
					if (result < 0)
						return true;
					if (result > 0)
						return false;
					current1 = last_nondigit1;
					current2 = last_nondigit2;
				}
			}

			if (current1 == lhsEnd && current2 == rhsEnd) {
				return false;
			}
			else {
				return current1 == lhsEnd;
			}
		}

		template<typename String>
		inline bool compare(const String& first, const String& second)
		{
			return _compare<typename String::value_type, typename String::const_iterator>(first.begin(), first.end(), second.begin(), second.end());
		}
		template<>
		inline bool compare(char* const& first, char* const& second)
		{
			char* it1 = first;
			while (*it1 != '\0')it1++;
			char* it2 = second;
			while (*it2 != '\0')it2++;
			return _compare<char, char*>(first, it1, second, it2);
		}


		template<typename Container>
		inline void sort(Container& container)
		{
			std::sort(container.begin(), container.end(), compare<typename Container::value_type>);
		}

		template<typename Iterator>
		inline void sort(const Iterator& first, const Iterator& end)
		{
			std::sort(first, end, compare<typename Iterator::value_type>);
		}

		template<typename ValueType>
		inline void sort(ValueType* const first, ValueType* const end)
		{
			std::sort(first, end, compare<ValueType>);
		}

		template<typename ValueType, int N>
		inline void sort(ValueType container[N])
		{
			std::sort(&container[0], &container[0] + N, compare<ValueType>);
		}

	}//namespace natural
}//namespace SI

#endif