10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 20ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Copyright 2010, 2011, 2012 Google Inc. All rights reserved. 30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/ 40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without 60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met: 70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice, 90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer. 100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice, 110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer in the documentation 120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and/or other materials provided with the distribution. 130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be 140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// used to endorse or promote products derived from this software without 150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// specific prior written permission. 160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE. 280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: keir@google.com (Keir Mierle) 300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Originally by Anton Carver 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifndef CERES_INTERNAL_MAP_UTIL_H_ 340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#define CERES_INTERNAL_MAP_UTIL_H_ 350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <utility> 370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/port.h" 381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "glog/logging.h" 390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Perform a lookup in a map or hash_map, assuming that the key exists. 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Crash if it does not. 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// This is intended as a replacement for operator[] as an rvalue (for reading) 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// when the key is guaranteed to exist. 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// operator[] is discouraged for several reasons: 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * It has a side-effect of inserting missing keys 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * It is not thread-safe (even when it is not inserting, it can still 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// choose to resize the underlying storage) 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * It invalidates iterators (when it chooses to resize) 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * It default constructs a value object even if it doesn't need to 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// This version assumes the key is printable, and includes it in the fatal log 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// message. 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate <class Collection> 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongconst typename Collection::value_type::second_type& 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongFindOrDie(const Collection& collection, 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::first_type& key) { 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong typename Collection::const_iterator it = collection.find(key); 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CHECK(it != collection.end()) << "Map key not found: " << key; 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return it->second; 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Perform a lookup in a map or hash_map. 670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// If the key is present in the map then the value associated with that 680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// key is returned, otherwise the value passed as a default is returned. 690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate <class Collection> 700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongconst typename Collection::value_type::second_type& 710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongFindWithDefault(const Collection& collection, 720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::first_type& key, 730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::second_type& value) { 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong typename Collection::const_iterator it = collection.find(key); 750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (it == collection.end()) { 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return value; 770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return it->second; 790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Insert a new key and value into a map or hash_map. 820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// If the key is not present in the map the key and value are 830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// inserted, otherwise nothing happens. True indicates that an insert 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// took place, false indicates the key was already present. 850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate <class Collection> 860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongbool InsertIfNotPresent( 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Collection * const collection, 880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::first_type& key, 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::second_type& value) { 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong pair<typename Collection::iterator, bool> ret = 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong collection->insert(typename Collection::value_type(key, value)); 920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return ret.second; 930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Perform a lookup in a map or hash_map. 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Same as above but the returned pointer is not const and can be used to change 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// the stored value. 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate <class Collection> 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtypename Collection::value_type::second_type* 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongFindOrNull(Collection& collection, // NOLINT 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::first_type& key) { 1020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong typename Collection::iterator it = collection.find(key); 1030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (it == collection.end()) { 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return 0; 1050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return &it->second; 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Test to see if a set, map, hash_set or hash_map contains a particular key. 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Returns true if the key is in the collection. 1110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate <class Collection, class Key> 1120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongbool ContainsKey(const Collection& collection, const Key& key) { 1130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong typename Collection::const_iterator it = collection.find(key); 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return it != collection.end(); 1150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Inserts a new key/value into a map or hash_map. 1180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Dies if the key is already present. 1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate<class Collection> 1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongvoid InsertOrDie(Collection* const collection, 1210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::first_type& key, 1220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const typename Collection::value_type::second_type& data) { 1230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong typedef typename Collection::value_type value_type; 1240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CHECK(collection->insert(value_type(key, data)).second) 1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "duplicate key: " << key; 1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 1290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif // CERES_INTERNAL_MAP_UTIL_H_ 131