nxssetreader.cpp

//  Copyright (C) 1999-2003 Paul O. Lewis
//
//  This file is part of NCL (Nexus Class Library) version 2.0.
//
//  NCL 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.
//
//  NCL 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 NCL; if not, write to the Free Software Foundation, Inc.,
//  59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
#include <climits>
#include "ncl/nxssetreader.h"
#include "ncl/nxstoken.h"
#include <algorithm>
using namespace std;

void NxsSetReader::AddRangeToSet(unsigned first, unsigned last, unsigned stride, NxsUnsignedSet * destination, const NxsUnsignedSet * taboo, NxsToken &token)
    {
    NCL_ASSERT (last >= first);
    NCL_ASSERT (last !=UINT_MAX);
    NCL_ASSERT (stride !=UINT_MAX);
    if (destination == NULL)
        return;
    NxsUnsignedSet::iterator dIt = destination->insert(first).first;
    for (unsigned curr = first + stride; curr <= last; curr += stride)
        {
        if (taboo != NULL && taboo->count(curr) > 0)
            {
            NxsString errormsg;
            errormsg << "Illegal repitition of an index (" << curr + 1 << ") in multiple subsets.";
            throw NxsException(errormsg, token);
            }
        dIt = destination->insert(dIt, curr);
        }
    }

unsigned NxsSetReader::InterpretTokenAsIndices(NxsToken &token,
  const NxsLabelToIndicesMapper & mapper,
  const char * setType,
  const char * cmdName,
  NxsUnsignedSet * destination)
    {
    try {
        const std::string t = token.GetToken();
        if (NxsString::case_insensitive_equals(t.c_str(), "ALL"))
            {
            unsigned m = mapper.GetMaxIndex();
            NxsUnsignedSet s;
            for (unsigned i = 0; i <= m; ++i)
                s.insert(i);
            destination->insert(s.begin(), s.end());
            return (unsigned)s.size();
            }
        return mapper.GetIndicesForLabel(t, destination);
        }
    catch (const NxsException & x)
        {
        NxsString errormsg = "Error in the ";
        errormsg << setType << " descriptor of a " << cmdName << " command.\n";
        errormsg += x.msg;
        throw NxsException(errormsg, token);
        }
    catch (...)
        {
        NxsString errormsg = "Expecting a ";
        errormsg << setType << " descriptor (number or label) in the " << cmdName << ".  Encountered ";
        errormsg <<  token.GetToken();
        throw NxsException(errormsg, token);
        }
    }

void NxsSetReader::ReadSetDefinition(
  NxsToken &token,
  const NxsLabelToIndicesMapper & mapper,
  const char * setType, /* "TAXON" or "CHARACTER" -- for error messages only */
  const char * cmdName, /* command name -- "TAXSET" or "EXSET"-- for error messages only */
  NxsUnsignedSet * destination, 
  const NxsUnsignedSet * taboo)
    {
    NxsString errormsg;
    NxsUnsignedSet tmpset;
    NxsUnsignedSet dummy;
    if (destination == NULL)
        destination = & dummy;
    unsigned previousInd = UINT_MAX;
    std::vector<unsigned> intersectVec;
    while (!token.Equals(";"))
        {
        if (taboo && token.Equals(","))
            return;
        if (token.Equals("-"))
            {
            if (previousInd == UINT_MAX)
                {
                errormsg = "The '-' must be preceded by number or a ";
                errormsg << setType << " label in the " << cmdName << " command.";
                throw NxsException(errormsg, token);
                }
            token.GetNextToken();
            if (token.Equals(";") || token.Equals("\\"))
                {
                errormsg = "Range in the ";
                errormsg << setType << " set definition in the " << cmdName << " command must be closed with a number or label.";
                throw NxsException(errormsg, token);
                }
            unsigned endpoint;
            if (token.Equals("."))
                endpoint = mapper.GetMaxIndex();
            else
                {
                tmpset.clear();
                unsigned nAdded = NxsSetReader::InterpretTokenAsIndices(token, mapper, setType, cmdName, &tmpset);
                if (nAdded != 1)
                    {
                    errormsg = "End of a range in a ";
                    errormsg << setType << " set definition in the " << cmdName << " command must be closed with a single number or label (not a set).";
                    throw NxsException(errormsg, token);
                    }
                endpoint = *(tmpset.begin());
                if (endpoint < previousInd)
                    {
                    errormsg = "End of a range in a ";
                    errormsg << setType << " set definition in the " << cmdName << " command must be a larger index than the start of the range (found ";
                    errormsg << previousInd + 1 << " - " << token.GetToken();
                    throw NxsException(errormsg, token);
                    }
                }
            token.GetNextToken();
            if (token.Equals("\\"))
                {
                token.GetNextToken();
                NxsString t = token.GetToken();
                unsigned stride = 0;
                try
                    {
                    stride = t.ConvertToUnsigned();
                    }
                catch (const NxsString::NxsX_NotANumber &)
                    {}
                if (stride == 0)
                    {
                    errormsg = "Expecting a positive number indicating the 'stride' after the \\ in the ";
                    errormsg << setType << " set definition in the " << cmdName << " command. Encountered ";
                    errormsg << t;
                    throw NxsException(errormsg, token);
                    }
                AddRangeToSet(previousInd, endpoint, stride, destination, taboo, token);
                token.GetNextToken();
                }
            else
                AddRangeToSet(previousInd, endpoint, 1, destination, taboo, token);
            previousInd = UINT_MAX;
            }
        else
            {
            tmpset.clear();
            const unsigned nAdded = NxsSetReader::InterpretTokenAsIndices(token, mapper, setType, cmdName, &tmpset);
            if (taboo != NULL)
                {
                set_intersection(taboo->begin(), taboo->end(), tmpset.begin(), tmpset.end(), back_inserter(intersectVec));
                if (!intersectVec.empty())
                    {
                    errormsg << "Illegal repitition of an index (" << 1 + *(intersectVec.begin()) << ") in multiple subsets.";
                    throw NxsException(errormsg, token);
                    }
                }
            if (nAdded == 1 )
                {
                previousInd = *(tmpset.begin());
                destination->insert(previousInd);
                }
            else
                {
                previousInd = UINT_MAX;
                destination->insert(tmpset.begin(), tmpset.end());
                }
            token.GetNextToken();
            }
        }
    }

NxsSetReader::NxsSetReader(
  NxsToken          &t,         /* reference to the NxsToken being used to read in the NEXUS data file */
  unsigned          maxValue,   /* maximum possible value allowed in this set (e.g. nchar or ntax) */
  NxsUnsignedSet    &iset,      /* reference to the set object to store the set defined in the NEXUS data file */
  NxsBlock          &nxsblk,    /* reference to the NxsBlock object (used for looking up taxon or character labels when encountered in the set definition) */
  unsigned          type)       /* one of the elements in the NxsSetReaderEnum enumeration */
  : block(nxsblk), token(t), nxsset(iset)
    {
    max     = maxValue;
    settype = type;
    nxsset.clear();
    }

bool NxsSetReader::AddRange(
  unsigned first,       /* the first member of the range (inclusive, offset 1) */
  unsigned last,        /* the last member of the range (inclusive, offset 1) */
  unsigned modulus)     /* the modulus to use (if non-zero) */
    {
    if (last > max || first < 1 || first > last)
        return false;

    for (unsigned i = first - 1; i < last; i++)
        {
        unsigned diff = i - first + 1;
        if (modulus > 0 && diff % modulus != 0)
            continue;
        nxsset.insert(i);
        }

    return true;
    }

unsigned NxsSetReader::GetTokenValue()
    {
    unsigned v = atoi(token.GetToken().c_str());

    if (v == 0 && settype != NxsSetReader::generic)
        {
        if (settype == NxsSetReader::charset)
            v = block.CharLabelToNumber(token.GetToken());
        else if (settype == NxsSetReader::taxset)
            v = block.TaxonLabelToNumber(token.GetToken());
        }

    if (v == 0)
        {
        block.errormsg = "Set element (";
        block.errormsg += token.GetToken();
        block.errormsg += ") not a number ";
        if (settype == NxsSetReader::charset)
            block.errormsg += "and not a valid character label";
        else if (settype == NxsSetReader::taxset)
            block.errormsg += "and not a valid taxon label";

        throw NxsException(block.errormsg, token.GetFilePosition(), token.GetFileLine(), token.GetFileColumn());
        }

    return v;
    }

std::vector<unsigned> NxsSetReader::GetSetAsVector(const NxsUnsignedSet &s)
    {
    std::vector<unsigned> u;
    u.reserve(s.size());
    for (NxsUnsignedSet::const_iterator sIt = s.begin(); sIt != s.end(); ++sIt)
        u.push_back(*sIt);
    return u;
    }

void NxsSetReader::WriteSetAsNexusValue(const NxsUnsignedSet & nxsset, std::ostream & out)
    {
    NxsUnsignedSet::const_iterator currIt = nxsset.begin();
    const NxsUnsignedSet::const_iterator endIt = nxsset.end();
    if (currIt == endIt)
        return;
    unsigned rangeBegin = 1 + *currIt++;
    if (currIt == endIt)
        {
        out << ' ' << rangeBegin;
        return;
        }
    unsigned prev = 1 + *currIt++;
    if (currIt == endIt)
        {
        out << ' ' << rangeBegin << ' ' << prev;
        return;
        }
    unsigned stride = prev - rangeBegin;
    unsigned curr = 1 + *currIt++;
    bool inRange = true;
    while (currIt != endIt)
        {
        if (inRange)
            {
            if (curr - prev != stride)
                {
                if (prev - rangeBegin == stride)
                    {
                    out << ' ' << rangeBegin;
                    rangeBegin = prev;
                    stride = curr - prev;
                    }
                else
                    {
                    if (stride > 1)
                        out << ' ' << rangeBegin << '-' << prev << " \\ " << stride;
                    else
                        out << ' ' << rangeBegin << '-' << prev ;
                    inRange = false;
                    }
                }
            }
        else
            {
            inRange = true;
            rangeBegin = prev;
            stride = curr - prev;
            }
        prev = curr;
        curr = 1 + *currIt;
        currIt++;
        }
    if (inRange)
        {
        if (curr - prev != stride)
            {
            if (prev - rangeBegin == stride)
                out << ' ' << rangeBegin << ' ' << prev;
            else
                {
                if (stride > 1)
                    out << ' ' << rangeBegin << '-' << prev << " \\ " << stride;
                else
                    out << ' ' << rangeBegin << '-' << prev ;
                }
            out << ' ' << curr;
            }
        else
            {
            if (stride > 1)
                out << ' ' << rangeBegin << '-' << curr << " \\ " << stride;
            else
                out << ' ' << rangeBegin << '-' << curr ;
            }
        }
    else
        out << ' ' << prev << ' ' << curr;
    }
bool NxsSetReader::Run()
    {
    bool ok;
    bool retval = false;

    unsigned rangeBegin = UINT_MAX;
    unsigned rangeEnd = rangeBegin;
    bool insideRange = false;
    unsigned modValue = 1;

    for (;;)
        {
        // Next token should be one of the following:
        //   ';'        --> set definition finished
        //   '-'        --> range being defined
        //   <integer>  --> member of set (or beginning or end of a range)
        //   '.'        --> signifies the number max
        //   '\'        --> signifies modulus value coming next
        //
        token.GetNextToken();

        if (token.Equals("-"))
            {
            // We should not be inside a range when we encounter a hyphenation symbol.
            // The hyphen is what _puts_ us inside a range!
            //
            if (insideRange)
                {
                block.errormsg = "The symbol '-' is out of place here";
                throw NxsException(block.errormsg, token.GetFilePosition(), token.GetFileLine(), token.GetFileColumn());
                }
            insideRange = true;
            }

        else if (token.Equals("."))
            {
            // We _should_ be inside a range if we encounter a period, as this
            // is a range termination character
            //
            if (!insideRange)
                {
                block.errormsg = "The symbol '.' can only be used to specify the end of a range";
                throw NxsException(block.errormsg, token.GetFilePosition(), token.GetFileLine(), token.GetFileColumn());
                }
            rangeEnd = max;
            }

        else if (token.Equals("\\"))
            {
            // The backslash character is used to specify a modulus to a range, and
            // thus should only be encountered if currently inside a range
            //
            if (!insideRange)
                {
                block.errormsg = "The symbol '\\' can only be used after the end of a range has been specified";
                throw NxsException(block.errormsg, token.GetFilePosition(), token.GetFileLine(), token.GetFileColumn());
                }

            // This should be the modulus value
            //
            modValue = NxsToken::DemandPositiveInt(token, block.errormsg, "The modulus value");
            }

        else if (insideRange && rangeEnd == UINT_MAX)
            {
            // The beginning of the range and the hyphen symbol have been read
            // already, just need to store the end of the range at this point
            //
            rangeEnd = GetTokenValue();
            }

        else if (insideRange)
            {
            // If insideRange is true, we must have already stored the beginning
            // of the range and read in the hyphen character. We would not have
            // made it this far if we had also not already stored the range end.
            // Thus, we can go ahead and add the range.
            //
            ok = AddRange(rangeBegin, rangeEnd, modValue);
            modValue = 1;

            if (!ok)
                {
                block.errormsg = "Character number out of range (or range incorrectly specified) in set specification";
                throw NxsException(block.errormsg, token.GetFilePosition(), token.GetFileLine(), token.GetFileColumn());
                }

            // We have actually already read in the next token, so deal with it
            // now so that we don't end up skipping a token
            //
            if (token.Equals(";"))
                {
                retval = true;
                break;
                }
            else if (token.Equals(","))
                {
                break;
                }

            rangeBegin = GetTokenValue();
            rangeEnd = UINT_MAX;
            insideRange = false;
            }

        else if (rangeBegin != UINT_MAX)
            {
            // If we were inside a range, we would have not gotten this far.
            // If not in a range, we are either getting ready to begin a new
            // range or have previously read in a single value. Handle the
            // latter possibility here.
            //
            ok = AddRange(rangeBegin, rangeBegin, modValue);
            modValue = 1;

            if (!ok)
                {
                block.errormsg = "Number out of range (or range incorrectly specified) in set specification";
                throw NxsException(block.errormsg, token.GetFilePosition(), token.GetFileLine(), token.GetFileColumn());
                }

            if (token.Equals(";"))
                {
                retval = true;
                break;
                }
            else if (token.Equals(","))
                {
                break;
                }

            rangeBegin = GetTokenValue();
            rangeEnd = UINT_MAX;
            }

        else if (token.Equals(";"))
            {
            retval = true;
            break;
            }

        else if (token.Equals(","))
            {
            break;
            }

        else if (token.Equals("ALL"))
            {
            rangeBegin = 1;
            rangeEnd = max;
            ok = AddRange(rangeBegin, rangeEnd);
            }

        else
            {
            // Can only get here if rangeBegin still equals UINT_MAX and thus we
            // are reading in the very first token and that token is neither
            // the word "all" nor is it a semicolon
            //
            rangeBegin = GetTokenValue();
            rangeEnd = UINT_MAX;
            }
        }

    return retval;
    }

---