g_src/template.h

   1 template <class T> int32_t get_vector_sum(svector<T> &vec)
   2 {
   3         T total=0;
   4         auto ii_s=vec.begin(),ii_e=vec.end();
   5         for(;ii_s<ii_e;++ii_s)
   6                 {
   7                 total+=(*ii_s);
   8                 }
   9         return total;
  10 }
  11
  12 template <class T> int32_t get_random_biased_index(svector<T> &chance)
  13 {
  14         if(chance.size()==0)
  15                 {
  16                 errorlog_string("Empty biased index vector");
  17                 return -1;
  18                 }
  19
  20         T roll=trandom(get_vector_sum(chance));
  21
  22         auto ii_s=chance.begin(),ii_e=chance.end();
  23         auto ii_b=ii_s;
  24         for(;ii_s<ii_e;++ii_s)
  25                 {
  26                 if(roll<(*ii_s))return (int32_t)(ii_s-ii_b);
  27                 roll-=(*ii_s);
  28                 }
  29
  30         errorlog_string("Biased index vector computation error");
  31         return 0;//MORE FUNCTIONS WILL BE HAPPIER WITH 0 THAN -1 HERE
  32 }
  33
  34 template <class T> void zero_vector(svector<T> &vc)
  35 {
  36         //NOTE: vector MEMORY IS GUARANTEED TO BE CONTIGUOUS, AND THIS IS FASTER THAN GOING THROUGH ONE BY ONE
  37                         //apparently this gives linux a headache though, so back to the slower way
  38         //int32_t sz=vc.size();
  39         //if(sz==0)return;
  40         //memset(&(vc[0]),0,sizeof(T)*sz);
  41         auto ii_s=vc.begin(),ii_e=vc.end();
  42         for(;ii_s<ii_e;++ii_s)(*ii_s)=0;
  43 }
  44
  45 template <class T> bool positive_vector(svector<T> &vc)
  46 {
  47         auto ii_s=vc.begin(),ii_e=vc.end();
  48         for(;ii_s<ii_e;++ii_s)
  49                 {
  50                 if((*ii_s)>0)return true;
  51                 }
  52         return false;
  53 }
  54
  55 template <class T> void add_unique_to_vector(T nl,svector<T> &vc)
  56 {
  57         auto ii_s=vc.begin(),ii_e=vc.end();
  58         for(;ii_s<ii_e;++ii_s)
  59                 {
  60                 if((*ii_s)==nl)return;
  61                 }
  62         vc.push_back(nl);
  63 }
  64
  65 template <class T,class T2> void add_dual_unique_to_vectors(T nl,T2 nl2,svector<T> &vc,svector<T2> &vc2)
  66 {
  67         auto ii_s=vc.begin(),ii_e=vc.end();
  68         auto ii_s2=vc2.begin(),ii_e2=vc2.end();
  69         for(;ii_s<ii_e;++ii_s,++ii_s2)
  70                 {
  71                 if((*ii_s)==nl&&
  72                         (*ii_s2)==nl2)return;
  73                 }
  74         vc.push_back(nl);
  75         vc2.push_back(nl2);
  76 }
  77
  78 template <class T,class T2,class T3,class T4> void add_quad_unique_to_vectors(T nl,T2 nl2,T3 nl3,T4 nl4,
  79                                                                                                                                                                 svector<T> &vc,svector<T2> &vc2,svector<T3> &vc3,svector<T4> &vc4)
  80 {
  81         auto ii_s=vc.begin(),ii_e=vc.end();
  82         auto ii_s2=vc2.begin(),ii_e2=vc2.end();
  83         auto ii_s3=vc3.begin(),ii_e3=vc3.end();
  84         auto ii_s4=vc4.begin(),ii_e4=vc4.end();
  85         for(;ii_s<ii_e;++ii_s,++ii_s2,++ii_s3,++ii_s4)
  86                 {
  87                 if((*ii_s)==nl&&
  88                         (*ii_s2)==nl2&&
  89                         (*ii_s3)==nl3&&
  90                         (*ii_s4)==nl4)return;
  91                 }
  92         vc.push_back(nl);
  93         vc2.push_back(nl2);
  94         vc3.push_back(nl3);
  95         vc4.push_back(nl4);
  96 }
  97
  98 template <class T> void remove_all_from_vector(T nl,svector<T> &vc)
  99 {
 100         int32_t i;
 101         for(i=(int32_t)vc.size()-1;i>=0;i--)
 102                 {
 103                 if(vc[i]==nl)vc.erase(i);
 104                 }
 105 }
 106
 107 template <class T,class T2> void remove_all_from_dual_vectors(T nl,T2 nl2,svector<T> &vc,svector<T2> &vc2)
 108 {
 109         int32_t i;
 110         for(i=(int32_t)vc.size()-1;i>=0;i--)
 111                 {
 112                 if(vc[i]==nl&&
 113                         vc2[i]==nl2)
 114                         {
 115                         vc.erase(i);
 116                         vc2.erase(i);
 117                         }
 118                 }
 119 }
 120
 121 template <class T> int32_t get_vector_index(T a,svector<T> &v)
 122 {
 123         auto ii_s=v.begin(),ii_e=v.end();
 124         auto ii_b=ii_s;
 125         for(;ii_s<ii_e;++ii_s)
 126                 {
 127                 if((*ii_s)==a)return (int32_t)(ii_s-ii_b);
 128                 }
 129         return -1;
 130 }
 131
 132 template <class T,class T2> int32_t get_dual_vector_index(T a1,T2 a2,svector<T> &vc,svector<T2> &vc2)
 133 {
 134         auto ii_s=vc.begin(),ii_e=vc.end();
 135         auto ii_s2=vc2.begin(),ii_e2=vc2.end();
 136         auto ii_b=ii_s;
 137         for(;ii_s<ii_e;++ii_s,++ii_s2)
 138                 {
 139                 if((*ii_s)==a1&&
 140                         (*ii_s2)==a2)return (int32_t)(ii_s-ii_b);
 141                 }
 142         return -1;
 143 }
 144
 145 template <class T,class T2,class T3,class T4> int32_t get_quad_vector_index(T a1,T2 a2,T3 a3,T4 a4,
 146                                                                                                                                                 svector<T> &vc,svector<T2> &vc2,
 147                                                                                                                                                 svector<T3> &vc3,svector<T4> &vc4)
 148 {
 149         auto ii_s=vc.begin(),ii_e=vc.end();
 150         auto ii_s2=vc2.begin(),ii_e2=vc2.end();
 151         auto ii_s3=vc3.begin(),ii_e3=vc3.end();
 152         auto ii_s4=vc4.begin(),ii_e4=vc4.end();
 153         auto ii_b=ii_s;
 154         for(;ii_s<ii_e;++ii_s,++ii_s2,++ii_s3,++ii_s4)
 155                 {
 156                 if((*ii_s)==a1&&
 157                         (*ii_s2)==a2&&
 158                         (*ii_s3)==a3&&
 159                         (*ii_s4)==a4)return (int32_t)(ii_s-ii_b);
 160                 }
 161         return -1;
 162 }
 163
 164 template <class T> void merge_vectors(T &master, T &merger)
 165 {
 166         auto ii_s=merger.begin(),ii_e=merger.end();
 167         for(;ii_s<ii_e;++ii_s)
 168                 {
 169                 auto ii_s2=master.begin(),ii_e2=master.end();
 170                 for(;ii_s2<ii_e2;++ii_s2)
 171                         {
 172                         if((*ii_s)==(*ii_s2))break;
 173                         }
 174                 if(ii_s2>=ii_e2)
 175                         {
 176                         master.push_back((*ii_s));
 177                         }
 178                 }
 179 }
 180
 181 template <class T> int32_t get_common_element_vector_index(T &master, T &merger)
 182 {
 183         auto ii_s=merger.begin(),ii_e=merger.end();
 184         auto ii_s2=master.begin(),ii_e2=master.end();
 185         auto ii_b2=ii_s2;
 186
 187         for(;ii_s<ii_e;++ii_s)
 188                 {
 189                 for(;ii_s2<ii_e2;++ii_s2)
 190                         {
 191                         if((*ii_s)==(*ii_s2))return (int32_t)(ii_s2-ii_b2);
 192                         }
 193                 ii_s2=ii_b2;
 194                 }
 195
 196         return -1;
 197 }
 198
 199 template <class T,class T2> void merge_dual_vectors(T &master, T2 &master2, T &merger, T2 &merger2)
 200 {
 201         auto ii_s=merger.begin(),ii_e=merger.end();
 202         auto ii_s2=merger2.begin(),ii_e2=merger2.end();
 203         for(;ii_s<ii_e;++ii_s,++ii_s2)
 204                 {
 205                 auto ii_s3=master.begin(),ii_e3=master.end();
 206                 auto ii_s4=master2.begin(),ii_e4=master2.end();
 207                 for(;ii_s3<ii_e3;++ii_s3,++ii_s4)
 208                         {
 209                         if((*ii_s)==(*ii_s3)&&
 210                                 (*ii_s2)==(*ii_s4))break;
 211                         }
 212                 if(ii_s3>=ii_e3)
 213                         {
 214                         master.push_back((*ii_s));
 215                         master2.push_back((*ii_s2));
 216                         }
 217                 }
 218 }
 219
 220 template <class T,class T2,class T3,class T4> void merge_quad_vectors(T &master, T2 &master2, T3 &master3, T4 &master4,
 221                                                                                                                                                 T &merger, T2 &merger2, T3 &merger3, T4 &merger4)
 222 {
 223         auto ii_s=merger.begin(),ii_e=merger.end();
 224         auto ii_s2=merger2.begin(),ii_e2=merger2.end();
 225         auto ii_s3=merger3.begin(),ii_e3=merger3.end();
 226         auto ii_s4=merger4.begin(),ii_e4=merger4.end();
 227         for(;ii_s<ii_e;++ii_s,++ii_s2,++ii_s3,++ii_s4)
 228                 {
 229                 auto ii_s5=master.begin(),ii_e5=master.end();
 230                 auto ii_s6=master2.begin(),ii_e6=master2.end();
 231                 auto ii_s7=master3.begin(),ii_e7=master3.end();
 232                 auto ii_s8=master4.begin(),ii_e8=master4.end();
 233                 for(;ii_s5<ii_e5;++ii_s5,++ii_s6,++ii_s7,++ii_s8)
 234                         {
 235                         if((*ii_s)==(*ii_s5)&&
 236                                 (*ii_s2)==(*ii_s6)&&
 237                                 (*ii_s3)==(*ii_s7)&&
 238                                 (*ii_s4)==(*ii_s8))break;
 239                         }
 240                 if(ii_s5>=ii_e5)
 241                         {
 242                         master.push_back((*ii_s));
 243                         master2.push_back((*ii_s2));
 244                         master3.push_back((*ii_s3));
 245                         master4.push_back((*ii_s4));
 246                         }
 247                 }
 248 }
 249
 250 template <class T> void cull_vectors(T &master,T &cull)
 251 {
 252         int32_t i,i2;
 253         for(i=(int32_t)cull.size()-1;i>=0;i--)
 254                 {
 255                 for(i2=(int32_t)master.size()-1;i2>=0;i2--)
 256                         {
 257                         if(cull[i]==master[i2])
 258                                 {
 259                                 master.erase(i2);
 260                                 break;
 261                                 }
 262                         }
 263                 }
 264 }
 265
 266 template <class T> void push_on_vector(T &master,T &new_stuff)
 267 {
 268         auto ii_s=new_stuff.begin(),ii_e=new_stuff.end();
 269         for(;ii_s<ii_e;++ii_s)
 270                 {
 271                 master.push_back(*ii_s);
 272                 }
 273 }
 274
 275 template<class T> VIndex add_to_global_id_vector(T ptr,svector<T> &vect)
 276 {
 277         int32_t size=vect.size();
 278         if(size==0)
 279                 {
 280                 vect.push_back(ptr);
 281                 return 1;
 282                 }
 283         if(vect[size-1]->global_id<ptr->global_id)
 284                 {
 285                 vect.push_back(ptr);
 286                 return size;
 287                 }
 288
 289         int32_t start=0;
 290         int32_t end=size-1;
 291         T cptr;
 292         int32_t mid;
 293         while(start<=end)
 294                 {
 295                 mid=(start+end)>>1;
 296
 297                 cptr=vect[mid];
 298                 if(cptr->global_id==ptr->global_id)return -1;
 299                 if(start==end)
 300                         {
 301                         if(cptr->global_id<ptr->global_id)
 302                                 {
 303                                 if(start+1>=size)return -1;//push_back() FOR UNIQUE ALREADY HANDLED
 304                                 else
 305                                         {
 306                                         vect.insert(start+1,ptr);
 307                                         return start+1;
 308                                         }
 309                                 }
 310                         else if(cptr->global_id>ptr->global_id)
 311                                 {
 312                                 vect.insert(start,ptr);
 313                                 return start;
 314                                 }
 315                         return -1;
 316                         }
 317
 318                 if(cptr->global_id>ptr->global_id)end=mid-1;
 319                 else start=mid+1;
 320                 }
 321
 322         if(end<0)
 323                 {
 324                 T cptr=vect[start];
 325                 if(cptr->global_id<ptr->global_id)
 326                         {
 327                         if(start+1>=size)return -1;//push_back() FOR UNIQUE ALREADY HANDLED
 328                         else
 329                                 {
 330                                 vect.insert(start+1,ptr);
 331                                 return start+1;
 332                                 }
 333                         }
 334                 else if(cptr->global_id>ptr->global_id)
 335                         {
 336                         vect.insert(start,ptr);
 337                         return start;
 338                         }
 339                 }
 340         else if(end<size)
 341                 {
 342                 T cptr=vect[end];
 343                 if(cptr->global_id<ptr->global_id)
 344                         {
 345                         if(end+1>=size)return -1;//push_back() FOR UNIQUE ALREADY HANDLED
 346                         else
 347                                 {
 348                                 vect.insert(end+1,ptr);
 349                                 return end+1;
 350                                 }
 351                         }
 352                 else if(cptr->global_id>ptr->global_id)
 353                         {
 354                         vect.insert(end,ptr);
 355                         return end;
 356                         }
 357                 }
 358         return -1;//push_back() FOR UNIQUE ALREADY HANDLED SO NO else
 359 }
 360
 361 template<class T> void remove_from_global_id_vector(T ptr,svector<T> &vect)
 362 {
 363         int32_t start=0;
 364         int32_t end=(int32_t)vect.size()-1;
 365
 366         T cptr;
 367         int32_t mid;
 368         while(start<=end)
 369                 {
 370                 mid=(start+end)>>1;
 371                 cptr=vect[mid];
 372                 if(cptr==ptr)
 373                         {
 374                         vect.erase(mid);
 375                         return;
 376                         }
 377
 378                 if(cptr->global_id>ptr->global_id)end=mid-1;
 379                 else start=mid+1;
 380                 }
 381 }
 382
 383 template<class T> void remove_from_global_id_vector_by_id(int32_t id,svector<T> &vect)
 384 {
 385         int32_t start=0;
 386         int32_t end=(int32_t)vect.size()-1;
 387
 388         T cptr;
 389         int32_t mid;
 390         while(start<=end)
 391                 {
 392                 mid=(start+end)>>1;
 393                 cptr=vect[mid];
 394                 if(cptr->global_id==id)
 395                         {
 396                         vect.erase(mid);
 397                         return;
 398                         }
 399
 400                 if(cptr->global_id>id)end=mid-1;
 401                 else start=mid+1;
 402                 }
 403 }
 404
 405 template<class T> T get_from_global_id_vector(int32_t id,svector<T> &vect)
 406 {
 407         int32_t start=0;
 408         int32_t end=(int32_t)vect.size()-1;
 409
 410         T cptr;
 411         int32_t mid;
 412         while(start<=end)
 413                 {
 414                 mid=(start+end)>>1;
 415
 416                 cptr=vect[mid];
 417                 if(cptr->global_id==id)return cptr;
 418                 else if(cptr->global_id>id)end=mid-1;
 419                 else start=mid+1;
 420                 }
 421
 422         return NULL;
 423 }
 424
 425 template<class T> int32_t get_index_from_global_id_vector(int32_t id,svector<T> &vect)
 426 {
 427         int32_t start=0;
 428         int32_t end=(int32_t)vect.size()-1;
 429
 430         T cptr;
 431         int32_t mid;
 432         while(start<=end)
 433                 {
 434                 mid=(start+end)>>1;
 435
 436                 cptr=vect[mid];
 437                 if(cptr->global_id==id)return mid;
 438                 else if(cptr->global_id>id)end=mid-1;
 439                 else start=mid+1;
 440                 }
 441
 442         return -1;
 443 }
 444
 445 template<class T> VIndex add_to_binary_vector(T ptr,svector<T> &vect)
 446 {
 447         int32_t size=vect.size();
 448         if(size==0)
 449                 {
 450                 vect.push_back(ptr);
 451                 return 0;
 452                 }
 453         if(vect[size-1]<ptr)
 454                 {
 455                 vect.push_back(ptr);
 456                 return size;
 457                 }
 458
 459         int32_t start=0;
 460         int32_t end=size-1;
 461         int32_t mid;
 462         T cptr;
 463
 464         while(start<=end)
 465                 {
 466                 mid=(start+end)>>1;
 467
 468                 cptr=vect[mid];
 469                 if(cptr==ptr)
 470                         {
 471                         vect.insert(mid,ptr);//INSERT A COPY HERE SINCE THIS IS A NON-UNIQUE VECTOR
 472                         return mid;
 473                         }
 474                 if(start==end)
 475                         {
 476                         if(cptr<ptr)
 477                                 {
 478                                 if(start+1>=size)vect.push_back(ptr);
 479                                 else vect.insert(start+1,ptr);
 480                                 return start+1;
 481                                 }
 482                         else
 483                                 {
 484                                 vect.insert(start,ptr);
 485                                 return start;
 486                                 }
 487                         }
 488
 489                 if(cptr>ptr)end=mid-1;
 490                 else start=mid+1;
 491                 }
 492
 493         if(end<0)
 494                 {
 495                 T cptr=vect[start];
 496                 if(cptr<ptr)
 497                         {
 498                         if(start+1>=size)vect.push_back(ptr);
 499                         else vect.insert(start+1,ptr);
 500                         return start+1;
 501                         }
 502                 else
 503                         {
 504                         vect.insert(start,ptr);
 505                         return start;
 506                         }
 507                 }
 508         else if(end<size)
 509                 {
 510                 T cptr=vect[end];
 511                 if(cptr<ptr)
 512                         {
 513                         if(end+1>=size)vect.push_back(ptr);
 514                         else vect.insert(end+1,ptr);
 515                         return end+1;
 516                         }
 517                 else
 518                         {
 519                         vect.insert(end,ptr);
 520                         return end;
 521                         }
 522                 }
 523         else vect.push_back(ptr);
 524         return end;
 525 }
 526
 527 //NOTE: RETURNS -1 IF ALREADY PRESENT, NOT THE INDEX
 528 template<class T> VIndex add_unique_to_binary_vector(T ptr,svector<T> &vect)
 529 {
 530         int32_t size=vect.size();
 531         if(size==0)
 532                 {
 533                 vect.push_back(ptr);
 534                 return 0;
 535                 }
 536         if(vect[size-1]<ptr)
 537                 {
 538                 vect.push_back(ptr);
 539                 return size;
 540                 }
 541
 542         int32_t start=0;
 543         int32_t end=size-1;
 544         int32_t mid;
 545         T cptr;
 546
 547         while(start<=end)
 548                 {
 549                 mid=(start+end)>>1;
 550
 551                 cptr=vect[mid];
 552                 if(cptr==ptr)return -1;//ALREADY IN VECTOR
 553                 if(start==end)
 554                         {
 555                         if(cptr<ptr)
 556                                 {
 557                                 if(start+1>=(int32_t)vect.size())return -1;//push_back() CASE ALREADY HANDLED
 558
 559                                 vect.insert(start+1,ptr);
 560                                 return start+1;
 561                                 }
 562                         else if(cptr>ptr)
 563                                 {
 564                                 vect.insert(start,ptr);
 565                                 return start;
 566                                 }
 567                         return -1;
 568                         }
 569
 570                 if(cptr>ptr)end=mid-1;
 571                 else start=mid+1;
 572                 }
 573
 574         if(end<0)
 575                 {
 576                 T cptr=vect[start];
 577                 if(cptr<ptr)
 578                         {
 579                         if(start+1>=size)return -1;//push_back() CASE ALREADY HANDLED
 580
 581                         vect.insert(start+1,ptr);
 582                         return start+1;
 583                         }
 584                 else if(cptr>ptr)
 585                         {
 586                         vect.insert(start,ptr);
 587                         return start;
 588                         }
 589                 }
 590         else if(end<size)
 591                 {
 592                 T cptr=vect[end];
 593                 if(cptr<ptr)
 594                         {
 595                         if(end+1>=size)return -1;//push_back() CASE ALREADY HANDLED
 596
 597                         vect.insert(end+1,ptr);
 598                         return end+1;
 599                         }
 600                 else if(cptr>ptr)
 601                         {
 602                         vect.insert(end,ptr);
 603                         return end;
 604                         }
 605                 }
 606         return -1;//push_back() CASE ALREADY HANDLED SO NO else
 607 }
 608
 609 //NOTE: RETURNS INDEX IF ALREADY PRESENT
 610 template<class T> VIndex add_unique_to_binary_vector_always_index(T ptr,svector<T> &vect,bool &was_present)
 611 {
 612         was_present=false;
 613
 614         int32_t size=vect.size();
 615         if(size==0)
 616                 {
 617                 vect.push_back(ptr);
 618                 return 0;
 619                 }
 620         if(vect[size-1]<ptr)
 621                 {
 622                 vect.push_back(ptr);
 623                 return size;
 624                 }
 625
 626         int32_t start=0;
 627         int32_t end=size-1;
 628         int32_t mid;
 629         T cptr;
 630
 631         while(start<=end)
 632                 {
 633                 mid=(start+end)>>1;
 634
 635                 cptr=vect[mid];
 636                 if(cptr==ptr){was_present=true;return mid;}//ALREADY IN VECTOR
 637                 if(start==end)
 638                         {
 639                         if(cptr<ptr)
 640                                 {
 641                                 if(start+1>=(int32_t)vect.size())return -1;//push_back() CASE ALREADY HANDLED
 642
 643                                 vect.insert(start+1,ptr);
 644                                 return start+1;
 645                                 }
 646                         else if(cptr>ptr)
 647                                 {
 648                                 vect.insert(start,ptr);
 649                                 return start;
 650                                 }
 651                         return -1;
 652                         }
 653
 654                 if(cptr>ptr)end=mid-1;
 655                 else start=mid+1;
 656                 }
 657
 658         if(end<0)
 659                 {
 660                 T cptr=vect[start];
 661                 if(cptr<ptr)
 662                         {
 663                         if(start+1>=size)return -1;//push_back() CASE ALREADY HANDLED
 664
 665                         vect.insert(start+1,ptr);
 666                         return start+1;
 667                         }
 668                 else if(cptr>ptr)
 669                         {
 670                         vect.insert(start,ptr);
 671                         return start;
 672                         }
 673                 if(cptr==ptr){was_present=true;return start;}//ALREADY IN VECTOR
 674                 }
 675         else if(end<size)
 676                 {
 677                 T cptr=vect[end];
 678                 if(cptr<ptr)
 679                         {
 680                         if(end+1>=size)return -1;//push_back() CASE ALREADY HANDLED
 681
 682                         vect.insert(end+1,ptr);
 683                         return end+1;
 684                         }
 685                 else if(cptr>ptr)
 686                         {
 687                         vect.insert(end,ptr);
 688                         return end;
 689                         }
 690                 if(cptr==ptr){was_present=true;return end;}//ALREADY IN VECTOR
 691                 }
 692         return -1;//push_back() CASE ALREADY HANDLED SO NO else
 693 }
 694
 695 template<class T> void remove_from_binary_vector(T ptr,svector<T> &vect)
 696 {
 697         int32_t start=0;
 698         int32_t end=(int32_t)vect.size()-1;
 699         int32_t mid;
 700         T cptr;
 701
 702         while(start<=end)
 703                 {
 704                 mid=(start+end)>>1;
 705
 706                 cptr=vect[mid];
 707                 if(cptr==ptr)
 708                         {
 709                         vect.erase(mid);
 710                         return;
 711                         }
 712
 713                 if(cptr>ptr)end=mid-1;
 714                 else start=mid+1;
 715                 }
 716 }
 717
 718 template<class T> int32_t get_index_from_binary_vector(T id,svector<T> &vect)
 719 {
 720         int32_t size=vect.size();
 721         if(size==0||id==-1)return -1;
 722
 723         int32_t start=0;
 724         int32_t end=size-1;
 725         int32_t mid;
 726         T cptr;
 727
 728         while(start<=end)
 729                 {
 730                 mid=(start+end)>>1;
 731
 732                 cptr=vect[mid];
 733                 if(cptr==id)
 734                         {
 735                         return mid;
 736                         }
 737
 738                 if(cptr>id)end=mid-1;
 739                 else start=mid+1;
 740                 }
 741
 742         return -1;
 743 }
 744
 745 template<class T> int32_t get_floor_index_from_binary_vector(T ptr,svector<T> &vect)
 746 {
 747         int32_t size=vect.size();
 748         if(size==0)return -1;
 749         if(vect[size-1]<ptr)return size-1;
 750
 751         int32_t start=0;
 752         int32_t end=size-1;
 753         int32_t mid;
 754         T cptr;
 755
 756         while(start<=end)
 757                 {
 758                 mid=(start+end)>>1;
 759
 760                 cptr=vect[mid];
 761                 if(cptr==ptr)
 762                         {
 763                         while(mid>0)
 764                                 {
 765                                 if(vect[mid-1]<ptr)return mid;
 766                                 mid--;
 767                                 }
 768                         return mid;
 769                         }
 770                 if(start==end)
 771                         {
 772                         if(cptr<ptr)
 773                                 {
 774                                 if(start+1>=size)return start;
 775                                 else return start;
 776                                 }
 777                         //NOTE: cptr>ptr as == is already handled above
 778                         else
 779                                 {
 780                                 if(start<=0)return 0;
 781                                 else return start-1;
 782                                 }
 783                         }
 784
 785                 if(cptr>ptr)end=mid-1;
 786                 else start=mid+1;
 787                 }
 788
 789         if(end<0)
 790                 {
 791                 T cptr=vect[start];
 792                 if(cptr<ptr)
 793                         {
 794                         if(start+1>=size)return start;
 795                         else return start;
 796                         }
 797                 else if(cptr>ptr)
 798                         {
 799                         if(start<=0)return 0;
 800                         else return start-1;
 801                         }
 802                 }
 803         else if(end<size)
 804                 {
 805                 T cptr=vect[end];
 806                 if(cptr<ptr)
 807                         {
 808                         if(end+1>=size)return end;
 809                         else return end;
 810                         }
 811                 else if(cptr>ptr)
 812                         {
 813                         if(end<=0)return 0;
 814                         else return end-1;
 815                         }
 816                 }
 817         return start;
 818 }
 819
 820 template<class T> void fixed_array_push_back(T ptr,T *vect,int32_t &size,int32_t max)
 821 {
 822         if(size>=max)return;
 823         vect[size]=ptr;
 824         size++;
 825 }
 826
 827 template<class T> void fixed_array_insert(int32_t index,T ptr,T *vect,int32_t &size,int32_t max)
 828 {
 829         if(size>=max)return;
 830         if(size>0)
 831                 {
 832                 T *ptr1=vect+size;
 833                 T *ptr2=vect+(size-1);
 834                 T *stop=vect+index;
 835                 while(ptr2>=stop)
 836                         {
 837                         (*ptr1)=(*ptr2);
 838                         --ptr1;
 839                         --ptr2;
 840                         }
 841                 (*ptr1)=ptr;
 842                 return;
 843                 }
 844         else
 845                 {
 846                 vect[index]=ptr;
 847                 ++size;
 848                 }
 849 }
 850
 851 template<class T> void add_to_fixed_binary_array(T ptr,T *vect,int32_t &size,int32_t max)
 852 {
 853         if(size==0)
 854                 {
 855                 fixed_array_push_back(ptr,vect,size,max);
 856                 return;
 857                 }
 858         if(vect[size-1]<ptr)
 859                 {
 860                 fixed_array_push_back(ptr,vect,size,max);
 861                 return;
 862                 }
 863
 864         int32_t start=0;
 865         int32_t end=size-1;
 866
 867         T cptr;
 868         int32_t mid;
 869         while(start<=end)
 870                 {
 871                 mid=(start+end)>>1;
 872
 873                 cptr=vect[mid];
 874                 if(cptr==ptr)
 875                         {
 876                         fixed_array_insert(mid,ptr,vect,size,max);//INSERT A COPY SINCE THIS IS NON-UNIQUE CASE
 877                         return;
 878                         }
 879                 if(start==end)
 880                         {
 881                         if(cptr<ptr)
 882                                 {
 883                                 if(start+1>=size)fixed_array_push_back(ptr,vect,size,max);
 884                                 else fixed_array_insert(start+1,ptr,vect,size,max);
 885                                 }
 886                         else fixed_array_insert(start,ptr,vect,size,max);
 887                         return;
 888                         }
 889
 890                 if(cptr>ptr)end=mid-1;
 891                 else start=mid+1;
 892                 }
 893
 894         if(end<0)
 895                 {
 896                 T cptr=vect[start];
 897                 if(cptr<ptr)
 898                         {
 899                         if(start+1>=size)fixed_array_push_back(ptr,vect,size,max);
 900                         else fixed_array_insert(start+1,ptr,vect,size,max);
 901                         }
 902                 else fixed_array_insert(start,ptr,vect,size,max);
 903                 }
 904         else if(end<size)
 905                 {
 906                 T cptr=vect[end];
 907                 if(cptr<ptr)
 908                         {
 909                         if(end+1>=size)fixed_array_push_back(ptr,vect,size,max);
 910                         else fixed_array_insert(end+1,ptr,vect,size,max);
 911                         }
 912                 else fixed_array_insert(end,ptr,vect,size,max);
 913                 }
 914         else fixed_array_push_back(ptr,vect,size,max);
 915 }
 916
 917 template<class T> void add_unique_to_fixed_binary_array(T ptr,T *vect,int32_t &size,int32_t max)
 918 {
 919         if(size==0)
 920                 {
 921                 fixed_array_push_back(ptr,vect,size,max);
 922                 return;
 923                 }
 924         if(vect[size-1]<ptr)
 925                 {
 926                 fixed_array_push_back(ptr,vect,size,max);
 927                 return;
 928                 }
 929
 930         int32_t start=0;
 931         int32_t end=size-1;
 932
 933         T cptr;
 934         int32_t mid;
 935         while(start<=end)
 936                 {
 937                 mid=(start+end)>>1;
 938
 939                 cptr=vect[mid];
 940                 if(cptr==ptr)return;
 941                 if(start==end)
 942                         {
 943                         if(cptr<ptr)
 944                                 {
 945                                 if(start+1>=size)return;//WAS push_back()
 946                                 else fixed_array_insert(start+1,ptr,vect,size,max);
 947                                 }
 948                         else if(cptr>ptr)fixed_array_insert(start,ptr,vect,size,max);
 949                         return;
 950                         }
 951
 952                 if(cptr>ptr)end=mid-1;
 953                 else start=mid+1;
 954                 }
 955
 956         if(end<0)
 957                 {
 958                 T cptr=vect[start];
 959                 if(cptr<ptr)
 960                         {
 961                         if(start+1>=size)return;//WAS push_back()
 962                         else fixed_array_insert(start+1,ptr,vect,size,max);
 963                         }
 964                 else if(cptr>ptr)fixed_array_insert(start,ptr,vect,size,max);
 965                 }
 966         else if(end<size)
 967                 {
 968                 T cptr=vect[end];
 969                 if(cptr<ptr)
 970                         {
 971                         if(end+1>=size)return;//WAS push_back()
 972                         else fixed_array_insert(end+1,ptr,vect,size,max);
 973                         }
 974                 else if(cptr>ptr)fixed_array_insert(end,ptr,vect,size,max);
 975                 }
 976         //NOTE: NO else CASE HERE BECAUSE IN THE NON-UNIQUE VERSION IT JUST PUSHED BACK
 977                 //AND PUSHING BACK IS HANDLED IN THE OPENING FUNCTION
 978 }
 979
 980 template<class T> void add_to_local_id_vector(T ptr,svector<T> &vect)
 981 {
 982         int32_t size=vect.size();
 983         if(size==0)
 984                 {
 985                 vect.push_back(ptr);
 986                 return;
 987                 }
 988         if(vect[size-1]->local_id<ptr->local_id)
 989                 {
 990                 vect.push_back(ptr);
 991                 return;
 992                 }
 993
 994         int32_t start=0;
 995         int32_t end=size-1;
 996
 997         T cptr;
 998         int32_t mid;
 999         while(start<=end)
1000                 {
1001                 mid=(start+end)>>1;
1002
1003                 cptr=vect[mid];
1004                 if(cptr->local_id==ptr->local_id)return;
1005                 if(start==end)
1006                         {
1007                         if(cptr->local_id<ptr->local_id)
1008                                 {
1009                                 if(start+1>=size)return;//push_back() FOR UNIQUE ALREADY HANDLED
1010                                 else vect.insert(start+1,ptr);
1011                                 }
1012                         else if(cptr->local_id>ptr->local_id)vect.insert(start,ptr);
1013                         return;
1014                         }
1015
1016                 if(cptr->local_id>ptr->local_id)end=mid-1;
1017                 else start=mid+1;
1018                 }
1019
1020         if(end<0)
1021                 {
1022                 T cptr=vect[start];
1023                 if(cptr->local_id<ptr->local_id)
1024                         {
1025                         if(start+1>=size)return;//push_back() FOR UNIQUE ALREADY HANDLED
1026                         else vect.insert(start+1,ptr);
1027                         }
1028                 else if(cptr->local_id>ptr->local_id)vect.insert(start,ptr);
1029                 }
1030         else if(end<size)
1031                 {
1032                 T cptr=vect[end];
1033                 if(cptr->local_id<ptr->local_id)
1034                         {
1035                         if(end+1>=size)return;//push_back() FOR UNIQUE ALREADY HANDLED
1036                         else vect.insert(end+1,ptr);
1037                         }
1038                 else if(cptr->local_id>ptr->local_id)vect.insert(end,ptr);
1039                 }
1040 }
1041
1042 template<class T> void remove_from_local_id_vector(T ptr,svector<T> &vect)
1043 {
1044         int32_t start=0;
1045         int32_t end=(int32_t)vect.size()-1;
1046
1047         T cptr;
1048         int32_t mid;
1049         while(start<=end)
1050                 {
1051                 mid=(start+end)>>1;
1052
1053                 cptr=vect[mid];
1054                 if(cptr==ptr)
1055                         {
1056                         vect.erase(mid);
1057                         return;
1058                         }
1059
1060                 if(cptr->local_id>ptr->local_id)end=mid-1;
1061                 else start=mid+1;
1062                 }
1063 }
1064
1065 template<class T> T get_from_local_id_vector(int32_t id,svector<T> &vect)
1066 {
1067         int32_t start=0;
1068         int32_t end=(int32_t)vect.size()-1;
1069
1070         T cptr;
1071         int32_t mid;
1072         while(start<=end)
1073                 {
1074                 mid=(start+end)>>1;
1075
1076                 cptr=vect[mid];
1077                 if(cptr->local_id==id)return cptr;
1078                 else if(cptr->local_id>id)end=mid-1;
1079                 else start=mid+1;
1080                 }
1081
1082         return NULL;
1083 }
1084
1085 template<class T> int32_t get_index_from_local_id_vector(int32_t id,svector<T> &vect)
1086 {
1087         int32_t start=0;
1088         int32_t end=(int32_t)vect.size()-1;
1089
1090         T cptr;
1091         int32_t mid;
1092         while(start<=end)
1093                 {
1094                 mid=(start+end)>>1;
1095
1096                 cptr=vect[mid];
1097                 if(cptr->local_id==id)return mid;
1098                 else if(cptr->local_id>id)end=mid-1;
1099                 else start=mid+1;
1100                 }
1101
1102         return -1;
1103 }
1104
1105 template<class T> void add_to_short_id_vector(T ptr,svector<T> &vect)
1106 {
1107         int16_t size=vect.size();
1108         if(size==0)
1109                 {
1110                 vect.push_back(ptr);
1111                 return;
1112                 }
1113         if(vect[size-1]->short_id<ptr->short_id)
1114                 {
1115                 vect.push_back(ptr);
1116                 return;
1117                 }
1118
1119         int16_t start=0;
1120         int16_t end=size-1;
1121         int16_t mid;
1122         T cptr;
1123
1124         while(start<=end)
1125                 {
1126                 mid=(start+end)>>1;
1127
1128                 cptr=vect[mid];
1129                 if(cptr->short_id==ptr->short_id)return;
1130                 if(start==end)
1131                         {
1132                         if(cptr->short_id<ptr->short_id)
1133                                 {
1134                                 if(start+1>=size)return;//push_back() FOR UNIQUE ALREADY HANDLED
1135                                 else vect.insert(start+1,ptr);
1136                                 }
1137                         else if(cptr->short_id>ptr->short_id)vect.insert(start,ptr);
1138                         return;
1139                         }
1140
1141                 if(cptr->short_id>ptr->short_id)end=mid-1;
1142                 else start=mid+1;
1143                 }
1144
1145         if(end<0)
1146                 {
1147                 T cptr=vect[start];
1148                 if(cptr->short_id<ptr->short_id)
1149                         {
1150                         if(start+1>=size)return;//push_back() FOR UNIQUE ALREADY HANDLED
1151                         else vect.insert(start+1,ptr);
1152                         }
1153                 else if(cptr->short_id>ptr->short_id)vect.insert(start,ptr);
1154                 }
1155         else if(end<size)
1156                 {
1157                 T cptr=vect[end];
1158                 if(cptr->short_id<ptr->short_id)
1159                         {
1160                         if(end+1>=size)return;//push_back() FOR UNIQUE ALREADY HANDLED
1161                         else vect.insert(end+1,ptr);
1162                         }
1163                 else if(cptr->short_id>ptr->short_id)vect.insert(end,ptr);
1164                 }
1165 }
1166
1167 template<class T> void remove_from_short_id_vector(T ptr,svector<T> &vect)
1168 {
1169         int16_t start=0;
1170         int16_t end=(int16_t)vect.size()-1;
1171         T cptr;
1172
1173         while(start<=end)
1174                 {
1175                 int16_t mid=(start+end)>>1;
1176
1177                 T cptr=vect[mid];
1178                 if(cptr==ptr)
1179                         {
1180                         vect.erase(mid);
1181                         return;
1182                         }
1183
1184                 if(cptr->short_id>ptr->short_id)end=mid-1;
1185                 else start=mid+1;
1186                 }
1187 }
1188
1189 template<class T> T get_from_short_id_vector(int16_t id,svector<T> &vect)
1190 {
1191         int16_t start=0;
1192         int16_t end=(int16_t)vect.size()-1;
1193         int16_t mid;
1194         T cptr;
1195
1196         while(start<=end)
1197                 {
1198                 mid=(start+end)>>1;
1199
1200                 cptr=vect[mid];
1201                 if(cptr->short_id==id)
1202                         {
1203                         return cptr;
1204                         }
1205
1206                 if(cptr->short_id>id)end=mid-1;
1207                 else start=mid+1;
1208                 }
1209
1210         return NULL;
1211 }
1212
1213 template<class T> int16_t get_index_from_short_id_vector(int16_t id,svector<T> &vect)
1214 {
1215         int16_t start=0;
1216         int16_t end=(int16_t)vect.size()-1;
1217         int16_t mid;
1218         T cptr;
1219
1220         while(start<=end)
1221                 {
1222                 mid=(start+end)>>1;
1223
1224                 cptr=vect[mid];
1225                 if(cptr->short_id==id)
1226                         {
1227                         return mid;
1228                         }
1229
1230                 if(cptr->short_id>id)end=mid-1;
1231                 else start=mid+1;
1232                 }
1233
1234         return -1;
1235 }