1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
3 /*********************************************************************
4 * Clustal Omega - Multiple sequence alignment
6 * Copyright (C) 2010 University College Dublin
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.
13 * This file is part of Clustal-Omega.
15 ********************************************************************/
18 * RCS $Id: hash.h 143 2010-10-14 13:11:14Z andreas $
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
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)
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)
39 // Memory complexity: ~3*num_keys*(datasize+12bytes) + num_slots*4bytes + total added length of keys (including \0)
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.
51 ////////////////////////////////////////////////////////////////////////////////////////////
52 // Declaration of Pair, consisting of a key string and a data element of type Typ
53 ////////////////////////////////////////////////////////////////////////////////////////////
60 Typ data; //data for key
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;}
67 ////////////////////////////////////////////////////////////////////////////////////////////
68 // Declaration of Slot, a list of key/data pairs
69 ////////////////////////////////////////////////////////////////////////////////////////////
72 class Slot : public List< Pair<Typ> >
75 //Destructor of Slot deletes whole list TOGETHER WITH THE KEY STRINGS
76 ~Slot() {this->Reset(); while (!this->End()) delete[] this->Pop().key; }
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)
82 Pair<Typ> pair(l,key,data); //create a pair with key/data
83 return &(List<Pair<Typ> >::Push(pair)->data);
88 ////////////////////////////////////////////////////////////////////////////////////////////
89 // Declaration of Hash, an array of slots, i.e. pointers to lists of key/data
90 ////////////////////////////////////////////////////////////////////////////////////////////
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
104 Slot<Typ>** slot; //each slot[i] (i<num_slots) points to a list of key/data pairs for this slot
106 inline unsigned int HashValue(char* key); //returns the hash value for key
111 Hash(int nslots, Typ n);
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;}
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));
121 // Update maximum key length and caculate key_len;
122 inline void KeyLen() {if(key_len>max_len) max_len=key_len; return;}
125 ////////////////////////////////////////////////////////////////////////////////////////////
126 // Methods that work with a key supplied as an argument
128 // Return data element for key. Returns 'fail' if key does not exist
130 inline Typ operator[](char* key) {return Show(key);}
132 // Add/replace key/data pair to hash and return address of data element for key
133 Typ* Add(char* key, Typ data);
135 // Add key to hash and return address of data element. If key exists leave data element unchanged, else set it to 'fail'.
137 inline Typ* operator()(char* key) {return Add(key);}
139 // Remove key from hash and return data element for key ('fail' if key does not exist)
140 Typ Remove(char* key);
142 // Remove all keys from hash
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
151 // Return data of next key. Return 'fail' data and empty key if at end
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);
158 // Return data of current key
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);
165 // Remove current key, return data and advance to next key
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);
173 // Reset readout of keys to beginning of hash
176 // Returns 1 if the current key has arrived at the end, 0 otherwise
177 int End() {return (curr>=num_slots);}
181 ///////////////////////////////////////////////////////////////////////////////////////////
182 // Methods that return usefull information about the data stored in Hash:
184 // Returns 1 if the hash contains key, 0 otherwise
185 int Contains(char* key);
187 // Return number of slots
188 int Size() {return num_keys;}
190 // Return length of longest key INCLUDING DELETED KEYS (excluding \0)
191 int MaxLen() {return max_len;}
193 //print out list of keys and data
196 //Print out hash with internal representation as array