Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set

// doxy/ or-tools/ src/ util/

or-tools/src/util/vector_map.h

Go to the documentation of this file.

// Copyright 2010-2012 Google
// Licensed 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.

// Vector with map from element to index in the vector.

#ifndef OR_TOOLS_UTIL_VECTOR_MAP_H_
#define OR_TOOLS_UTIL_VECTOR_MAP_H_

#include "base/hash.h"
#include <vector>
#include "base/map-util.h"

namespace operations_research {

// This class stores a vector of distinct elements, as well as a map
// from elements to index to find the index in the vector.
// This is useful to store mapping between objects and indices.
template <class T> class VectorMap {
 public:
  // Adds an element if not already present, and returns its index in
  // the vector-map.
  int Add(const T& element) {
    int current_index = Index(element);
    if (current_index != -1) {
      return current_index;
    }
    const int index = list_.size();
    CHECK_EQ(index, map_.size());
    list_.push_back(element);
    map_[element] = index;
    return index;
  }
  // TODO(user): Use ArraySlice.

  // Adds all elements of the vector.
  void Add(const std::vector<T>& elements) {
    for (int i = 0; i < elements.size(); ++i) {
      Add(elements[i]);
    }
  }

  // Returns -1 if the element is not in the vector, or its unique
  // index if it is.
  int Index(const T& element) const {
    return FindWithDefault(map_, element, -1);
  }
  // TODO(user): explore a int-type version.

  // Returns wether the element has already been added to the vector-map.
  bool Contains(const T& element) const {
    return ContainsKey(map_, element);
  }

  // Returns the element at position index.
  const T& Element(int index) const {
    CHECK_GE(index, 0);
    CHECK_LT(index, list_.size());
    return list_[index];
  }

  // Returns the number of distinct elements added to the vector-map.
  int size() const { return list_.size(); }

  // Clears all the elements added to the vector-map.
  void clear() {
    list_.clear();
    map_.clear();
  }

  // Returns a read-only access to the vector of elements.
  const std::vector<T>& list() const { return list_; }

  // Standard STL container boilerplate.
  typedef T value_type;
  typedef const T* pointer;
  typedef const T& reference;
  typedef const T& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  static const size_type npos;
  typedef const T* const_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  const_iterator begin() const { return list_.data(); }
  const_iterator end() const { return list_.data() + list_.size(); }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(list_.data() + list_.size());
  }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(list_.data());
  }

 private:
  std::vector<T> list_;
  hash_map<T, int> map_;
};

}  // namespace operations_research
#endif  // OR_TOOLS_UTIL_VECTOR_MAP_H_