Home | History | Annotate | Download | only in ceres 
      1 // Ceres Solver - A fast non-linear least squares minimizer
      2 // Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
      3 // http://code.google.com/p/ceres-solver/
      4 //
      5 // Redistribution and use in source and binary forms, with or without
      6 // modification, are permitted provided that the following conditions are met:
      7 //
      8 // * Redistributions of source code must retain the above copyright notice,
      9 //   this list of conditions and the following disclaimer.
     10 // * Redistributions in binary form must reproduce the above copyright notice,
     11 //   this list of conditions and the following disclaimer in the documentation
     12 //   and/or other materials provided with the distribution.
     13 // * Neither the name of Google Inc. nor the names of its contributors may be
     14 //   used to endorse or promote products derived from this software without
     15 //   specific prior written permission.
     16 //
     17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
     18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
     21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     27 // POSSIBILITY OF SUCH DAMAGE.
     28 //
     29 // Author: keir (at) google.com (Keir Mierle)
     30 
     31 #include "ceres/split.h"
     32 
     33 #include <string>
     34 #include <vector>
     35 #include <iterator>
     36 #include "ceres/internal/port.h"
     37 
     38 namespace ceres {
     39 
     40 // If we know how much to allocate for a vector of strings, we can allocate the
     41 // vector<string> only once and directly to the right size. This saves in
     42 // between 33-66 % of memory space needed for the result, and runs faster in the
     43 // microbenchmarks.
     44 //
     45 // The reserve is only implemented for the single character delim.
     46 //
     47 // The implementation for counting is cut-and-pasted from
     48 // SplitStringToIteratorUsing. I could have written my own counting iterator,
     49 // and use the existing template function, but probably this is more clear and
     50 // more sure to get optimized to reasonable code.
     51 static int CalculateReserveForVector(const string& full, const char* delim) {
     52   int count = 0;
     53   if (delim[0] != '\0' && delim[1] == '\0') {
     54     // Optimize the common case where delim is a single character.
     55     char c = delim[0];
     56     const char* p = full.data();
     57     const char* end = p + full.size();
     58     while (p != end) {
     59       if (*p == c) {  // This could be optimized with hasless(v,1) trick.
     60         ++p;
     61       } else {
     62         while (++p != end && *p != c) {
     63           // Skip to the next occurence of the delimiter.
     64         }
     65         ++count;
     66       }
     67     }
     68   }
     69   return count;
     70 }
     71 
     72 template <typename StringType, typename ITR>
     73 static inline
     74 void SplitStringToIteratorUsing(const StringType& full,
     75                                 const char* delim,
     76                                 ITR& result) {
     77   // Optimize the common case where delim is a single character.
     78   if (delim[0] != '\0' && delim[1] == '\0') {
     79     char c = delim[0];
     80     const char* p = full.data();
     81     const char* end = p + full.size();
     82     while (p != end) {
     83       if (*p == c) {
     84         ++p;
     85       } else {
     86         const char* start = p;
     87         while (++p != end && *p != c) {
     88           // Skip to the next occurence of the delimiter.
     89         }
     90         *result++ = StringType(start, p - start);
     91       }
     92     }
     93     return;
     94   }
     95 
     96   string::size_type begin_index, end_index;
     97   begin_index = full.find_first_not_of(delim);
     98   while (begin_index != string::npos) {
     99     end_index = full.find_first_of(delim, begin_index);
    100     if (end_index == string::npos) {
    101       *result++ = full.substr(begin_index);
    102       return;
    103     }
    104     *result++ = full.substr(begin_index, (end_index - begin_index));
    105     begin_index = full.find_first_not_of(delim, end_index);
    106   }
    107 }
    108 
    109 void SplitStringUsing(const string& full,
    110                       const char* delim,
    111                       vector<string>* result) {
    112   result->reserve(result->size() + CalculateReserveForVector(full, delim));
    113   back_insert_iterator< vector<string> > it(*result);
    114   SplitStringToIteratorUsing(full, delim, it);
    115 }
    116 
    117 }  // namespace ceres
    118