binaries/src/clustalo/src/hhalign/hash-C.h

   1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2
   3 /*********************************************************************
   4  * Clustal Omega - Multiple sequence alignment
   5  *
   6  * Copyright (C) 2010 University College Dublin
   7  *
   8  * Clustal-Omega is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License as
  10  * published by the Free Software Foundation; either version 2 of the
  11  * License, or (at your option) any later version.
  12  *
  13  * This file is part of Clustal-Omega.
  14  *
  15  ********************************************************************/
  16
  17 /*
  18  * RCS $Id: hash-C.h 309 2016-06-13 14:10:11Z fabian $
  19  */
  20
  21 // hash.C
  22 // Class for Hash data structure
  23 // * works in the same way as a hash in Perl
  24 // * keys are strings of type char*
  25 // * data elements are of type Typ
  26 // * objects have to be declared with maximal size, e.g. Hash hash1(10000) (num_slots should not be a power of 2)
  27 // * works also if maximal size is exceeded, but gets slower by a factor ~num_keys/num_slots
  28
  29 /*
  30  * RCS $Id: hash-C.h 309 2016-06-13 14:10:11Z fabian $
  31  */
  32
  33 #ifndef HASH
  34 #define HASH
  35
  36 #ifndef MAIN
  37 #include <iostream>   // cin, cout, cerr
  38 #include <cstdio>     // printf
  39 #include <stdlib.h>   // exit
  40 #include <string>     // strcmp, strstr
  41 #include <math.h>     // sqrt, pow
  42 #include <limits.h>   // INT_MIN
  43 #include <float.h>    // FLT_MIN
  44 #include <ctype.h>    // islower, isdigit etc
  45 #include <time.h>     // clock
  46 #include <errno.h>    // perror()
  47 using std::cout;
  48 using std::cerr;
  49 using std::endl;
  50 using std::ios;
  51 using std::ifstream;
  52 using std::ofstream;
  53 #endif
  54
  55 #ifndef JLIST
  56 #define JLIST
  57 #include "list.h"       // List<Typ>
  58 #include "list-C.h"    ////////////////////////////////// DEBUG
  59 #endif
  60
  61 #include "hash.h"
  62 //#include "new_new.h" /* memory tracking */
  63
  64
  65 //////////////////////////////////////////////////////////////////////////////
  66 ////////////////////// Methods of class Hash /////////////////////////////////
  67 //////////////////////////////////////////////////////////////////////////////
  68
  69 //////////////////////////////////////////////////////////////////////////////
  70 //                                Private Methods
  71
  72
  73 //////////////////////////////////////////////////////////////////////////////
  74 //                        Constructor and Destructor of Hash
  75 //////////////////////////////////////////////////////////////////////////////
  76 // Constructor of class Hash
  77 //////////////////////////////////////////////////////////////////////////////
  78 template<class Typ>
  79 Hash<Typ>::Hash()
  80 {
  81   num_keys=0; max_len=0; prev=curr=num_slots = 0; slot=NULL;
  82 }
  83
  84 template<class Typ>
  85 Hash<Typ>::Hash(int nslots)
  86 {
  87   num_keys=0; max_len=0; prev=curr=num_slots = nslots;
  88   slot = new Slot<Typ>*[num_slots];             //Create array of num_slots slots
  89   for (int i=0; i<num_slots; i++) slot[i]=NULL; //set pointers to NULL
  90   fail = static_cast<Typ>(0);
  91 }
  92
  93 template<class Typ>
  94 Hash<Typ>::Hash(int nslots, Typ f)
  95 {
  96   num_keys=0; max_len=0; prev=curr=num_slots = nslots;
  97   slot = new Slot<Typ>*[num_slots];             //Create array of num_slots slots
  98   for (int i=0; i<num_slots; i++) slot[i]=NULL; //set pointers to NULL
  99   fail=f;
 100 }
 101
 102
 103 ////////////////////////////////////////////////////////////////////////////////////////////
 104 // Destructor of class Hash
 105 ////////////////////////////////////////////////////////////////////////////////////////////
 106 template<class Typ>
 107 Hash<Typ>::~Hash()
 108 {
 109   RemoveAll();
 110   delete[] slot; slot = NULL;
 111 }
 112
 113
 114 ////////////////////////////////////////////////////////////////////////////////////////////
 115 // Hash function
 116 ////////////////////////////////////////////////////////////////////////////////////////////
 117 template<class Typ>
 118 inline unsigned int Hash<Typ>::HashValue(char* key)  //returns the hash value for key
 119     {
 120       // Calculate a hash value by the division method:
 121       // Transform key into a natural number k = sum ( key[i]*128^(L-i) ) and calculate i= k % num_slots.
 122       // Since calculating k would lead to an overflow, i is calculated iteratively
 123       // and at each iteration the part divisible by num_slots is subtracted, i.e. (% num_slots is taken).
 124       if (key==NULL) {printf("Warning from hash.C: key=NULL\n"); return 0;}
 125       unsigned int i=0;     // Start of iteration: k is zero
 126       char* c = key;
 127       while(*c) i = ((i<<7) + *(c++)) % num_slots;
 128       key_len = c - key;
 129       //   cerr<<"      Hash value for \'"<<key<<"\' is "<<i<<"\n";
 130       return i;
 131     }
 132
 133 ////////////////////////////////////////////////////////////////////////////////////////////
 134 // Create new hash (and delete any data present)
 135 ////////////////////////////////////////////////////////////////////////////////////////////
 136 template<class Typ>
 137 void Hash<Typ>::New(int nslots, Typ f)
 138 {
 139   fail=f;
 140   RemoveAll();
 141   delete[] slot; slot = NULL;
 142   num_keys=0; max_len=0; prev=curr=num_slots = nslots;
 143   slot = new Slot<Typ>*[num_slots];             //Create array of num_slots slots
 144   for (int i=0; i<num_slots; i++) slot[i]=NULL; //set pointers to NULL
 145 }
 146
 147
 148
 149 ////////////////////////////////////////////////////////////////////////////////////////////
 150 //                  Methods that work with a key supplied as an argument
 151
 152 ////////////////////////////////////////////////////////////////////////////////////////////
 153 // Return data element for key. Returns 'fail' if key does not exist
 154 ////////////////////////////////////////////////////////////////////////////////////////////
 155 template<class Typ>
 156 Typ Hash<Typ>::Show(char* key)
 157 {
 158   Slot<Typ>* pslot;
 159   int i = HashValue(key);
 160
 161   pslot = slot[i];
 162   if (!pslot) return fail;
 163   pslot->Reset();
 164   do{
 165     if(!strcmp(pslot->ReadNext().key,key)) return pslot->ReadCurrent().data;
 166   } while(!pslot->End());
 167   return fail;
 168 }
 169
 170 ////////////////////////////////////////////////////////////////////////////////////////////
 171 // Add/replace key/data pair to hash and return address of data element
 172 ////////////////////////////////////////////////////////////////////////////////////////////
 173 template<class Typ>
 174 Typ* Hash<Typ>::Add(char* key, Typ data)
 175 {
 176   Pair<Typ>* pairp;
 177   Slot<Typ>* pslot;
 178   int i = HashValue(key);
 179
 180   pslot = slot[i];
 181   if (!pslot) { num_keys++; KeyLen(); slot[i]=new(Slot<Typ>); return slot[i]->Push(key_len,key,data);}
 182   pslot->Reset();
 183   do
 184     {
 185       pairp = pslot->ReadNextAddress();
 186       if(!strcmp(pairp->key,key))
 187         {
 188           pairp->data=data;
 189           pslot->Overwrite(*pairp);
 190           return &(pairp->data);
 191         }
 192     } while(!pslot->End());
 193   num_keys++;
 194   KeyLen();
 195   return pslot->Push(key_len,key,data);
 196 }
 197
 198
 199
 200 ////////////////////////////////////////////////////////////////////////////////////////////
 201 // Add key to hash and return address of data element.
 202 // If key exists leave data element unchanged, else set it to 'fail'.
 203 ////////////////////////////////////////////////////////////////////////////////////////////
 204 template<class Typ>
 205 Typ* Hash<Typ>::Add(char* key)
 206 {
 207   Slot<Typ>* pslot;
 208   int i = HashValue(key);
 209
 210   pslot = slot[i];
 211   if (!pslot) { num_keys++; KeyLen(); slot[i]=new(Slot<Typ>); return slot[i]->Push(key_len,key,fail);}
 212   pslot->Reset();
 213   do
 214     {
 215       if(!strcmp(pslot->ReadNext().key,key))
 216         {
 217           return &((pslot->ReadCurrentAddress())->data);
 218         }
 219     } while(!pslot->End());
 220   num_keys++;
 221   KeyLen();
 222   return pslot->Push(key_len,key,fail);
 223 }
 224
 225
 226 /////////////////////////////////////////////////////////////////////////////////////////////
 227 // Remove key from hash and return data element for key ('fail' if key does not exist)
 228 /////////////////////////////////////////////////////////////////////////////////////////////
 229 template<class Typ>
 230 Typ Hash<Typ>::Remove(char* key)
 231 {
 232   Slot<Typ>* pslot;
 233   int i = HashValue(key);
 234
 235   pslot = slot[i];
 236   if (!pslot) return fail;
 237   pslot->Reset();
 238   do
 239     {
 240       if(!strcmp(pslot->ReadNext().key,key))
 241         {
 242           num_keys--;
 243           pslot->Delete();
 244           // if key was the only element in pslot then delete whole list
 245           if (pslot->Size()==0) {delete pslot; pslot = NULL;slot[i]=0;}
 246           return pslot->ReadCurrent().data;
 247         }
 248     } while(!pslot->End());
 249   return fail;
 250 }
 251
 252
 253 //////////////////////////////////////////////////////////////////////////////
 254 // Remove all keys from hash;
 255 //////////////////////////////////////////////////////////////////////////////
 256 template<class Typ>
 257 void Hash<Typ>::RemoveAll()
 258 {
 259   for(int i=0; i<num_slots; i++)
 260     if(slot[i]) {delete slot[i]; slot[i]=NULL;}
 261   num_keys=0;
 262   max_len=0;
 263   curr=prev=num_slots;
 264 }
 265
 266
 267
 268
 269
 270 //////////////////////////////////////////////////////////////////////////////
 271 //                  Methods that work with an internal "current key":
 272
 273
 274 //////////////////////////////////////////////////////////////////////////////
 275 // Return data of next key. Return 'fail' data and empty key if at end
 276 //////////////////////////////////////////////////////////////////////////////
 277 template<class Typ>
 278 Typ Hash<Typ>::ReadNext()
 279 {
 280   Pair<Typ>* pairp;
 281   Slot<Typ>* pslot;
 282
 283   if (curr>=num_slots) {return fail;}
 284   pslot = slot[curr];  // current list is never empty, except when current=num_slots
 285   pairp = pslot->ReadNextAddress();
 286   if (pslot->End()) {
 287     prev=curr;
 288     do   // move on to next non-empty list
 289       {
 290         if (++curr>=num_slots) return pairp->data;
 291         pslot = slot[curr];
 292       } while (!pslot);
 293     pslot->Reset();
 294   }
 295   return pairp->data;
 296 }
 297
 298 //////////////////////////////////////////////////////////////////////////////
 299 // Write next key into variable key and return data. Return 'fail' data and empty key if at end
 300 // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
 301 //////////////////////////////////////////////////////////////////////////////
 302 template<class Typ>
 303 Typ Hash<Typ>::ReadNext(char* key)
 304 {
 305   Pair<Typ>* pairp;
 306   Slot<Typ>* pslot;
 307
 308   if (curr>=num_slots) {*key='\0'; return fail;}
 309   pslot = slot[curr];  // current list is never empty, except when current=num_slots
 310   pairp = pslot->ReadNextAddress();
 311   strcpy(key,pairp->key);
 312   if (pslot->End()) {
 313     prev=curr;
 314     do   // move on to next non-empty list
 315       {
 316         if (++curr>=num_slots) return pairp->data;
 317         pslot = slot[curr];
 318       } while (!pslot);
 319     pslot->Reset();
 320   }
 321   return pairp->data;
 322 }
 323
 324
 325
 326 //////////////////////////////////////////////////////////////////////////////
 327 // Return data of current key
 328 //////////////////////////////////////////////////////////////////////////////
 329 template<class Typ>
 330 Typ Hash<Typ>::ReadCurrent()
 331 {
 332   Pair<Typ>* pairp;
 333   Slot<Typ>* pslot;
 334
 335   curr=prev;
 336   if (curr>=num_slots) {return fail;}
 337   pslot = slot[curr];  // current list is never empty, except when current=num_slots
 338   pairp = &(pslot->ReadCurrent());
 339   if (pslot->End()) {
 340     do   // move on to next non-empty list
 341       {
 342         if (++curr>=num_slots) return pairp->data;
 343         pslot = slot[curr];
 344       } while (!pslot);
 345     pslot->Reset();
 346   }
 347   return pairp->data;
 348 }
 349
 350 //////////////////////////////////////////////////////////////////////////////
 351 // Write key last read into variable key and return data
 352 // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
 353 //////////////////////////////////////////////////////////////////////////////
 354 template<class Typ>
 355 Typ Hash<Typ>::ReadCurrent(char* key)
 356 {
 357   Pair<Typ>* pairp;
 358   Slot<Typ>* pslot;
 359
 360   curr=prev;
 361   if (curr>=num_slots) {*key='\0'; return fail;}
 362   pslot = slot[curr];  // current list is never empty, except when current=num_slots
 363   pairp = &(pslot->ReadCurrent());
 364   strcpy(key,pairp->key);
 365   if (pslot->End()) {
 366     do   // move on to next non-empty list
 367       {
 368         if (++curr>=num_slots) return pairp->data;
 369         pslot = slot[curr];
 370       } while (!pslot);
 371     pslot->Reset();
 372   }
 373   return pairp->data;
 374 }
 375
 376 //////////////////////////////////////////////////////////////////////////////
 377 // Remove current key, return data, and advance to next key (after Reset() remove first element)
 378 //////////////////////////////////////////////////////////////////////////////
 379 template<class Typ>
 380 Typ Hash<Typ>::RemoveCurrent()
 381 {
 382   Pair<Typ>* pairp;
 383   Slot<Typ>* pslot;
 384   curr=prev;
 385
 386   if (curr>=num_slots) {return fail;}
 387   pslot = slot[curr];  // current list is never empty, except when current=num_slots
 388   pairp = &(pslot->Delete());
 389   num_keys--;
 390   // if key was the only element in pslot then delete whole list
 391   if (pslot->Size()==0) {delete pslot; pslot = NULL; slot[curr]=0;}
 392   if (!pslot || pslot->End()) {
 393     do   // move on to next non-empty list
 394       {
 395         if (++curr>=num_slots) {prev=curr; return pairp->data;}
 396         pslot = slot[curr];
 397       } while (!pslot);
 398     pslot->Reset();
 399   }
 400   prev=curr;
 401   return pairp->data;
 402 }
 403
 404 //////////////////////////////////////////////////////////////////////////////
 405 // Remove current key, return data, copy current key into key, and advance to next key
 406 // (After Reset() remove first element)
 407 // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
 408 //////////////////////////////////////////////////////////////////////////////
 409 template<class Typ>
 410 Typ Hash<Typ>::RemoveCurrent(char* key)
 411 {
 412   Pair<Typ>* pairp;
 413   Slot<Typ>* pslot;
 414
 415   curr=prev;
 416   if (curr>=num_slots) {*key='\0'; return fail;}
 417   pslot = slot[curr];  // current list is never empty, except when current=num_slots
 418   pairp = &(pslot->Delete());
 419   strcpy(key,pairp->key);
 420   num_keys--;
 421   // if key was the only element in pslot then delete whole list
 422   if (pslot->Size()==0) {delete pslot; pslot = NULL; slot[curr]=0;}
 423   if (!pslot || pslot->End()) {
 424     do   // move on to next non-empty list
 425       {
 426         if (++curr>=num_slots) {prev=curr; return pairp->data;}
 427         pslot = slot[curr];
 428       } while (!pslot);
 429     pslot->Reset();
 430   }
 431   prev=curr;
 432   return pairp->data;
 433 }
 434
 435
 436
 437 //////////////////////////////////////////////////////////////////////////////
 438 // Reset current position to beginning of hash
 439 //////////////////////////////////////////////////////////////////////////////
 440 template<class Typ>
 441 void Hash<Typ>::Reset()
 442   {
 443     curr=-1;
 444     Slot<Typ>* pslot;
 445     do
 446       {
 447         curr++;
 448         if (curr>=num_slots) {prev=curr; return;}
 449         pslot = slot[curr];
 450       } while (!pslot);
 451      pslot->Reset();
 452      prev=curr;
 453      return;
 454   }
 455
 456
 457 /////////////////////////////////////////////////////////////////////////////////////////////
 458 //            Methods that return usefull information about the data stored in Hash:
 459
 460
 461 ////////////////////////////////////////////////////////////////////////////////////////////
 462 // Returns 1 if the hash contains key, 0 otherwise
 463 ////////////////////////////////////////////////////////////////////////////////////////////
 464 template<class Typ>
 465 int Hash<Typ>::Contains(char* key)
 466 {
 467   Slot<Typ>* pslot;
 468   int i = HashValue(key);
 469
 470   pslot = slot[i];
 471   if (!pslot) return 0;
 472   pslot->Reset();
 473   do{
 474     if(!strcmp(pslot->ReadNext().key,key)) return 1;
 475   } while(!pslot->End());
 476   return 0;
 477 }
 478
 479 /////////////////////////////////////////////////////////////////////////////////////////////
 480 //print out list of keys and data
 481 /////////////////////////////////////////////////////////////////////////////////////////////
 482 template<class Typ>
 483 void Hash<Typ>::Print()
 484 {
 485   char key[MaxLen()+1];
 486
 487   cout<<"\nPrint hash:\n";
 488   Reset();
 489   while(!End())
 490     cout<<key<<"->"<<ReadNext(key)<<"\n";
 491 }
 492
 493 /////////////////////////////////////////////////////////////////////////////////////////////
 494 //Print out hash with internal representation as array
 495 /////////////////////////////////////////////////////////////////////////////////////////////
 496 template<class Typ>
 497 void Hash<Typ>::DebugPrint()
 498 {
 499   Pair<Typ>* pairp;
 500   Slot<Typ>* pslot;
 501
 502   cout<<"\n";
 503   cout<<"Debug-print hash:";
 504   for(int i=0; i<num_slots; i++)
 505     {
 506       pslot = slot[i];
 507       if (pslot)
 508         {
 509           cout<<"\nhash value "<<i;
 510           pslot->Reset();
 511           while(!pslot->End())
 512             {
 513               pairp = pslot->ReadNextAddress();
 514               cout<<"  "<<pairp->key<<"->"<<pairp->data;
 515             }
 516         }
 517     }
 518   cout<<"\n\n";
 519   return;
 520 }
 521
 522
 523
 524 #endif /* HASH */
 525
 526
 527
 528 ////////////////////////////////////////////////////////////////////////////////
 529 // Main program: test class Hash
 530 ////////////////////////////////////////////////////////////////////////////////
 531 //  int main()
 532 //  {
 533 //    Hash<int> ihash(5);
 534 //    char* key=new char[128];
 535 //    int data;
 536
 537 //    ihash.Fail(1000);
 538 //    ihash.Add("So many monsters",36);
 539 //    ihash.Add("So many chickens",25);
 540
 541 // //    cerr<<"Address of ihash(\"So many monsters\") is "<<ihash("So many monsters")<<"\n";
 542 // //    cerr<<"Address of ihash(\"So many monsters\") is "<<ihash("So many monsters")<<"\n";
 543 // //    *ihash("So many monsters")=2;
 544 // //    (*ihash("So many monsters"))++;
 545 // //    (*ihash("So many monsters"))++;
 546 //    cout<<"Size of hash="<<ihash.Size()<<"\n";
 547 //    ihash.DebugPrint();
 548 //    ihash.Print();
 549
 550 //    strcpy(key,"Some more monsters");
 551 //    ihash.Add(key,3);
 552 //    strcpy(key,"Even more monsters");
 553 //    ihash.Add(key,7);
 554 //    cout<<"Size of hash="<<ihash.Size()<<"\n";
 555 //    cout<<"Maximum key length = "<<ihash.MaxLen()<<"\n";
 556 //    ihash.Print();
 557
 558 //    cout<<"ihash.Remove(\"Even more monsters\") returns "<<ihash.Remove("Even more monsters")<<"\n";
 559 //    ihash.Print();
 560
 561
 562 //    cout<<"ihash.Remove(\"More monsters\") returns "<<ihash.Remove("More monsters")<<"\n";
 563 //    ihash.Add("So many chickens",999);
 564 //    ihash.Add("So many monster",1);
 565 //    ihash.Print();
 566
 567 //    cout<<"So many chickens:"<<ihash.Show("So many chickens")<<"\n";
 568 //    cout<<"Size of hash="<<ihash.Size()<<"\n";
 569
 570
 571
 572 //    ihash.Reset();
 573 //    while (!ihash.End())
 574 //      {
 575 //        data = ihash.ReadNext(key);
 576 //        cout<<" "<<key<<"->"<<data<<endl;
 577 //        data = ihash.ReadCurrent(key);
 578 //        cout<<" "<<key<<"->"<<data<<endl;
 579 //      }
 580 //    cout<<"Removing all keys..."<<endl;
 581 //    cout<<"Size of hash="<<ihash.Size()<<"\n";
 582 //    ihash.Reset();
 583 //    while (ihash.Size())
 584 //      {
 585 //        data = ihash.RemoveCurrent(key);
 586 //        cout<<" "<<key<<"->"<<data<<"\n";
 587 //        cout<<"Size of hash="<<ihash.Size()<<"\n";
 588 //      }
 589
 590 //    ihash.ReadCurrent(key);
 591
 592 //    ihash.Print();
 593 //    return 0;
 594 //  }