strfind.cc

Go to the documentation of this file.

////////////////////////////////////////////////////////////////////////
//
// Copyright (C) 2009-2021 The Octave Project Developers
//
// See the file COPYRIGHT.md in the top-level directory of this
// distribution or <https://octave.org/copyright/>.
//
// This file is part of Octave.
//
// Octave is free software: you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Octave is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Octave; see the file COPYING.  If not, see
// <https://www.gnu.org/licenses/>.
//
////////////////////////////////////////////////////////////////////////
 
#if defined (HAVE_CONFIG_H)
#  include "config.h"
#endif
 
#include <algorithm>
#include <deque>
#include <limits>
#include <string>
 
#include "oct-locbuf.h"
 
#include "Cell.h"
#include "builtin-defun-decls.h"
#include "defun.h"
#include "errwarn.h"
#include "error.h"
#include "ov.h"
#include "unwind-prot.h"
#include "utils.h"
 
// This allows safe indexing with char.
// In C++, char may be (and often is) signed!
#define ORD(ch) static_cast<unsigned char>(ch)
#define TABSIZE (std::numeric_limits<unsigned char>::max () + 1)
 
// This is the quick search algorithm, as described at
// http://www-igm.univ-mlv.fr/~lecroq/string/node19.html
static void
qs_preprocess (const Array<char>& needle,
               octave_idx_type *table)
{
  const char *x = needle.data ();
  octave_idx_type m = needle.numel ();
 
  for (octave_idx_type i = 0; i < TABSIZE; i++)
    table[i] = m + 1;
  for (octave_idx_type i = 0; i < m; i++)
    table[ORD(x[i])] = m - i;
}
 
static Array<octave_idx_type>
qs_search (const Array<char>& needle,
           const Array<char>& haystack,
           const octave_idx_type *table,
           bool overlaps = true)
{
  const char *x = needle.data ();
  octave_idx_type m = needle.numel ();
  const char *y = haystack.data ();
  octave_idx_type n = haystack.numel ();
 
  // We'll use deque because it typically has the most favorable properties for
  // the operation we need.
  std::deque<octave_idx_type> accum;
  if (m == 1)
    {
      // Looking for a single character.
      for (octave_idx_type i = 0; i < n; i++)
        {
          if (y[i] == x[0])
            accum.push_back (i);
        }
    }
  else if (m == 2)
    {
      // Two characters.
      if (overlaps)
        {
          for (octave_idx_type i = 0; i < n-1; i++)
            {
              if (y[i] == x[0] && y[i+1] == x[1])
                accum.push_back (i);
            }
        }
      else
        {
          for (octave_idx_type i = 0; i < n-1; i++)
            {
              if (y[i] == x[0] && y[i+1] == x[1])
                accum.push_back (i++);
            }
        }
    }
  else if (n >= m)
    {
      // General case.
      octave_idx_type j = 0;
 
      if (overlaps)
        {
          while (j < n - m)
            {
              if (std::equal (x, x + m, y + j))
                accum.push_back (j);
              j += table[ORD(y[j + m])];
            }
        }
      else
        {
          while (j < n - m)
            {
              if (std::equal (x, x + m, y + j))
                {
                  accum.push_back (j);
                  j += m;
                }
              else
                j += table[ORD(y[j + m])];
            }
        }
 
      if (j == n - m && std::equal (x, x + m, y + j))
        accum.push_back (j);
    }
 
  octave_idx_type nmatch = accum.size ();
  octave_idx_type one = 1;
  Array<octave_idx_type> result (dim_vector (std::min (one, nmatch), nmatch));
  octave_idx_type k = 0;
  for (const auto& idx : accum)
    result.xelem (k++) = idx;
 
  return result;
}
 
DEFUN (strfind, args, ,
       doc: /* -*- texinfo -*-
@deftypefn  {} {@var{idx} =} strfind (@var{str}, @var{pattern})
@deftypefnx {} {@var{idx} =} strfind (@var{cellstr}, @var{pattern})
@deftypefnx {} {@var{idx} =} strfind (@dots{}, "overlaps", @var{val})
@deftypefnx {} {@var{idx} =} strfind (@dots{}, "forcecelloutput", @var{val})
Search for @var{pattern} in the string @var{str} and return the starting
index of every such occurrence in the vector @var{idx}.
 
If there is no such occurrence, or if @var{pattern} is longer than
@var{str}, or if @var{pattern} itself is empty, then @var{idx} is the empty
array @code{[]}.
 
The optional argument @qcode{"overlaps"} determines whether the pattern
can match at every position in @var{str} (true), or only for unique
occurrences of the complete pattern (false).  The default is true.
 
If a cell array of strings @var{cellstr} is specified then @var{idx} is a
cell array of vectors, as specified above.
 
The optional argument @qcode{"forcecelloutput"} forces @var{idx} to be
returned as a cell array of vectors.  The default is false.
 
Examples:
 
@example
@group
strfind ("abababa", "aba")
     @result{} [1, 3, 5]
@end group
 
@group
strfind ("abababa", "aba", "overlaps", false)
     @result{} [1, 5]
@end group
 
@group
strfind (@{"abababa", "bebebe", "ab"@}, "aba")
     @result{}
        @{
          [1,1] =
 
             1   3   5
 
          [1,2] = [](1x0)
          [1,3] = [](1x0)
        @}
@end group
 
@group
strfind ("abababa", "aba", "forcecelloutput", true)
     @result{}
        @{
          [1,1] =
 
             1   3   5
        @}
@end group
@end example
@seealso{regexp, regexpi, find}
@end deftypefn */)
{
  int nargin = args.length ();
 
  if (nargin != 4 && nargin != 2)
    print_usage ();
 
  bool overlaps = true;
  bool forcecelloutput = false;
  if (nargin == 4)
    {
      if (! args(2).is_string () || ! args(3).is_scalar_type ())
        error ("strfind: invalid optional arguments");
 
      std::string opt = args(2).string_value ();
      std::transform (opt.begin (), opt.end (), opt.begin (), tolower);
 
      if (opt == "overlaps")
        overlaps = args(3).bool_value ();
      else if (opt == "forcecelloutput")
        forcecelloutput = args(3).bool_value ();
      else
        error ("strfind: unknown option: %s", opt.c_str ());
    }
 
  octave_value retval;
 
  octave_value argstr = args(0);
  octave_value argpat = args(1);
 
  if (argpat.is_string ())
    {
      Array<char> needle = argpat.char_array_value ();
      OCTAVE_LOCAL_BUFFER (octave_idx_type, table, TABSIZE);
      qs_preprocess (needle, table);
 
      if (argstr.is_string ())
        {
          if (argpat.isempty ())
            // Return a null matrix for null pattern for MW compatibility
            retval = Matrix ();
          else
            retval = octave_value (qs_search (needle,
                                              argstr.char_array_value (),
                                              table, overlaps),
                                   true, true);
          if (forcecelloutput)
            retval = Cell (retval);
        }
      else if (argstr.iscell ())
        {
          const Cell argsc = argstr.cell_value ();
          Cell retc (argsc.dims ());
          octave_idx_type ns = argsc.numel ();
 
          for (octave_idx_type i = 0; i < ns; i++)
            {
              octave_value argse = argsc(i);
              if (! argse.is_string ())
                error ("strfind: each element of CELLSTR must be a string");
 
              if (argpat.isempty ())
                retc(i) = Matrix ();
              else
                retc(i) = octave_value (qs_search (needle,
                                                   argse.char_array_value (),
                                                   table, overlaps),
                                        true, true);
            }
 
          retval = retc;
        }
      else
        error ("strfind: first argument must be a string or cell array of strings");
    }
  else if (argpat.iscell ())
    retval = octave::do_simple_cellfun (Fstrfind, "strfind", args);
  else
    error ("strfind: PATTERN must be a string or cell array of strings");
 
  return retval;
}
 
/*
%!assert (strfind ("abababa", "aba"), [1, 3, 5])
%!assert (strfind ("abababa", "aba", "overlaps", false), [1, 5])
%!assert (strfind ("abababa", "aba", "forcecelloutput", false), [1, 3, 5])
%!assert (strfind ("abababa", "aba", "forcecelloutput", true), {[1, 3, 5]})
%!assert (strfind ({"abababa", "bla", "bla"}, "a"), {[1, 3, 5, 7], 3, 3})
%!assert (strfind ({"abababa", "bla", "bla"}, "a", "forcecelloutput", false), {[1, 3, 5, 7], 3, 3})
%!assert (strfind ({"abababa", "bla", "bla"}, "a", "forcecelloutput", true), {[1, 3, 5, 7], 3, 3})
%!assert (strfind ("Linux _is_ user-friendly. It just isn't ignorant-friendly or idiot-friendly.", "friendly"), [17, 50, 68])
%!assert (strfind ("abc", ""), [])
%!assert (strfind ("abc", {"", "b", ""}), {[], 2, []})
%!assert (strfind ({"abc", "def"}, ""), {[], []})
 
%!error strfind ()
%!error strfind ("foo", "bar", 1)
%!error <unknown option: foobar> strfind ("foo", 100, "foobar", 1)
%!error <each element of CELLSTR must be a string> strfind ({"A", 1}, "foo")
%!error <first argument must be a string> strfind (100, "foo")
%!error <PATTERN must be a string> strfind ("foo", 100)
*/
 
static Array<char>
qs_replace (const Array<char>& str, const Array<char>& pat,
            const Array<char>& rep,
            const octave_idx_type *table,
            bool overlaps = true)
{
  Array<char> ret = str;
 
  octave_idx_type siz = str.numel ();
  octave_idx_type psiz = pat.numel ();
  octave_idx_type rsiz = rep.numel ();
 
  if (psiz != 0)
    {
      // Look up matches, without overlaps.
      const Array<octave_idx_type> idx = qs_search (pat, str, table, overlaps);
      octave_idx_type nidx = idx.numel ();
 
      if (nidx)
        {
          // Compute result size.
          octave_idx_type retsiz;
          if (overlaps)
            {
              retsiz = 0;
              // OMG.  Is this the "right answer" MW always looks for, or
              // someone was just lazy?
              octave_idx_type k = 0;
              for (octave_idx_type i = 0; i < nidx; i++)
                {
                  octave_idx_type j = idx(i);
                  if (j >= k)
                    retsiz += j - k;
                  retsiz += rsiz;
                  k = j + psiz;
                }
 
              retsiz += siz - k;
            }
          else
            retsiz = siz + nidx * (rsiz - psiz);
 
          if (retsiz == 0)
            ret.clear (dim_vector (0, 0));
          else
            {
              ret.clear (dim_vector (1, retsiz));
              const char *src = str.data ();
              const char *reps = rep.data ();
              char *dest = ret.fortran_vec ();
 
              octave_idx_type k = 0;
              for (octave_idx_type i = 0; i < nidx; i++)
                {
                  octave_idx_type j = idx(i);
                  if (j >= k)
                    dest = std::copy (src + k, src + j, dest);
                  dest = std::copy (reps, reps + rsiz, dest);
                  k = j + psiz;
                }
 
              std::copy (src + k, src + siz, dest);
            }
        }
    }
 
  return ret;
}
 
DEFUN (strrep, args, ,
       doc: /* -*- texinfo -*-
@deftypefn  {} {@var{newstr} =} strrep (@var{str}, @var{ptn}, @var{rep})
@deftypefnx {} {@var{newstr} =} strrep (@var{cellstr}, @var{ptn}, @var{rep})
@deftypefnx {} {@var{newstr} =} strrep (@dots{}, "overlaps", @var{val})
Replace all occurrences of the pattern @var{ptn} in the string @var{str}
with the string @var{rep} and return the result.
 
The optional argument @qcode{"overlaps"} determines whether the pattern
can match at every position in @var{str} (true), or only for unique
occurrences of the complete pattern (false).  The default is true.
 
@var{s} may also be a cell array of strings, in which case the replacement
is done for each element and a cell array is returned.
 
Example:
 
@example
@group
strrep ("This is a test string", "is", "&%$")
    @result{}  "Th&%$ &%$ a test string"
@end group
@end example
 
@seealso{regexprep, strfind}
@end deftypefn */)
{
  int nargin = args.length ();
 
  if (nargin != 3 && nargin != 5)
    print_usage ();
 
  bool overlaps = true;
 
  if (nargin == 5)
    {
      if (! args(3).is_string () || ! args(4).is_scalar_type ())
        error ("strrep: invalid optional arguments");
 
      std::string opt = args(3).string_value ();
      if (opt == "overlaps")
        overlaps = args(4).bool_value ();
      else
        error ("strrep: unknown option: %s", opt.c_str ());
    }
 
  octave_value retval;
 
  octave_value argstr = args(0);
  octave_value argpat = args(1);
  octave_value argrep = args(2);
 
  if (argpat.is_string () && argrep.is_string ())
    {
      const Array<char> pat = argpat.char_array_value ();
      const Array<char> rep = argrep.char_array_value ();
 
      OCTAVE_LOCAL_BUFFER (octave_idx_type, table, TABSIZE);
      qs_preprocess (pat, table);
 
      if (argstr.is_string ())
        retval = qs_replace (argstr.char_array_value (), pat, rep,
                             table, overlaps);
      else if (argstr.iscell ())
        {
          const Cell argsc = argstr.cell_value ();
          Cell retc (argsc.dims ());
          octave_idx_type ns = argsc.numel ();
 
          for (octave_idx_type i = 0; i < ns; i++)
            {
              octave_value argse = argsc(i);
              if (argse.is_string ())
                retc(i) = qs_replace (argse.char_array_value (), pat, rep,
                                      table, overlaps);
              else
                error ("strrep: each element of S must be a string");
            }
 
          retval = retc;
        }
      else
        error ("strrep: S must be a string or cell array of strings");
    }
  else if (argpat.iscell () || argrep.iscell ())
    retval = octave::do_simple_cellfun (Fstrrep, "strrep", args);
  else
    error ("strrep: PTN and REP arguments must be strings or cell arrays of strings");
 
  return retval;
}
 
/*
%!assert (strrep ("This is a test string", "is", "&%$"),
%!                "Th&%$ &%$ a test string")
%!assert (strrep ("abababc", "abab", "xyz"), "xyzxyzc")
%!assert (strrep ("abababc", "abab", "xyz", "overlaps", false), "xyzabc")
 
%!assert (size (strrep ("a", "a", "")), [0 0])
 
%!error strrep ()
%!error strrep ("foo", "bar", 3, 4)
*/