src/Utility/vmap.cpp

Go to the documentation of this file.

// -*- C++ -*-
/***************************************************************************
 *
 * The IPPL Framework
 * 
 * This program was prepared by PSI. 
 * All rights in the program are reserved by PSI.
 * Neither PSI nor the author(s)
 * makes any warranty, express or implied, or assumes any liability or
 * responsibility for the use of this software
 *
 * Visit http://www.acl.lanl.gov/POOMS for more details
 *
 ***************************************************************************/

// -*- C++ -*-
/***************************************************************************
 *
 * The IPPL Framework
 * 
 *
 * Visit http://people.web.psi.ch/adelmann/ for more details
 *
 ***************************************************************************/

// include files
#include "Utility/vmap.h"
#include "Profile/Profiler.h"

#ifdef IPPL_STDSTL
#include <algorithm>
using std::lower_bound;
using std::upper_bound;
using std::equal_range;
#else
#include <algo.h>
#endif

//
// Copy ctor
//
template<class Key, class T, class Compare>
vmap<Key,T,Compare>::vmap( const vmap<Key,T,Compare>& x_ac )
  : Lt(x_ac.Lt)                 // Copy the comparison object.
{
  TAU_TYPE_STRING(taustr, "void (" + CT(x_ac) + " )" );
  TAU_PROFILE("vmap::vmap()", taustr, TAU_UTILITY );
  V_c = x_ac.V_c;               // Copy the vector of data.
}

//
// Assignment
//
template<class Key, class T, class Compare>
vmap<Key,T,Compare>&
vmap<Key,T,Compare>::operator=( const vmap<Key,T,Compare>& x_ac )
{
  TAU_TYPE_STRING(taustr, "void (" + CT(x_ac) + " )" );
  TAU_PROFILE("vmap::operator=()", taustr, TAU_UTILITY );
  Lt = x_ac.Lt;                 // Copy the comparison object.
  V_c = x_ac.V_c;               // Copy the vector of data.
  return *this;
}

//
// Insert operations.
//

//
// Insert a single value.
// Return ptr to the inserted and a bool for success.
//

template<class Key, class T, class Compare>
pair<typename vmap<Key,T,Compare>::iterator,bool>
vmap<Key,T,Compare>::insert(const value_type& value)
{
  iterator f_i;
  TAU_TYPE_STRING(taustr, "pair<" + CT(f_i) + ", bool> (value_type )" );
  TAU_PROFILE("vmap::insert()", taustr, TAU_UTILITY );

  bool success;
  f_i = lower_bound( value.first );            // Look for it.
  if ( f_i == end() )                          // Are we at the end?
    {                                          // Yes, we can't deref f_i.
      V_c.push_back(value);                    // Append. Could realloc
      f_i = begin() + size() - 1;
      success = true;
    } 
  // BFH: Ge -> Le
  else if ( Le((*f_i).first,value.first))      // Did you find it?
    {
      success = false;
    }
  else 
    {
      size_type n = f_i - begin();             // Not there, remember location.
      V_c.insert( f_i , value );               // Insert. Could cause realloc.
      f_i = begin() + n;
      success = true;
    }
  return pair<iterator,bool>(f_i,success);     // Return ptr to inserted.
}

//
// Insert a single value given a hint for where it should go.
// It is robust: even if the hint is wrong it will insert in the right place.
// If you start with values sorted in increasing order and give it 
// end() as the hint then it will insert in constant time.
// Return a ptr to the inserted position.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::iterator
vmap<Key,T,Compare>::insert(iterator hint_i, const value_type& value)
{
  TAU_TYPE_STRING(taustr, CT(hint_i) + " (" + CT(hint_i) + ", value_type )" );
  TAU_PROFILE("vmap::insert()", taustr, TAU_UTILITY );
  iterator low_i = begin();     // The bounds for the search range
  iterator high_i = end();      // to find where to really put it.
  if ( hint_i == high_i )       // Is the hint to append?
    if ( empty() || Ge( value.first , hint_i[-1].first ) ) // Is that right?
      {                         // Yes!
        V_c.push_back(value);   // Quick append.  Could cause realloc!
        return end()-1;         // return where we put it.
      }
  else                                          // Hint is not for append.
    if ( Lt(value.first,(*hint_i).first) )      // Is it to the left?
      high_i = hint_i;                          //   range = (begin,hint)
    else                                        // It is to the right.
      low_i = hint_i;                           //   range = (hint,end)

  // Given the range figured out above, find where to really put it.
  hint_i = ::upper_bound( low_i, high_i, value, value_compare(Lt) );
  size_type n = hint_i - begin();            // Remember the location.
  V_c.insert(hint_i,value);                  // Insert here, could realloc.
  return V_c.begin() + n;                    // return iterator.
}

//
// Insert a range of values, with append as the hint.
// If the values being inserted are sorted and all greater than or equal
// to the elements in the vmap this works out to a fast append.
//

template<class Key, class T, class Compare>
void
vmap<Key,T,Compare>::insert(const value_type *first_i,const value_type *last_i)
{
  TAU_TYPE_STRING(taustr, CT(*this) + "void (value_type, value_type )" );
  TAU_PROFILE("vmap::insert()", taustr, TAU_UTILITY );
  for (; first_i != last_i; ++first_i)
    insert( end() , *first_i );
}

//
// erase operations.
//

//
// Erase a single element.
//

template<class Key, class T, class Compare>
void
vmap<Key,T,Compare>::erase(iterator p_i)
{
  TAU_TYPE_STRING(taustr, " void (" + CT(p_i) + " )" );
  TAU_PROFILE("vmap::erase()", taustr, TAU_UTILITY );
  V_c.erase(p_i);
}

//
// Erase a range of elements.
//

template<class Key, class T, class Compare>
void
vmap<Key,T,Compare>::erase(iterator first_i, iterator last_i)
{
  TAU_TYPE_STRING(taustr, " void (" + CT(first_i) + ", " + CT(last_i) + " )" );
  TAU_PROFILE("vmap::erase()", taustr, TAU_UTILITY );
  V_c.erase(first_i, last_i);
}

//
// Erase all the values with key equal to the given.
// Return the number erased.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::size_type
vmap<Key,T,Compare>::erase(const key_type& key)
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::size_type (key_type )" );
  TAU_PROFILE("vmap::erase()", taustr, TAU_UTILITY );
  pair<iterator,iterator> range( equal_range(key) );
  erase(range.first, range.second);
  return range.second - range.first;
}

//
// Map operations.
//

//
// Find a value if it is there.
// Return end() if it is not.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::iterator
vmap<Key,T,Compare>::find(const key_type& key)
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::iterator (key_type )" );
  TAU_PROFILE("vmap::find()", taustr, TAU_UTILITY );
  iterator f_i = lower_bound(key); // Look for it.
  if ( f_i == end() )              // Are we at the end?
    return end();                  //   Yes, don't try to deref.
  // BFH: Ge -> Le
  if ( Le((*f_i).first , key) )    // Did you find it?
    return f_i;                    //   yes, return it.
  else                             // or...
    return end();                  //   no, return end().
}

//
// Return ptr to the first element that is >= the given one.
// Can also think of it as the first place it could be put
// without violating the sequence.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::iterator
vmap<Key,T,Compare>::lower_bound(const key_type& key)
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::iterator (key_type )" );
  TAU_PROFILE("vmap::lower_bound()", taustr, TAU_UTILITY );
  return ::lower_bound(begin(),end(),value_type(key,T()),value_compare(Lt));
}

//
// Return ptr to the first element > the given one.
// Can also think of it as the last place it could be put
// without violating the sequence.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::iterator
vmap<Key,T,Compare>::upper_bound(const key_type& key)
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::iterator (key_type )" );
  TAU_PROFILE("vmap::upper_bound()", taustr, TAU_UTILITY );
  return ::upper_bound(begin(),end(),value_type(key,T()),value_compare(Lt));
}

//
// Return a lower_bound, upper_bound pair.
//

template<class Key, class T, class Compare>
pair<typename vmap<Key,T,Compare>::iterator,
     typename vmap<Key,T,Compare>::iterator>
vmap<Key,T,Compare>::equal_range(const key_type& key)
{
  TAU_TYPE_STRING(taustr, "pair<" + CT(*this) + "::iterator, " + CT(*this) 
    + "::iterator> (key_type )" );
  TAU_PROFILE("vmap::equal_range()", taustr, TAU_UTILITY );
  return ::equal_range(begin(),end(),value_type(key,T()),value_compare(Lt));
}

//
// Look up an element given a key.
// If there is not one there already, make space for it.
//

template<class Key, class T, class Compare>
T&
vmap<Key,T,Compare>::operator[](const key_type& key)
{
  TAU_TYPE_STRING(taustr, CT(*this) + " T (key_type )" );
  TAU_PROFILE("vmap::operator[]()", taustr, TAU_UTILITY );
  size_type n;                  // We will need to calculate the offset.
  iterator f_i;                 // Pointer to the data we find.
  if ( V_c.empty() )            // Is there anything here?
    {                           //    No.  Can't dereference.
      n = 0;                    //    The new one will be at the beginning.
      f_i = begin();            //    Point to the beginning.
    }
  else                                 // Yes, there is something here.
    {                                  // 
      f_i = lower_bound(key);          // Search the whole range.
      // BFH: Ge -> Le
      if ((f_i!=end()) && Le((*f_i).first,key)) // Did we find this one?
        return (*f_i).second;          //    Yes, return ref to data.
      n = f_i - begin();               // Not there, remember location.
    }
  V_c.insert( f_i , value_type(key,T()) ); // Insert. Could cause realloc.
  return V_c[n].second;                    // Return ref to data.
}

//
// Const map operations.
//

//
// Find how many have the given key.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::size_type
vmap<Key,T,Compare>::count(const key_type& key) const
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::size_type (key_type )" );
  TAU_PROFILE("vmap::count()", taustr, TAU_UTILITY );
  pair<const_iterator,const_iterator>
    range( equal_range(key) );       // Find the bounds.
  return range.second - range.first; // Difference to get the count.
}

//
// Find a value if it is there.
// Return end() if it is not.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::const_iterator
vmap<Key,T,Compare>::find(const key_type& key) const
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::const_iterator (key_type )" );
  TAU_PROFILE("vmap::find()", taustr, TAU_UTILITY );
  const_iterator f_i = lower_bound(key); // Look for it.
  // BFH: Ge -> Le
  if ( Le((*f_i).first , key ))          // Did you find it?
    return f_i;                          //   yes, return it.
  else                                   // or...
    return end();                        //   no, return end().
}

//
// Return ptr to the first element that is >= the given one.
// Can also think of it as the first place it could be put
// without violating the sequence.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::const_iterator
vmap<Key,T,Compare>::lower_bound(const key_type& key) const
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::const_iterator (key_type )" );
  TAU_PROFILE("vmap::lower_bound()", taustr, TAU_UTILITY );
  return ::lower_bound(begin(),end(),value_type(key,T()),value_compare(Lt));
}

//
// Return ptr to the first element > the given one.
// Can also think of it as the last place it could be put
// without violating the sequence.
//

template<class Key, class T, class Compare>
typename vmap<Key,T,Compare>::const_iterator
vmap<Key,T,Compare>::upper_bound(const key_type& key) const
{
  TAU_TYPE_STRING(taustr, CT(*this) + "::const_iterator (key_type )" );
  TAU_PROFILE("vmap::upper_bound()", taustr, TAU_UTILITY );
  return ::upper_bound(begin(),end(),value_type(key,T()),value_compare(Lt));
}

//
// Return a lower_bound, upper_bound pair.
//

template<class Key, class T, class Compare>
pair<typename vmap<Key,T,Compare>::const_iterator,
     typename vmap<Key,T,Compare>::const_iterator>
vmap<Key,T,Compare>::equal_range(const key_type& key) const
{
  TAU_TYPE_STRING(taustr, "pair<" + CT(*this) + "::const_iterator, " 
    + CT(*this) + "::const_iterator> (key_type )" );
  TAU_PROFILE("vmap::equal_range()", taustr, TAU_UTILITY );
  return ::equal_range(begin(),end(),value_type(key,T()),value_compare(Lt));
}


//
// Look up an element given a key.
// Scream and die if it is not there.
//

template<class Key, class T, class Compare>
const T&
vmap<Key,T,Compare>::operator[](const key_type& key) const
{
  TAU_TYPE_STRING(taustr, CT(*this) + " T (key_type )" );
  TAU_PROFILE("vmap::operator[]()", taustr, TAU_UTILITY );
  const_iterator f_i = lower_bound(key);   // Search the whole range.
  return (*f_i).second;              // Return what you found.
}

/***************************************************************************
 * $RCSfile: vmap.cpp,v $   $Author: adelmann $
 * $Revision: 1.1.1.1 $   $Date: 2003/01/23 07:40:34 $
 * IPPL_VERSION_ID: $Id: vmap.cpp,v 1.1.1.1 2003/01/23 07:40:34 adelmann Exp $ 
 ***************************************************************************/

---