cluster.cpp

Go to the documentation of this file.

/*****************************************************************************
    NumeRe: Framework fuer Numerische Rechnungen
    Copyright (C) 2019  Erik Haenel et al.
 
    This program 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 3 of the License, or
    (at your option) any later version.
 
    This program 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 program.  If not, see <http://www.gnu.org/licenses/>.
******************************************************************************/
 
#include <gsl/gsl_statistics.h>
 
#include "cluster.hpp"
#include "../ui/error.hpp"
 
namespace NumeRe
{
    //
    // class CLUSTER
    //
    //
 
    void Cluster::assign(const Cluster& cluster)
    {
        bSortCaseInsensitive = false;
 
        // Clear the contents first
        clear();
 
        nGlobalType = cluster.nGlobalType;
 
        // Fill the cluster with copies from the passed cluster
        for (size_t i = 0; i < cluster.vClusterArray.size(); i++)
        {
            if (cluster.vClusterArray[i]->getType() == ClusterItem::ITEMTYPE_DOUBLE)
                vClusterArray.push_back(new ClusterDoubleItem(cluster.vClusterArray[i]->getDouble()));
            else
                vClusterArray.push_back(new ClusterStringItem(cluster.vClusterArray[i]->getInternalString()));
        }
    }
 
 
    void Cluster::assign(const std::vector<mu::value_type>& vVals)
    {
        bSortCaseInsensitive = false;
 
        // clear the contents first
        clear();
 
        nGlobalType = ClusterItem::ITEMTYPE_DOUBLE;
 
        // Fill the cluster with new double items
        for (size_t i = 0; i < vVals.size(); i++)
        {
            vClusterArray.push_back(new ClusterDoubleItem(vVals[i]));
        }
    }
 
 
    void Cluster::assign(const std::vector<std::string>& vStrings)
    {
        bSortCaseInsensitive = false;
 
        // Clear the contents first
        clear();
 
        nGlobalType = ClusterItem::ITEMTYPE_STRING;
 
        // Fill the cluster with new string items
        for (size_t i = 0; i < vStrings.size(); i++)
        {
            vClusterArray.push_back(new ClusterStringItem(vStrings[i]));
        }
    }
 
 
    void Cluster::assignVectorResults(Indices _idx, int nNum, mu::value_type* data)
    {
        if (nGlobalType != ClusterItem::ITEMTYPE_DOUBLE)
            nGlobalType = ClusterItem::ITEMTYPE_INVALID;
 
        if (nNum == 1)
            _idx.row.setOpenEndIndex(std::max((size_t)_idx.row.front(), size()) - 1);
 
        // Assign the single results
        for (size_t i = 0; i < _idx.row.size(); i++)
        {
            if (nNum > 1 && (size_t)nNum <= i)
                return;
 
            // Expand the current cluster on-the-fly
            while (_idx.row[i] >= (int)vClusterArray.size())
                push_back(new ClusterDoubleItem(NAN));
 
            // Assign the value and expand singletons
            if (vClusterArray[_idx.row[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE)
            {
                // Re-create the current item as double
                delete vClusterArray[_idx.row[i]];
                vClusterArray[_idx.row[i]] = new ClusterDoubleItem(nNum == 1 ? data[0] : data[i]);
            }
            else
                vClusterArray[_idx.row[i]]->setDouble(nNum == 1 ? data[0] : data[i]);
        }
    }
 
 
    int Cluster::compare(int i, int j, int col)
    {
        if (isString() || isMixed())
        {
            if (bSortCaseInsensitive)
            {
                if (toLowerCase(vClusterArray[i]->getParserString()) < toLowerCase(vClusterArray[j]->getParserString()))
                    return -1;
 
                if (toLowerCase(vClusterArray[i]->getParserString()) == toLowerCase(vClusterArray[j]->getParserString()))
                    return 0;
            }
            else
            {
                if (vClusterArray[i]->getParserString() < vClusterArray[j]->getParserString())
                    return -1;
 
                if (vClusterArray[i]->getParserString() == vClusterArray[j]->getParserString())
                    return 0;
            }
 
            return 1;
        }
        else if (isDouble())
        {
            if (vClusterArray[i]->getDouble().real() < vClusterArray[j]->getDouble().real())
                return -1;
 
            if (vClusterArray[i]->getDouble() == vClusterArray[j]->getDouble())
                return 0;
 
            return 1;
        }
 
        return 0;
    }
 
 
    bool Cluster::isValue(int line, int col)
    {
        if (vClusterArray[line]->getType() == ClusterItem::ITEMTYPE_DOUBLE && !std::isnan(vClusterArray[line]->getDouble().real()))
            return true;
 
        if (vClusterArray[line]->getType() == ClusterItem::ITEMTYPE_STRING && vClusterArray[line]->getParserString() != "\"\"")
            return true;
 
        return false;
    }
 
 
    void Cluster::reorderElements(std::vector<int> vIndex, int i1, int i2)
    {
        std::vector<ClusterItem*> vSortVector = vClusterArray;
 
        // Copy the contents directly from the
        // prepared in the new order
        for (int i = 0; i <= i2-i1; i++)
        {
            vClusterArray[i+i1] = vSortVector[vIndex[i]];
        }
    }
 
 
    void Cluster::reduceSize(size_t s)
    {
        if (vClusterArray.size() <= s)
            return;
 
        for (size_t i = s; i < vClusterArray.size(); i++)
            delete vClusterArray[i];
 
        vClusterArray.resize(s);
    }
 
 
    void Cluster::push_back(ClusterItem* item)
    {
        if (item)
            vClusterArray.push_back(item);
 
        if (nGlobalType == ClusterItem::ITEMTYPE_INVALID)
            return;
 
        if (item->getType() != nGlobalType)
            nGlobalType = ClusterItem::ITEMTYPE_MIXED;
    }
 
 
    void Cluster::push_back(const mu::value_type& val)
    {
        vClusterArray.push_back(new ClusterDoubleItem(val));
 
        if (nGlobalType == ClusterItem::ITEMTYPE_INVALID)
            return;
 
        if (nGlobalType == ClusterItem::ITEMTYPE_STRING)
            nGlobalType = ClusterItem::ITEMTYPE_MIXED;
    }
 
 
    void Cluster::push_back(const std::string& strval)
    {
        vClusterArray.push_back(new ClusterStringItem(strval));
 
        if (nGlobalType == ClusterItem::ITEMTYPE_INVALID)
            return;
 
        if (nGlobalType == ClusterItem::ITEMTYPE_DOUBLE)
            nGlobalType = ClusterItem::ITEMTYPE_MIXED;
    }
 
 
    void Cluster::pop_back()
    {
        if (vClusterArray.size())
        {
            delete vClusterArray.back();
            vClusterArray.pop_back();
 
            nGlobalType = ClusterItem::ITEMTYPE_INVALID;
        }
    }
 
 
    size_t Cluster::size() const
    {
        return vClusterArray.size();
    }
 
 
    size_t Cluster::getBytes() const
    {
        size_t nBytes = 0;
 
        // Go through the internal cluster array and calculate
        // the bytes needed for each single cluster item
        for (size_t i = 0; i < vClusterArray.size(); i++)
        {
            if (vClusterArray[i]->getType() == ClusterItem::ITEMTYPE_DOUBLE)
                nBytes += sizeof(mu::value_type);
            else if (vClusterArray[i]->getType() == ClusterItem::ITEMTYPE_STRING)
                nBytes += sizeof(char) * (vClusterArray[i]->getParserString().length()-2);
        }
 
        return nBytes;
    }
 
 
    void Cluster::clear()
    {
        for (size_t i = 0; i < vClusterArray.size(); i++)
        {
            delete vClusterArray[i];
        }
 
        vClusterArray.clear();
        nGlobalType = ClusterItem::ITEMTYPE_INVALID;
    }
 
 
    bool Cluster::isMixed() const
    {
        // Only do something, if the array has a length
        if (vClusterArray.size())
        {
            if (nGlobalType != ClusterItem::ITEMTYPE_INVALID)
                return nGlobalType == ClusterItem::ITEMTYPE_MIXED;
 
            // Store the first type
            int nFirstType = vClusterArray[0]->getType();
 
            for (size_t i = 1; i < vClusterArray.size(); i++)
            {
                // Is there any item with a different type?
                if (vClusterArray[i]->getType() != nFirstType)
                {
                    nGlobalType = ClusterItem::ITEMTYPE_MIXED;
                    return true;
                }
            }
 
            nGlobalType = nFirstType;
            return false;
        }
 
        return false;
    }
 
 
    bool Cluster::isDouble() const
    {
        // Only do something, if the array has a length
        if (vClusterArray.size())
        {
            if (nGlobalType != ClusterItem::ITEMTYPE_INVALID)
                return nGlobalType == ClusterItem::ITEMTYPE_DOUBLE;
 
            for (size_t i = 0; i < vClusterArray.size(); i++)
            {
                // Is there any item, which is NOT a double?
                if (vClusterArray[i]->getType() != ClusterItem::ITEMTYPE_DOUBLE)
                {
                    if (i)
                        nGlobalType = ClusterItem::ITEMTYPE_MIXED;
 
                    return false;
                }
            }
 
            nGlobalType = ClusterItem::ITEMTYPE_DOUBLE;
            return true;
        }
 
        return false;
    }
 
 
    bool Cluster::isString() const
    {
        // Only do something, if the array has a length
        if (vClusterArray.size())
        {
            if (nGlobalType != ClusterItem::ITEMTYPE_INVALID)
                return nGlobalType == ClusterItem::ITEMTYPE_STRING;
 
            for (size_t i = 0; i < vClusterArray.size(); i++)
            {
                // Is there any item, which is NOT a string?
                if (vClusterArray[i]->getType() != ClusterItem::ITEMTYPE_STRING)
                {
                    if (i)
                        nGlobalType = ClusterItem::ITEMTYPE_MIXED;
 
                    return false;
                }
            }
 
            nGlobalType = ClusterItem::ITEMTYPE_STRING;
            return true;
        }
 
        return false;
    }
 
 
    unsigned short Cluster::getType(size_t i) const
    {
        if (vClusterArray.size() > i)
            return vClusterArray[i]->getType();
 
        return ClusterItem::ITEMTYPE_INVALID;
    }
 
 
    mu::value_type Cluster::getDouble(size_t i) const
    {
        if (vClusterArray.size() > i)
            return vClusterArray[i]->getDouble();
 
        return NAN;
    }
 
 
    void Cluster::setDouble(size_t i, const mu::value_type& value)
    {
        // Create new items if needed
        while (vClusterArray.size() <= i)
            push_back(new ClusterDoubleItem(NAN));
 
        // Assign the data
        if (vClusterArray[i]->getType() != ClusterItem::ITEMTYPE_DOUBLE)
        {
            // Re-create the item as double item
            delete vClusterArray[i];
            vClusterArray[i] = new ClusterDoubleItem(value);
        }
        else
            vClusterArray[i]->setDouble(value);
 
        nGlobalType = ClusterItem::ITEMTYPE_INVALID;
    }
 
 
    std::vector<mu::value_type> Cluster::getDoubleArray() const
    {
        std::vector<mu::value_type> vArray;
 
        for (size_t i = 0; i < vClusterArray.size(); i++)
        {
            vArray.push_back(vClusterArray[i]->getDouble());
        }
 
        return vArray;
    }
 
 
    void Cluster::insertDataInArray(std::vector<mu::value_type>* vTarget, const VectorIndex& _vLine)
    {
        if (vTarget == nullptr)
            return;
 
        // Try to resize the array as copy-efficient as
        // possible
        if (_vLine.size() > 1 && !vClusterArray.size())
            vTarget->resize(1, NAN);
        else
        {
            vTarget->resize(_vLine.size(), NAN);
 
            // Insert the elements in the passed array
            for (unsigned int i = 0; i < _vLine.size(); i++)
            {
                if (_vLine[i] >= (int)vClusterArray.size() || _vLine[i] < 0)
                    (*vTarget)[i] = NAN;
                else
                    (*vTarget)[i] = vClusterArray[_vLine[i]]->getDouble();
 
            }
        }
    }
 
 
    void Cluster::setDoubleArray(const std::vector<mu::value_type>& vVals)
    {
        // Create new cluster items, if needed
        while (vClusterArray.size() < vVals.size())
            push_back(new ClusterDoubleItem(NAN));
 
        for (size_t i = 0; i < vVals.size(); i++)
        {
            // Assign the value
            if (vClusterArray[i]->getType() != ClusterItem::ITEMTYPE_DOUBLE)
            {
                // Re-create the current item as double
                delete vClusterArray[i];
                vClusterArray[i] = new ClusterDoubleItem(vVals[i]);
            }
            else
                static_cast<ClusterDoubleItem*>(vClusterArray[i])->setDouble(vVals[i]);
        }
 
        reduceSize(vVals.size());
        nGlobalType = ClusterItem::ITEMTYPE_DOUBLE;
    }
 
 
    void Cluster::setDoubleArray(int nNum, mu::value_type* data)
    {
        // Create new cluster items, if needed
        while (vClusterArray.size() < (size_t)nNum)
            push_back(new ClusterDoubleItem(NAN));
 
        for (int i = 0; i < nNum; i++)
        {
            // Assign the value
            if (vClusterArray[i]->getType() != ClusterItem::ITEMTYPE_DOUBLE)
            {
                // Re-create the current item as double
                delete vClusterArray[i];
                vClusterArray[i] = new ClusterDoubleItem(data[i]);
            }
            else
                static_cast<ClusterDoubleItem*>(vClusterArray[i])->setDouble(data[i]);
        }
 
        reduceSize(nNum);
        nGlobalType = ClusterItem::ITEMTYPE_DOUBLE;
    }
 
 
    void Cluster::assignResults(Indices _idx, int nNum, mu::value_type* data)
    {
        // If the indices indicate a complete override
        // do that here and return
        if (_idx.row.isOpenEnd() && _idx.row.front() == 0)
        {
            setDoubleArray(nNum, data);
            return;
        }
 
        // Assign the results depending on the type of the
        // passed indices
        assignVectorResults(_idx, nNum, data);
    }
 
 
    std::string Cluster::getString(size_t i) const
    {
        if (vClusterArray.size() > i)
            return vClusterArray[i]->getString();
 
        return "\"\"";
    }
 
 
    std::string Cluster::getInternalString(size_t i) const
    {
        if (vClusterArray.size() > i)
            return vClusterArray[i]->getInternalString();
 
        return "";
    }
 
 
    std::string Cluster::getParserString(size_t i) const
    {
        if (vClusterArray.size() > i)
            return vClusterArray[i]->getParserString();
 
        return "\"\"";
    }
 
 
    void Cluster::setString(size_t i, const std::string& strval)
    {
        // Create new cluster items, if needed
        while (vClusterArray.size() <= i)
            push_back(new ClusterStringItem(""));
 
        // Assign the value
        if (vClusterArray[i]->getType() != ClusterItem::ITEMTYPE_STRING)
        {
            // Re-create the current item as a string
            delete vClusterArray[i];
            vClusterArray[i] = new ClusterStringItem(strval);
        }
        else
            vClusterArray[i]->setString(strval);
 
        nGlobalType = ClusterItem::ITEMTYPE_INVALID;
    }
 
 
    std::vector<std::string> Cluster::getStringArray() const
    {
        std::vector<std::string> vArray;
 
        for (size_t i = 0; i < vClusterArray.size(); i++)
        {
            vArray.push_back(vClusterArray[i]->getParserString());
        }
 
        return vArray;
    }
 
 
    std::vector<std::string> Cluster::getInternalStringArray() const
    {
        std::vector<std::string> vArray;
 
        for (size_t i = 0; i < vClusterArray.size(); i++)
        {
            vArray.push_back(vClusterArray[i]->getInternalString());
        }
 
        return vArray;
    }
 
 
    void Cluster::setStringArray(const std::vector<std::string>& sVals)
    {
        // Create new cluster items, if needed
        while (vClusterArray.size() < sVals.size())
            push_back(new ClusterStringItem(""));
 
        for (size_t i = 0; i < sVals.size(); i++)
        {
            // Assign the value
            if (vClusterArray[i]->getType() != ClusterItem::ITEMTYPE_STRING)
            {
                // Re-create the current item as a string
                delete vClusterArray[i];
                vClusterArray[i] = new ClusterStringItem(sVals[i]);
            }
            else
                vClusterArray[i]->setString(sVals[i]);
        }
 
        reduceSize(sVals.size());
        nGlobalType = ClusterItem::ITEMTYPE_STRING;
    }
 
 
    std::vector<std::string> Cluster::to_string() const
    {
        std::vector<std::string> vString(vClusterArray.size());
 
        // Append the contained data depending on its type
        for (size_t i = 0; i < vClusterArray.size(); i++)
        {
            if (vClusterArray[i]->getType() == ClusterItem::ITEMTYPE_DOUBLE)
                vString[i] = toCmdString(vClusterArray[i]->getDouble());
            else
                vString[i] = vClusterArray[i]->getParserString();
        }
 
        return vString;
    }
 
 
    std::string Cluster::getVectorRepresentation() const
    {
        // Return nan, if no data is available
        if (!vClusterArray.size())
            return "nan";
 
        std::string sVector = "{";
 
        std::vector<std::string> vString = to_string();
 
        // Append the contained data depending on its type
        for (const auto& component : vString)
        {
            sVector += component + ",";
        }
 
        // Replace the last comma with a closing brace
        sVector.back() = '}';
 
        return sVector;
    }
 
 
    std::string Cluster::getShortVectorRepresentation(size_t maxStringLength) const
    {
        // Return an empty brace pair, if no data is
        // available
        if (!vClusterArray.size())
            return "{}";
 
        std::string sVector = "{";
 
        // Append the contained data depending on its type but
        // restrict the number to maximal five values (use the first
        // and the last ones) and insert an ellipsis in the middle
        for (size_t i = 0; i < vClusterArray.size(); i++)
        {
            if (vClusterArray[i]->getType() == ClusterItem::ITEMTYPE_DOUBLE)
                sVector += toString(vClusterArray[i]->getDouble(), 5) + ", ";
            else if (maxStringLength < std::string::npos)
                sVector += ellipsize(vClusterArray[i]->getString(), maxStringLength/4) + ", ";
            else
                sVector += vClusterArray[i]->getString() + ", ";
 
            // Insert the ellipsis in the middle
            if (i == 1 && vClusterArray.size() > 5)
            {
                sVector += "..., ";
                i = vClusterArray.size()-3;
            }
        }
 
        sVector.pop_back();
        sVector.back() = '}';
 
        return sVector;
    }
 
 
    std::vector<int> Cluster::sortElements(long long int i1, long long int i2, const std::string& sSortingExpression)
    {
        if (!vClusterArray.size())
            return std::vector<int>();
 
        bool bReturnIndex = false;
        bSortCaseInsensitive = false;
        int nSign = 1;
        std::vector<int> vIndex;
 
        // Look for command line parameters
        if (findParameter(sSortingExpression, "desc"))
            nSign = -1;
 
        if (findParameter(sSortingExpression, "ignorecase"))
            bSortCaseInsensitive = true;
 
        if (findParameter(sSortingExpression, "index"))
            bReturnIndex = true;
 
        // Prepare the indices
        if (i2 == -1)
            i2 = i1;
 
        // Create the sorting index
        for (int i = i1; i <= i2; i++)
            vIndex.push_back(i);
 
        // Sort everything
        if (!qSort(&vIndex[0], i2-i1+1, 0, 0, i2-i1, nSign))
        {
            throw SyntaxError(SyntaxError::CANNOT_SORT_DATA, "cluster{} " + sSortingExpression, SyntaxError::invalid_position);
        }
 
        // If the sorting index is requested,
        // then only sort the first column and return
        if (!bReturnIndex)
        {
            reorderElements(vIndex, i1, i2);
        }
        else
        {
            // If the index was requested, increment every index by one
            for (int i = 0; i <= i2-i1; i++)
                vIndex[i]++;
        }
 
        if (!bReturnIndex)
            return std::vector<int>();
 
        return vIndex;
    }
 
 
    void Cluster::deleteItems(long long int i1, long long int i2)
    {
        if (i2 >= vClusterArray.size())
            i2 = vClusterArray.size()-1;
 
        // If everything shall be erased, use the
        // "clear()" function
        if (!i1 && i2+1 == vClusterArray.size())
        {
            clear();
            return;
        }
 
        // Delete the cluster items first and
        // set the pointer to a nullpointer
        for (long long int i = i1; i < i2; i++)
        {
            delete vClusterArray[i];
            vClusterArray[i] = nullptr;
        }
 
        auto iter = vClusterArray.begin();
 
        // Remove all nullpointers from the array
        while (iter != vClusterArray.end())
        {
            if (!(*iter))
                iter = vClusterArray.erase(iter);
            else
                ++iter;
        }
 
        nGlobalType = ClusterItem::ITEMTYPE_INVALID;
    }
 
 
    void Cluster::deleteItems(const VectorIndex& vLines)
    {
        // Delete the cluster items first and
        // set the pointer to a nullpointer
        for (size_t i = 0; i < vLines.size(); i++)
        {
            if (vLines[i] < 0 || vLines[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[vLines[i]])
                delete vClusterArray[vLines[i]];
 
            vClusterArray[vLines[i]] = nullptr;
        }
 
        auto iter = vClusterArray.begin();
 
        // Remove all nullpointers from the array
        while (iter != vClusterArray.end())
        {
            if (!(*iter))
                iter = vClusterArray.erase(iter);
            else
                ++iter;
        }
 
        nGlobalType = ClusterItem::ITEMTYPE_INVALID;
    }
 
 
    //
    // Statistic functions section
    //
 
    mu::value_type Cluster::std(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return NAN;
 
        // Calculate the average of the referenced items
        mu::value_type dAvg = avg(_vLine);
        mu::value_type dStd = 0.0;
        unsigned int nInvalid = 0;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                nInvalid++;
            else if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(std::abs(vClusterArray[_vLine[i]]->getDouble())))
                nInvalid++;
            else
                dStd += (dAvg - vClusterArray[_vLine[i]]->getDouble()) * conj(dAvg - vClusterArray[_vLine[i]]->getDouble());
        }
 
        if (nInvalid >= _vLine.size() - 1)
            return NAN;
 
        return std::sqrt(dStd / ((_vLine.size()) - 1 - (double)nInvalid));
    }
 
 
    mu::value_type Cluster::avg(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return NAN;
 
        mu::value_type dAvg = 0.0;
        unsigned int nInvalid = 0;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                nInvalid++;
            else if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(std::abs(vClusterArray[_vLine[i]]->getDouble())))
                nInvalid++;
            else
                dAvg += vClusterArray[_vLine[i]]->getDouble();
        }
 
        if (nInvalid >= _vLine.size())
            return NAN;
 
        return dAvg / (_vLine.size() - (double)nInvalid);
    }
 
 
    mu::value_type Cluster::max(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size() || isString())
            return NAN;
 
        double dMax = NAN;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(vClusterArray[_vLine[i]]->getDouble().real()))
                continue;
 
            if (std::isnan(dMax))
                dMax = vClusterArray[_vLine[i]]->getDouble().real();
 
            if (dMax < vClusterArray[_vLine[i]]->getDouble().real())
                dMax = vClusterArray[_vLine[i]]->getDouble().real();
        }
 
        return dMax;
    }
 
 
    std::string Cluster::strmax(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size() || isDouble())
            return "";
 
        std::string sMax = "";
 
        // Apply the operation on all items and convert
        // their values on-the-fly
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (!sMax.length())
                sMax = vClusterArray[_vLine[i]]->getParserString();
 
            if (sMax < vClusterArray[_vLine[i]]->getParserString())
                sMax = vClusterArray[_vLine[i]]->getParserString();
        }
 
        return sMax;
    }
 
 
    mu::value_type Cluster::min(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size() || isString())
            return NAN;
 
        double dMin = NAN;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(vClusterArray[_vLine[i]]->getDouble().real()))
                continue;
 
            if (std::isnan(dMin))
                dMin = vClusterArray[_vLine[i]]->getDouble().real();
 
            if (dMin > vClusterArray[_vLine[i]]->getDouble().real())
                dMin = vClusterArray[_vLine[i]]->getDouble().real();
        }
 
        return dMin;
    }
 
 
    std::string Cluster::strmin(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size() || isDouble())
            return "";
 
        std::string sMin = "";
 
        // Apply the operation on all items and convert
        // their values on-the-fly
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (!sMin.length())
                sMin = vClusterArray[_vLine[i]]->getParserString();
 
            if (sMin > vClusterArray[_vLine[i]]->getParserString())
                sMin = vClusterArray[_vLine[i]]->getParserString();
        }
 
        return sMin;
    }
 
 
    mu::value_type Cluster::prd(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return NAN;
 
        mu::value_type dPrd = 1.0;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (std::isnan(std::abs(vClusterArray[_vLine[i]]->getDouble())))
                continue;
 
            dPrd *= vClusterArray[_vLine[i]]->getDouble();
        }
 
        return dPrd;
    }
 
 
    mu::value_type Cluster::sum(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size() && isString())
            return NAN;
 
        mu::value_type dSum = 0.0;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(std::abs(vClusterArray[_vLine[i]]->getDouble())))
                continue;
 
            dSum += vClusterArray[_vLine[i]]->getDouble();
        }
 
        return dSum;
    }
 
 
    std::string Cluster::strsum(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size() || isDouble())
            return "";
 
        std::string sSum = "";
 
        // Apply the operation on all items and convert
        // their values on-the-fly
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            sSum += vClusterArray[_vLine[i]]->getParserString();
        }
 
        return sSum;
    }
 
 
    mu::value_type Cluster::num(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return 0;
 
        int nInvalid = 0;
 
        // Apply the operation and ignore invalid values
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                nInvalid++;
            else if (vClusterArray[_vLine[i]]->getType() == ClusterItem::ITEMTYPE_DOUBLE && std::isnan(vClusterArray[_vLine[i]]->getDouble().real()))
                nInvalid++;
            else if (vClusterArray[_vLine[i]]->getType() == ClusterItem::ITEMTYPE_STRING && vClusterArray[_vLine[i]]->getParserString() == "\"\"")
                nInvalid++;
        }
 
        return _vLine.size() - (double)nInvalid;
    }
 
 
    mu::value_type Cluster::and_func(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return 0.0;
 
        double dRetVal = NAN;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (std::isnan(dRetVal))
                dRetVal = 1.0;
 
            if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(vClusterArray[_vLine[i]]->getDouble().real()) || vClusterArray[_vLine[i]]->getDouble() == 0.0)
                return 0.0;
        }
 
        if (std::isnan(dRetVal))
            return 0.0;
 
        return 1.0;
    }
 
 
    mu::value_type Cluster::or_func(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return 0.0;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[_vLine[i]]->getType() == ClusterItem::ITEMTYPE_DOUBLE
                && (std::isnan(vClusterArray[_vLine[i]]->getDouble().real()) || vClusterArray[_vLine[i]]->getDouble() != 0.0))
                return 1.0;
        }
 
        return 0.0;
    }
 
 
    mu::value_type Cluster::xor_func(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return 0.0;
 
        bool isTrue = false;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[_vLine[i]]->getType() == ClusterItem::ITEMTYPE_DOUBLE
                && (std::isnan(vClusterArray[_vLine[i]]->getDouble().real()) || vClusterArray[_vLine[i]]->getDouble() != 0.0))
            {
                if (!isTrue)
                    isTrue = true;
                else
                    return 0.0;
            }
        }
 
        if (isTrue)
            return 1.0;
 
        return 0.0;
    }
 
 
    mu::value_type Cluster::cnt(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return 0;
 
        int nInvalid = 0;
 
        // Apply the operation and ignore invalid locations
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                nInvalid++;
        }
        return _vLine.size() - (double)nInvalid;
    }
 
 
    mu::value_type Cluster::norm(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return NAN;
 
        mu::value_type dNorm = 0.0;
 
        // Apply the operation and ignore invalid or non-double items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(std::abs(vClusterArray[_vLine[i]]->getDouble())))
                continue;
 
            dNorm += vClusterArray[_vLine[i]]->getDouble() * conj(vClusterArray[_vLine[i]]->getDouble());
        }
 
        return std::sqrt(dNorm);
    }
 
 
    mu::value_type Cluster::cmp(const VectorIndex& _vLine, mu::value_type dRef, int _nType)
    {
        if (!vClusterArray.size())
            return NAN;
 
        enum
        {
            RETURN_VALUE = 1,
            RETURN_LE = 2,
            RETURN_GE = 4,
            RETURN_FIRST = 8
        };
 
        int nType = 0;
 
        mu::value_type dKeep = dRef;
        int nKeep = -1;
 
        if (_nType > 0)
            nType = RETURN_GE;
        else if (_nType < 0)
            nType = RETURN_LE;
 
        switch (intCast(fabs(_nType)))
        {
            case 2:
                nType |= RETURN_VALUE;
                break;
            case 3:
                nType |= RETURN_FIRST;
                break;
            case 4:
                nType |= RETURN_FIRST | RETURN_VALUE;
                break;
        }
 
        // Apply the operation and ignore invalid or non-double items
        for (long long int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                continue;
 
            if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(std::abs(vClusterArray[_vLine[i]]->getDouble())))
                continue;
 
            if (vClusterArray[_vLine[i]]->getDouble() == dRef)
            {
                if (nType & RETURN_VALUE)
                    return vClusterArray[_vLine[i]]->getDouble();
 
                return _vLine[i] + 1;
            }
            else if (nType & RETURN_GE && vClusterArray[_vLine[i]]->getDouble().real() > dRef.real())
            {
                if (nType & RETURN_FIRST)
                {
                    if (nType & RETURN_VALUE)
                        return vClusterArray[_vLine[i]]->getDouble().real();
 
                    return _vLine[i]+1;
                }
 
                if (nKeep == -1 || vClusterArray[_vLine[i]]->getDouble().real() < dKeep.real())
                {
                    dKeep = vClusterArray[_vLine[i]]->getDouble().real();
                    nKeep = _vLine[i];
                }
                else
                    continue;
            }
            else if (nType & RETURN_LE && vClusterArray[_vLine[i]]->getDouble().real() < dRef.real())
            {
                if (nType & RETURN_FIRST)
                {
                    if (nType & RETURN_VALUE)
                        return vClusterArray[_vLine[i]]->getDouble().real();
 
                    return _vLine[i]+1;
                }
 
                if (nKeep == -1 || vClusterArray[_vLine[i]]->getDouble().real() > dKeep.real())
                {
                    dKeep = vClusterArray[_vLine[i]]->getDouble().real();
                    nKeep = _vLine[i];
                }
                else
                    continue;
            }
        }
 
        if (nKeep == -1)
            return NAN;
        else if (nType & RETURN_VALUE)
            return dKeep;
 
        return nKeep+1;
    }
 
 
    mu::value_type Cluster::med(const VectorIndex& _vLine)
    {
        if (!vClusterArray.size())
            return NAN;
 
        double dMed = 0.0;
        unsigned int nInvalid = 0;
        unsigned int nCount = 0;
        double* dData = 0;
 
        // Calculate the number of valid items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                nInvalid++;
            else if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(vClusterArray[_vLine[i]]->getDouble().real()))
                nInvalid++;
        }
 
        if (nInvalid >= _vLine.size())
            return NAN;
 
        // Create a memory buffer of the corresponding size
        dData = new double[_vLine.size() - nInvalid];
 
        // copy the data to the buffer
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size() || vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(vClusterArray[_vLine[i]]->getDouble().real()))
                continue;
 
            dData[nCount] = vClusterArray[_vLine[i]]->getDouble().real();
            nCount++;
 
            if (nCount == _vLine.size() - nInvalid)
                break;
        }
 
        // Sort the data
        nCount = qSortDouble(dData, nCount);
 
        if (!nCount)
        {
            delete[] dData;
            return NAN;
        }
 
        // Calculate the median value
        dMed = gsl_stats_median_from_sorted_data(dData, 1, nCount);
 
        delete[] dData;
 
        return dMed;
    }
 
 
    mu::value_type Cluster::pct(const VectorIndex& _vLine, mu::value_type dPct)
    {
        if (!vClusterArray.size())
            return NAN;
 
        unsigned int nInvalid = 0;
        unsigned int nCount = 0;
        double* dData = 0;
 
        if (dPct.real() >= 1 || dPct.real() <= 0)
            return NAN;
 
        // Calculate the number of valid items
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size())
                nInvalid++;
            else if (vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(vClusterArray[_vLine[i]]->getDouble().real()))
                nInvalid++;
        }
 
        if (nInvalid >= _vLine.size())
            return NAN;
 
        // Create a memory buffer of the corresponding size
        dData = new double[_vLine.size() - nInvalid];
 
        // copy the data to the buffer
        for (unsigned int i = 0; i < _vLine.size(); i++)
        {
            if (_vLine[i] < 0 || _vLine[i] >= (int)vClusterArray.size() || vClusterArray[_vLine[i]]->getType() != ClusterItem::ITEMTYPE_DOUBLE || std::isnan(vClusterArray[_vLine[i]]->getDouble().real()))
                continue;
 
            dData[nCount] = vClusterArray[_vLine[i]]->getDouble().real();
            nCount++;
 
            if (nCount == _vLine.size() - nInvalid)
                break;
        }
 
        // Sort the data
        nCount = qSortDouble(dData, nCount);
 
        if (!nCount)
        {
            delete[] dData;
            return NAN;
        }
 
        // Calculate the p-th percentile
        dPct = gsl_stats_quantile_from_sorted_data(dData, 1, nCount, dPct.real());
 
        delete[] dData;
 
        return dPct;
    }
 
 
    //
    // class CLUSTERMANAGER
    //
    //
 
 
    std::string ClusterManager::validateClusterName(const std::string& sCluster)
    {
        std::string sClusterName = sCluster.substr(0, sCluster.find('{'));
        const static std::string sVALIDCHARACTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_~";
 
        if ((sClusterName[0] >= '0' && sClusterName[0] <= '9') || sClusterName[0] == '~' || sClusterName.find_first_not_of(sVALIDCHARACTERS) != std::string::npos)
            throw SyntaxError(SyntaxError::INVALID_CLUSTER_NAME, "", SyntaxError::invalid_position, sClusterName);
 
        return sClusterName;
    }
 
 
    std::map<std::string, Cluster>::const_iterator ClusterManager::mapStringViewFind(StringView view) const
    {
        for (auto iter = mClusterMap.begin(); iter != mClusterMap.end(); ++iter)
        {
            if (view == iter->first)
                return iter;
            else if (view < iter->first)
                return mClusterMap.end();
        }
 
        return mClusterMap.end();
    }
 
    std::map<std::string, Cluster>::iterator ClusterManager::mapStringViewFind(StringView view)
    {
        for (auto iter = mClusterMap.begin(); iter != mClusterMap.end(); ++iter)
        {
            if (view == iter->first)
                return iter;
            else if (view < iter->first)
                return mClusterMap.end();
        }
 
        return mClusterMap.end();
    }
 
 
    bool ClusterManager::containsClusters(const std::string& sCmdLine) const
    {
        size_t nQuotes = 0;
 
        if (sCmdLine.find('{') == std::string::npos)
            return false;
 
        // Search through the expression
        for (size_t i = 0; i < sCmdLine.length(); i++)
        {
            // Consider quotation marks
            if (sCmdLine[i] == '"' && (!i || sCmdLine[i-1] != '\\'))
                nQuotes++;
 
            if (!(nQuotes % 2))
            {
                // If the current character might probably be an
                // identifier for a table, search for the next
                // nonmatching character and try to find the obtained
                // string in the internal map
                if (isalpha(sCmdLine[i]) || sCmdLine[i] == '_' || sCmdLine[i] == '~')
                {
                    size_t nStartPos = i;
 
                    do
                    {
                        i++;
                    }
                    while (isalnum(sCmdLine[i]) || sCmdLine[i] == '_' || sCmdLine[i] == '~' || sCmdLine[i] == '[' || sCmdLine[i] == ']');
 
                    if (sCmdLine[i] == '{')
                    {
                        if (mClusterMap.find(sCmdLine.substr(nStartPos, i - nStartPos)) != mClusterMap.end())
                            return true;
                    }
                }
            }
        }
 
        return false;
    }
 
 
    bool ClusterManager::isCluster(StringView sCluster) const
    {
        if (mapStringViewFind(sCluster.subview(0, sCluster.find('{'))) != mClusterMap.end())
            return true;
 
        return false;
    }
 
 
    bool ClusterManager::isCluster(const std::string& sCluster) const
    {
        if (mClusterMap.find(sCluster.substr(0, sCluster.find('{'))) != mClusterMap.end())
            return true;
 
        return false;
    }
 
 
    Cluster& ClusterManager::getCluster(StringView sCluster)
    {
        auto iter = mapStringViewFind(sCluster.subview(0, sCluster.find('{')));
 
        if (iter == mClusterMap.end())
            throw SyntaxError(SyntaxError::CLUSTER_DOESNT_EXIST, sCluster.to_string(), sCluster.to_string());
 
        return iter->second;
    }
 
 
    Cluster& ClusterManager::getCluster(const std::string& sCluster)
    {
        auto iter = mClusterMap.find(sCluster.substr(0, sCluster.find('{')));
 
        if (iter == mClusterMap.end())
            throw SyntaxError(SyntaxError::CLUSTER_DOESNT_EXIST, sCluster, sCluster);
 
        return iter->second;
    }
 
 
    const Cluster& ClusterManager::getCluster(const std::string& sCluster) const
    {
        auto iter = mClusterMap.find(sCluster.substr(0, sCluster.find('{')));
 
        if (iter == mClusterMap.end())
            throw SyntaxError(SyntaxError::CLUSTER_DOESNT_EXIST, sCluster, sCluster);
 
        return iter->second;
    }
 
 
    Cluster& ClusterManager::newCluster(const std::string& sCluster)
    {
        std::string sValidName = validateClusterName(sCluster);
        mClusterMap[sValidName] = Cluster();
 
        return mClusterMap[sValidName];
    }
 
 
    void ClusterManager::appendCluster(const std::string& sCluster, const Cluster& cluster)
    {
        mClusterMap[validateClusterName(sCluster)] = cluster;
    }
 
 
    void ClusterManager::removeCluster(const std::string& sCluster)
    {
        auto iter = mClusterMap.find(sCluster);
 
        if (iter != mClusterMap.end())
            mClusterMap.erase(iter);
    }
 
 
    std::string ClusterManager::createTemporaryCluster(const std::string& suffix)
    {
        std::string sTemporaryClusterName = "_~~TC_" + toString(mClusterMap.size()) + "_" + suffix;
        mClusterMap[sTemporaryClusterName] = Cluster();
 
        return sTemporaryClusterName + "{}";
    }
 
 
    void ClusterManager::removeTemporaryClusters()
    {
        auto iter = mClusterMap.begin();
 
        while (iter != mClusterMap.end())
        {
            if (iter->first.substr(0, 6) == "_~~TC_")
                iter = mClusterMap.erase(iter);
            else
                ++iter;
        }
    }
 
 
    void ClusterManager::clearAllClusters()
    {
        mClusterMap.clear();
    }
 
 
    bool ClusterManager::updateClusterSizeVariables(StringView sCluster)
    {
        if (isCluster(sCluster))
            dClusterElementsCount = getCluster(sCluster.subview(0, sCluster.find('{'))).size();
        else
            dClusterElementsCount = 0.0;
 
        return true;
    }
}