///
/// \file
/// Contains the C implementation of ANTLR3 bitsets as adapted from Terence Parr's
/// Java implementation.
///

// [The "BSD licence"]
// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
// http://www.temporal-wave.com
// http://www.linkedin.com/in/jimidle
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
// 3. The name of the author may not be used to endorse or promote products
//    derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include    <antlr3bitset.h>

// External interface
//

static  pANTLR3_BITSET  antlr3BitsetClone               (pANTLR3_BITSET inSet);
static  pANTLR3_BITSET  antlr3BitsetOR                  (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);
static  void                    antlr3BitsetORInPlace   (pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2);
static  ANTLR3_UINT32   antlr3BitsetSize                (pANTLR3_BITSET bitset);
static  void                    antlr3BitsetAdd                 (pANTLR3_BITSET bitset, ANTLR3_INT32 bit);
static  ANTLR3_BOOLEAN  antlr3BitsetEquals              (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);
static  ANTLR3_BOOLEAN  antlr3BitsetMember              (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);
static  ANTLR3_UINT32   antlr3BitsetNumBits             (pANTLR3_BITSET bitset);
static  void                    antlr3BitsetRemove              (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);
static  ANTLR3_BOOLEAN  antlr3BitsetIsNil               (pANTLR3_BITSET bitset);
static  pANTLR3_INT32   antlr3BitsetToIntList   (pANTLR3_BITSET bitset);

// Local functions
//
static  void                    growToInclude           (pANTLR3_BITSET bitset, ANTLR3_INT32 bit);
static  void                    grow                            (pANTLR3_BITSET bitset, ANTLR3_INT32 newSize);
static  ANTLR3_UINT64   bitMask                         (ANTLR3_UINT32 bitNumber);
static  ANTLR3_UINT32   numWordsToHold          (ANTLR3_UINT32 bit);
static  ANTLR3_UINT32   wordNumber                      (ANTLR3_UINT32 bit);
static  void                    antlr3BitsetFree        (pANTLR3_BITSET bitset);

static void
antlr3BitsetFree(pANTLR3_BITSET bitset)
{
    if  (bitset->blist.bits != NULL)
    {
                ANTLR3_FREE(bitset->blist.bits);
                bitset->blist.bits = NULL;
    }
    ANTLR3_FREE(bitset);

    return;
}

ANTLR3_API pANTLR3_BITSET
antlr3BitsetNew(ANTLR3_UINT32 numBits)
{
        pANTLR3_BITSET  bitset;

        ANTLR3_UINT32   numelements;

        // Allocate memory for the bitset structure itself
        //
        bitset  = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));

        if      (bitset == NULL)
        {
                return  NULL;
        }

        // Avoid memory thrashing at the up front expense of a few bytes
        //
        if      (numBits < (8 * ANTLR3_BITSET_BITS))
        {
                numBits = 8 * ANTLR3_BITSET_BITS;
        }

        // No we need to allocate the memory for the number of bits asked for
        // in multiples of ANTLR3_UINT64.
        //
        numelements     = ((numBits -1) >> ANTLR3_BITSET_LOG_BITS) + 1;

        bitset->blist.bits    = (pANTLR3_BITWORD) ANTLR3_MALLOC((size_t)(numelements * sizeof(ANTLR3_BITWORD)));
        if      (bitset->blist.bits == NULL)
        {
                ANTLR3_FREE(bitset);
                return  NULL;
        }
        memset(bitset->blist.bits, 0, (size_t)(numelements * sizeof(ANTLR3_BITWORD)));
        bitset->blist.length  = numelements;

        antlr3BitsetSetAPI(bitset);


        // All seems good
        //
        return  bitset;
}

ANTLR3_API void
antlr3BitsetSetAPI(pANTLR3_BITSET bitset)
{
    bitset->clone               =    antlr3BitsetClone;
    bitset->bor                 =    antlr3BitsetOR;
    bitset->borInPlace  =    antlr3BitsetORInPlace;
    bitset->size                =    antlr3BitsetSize;
    bitset->add                 =    antlr3BitsetAdd;
    bitset->grow                =    grow;
    bitset->equals              =    antlr3BitsetEquals;
    bitset->isMember    =    antlr3BitsetMember;
    bitset->numBits             =    antlr3BitsetNumBits;
    bitset->remove              =    antlr3BitsetRemove;
    bitset->isNilNode           =    antlr3BitsetIsNil;
    bitset->toIntList   =    antlr3BitsetToIntList;

    bitset->free                =    antlr3BitsetFree;
}

ANTLR3_API pANTLR3_BITSET
antlr3BitsetCopy(pANTLR3_BITSET_LIST blist)
{
    pANTLR3_BITSET  bitset;
        int                             numElements;

    // Allocate memory for the bitset structure itself
    //
    bitset  = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));

    if  (bitset == NULL)
    {
                return  NULL;
    }

        numElements = blist->length;

    // Avoid memory thrashing at the expense of a few more bytes
    //
    if  (numElements < 8)
    {
                numElements = 8;
    }

    // Install the length in ANTLR3_UINT64 units
    //
    bitset->blist.length  = numElements;

    bitset->blist.bits    = (pANTLR3_BITWORD)ANTLR3_MALLOC((size_t)(numElements * sizeof(ANTLR3_BITWORD)));

    if  (bitset->blist.bits == NULL)
    {
                ANTLR3_FREE(bitset);
                return  NULL;
    }

        ANTLR3_MEMCPY(bitset->blist.bits, blist->bits, (ANTLR3_UINT64)(numElements * sizeof(ANTLR3_BITWORD)));

    // All seems good
    //
    return  bitset;
}

static pANTLR3_BITSET
antlr3BitsetClone(pANTLR3_BITSET inSet)
{
    pANTLR3_BITSET  bitset;

    // Allocate memory for the bitset structure itself
    //
    bitset  = antlr3BitsetNew(ANTLR3_BITSET_BITS * inSet->blist.length);

    if  (bitset == NULL)
    {
                return  NULL;
    }

    // Install the actual bits in the source set
    //
    ANTLR3_MEMCPY(bitset->blist.bits, inSet->blist.bits, (ANTLR3_UINT64)(inSet->blist.length * sizeof(ANTLR3_BITWORD)));

    // All seems good
    //
    return  bitset;
}


ANTLR3_API pANTLR3_BITSET
antlr3BitsetList(pANTLR3_HASH_TABLE list)
{
    pANTLR3_BITSET              bitSet;
    pANTLR3_HASH_ENUM   en;
    pANTLR3_HASH_KEY    key;
    ANTLR3_UINT64               bit;

    // We have no idea what exactly is in the list
    // so create a default bitset and then just add stuff
    // as we enumerate.
    //
    bitSet  = antlr3BitsetNew(0);

    en          = antlr3EnumNew(list);

    while   (en->next(en, &key, (void **)(&bit)) == ANTLR3_SUCCESS)
    {
                bitSet->add(bitSet, (ANTLR3_UINT32)bit);
    }
    en->free(en);

    return NULL;
}

///
/// \brief
/// Creates a new bitset with at least one 64 bit bset of bits, but as
/// many 64 bit sets as are required.
///
/// \param[in] bset
/// A variable number of bits to add to the set, ending in -1 (impossible bit).
///
/// \returns
/// A new bit set with all of the specified bitmaps in it and the API
/// initialized.
///
/// Call as:
///  - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1);
///  - pANTLR3_BITSET = antlrBitsetOf(-1);  Create empty bitset
///
/// \remarks
/// Stdargs function - must supply -1 as last paremeter, which is NOT
/// added to the set.
///
///
ANTLR3_API pANTLR3_BITSET
antlr3BitsetLoad(pANTLR3_BITSET_LIST inBits)
{
        pANTLR3_BITSET  bitset;
        ANTLR3_UINT32  count;

        // Allocate memory for the bitset structure itself
        // the input parameter is the bit number (0 based)
        // to include in the bitset, so we need at at least
        // bit + 1 bits. If any arguments indicate a
        // a bit higher than the default number of bits (0 means default size)
        // then Add() will take care
        // of it.
        //
        bitset  = antlr3BitsetNew(0);

        if      (bitset == NULL)
        {
                return  NULL;
        }

        if      (inBits != NULL)
        {
                // Now we can add the element bits into the set
                //
                count=0;
                while (count < inBits->length)
                {
                        if  (bitset->blist.length <= count)
                        {
                                bitset->grow(bitset, count+1);
                        }

                        bitset->blist.bits[count] = *((inBits->bits)+count);
                        count++;
                }
        }

        // return the new bitset
        //
        return  bitset;
}

///
/// \brief
/// Creates a new bitset with at least one element, but as
/// many elements are required.
///
/// \param[in] bit
/// A variable number of bits to add to the set, ending in -1 (impossible bit).
///
/// \returns
/// A new bit set with all of the specified elements added into it.
///
/// Call as:
///  - pANTLR3_BITSET = antlrBitsetOf(n, n1, n2, -1);
///  - pANTLR3_BITSET = antlrBitsetOf(-1);  Create empty bitset
///
/// \remarks
/// Stdargs function - must supply -1 as last paremeter, which is NOT
/// added to the set.
///
///
ANTLR3_API pANTLR3_BITSET
antlr3BitsetOf(ANTLR3_INT32 bit, ...)
{
    pANTLR3_BITSET  bitset;

    va_list ap;

    // Allocate memory for the bitset structure itself
    // the input parameter is the bit number (0 based)
    // to include in the bitset, so we need at at least
    // bit + 1 bits. If any arguments indicate a
    // a bit higher than the default number of bits (0 menas default size)
    // then Add() will take care
    // of it.
    //
    bitset  = antlr3BitsetNew(0);

    if  (bitset == NULL)
    {
                return  NULL;
    }

    // Now we can add the element bits into the set
    //
    va_start(ap, bit);
    while   (bit != -1)
    {
                antlr3BitsetAdd(bitset, bit);
                bit = va_arg(ap, ANTLR3_UINT32);
    }
    va_end(ap);

    // return the new bitset
    //
    return  bitset;
}

static pANTLR3_BITSET
antlr3BitsetOR(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)
{
    pANTLR3_BITSET  bitset;

    if  (bitset1 == NULL)
    {
                return antlr3BitsetClone(bitset2);
    }

    if  (bitset2 == NULL)
    {
                return  antlr3BitsetClone(bitset1);
    }

    // Allocate memory for the newly ordered bitset structure itself.
    //
    bitset  = antlr3BitsetClone(bitset1);

    antlr3BitsetORInPlace(bitset, bitset2);

    return  bitset;

}

static void
antlr3BitsetAdd(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)
{
    ANTLR3_UINT32   word;

    word    = wordNumber(bit);

    if  (word   >= bitset->blist.length)
    {
                growToInclude(bitset, bit);
    }

    bitset->blist.bits[word] |= bitMask(bit);

}

static void
grow(pANTLR3_BITSET bitset, ANTLR3_INT32 newSize)
{
    pANTLR3_BITWORD   newBits;

    // Space for newly sized bitset - TODO: come back to this and use realloc?, it may
    // be more efficient...
    //
    newBits = (pANTLR3_BITWORD) ANTLR3_CALLOC(1, (size_t)(newSize * sizeof(ANTLR3_BITWORD)));
    if  (bitset->blist.bits != NULL)
    {
                // Copy existing bits
                //
                ANTLR3_MEMCPY((void *)newBits, (const void *)bitset->blist.bits, (size_t)(bitset->blist.length * sizeof(ANTLR3_BITWORD)));

                // Out with the old bits... de de de derrr
                //
                ANTLR3_FREE(bitset->blist.bits);
    }

    // In with the new bits... keerrrang.
    //
    bitset->blist.bits      = newBits;
    bitset->blist.length    = newSize;
}

static void
growToInclude(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)
{
        ANTLR3_UINT32   bl;
        ANTLR3_UINT32   nw;

        bl = (bitset->blist.length << 1);
        nw = numWordsToHold(bit);

        if      (bl > nw)
        {
                bitset->grow(bitset, bl);
        }
        else
        {
                bitset->grow(bitset, nw);
        }
}

static void
antlr3BitsetORInPlace(pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2)
{
    ANTLR3_UINT32   minimum;
    ANTLR3_UINT32   i;

    if  (bitset2 == NULL)
    {
                return;
    }


    // First make sure that the target bitset is big enough
    // for the new bits to be ored in.
    //
    if  (bitset->blist.length < bitset2->blist.length)
    {
                growToInclude(bitset, (bitset2->blist.length * sizeof(ANTLR3_BITWORD)));
    }

    // Or the miniimum number of bits after any resizing went on
    //
    if  (bitset->blist.length < bitset2->blist.length)
        {
                minimum = bitset->blist.length;
        }
        else
        {
                minimum = bitset2->blist.length;
        }

    for (i = minimum; i > 0; i--)
    {
                bitset->blist.bits[i-1] |= bitset2->blist.bits[i-1];
    }
}

static ANTLR3_UINT64
bitMask(ANTLR3_UINT32 bitNumber)
{
    return  ((ANTLR3_UINT64)1) << (bitNumber & (ANTLR3_BITSET_MOD_MASK));
}

static ANTLR3_UINT32
antlr3BitsetSize(pANTLR3_BITSET bitset)
{
    ANTLR3_UINT32   degree;
    ANTLR3_INT32   i;
    ANTLR3_INT8    bit;

    // TODO: Come back to this, it may be faster to & with 0x01
    // then shift right a copy of the 4 bits, than shift left a constant of 1.
    // But then again, the optimizer might just work this out
    // anyway.
    //
    degree  = 0;
    for (i = bitset->blist.length - 1; i>= 0; i--)
    {
                if  (bitset->blist.bits[i] != 0)
                {
                        for     (bit = ANTLR3_BITSET_BITS - 1; bit >= 0; bit--)
                        {
                                if  ((bitset->blist.bits[i] & (((ANTLR3_BITWORD)1) << bit)) != 0)
                                {
                                        degree++;
                                }
                        }
                }
    }
    return degree;
}

static ANTLR3_BOOLEAN
antlr3BitsetEquals(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)
{
    ANTLR3_INT32   minimum;
    ANTLR3_INT32   i;

    if  (bitset1 == NULL || bitset2 == NULL)
    {
        return  ANTLR3_FALSE;
    }

    // Work out the minimum comparison set
    //
    if  (bitset1->blist.length < bitset2->blist.length)
    {
                minimum = bitset1->blist.length;
    }
    else
    {
                minimum = bitset2->blist.length;
    }

    // Make sure explict in common bits are equal
    //
    for (i = minimum - 1; i >=0 ; i--)
    {
                if  (bitset1->blist.bits[i] != bitset2->blist.bits[i])
                {
                        return  ANTLR3_FALSE;
                }
    }

    // Now make sure the bits of the larger set are all turned
    // off.
    //
    if  (bitset1->blist.length > (ANTLR3_UINT32)minimum)
    {
                for (i = minimum ; (ANTLR3_UINT32)i < bitset1->blist.length; i++)
                {
                        if      (bitset1->blist.bits[i] != 0)
                        {
                                return  ANTLR3_FALSE;
                        }
                }
    }
    else if (bitset2->blist.length > (ANTLR3_UINT32)minimum)
    {
                for (i = minimum; (ANTLR3_UINT32)i < bitset2->blist.length; i++)
                {
                        if      (bitset2->blist.bits[i] != 0)
                        {
                                return  ANTLR3_FALSE;
                        }
                }
    }

    return  ANTLR3_TRUE;
}

static ANTLR3_BOOLEAN
antlr3BitsetMember(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)
{
    ANTLR3_UINT32    wordNo;

    wordNo  = wordNumber(bit);

    if  (wordNo >= bitset->blist.length)
    {
                return  ANTLR3_FALSE;
    }

    if  ((bitset->blist.bits[wordNo] & bitMask(bit)) == 0)
    {
                return  ANTLR3_FALSE;
    }
    else
    {
                return  ANTLR3_TRUE;
    }
}

static void
antlr3BitsetRemove(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)
{
    ANTLR3_UINT32    wordNo;

    wordNo  = wordNumber(bit);

    if  (wordNo < bitset->blist.length)
    {
                bitset->blist.bits[wordNo] &= ~(bitMask(bit));
    }
}
static ANTLR3_BOOLEAN
antlr3BitsetIsNil(pANTLR3_BITSET bitset)
{
   ANTLR3_INT32    i;

   for  (i = bitset->blist.length -1; i>= 0; i--)
   {
       if   (bitset->blist.bits[i] != 0)
       {
                        return ANTLR3_FALSE;
       }
   }

   return   ANTLR3_TRUE;
}

static ANTLR3_UINT32
numWordsToHold(ANTLR3_UINT32 bit)
{
    return  (bit >> ANTLR3_BITSET_LOG_BITS) + 1;
}

static  ANTLR3_UINT32
wordNumber(ANTLR3_UINT32 bit)
{
    return  bit >> ANTLR3_BITSET_LOG_BITS;
}

static ANTLR3_UINT32
antlr3BitsetNumBits(pANTLR3_BITSET bitset)
{
    return  bitset->blist.length << ANTLR3_BITSET_LOG_BITS;
}

/** Produce an integer list of all the bits that are turned on
 *  in this bitset. Used for error processing in the main as the bitset
 *  reresents a number of integer tokens which we use for follow sets
 *  and so on.
 *
 *  The first entry is the number of elements following in the list.
 */
static  pANTLR3_INT32
antlr3BitsetToIntList   (pANTLR3_BITSET bitset)
{
    ANTLR3_UINT32   numInts;        // How many integers we will need
    ANTLR3_UINT32   numBits;        // How many bits are in the set
    ANTLR3_UINT32   i;
    ANTLR3_UINT32   index;

    pANTLR3_INT32  intList;

    numInts = bitset->size(bitset) + 1;
    numBits = bitset->numBits(bitset);

    intList = (pANTLR3_INT32)ANTLR3_MALLOC(numInts * sizeof(ANTLR3_INT32));

    if  (intList == NULL)
    {
                return NULL;    // Out of memory
    }

    intList[0] = numInts;

    // Enumerate the bits that are turned on
    //
    for (i = 0, index = 1; i<numBits; i++)
    {
                if  (bitset->isMember(bitset, i) == ANTLR3_TRUE)
                {
                        intList[index++]    = i;
                }
    }

    // Result set
    //
    return  intList;
}