--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mupdf-source/thirdparty/tesseract/src/training/common/intfeaturemap.cpp	Mon Sep 15 11:43:07 2025 +0200
@@ -0,0 +1,241 @@
+// Copyright 2010 Google Inc. All Rights Reserved.
+// Author: rays@google.com (Ray Smith)
+///////////////////////////////////////////////////////////////////////
+// File:        intfeaturemap.cpp
+// Description: Encapsulation of IntFeatureSpace with IndexMapBiDi
+//              to provide a subspace mapping and fast feature lookup.
+//
+// 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.
+//
+///////////////////////////////////////////////////////////////////////
+
+#include "intfeaturemap.h"
+
+#include "intfeaturespace.h"
+#include "intfx.h"
+// These includes do not exist yet, but will be coming soon.
+//#include "sampleiterator.h"
+//#include "trainingsample.h"
+//#include "trainingsampleset.h"
+
+namespace tesseract {
+
+const int kMaxOffsetDist = 32;
+
+IntFeatureMap::IntFeatureMap() : mapping_changed_(true), compact_size_(0) {
+  for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
+    offset_plus_[dir] = nullptr;
+    offset_minus_[dir] = nullptr;
+  }
+}
+
+IntFeatureMap::~IntFeatureMap() {
+  Clear();
+}
+
+// Pseudo-accessors.
+int IntFeatureMap::IndexFeature(const INT_FEATURE_STRUCT &f) const {
+  return feature_space_.Index(f);
+}
+int IntFeatureMap::MapFeature(const INT_FEATURE_STRUCT &f) const {
+  return feature_map_.SparseToCompact(feature_space_.Index(f));
+}
+int IntFeatureMap::MapIndexFeature(int index_feature) const {
+  return feature_map_.SparseToCompact(index_feature);
+}
+INT_FEATURE_STRUCT IntFeatureMap::InverseIndexFeature(int index_feature) const {
+  return feature_space_.PositionFromIndex(index_feature);
+}
+INT_FEATURE_STRUCT IntFeatureMap::InverseMapFeature(int map_feature) const {
+  int index = feature_map_.CompactToSparse(map_feature);
+  return feature_space_.PositionFromIndex(index);
+}
+void IntFeatureMap::DeleteMapFeature(int map_feature) {
+  feature_map_.Merge(-1, map_feature);
+  mapping_changed_ = true;
+}
+bool IntFeatureMap::IsMapFeatureDeleted(int map_feature) const {
+  return feature_map_.IsCompactDeleted(map_feature);
+}
+
+// Copies the given feature_space and uses it as the index feature map
+// from INT_FEATURE_STRUCT.
+void IntFeatureMap::Init(const IntFeatureSpace &feature_space) {
+  feature_space_ = feature_space;
+  mapping_changed_ = false;
+  int sparse_size = feature_space_.Size();
+  feature_map_.Init(sparse_size, true);
+  feature_map_.Setup();
+  compact_size_ = feature_map_.CompactSize();
+  // Initialize look-up tables if needed.
+  FCOORD dir = FeatureDirection(0);
+  if (dir.x() == 0.0f && dir.y() == 0.0f) {
+    InitIntegerFX();
+  }
+  // Compute look-up tables to generate offset features.
+  for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
+    delete[] offset_plus_[dir];
+    delete[] offset_minus_[dir];
+    offset_plus_[dir] = new int[sparse_size];
+    offset_minus_[dir] = new int[sparse_size];
+  }
+  for (int dir = 1; dir <= kNumOffsetMaps; ++dir) {
+    for (int i = 0; i < sparse_size; ++i) {
+      int offset_index = ComputeOffsetFeature(i, dir);
+      offset_plus_[dir - 1][i] = offset_index;
+      offset_index = ComputeOffsetFeature(i, -dir);
+      offset_minus_[dir - 1][i] = offset_index;
+    }
+  }
+}
+
+// Helper to return an offset index feature. In this context an offset
+// feature with a dir of +/-1 is a feature of a similar direction,
+// but shifted perpendicular to the direction of the feature. An offset
+// feature with a dir of +/-2 is feature at the same position, but rotated
+// by +/- one [compact] quantum. Returns the index of the generated offset
+// feature, or -1 if it doesn't exist. Dir should be in
+// [-kNumOffsetMaps, kNumOffsetMaps] to indicate the relative direction.
+// A dir of 0 is an identity transformation.
+// Both input and output are from the index(sparse) feature space, not
+// the mapped/compact feature space, but the offset feature is the minimum
+// distance moved from the input to guarantee that it maps to the next
+// available quantum in the mapped/compact space.
+int IntFeatureMap::OffsetFeature(int index_feature, int dir) const {
+  if (dir > 0 && dir <= kNumOffsetMaps) {
+    return offset_plus_[dir - 1][index_feature];
+  } else if (dir < 0 && -dir <= kNumOffsetMaps) {
+    return offset_minus_[-dir - 1][index_feature];
+  } else if (dir == 0) {
+    return index_feature;
+  } else {
+    return -1;
+  }
+}
+
+//#define EXPERIMENT_ON
+#ifdef EXPERIMENT_ON // This code is commented out as SampleIterator and
+// TrainingSample are not reviewed/checked in yet, but these functions are a
+// useful indicator of how an IntFeatureMap is setup.
+
+// Computes the features used by the subset of samples defined by
+// the iterator and sets up the feature mapping.
+// Returns the size of the compacted feature space.
+int IntFeatureMap::FindNZFeatureMapping(SampleIterator *it) {
+  feature_map_.Init(feature_space_.Size(), false);
+  int total_samples = 0;
+  for (it->Begin(); !it->AtEnd(); it->Next()) {
+    const TrainingSample &sample = it->GetSample();
+    std::vector<int> features;
+    feature_space_.IndexAndSortFeatures(sample.features(), sample.num_features(), &features);
+    int num_features = features.size();
+    for (int f = 0; f < num_features; ++f)
+      feature_map_.SetMap(features[f], true);
+    ++total_samples;
+  }
+  feature_map_.Setup();
+  compact_size_ = feature_map_.CompactSize();
+  mapping_changed_ = true;
+  FinalizeMapping(it);
+  tprintf("%d non-zero features found in %d samples\n", compact_size_, total_samples);
+  return compact_size_;
+}
+#endif
+
+// After deleting some features, finish setting up the mapping, and map
+// all the samples. Returns the size of the compacted feature space.
+int IntFeatureMap::FinalizeMapping(SampleIterator *it) {
+  if (mapping_changed_) {
+    feature_map_.CompleteMerges();
+    compact_size_ = feature_map_.CompactSize();
+#ifdef EXPERIMENT_ON
+    it->MapSampleFeatures(*this);
+#endif
+    mapping_changed_ = false;
+  }
+  return compact_size_;
+}
+
+// Prints the map features from the set in human-readable form.
+void IntFeatureMap::DebugMapFeatures(const std::vector<int> &map_features) const {
+  for (int map_feature : map_features) {
+    INT_FEATURE_STRUCT f = InverseMapFeature(map_feature);
+    f.print();
+  }
+}
+
+void IntFeatureMap::Clear() {
+  for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
+    delete[] offset_plus_[dir];
+    delete[] offset_minus_[dir];
+    offset_plus_[dir] = nullptr;
+    offset_minus_[dir] = nullptr;
+  }
+}
+
+// Helper to compute an offset index feature. In this context an offset
+// feature with a dir of +/-1 is a feature of a similar direction,
+// but shifted perpendicular to the direction of the feature. An offset
+// feature with a dir of +/-2 is feature at the same position, but rotated
+// by +/- one [compact] quantum. Returns the index of the generated offset
+// feature, or -1 if it doesn't exist. Dir should be in
+// [-kNumOffsetMaps, kNumOffsetMaps] to indicate the relative direction.
+// A dir of 0 is an identity transformation.
+// Both input and output are from the index(sparse) feature space, not
+// the mapped/compact feature space, but the offset feature is the minimum
+// distance moved from the input to guarantee that it maps to the next
+// available quantum in the mapped/compact space.
+int IntFeatureMap::ComputeOffsetFeature(int index_feature, int dir) const {
+  INT_FEATURE_STRUCT f = InverseIndexFeature(index_feature);
+  ASSERT_HOST(IndexFeature(f) == index_feature);
+  if (dir == 0) {
+    return index_feature;
+  } else if (dir == 1 || dir == -1) {
+    FCOORD feature_dir = FeatureDirection(f.Theta);
+    FCOORD rotation90(0.0f, 1.0f);
+    feature_dir.rotate(rotation90);
+    // Find the nearest existing feature.
+    for (int m = 1; m < kMaxOffsetDist; ++m) {
+      double x_pos = f.X + feature_dir.x() * (m * dir);
+      double y_pos = f.Y + feature_dir.y() * (m * dir);
+      int x = IntCastRounded(x_pos);
+      int y = IntCastRounded(y_pos);
+      if (x >= 0 && x <= UINT8_MAX && y >= 0 && y <= UINT8_MAX) {
+        INT_FEATURE_STRUCT offset_f;
+        offset_f.X = x;
+        offset_f.Y = y;
+        offset_f.Theta = f.Theta;
+        int offset_index = IndexFeature(offset_f);
+        if (offset_index != index_feature && offset_index >= 0) {
+          return offset_index; // Found one.
+        }
+      } else {
+        return -1; // Hit the edge of feature space.
+      }
+    }
+  } else if (dir == 2 || dir == -2) {
+    // Find the nearest existing index_feature.
+    for (int m = 1; m < kMaxOffsetDist; ++m) {
+      int theta = f.Theta + m * dir / 2;
+      INT_FEATURE_STRUCT offset_f;
+      offset_f.X = f.X;
+      offset_f.Y = f.Y;
+      offset_f.Theta = Modulo(theta, 256);
+      int offset_index = IndexFeature(offset_f);
+      if (offset_index != index_feature && offset_index >= 0) {
+        return offset_index; // Found one.
+      }
+    }
+  }
+  return -1; // Nothing within the max distance.
+}
+
+} // namespace tesseract.