<commit_before>/**
 * @license
 * Copyright 2021 <NAME>
 * 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.
 */

/*
 * Connected Components for 2D images. 

 * Author: <NAME>
 * Affiliation: Seung Lab, Princeton University
 * Date: August 2018 - June 2019, June 2021
 *
 * ----
 * Notes on the license:
 * 
 * This is a special reduced feature version of cc3d 
 * that includes only the logic needed for CCL 4-connected
 * and 6-connected. It is also modified to treat black as 
 * foreground and black as background. 
 * 
 * cc3d is ordinarily licensed as GPL v3. 
 * Get the full version of cc3d here: 
 * 
 * https://github.com/seung-lab/connected-components-3d
 */

#ifndef CC3D_SPECIAL_4_HPP
#define CC3D_SPECIAL_4_HPP 

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <stdexcept>

namespace cc3d {

static size_t _dummy_N;

template <typename T>
class DisjointSet {
public:
  T *ids;
  size_t length;

  DisjointSet () {
    length = 65536; // 2^16, some "reasonable" starting size
    ids = new T[length]();
  }

  DisjointSet (size_t len) {
    length = len;
    ids = new T[length]();
  }

  DisjointSet (const DisjointSet &cpy) {
    length = cpy.length;
    ids = new T[length]();

    for (int i = 0; i < length; i++) {
      ids[i] = cpy.ids[i];
    }
  }

  ~DisjointSet () {
    delete []ids;
  }

  T root (T n) {
    T i = ids[n];
    while (i != ids[i]) {
      ids[i] = ids[ids[i]]; // path compression
      i = ids[i];
    }

    return i;
  }

  bool find (T p, T q) {
    return root(p) == root(q);
  }

  void add(T p) {
    if (ids[p] == 0) {
      ids[p] = p;
    }
  }

  void unify (T p, T q) {
    if (p == q) {
      return;
    }

    T i = root(p);
    T j = root(q);

    if (i == 0) {
      add(p);
      i = p;
    }

    if (j == 0) {
      add(q);
      j = q;
    }

    ids[i] = j;
  }

  // would be easy to write remove. 
  // Will be O(n).
};

// This is the second raster pass of the two pass algorithm family.
// The input array (output_labels) has been assigned provisional 
// labels and this resolves them into their final labels. We
// modify this pass to also ensure that the output labels are
// numbered from 1 sequentially.
template <typename OUT = uint32_t>
OUT* relabel(
    OUT* out_labels, const int64_t voxels,
    const int64_t num_labels, DisjointSet<uint32_t> &equivalences,
    size_t &N = _dummy_N, OUT start_label = 1
  ) {

  OUT label;
  OUT* renumber = new OUT[num_labels + 1]();
  OUT next_label = start_label;

  for (int64_t i = 1; i <= num_labels; i++) {
    label = equivalences.root(i);
    if (renumber[label] == 0) {
      renumber[label] = next_label;
      renumber[i] = next_label;
      next_label++;
    }
    else {
      renumber[i] = renumber[label];
    }
  }

  // Raster Scan 2: Write final labels based on equivalences
  N = next_label - start_label;
  if (N < static_cast<size_t>(num_labels) || start_label != 1) {
    for (int64_t loc = 0; loc < voxels; loc++) {
      out_labels[loc] = renumber[out_labels[loc]];
    }
  }

  delete[] renumber;

  return out_labels;
}

template <typename OUT = uint32_t>
OUT* connected_components2d_4(
    bool* in_labels, 
    const int64_t sx, const int64_t sy, const int64_t sz,
    size_t max_labels, OUT *out_labels = NULL, 
    size_t &N = _dummy_N, OUT start_label = 1
  ) {

  const int64_t sxy = sx * sy;
  const int64_t voxels = sx * sy * sz;

  max_labels++;
  max_labels = std::min(max_labels, static_cast<size_t>(voxels) + 1); // + 1L for an array with no zeros
  max_labels = std::min(max_labels, static_cast<size_t>(std::numeric_limits<OUT>::max()));


  DisjointSet<uint32_t> equivalences(max_labels);

  if (out_labels == NULL) {<commit_msg>refactor: use unique_ptr for renumber<commit_after>/**
 * @license
 * Copyright 2021 <NAME>
 * 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.
 */

/*
 * Connected Components for 2D images. 

 * Author: <NAME>
 * Affiliation: Seung Lab, Princeton University
 * Date: August 2018 - June 2019, June 2021
 *
 * ----
 * Notes on the license:
 * 
 * This is a special reduced feature version of cc3d 
 * that includes only the logic needed for CCL 4-connected
 * and 6-connected. It is also modified to treat black as 
 * foreground and black as background. 
 * 
 * cc3d is ordinarily licensed as GPL v3. 
 * Get the full version of cc3d here: 
 * 
 * https://github.com/seung-lab/connected-components-3d
 */

#ifndef CC3D_SPECIAL_4_HPP
#define CC3D_SPECIAL_4_HPP 

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <stdexcept>

namespace cc3d {

static size_t _dummy_N;

template <typename T>
class DisjointSet {
public:
  T *ids;
  size_t length;

  DisjointSet () {
    length = 65536; // 2^16, some "reasonable" starting size
    ids = new T[length]();
  }

  DisjointSet (size_t len) {
    length = len;
    ids = new T[length]();
  }

  DisjointSet (const DisjointSet &cpy) {
    length = cpy.length;
    ids = new T[length]();

    for (int i = 0; i < length; i++) {
      ids[i] = cpy.ids[i];
    }
  }

  ~DisjointSet () {
    delete []ids;
  }

  T root (T n) {
    T i = ids[n];
    while (i != ids[i]) {
      ids[i] = ids[ids[i]]; // path compression
      i = ids[i];
    }

    return i;
  }

  bool find (T p, T q) {
    return root(p) == root(q);
  }

  void add(T p) {
    if (ids[p] == 0) {
      ids[p] = p;
    }
  }

  void unify (T p, T q) {
    if (p == q) {
      return;
    }

    T i = root(p);
    T j = root(q);

    if (i == 0) {
      add(p);
      i = p;
    }

    if (j == 0) {
      add(q);
      j = q;
    }

    ids[i] = j;
  }

  // would be easy to write remove. 
  // Will be O(n).
};

// This is the second raster pass of the two pass algorithm family.
// The input array (output_labels) has been assigned provisional 
// labels and this resolves them into their final labels. We
// modify this pass to also ensure that the output labels are
// numbered from 1 sequentially.
template <typename OUT = uint32_t>
OUT* relabel(
    OUT* out_labels, const int64_t voxels,
    const int64_t num_labels, DisjointSet<uint32_t> &equivalences,
    size_t &N = _dummy_N, OUT start_label = 1
  ) {

  OUT label;
  std::unique_ptr<OUT[]> renumber(new OUT[num_labels + 1]());
  OUT next_label = start_label;

  for (int64_t i = 1; i <= num_labels; i++) {
    label = equivalences.root(i);
    if (renumber[label] == 0) {
      renumber[label] = next_label;
      renumber[i] = next_label;
      next_label++;
    }
    else {
      renumber[i] = renumber[label];
    }
  }

  // Raster Scan 2: Write final labels based on equivalences
  N = next_label - start_label;
  if (N < static_cast<size_t>(num_labels) || start_label != 1) {
    for (int64_t loc = 0; loc < voxels; loc++) {
      out_labels[loc] = renumber[out_labels[loc]];
    }
  }

  return out_labels;
}

template <typename OUT = uint32_t>
OUT* connected_components2d_4(
    bool* in_labels, 
    const int64_t sx, const int64_t sy, const int64_t sz,
    size_t max_labels, OUT *out_labels = NULL, 
    size_t &N = _dummy_N, OUT start_label = 1
  ) {

  const int64_t sxy = sx * sy;
  const int64_t voxels = sx * sy * sz;

  max_labels++;
  max_labels = std::min(max_labels, static_cast<size_t>(voxels) + 1); // + 1L for an array with no zeros
  max_labels = std::min(max_labels, static_cast<size_t>(std::numeric_limits<OUT>::max()));


  DisjointSet<uint32_t> equivalences(max_labels);

  if (out_labels == NULL) {
{'fraction_non_alphanumeric': 0.12130563798219585, 'fraction_numerical': 0.019940652818991097, 'mean_word_length': 2.816123188405797, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 34, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2881368', 'n_tokens_mistral': 3133, 'n_tokens_neox': 2907, 'n_words': 963}