parttype.h

Go to the documentation of this file.

/// @addtogroup unifexp
/// @{

/////////////////////////////////////////////////////////////////////////////
///
/// @file parttype.h
///
/// This file contains the definition of an abstract partition type.
///
/// @author Pawel Pilarczyk
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 2007 by Pawel Pilarczyk.
//
// This file is part of my research program package.  This 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 software 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 General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this software; see the file "license.txt".  If not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// Started on March 8, 2007. Last revision: August 22, 2007.

#ifndef _parttype_h_
#define _parttype_h_

#include <vector>
#include <string>
#include <algorithm>
#include "chomp/struct/bitfield.h"
#include "maptype.h"


namespace unifexp {

// --------------------------------------------------
// ----------------- partition type -----------------
// --------------------------------------------------

/// An abstract partition type.
/// All the other partition types should inherit from this one.
template <class numType>
class partType
{
public:
        /// The constructor.
        partType ();

        /// The virtual destructor.
        virtual ~partType ();

        /// Returns the name of the object.
        virtual std::string name () const = 0;

        /// Creates a partition based on the given map, the requested
        /// number of elements in the partition, and the width of the
        /// critical neighborhood.
        virtual void create (const mapType<numType> &theMap, int partCount,
                const numType &delta) = 0;

        /// Runs the bisection algorithm to find the maximal element in the
        /// partition table which is less than or equal to the given number.
        /// Uses operator < for comparision, operator [] to extract from
        /// the table. Returns the number of that element or -1 if the number
        /// is below the leftmost limit.
        int find (const numType &number) const;

        /// Returns the given interval bound from the partition: the left end
        /// of the n-th interval, or right end of the (n-1)-th one.
        /// Does not verify the correctness of the index.
        /// Note that the operator [] which accesses a non-constant object
        /// is protected, so it may be necessary to use a const reference
        /// to access the data of a non-const object with operator [].
        /// In case of any problems, use the function "at" instead (it is
        /// also safer, because it verifies the correctness of the index).
        const numType &operator [] (int n) const;

        /// Returns the given interval bound from the partition: the left end
        /// of the n-th interval, or right end of the (n-1)-th one.
        /// Verifies the correctness of the index and throws an error message
        /// if n is out of range.
        const numType &at (int n) const;

        /// Returns true if the given interval is part of a neighborhood
        /// of some critical point. Returns false otherwise.
        /// Note that this function does not verify the correctness of n,
        /// so it must be used with caution.
        bool isCritical (int n) const;

        /// Returns the number of the interval which is a neighborhood
        /// of a critical point, or throws an exception if 'n' out of scope.
        /// See the map class for the actual number of critical points.
        int getCritical (int n = 0) const;

protected:
        /// Allocates the table to store the given number of intervals.
        /// It is automatically deallocated by the destructor.
        void allocate (int n);

        /// Adds a critical interval to the list of critical intervals.
        void addCritical (int n);

        /// Returns the given interval bound from the partition: the left end
        /// of the n-th interval, or right end of the (n-1)-th one.
        /// Does not verify the correctness of the index.
        numType &operator [] (int n);

private:
        /// The table with the bounds of partition intervals.
        /// Initially this address is set to 0.
        /// Use the function "allocate" to (re)allocate this table,
        /// and the operator [] and function "at" to access its elements.
        numType *intBounds;

        /// The number of intervals in the partition.
        /// Initialized to 0, set by the function "allocate".
        int intCount;

        /// The list of critical intervals.
        std::vector<int> critical;

        /// A bit field which stores the information about intervals
        /// if they are critical or not.
        chomp::homology::BitField b;

        /// Copy constructor is not implemented.
        partType (const partType<numType> &);

        /// Assignment operator is not implemented.
        partType<numType> &operator = (const partType<numType> &);

}; /* class partType */

// --------------------------------------------------

template <class numType>
inline partType<numType>::partType (): intBounds (0), intCount (0)
{
        return;
} /* partType::partType */

template <class numType>
inline partType<numType>::partType (const partType<numType> &)
{
        throw "Copy constructor not implemented for partitions.";
        return;
} /* partType::partType */

template <class numType>
inline partType<numType> &partType<numType>::operator =
        (const partType<numType> &)
{
        throw "Assignment operator not implemented for partitions.";
        return *this;
} /* partType::operator = */

template <class numType>
inline partType<numType>::~partType ()
{
        if (intBounds)
        {
                delete [] intBounds;
                b. free ();
        }
        return;
} /* partType::~partType */

template <class numType>
inline const numType &partType<numType>::operator [] (int n) const
{
        return intBounds [n];
} /* partType::operator [] */

template <class numType>
inline numType &partType<numType>::operator [] (int n)
{
        return intBounds [n];
} /* partType::operator [] */

template <class numType>
inline const numType &partType<numType>::at (int n) const
{
        if (!intBounds || (n < 0) || (n > intCount))
                throw "Partition element out of range requested.";
        return intBounds [n];
} /* partType::at */

template <class numType>
inline bool partType<numType>::isCritical (int n) const
{
        return !!b. test (n);
//      return (std::find (critical. begin (), critical. end (), n) !=
//              critical. end ());
} /* partType::isCritical */

template <class numType>
inline int partType<numType>::getCritical (int n) const
{
        if ((n < 0) || (n >= static_cast<int> (critical. size ())))
                throw "Critical interval number out of range.";
        return critical [n];
} /* partType::getCritical */

// --------------------------------------------------

template <class numType>
inline int partType<numType>::find (const numType &number) const
{
        if (!intBounds)
                throw "Partition not allocated.";
        if (number < intBounds [0])
                return -1;
        if (number >= intBounds [intCount])
                return intCount;
        int lowerbound = 0, upperbound = intCount + 1;
        while (upperbound - lowerbound > 1)
        {
                int middle = (lowerbound + upperbound) >> 1;
                if (number < intBounds [middle])
                        upperbound = middle;
                else
                        lowerbound = middle;
        }
        return lowerbound;
} /* partType::find */

template <class numType>
inline void partType<numType>::addCritical (int n)
{
        critical. push_back (n);
        b. set (n);
        return;
} /* partType::addCritical */

template <class numType>
inline void partType<numType>::allocate (int n)
{
        if (n <= 0)
        {
                throw "A non-positive number of partition intervals "
                        "requested.";
        }
        if (intBounds)
        {
                delete [] intBounds;
                b. free ();
        }
        intBounds = new numType [n + 1];
        intCount = n;
        b. allocate (n);
        b. clearall (n);
        critical. clear ();
        return;
} /* partType::allocate */


} // namespace unifexp

#endif // _parttype_h_

/// @}