#if !defined(DISAMBIGUATE_H)
#define DISAMBIGUATE_H

#include <string>
#include <algorithm>
#include <vector>

#include <boost/spirit/core/parser.hpp>
#include <boost/spirit/core/primitives/primitives.hpp>
#include <boost/spirit/core/composite/operators.hpp>
#include <boost/spirit/core/composite/directives.hpp>
#include <boost/spirit/core/composite/epsilon.hpp>
#include <boost/spirit/utility/chset.hpp>
#include <boost/spirit/utility/functor_parser.hpp>

#include <boost/bind.hpp>

namespace boost {
   namespace spirit {

struct DisambiguateItem
{
   DisambiguateItem(std::string n, int a) : name(n), ambiguity(a) {}
   std::string name;
   int ambiguity;
};

namespace impl
{

   bool DisambiguateItemOrdering(DisambiguateItem const& left, DisambiguateItem const& right)
   {
      return left.name < right.name;
   }

   bool IsNamedItem(DisambiguateItem const& item, const std::string& name)
   {
      return item.name == name;
   }

   void SetAmbiguity(DisambiguateItem& item, int ambiguity)
   {
      item.ambiguity = std::min<int>(item.name.length(), std::max<int>(item.ambiguity, ambiguity));
   }

   bool SubItemOrdering(DisambiguateItem const& left, DisambiguateItem const& right, int ambigLength)
   {
      const std::string& sLeft = left.name;
      const std::string& sRight = right.name;
      const int lengthToUse = std::min<int>(sLeft.length(), std::min<int>(sRight.length(), ambigLength));

      return sLeft.substr(0, lengthToUse) < sRight.substr(0, lengthToUse);
   }
}

class Disambiguator
{
public:
   typedef std::vector<DisambiguateItem> DisambiguateItems;
   typedef DisambiguateItems::const_iterator const_iterator;
   typedef DisambiguateItems::iterator iterator;
   Disambiguator(int minAmbiguity = 1) : minAmbiguity_(minAmbiguity)
   {
   }

   Disambiguator& operator()(std::string const& name)
   {
      AddString(name);
      return *this;
   }

   void AddString(std::string const& name)
   {
      DisambiguateItem newItem(name, minAmbiguity_);
      iterator begin = items_.begin();
      iterator end = items_.end();
      if (GetItem(name) == end)
      {
         iterator insertPos = std::lower_bound(begin, end, newItem, &impl::DisambiguateItemOrdering);
         items_.insert(insertPos, newItem);
         iterator ambigBegin = items_.begin();
         iterator ambigEnd = items_.end();
         for(int length = 1;length <= name.length();++length)
         {
            std::pair<iterator, iterator> ambig = std::equal_range(ambigBegin, ambigEnd,
                                                                   newItem,
                                                                   boost::bind(&impl::SubItemOrdering, _1, _2, length));
            ambigBegin = ambig.first;
            ambigEnd = ambig.second;
            const int ambigCount = std::distance(ambigBegin, ambigEnd);
            assert(ambigCount > 0);
            if (ambigCount == 1)
            {
               assert(ambigBegin->name == name);
               break;
            }
            std::for_each(ambigBegin, ambigEnd, boost::bind(&impl::SetAmbiguity, _1, 1+length));
         }
      }
   }

   int Ambiguity(std::string const& name) const
   {
      const_iterator foundItem = GetItem(name);
      if (foundItem == end())
         throw name;
      return foundItem->ambiguity;
   }

   const_iterator begin() const { return items_.begin(); }
   const_iterator end() const { return items_.end(); }
private:
   iterator GetItem(std::string const& name)
   {
      return std::find_if(items_.begin(), items_.end(), boost::bind(&impl::IsNamedItem, _1, name));
   }
   const_iterator GetItem(std::string const& name) const
   {
      return std::find_if(begin(), end(), boost::bind(&impl::IsNamedItem, _1, name));
   }

   DisambiguateItems items_;
   int minAmbiguity_;
};

namespace impl
{
   struct min_unambiguous_parser_f
   {
      typedef std::string result_t;

      min_unambiguous_parser_f(std::string const& s, Disambiguator& d, int userMinLen = 1)
         : d_(d), s_(s), minLen_(-1), userMinLen_(userMinLen)
      {
         d_.AddString(s_);
      }

      template <typename ScannerT>
      std::ptrdiff_t
      operator()(ScannerT const& scan, result_t& result) const
      {
         if (scan.at_end())
             return -1;

         std::ptrdiff_t const maxLen = s_.length();
         std::ptrdiff_t len = 0;

         while (len <= maxLen && !(scan.at_end() || *scan != s_[len]))
         {
            ++len;
            ++scan;
         }

         if (minLen_==-1)
         {
            minLen_= std::max(d_.Ambiguity(s_), userMinLen_);
         }
         if (len < minLen_)
         {
            return -1;
         }

         result = s_;
         return len;
      }

      std::string const s_;
      mutable std::ptrdiff_t minLen_;
      const std::ptrdiff_t userMinLen_;
      Disambiguator& d_;
   };
}

typedef functor_parser<impl::min_unambiguous_parser_f> min_unambiguous_parser_p;

typedef contiguous<sequence<min_unambiguous_parser_p,
                            negated_empty_match_parser<spirit::impl::epsilon_selector<chset<char> >::subject_t> >
        > min_unambiguous_parser;

inline min_unambiguous_parser min_unambig_p(std::string const& s, int minReqLength, Disambiguator& d)
{
   return lexeme_d[min_unambiguous_parser_p(impl::min_unambiguous_parser_f(s, d, minReqLength)) >> ~epsilon_p(chset_p("A-Za-z0-9_"))];
}

inline min_unambiguous_parser min_unambig_p(std::string const& s, Disambiguator& d)
{
   return min_unambig_p(s, 1, d);
}

inline min_unambiguous_parser min_unambig_p(std::string const& required, std::string const& optional, Disambiguator& d)
{
   return min_unambig_p(required+optional, required.length(), d);
}

}
}

#endif // DISAMBIGUATE_H