utils/text_utils.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "text_utils.hpp" | ||
| 2 | #include <algorithm> | ||
| 3 | #include <cctype> | ||
| 4 | #include <stdexcept> | ||
| 5 | |||
| 6 | /** | ||
| 7 | * Abbreviations that end with a period but do not end a sentence. | ||
| 8 | * Entries are lowercase and include the trailing period. | ||
| 9 | */ | ||
| 10 | const std::vector<std::string> TextUtils::abbreviationExceptions = {"e.g.", "i.e.", "vs.", "approx.", "dr.", "mr.", | ||
| 11 | "mrs.", "ms.", "prof.", "jr.", "sr.", "st.", | ||
| 12 | "fig.", "no.", "vol.", "pp.", "ca."}; | ||
| 13 | |||
| 14 | /** | ||
| 15 | * Wraps text to fit within a maximum line width. | ||
| 16 | * | ||
| 17 | * Splits the input text into lines, breaking at the last space that fits | ||
| 18 | * within max_width. Spaces at the start of each wrapped line and at the end | ||
| 19 | * of each line are removed. | ||
| 20 | * | ||
| 21 | * @param text The input text to wrap. | ||
| 22 | * @param max_width The maximum number of characters per line. Must be greater than 0. | ||
| 23 | * @return A vector of wrapped lines. Each line is at most max_width characters. | ||
| 24 | * The last line may be shorter. | ||
| 25 | * | ||
| 26 | * @throws std::invalid_argument if max_width is 0 or negative. | ||
| 27 | * | ||
| 28 | * @note If a single word is longer than max_width, it is broken at max_width | ||
| 29 | * characters. Only space characters are treated as break points. | ||
| 30 | * | ||
| 31 | * Algorithm: | ||
| 32 | * 1. Remove leading spaces from the text. | ||
| 33 | * 2. While the remaining text is longer than max_width, find the last space | ||
| 34 | * at or before max_width. | ||
| 35 | * 3. If no space exists, break at max_width. | ||
| 36 | * 4. Emit the line without trailing spaces, then remove leading spaces from the rest. | ||
| 37 | * 5. Emit any remaining text. | ||
| 38 | */ | ||
| 39 | 103 | std::vector<std::string> TextUtils::wrap_text(const std::string& text, const int max_width) { | |
| 40 | 103 | if (max_width <= 0) { | |
| 41 | 3 | throw std::invalid_argument("max_width must be greater than 0"); | |
| 42 | } | ||
| 43 | |||
| 44 | 100 | const size_t width = static_cast<size_t>(max_width); | |
| 45 | 100 | std::vector<std::string> result; | |
| 46 | |||
| 47 | 100 | const size_t first = text.find_first_not_of(' '); | |
| 48 | 100 | std::string remaining = (first == std::string::npos) ? std::string() : text.substr(first); | |
| 49 | |||
| 50 | 3700 | while (remaining.length() > width) { | |
| 51 | // Find the last space within the width, or break at the width if none exists. | ||
| 52 | 3600 | size_t wrap_position = remaining.rfind(' ', width); | |
| 53 | 3600 | if (wrap_position == std::string::npos) { | |
| 54 | 52 | wrap_position = width; | |
| 55 | } | ||
| 56 | |||
| 57 | // Emit the line without trailing spaces. The first character is never a space | ||
| 58 | // here, so the line is never empty. | ||
| 59 | 3600 | std::string line = remaining.substr(0, wrap_position); | |
| 60 | 3600 | line.erase(line.find_last_not_of(' ') + 1); | |
| 61 | 3600 | result.push_back(line); | |
| 62 | |||
| 63 | // Move past the break and remove leading spaces from the next line. | ||
| 64 | 3600 | remaining = remaining.substr(wrap_position); | |
| 65 | 3600 | const size_t next_start = remaining.find_first_not_of(' '); | |
| 66 | 3600 | remaining = (next_start == std::string::npos) ? std::string() : remaining.substr(next_start); | |
| 67 | 3600 | } | |
| 68 | |||
| 69 | 100 | if (!remaining.empty()) { | |
| 70 | // The first character is never a space here, so find_last_not_of always finds | ||
| 71 | // a non-space character and the final line is never empty. | ||
| 72 | 97 | remaining.erase(remaining.find_last_not_of(' ') + 1); | |
| 73 | 97 | result.push_back(remaining); | |
| 74 | } | ||
| 75 | |||
| 76 | 200 | return result; | |
| 77 | 100 | } | |
| 78 | |||
| 79 | /** | ||
| 80 | * Checks whether a character is whitespace. | ||
| 81 | * | ||
| 82 | * @param c The character to test. | ||
| 83 | * @return true if c is a space, tab, newline, or other whitespace character. | ||
| 84 | */ | ||
| 85 | 34757 | bool TextUtils::is_space(const char c) { | |
| 86 | 34757 | return std::isspace(static_cast<unsigned char>(c)) != 0; | |
| 87 | } | ||
| 88 | |||
| 89 | /** | ||
| 90 | * Checks whether the token ending before a whitespace character is an abbreviation. | ||
| 91 | * | ||
| 92 | * Extracts the token that ends at space_idx, strips leading punctuation such as | ||
| 93 | * '(' or '"', converts it to lowercase, and compares it to abbreviationExceptions. | ||
| 94 | * | ||
| 95 | * @param text The full input text. | ||
| 96 | * @param space_idx The index of the whitespace character that follows the token. | ||
| 97 | * @return true if the token is in abbreviationExceptions. | ||
| 98 | */ | ||
| 99 | 246 | bool TextUtils::is_abbreviation(const std::string& text, const size_t space_idx) { | |
| 100 | 246 | size_t word_start = space_idx; | |
| 101 | 1230 | while (word_start > 0 && !is_space(text[word_start - 1])) { | |
| 102 | 984 | word_start -= 1; | |
| 103 | } | ||
| 104 | |||
| 105 | // Strip leading punctuation so "(e.g." still matches. | ||
| 106 | 246 | while (word_start < space_idx && !std::isalnum(static_cast<unsigned char>(text[word_start]))) { | |
| 107 | ✗ | word_start += 1; | |
| 108 | } | ||
| 109 | |||
| 110 | 246 | std::string word = text.substr(word_start, space_idx - word_start); | |
| 111 | 246 | std::transform(word.begin(), word.end(), word.begin(), | |
| 112 | 984 | [](unsigned char c) { return static_cast<char>(std::tolower(c)); }); | |
| 113 | |||
| 114 | 246 | return std::find(abbreviationExceptions.begin(), abbreviationExceptions.end(), word) | |
| 115 | 738 | != abbreviationExceptions.end(); | |
| 116 | 246 | } | |
| 117 | |||
| 118 | /** | ||
| 119 | * Checks whether a whitespace character marks the end of a sentence. | ||
| 120 | * | ||
| 121 | * A sentence ends at whitespace preceded by '!' or '?', or by '.' when the | ||
| 122 | * preceding token is not an abbreviation. | ||
| 123 | * | ||
| 124 | * @param text The full input text. | ||
| 125 | * @param i The index to test. Must be less than text.length(). | ||
| 126 | * @return true if index i is a sentence boundary. | ||
| 127 | */ | ||
| 128 | 19336 | bool TextUtils::is_sentence_boundary(const std::string& text, const size_t i) { | |
| 129 | 19336 | if (i == 0 || !is_space(text[i])) { | |
| 130 | 15587 | return false; | |
| 131 | } | ||
| 132 | |||
| 133 | 3749 | const char prev = text[i - 1]; | |
| 134 | 3749 | if (prev == '!' || prev == '?') { | |
| 135 | 527 | return true; | |
| 136 | } | ||
| 137 | 3222 | if (prev == '.') { | |
| 138 | 246 | return !is_abbreviation(text, i); | |
| 139 | } | ||
| 140 | 2976 | return false; | |
| 141 | } | ||
| 142 | |||
| 143 | /** | ||
| 144 | * Finds the best position to end a chunk within a window. | ||
| 145 | * | ||
| 146 | * Searches backward from end for a sentence boundary first, then for any | ||
| 147 | * whitespace. Only positions at or after start + min_len are considered, | ||
| 148 | * so the resulting chunk is at least min_len characters long. | ||
| 149 | * | ||
| 150 | * @param text The full input text. | ||
| 151 | * @param start The index where the current chunk begins. | ||
| 152 | * @param end The maximum index for the chunk end. Must be less than text.length(). | ||
| 153 | * @param min_len The minimum chunk length in characters. | ||
| 154 | * @return The break index, or 0 if no suitable break exists. | ||
| 155 | */ | ||
| 156 | 2374 | size_t TextUtils::find_break(const std::string& text, const size_t start, const size_t end, const size_t min_len) { | |
| 157 | 2374 | const size_t lo = start + std::max<size_t>(1, min_len); // chunk must be at least min_len long | |
| 158 | 2374 | if (lo > end) { | |
| 159 | ✗ | return 0; | |
| 160 | } | ||
| 161 | |||
| 162 | 14522 | for (size_t i = end; i >= lo; i -= 1) { | |
| 163 | 12852 | if (is_sentence_boundary(text, i)) { | |
| 164 | 704 | return i; | |
| 165 | } | ||
| 166 | } | ||
| 167 | |||
| 168 | 5095 | for (size_t i = end; i >= lo; i -= 1) { | |
| 169 | 4783 | if (is_space(text[i])) { | |
| 170 | 1358 | return i; | |
| 171 | } | ||
| 172 | } | ||
| 173 | |||
| 174 | 312 | return 0; | |
| 175 | } | ||
| 176 | |||
| 177 | /** | ||
| 178 | * Splits text into sentence-aware chunks with optional overlap. | ||
| 179 | * | ||
| 180 | * Each chunk is at most chunk_size characters. The method prefers to end a | ||
| 181 | * chunk at a sentence boundary, then at any whitespace, and only splits inside | ||
| 182 | * a word when the window contains no whitespace in its second half. Chunks are | ||
| 183 | * at least chunk_size / 2 characters long, except for the final chunk. | ||
| 184 | * | ||
| 185 | * Consecutive chunks share approximately overlap characters. The next chunk | ||
| 186 | * starts at the earliest sentence start inside the overlap region, or at the | ||
| 187 | * nearest word start if there is none. The overlap is therefore at most | ||
| 188 | * overlap characters and may be smaller. | ||
| 189 | * | ||
| 190 | * Leading and trailing whitespace is removed from each chunk. | ||
| 191 | * | ||
| 192 | * @param text The input text to split. | ||
| 193 | * @param chunk_size The maximum size of each chunk in characters. Must be greater than 0. | ||
| 194 | * @param overlap The approximate number of characters shared between consecutive chunks. | ||
| 195 | * Must be less than chunk_size. | ||
| 196 | * @return A vector of chunks. Returns an empty vector if text contains only whitespace. | ||
| 197 | * | ||
| 198 | * @throws std::invalid_argument if chunk_size is 0 or overlap is greater than or equal to chunk_size. | ||
| 199 | */ | ||
| 200 | 250 | std::vector<std::string> TextUtils::split_text(const std::string& text, const size_t chunk_size, const size_t overlap) { | |
| 201 | 250 | if (chunk_size == 0) { | |
| 202 | 1 | throw std::invalid_argument("chunk_size must be greater than 0"); | |
| 203 | } | ||
| 204 | 249 | if (overlap >= chunk_size) { | |
| 205 | 2 | throw std::invalid_argument("overlap must be smaller than chunk_size"); | |
| 206 | } | ||
| 207 | |||
| 208 | 247 | const size_t min_len = chunk_size / 2; | |
| 209 | 247 | std::vector<std::string> chunks; | |
| 210 | 247 | const size_t text_length = text.length(); | |
| 211 | 247 | size_t start = 0; | |
| 212 | |||
| 213 | 257 | while (start < text_length && is_space(text[start])) { | |
| 214 | 10 | start += 1; | |
| 215 | } | ||
| 216 | |||
| 217 | 2621 | while (start < text_length) { | |
| 218 | 2619 | size_t end = std::min(start + chunk_size, text_length); | |
| 219 | |||
| 220 | 2619 | if (end < text_length) { | |
| 221 | 2374 | const size_t text_break = find_break(text, start, end, min_len); | |
| 222 | 2374 | if (text_break != 0) { | |
| 223 | 2062 | end = text_break; // otherwise no acceptable break exists: hard split | |
| 224 | } | ||
| 225 | } | ||
| 226 | |||
| 227 | 2619 | size_t chunk_end = end; | |
| 228 | 2622 | while (chunk_end > start && is_space(text[chunk_end - 1])) { | |
| 229 | 3 | chunk_end -= 1; | |
| 230 | } | ||
| 231 | 2619 | chunks.push_back(text.substr(start, chunk_end - start)); | |
| 232 | |||
| 233 | 2619 | if (end >= text_length) { | |
| 234 | 245 | break; | |
| 235 | } | ||
| 236 | |||
| 237 | // Begin the next chunk `overlap` characters back. | ||
| 238 | 2374 | size_t next = (end > overlap) ? end - overlap : 0; | |
| 239 | 2374 | if (next <= start) { | |
| 240 | 496 | next = end; // guarantees forward progress | |
| 241 | } | ||
| 242 | |||
| 243 | // Prefer the earliest sentence start inside the overlap region. | ||
| 244 | 2374 | size_t sentence_start = end; | |
| 245 | 8790 | for (size_t i = next; i < end; i += 1) { | |
| 246 | 6484 | if (is_sentence_boundary(text, i)) { | |
| 247 | 68 | sentence_start = i; | |
| 248 | 68 | break; | |
| 249 | } | ||
| 250 | } | ||
| 251 | |||
| 252 | 2374 | if (sentence_start < end) { | |
| 253 | 68 | next = sentence_start; | |
| 254 | } else { | ||
| 255 | // Snap forward to the first word start inside [next, end). | ||
| 256 | // If there is none, keep the overlap start so the overlap is honored. | ||
| 257 | 2306 | size_t word_start = next; | |
| 258 | 4866 | while (word_start < end && !is_space(text[word_start - 1])) { | |
| 259 | 2560 | word_start += 1; | |
| 260 | } | ||
| 261 | 2306 | if (word_start < end) { | |
| 262 | 705 | next = word_start; | |
| 263 | } | ||
| 264 | } | ||
| 265 | |||
| 266 | 3266 | while (next < text_length && is_space(text[next])) { | |
| 267 | 892 | next += 1; // skip the whitespace | |
| 268 | } | ||
| 269 | 2374 | start = next; | |
| 270 | } | ||
| 271 | |||
| 272 | 494 | return chunks; | |
| 273 | ✗ | } | |
| 274 |