slice_algo.hpp

Go to the documentation of this file.

/*
 
Copyright 2025 Matthew Tolman
 
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.
 
*/
 
#ifndef MTCORE_SLICE_ALGO_H
#define MTCORE_SLICE_ALGO_H
 
#include "optional.hpp"
#include "pair.hpp"
#include "slice.hpp"

namespace mtcore::slices {
  template<typename T>
  bool starts_with(const Slice<T> &needle, const Slice<T> &haystack) {
    if (needle.empty()) {
      mtcore_warn_trace("Empty needle provided!");
      return false;
    }
    if (needle.size() > haystack.size()) {
      return false;
    }
    ensure(needle.size() <= haystack.size(), "BAD SIZE COMP");
    for (size_t i = 0; i < needle.size(); ++i) {
      if (needle[i] != haystack[i]) {
        return false;
      }
    }
    return true;
  }

  template<typename T>
  void shift_right(Slice<T> slice, size_t amt) {
    for (size_t i = 0; i < slice.size() - amt; ++i) {
      auto destIndex = i + amt;
      if (destIndex < amt) {
        break;
      }
      auto srcIndex    = destIndex - amt;
      slice[destIndex] = slice[srcIndex];
    }
  }

  template<typename T>
  void shift_left(Slice<T> slice, size_t amt) {
    for (size_t i = slice.size(); i > 0; --i) {
      auto destIndex = i - amt;
      if (destIndex < amt) {
        break;
      }
      auto srcIndex    = destIndex - amt;
      slice[destIndex] = slice[srcIndex];
    }
  }

  template<typename T>
  bool starts_with(const std::remove_const_t<T> &needle, const Slice<T> &haystack) {
    if (haystack.empty()) {
      return false;
    }
    return haystack[0] == needle;
  }

  template<typename T>
  bool contains(const std::remove_const_t<T> &needle, const Slice<T> &haystack) {
    if (haystack.empty()) {
      return false;
    }
    for (size_t i = 0; i < haystack.size(); ++i) {
      if (needle == haystack[i]) {
        return true;
      }
    }
    return false;
  }

  template<typename T>
  bool contains(const Slice<T> &needle, const Slice<T> &haystack) {
    if (needle.empty()) {
      mtcore_warn_trace("Empty needle provided!");
      return false;
    }
    if (needle.size() > haystack.size()) {
      return false;
    }
    ensure(needle.size() <= haystack.size(), "BAD SIZE COMP");
    for (size_t i = 0; i < haystack.size() - needle.size() + 1; ++i) {
      if (needle[0] == haystack[i]) {
        bool looking = true;
        for (size_t ni = 1; looking && ni < needle.size(); ++ni) {
          if (needle[ni] != haystack[i + ni]) {
            looking = false;
          }
        }
        if (looking) {
          return true;
        }
      }
    }
    return false;
  }

  template<typename T>
  mtcore::Optional<size_t> first_index_not_proceeded_by(const std::remove_const_t<T> &prefix,
                                                        const std::remove_const_t<T> &needle,
                                                        const Slice<T> &haystack) {
    if (haystack.empty()) {
      return nullopt;
    }
    bool skip = false;
    for (size_t i = 0; i < haystack.size(); ++i) {
      if (skip) {
        skip = false;
        continue;
      }
      if (haystack[i] == prefix) {
        skip = true;
      }
      else if (needle == haystack[i]) {
        return i;
      }
    }
    return nullopt;
  }

  template<typename T>
  mtcore::Optional<size_t> first_index_not_proceeded_by(const std::remove_const_t<T> &prefix, const Slice<T> &needle,
                                                        const Slice<T> &haystack) {
    if (needle.empty()) {
      mtcore_warn_trace("Empty needle provided!");
      return nullopt;
    }
    if (needle.size() > haystack.size()) {
      return nullopt;
    }
    ensure(needle.size() <= haystack.size(), "BAD SIZE COMP");
    bool skip = false;
    for (size_t i = 0; i < haystack.size() - needle.size() + 1; ++i) {
      if (skip) {
        skip = false;
        continue;
      }
      if (haystack[i] == prefix) {
        skip = true;
      }
      else if (needle[0] == haystack[i]) {
        bool looking = true;
        for (size_t ni = 1; looking && ni < needle.size(); ++ni) {
          if (needle[ni] != haystack[i + ni]) {
            looking = false;
          }
        }
        if (looking) {
          return i;
        }
      }
    }
    return nullopt;
  }

  template<typename T>
  mtcore::Optional<size_t> first_index(const Slice<T> &needle, const Slice<T> &haystack) {
    if (needle.empty()) {
      mtcore_warn_trace("Empty needle provided!");
      return nullopt;
    }
    if (needle.size() > haystack.size()) {
      return nullopt;
    }
    ensure(needle.size() <= haystack.size(), "BAD SIZE COMP");
    for (size_t i = 0; i < haystack.size() - needle.size() + 1; ++i) {
      if (needle[0] == haystack[i]) {
        bool looking = true;
        for (size_t ni = 1; looking && ni < needle.size(); ++ni) {
          if (needle[ni] != haystack[i + ni]) {
            looking = false;
          }
        }
        if (looking) {
          return i;
        }
      }
    }
    return nullopt;
  }

  template<typename T>
  mtcore::Optional<size_t> first_index_one_of(const Slice<T> &needles, const Slice<T> &haystack) {
    if (needles.empty()) {
      mtcore_warn_trace("Empty needle provided!");
      return nullopt;
    }
    for (size_t i = 0; i < haystack.size(); ++i) {
      if (contains(haystack[i], needles)) {
        return i;
      }
    }
    return nullopt;
  }

  template<typename T>
  mtcore::Optional<size_t> first_index_not(const std::remove_const_t<T> &needle, const Slice<T> &haystack) {
    if (haystack.empty()) {
      return nullopt;
    }
 
    size_t i = 0;
    for (; i < haystack.size() && needle == haystack[i]; ++i) {}
 
    if (i >= haystack.size()) {
      return nullopt;
    }
    return i;
  }

  template<typename T>
  mtcore::Optional<size_t> first_index(const std::remove_const_t<T> &needle, const Slice<T> &haystack) {
    if (haystack.empty()) {
      return nullopt;
    }
    for (size_t i = 0; i < haystack.size(); ++i) {
      if (needle == haystack[i]) {
        return i;
      }
    }
    return nullopt;
  }

  template<typename T>
  mtcore::Optional<size_t> last_index(const Slice<T> &needle, const Slice<T> &haystack) {
    if (needle.empty()) {
      mtcore_warn_trace("Empty needle provided!");
      return nullopt;
    }
    if (needle.size() > haystack.size()) {
      return nullopt;
    }
    ensure(needle.size() <= haystack.size(), "BAD SIZE COMP");
    for (size_t indx = haystack.size() - needle.size() + 1; indx > 0; --indx) {
      const auto i = indx - 1;
      if (needle[0] == haystack[i]) {
        bool looking = true;
        for (size_t ni = 1; looking && ni < needle.size(); ++ni) {
          if (needle[ni] != haystack[i + ni]) {
            looking = false;
          }
        }
        if (looking) {
          return i;
        }
      }
    }
    return nullopt;
  }

  template<typename T>
  mtcore::Optional<size_t> last_index(const std::remove_const_t<T> &needle, const Slice<T> &haystack) {
    if (haystack.empty()) {
      return nullopt;
    }
    for (size_t indx = haystack.size(); indx > 0; --indx) {
      const auto i = indx - 1;
      if (needle == haystack[i]) {
        return i;
      }
    }
    return nullopt;
  }
 
  template<typename T, typename N>
  struct SearchIndexes {
    N needle;
    Slice<T> haystack;
    size_t cur = 0;
 
    Optional<size_t> next() {
      if (cur >= haystack.size()) {
        return nullopt;
      }
 
      auto nxt       = haystack.sub(cur);
      const auto opt = slices::first_index(needle, nxt);
      if (!opt.has_value()) {
        return nullopt;
      }
 
      mtdefer { cur += opt.value() + 1; };
      return cur + opt.value();
    }
  };

  template<typename T>
  SearchIndexes<T, Slice<T>> indexes_of(const Slice<T> &needle, const Slice<T> &haystack) {
    return {needle, haystack};
  }

  template<typename T>
  SearchIndexes<T, std::remove_const_t<T>> indexes_of(const std::remove_const_t<T> &needle, const Slice<T> &haystack) {
    return {needle, haystack};
  }

  template<typename T, typename N>
  struct SplitIter;
 
  template<typename T>
  struct SplitIter<T, Slice<T>> {
    Slice<T> needle;
    Slice<T> haystack;
    bool emittedLast = true;
 
    Optional<Slice<T>> next() {
      if (haystack.empty()) {
        if (emittedLast) {
          return nullopt;
        }
        emittedLast = true;
        return haystack;
      }
 
      auto nxt = first_index(needle, haystack);
      if (!nxt.has_value()) {
        emittedLast = true;
        auto res    = haystack;
        haystack    = haystack.sub(haystack.size());
        return res;
      }
 
      emittedLast = false;
      auto res    = haystack.sub(0, nxt.value());
      haystack    = haystack.sub(nxt.value() + needle.size());
      return res;
    }
  };
 
  template<typename T, typename N>
  struct SplitIter {
    N needle;
    Slice<T> haystack;
    bool emittedLast = true;
 
    Optional<Slice<T>> next() {
      if (haystack.empty()) {
        if (emittedLast) {
          return nullopt;
        }
        emittedLast = true;
        return haystack;
      }
 
      auto nxt = first_index(needle, haystack);
      if (!nxt.has_value()) {
        emittedLast = true;
        auto res    = haystack;
        haystack    = haystack.sub(haystack.size());
        return res;
      }
 
      emittedLast = false;
      auto res    = haystack.sub(0, nxt.value());
      haystack    = haystack.sub(nxt.value() + 1);
      return res;
    }
  };

  template<typename T>
  SplitIter<T, Slice<T>> split(const Slice<T> &needle, const Slice<T> &haystack) {
    return {needle, haystack};
  }

  template<typename T>
  SplitIter<T, std::remove_const_t<T>> split(const std::remove_const_t<T> &needle, const Slice<T> &haystack) {
    return {needle, haystack};
  }
 
  template<typename T>
  struct SplitOneOfIter {
    Slice<std::add_const_t<T>> needles;
    Slice<T> haystack;
    Optional<std::remove_const_t<T>> foundNeedle = nullopt;
    bool emittedLast                             = true;
 
    Optional<Pair<Slice<T>, Optional<std::remove_const_t<T>>>> next() {
      if (haystack.empty()) {
        mtdefer { emittedLast = true; };
        if (emittedLast) {
          return nullopt;
        }
        return make_pair(haystack, foundNeedle);
      }
 
      auto nxt = first_index_one_of(needles, haystack);
      if (!nxt.has_value()) {
        mtdefer {
          foundNeedle = nullopt;
          haystack    = haystack.sub(haystack.size());
          emittedLast = true;
        };
        return make_pair(haystack, foundNeedle);
      }
 
      mtdefer {
        foundNeedle = haystack[nxt.value()];
        haystack    = haystack.sub(nxt.value() + 1);
        emittedLast = false;
      };
 
      return make_pair(haystack.sub(0, nxt.value()), foundNeedle);
    }
  };

  template<typename T>
  SplitOneOfIter<T> split_one_of(const Slice<std::add_const_t<T>> &needles, const Slice<T> &haystack) {
    return {needles, haystack};
  }
}  // namespace mtcore::slices
 
#endif  // MTCORE_SLICE_ALGO_H