/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2006-2009
//
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////
//[doc_assoc_optimized_code_normal_find
#include <boost/intrusive/set.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <cstring>

using namespace boost::intrusive;

// Hash function for strings
struct StrHasher
{
   std::size_t operator()(const char *str) const
   {  
      std::size_t seed = 0;
      for(; *str; ++str)   boost::hash_combine(seed, *str);
      return seed;
   }
};

class Expensive : public set_base_hook<>, public unordered_set_base_hook<>
{
   std::string key_;
   // Other members...
  
   public:
   Expensive(const char *key)
      :  key_(key)
      {}  //other expensive initializations...

   const std::string & get_key() const
      {  return key_;   }

   friend bool operator <  (const Expensive &a, const Expensive &b)
      {  return a.key_ < b.key_;  }

   friend bool operator == (const Expensive &a, const Expensive &b)
      {  return a.key_ == b.key_;  }

   friend std::size_t hash_value(const Expensive &object)
      {  return StrHasher()(object.get_key().c_str());  }
};

// A set and unordered_set that store Expensive objects
typedef set<Expensive>           Set;
typedef unordered_set<Expensive> UnorderedSet;

// Search functions
Expensive *get_from_set(const char* key, Set &set_object)
{
   Set::iterator it = set_object.find(Expensive(key));
   if( it == set_object.end() )     return 0;
   return &*it;
}

Expensive *get_from_uset(const char* key, UnorderedSet &uset_object)
{
   UnorderedSet::iterator it = uset_object.find(Expensive (key));
   if( it == uset_object.end() )  return 0;
   return &*it;
}
//]

//[doc_assoc_optimized_code_optimized_find
// These compare Expensive and a c-string
struct StrExpComp
{
   bool operator()(const char *str, const Expensive &c) const
   {  return std::strcmp(str, c.get_key().c_str()) < 0;  }

   bool operator()(const Expensive &c, const char *str) const
   {  return std::strcmp(c.get_key().c_str(), str) < 0;  }
};

struct StrExpEqual
{
   bool operator()(const char *str, const Expensive &c) const
   {  return std::strcmp(str, c.get_key().c_str()) == 0;  }

   bool operator()(const Expensive &c, const char *str) const
   {  return std::strcmp(c.get_key().c_str(), str) == 0;  }
};

// Optimized search functions
Expensive *get_from_set_optimized(const char* key, Set &set_object)
{
   Set::iterator it = set_object.find(key, StrExpComp());
   if( it == set_object.end() )   return 0;
   return &*it;
}

Expensive *get_from_uset_optimized(const char* key, UnorderedSet &uset_object)
{
   UnorderedSet::iterator it = uset_object.find(key, StrHasher(), StrExpEqual());
   if( it == uset_object.end() )  return 0;
   return &*it;
}
//]

//[doc_assoc_optimized_code_normal_insert
// Insertion functions
bool insert_to_set(const char* key, Set &set_object)
{
   Expensive *pobject = new Expensive(key);
   bool success = set_object.insert(*pobject).second;
   if(!success)   delete pobject;
   return success;
}

bool insert_to_uset(const char* key, UnorderedSet &uset_object)
{
   Expensive *pobject = new Expensive(key);
   bool success = uset_object.insert(*pobject).second;
   if(!success)   delete pobject;
   return success;
}
//]

//[doc_assoc_optimized_code_optimized_insert
// Optimized insertion functions
bool insert_to_set_optimized(const char* key, Set &set_object)
{
   Set::insert_commit_data insert_data;
   bool success = set_object.insert_check(key, StrExpComp(), insert_data).second;
   if(success) set_object.insert_commit(*new Expensive(key), insert_data);
   return success;
}

bool insert_to_uset_optimized(const char* key, UnorderedSet &uset_object)
{
   UnorderedSet::insert_commit_data insert_data;
   bool success = uset_object.insert_check
      (key, StrHasher(), StrExpEqual(), insert_data).second;
   if(success) uset_object.insert_commit(*new Expensive(key), insert_data);
   return success;
}
//]

int main()
{
   Set set;
   UnorderedSet::bucket_type buckets[10];
   UnorderedSet unordered_set(UnorderedSet::bucket_traits(buckets, 10));

   const char * const expensive_key
      = "A long string that avoids small string optimization";

   Expensive value(expensive_key);

   if(get_from_set(expensive_key, set)){
      return 1;
   }

   if(get_from_uset(expensive_key, unordered_set)){
      return 1;
   }

   if(get_from_set_optimized(expensive_key, set)){
      return 1;
   }

   if(get_from_uset_optimized(expensive_key, unordered_set)){
      return 1;
   }

   Set::iterator setit =  set.insert(value).first;
   UnorderedSet::iterator unordered_setit =  unordered_set.insert(value).first;

   if(!get_from_set(expensive_key, set)){
      return 1;
   }

   if(!get_from_uset(expensive_key, unordered_set)){
      return 1;
   }

   if(!get_from_set_optimized(expensive_key, set)){
      return 1;
   }

   if(!get_from_uset_optimized(expensive_key, unordered_set)){
      return 1;
   }

   set.erase(setit);
   unordered_set.erase(unordered_setit);

   if(!insert_to_set(expensive_key, set)){
      return 1;
   }

   if(!insert_to_uset(expensive_key, unordered_set)){
      return 1;
   }

   {
      Expensive *ptr = &*set.begin();
      set.clear();
      delete ptr;
   }

   {
      Expensive *ptr = &*unordered_set.begin();
      unordered_set.clear();
      delete ptr;
   }

   if(!insert_to_set_optimized(expensive_key, set)){
      return 1;
   }

   if(!insert_to_uset_optimized(expensive_key, unordered_set)){
      return 1;
   }

   {
      Expensive *ptr = &*set.begin();
      set.clear();
      delete ptr;
   }

   {
      Expensive *ptr = &*unordered_set.begin();
      unordered_set.clear();
      delete ptr;
   }

   setit       =  set.insert(value).first;
   unordered_setit   =  unordered_set.insert(value).first;

   if(insert_to_set(expensive_key, set)){
      return 1;
   }

   if(insert_to_uset(expensive_key, unordered_set)){
      return 1;
   }

   if(insert_to_set_optimized(expensive_key, set)){
      return 1;
   }

   if(insert_to_uset_optimized(expensive_key, unordered_set)){
      return 1;
   }

   set.erase(value);
   unordered_set.erase(value);

   return 0;
}