/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

/*

 * This file is part of the LibreOffice project.

 *

 * This Source Code Form is subject to the terms of the Mozilla Public

 * License, v. 2.0. If a copy of the MPL was not distributed with this

 * file, You can obtain one at http://mozilla.org/MPL/2.0/.

 *

 * This file incorporates work covered by the following license notice:

 *

 *   Licensed to the Apache Software Foundation (ASF) under one or more

 *   contributor license agreements. See the NOTICE file distributed

 *   with this work for additional information regarding copyright

 *   ownership. The ASF licenses this file to you under the Apache

 *   License, Version 2.0 (the "License"); you may not use this file

 *   except in compliance with the License. You may obtain a copy of

 *   the License at http://www.apache.org/licenses/LICENSE-2.0 .

 */

#include <sal/config.h>

#include <cstddef>

#include <o3tl/string_view.hxx>

#include <tools/debug.hxx>

#include <tools/multisel.hxx>

#include <rtl/ustrbuf.hxx>

void MultiSelection::ImplClear()

{

    // no selected indexes

    nSelCount = 0;

    aSels.clear();

}

std::size_t MultiSelection::ImplFindSubSelection( sal_Int32 nIndex ) const

{

    // iterate through the sub selections

    std::size_t n = 0;

    for ( ;

          n < aSels.size() && nIndex > aSels[ n ].Max();

          ++n ) {} /* empty loop */

    return n;

}

void MultiSelection::ImplMergeSubSelections( sal_Int32 nPos1, std::size_t nPos2 )

{

    // didn't a sub selection at nPos2 exist?

    if ( nPos2 >= aSels.size() )

        return;

    // did the sub selections touch each other?

    if ( (aSels[ nPos1 ].Max() + 1) == aSels[ nPos2 ].Min() )

    {

        // merge them

        aSels[ nPos1 ].Max() = aSels[ nPos2 ].Max();

        aSels.erase( aSels.begin() + nPos2 );

    }

}

MultiSelection::MultiSelection():

    aTotRange( 0, -1 ),

    nCurSubSel(0),

    nCurIndex(0),

    nSelCount(0),

    bCurValid(false)

{

}

void MultiSelection::Reset()

{

    aTotRange = Range(0, -1);

    bCurValid = false;

    // clear the old sub selections

    ImplClear();

}

MultiSelection::MultiSelection( const MultiSelection& rOrig ) :

    aTotRange(rOrig.aTotRange),

    nSelCount(rOrig.nSelCount),

    bCurValid(rOrig.bCurValid)

{

    if ( bCurValid )

    {

        nCurSubSel = rOrig.nCurSubSel;

        nCurIndex = rOrig.nCurIndex;

    }

    else

    {

        nCurSubSel = 0;

        nCurIndex = 0;

    }

    // copy the sub selections

    aSels.insert( aSels.end(), rOrig.aSels.begin(), rOrig.aSels.end() );

}

MultiSelection::MultiSelection( const Range& rRange ):

    aTotRange(rRange),

    nCurSubSel(0),

    nCurIndex(0),

    nSelCount(0),

    bCurValid(false)

{

}

MultiSelection::~MultiSelection()

{

}

MultiSelection& MultiSelection::operator= ( const MultiSelection& rOrig )

{

    aTotRange = rOrig.aTotRange;

    bCurValid = rOrig.bCurValid;

    if ( bCurValid )

    {

        nCurSubSel = rOrig.nCurSubSel;

        nCurIndex = rOrig.nCurIndex;

    }

    // clear the old and copy the sub selections

    ImplClear();

    aSels.insert( aSels.end(), rOrig.aSels.begin(), rOrig.aSels.end() );

    nSelCount = rOrig.nSelCount;

    return *this;

}

void MultiSelection::SelectAll( bool bSelect )

{

    ImplClear();

    if ( bSelect )

    {

        aSels.push_back( aTotRange );

        nSelCount = aTotRange.Len();

    }

}

bool MultiSelection::Select( sal_Int32 nIndex, bool bSelect )

{

    DBG_ASSERT( aTotRange.Contains(nIndex), "selected index out of range" );

    // out of range?

    if ( !aTotRange.Contains(nIndex) )

        return false;

    // find the virtual target position

    std::size_t nSubSelPos = ImplFindSubSelection( nIndex );

    if ( bSelect )

    {

        // is it included in the found sub selection?

        if ( nSubSelPos < aSels.size() && aSels[ nSubSelPos ].Contains( nIndex ) )

            // already selected, nothing to do

            return false;

        // it will become selected

        ++nSelCount;

        // is it at the end of the previous sub selection

        if ( nSubSelPos > 0 &&

             aSels[ nSubSelPos-1 ].Max() == (nIndex-1) )

        {

            // expand the previous sub selection

            aSels[ nSubSelPos-1 ].Max() = nIndex;

            // try to merge the previous sub selection

            ImplMergeSubSelections( nSubSelPos-1, nSubSelPos );

        }

        // is it at the beginning of the found sub selection

        else if (  nSubSelPos < aSels.size()

                && aSels[ nSubSelPos ].Min() == (nIndex+1)

        )

            // expand the found sub selection

            aSels[ nSubSelPos ].Min() = nIndex;

        else

        {

            // create a new sub selection

            if ( nSubSelPos < aSels.size() ) {

                aSels.insert( aSels.begin() + nSubSelPos, Range( nIndex, nIndex ) );

            } else {

                aSels.push_back( Range( nIndex, nIndex ) );

            }

            if ( bCurValid && nCurSubSel >= nSubSelPos )

                ++nCurSubSel;

        }

    }

    else

    {

        // is it excluded from the found sub selection?

        if (  nSubSelPos >= aSels.size()

           || !aSels[ nSubSelPos ].Contains( nIndex )

        ) {

            // not selected, nothing to do

            return false;

        }

        // it will become deselected

        --nSelCount;

        // is it the only index in the found sub selection?

        if ( aSels[ nSubSelPos ].Len() == 1 )

        {

            // remove the complete sub selection

            aSels.erase( aSels.begin() + nSubSelPos );

            return true;

        }

        // is it at the beginning of the found sub selection?

        if ( aSels[ nSubSelPos ].Min() == nIndex )

            ++aSels[ nSubSelPos ].Min();

        // is it at the end of the found sub selection?

        else if ( aSels[ nSubSelPos ].Max() == nIndex )

            --aSels[ nSubSelPos ].Max();

        // it is in the middle of the found sub selection?

        else

        {

            // split the sub selection

            // we know nSubSelPos < aSels.size() since it's been tested some lines before

            aSels.insert( aSels.begin() + nSubSelPos, Range( aSels[ nSubSelPos ].Min(), nIndex-1 ) );

            aSels[ nSubSelPos+1 ].Min() = nIndex + 1;

        }

    }

    return true;

}

void MultiSelection::Select( const Range& rIndexRange, bool bSelect )

{

    sal_Int32 nOld;

    sal_Int32 nTmpMin = rIndexRange.Min();

    sal_Int32 nTmpMax = rIndexRange.Max();

    sal_Int32 nCurMin = FirstSelected();

    sal_Int32 nCurMax = LastSelected();

    DBG_ASSERT(aTotRange.Contains(nTmpMax), "selected index out of range" );

    DBG_ASSERT(aTotRange.Contains(nTmpMin), "selected index out of range" );

    // replace whole selection?

    if( aSels.empty() || (nTmpMin <= nCurMin && nTmpMax >= nCurMax ) )

    {

        ImplClear();

        if ( bSelect )

        {

            aSels.push_back( rIndexRange );

            nSelCount = rIndexRange.Len();

        }

        return;

    }

    // expand on left side?

    if( nTmpMax < nCurMin )

    {

        if( bSelect )

        {

            // extend first range?

            if( nCurMin > (nTmpMax+1)  )

            {

                aSels.insert( aSels.begin(), rIndexRange );

                nSelCount += rIndexRange.Len();

            }

            else

            {

                auto & rRange = aSels.front();

                nOld = rRange.Min();

                rRange.Min() = nTmpMin;

                nSelCount += ( nOld - nTmpMin );

            }

            bCurValid = false;

        }

        return;

    }

    // expand on right side?

    else if( nTmpMin > nCurMax )

    {

        if( bSelect )

        {

            // extend last range?

            if( nTmpMin > (nCurMax+1) )

            {

                aSels.push_back( rIndexRange );

                nSelCount += rIndexRange.Len();

            }

            else

            {

                auto & rRange = aSels.back();

                nOld = rRange.Max();

                rRange.Max() = nTmpMax;

                nSelCount += ( nTmpMax - nOld );

            }

            bCurValid = false;

        }

        return;

    }

    // TODO here is potential for optimization

    while( nTmpMin <= nTmpMax )

    {

        Select( nTmpMin, bSelect );

        nTmpMin++;

    }

}

bool MultiSelection::IsSelected( sal_Int32 nIndex ) const

{

    // find the virtual target position

    std::size_t nSubSelPos = ImplFindSubSelection( nIndex );

    return nSubSelPos < aSels.size() && aSels[ nSubSelPos ].Contains(nIndex);

}

void MultiSelection::Insert( sal_Int32 nIndex, sal_Int32 nCount )

{

    // find the virtual target position

    std::size_t nSubSelPos = ImplFindSubSelection( nIndex );

    // did we need to shift the sub selections?

    if ( nSubSelPos < aSels.size() )

    {   // did we insert an unselected into an existing sub selection?

        if (  aSels[ nSubSelPos ].Min() != nIndex

           && aSels[ nSubSelPos ].Contains(nIndex)

        ) { // split the sub selection

            aSels.insert( aSels.begin() + nSubSelPos, Range( aSels[ nSubSelPos ].Min(), nIndex-1 ) );

            ++nSubSelPos;

            aSels[ nSubSelPos ].Min() = nIndex;

        }

        // shift the sub selections behind the inserting position

        for ( std::size_t nPos = nSubSelPos; nPos < aSels.size(); ++nPos )

        {

            aSels[ nPos ].Min() += nCount;

            aSels[ nPos ].Max() += nCount;

        }

    }

    bCurValid = false;

    aTotRange.Max() += nCount;

}

void MultiSelection::Remove( sal_Int32 nIndex )

{

    // find the virtual target position

    std::size_t nSubSelPos = ImplFindSubSelection( nIndex );

    // did we remove from an existing sub selection?

    if (  nSubSelPos < aSels.size()

       && aSels[ nSubSelPos ].Contains(nIndex)

    ) {

        // does this sub selection only contain the index to be deleted

        if ( aSels[ nSubSelPos ].Len() == 1 ) {

            // completely remove the sub selection

            aSels.erase( aSels.begin() + nSubSelPos );

        } else {

            // shorten this sub selection

            --( aSels[ nSubSelPos++ ].Max() );

        }

        // adjust the selected counter

        --nSelCount;

    }

    // shift the sub selections behind the removed index

    for ( std::size_t nPos = nSubSelPos; nPos < aSels.size(); ++nPos )

    {

        --( aSels[ nPos ].Min() );

        --( aSels[ nPos ].Max() );

    }

    bCurValid = false;

    aTotRange.Max() -= 1;

}

sal_Int32 MultiSelection::FirstSelected()

{

    nCurSubSel = 0;

    bCurValid = !aSels.empty();

    if ( !bCurValid )

        return SFX_ENDOFSELECTION;

    nCurIndex = aSels[ 0 ].Min();

    return nCurIndex;

}

sal_Int32 MultiSelection::LastSelected()

{

    bCurValid = !aSels.empty();

    if ( !bCurValid )

        return SFX_ENDOFSELECTION;

    nCurSubSel = aSels.size() - 1;

    nCurIndex = aSels[ nCurSubSel ].Max();

    return nCurIndex;

}

sal_Int32 MultiSelection::NextSelected()

{

    if ( !bCurValid )

        return SFX_ENDOFSELECTION;

    // is the next index in the current sub selection too?

    if ( nCurIndex < aSels[ nCurSubSel ].Max() )

        return ++nCurIndex;

    // are there further sub selections?

    if ( ++nCurSubSel >= aSels.size() )

        // we are at the end!

        return SFX_ENDOFSELECTION;

    nCurIndex = aSels[ nCurSubSel ].Min();

    return nCurIndex;

}

void MultiSelection::SetTotalRange( const Range& rTotRange )

{

    aTotRange = rTotRange;

    // adjust lower boundary

    Range* pRange = aSels.empty() ? nullptr : &aSels.front();

    while( pRange )

    {

        if( pRange->Max() < aTotRange.Min() )

        {

            aSels.erase( aSels.begin() );

        }

        else if( pRange->Min() < aTotRange.Min() )

        {

            pRange->Min() = aTotRange.Min();

            break;

        }

        else

            break;

        pRange = aSels.empty() ? nullptr : &aSels.front();

    }

    // adjust upper boundary

    sal_Int32 nCount = aSels.size();

    while( nCount )

    {

        pRange = &aSels[ nCount - 1 ];

        if( pRange->Min() > aTotRange.Max() )

        {

            aSels.pop_back();

        }

        else if( pRange->Max() > aTotRange.Max() )

        {

            pRange->Max() = aTotRange.Max();

            break;

        }

        else

            break;

        nCount = aSels.size();

    }

    // re-calculate selection count

    nSelCount = 0;

    for (Range const & rSel : aSels)

        nSelCount += rSel.Len();

    bCurValid = false;

    nCurIndex = 0;

}

// StringRangeEnumerator

StringRangeEnumerator::StringRangeEnumerator( std::u16string_view i_rInput,

                                              sal_Int32 i_nMinNumber,

                                              sal_Int32 i_nMaxNumber,

                                              sal_Int32 i_nLogicalOffset

                                              )

    : mnCount( 0 )

    , mnMin( i_nMinNumber )

    , mnMax( i_nMaxNumber )

    , mnOffset( i_nLogicalOffset )

    , mbValidInput( false )

{

    // Parse string only if boundaries are valid.

    if( mnMin >= 0 && mnMax >= 0 && mnMin <= mnMax )

        mbValidInput = setRange( i_rInput );

}

bool StringRangeEnumerator::checkValue( sal_Int32 i_nValue, const o3tl::sorted_vector< sal_Int32 >* i_pPossibleValues ) const

{

    if( i_nValue < 0 || i_nValue < mnMin || i_nValue > mnMax )

        return false;

    if( i_pPossibleValues && i_pPossibleValues->find( i_nValue ) == i_pPossibleValues->end() )

        return false;

    return true;

}

bool StringRangeEnumerator::insertRange( sal_Int32 i_nFirst, sal_Int32 i_nLast, bool bSequence )

{

    bool bSuccess = true;

    if( bSequence )

    {

        // Check if the range is completely outside of possible pages range

        if ((i_nFirst < mnMin && i_nLast < mnMin) ||

            (i_nFirst > mnMax && i_nLast > mnMax))

            return false;

        if( i_nFirst < mnMin )

            i_nFirst = mnMin;

        if( i_nFirst > mnMax )

            i_nFirst = mnMax;

        if( i_nLast < mnMin )

            i_nLast = mnMin;

        if( i_nLast > mnMax )

            i_nLast = mnMax;

        if( checkValue( i_nFirst ) && checkValue( i_nLast ) )

        {

            maSequence.push_back( Range( i_nFirst, i_nLast ) );

            sal_Int32 nNumber = i_nLast - i_nFirst;

            nNumber = nNumber < 0 ? -nNumber : nNumber;

            mnCount += nNumber + 1;

        }

        else

            bSuccess = false;

    }

    else

    {

        if( checkValue( i_nFirst ) )

        {

            maSequence.push_back( Range( i_nFirst, i_nFirst ) );

            mnCount++;

        }

        else if( checkValue( i_nLast ) )

        {

            maSequence.push_back( Range( i_nLast, i_nLast ) );

            mnCount++;

        }

        else

            bSuccess = false;

    }

    return bSuccess;

}

void StringRangeEnumerator::insertJoinedRanges(

    const std::vector< sal_Int32 >& rNumbers )

{

    size_t nCount = rNumbers.size();

    if( nCount == 0 )

        return;

    if( nCount == 1 )

    {

        insertRange( rNumbers[0], -1, false );

        return;

    }

    for( size_t i = 0; i < nCount - 1; i++ )

    {

        sal_Int32 nFirst = rNumbers[i];

        sal_Int32 nLast  = rNumbers[i + 1];

        if( i > 0 )

        {

            if     ( nFirst > nLast ) nFirst--;

            else if( nFirst < nLast ) nFirst++;

        }

        insertRange( nFirst, nLast, nFirst != nLast );

    }

}

bool StringRangeEnumerator::setRange( std::u16string_view aNewRange )

{

    mnCount = 0;

    maSequence.clear();

    auto pInput = aNewRange.begin();

    auto pInputEnd = aNewRange.end();

    OUStringBuffer aNumberBuf( 16 );

    std::vector< sal_Int32 > aNumbers;

    bool bSequence = false;

    while( pInput != pInputEnd )

    {

        while( pInput != pInputEnd && *pInput >= '0' && *pInput <= '9' )

            aNumberBuf.append( *pInput++ );

        if( !aNumberBuf.isEmpty() )

        {

            sal_Int32 nNumber = o3tl::toInt32(aNumberBuf) + mnOffset;

            aNumberBuf.setLength(0);

            aNumbers.push_back( nNumber );

            bSequence = false;

        }

        if (pInput == pInputEnd)

            break;

        if( *pInput == '-' )

        {

            bSequence = true;

            if( aNumbers.empty() )

            {

                // push out-of-range small value, to exclude ranges totally outside of possible range

                aNumbers.push_back( mnMin-1 );

            }

        }

        else if( *pInput == ',' || *pInput == ';' )

        {

            if( bSequence && !aNumbers.empty() )

            {

                // push out-of-range large value, to exclude ranges totally outside of possible range

                aNumbers.push_back( mnMax+1 );

            }

            insertJoinedRanges( aNumbers );

            aNumbers.clear();

            bSequence = false;

        }

        else if( *pInput != ' ' )

            return false; // parse error

        pInput++;

    }

    // insert last entries

    if( bSequence && !aNumbers.empty() )

    {

        // push out-of-range large value, to exclude ranges totally outside of possible range

        aNumbers.push_back( mnMax+1 );

    }

    insertJoinedRanges( aNumbers );

    return true;

}

bool StringRangeEnumerator::hasValue( sal_Int32 i_nValue, const o3tl::sorted_vector< sal_Int32 >* i_pPossibleValues ) const

{

    if( i_pPossibleValues && i_pPossibleValues->find( i_nValue ) == i_pPossibleValues->end() )

        return false;

    size_t n = maSequence.size();

    for( size_t i= 0; i < n; ++i )

    {

        const StringRangeEnumerator::Range rRange( maSequence[i] );

        if( rRange.nFirst < rRange.nLast )

        {

            if( i_nValue >= rRange.nFirst && i_nValue <= rRange.nLast )

                return true;

        }

        else

        {

            if( i_nValue >= rRange.nLast && i_nValue <= rRange.nFirst )

                return true;

        }

    }

    return false;

}

StringRangeEnumerator::Iterator& StringRangeEnumerator::Iterator::operator++()

{

    if( nRangeIndex >= 0 && nCurrent >= 0 && pEnumerator )

    {

        const StringRangeEnumerator::Range& rRange( pEnumerator->maSequence[nRangeIndex] );

        bool bRangeChange = false;

        if( rRange.nLast < rRange.nFirst )

        {

            // backward range

            if( nCurrent > rRange.nLast )

                nCurrent--;

            else

                bRangeChange = true;

        }

        else

        {

            // forward range

            if( nCurrent < rRange.nLast )

                nCurrent++;

            else

                bRangeChange = true;

        }

        if( bRangeChange )

        {

            nRangeIndex++;

            if( size_t(nRangeIndex) == pEnumerator->maSequence.size() )

            {

                // reached the end

                nRangeIndex = nCurrent = -1;

            }

            else

                nCurrent = pEnumerator->maSequence[nRangeIndex].nFirst;

        }

        if( nRangeIndex != -1 && nCurrent != -1 )

        {

            if( ! pEnumerator->checkValue( nCurrent, pPossibleValues ) )

                return ++(*this);

        }

    }

    return *this;

}

bool StringRangeEnumerator::Iterator::operator==( const Iterator& i_rCompare ) const

{

    return i_rCompare.pEnumerator == pEnumerator && i_rCompare.nRangeIndex == nRangeIndex && i_rCompare.nCurrent == nCurrent;

}

StringRangeEnumerator::Iterator StringRangeEnumerator::begin( const o3tl::sorted_vector< sal_Int32 >* i_pPossibleValues ) const

{

    StringRangeEnumerator::Iterator it( this,

                                        i_pPossibleValues,

                                        maSequence.empty() ? -1 : 0,

                                        maSequence.empty() ? -1 : maSequence[0].nFirst );

    if( ! checkValue(*it, i_pPossibleValues ) )

        ++it;

    return it;

}

StringRangeEnumerator::Iterator StringRangeEnumerator::end( const o3tl::sorted_vector< sal_Int32 >* i_pPossibleValues ) const

{

    return StringRangeEnumerator::Iterator( this, i_pPossibleValues, -1, -1 );

}

bool StringRangeEnumerator::getRangesFromString( std::u16string_view i_rPageRange,

                                                 std::vector< sal_Int32 >& o_rPageVector,

                                                 sal_Int32 i_nMinNumber,

                                                 sal_Int32 i_nMaxNumber,

                                                 sal_Int32 i_nLogicalOffset,

                                                 o3tl::sorted_vector< sal_Int32 > const * i_pPossibleValues

                                               )

{

    o_rPageVector.clear();

    StringRangeEnumerator aEnum( i_rPageRange, i_nMinNumber, i_nMaxNumber, i_nLogicalOffset ) ;

    //Even if the input range wasn't completely valid, return what ranges could

    //be extracted from the input.

    o_rPageVector.reserve( static_cast< size_t >( aEnum.size() ) );

    for( StringRangeEnumerator::Iterator it = aEnum.begin( i_pPossibleValues );

         it != aEnum.end( i_pPossibleValues ); ++it )

    {

        o_rPageVector.push_back( *it );

    }

    return aEnum.mbValidInput;

}

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */