--- /dev/null
+/* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+
+/*********************************************************************
+ * Clustal Omega - Multiple sequence alignment
+ *
+ * Copyright (C) 2010 University College Dublin
+ *
+ * Clustal-Omega is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This file is part of Clustal-Omega.
+ *
+ ********************************************************************/
+
+/*
+ * RCS $Id: hash.h 143 2010-10-14 13:11:14Z andreas $
+ */
+
+// Class for Hash data structure
+// * works in the same way as a hash in Perl
+// * keys are strings of type char*
+// * data elements are of type Typ
+// * objects have to be declared with maximal size, e.g. Hash hash1(10000) (num_slots should not be a power of 2)
+// * works also if maximal size is exceeded, but gets slower by a factor ~num_keys/num_slots
+//
+// Applications
+// * fast storage and retrieval of data by a key
+// * fast check if a string occurs in a list of strings (data field not used)
+//
+// Time complexity: (L is the length of the key string)
+// * Show(key), Add(key), Remove(key): O(L) for calculating hash value & compare keys in slot list
+// * ReadNext, ReadCurrent, RemoveCurrent: O(L) for copying key into returned string
+// * Contains: O(L) for calculating hash value
+// * Size, MaxLen, Reset: O(1)
+// * RemoveAll(), Hash() and ~Hash(): O(num_slots)
+//
+// Memory complexity: ~3*num_keys*(datasize+12bytes) + num_slots*4bytes + total added length of keys (including \0)
+//
+// Implementation:
+// Hash is an array of pointers to lists of size num_slots. The lists, called slots, contain key/data pairs.
+// When a key/data pair is added (e.g. with Add()) the array index i for the key (0<=i<num_slots)
+// is calculated with the HashValue() function.
+// When data is to be retrieved for key (e.g. with Show()) the hash value for key is calculated and
+// the corresponding list (=slot) is searched for the occurence of the key.
+// Array elements of hash values that have no keys associated yet contain the null pointer
+// for faster rejection of undefined keys.
+//
+
+////////////////////////////////////////////////////////////////////////////////////////////
+// Declaration of Pair, consisting of a key string and a data element of type Typ
+////////////////////////////////////////////////////////////////////////////////////////////
+
+template<class Typ>
+class Pair
+{
+public:
+ char* key; //hash key
+ Typ data; //data for key
+ Pair() {}
+ Pair(char* k, Typ& d) {key = new char[strlen(k)+1]; strcpy(key,k); data=d;}
+ Pair(int& l, char* k, Typ& d) {key = new char[l+1]; strcpy(key,k); data=d;}
+};
+
+
+////////////////////////////////////////////////////////////////////////////////////////////
+// Declaration of Slot, a list of key/data pairs
+////////////////////////////////////////////////////////////////////////////////////////////
+
+template<class Typ>
+class Slot : public List< Pair<Typ> >
+{
+public:
+ //Destructor of Slot deletes whole list TOGETHER WITH THE KEY STRINGS
+ ~Slot() {this->Reset(); while (!this->End()) delete[] this->Pop().key; }
+
+ // Push key/data pair onto slot list and return address of data element
+ // Attention: l must be at least length of key
+ inline Typ* Push(int& l, char* key, Typ& data)
+ {
+ Pair<Typ> pair(l,key,data); //create a pair with key/data
+ return &(List<Pair<Typ> >::Push(pair)->data);
+ }
+};
+
+
+////////////////////////////////////////////////////////////////////////////////////////////
+// Declaration of Hash, an array of slots, i.e. pointers to lists of key/data
+////////////////////////////////////////////////////////////////////////////////////////////
+
+template<class Typ>
+class Hash
+{
+private:
+ int num_slots; //number of slots in slot[]. num_slots is set with the constructor
+ int curr; //index of current slot
+ int prev; //index of slot from previous ReadNext()
+ int num_keys; //total number of keys in hash
+ int max_len; //length of longest key in hash
+ int key_len; //length of key in argument
+ Typ fail;
+
+ Slot<Typ>** slot; //each slot[i] (i<num_slots) points to a list of key/data pairs for this slot
+
+ inline unsigned int HashValue(char* key); //returns the hash value for key
+
+public:
+ Hash();
+ Hash(int nslots);
+ Hash(int nslots, Typ n);
+ ~Hash();
+
+ // Set Fail element to be returned when the current key or supplied key are not defined
+ inline void Null(Typ f) {fail=f;}
+ inline void Fail(Typ f) {fail=f;}
+
+ // Set 'fail' element to be returned when the current key or supplied key are not defined (default: 0)
+ void New(int nslots, Typ n=static_cast<Typ>(0));
+
+ // Update maximum key length and caculate key_len;
+ inline void KeyLen() {if(key_len>max_len) max_len=key_len; return;}
+
+
+////////////////////////////////////////////////////////////////////////////////////////////
+// Methods that work with a key supplied as an argument
+
+ // Return data element for key. Returns 'fail' if key does not exist
+ Typ Show(char* key);
+ inline Typ operator[](char* key) {return Show(key);}
+
+ // Add/replace key/data pair to hash and return address of data element for key
+ Typ* Add(char* key, Typ data);
+
+ // Add key to hash and return address of data element. If key exists leave data element unchanged, else set it to 'fail'.
+ Typ* Add(char* key);
+ inline Typ* operator()(char* key) {return Add(key);}
+
+ // Remove key from hash and return data element for key ('fail' if key does not exist)
+ Typ Remove(char* key);
+
+ // Remove all keys from hash
+ void RemoveAll();
+
+
+///////////////////////////////////////////////////////////////////////////////////////////
+// Methods that work with an internal "current key":
+// It is set to the first key by Reset() and moves to the next key with ReadNext or RemoveCurrent
+// Note:the methods above (e.g. Store, Show, [], Add, (), etc. DO NOT CHANGE the current key
+
+ // Return data of next key. Return 'fail' data and empty key if at end
+ Typ ReadNext();
+
+ // Write next key into variable key and return data. Return 'fail' data and empty key if at end
+ // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
+ Typ ReadNext(char* key);
+
+ // Return data of current key
+ Typ ReadCurrent();
+
+ // Write key last read into variable key and return data
+ // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
+ Typ ReadCurrent(char* key);
+
+ // Remove current key, return data and advance to next key
+ Typ RemoveCurrent();
+
+ // Remove current key, return data, copy current key into key, and advance to next key
+ // (After Reset() remove first element)
+ // Attention: 'key' must have memory of at least char[MaxLen()+1] allocated!
+ Typ RemoveCurrent(char* key);
+
+ // Reset readout of keys to beginning of hash
+ void Reset();
+
+ // Returns 1 if the current key has arrived at the end, 0 otherwise
+ int End() {return (curr>=num_slots);}
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////
+// Methods that return usefull information about the data stored in Hash:
+
+ // Returns 1 if the hash contains key, 0 otherwise
+ int Contains(char* key);
+
+ // Return number of slots
+ int Size() {return num_keys;}
+
+ // Return length of longest key INCLUDING DELETED KEYS (excluding \0)
+ int MaxLen() {return max_len;}
+
+ //print out list of keys and data
+ void Print();
+
+ //Print out hash with internal representation as array
+ void DebugPrint();
+};
+
git://source.jalview.org / jabaws.git / blobdiff