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#include <string> 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <vector> 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <iterator> 340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/port.h" 350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// If we know how much to allocate for a vector of strings, we can allocate the 390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// vector<string> only once and directly to the right size. This saves in 400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// between 33-66 % of memory space needed for the result, and runs faster in the 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// microbenchmarks. 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// The reserve is only implemented for the single character delim. 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// The implementation for counting is cut-and-pasted from 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SplitStringToIteratorUsing. I could have written my own counting iterator, 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and use the existing template function, but probably this is more clear and 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// more sure to get optimized to reasonable code. 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongstatic int CalculateReserveForVector(const string& full, const char* delim) { 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int count = 0; 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (delim[0] != '\0' && delim[1] == '\0') { 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Optimize the common case where delim is a single character. 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong char c = delim[0]; 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const char* p = full.data(); 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const char* end = p + full.size(); 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong while (p != end) { 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (*p == c) { // This could be optimized with hasless(v,1) trick. 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ++p; 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } else { 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong while (++p != end && *p != c) { 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Skip to the next occurence of the delimiter. 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ++count; 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return count; 680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate <typename StringType, typename ITR> 710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongstatic inline 720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongvoid SplitStringToIteratorUsing(const StringType& full, 730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const char* delim, 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ITR& result) { 750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Optimize the common case where delim is a single character. 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (delim[0] != '\0' && delim[1] == '\0') { 770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong char c = delim[0]; 780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const char* p = full.data(); 790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const char* end = p + full.size(); 800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong while (p != end) { 810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (*p == c) { 820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ++p; 830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } else { 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const char* start = p; 850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong while (++p != end && *p != c) { 860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Skip to the next occurence of the delimiter. 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *result++ = StringType(start, p - start); 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string::size_type begin_index, end_index; 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong begin_index = full.find_first_not_of(delim); 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong while (begin_index != string::npos) { 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong end_index = full.find_first_of(delim, begin_index); 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (end_index == string::npos) { 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *result++ = full.substr(begin_index); 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *result++ = full.substr(begin_index, (end_index - begin_index)); 1030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong begin_index = full.find_first_not_of(delim, end_index); 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongvoid SplitStringUsing(const string& full, 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const char* delim, 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong vector<string>* result) { 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong result->reserve(result->size() + CalculateReserveForVector(full, delim)); 1110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong back_insert_iterator< vector<string> > it(*result); 1120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong SplitStringToIteratorUsing(full, delim, it); 1130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 116