4limit.html

C ++ in action

template <class T>
inline T & DynArray<T>::operator [] (int i)
{
    assert (i < _capacity);
    return _arr[i];
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>The <var>Grow</var> method works by doubling the size of the array. However, when asked to extend the array beyond doubling, it will oblige, too.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>// private method
template &lt;class T&gt;
void DynArray &lt;T&gt;::Grow (int idxMax)
{
    int newSize = 2 * _capacity;
    if (idxMax &gt;= newSize)
        newSize = idxMax + 1;
    // allocate new array
    T * arrNew = new T [newSize];
    // copy all entries
    int i;
    for (i = 0; i &lt; _capacity; ++i)
        arrNew [i] = _arr [i];
    for (; i &lt; newSize; ++i)
        arrNew [i] = _valDefault;
    _capacity = newSize;
    // free old memory
    delete []_arr;
    // substitute new array for old array
    _arr = arrNew;
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>Now it's time to make use of our dynamic array template to see how easy it really is. Let's start with the class <var>MultiNode</var>. In the old, limited, implementation it had two arrays: an array of pointers to <var>Node</var> and an array of Boolean flags. Our first step is to change the types of these arrays to, respectively, <var>DynArray&lt;Node*&gt;</var> and <var>DynArray&lt;bool&gt;</var>. We have to pass default values to the constructors of these arrays in the preamble to <var>MultiNode</var> constructor. These methods that just access the arrays will work with no changes (due to our overloading of operator []), except for the places where we used to check for array bounds. Those are the places where we might have to extend the arrays, so we should use the new <var>Add</var> method. It so happens that the only place we do it is inside the <var>AddChild</var> method and the conversion is straightforward.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class MultiNode: public Node
{
public:
    MultiNode (Node * pNode)
        : _aChild (0),
          _aIsPositive (false),
          _iCur (0)
    {
        AddChild (pNode, true);
    }
    ~MultiNode ();
    void AddChild (Node * pNode, bool isPositive)
    {
        _aChild.Add (_iCur, pNode);
        _aIsPositive.Add (_iCur, isPositive);
        ++_iCur;
    }
protected: 
    int                   _iCur;
    DynArray&lt;Node*&gt;       _aChild;
    DynArray&lt;bool&gt;        _aIsPositive;
};

MultiNode::~MultiNode ()
{
    for (int i = 0; i &lt; _iCur; ++i)
        delete _aChild [i];
}</pre>
    </td></tr>
</table>
<!-- End Code -->


<P>Let's have one more look at the <var>Calc</var> method of <var>SumNode</var>. Other than for the removal of error checking (we have gotten rid of the unnecessary flag, <var>_isError</var>), it works as if nothing have changed.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>double SumNode::Calc () const
{
    double sum = 0.0;
    for (int i = 0; i &lt; _iCur; ++i)
    {
        double val = _aChild [i]-&gt;Calc ();
        if (_aIsPositive[i])
            sum += val;
        else
            sum --= val;
    }
    return sum;
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>The only difference is that when we access our arrays <var>_aChild [i]</var> and <var>_aIsPositive [i]</var>, we are really calling the overloaded operator [] of the respective dynamic arrays. And, by the way, since the method <var>Calc</var> is const, it is the const version of the overload we're calling. Isn't that beautiful?
<h3>Separating Functionality into New Classes</h3>
<P>I'm not happy with the structuring of the symbol table. Just one look at the seven data members tells me that a new class is budding. (Seven is the magic number.) Here they are again:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>HTable   _htab;
int    * _offStr;
int      _capacity;
int      _curId;
char   * _strBuf;
int      _bufSize;
int      _curStrOff;</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>The rule of thumb is that if you have too many data members you should group some of them into new classes. This is actually one of the three rules of class formation. You need a new class when there are
<ul>
<li>too many local variables in a function,
<li>too many data members in a class or
<li>too many arguments to a function.
</ul>
<P>It will become clearer why these rules make perfect sense (and why seven is the magic number) when we talk about ways of dealing with complexity in the third part of this book.
<P>The last three data members of the symbol table are perfect candidates for a new string-buffer object. The string buffer is able to store strings and assign them numbers, called offsets, that uniquely identify them. As a bonus, we'll make the string buffer dynamic, so we won't have to worry about overflowing it with too many strings.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class StringBuffer
{
public:
    StringBuffer ()
        : _strBuf (0), _bufSize (0), _curStrOff (0)
    {}
    ~StringBuffer ()
    {
        delete _strBuf;
    }
    int AddString (char const * str);
    char const * GetString (int off) const
    {
        assert (off &lt; _curStrOff);
        return &amp;_strBuf [off];
    }
private:
    void Reallocate (int addLen);

    char  * _strBuf;
    int     _bufSize;
    int     _curStrOff;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>When the buffer runs out of space, the <var>AddString</var> method reallocates the whole buffer.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>int StringBuffer::AddString (char const * str)
{
    int len = strlen (str);
    int offset = _curStrOff;
    // is there enough space?
    if (_curStrOff + len + 1 &gt;= _bufSize)
    {
        Reallocate (len + 1);
    }
    // copy the string there
    strncpy (&amp;_strBuf [_curStrOff], str, len);
    // calculate new offset
    _curStrOff += len;
    _strBuf [_curStrOff] = 0;  // null terminate
    ++_curStrOff;
    return offset;
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>The reallocation follows the standard doubling pattern--but making sure that the new string will fit no matter what.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>void StringBuffer::Reallocate (int addLen)
{
    int newSize = _bufSize * 2;
    if (newSize &lt;= _curStrOff + addLen)
        newSize = _curStrOff + addLen;
    char * newBuf = new char [newSize];
    for (int i = 0; i &lt; _curStrOff; ++i)
        newBuf [i] = _strBuf [i];
    delete []_strBuf;
    _strBuf = newBuf;
    _bufSize = newSize;
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>Now the symbol table is much simpler. It only has four data members. I also used this opportunity to turn the array <var>_aOffStr</var> into a dynamic array.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class SymbolTable
{
    // Private embedded anonymous enum
    enum { cSymInit = 64 };
public:
    // Public embedded anonymous enum
    enum { idNotFound = -1 };
    SymbolTable ();
    int ForceAdd (char const * str);
    int Find (char const * str) const;
    char const * GetString (int id) const;
private:
    int               _curId;
    HTable            _htab;
    DynArray&lt;int&gt;     _aOffStr; // offsets of strings in buffer
    StringBuffer      _bufStr;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>Here's the new improved implementation of <var>ForceAdd</var>. We don't have to worry any more about overflowing the offset table or the string buffer. 
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>int SymbolTable::ForceAdd (char const * str)
{
    int offset = _bufStr.AddString (str);
    _aOffStr.Add (_curId, offset);
    _htab.Add (str, _curId);
    ++_curId;
    return _curId - 1;
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>It's always a pleasure to be able to simplify some code. This is the part of programming that I like best. <var>ForceAdd</var> now reads almost like a haiku.
<p>This is how the constructor of the symbol table shrinks
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>SymbolTable::SymbolTable ()
    : _curId (0), 
      _htab (cSymInit + 1),
      _aOffStr (0)
{}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>And this is how simple the parsing of a symbolic variable becomes
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>// Factor := Ident
if (id == SymbolTable::idNotFound)
    id = _symTab.ForceAdd (strSymbol);
assert (id != SymbolTable::idNotFound);
pNode = new VarNode (id, _store);</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>Class <var>Store</var> needs two dynamic arrays and a few little changes where the bounds used to be checked.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class Store
{
private:
    // private anonymous enum
    enum { stNotInit, stInit };
public:
    explicit Store (SymbolTable &amp; symTab);
    bool IsInit (int id) const
    {
        assert (id &gt;= 0);