// Copyright 2002 Google Inc.
//
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.
//
// ---
//
//
// STL utility functions.  Usually, these replace built-in, but slow(!),
// STL functions with more efficient versions or provide a more convenient
// and Google friendly API.
//

#ifndef UTIL_GTL_STL_UTIL_H_
#define UTIL_GTL_STL_UTIL_H_

#include <stddef.h>
#include <string.h>  // for memcpy
#include <algorithm>
#include <cassert>
#include <deque>
#include <functional>
#include <iterator>
#include <memory>
#include <string>
#include <vector>

#include "kudu/gutil/integral_types.h"
#include "kudu/gutil/macros.h"
#include "kudu/gutil/port.h"

// Sort and remove duplicates of an STL vector or deque.
template<class T>
void STLSortAndRemoveDuplicates(T *v) {
  std::sort(v->begin(), v->end());
  v->erase(unique(v->begin(), v->end()), v->end());
}

// Clear internal memory of an STL object.
// STL clear()/reserve(0) does not always free internal memory allocated
// This function uses swap/destructor to ensure the internal memory is freed.
template<class T> void STLClearObject(T* obj) {
  T tmp;
  tmp.swap(*obj);
  obj->reserve(0);  // this is because sometimes "T tmp" allocates objects with
                    // memory (arena implementation?).  use reserve()
                    // to clear() even if it doesn't always work
}

// Specialization for deque. Same as STLClearObject but doesn't call reserve
// since deque doesn't have reserve.
template <class T, class A>
void STLClearObject(std::deque<T, A>* obj) {
  std::deque<T, A> tmp;
  tmp.swap(*obj);
}

// Reduce memory usage on behalf of object if its capacity is greater
// than or equal to "limit", which defaults to 2^20.
template <class T> inline void STLClearIfBig(T* obj, size_t limit = 1<<20) {
  if (obj->capacity() >= limit) {
    STLClearObject(obj);
  } else {
    obj->clear();
  }
}

// Specialization for deque, which doesn't implement capacity().
template <class T, class A>
inline void STLClearIfBig(std::deque<T, A>* obj, size_t limit = 1<<20) {
  if (obj->size() >= limit) {
    STLClearObject(obj);
  } else {
    obj->clear();
  }
}

// Reduce the number of buckets in a hash_set or hash_map back to the
// default if the current number of buckets is "limit" or more.
//
// Suppose you repeatedly fill and clear a hash_map or hash_set.  If
// you ever insert a lot of items, then your hash table will have lots
// of buckets thereafter.  (The number of buckets is not reduced when
// the table is cleared.)  Having lots of buckets is good if you
// insert comparably many items in every iteration, because you'll
// reduce collisions and table resizes.  But having lots of buckets is
// bad if you insert few items in most subsequent iterations, because
// repeatedly clearing out all those buckets can get expensive.
//
// One solution is to call STLClearHashIfBig() with a "limit" value
// that is a small multiple of the typical number of items in your
// table.  In the common case, this is equivalent to an ordinary
// clear.  In the rare case where you insert a lot of items, the
// number of buckets is reset to the default to keep subsequent clear
// operations cheap.  Note that the default number of buckets is 193
// in the Gnu library implementation as of Jan '08.
template <class T> inline void STLClearHashIfBig(T *obj, size_t limit) {
  if (obj->bucket_count() >= limit) {
    T tmp;
    tmp.swap(*obj);
  } else {
    obj->clear();
  }
}

// Reserve space for STL object.
// STL's reserve() will always copy.
// This function avoid the copy if we already have capacity
template<class T> void STLReserveIfNeeded(T* obj, int new_size) {
  if (obj->capacity() < new_size)   // increase capacity
    obj->reserve(new_size);
  else if (obj->size() > new_size)  // reduce size
    obj->resize(new_size);
}

// STLDeleteContainerPointers()
//  For a range within a container of pointers, calls delete
//  (non-array version) on these pointers.
// NOTE: for these three functions, we could just implement a DeleteObject
// functor and then call for_each() on the range and functor, but this
// requires us to pull in all of <algorithm>, which seems expensive.
// For hash_[multi]set, it is important that this deletes behind the iterator
// because the hash_set may call the hash function on the iterator when it is
// advanced, which could result in the hash function trying to deference a
// stale pointer.
// NOTE: If you're calling this on an entire container, you probably want
// to call STLDeleteElements(&container) instead, or use an ElementDeleter.
template <class ForwardIterator>
void STLDeleteContainerPointers(ForwardIterator begin,
                                ForwardIterator end) {
  while (begin != end) {
    ForwardIterator temp = begin;
    ++begin;
    delete *temp;
  }
}

// STLDeleteContainerPairPointers()
//  For a range within a container of pairs, calls delete
//  (non-array version) on BOTH items in the pairs.
// NOTE: Like STLDeleteContainerPointers, it is important that this deletes
// behind the iterator because if both the key and value are deleted, the
// container may call the hash function on the iterator when it is advanced,
// which could result in the hash function trying to dereference a stale
// pointer.
template <class ForwardIterator>
void STLDeleteContainerPairPointers(ForwardIterator begin,
                                    ForwardIterator end) {
  while (begin != end) {
    ForwardIterator temp = begin;
    ++begin;
    delete temp->first;
    delete temp->second;
  }
}

// STLDeleteContainerPairFirstPointers()
//  For a range within a container of pairs, calls delete (non-array version)
//  on the FIRST item in the pairs.
// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator.
template <class ForwardIterator>
void STLDeleteContainerPairFirstPointers(ForwardIterator begin,
                                         ForwardIterator end) {
  while (begin != end) {
    ForwardIterator temp = begin;
    ++begin;
    delete temp->first;
  }
}

// STLDeleteContainerPairSecondPointers()
//  For a range within a container of pairs, calls delete
//  (non-array version) on the SECOND item in the pairs.
// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator.
// Deleting the value does not always invalidate the iterator, but it may
// do so if the key is a pointer into the value object.
// NOTE: If you're calling this on an entire container, you probably want
// to call STLDeleteValues(&container) instead, or use ValueDeleter.
template <class ForwardIterator>
void STLDeleteContainerPairSecondPointers(ForwardIterator begin,
                                          ForwardIterator end) {
  while (begin != end) {
    ForwardIterator temp = begin;
    ++begin;
    delete temp->second;
  }
}

template<typename T>
inline void STLAssignToVector(std::vector<T>* vec,
                              const T* ptr,
                              size_t n) {
  vec->resize(n);
  if (n == 0) return;
  memcpy(&vec->front(), ptr, n*sizeof(T));
}

// Not faster; but we need the specialization so the function works at all
// on the vector<bool> specialization.
template<>
inline void STLAssignToVector(std::vector<bool>* vec,
                              const bool* ptr,
                              size_t n) {
  vec->clear();
  if (n == 0) return;
  vec->insert(vec->begin(), ptr, ptr + n);
}

/***** Hack to allow faster assignment to a vector *****/

// This routine speeds up an assignment of 32 bytes to a vector from
// about 250 cycles per assignment to about 140 cycles.
//
// Usage:
//      STLAssignToVectorChar(&vec, ptr, size);
//      STLAssignToString(&str, ptr, size);

inline void STLAssignToVectorChar(std::vector<char>* vec,
                                  const char* ptr,
                                  size_t n) {
  STLAssignToVector(vec, ptr, n);
}

// A struct that mirrors the GCC4 implementation of a string. See:
// /usr/crosstool/v8/gcc-4.1.0-glibc-2.2.2/i686-unknown-linux-gnu/include/c++/4.1.0/ext/sso_string_base.h
struct InternalStringRepGCC4 {
  char*  _M_data;
  size_t _M_string_length;

  enum { _S_local_capacity = 15 };

  union {
    char             _M_local_data[_S_local_capacity + 1];
    size_t           _M_allocated_capacity;
  };
};

// Like str->resize(new_size), except any new characters added to
// "*str" as a result of resizing may be left uninitialized, rather
// than being filled with '0' bytes.  Typically used when code is then
// going to overwrite the backing store of the string with known data.
inline void STLStringResizeUninitialized(std::string* s, size_t new_size) {
  if (sizeof(*s) == sizeof(InternalStringRepGCC4)) {
    if (new_size > s->capacity()) {
      s->reserve(new_size);
    }
    // The line below depends on the layout of 'string'.  THIS IS
    // NON-PORTABLE CODE.  If our STL implementation changes, we will
    // need to change this as well.
    InternalStringRepGCC4* rep = reinterpret_cast<InternalStringRepGCC4*>(s);
    assert(rep->_M_data == s->data());
    assert(rep->_M_string_length == s->size());

    // We have to null-terminate the string for c_str() to work properly.
    // So we leave the actual contents of the string uninitialized, but
    // we set the byte one past the new end of the string to '\0'
    const_cast<char*>(s->data())[new_size] = '\0';
    rep->_M_string_length = new_size;
  } else {
    // Slow path: have to reallocate stuff, or an unknown string rep
    s->resize(new_size);
  }
}

// Returns true if the string implementation supports a resize where
// the new characters added to the string are left untouched.
inline bool STLStringSupportsNontrashingResize(const std::string& s) {
  return (sizeof(s) == sizeof(InternalStringRepGCC4));
}

inline void STLAssignToString(std::string* str, const char* ptr, size_t n) {
  STLStringResizeUninitialized(str, n);
  if (n == 0) return;
  memcpy(&*str->begin(), ptr, n);
}

inline void STLAppendToString(std::string* str, const char* ptr, size_t n) {
  if (n == 0) return;
  size_t old_size = str->size();
  STLStringResizeUninitialized(str, old_size + n);
  memcpy(&*str->begin() + old_size, ptr, n);
}

// To treat a possibly-empty vector as an array, use these functions.
// If you know the array will never be empty, you can use &*v.begin()
// directly, but that is allowed to dump core if v is empty.  This
// function is the most efficient code that will work, taking into
// account how our STL is actually implemented.  THIS IS NON-PORTABLE
// CODE, so call us instead of repeating the nonportable code
// everywhere.  If our STL implementation changes, we will need to
// change this as well.

template<typename T, typename Allocator>
inline T* vector_as_array(std::vector<T, Allocator>* v) {
# ifdef NDEBUG
  return &*v->begin();
# else
  return v->empty() ? NULL : &*v->begin();
# endif
}

template<typename T, typename Allocator>
inline const T* vector_as_array(const std::vector<T, Allocator>* v) {
# ifdef NDEBUG
  return &*v->begin();
# else
  return v->empty() ? NULL : &*v->begin();
# endif
}

// Return a mutable char* pointing to a string's internal buffer,
// which may not be null-terminated. Writing through this pointer will
// modify the string.
//
// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
// next call to a string method that invalidates iterators.
//
// Prior to C++11, there was no standard-blessed way of getting a mutable
// reference to a string's internal buffer. The requirement that string be
// contiguous is officially part of the C++11 standard [string.require]/5.
// According to Matt Austern, this should already work on all current C++98
// implementations.
inline char* string_as_array(std::string* str) {
  // DO NOT USE const_cast<char*>(str->data())! See the unittest for why.
  return str->empty() ? NULL : &*str->begin();
}

// These are methods that test two hash maps/sets for equality.  These exist
// because the == operator in the STL can return false when the maps/sets
// contain identical elements.  This is because it compares the internal hash
// tables which may be different if the order of insertions and deletions
// differed.

template <class HashSet>
inline bool
HashSetEquality(const HashSet& set_a,
                const HashSet& set_b) {
  if (set_a.size() != set_b.size()) return false;
  for (typename HashSet::const_iterator i = set_a.begin();
       i != set_a.end();
       ++i)
    if (set_b.find(*i) == set_b.end()) return false;
  return true;
}

template <class HashMap>
inline bool
HashMapEquality(const HashMap& map_a,
                const HashMap& map_b) {
  if (map_a.size() != map_b.size()) return false;
  for (typename HashMap::const_iterator i = map_a.begin();
       i != map_a.end(); ++i) {
    typename HashMap::const_iterator j = map_b.find(i->first);
    if (j == map_b.end()) return false;
    if (i->second != j->second) return false;
  }
  return true;
}

// The following functions are useful for cleaning up STL containers
// whose elements point to allocated memory.

// STLDeleteElements() deletes all the elements in an STL container and clears
// the container.  This function is suitable for use with a vector, set,
// hash_set, or any other STL container which defines sensible begin(), end(),
// and clear() methods.
//
// If container is NULL, this function is a no-op.
//
// As an alternative to calling STLDeleteElements() directly, consider
// ElementDeleter (defined below), which ensures that your container's elements
// are deleted when the ElementDeleter goes out of scope.
template <class T>
void STLDeleteElements(T *container) {
  if (!container) return;
  STLDeleteContainerPointers(container->begin(), container->end());
  container->clear();
}

// Given an STL container consisting of (key, value) pairs, STLDeleteValues
// deletes all the "value" components and clears the container.  Does nothing
// in the case it's given a NULL pointer.
template <class T>
void STLDeleteValues(T *v) {
  if (!v) return;
  STLDeleteContainerPairSecondPointers(v->begin(), v->end());
  v->clear();
}


// ElementDeleter and ValueDeleter provide a convenient way to delete all
// elements or values from STL containers when they go out of scope.  This
// greatly simplifies code that creates temporary objects and has multiple
// return statements.  Example:
//
// vector<MyProto *> tmp_proto;
// ElementDeleter d(&tmp_proto);
// if (...) return false;
// ...
// return success;

// A very simple interface that simply provides a virtual destructor.  It is
// used as a non-templated base class for the TemplatedElementDeleter and
// TemplatedValueDeleter classes.  Clients should not typically use this class
// directly.
class BaseDeleter {
 public:
  virtual ~BaseDeleter() {}

 protected:
  BaseDeleter() {}

 private:
  DISALLOW_EVIL_CONSTRUCTORS(BaseDeleter);
};

// Given a pointer to an STL container, this class will delete all the element
// pointers when it goes out of scope.  Clients should typically use
// ElementDeleter rather than invoking this class directly.
template<class STLContainer>
class TemplatedElementDeleter : public BaseDeleter {
 public:
  explicit TemplatedElementDeleter<STLContainer>(STLContainer *ptr)
      : container_ptr_(ptr) {
  }

  virtual ~TemplatedElementDeleter<STLContainer>() {
    STLDeleteElements(container_ptr_);
  }

 private:
  STLContainer *container_ptr_;

  DISALLOW_EVIL_CONSTRUCTORS(TemplatedElementDeleter);
};

// Like TemplatedElementDeleter, this class will delete element pointers from a
// container when it goes out of scope.  However, it is much nicer to use,
// since the class itself is not templated.
class ElementDeleter {
 public:
  template <class STLContainer>
  explicit ElementDeleter(STLContainer *ptr)
      : deleter_(new TemplatedElementDeleter<STLContainer>(ptr)) {
  }

  ~ElementDeleter() {
    delete deleter_;
  }

 private:
  BaseDeleter *deleter_;

  DISALLOW_EVIL_CONSTRUCTORS(ElementDeleter);
};

// Given a pointer to an STL container this class will delete all the value
// pointers when it goes out of scope.  Clients should typically use
// ValueDeleter rather than invoking this class directly.
template<class STLContainer>
class TemplatedValueDeleter : public BaseDeleter {
 public:
  explicit TemplatedValueDeleter<STLContainer>(STLContainer *ptr)
      : container_ptr_(ptr) {
  }

  virtual ~TemplatedValueDeleter<STLContainer>() {
    STLDeleteValues(container_ptr_);
  }

 private:
  STLContainer *container_ptr_;

  DISALLOW_EVIL_CONSTRUCTORS(TemplatedValueDeleter);
};

// Similar to ElementDeleter, but wraps a TemplatedValueDeleter rather than an
// TemplatedElementDeleter.
class ValueDeleter {
 public:
  template <class STLContainer>
  explicit ValueDeleter(STLContainer *ptr)
      : deleter_(new TemplatedValueDeleter<STLContainer>(ptr)) {
  }

  ~ValueDeleter() {
    delete deleter_;
  }

 private:
  BaseDeleter *deleter_;

  DISALLOW_EVIL_CONSTRUCTORS(ValueDeleter);
};


// STLElementDeleter and STLValueDeleter are similar to ElementDeleter and
// ValueDeleter, except that:
// - The classes are templated, making them less convenient to use.
// - Their destructors are not virtual, making them potentially more efficient.
// New code should typically use ElementDeleter and ValueDeleter unless
// efficiency is a large concern.

template<class STLContainer> class STLElementDeleter {
 public:
  STLElementDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {}
  ~STLElementDeleter<STLContainer>() { STLDeleteElements(container_ptr_); }
 private:
  STLContainer *container_ptr_;
};

template<class STLContainer> class STLValueDeleter {
 public:
  STLValueDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {}
  ~STLValueDeleter<STLContainer>() { STLDeleteValues(container_ptr_); }
 private:
  STLContainer *container_ptr_;
};


// STLSet{Difference,SymmetricDifference,Union,Intersection}(A a, B b, C *c)
// *APPEND* the set {difference, symmetric difference, union, intersection} of
// the two sets a and b to c.
// STLSet{Difference,SymmetricDifference,Union,Intersection}(T a, T b) do the
// same but return the result by value rather than by the third pointer
// argument.  The result type is the same as both of the inputs in the two
// argument case.
//
// Requires:
//   a and b must be STL like containers that contain sorted data (as defined
//   by the < operator).
//   For the 3 argument version &a == c or &b == c are disallowed.  In those
//   cases the 2 argument version is probably what you want anyway:
//   a = STLSetDifference(a, b);
//
// These function are convenience functions.  The code they implement is
// trivial (at least for now).  The STL incantations they wrap are just too
// verbose for programmers to use then and they are unpleasant to the eye.
// Without these convenience versions people will simply keep writing one-off
// for loops which are harder to read and more error prone.
//
// Note that for initial construction of an object it is just as efficient to
// use the 2 argument version as the 3 version due to RVO (return value
// optimization) of modern C++ compilers:
//   set<int> c = STLSetDifference(a, b);
// is an example of where RVO comes into play.

template<typename SortedSTLContainerA,
         typename SortedSTLContainerB,
         typename SortedSTLContainerC>
void STLSetDifference(const SortedSTLContainerA &a,
                      const SortedSTLContainerB &b,
                      SortedSTLContainerC *c) {
  // The qualified name avoids an ambiguity error, particularly with C++11:
  assert(std::is_sorted(a.begin(), a.end()));
  assert(std::is_sorted(b.begin(), b.end()));
  assert(static_cast<const void *>(&a) !=
         static_cast<const void *>(c));
  assert(static_cast<const void *>(&b) !=
         static_cast<const void *>(c));
  std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                      std::inserter(*c, c->end()));
}

template<typename SortedSTLContainer>
SortedSTLContainer STLSetDifference(const SortedSTLContainer &a,
                                    const SortedSTLContainer &b) {
  SortedSTLContainer c;
  STLSetDifference(a, b, &c);
  return c;
}

template<typename SortedSTLContainerA,
         typename SortedSTLContainerB,
         typename SortedSTLContainerC>
void STLSetUnion(const SortedSTLContainerA &a,
                 const SortedSTLContainerB &b,
                 SortedSTLContainerC *c) {
  assert(std::is_sorted(a.begin(), a.end()));
  assert(std::is_sorted(b.begin(), b.end()));
  assert(static_cast<const void *>(&a) !=
         static_cast<const void *>(c));
  assert(static_cast<const void *>(&b) !=
         static_cast<const void *>(c));
  std::set_union(a.begin(), a.end(), b.begin(), b.end(),
                 std::inserter(*c, c->end()));
}

template<typename SortedSTLContainerA,
         typename SortedSTLContainerB,
         typename SortedSTLContainerC>
void STLSetSymmetricDifference(const SortedSTLContainerA &a,
                               const SortedSTLContainerB &b,
                               SortedSTLContainerC *c) {
  assert(std::is_sorted(a.begin(), a.end()));
  assert(std::is_sorted(b.begin(), b.end()));
  assert(static_cast<const void *>(&a) !=
         static_cast<const void *>(c));
  assert(static_cast<const void *>(&b) !=
         static_cast<const void *>(c));
  std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
                                std::inserter(*c, c->end()));
}

template<typename SortedSTLContainer>
SortedSTLContainer STLSetSymmetricDifference(const SortedSTLContainer &a,
                                             const SortedSTLContainer &b) {
  SortedSTLContainer c;
  STLSetSymmetricDifference(a, b, &c);
  return c;
}

template<typename SortedSTLContainer>
SortedSTLContainer STLSetUnion(const SortedSTLContainer &a,
                               const SortedSTLContainer &b) {
  SortedSTLContainer c;
  STLSetUnion(a, b, &c);
  return c;
}

template<typename SortedSTLContainerA,
         typename SortedSTLContainerB,
         typename SortedSTLContainerC>
void STLSetIntersection(const SortedSTLContainerA &a,
                        const SortedSTLContainerB &b,
                        SortedSTLContainerC *c) {
  assert(std::is_sorted(a.begin(), a.end()));
  assert(std::is_sorted(b.begin(), b.end()));
  assert(static_cast<const void *>(&a) !=
         static_cast<const void *>(c));
  assert(static_cast<const void *>(&b) !=
         static_cast<const void *>(c));
  std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                        std::inserter(*c, c->end()));
}

template<typename SortedSTLContainer>
SortedSTLContainer STLSetIntersection(const SortedSTLContainer &a,
                                      const SortedSTLContainer &b) {
  SortedSTLContainer c;
  STLSetIntersection(a, b, &c);
  return c;
}

// Similar to STLSet{Union,Intesection,etc}, but simpler because the result is
// always bool.
template<typename SortedSTLContainerA,
         typename SortedSTLContainerB>
bool STLIncludes(const SortedSTLContainerA &a,
                 const SortedSTLContainerB &b) {
  assert(std::is_sorted(a.begin(), a.end()));
  assert(std::is_sorted(b.begin(), b.end()));
  return std::includes(a.begin(), a.end(),
                       b.begin(), b.end());
}

// Functors that compose arbitrary unary and binary functions with a
// function that "projects" one of the members of a pair.
// Specifically, if p1 and p2, respectively, are the functions that
// map a pair to its first and second, respectively, members, the
// table below summarizes the functions that can be constructed:
//
// * UnaryOperate1st<pair>(f) returns the function x -> f(p1(x))
// * UnaryOperate2nd<pair>(f) returns the function x -> f(p2(x))
// * BinaryOperate1st<pair>(f) returns the function (x,y) -> f(p1(x),p1(y))
// * BinaryOperate2nd<pair>(f) returns the function (x,y) -> f(p2(x),p2(y))
//
// A typical usage for these functions would be when iterating over
// the contents of an STL map. For other sample usage, see the unittest.

template<typename Pair, typename UnaryOp>
class UnaryOperateOnFirst
    : public std::unary_function<Pair, typename UnaryOp::result_type> {
 public:
  UnaryOperateOnFirst() {
  }

  UnaryOperateOnFirst(const UnaryOp& f) : f_(f) {  // TODO(user): explicit?
  }

  typename UnaryOp::result_type operator()(const Pair& p) const {
    return f_(p.first);
  }

 private:
  UnaryOp f_;
};

template<typename Pair, typename UnaryOp>
UnaryOperateOnFirst<Pair, UnaryOp> UnaryOperate1st(const UnaryOp& f) {
  return UnaryOperateOnFirst<Pair, UnaryOp>(f);
}

template<typename Pair, typename UnaryOp>
class UnaryOperateOnSecond
    : public std::unary_function<Pair, typename UnaryOp::result_type> {
 public:
  UnaryOperateOnSecond() {
  }

  UnaryOperateOnSecond(const UnaryOp& f) : f_(f) {  // TODO(user): explicit?
  }

  typename UnaryOp::result_type operator()(const Pair& p) const {
    return f_(p.second);
  }

 private:
  UnaryOp f_;
};

template<typename Pair, typename UnaryOp>
UnaryOperateOnSecond<Pair, UnaryOp> UnaryOperate2nd(const UnaryOp& f) {
  return UnaryOperateOnSecond<Pair, UnaryOp>(f);
}

template<typename Pair, typename BinaryOp>
class BinaryOperateOnFirst
    : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> {
 public:
  BinaryOperateOnFirst() {
  }

  BinaryOperateOnFirst(const BinaryOp& f) : f_(f) {  // TODO(user): explicit?
  }

  typename BinaryOp::result_type operator()(const Pair& p1,
                                            const Pair& p2) const {
    return f_(p1.first, p2.first);
  }

 private:
  BinaryOp f_;
};

// TODO(user): explicit?
template<typename Pair, typename BinaryOp>
BinaryOperateOnFirst<Pair, BinaryOp> BinaryOperate1st(const BinaryOp& f) {
  return BinaryOperateOnFirst<Pair, BinaryOp>(f);
}

template<typename Pair, typename BinaryOp>
class BinaryOperateOnSecond
    : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> {
 public:
  BinaryOperateOnSecond() {
  }

  BinaryOperateOnSecond(const BinaryOp& f) : f_(f) {
  }

  typename BinaryOp::result_type operator()(const Pair& p1,
                                            const Pair& p2) const {
    return f_(p1.second, p2.second);
  }

 private:
  BinaryOp f_;
};

template<typename Pair, typename BinaryOp>
BinaryOperateOnSecond<Pair, BinaryOp> BinaryOperate2nd(const BinaryOp& f) {
  return BinaryOperateOnSecond<Pair, BinaryOp>(f);
}

// Functor that composes a binary functor h from an arbitrary binary functor
// f and two unary functors g1, g2, so that:
//
// BinaryCompose1(f, g) returns function (x, y) -> f(g(x), g(y))
// BinaryCompose2(f, g1, g2) returns function (x, y) -> f(g1(x), g2(y))
//
// This is a generalization of the BinaryOperate* functors for types other
// than pairs.
//
// For sample usage, see the unittest.
//
// F has to be a model of AdaptableBinaryFunction.
// G1 and G2 have to be models of AdabtableUnaryFunction.
template<typename F, typename G1, typename G2>
class BinaryComposeBinary : public std::binary_function<typename G1::argument_type,
                                                        typename G2::argument_type,
                                                        typename F::result_type> {
 public:
  BinaryComposeBinary(F f, G1 g1, G2 g2) : f_(f), g1_(g1), g2_(g2) { }

  typename F::result_type operator()(typename G1::argument_type x,
                                     typename G2::argument_type y) const {
    return f_(g1_(x), g2_(y));
  }

 private:
  F f_;
  G1 g1_;
  G2 g2_;
};

template<typename F, typename G>
BinaryComposeBinary<F, G, G> BinaryCompose1(F f, G g) {
  return BinaryComposeBinary<F, G, G>(f, g, g);
}

template<typename F, typename G1, typename G2>
BinaryComposeBinary<F, G1, G2> BinaryCompose2(F f, G1 g1, G2 g2) {
  return BinaryComposeBinary<F, G1, G2>(f, g1, g2);
}

// This is a wrapper for an STL allocator which keeps a count of the
// active bytes allocated by this class of allocators.  This is NOT
// THREAD SAFE.  This should only be used in situations where you can
// ensure that only a single thread performs allocation and
// deallocation.
template <typename T, typename Alloc = std::allocator<T> >
class STLCountingAllocator : public Alloc {
 public:
  typedef typename Alloc::pointer pointer;
  typedef typename Alloc::size_type size_type;

  STLCountingAllocator() : bytes_used_(NULL) { }
  STLCountingAllocator(int64* b) : bytes_used_(b) {}  // TODO(user): explicit?

  // Constructor used for rebinding
  template <class U>
  STLCountingAllocator(const STLCountingAllocator<U>& x)
      : Alloc(x),
        bytes_used_(x.bytes_used()) {
  }

  pointer allocate(size_type n, std::allocator<void>::const_pointer hint = 0) {
    assert(bytes_used_ != NULL);
    *bytes_used_ += n * sizeof(T);
    return Alloc::allocate(n, hint);
  }

  void deallocate(pointer p, size_type n) {
    Alloc::deallocate(p, n);
    assert(bytes_used_ != NULL);
    *bytes_used_ -= n * sizeof(T);
  }

  // Rebind allows an allocator<T> to be used for a different type
  template <class U> struct rebind {
    typedef STLCountingAllocator<U,
                                 typename Alloc::template
                                 rebind<U>::other> other;
  };

  int64* bytes_used() const { return bytes_used_; }

 private:
  int64* bytes_used_;
};

// Even though a struct has no data members, it cannot have zero size
// according to the standard.  However, "empty base-class
// optimization" allows an empty parent class to add no additional
// size to the object.  STLEmptyBaseHandle is a handy way to "stuff"
// objects that are typically empty (e.g., allocators, compare
// objects) into other fields of an object without increasing the size
// of the object.
//
// struct Empty {
//   void Method() { }
// };
// struct OneInt {
//   STLEmptyBaseHandle<Empty, int> i;
// };
//
// In the example above, "i.data" refers to the integer field, whereas
// "i" refers to the empty base class.  sizeof(OneInt) == sizeof(int)
// despite the fact that sizeof(Empty) > 0.
template <typename Base, typename Data>
struct STLEmptyBaseHandle : public Base {
  template <typename U>
  STLEmptyBaseHandle(const U &b, const Data &d)
      : Base(b),
        data(d) {
  }
  Data data;
};

// These functions return true if there is some element in the sorted range
// [begin1, end) which is equal to some element in the sorted range [begin2,
// end2). The iterators do not have to be of the same type, but the value types
// must be less-than comparable. (Two elements a,b are considered equal if
// !(a < b) && !(b < a).
template<typename InputIterator1, typename InputIterator2>
bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1,
                                  InputIterator2 begin2, InputIterator2 end2) {
  assert(std::is_sorted(begin1, end1));
  assert(std::is_sorted(begin2, end2));
  while (begin1 != end1 && begin2 != end2) {
    if (*begin1 < *begin2) {
      ++begin1;
    } else if (*begin2 < *begin1) {
      ++begin2;
    } else {
      return true;
    }
  }
  return false;
}

// This is equivalent to the function above, but using a custom comparison
// function.
template<typename InputIterator1, typename InputIterator2, typename Comp>
bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1,
                                  InputIterator2 begin2, InputIterator2 end2,
                                  Comp comparator) {
  assert(std::is_sorted(begin1, end1, comparator));
  assert(std::is_sorted(begin2, end2, comparator));
  while (begin1 != end1 && begin2 != end2) {
    if (comparator(*begin1, *begin2)) {
      ++begin1;
    } else if (comparator(*begin2, *begin1)) {
      ++begin2;
    } else {
      return true;
    }
  }
  return false;
}

#endif  // UTIL_GTL_STL_UTIL_H_