seqimp.cpp

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C++ 代码 · 共 788 行 · 第 1/2 页

    for (long i = 0; i < m; i++)
        if (s.Includes (i)) {
            retVal.Add ((*this)[i]);
        }
    return retVal;
}


template <class BaseType>
CL_Sequence<BaseType> CL_Sequence<BaseType>::operator-
    (const CL_IntegerSet& s) const
{
    CL_IntegerSet t (0, Size()-1);
    return Subsequence (t-s);
}

template <class BaseType>
void CL_Sequence<BaseType>::operator-= (const CL_IntegerSet& s)
{
    register long m = Size();
    register long n = s.Size();
    register long current = s.ItemWithRank (0);
    register long next = current;
    if (n <= 0 || current < 0 || current >= Size())
        return;
    if (!_idata)
        return; // No memory
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    for (register long i = 0; i < n && next < m; i++) {
        next = minl (m, s.ItemWithRank (i+1));
        for (register long j = current; j < next; j++) {
            CL_Basics<BaseType>::Destroy (_data[j]);
            _data[j-i+1] = _data[j];
        }
    }
}


#endif // __GNUC__


template <class BaseType>
void CL_Sequence<BaseType>::MakeEmpty ()
{
    if (!_idata) {
        return;
    }
    if (!PrepareToChange())
        return;
    _DoMakeEmpty ();
    Notify ();
}

template <class BaseType>
void CL_Sequence<BaseType>::_DoMakeEmpty ()
{
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    for (long i = 0; i < _size; i++)
        CL_Basics<BaseType>::Destroy (_data[i]);
    _size = 0;
    _data.ResizeTo (0);
}






template <class BaseType>
bool CL_Sequence<BaseType>::ChangeSize (long new_size)
{
    if (!PrepareToChange ())
        return FALSE;
    if (!_idata) {
        return FALSE;
    }
    if (new_size == _size)
        return TRUE;
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    if (new_size < _size) {
        for (register long i = new_size; i < _size; i++)
            CL_Basics<BaseType>::Destroy (_data[i]);
    }
    if (!_data.ResizeTo (new_size))
        return FALSE;
    if (new_size > _size)  {
        BaseType nul = CL_Basics<BaseType>::NullValue ();
        for (register long i = _size; i < new_size; i++)
            _data[i] = CL_Basics<BaseType>::MakeCopy (nul);
    }
    _size = new_size;
    Notify();
    return TRUE;
}








template <class BaseType>
bool CL_Sequence<BaseType>::ShiftLeftAt (long pos, long amount)
{
    if (!PrepareToChange ())
        return FALSE;
    if (!_ShiftLeftAt (pos, amount))
        return FALSE;
    Notify();
    return TRUE;
}



template <class BaseType>
bool CL_Sequence<BaseType>::_ShiftLeftAt (long pos, long amount)
{
    if (!_idata || pos < 1 || pos > _size || amount > pos)
        return FALSE;
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    long i;
    for (i = pos-amount; i < pos; i++)
        CL_Basics<BaseType>::Destroy (_data[i]);
    for (i = pos; i < _size; i++) {
        _data[i-amount] = _data[i];
    }
    for (i = _size-amount; i < _size; i++)
        _data[i] = NULL;
    _size -= amount;
    _data.ResizeTo (_size);
    return TRUE;
}


template <class BaseType>
bool CL_Sequence<BaseType>::IsSorted () const
{
    long i;
    for (i = 0; i < _size; i++)
        if (_Compare ((*this)[i], (*this)[i+1]) > 0)
            return FALSE;
    return TRUE;
}





template <class BaseType>
bool CL_Sequence<BaseType>::Sort ()
{
    if (!_idata || !PrepareToChange())
        return FALSE;
    if (_QuickSort (0, _size-1)) {
        Notify ();
        return TRUE;
    }
    return FALSE;
}






template <class BaseType>
long CL_Sequence<BaseType>::LinearSearch (const BaseType& o) const
{
    if (!_idata || _size == 0)
        return -1;
    long i;
    short result;
    for (i = 0; i < _size; i++) {
        result = _Compare ((*this)[i], o);
        if (result == 0)
            return i;
    }
    return -1;
}



template <class BaseType>
bool CL_Sequence<BaseType>::BinarySearch (const BaseType& o, long& index) const
{
    if (!_idata)
        return FALSE;
    long i;
    short result;
    if (_size <= 7) { // Small number of keys, do a linear search
        if (_size == 0) {
            index = -1;
            return FALSE;
        }
        for (i = 0; i < _size; i++) {
            result = _Compare ((*this)[i], o);
            if (result >= 0)
                break;
        }
        if (result == 0) {
            index = i;
            return TRUE;
        }
        else  {
            index = i-1;
            return FALSE;
        }
    }

    // Do a binary search
    long lo = 0, hi = _size-1, mid;
    while (lo <= hi) {
        mid = (lo + hi)/2;
        result = _Compare ((*this)[mid], o);
        if (result == 0) {
            index = mid;
            return TRUE;
        }
        if (result < 0)
            lo = mid+1;
        else
            hi = mid-1;
    }
    index = (result <= 0) ? (mid) :  mid-1;
    return FALSE;
}







// #include <stdlib.h>

template <class BaseType>
bool CL_Sequence<BaseType>::_QuickSort (long left, long right)
{
    if (!_idata) {
        return FALSE;
    }
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);

    // The sort code is basically stolen from Bentley's "Programming
    // Pearls" book.
    long i;

    for (i = left; i < right; i++) // Scan to see if already sorted
        if (_Compare ((*this)[i], (*this)[i+1]) > 0)
            break;
    if (i >= right) // It's already sorted
        return FALSE;

    while (left < right) {
        BaseType t;
        CL_VoidPtr tmp;
        long r, m;
        // r = random (right - left - 1) + left + 1;
        r = left + 1;

        tmp         = _data[r];
        _data[r]    = _data[left];
        _data[left] = (CL_VoidPtr) tmp;

        m = left;
        for (i = left+1; i <= right; i++) {
            if (_Compare ((*this)[i], (*this)[left])
                < 0) {
                m ++;
                tmp      = _data[m];
                _data[m] = _data[i];
                _data[i] = tmp;
            }
        }
        tmp         = _data[m];
        _data[m]    = _data[left];
        _data[left] = tmp;

        // Now recurse on the smaller half, and loop back for the
        // bigger half so as to minimize stack depth
        if (m-left < right-m) {
            _QuickSort (left, m-1);
            left = m+1;
        }
        else {
            _QuickSort (m+1, right);
            right = m-1;
        }
    }
    return TRUE;
}






template <class BaseType>
long CL_Sequence<BaseType>::StorableFormWidth () const
{
    if (!_idata) {
        return 0;
    }
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    long l;
    for (long i = 0; i < _size; i++)
        l += CL_Basics<BaseType>::StoreWidth
            (CL_Basics<BaseType>::Deref (_data [i]));
    return l + (sizeof _size) + sizeof (CL_ClassId);
}




template <class BaseType>
bool CL_Sequence<BaseType>::ReadFrom (const CL_Stream& s)
{
    if (!_idata) {
        return FALSE;
    }
    if (!PrepareToChange() || !ReadClassId (s) )
        return FALSE;
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    long size;
    CL_ObjectPtr* p;
    long cap;
    if (!s.Read (size))
        return FALSE;
    long i;
    for (i = 0; i < _size; i++)
        CL_Basics<BaseType>::Destroy (_data[i]);
    if (!_data.ResizeTo (size))
        return FALSE;
    _size = size;
    BaseType nul = CL_Basics<BaseType>::NullValue ();
    for (i = 0; i < _size; i++) {
        _data[i] = CL_Basics<BaseType>::MakeCopy (nul);
        if (!_ReadElement (s, i))
            return FALSE;
    }
    Notify();
    return TRUE;
};
        

template <class BaseType>
bool CL_Sequence<BaseType>::_ReadElement (const CL_Stream& s, long i)
{
    return CL_RestoreFrom ((*this)[i], s, _builder);
}





template <class BaseType>
bool CL_Sequence<BaseType>::WriteTo (CL_Stream& s) const
{
    if (!_idata) {
        return FALSE;
    }
    if (!s.Write (ClassId())  || !s.Write (_size))
        return FALSE;
    for (long i = 0; i < _size; i++) {
        if (!_WriteElement (s, i))
            return FALSE;
    }
    return TRUE;
}


template <class BaseType>
bool CL_Sequence<BaseType>::_WriteElement (CL_Stream& s, long i) const
{
    return CL_SaveTo ((*this)[i], s, _builder);
}




template <class BaseType>
CL_Sequence<BaseType>::~CL_Sequence ()
{
    _DoMakeEmpty ();
    if (_idata)
        delete (SegmentedSequence*) _idata;
}



#endif   /* _seqimp_cxx */