/*
 *  Copyright 2001, 2002 Adrian Thurston <thurston@complang.org>
 */
/*  This file is part of Aapl.
 *
 *  Aapl is free software; you can redistribute it and/or modify it under the
 *  terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
 *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
 *  more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
 *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
#ifndef _AAPL_TABLE_H
#define _AAPL_TABLE_H
#ifdef AAPL_NAMESPACE
namespace Aapl {
#endif
/**
 * \addtogroup vector
 * @{
 */
/** \class Table
 * \brief Base class for dynamic arrays.
 *
 * Table is used as the common data storage class for vectors. It does not
 * provide any methods to operate on the data and as such it is not intended
 * to be used directly. It exists so that algorithms that operatate on dynamic
 * arrays can be written without knowing about the various vector classes that
 * my exist.
 */
/*@}*/
/* Table class. */
template <class T> class Table
{
public:
        /* Default Constructor. */
        inline Table();
        /**
         * \brief Get the length of the vector.
         *
         * \returns the length of the vector.
         */
        long length() const
                { return tabLen; }
        /**
         * \brief Table data.
         *
         * The pointer to the elements in the vector. Modifying the vector may
         * cause this pointer to change.
         */
        T *data;
        /**
         * \brief Table length.
         *
         * The number of items of type T in the table.
         */
        long tabLen;
        /**
         * \brief Allocated length.
         *
         * The number of items for which there is room in the current allocation.
         */
        long allocLen;
};
/**
 * \brief Default constructor
 *
 * Initialize table data to empty.
 */
template <class T> inline Table<T>::Table()
:
        data(0),
        tabLen(0),
        allocLen(0)
{
}
/* Default shared table header class. */
struct STabHead
{
        /**
         * \brief Table length.
         *
         * The number of items of type T in the table.
         */
        long tabLen;
        /**
         * \brief Allocated length.
         *
         * The number of items for which there is room in the current allocation.
         */
        long allocLen;
        /**
         * \brief Ref Count.
         *
         * The number of shared vectors referencing this data.
         */
        long refCount;
};
/**
 * \addtogroup vector
 * @{
 */
/** \class STable
 * \brief Base class for implicitly shared dynamic arrays.
 *
 * STable is used as the common data storage class for shared vectors. It does
 * not provide any methods to operate on the data and as such it is not
 * intended to be used directly. It exists so that algorithms that operatate
 * on dynamic arrays can be written without knowing about the various shared
 * vector classes that my exist.
 */
/*@}*/
/* STable class. */
template <class T> class STable
{
public:
        /* Default Constructor. */
        inline STable();
        /**
         * \brief Get the length of the shared vector.
         *
         * \returns the length of the shared vector.
         */
        long length() const
                { return data == 0 ? 0 : (((STabHead*)data) - 1)->tabLen; }
         
        /**
         * \brief Get header of the shared vector.
         *
         * \returns the header of the shared vector.
         */
        STabHead *header() const
                { return data == 0 ? 0 : (((STabHead*)data) - 1); }
        /**
         * \brief Table data.
         *
         * The pointer to the elements in the vector. The shared table header is
         * located just behind the data. Modifying the vector may cause this
         * pointer to change.
         */
        T *data;
};
/**
 * \brief Default constructor
 *
 * Initialize shared table data to empty.
 */
template <class T> inline STable<T>::STable()
:
        data(0)
{
}
/* If needed is greater than existing, give twice needed. */
#define EXPN_UP( existing, needed ) \
                needed > existing ? (needed<<1) : existing
         
/* If needed is less than 1 quarter existing, give twice needed. */
#define EXPN_DOWN( existing, needed ) \
                needed < (existing>>2) ? (needed<<1) : existing
/**
 * \addtogroup vector
 * @{
 */
/** \class ResizeExpn
 * \brief Exponential table resizer. 
 *
 * ResizeExpn is the default table resizer. When an up resize is needed, space
 * is doubled. When a down resize is needed, space is halved.  The result is
 * that when growing the vector in a linear fashion, the number of resizes of
 * the allocated space behaves logarithmically.
 *
 * If only up resizes are done, there will never be more than 2 times the
 * needed space allocated. If down resizes are done as well, there will never
 * be more than 4 times the needed space allocated.  ResizeExpn uses this 50%
 * usage policy on up resizing and 25% usage policy on down resizing to
 * improve performance when repeatedly inserting and removing a small number
 * of elements relative to the size of the array.  This scheme guarantees that
 * repetitive inserting and removing of a small number of elements will never
 * result in repetative reallocation.
 *
 * The sizes passed to the resizer from the vectors are in units of T.
 */
/*@}*/
/* Exponential resizer. */
class ResizeExpn
{
protected:
        /**
         * \brief Determine the new table size when up resizing.
         *
         * If the existing size is insufficient for the space needed then allocate
         * twice the space needed. Otherwise use the existing size.
         *
         * \returns The new table size.
         */
        static inline long upResize( long existing, long needed )
                { return EXPN_UP( existing, needed ); }
        /**
         * \brief Determine the new table size when down resizing.
         *
         * If the space needed is less than one quarter of the existing size then
         * allocate twice the space needed. Otherwise use the exitsing size.
         *
         * \returns The new table size.
         */
        static inline long downResize( long existing, long needed )
                { return EXPN_DOWN( existing, needed ); }
};
#undef EXPN_UP
#undef EXPN_DOWN
#ifdef AAPL_NAMESPACE
}
#endif
#endif /* _AAPL_TABLE_H */