PmergeMe.cpp
1 /* ************************************************************************** */ 2 /* */ 3 /* ::: :::::::: */ 4 /* PmergeMe.cpp :+: :+: :+: */ 5 /* +:+ +:+ +:+ */ 6 /* By: gychoi <gychoi@student.42seoul.kr> +#+ +:+ +#+ */ 7 /* +#+#+#+#+#+ +#+ */ 8 /* Created: 2023/12/31 17:50:53 by gychoi #+# #+# */ 9 /* Updated: 2024/01/16 21:10:22 by gychoi ### ########.fr */ 10 /* */ 11 /* ************************************************************************** */ 12 13 #include "PmergeMe.hpp" 14 15 std::vector<int> PmergeMe::sSequence; 16 std::deque<int> PmergeMe::sPartialJacobsthalSequence; 17 18 static int _getValidElement(char const* str); 19 static std::deque<int> _generatePartialJacobsthalSequence(); 20 static int _binarySearch(int* const& arr, 21 int left, int right, int target); 22 23 /* ************************************************************************** */ 24 /* Constructor & Destructor */ 25 /* ************************************************************************** */ 26 27 PmergeMe::PmergeMe() 28 { 29 // nothing to do 30 } 31 32 PmergeMe::PmergeMe 33 (__attribute__((unused)) PmergeMe const& other) 34 { 35 // nothing to do 36 } 37 38 PmergeMe& PmergeMe::operator= 39 (__attribute__((unused)) PmergeMe const& other) 40 { 41 return *this; 42 } 43 44 PmergeMe::~PmergeMe() 45 { 46 // nothing to do 47 } 48 49 /* ************************************************************************** */ 50 /* Getter & Setter */ 51 /* ************************************************************************** */ 52 53 std::vector<int> const& PmergeMe::getSequence() 54 { 55 return sSequence; 56 } 57 58 void PmergeMe::setSequence(char** seq, int len) 59 { 60 sSequence.reserve(len); 61 62 for (int i = 1; i < len; i++) 63 { 64 sSequence.push_back(_getValidElement(seq[i])); 65 } 66 67 sPartialJacobsthalSequence = _generatePartialJacobsthalSequence(); 68 } 69 70 /* ************************************************************************** */ 71 /* Public Member Function */ 72 /* ************************************************************************** */ 73 74 void PmergeMe::fordJohnsonSort(std::vector<int>& v, int size, int turn) 75 { 76 if (size <= 1) 77 { 78 return; 79 } 80 81 std::vector<int> staggler; 82 bool hasStaggler = false; 83 84 if (size % 2) 85 { 86 size--; 87 for (int i = 0; i < turn; i++) 88 { 89 staggler.push_back(v[(i + 1) * size]); 90 v.erase(v.begin() + ((i + 1) * size)); 91 } 92 hasStaggler = true; 93 } 94 95 for (int i = 0; i < size; i += 2) 96 { 97 if (v[i] < v[i + 1]) 98 { 99 std::swap(v[i], v[i + 1]); 100 101 for (int j = 1; j < turn; j++) 102 { 103 std::swap(v[j * size + i], v[j * size + i + 1]); 104 } 105 } 106 } 107 108 std::vector<int> temp; 109 110 for (int i = 0; i < turn; i++) 111 { 112 for (int j = 0; j < size / 2; j++) 113 { 114 temp.push_back(v[(2 * j) + (i * size)]); 115 } 116 for (int j = 0; j < size / 2; j++) 117 { 118 temp.push_back(v[(2 * j + 1) + (i * size)]); 119 } 120 } 121 122 v = temp; 123 124 fordJohnsonSort(v, size / 2, turn * 2); 125 126 if (!staggler.empty()) 127 { 128 for (int i = turn; i >= 0; i--) 129 { 130 if (staggler.empty()) 131 { 132 break; 133 } 134 v.insert(v.begin() + (i * size), staggler.back()); 135 staggler.pop_back(); 136 } 137 size++; 138 } 139 140 std::vector<ValuePair> main; 141 std::vector<ValuePair> pend; 142 143 for (int i = 0; i < size / 2; i++) 144 { 145 ValuePair mainPair; 146 ValuePair pendPair; 147 148 mainPair.value = v[i]; 149 mainPair.index = i; 150 pendPair.value = v[i + size / 2]; 151 pendPair.index = i + size / 2; 152 153 main.push_back(mainPair); 154 pend.push_back(pendPair); 155 } 156 157 if (hasStaggler) 158 { 159 ValuePair stagPair; 160 161 stagPair.value = v[size - 1]; 162 stagPair.index = size - 1; 163 164 pend.push_back(stagPair); 165 } 166 167 for (size_t i = 0; i < sPartialJacobsthalSequence.size(); i++) 168 { 169 if (i == 0) 170 { 171 main.insert(main.begin(), pend.front()); 172 continue; 173 } 174 175 size_t pendArrSize = pend.size(); 176 size_t currJacobNum = sPartialJacobsthalSequence[i]; 177 size_t prevJacobNum = sPartialJacobsthalSequence[i - 1]; 178 size_t rangeIndex = std::min(currJacobNum, pendArrSize) - 1; 179 180 for (size_t j = rangeIndex; j >= prevJacobNum; j--) 181 { 182 size_t mainArrSize = main.size(); 183 int mainArr[mainArrSize]; 184 size_t endRange = std::min(mainArrSize, 185 currJacobNum + prevJacobNum - 1) - 1; 186 187 for (size_t k = 0; k < mainArrSize; k++) 188 { 189 mainArr[k] = main[k].value; 190 } 191 192 int index = _binarySearch(mainArr, 0, endRange, pend[j].value); 193 194 main.insert(main.begin() + index, pend[j]); 195 } 196 197 if (rangeIndex == pendArrSize - 1) 198 { 199 break; 200 } 201 } 202 203 std::vector<int> index; 204 205 for (size_t i = 0; i < main.size(); i++) 206 { 207 index.push_back(main[i].index); 208 } 209 210 std::vector<int>().swap(temp); 211 212 for (int i = 0; i < turn; i++) 213 { 214 for (int j = 0; j < size; j++) 215 { 216 temp.push_back(v[i * size + index[j]]); 217 } 218 } 219 220 v = temp; 221 } 222 223 void PmergeMe::fordJohnsonSort(std::deque<int>& d, int size, int turn) 224 { 225 if (size <= 1) 226 { 227 return; 228 } 229 230 std::deque<int> staggler; 231 bool hasStaggler = false; 232 233 if (size % 2) 234 { 235 size--; 236 for (int i = 0; i < turn; i++) 237 { 238 staggler.push_back(d[(i + 1) * size]); 239 d.erase(d.begin() + ((i + 1) * size)); 240 } 241 hasStaggler = true; 242 } 243 244 for (int i = 0; i < size; i += 2) 245 { 246 if (d[i] < d[i + 1]) 247 { 248 std::swap(d[i], d[i + 1]); 249 250 for (int j = 1; j < turn; j++) 251 { 252 std::swap(d[j * size + i], d[j * size + i + 1]); 253 } 254 } 255 } 256 257 std::deque<int> temp; 258 259 for (int i = 0; i < turn; i++) 260 { 261 for (int j = 0; j < size / 2; j++) 262 { 263 temp.push_back(d[(2 * j) + (i * size)]); 264 } 265 for (int j = 0; j < size / 2; j++) 266 { 267 temp.push_back(d[(2 * j + 1) + (i * size)]); 268 } 269 } 270 271 d = temp; 272 273 fordJohnsonSort(d, size / 2, turn * 2); 274 275 if (!staggler.empty()) 276 { 277 for (int i = turn; i >= 0; i--) 278 { 279 if (staggler.empty()) 280 { 281 break; 282 } 283 d.insert(d.begin() + (i * size), staggler.back()); 284 staggler.pop_back(); 285 } 286 size++; 287 } 288 289 std::deque<ValuePair> main; 290 std::deque<ValuePair> pend; 291 292 for (int i = 0; i < size / 2; i++) 293 { 294 ValuePair mainPair; 295 ValuePair pendPair; 296 297 mainPair.value = d[i]; 298 mainPair.index = i; 299 pendPair.value = d[i + size / 2]; 300 pendPair.index = i + size / 2; 301 302 main.push_back(mainPair); 303 pend.push_back(pendPair); 304 } 305 306 if (hasStaggler) 307 { 308 ValuePair stagPair; 309 310 stagPair.value = d[size - 1]; 311 stagPair.index = size - 1; 312 313 pend.push_back(stagPair); 314 } 315 316 for (size_t i = 0; i < sPartialJacobsthalSequence.size(); i++) 317 { 318 if (i == 0) 319 { 320 main.insert(main.begin(), pend.front()); 321 continue; 322 } 323 324 size_t pendArrSize = pend.size(); 325 size_t currJacobNum = sPartialJacobsthalSequence[i]; 326 size_t prevJacobNum = sPartialJacobsthalSequence[i - 1]; 327 size_t rangeIndex = std::min(currJacobNum, pendArrSize) - 1; 328 329 for (size_t j = rangeIndex; j >= prevJacobNum; j--) 330 { 331 size_t mainArrSize = main.size(); 332 int mainArr[mainArrSize]; 333 size_t endRange = std::min(mainArrSize, 334 currJacobNum + prevJacobNum - 1) - 1; 335 336 for (size_t k = 0; k < mainArrSize; k++) 337 { 338 mainArr[k] = main[k].value; 339 } 340 341 int index = _binarySearch(mainArr, 0, endRange, pend[j].value); 342 343 main.insert(main.begin() + index, pend[j]); 344 } 345 346 if (rangeIndex == pendArrSize - 1) 347 { 348 break; 349 } 350 } 351 352 std::deque<int> index; 353 354 for (size_t i = 0; i < main.size(); i++) 355 { 356 index.push_back(main[i].index); 357 } 358 359 std::deque<int>().swap(temp); 360 361 for (int i = 0; i < turn; i++) 362 { 363 for (int j = 0; j < size; j++) 364 { 365 temp.push_back(d[i * size + index[j]]); 366 } 367 } 368 369 d = temp; 370 } 371 372 /* ************************************************************************** */ 373 /* Utility Function */ 374 /* ************************************************************************** */ 375 376 static int _getValidElement(char const* str) 377 { 378 if (str == 0 || std::strlen(str) == 0) 379 { 380 std::string arg = str; 381 throw std::invalid_argument("Invalid argument: " + arg); 382 } 383 else if (str[0] == '-') 384 { 385 std::string arg = str; 386 throw std::invalid_argument("Invalid argument: " + arg); 387 } 388 else if (str[0] == '0' && std::strlen(str) > 1) 389 { 390 std::string arg = str; 391 throw std::invalid_argument("Invalid argument: " + arg); 392 } 393 else 394 { 395 bool signFlag = false; 396 397 for (size_t i = 0; i < std::strlen(str); i++) 398 { 399 if (!std::isdigit(str[i])) 400 { 401 if (str[i] == '+' && signFlag == false) 402 { 403 signFlag = true; 404 continue; 405 } 406 else 407 { 408 std::string arg = str; 409 throw std::invalid_argument("Invalid argument: " + arg); 410 } 411 } 412 } 413 } 414 415 char* endPtr = 0; 416 double elem = std::strtod(str, &endPtr); 417 int ret = static_cast<int>(elem); 418 419 if (endPtr != 0 && *endPtr != '\0') 420 { 421 std::string arg = str; 422 throw std::invalid_argument("Invalid argument: " + arg); 423 } 424 else if (elem < 0 || elem > std::numeric_limits<int>::max()) 425 { 426 std::string arg = str; 427 throw std::invalid_argument("Invalid argument: " + arg); 428 } 429 else if (elem == 0) 430 { 431 std::string arg = str; 432 throw std::invalid_argument("Invalid argument: " + arg); 433 } 434 else 435 { 436 // valid element 437 } 438 439 return ret; 440 } 441 442 static std::deque<int> _generatePartialJacobsthalSequence() 443 { 444 std::deque<int> jacobSequence; 445 size_t n = 2; 446 447 jacobSequence.push_back(0); 448 jacobSequence.push_back(1); 449 450 while (true) 451 { 452 int jacobNum = jacobSequence[n - 1] + 2 * jacobSequence[n - 2]; 453 454 if (jacobNum < 0 || jacobNum > std::numeric_limits<int>::max()) 455 { 456 break; 457 } 458 jacobSequence.push_back(jacobNum); 459 n++; 460 } 461 462 jacobSequence.pop_front(); 463 jacobSequence.pop_front(); 464 465 return jacobSequence; 466 } 467 468 static int _binarySearch 469 (int* const& arr, int left, int right, int target) 470 { 471 while (left <= right) 472 { 473 int mid = left + (right - left) / 2; 474 475 if (arr[mid] == target) 476 { 477 return mid; 478 } 479 else if (arr[mid] < target) 480 { 481 left = mid + 1; 482 } 483 else 484 { 485 right = mid - 1; 486 } 487 } 488 return left; 489 } 490