+++ /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