MakeIndex.h

Go to the documentation of this file.

#ifndef LARDATA_UTILITIES_MAKEINDEX_H
#define LARDATA_UTILITIES_MAKEINDEX_H

namespace util {
  
  template <typename Coll, typename KeyOf>
  std::vector<size_t> MakeIndex(Coll const& data, KeyOf key_of = KeyOf()) {
    
    // we start the index with the best guess that all the items will have
    // a unique key and they are contiguous:
    // the index would have the same size as the data
    std::vector<size_t> Index(data.size(), std::numeric_limits<size_t>::max());
    
    size_t min_size = 0; // minimum size needed to hold all keys
    
    size_t iDatum = 0;
    for (auto const& datum: data) {
      size_t key = size_t(key_of(datum));
      if (key >= min_size) min_size = key + 1;
      if (Index.size() <= key) {
        // make room for the entry: double the size
        Index.resize(
          std::max(key + 1, Index.size() * 2),
          std::numeric_limits<size_t>::max()
          );
      } // if expand index
      Index[key] = iDatum;
      ++iDatum;
    } // for datum
    Index.resize(min_size);
    return Index;
  } // MakeIndex()
  
  
  template <typename Coll, typename KeyOf>
  auto MakeMap(Coll const& data, KeyOf key_of = KeyOf())
    -> std::vector<decltype(key_of(*(data.begin()))) const*>
  {
    using Mapped_t = decltype(key_of(*(data.begin())));
    using Ptr_t = Mapped_t const*;
    using Map_t = std::vector<Ptr_t>;
    
    // we start the index with the best guess that all the items will have
    // a unique key and they are contiguous:
    // the index would have the same size as the data
    Map_t Index(data.size(), nullptr);
    
    size_t min_size = 0; // minimum size needed to hold all keys
    
    for (auto const& datum: data) {
      size_t key = size_t(key_of(datum));
      if (key >= min_size) min_size = key + 1;
      if (Index.size() <= key) {
        // make room for the entry: double the size
        Index.resize(std::max(key + 1, Index.size() * 2), nullptr);
      } // if expand index
      Index[key] = &datum;
    } // for datum
    Index.resize(min_size);
    return Index;
  } // MakeMap()
  
} // namespace util


#endif // LARDATA_UTILITIES_MAKEINDEX_H