binaries/src/clustalo/src/hhalign/hash.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.h 143 2010-10-14 13:11:14Z andreas $
  19  */
  20
  21 // Class for Hash data structure
  22 // * works in the same way as a hash in Perl
  23 // * keys are strings of type char*
  24 // * data elements are of type Typ
  25 // * objects have to be declared with maximal size, e.g. Hash hash1(10000) (num_slots should not be a power of 2)
  26 // * works also if maximal size is exceeded, but gets slower by a factor ~num_keys/num_slots
  27 //
  28 // Applications
  29 // * fast storage and retrieval of data by a key
  30 // * fast check if a string occurs in a list of strings (data field not used)
  31 //
  32 // Time complexity: (L is the length of the key string)
  33 // * Show(key), Add(key), Remove(key): O(L) for calculating hash value & compare keys in slot list
  34 // * ReadNext, ReadCurrent, RemoveCurrent: O(L) for copying key into returned string
  35 // * Contains: O(L) for calculating hash value
  36 // * Size, MaxLen, Reset: O(1)
  37 // * RemoveAll(), Hash() and ~Hash(): O(num_slots)
  38 //
  39 // Memory complexity: ~3*num_keys*(datasize+12bytes) + num_slots*4bytes + total added length of keys (including \0)
  40 //
  41 // Implementation:
  42 // Hash is an array of pointers to lists of size num_slots. The lists, called slots, contain key/data pairs.
  43 // When a key/data pair is added (e.g. with Add()) the array index i for the key (0<=i<num_slots)
  44 // is calculated with the HashValue() function.
  45 // When data is to be retrieved for key (e.g. with Show()) the hash value for key is calculated and
  46 // the corresponding list (=slot) is searched for the occurence of the key.
  47 // Array elements of hash values that have no keys associated yet contain the null pointer
  48 // for faster rejection of undefined keys.
  49 //
  50
  51 ////////////////////////////////////////////////////////////////////////////////////////////
  52 // Declaration of Pair, consisting of a key string and a data element of type Typ
  53 ////////////////////////////////////////////////////////////////////////////////////////////
  54
  55 template<class Typ>
  56 class Pair
  57 {
  58 public:
  59   char* key;             //hash key
  60   Typ data;              //data for key
  61   Pair() {}
  62   Pair(char* k, Typ& d) {key = new char[strlen(k)+1]; strcpy(key,k); data=d;}
  63   Pair(int& l, char* k, Typ& d) {key = new char[l+1]; strcpy(key,k); data=d;}
  64 };
  65
  66
  67 ////////////////////////////////////////////////////////////////////////////////////////////
  68 // Declaration of Slot, a list of key/data pairs
  69 ////////////////////////////////////////////////////////////////////////////////////////////
  70
  71 template<class Typ>
  72 class Slot : public List< Pair<Typ> >
  73 {
  74 public:
  75   //Destructor of Slot deletes whole list TOGETHER WITH THE KEY STRINGS
  76   ~Slot() {this->Reset(); while (!this->End()) delete[] this->Pop().key; }
  77
  78   // Push key/data pair onto slot list and return address of data element
  79   // Attention: l must be at least length of key
  80   inline Typ* Push(int& l, char* key, Typ& data)
  81   {
  82     Pair<Typ> pair(l,key,data);  //create a pair with key/data
  83     return &(List<Pair<Typ> >::Push(pair)->data);
  84   }
  85 };
  86
  87
  88 ////////////////////////////////////////////////////////////////////////////////////////////
  89 // Declaration of Hash, an array of slots, i.e. pointers to lists of key/data
  90 ////////////////////////////////////////////////////////////////////////////////////////////
  91
  92 template<class Typ>
  93 class Hash
  94 {
  95 private:
  96   int num_slots;         //number of slots in slot[]. num_slots is set with the constructor
  97   int curr;              //index of current slot
  98   int prev;              //index of slot from previous ReadNext()
  99   int num_keys;          //total number of keys in hash
 100   int max_len;           //length of longest key in hash
 101   int key_len;           //length of key in argument
 102   Typ fail;
 103
 104   Slot<Typ>** slot;      //each slot[i] (i<num_slots) points to a list of key/data pairs for this slot
 105
 106   inline unsigned int HashValue(char* key);  //returns the hash value for key
 107
 108 public:
 109   Hash();
 110   Hash(int nslots);
 111   Hash(int nslots, Typ n);
 112   ~Hash();
 113
 114   // Set Fail element to be returned when the current key or supplied key are not defined
 115   inline void Null(Typ f) {fail=f;}
 116   inline void Fail(Typ f) {fail=f;}
 117
 118   // Set 'fail' element to be returned when the current key or supplied key are not defined (default: 0)
 119   void New(int nslots, Typ n=static_cast<Typ>(0));
 120
 121   // Update maximum key length and caculate key_len;
 122   inline void KeyLen() {if(key_len>max_len) max_len=key_len; return;}
 123
 124
 125 ////////////////////////////////////////////////////////////////////////////////////////////
 126 //                 Methods that work with a key supplied as an argument
 127
 128   // Return data element for key. Returns 'fail' if key does not exist
 129   Typ Show(char* key);
 130   inline Typ operator[](char* key) {return Show(key);}
 131
 132   // Add/replace key/data pair to hash and return address of data element for key
 133   Typ* Add(char* key, Typ data);
 134
 135   // Add key to hash and return address of data element. If key exists leave data element unchanged, else set it to 'fail'.
 136   Typ* Add(char* key);
 137   inline Typ* operator()(char* key) {return Add(key);}
 138
 139   // Remove key from hash and return data element for key ('fail' if key does not exist)
 140   Typ Remove(char* key);
 141
 142   // Remove all keys from hash
 143   void RemoveAll();
 144
 145
 146 ///////////////////////////////////////////////////////////////////////////////////////////
 147 //                  Methods that work with an internal "current key":
 148 // It is set to the first key by Reset() and moves to the next key with ReadNext or RemoveCurrent
 149 // Note:the methods above (e.g. Store, Show, [], Add, (), etc. DO NOT CHANGE the current key
 150
 151   // Return data of next key. Return 'fail' data and empty key if at end
 152   Typ ReadNext();
 153
 154   // Write next key into variable key and return data. Return 'fail' data and empty key if at end
 155   // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
 156   Typ ReadNext(char* key);
 157
 158   // Return data of current key
 159   Typ ReadCurrent();
 160
 161   // Write key last read into variable key and return data
 162   // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
 163   Typ ReadCurrent(char* key);
 164
 165   // Remove current key, return data and advance to next key
 166   Typ RemoveCurrent();
 167
 168   // Remove current key, return data, copy current key into key, and advance to next key
 169   // (After Reset() remove first element)
 170   // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
 171   Typ RemoveCurrent(char* key);
 172
 173   // Reset readout of keys to beginning of hash
 174   void Reset();
 175
 176   // Returns 1 if the current key has arrived at the end, 0 otherwise
 177   int End() {return (curr>=num_slots);}
 178
 179
 180
 181 ///////////////////////////////////////////////////////////////////////////////////////////
 182 //            Methods that return usefull information about the data stored in Hash:
 183
 184   // Returns 1 if the hash contains key, 0 otherwise
 185   int Contains(char* key);
 186
 187   // Return number of slots
 188   int Size()  {return num_keys;}
 189
 190   // Return length of longest key INCLUDING DELETED KEYS (excluding \0)
 191   int MaxLen()  {return max_len;}
 192
 193   //print out list of keys and data
 194   void Print();
 195
 196   //Print out hash with internal representation as array
 197   void DebugPrint();
 198 };
 199