Resolve/C++ Catalog
AT/General/Hash.h
Copyright © 2010, Reusable Software Research Group, The Ohio State University

//  /*-------------------------------------------------------------------*\
//  |   Abstract Template : General_Hash
//  \*-------------------------------------------------------------------*/

#ifndef AT_GENERAL_HASH
#define AT_GENERAL_HASH 1

///------------------------------------------------------------------------
/// Interface -------------------------------------------------------------
///------------------------------------------------------------------------

abstract_template <
	concrete_instance class T
    >
utility_class General_Hash
{
public:

    // For correct program behavior, HASH_FUNCTION must be a function
    // (a requirement of all math definitions) and its range must be
    // restricted to the set of standard machine-representable
    // integers.  However, the purpose of a hashing implementation is
    // to achieve better time performance (while maintaining correct
    // behavior).  It is necessary to consider factors other than just
    // this HASH_FUNCTION when reasoning about performance.  One such
    // factor is the distribution of values of type T that
    // is deemed likely to arise in a particular application.  Another
    // crucial factor is the pair of lower and upper bounds on the
    // indices into the hash table used in the application.  For
    // simplicity, let's assume that the lower bound is zero (0) and
    // the upper bound is ht_size - 1.  Then, the ideal situation for
    // obtaining good time performance is when N(k) is essentially
    // independent of k, where:
    //           N(k) = |{x: T
    //		               where
    //			    (HASH_FUNCTION(x) mod ht_size = k) (x)}|
    //		 (i.e., N(k) is the number of values x of type
    //		 T that give a particular value
    //		 HASH_FUNCTION(x) mod ht_size = k).
    // Intuitively, the values of HASH_FUNCTION mod ht_size are
    // distributed fairly evenly across the values of type
    // T, at least for the distribution of values of type
    // T that is deemed likely to arise in a particular
    // application.

    /*!
	math definition HASH_FUNCTION (
		x: T
	    ): integer satisfies restriction
	    MINIMUM_INTEGER <= HASH_FUNCTION (x) <= MAXIMUM_INTEGER
    !*/

    utility_function Integer Hash (
	    preserves T& x
	);
    /*!
	ensures
	    Hash = HASH_FUNCTION (x)		
    !*/

};

#endif // AT_GENERAL_HASH