seqimp.cpp

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

/*
 *
 *          Copyright (C) 1994, M. A. Sridhar
 *  
 *
 *     This software is Copyright M. A. Sridhar, 1994. You are free
 *     to copy, modify or distribute this software  as you see fit,
 *     and to use  it  for  any  purpose, provided   this copyright
 *     notice and the following   disclaimer are included  with all
 *     copies.
 *
 *                        DISCLAIMER
 *
 *     The author makes no warranties, either expressed or implied,
 *     with respect  to  this  software, its  quality, performance,
 *     merchantability, or fitness for any particular purpose. This
 *     software is distributed  AS IS.  The  user of this  software
 *     assumes all risks  as to its quality  and performance. In no
 *     event shall the author be liable for any direct, indirect or
 *     consequential damages, even if the  author has been  advised
 *     as to the possibility of such damages.
 *
 */







#ifndef _seqimp_cxx_ /* Sun Nov  7 12:38:41 1993 */
#define _seqimp_cxx_



// Implementation of the sequence data structure
// Invariants maintained:
//     - Initially nullify all cells from 0 to _size-1.




#include "base/sequence.h" 
#include "base/stream.h"


#ifndef __GNUC__
#include "base/intset.h"
#endif



#include "base/basicops.h"

#define NEW_OP new



// Helper class for managing segments

struct SegDesc;

class SegmentedSequence {

public:
    SegmentedSequence (long initial_cap = 8);
    ~SegmentedSequence ();

    CL_VoidPtr& operator[] (long index);

    bool ResizeTo    (long new_cap);
    // Guarantee that there are at least new_cap cells in the sequence.

protected:
    SegDesc*         _segs;
    short            _numSegs;
    long             _totalCap;
};



//                                                                     
// ------------------------ Creation and destruction --------------    
//


template <class BaseType>
CL_Sequence<BaseType>::CL_Sequence (long initial_size,
                                    CL_ObjectIOFilter* bld)
{
    _idata = new SegmentedSequence (initial_size);
    if (_idata)
        _size = initial_size;
    else
        _size = 0;
    if (_idata) {
        SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
        BaseType p = CL_Basics<BaseType>::NullValue ();
        for (long i = 0; i < _size; i++)
            _data[i] = CL_Basics<BaseType>::MakeCopy (p);
    }
    _builder = bld;
}




template <class BaseType>
CL_Sequence<BaseType>::CL_Sequence (const BaseType s[], long count,
                                    CL_ObjectIOFilter* bld)
{
    _idata = new SegmentedSequence (count);
    if (_idata)
        _size = count;
    else
        _size = 0;
    if (_idata) {
        _size = count;
        SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
        for (long i = 0; i < count; i++)
            _data[i] = CL_Basics<BaseType>::MakeCopy (s[i]);
    }
    else
        _size = 0;
    _builder = bld;
}


// Copy constructor
template <class BaseType>
CL_Sequence<BaseType>::CL_Sequence (const CL_Sequence<BaseType>& a)
{
    _size = 0;
    _idata = new SegmentedSequence;
    if (_idata)
        *this = a;
    _builder = a._builder;
}






//
// ------------------------ Element access ---------------------------

template <class BaseType>
bool CL_Sequence<BaseType>::Insert (const BaseType& o, long i)
{
    if (!PrepareToChange() ||  !_DoInsert (o, i))
        return FALSE;
    Notify ();
    return TRUE;
}
            

template <class BaseType>
BaseType& CL_Sequence<BaseType>::operator[] (long index) const
{
    if (!_idata) {
        static BaseType junk = CL_Basics<BaseType>::NullValue ();
        // This code better not be executed under BC++ 3.1: that compiler
        // seems to have a bug that generates bad code for static local
        // template objects, causing a program crash.
        return junk;
    }
    if (index < 0 ||  index >= _size) {
        CL_Error::Warning ("CL_Sequence::op[]: index %ld"
                           " out of range 0..%ld", index, _size-1);
        static BaseType junk = CL_Basics<BaseType>::NullValue ();
        // This code better not be executed under BC++ 3.1: that compiler
        // seems to have a bug that generates bad code for static local
        // template objects, causing a program crash.
        return junk;
    }
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    return CL_Basics<BaseType>::Deref (_data[index]);
}



template <class BaseType>
short CL_Sequence<BaseType>::_Compare (const BaseType& o1,
                                       const BaseType& o2) const
{
    return CL_Basics<BaseType>::Compare (o1, o2);
}







template <class BaseType>
short CL_Sequence<BaseType>::_DoInsert (const BaseType& o, long i)
{
    if (i < -1 || i >= _size)
        return FALSE;
    if (!_idata) {
        return FALSE;
    }
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    if (i == _size-1) {
        if (!_data.ResizeTo (_size+1))
            return FALSE;
        _data[i+1] = CL_Basics<BaseType>::MakeCopy (o);
        _size++;
    }
    else {
        if (!_ShiftRightAt (i+1, 1))
            return FALSE;
        (*this)[i+1] = o;
    }
    return TRUE;
}







template <class BaseType>
long CL_Sequence<BaseType>::InsertByRank (const BaseType& o)
{
    if (!_idata || !PrepareToChange())
        return FALSE;
    register long i;
    register long n = Size();
    for (i = 0; i < n; i++)
        if (CL_Basics<BaseType>::Compare ((*this)[i], o) >= 0)
            break;
    if (_DoInsert (o, i)) {
        Notify();
        return i;
    }
    return -1;
}



template <class BaseType>
BaseType CL_Sequence<BaseType>::Remove (long i)
{
    if (!PrepareToChange() || !_idata || _size <= 0 || i < 0 || i >= _size)
        return CL_Basics<BaseType>::NullValue();
    BaseType r = (*this)[i];
    if (_ShiftLeftAt (i+1, 1)) {
        Notify ();
        return r;
    }
    return CL_Basics<BaseType>::NullValue();
}


template <class BaseType>
BaseType CL_Sequence<BaseType>::ExtractLeftmost ()
{
    BaseType p;
    if (!PrepareToChange())
        return p;
    if (!_idata || _size <= 0)
        return CL_Basics<BaseType>::NullValue ();
    p = (*this)[0];
    _ShiftLeftAt (1,1);
    Notify ();
    return p;
}

template <class BaseType>
BaseType CL_Sequence<BaseType>::ExtractRightmost ()
{
    BaseType p;
    if (!_idata || _size <= 0 || !PrepareToChange())
        return CL_Basics<BaseType>::NullValue ();
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    p = (*this)[_size-1];
    CL_Basics<BaseType>::Destroy (_data[_size-1]);
    _size--;
    _data.ResizeTo (_size);
    Notify ();
    return p;
}




// ------------------- Sequence methods ------------------------

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




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



template <class BaseType>
void CL_Sequence<BaseType>::operator= (const CL_Sequence<BaseType>& a)
{
    if (this == &a || !PrepareToChange())
        return; // Do nothing
    long i;
    
    if (!_idata)
        return;
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    for (i = 0; i < _size; i++)
        CL_Basics<BaseType>::Destroy (_data[i]);
    if (!_data.ResizeTo (a.Size()))
        return;
    _size = a.Size();
    for (i = 0; i < _size; i++) {
        _data[i] = CL_Basics<BaseType>::MakeCopy (a[i]);
    }
    Notify ();
}



template <class BaseType>
CL_Sequence<BaseType>& CL_Sequence<BaseType>::operator +=
    (const CL_Sequence<BaseType>& a)
{
    if (!_idata) {
        return *this;
    }
    if (!PrepareToChange())
        return *this;
    SegmentedSequence& _data = (* (SegmentedSequence*) _idata);
    if (!_data.ResizeTo (_size + a._size))
        return *this;
    long old_size = _size;
    _size += a._size;
    register long n = a._size; 
    for (long i = 0; i < n; i++) {
        _data [old_size + i] = CL_Basics<BaseType>::MakeCopy (a[i]);
    }
    Notify ();
    return *this;
}



#ifndef __GNUC__
template <class BaseType>
CL_Sequence<BaseType> CL_Sequence<BaseType>::Subsequence
    (const CL_IntegerSet& s) const
{
    register long m = Size();
    CL_Sequence<BaseType> retVal;
    // Note that we cannot declare retVal to be of a particular size,
    // because we don't know how many elements of s represent legal
    // indices in this sequence. Well, maybe we could do something like
    //     CL_IntegerSet t (0, Size()-1); t *= s;
    // and then use t's size to be the initial size of retVal. But that
    // will likely not save much of the overhead incurred by expanding
    // retVal if it weren't pre-sized.