7
\$\begingroup\$

Please my review my implementation of the gap buffer algorithm for efficient text editing. I am particularly interested in the following areas:

  1. Have I properly implemented a C++14 container and random-access iterator? I found the spec to be a little hard to understand but I think I have everything required I hope. But in particular, have I implemented const iterators correctly?

  2. There are a couple of places where I need advice on whether I've coded correctly/efficiently. They are marked by comments.

  3. Any other C++ stylistic advice.


This is buffer.h:

// Buffer -- manages text in a text editor (Interface)
//
// By Jaldhar H. Vyas <[email protected]>
// Copyright (C) 2017, Consolidated Braincells Inc. All rights reserved.
// "Do what thou wilt" shall be the whole of the license.

#ifndef _BUFFER_H_
#define _BUFFER_H_

#include <vector>

using BUFFER = std::vector<char>;

template<typename T>
class Buffer {
public:
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using iterator = BufferIterator<T>;
    using const_iterator = BufferIterator<const T>;
    using difference_type = ptrdiff_t;
    using size_type = size_t;

    Buffer();
    Buffer(const Buffer<T>& that);

    Buffer<T>& operator=(const Buffer<T>& that);
    bool       operator==(const Buffer<T>& that) const;
    bool       operator!=(const Buffer<T>& that) const;
    reference  operator[](difference_type n);

    iterator begin();
    iterator end();

    const_iterator cbegin();
    const_iterator cend();

    size_type capacity();
    bool      empty();
    size_type max_size();
    size_type size();

    bool            deletePrevious();
    bool            deleteNext();
    bool            insert(value_type c);
    difference_type point() const;
    bool            pointMove(int count);
    bool            pointSet(BUFFER::iterator loc);

private:
    friend iterator;

    static constexpr size_t BUFFERSIZE = 80;

    BUFFER           _text;
    difference_type  _point;
    BUFFER::iterator _gapStart;
    BUFFER::iterator _gapEnd;

    void             moveGap();
    BUFFER::iterator userToGap(difference_type p);
    difference_type  gapToUser(BUFFER::iterator i);
};

template<typename T>
void std::swap(Buffer<T>& lhs, Buffer<T>& rhs);

template<typename T>
class BufferIterator {
public:
    // Iterator traits, previously from std::iterator.
    using value_type = T;
    using difference_type = typename BUFFER::difference_type;
    using pointer = typename BUFFER::iterator;
    using reference = typename Buffer<T>::reference;
    using iterator_category = std::random_access_iterator_tag;

    BufferIterator();
    BufferIterator(Buffer<T>& b);
    BufferIterator(const BufferIterator<T>& that);

    BufferIterator<T>&       operator=(const BufferIterator<T>& that);
    bool                     operator==(const BufferIterator<T>& that);
    bool                     operator!=(const BufferIterator<T>& that);
    BufferIterator<T>&       operator+=(const difference_type& n);
    BufferIterator<T>        operator+(const difference_type& n);
    BufferIterator<T>&       operator++();
    BufferIterator<T>        operator++(int);
    BufferIterator<T>&       operator-=(const difference_type& n);
    BufferIterator<T>        operator-(const difference_type& n);
    BufferIterator<T>&       operator--();
    const BufferIterator<T>& operator--(int);
    reference                operator*() const;
    pointer                  operator->() const;
    reference                operator[](const difference_type& n) const;

private:
    Buffer<T>& _b;
    pointer    _i;

};

template<typename T>
bool std::operator<(const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);
template<typename T>
bool std::operator>(const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);
template<typename T>
bool std::operator<=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs);
template<typename T>
bool std::operator>=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs);
template<typename T>
typename BufferIterator<T>::difference_type std::operator+(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);
template<typename T>
typename BufferIterator<T>::difference_type std::operator-(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);

template<typename T>
void std::swap(BufferIterator<T>& lhs, BufferIterator<T>& rhs);

#include "buffer.inl"

#endif

And this is buffer.inl:

// Buffer -- manages text in a text editor (Implementation)
//
// By Jaldhar H. Vyas <[email protected]>
// Copyright (C) 2017, Consolidated Braincells Inc. All rights reserved.
// "Do what thou wilt" shall be the whole of the license.

#include <algorithm>
#include <cstdlib>
#include <iterator>

template<typename T>
Buffer<T>::Buffer() : _text(BUFFERSIZE, 0), _point{0}, _gapStart{_text.begin()},
_gapEnd{_text.end()} {
}

template<typename T>
Buffer<T>::Buffer(const Buffer<T>& that) : _text(that._text),
_point{that._point}, _gapStart{that._gapStart}, _gapEnd{that._gapEnd} {
}

template<typename T>
Buffer<T>& Buffer<T>::operator=(const Buffer<T>& that) {
    if (this != &that) {
        this->_text = that._text;
        this->_point = that._point;
        this->_gapStart = that._gapStart;
        this->_gapEnd = that._gapEnd;
    }
    return *this;
}

template<typename T>
bool Buffer<T>::operator==(const Buffer<T>& that) const {
    return this->_text == that._text &&
        this->_point == that._point &&
        this->_gapStart == that._gapStart &&
        this->_gapEnd == that._gapEnd;
}

template<typename T>
bool Buffer<T>::operator!=(const Buffer<T>& that) const {
    return !operator==(that);
}

template<typename T>
typename Buffer<T>::reference Buffer<T>::operator[](difference_type n) {
    return Buffer<T>::iterator(*this)[n];
}

template<typename T>
typename Buffer<T>::iterator Buffer<T>::begin() {
    return Buffer<T>::iterator(*this);
}

template<typename T>
typename Buffer<T>::iterator Buffer<T>::end() {
    return Buffer<T>::iterator(*this) +  size();
}

template<typename T>
typename Buffer<T>::const_iterator Buffer<T>::cbegin() {
    return const_cast<const Buffer<T>&>(*this).begin();
}

template<typename T>
typename Buffer<T>::const_iterator Buffer<T>::cend() {
    return const_cast<const Buffer<T>&>(*this).end();
}

template<typename T>
typename Buffer<T>::size_type Buffer<T>::capacity() {
    return _text.capacity();
}

template<typename T>
bool Buffer<T>::empty() {
    return size() ? false : true;
}

template<typename T>
typename Buffer<T>::size_type Buffer<T>::max_size() {
    return _text.max_size();
}

template<typename T>
typename Buffer<T>::size_type Buffer<T>::size() {
    return _text.capacity() - (_gapEnd - _gapStart);
}

template<typename T>
bool Buffer<T>::deletePrevious() {
    if (_point <= 0 || _point > static_cast<difference_type>(size())) {
        return false;
    }

    moveGap();
    _gapStart--;
    return pointMove(-1);
}

template<typename T>
bool Buffer<T>::deleteNext() {
    if (_point < 0 || _point >= static_cast<difference_type>(size())) {
        return false;
    }

    moveGap();
    _gapEnd++;
    return true;
}

template<typename T>
bool Buffer<T>::insert(value_type c) {
    if (_point < 0 || _point > static_cast<difference_type>(size())) {
        return false;
    }

    moveGap();
    *_gapStart = c;
    _gapStart++;
    return pointMove(1);
}

template<typename T>
typename Buffer<T>::difference_type Buffer<T>::point() const {
    return _point;
}

template<typename T>
bool Buffer<T>::pointMove(int count) {
    Buffer<T>::difference_type loc = _point + count;
    if (loc < 0 || loc > static_cast<Buffer<T>::difference_type>(size())) {
        return false;
    }

    return pointSet(userToGap(loc));
}

template<typename T>
bool Buffer<T>::pointSet(BUFFER::iterator loc) {
    if (loc < _text.begin() || loc > _text.end()) {
        return false;
    }

    _point = gapToUser(loc);

    return true;
}

template<typename T>
void Buffer<T>::moveGap() {

    // I used shrink_to_fit because I found that resize() was sometimes
    // giving me more space than I asked for.  Is that normal?  If so, is
    // this how I should deal with it?  Should I bother trying to reclaim
    // space if the gap gets too big?

    if (_gapStart == _gapEnd) {
        _text.resize(_text.capacity() + BUFFERSIZE, 0);
        _text.shrink_to_fit();
        _gapStart = _text.end() - BUFFERSIZE;
        _gapEnd = _text.end();
    }

    BUFFER::iterator p = userToGap(_point);
    if (p == _gapStart) {
        return;
    }

    Buffer<T>::difference_type n;
    if (_gapStart < p) { // point is after gapStart
        n = p - _gapEnd;
        copy(p - n , p, _gapStart);
        _gapStart += n;
        _gapEnd += n;
        _point = gapToUser(_gapStart);
    } else { // point is before _gapStart
        n = _gapStart - p;
        _gapStart -= n;
        _gapEnd -= n;
        copy(p, p + n, _gapEnd);
    }
}

template<typename T>
BUFFER::iterator Buffer<T>::userToGap(difference_type p) {
    BUFFER::iterator i = _text.begin() + p;

    if (i > _gapStart) {
        i += (_gapEnd - _gapStart);
    }

    return i;
}

template<typename T>
typename Buffer<T>::difference_type Buffer<T>::gapToUser(BUFFER::iterator i) {
    Buffer<T>::difference_type p = distance(_text.begin(), i);

    if (i > _gapEnd) {
        p -= (_gapEnd - _gapStart);
    }

    return p;
}

template<typename T>
void std::swap(Buffer<T>& lhs, Buffer<T>& rhs) {
    if (lhs != rhs) {
        lhs._text.swap(rhs._text);
        std::swap(lhs._point, rhs._point);
        std::swap(lhs._gapStart, rhs._gapStart);
        std::swap(lhs._gapEnd, rhs._gapEnd);
    }
}

template<typename T>
BufferIterator<T>::BufferIterator() : _b{nullptr}, _i{nullptr} {
}

template<typename T>
BufferIterator<T>::BufferIterator(Buffer<T>& b) : _b{b} {
    if (b._gapStart == b._text.begin() && !_b.empty()) {
        _i = b._gapEnd;
    } else {
        _i = b._text.begin();
    }
}

template<typename T>
BufferIterator<T>::BufferIterator(const BufferIterator<T>& that) : _b(that._b),
_i{that._i} {
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator=(const BufferIterator<T>& that) {
    if (this != &that) {
        this->_b = that._b;
        this->_i = that._i;
    }
    return *this;
}

template<typename T>
bool BufferIterator<T>::operator==(const BufferIterator<T>& that) {
    return _i == that._i;
}

template<typename T>
bool BufferIterator<T>::operator!=(const BufferIterator<T>& that) {
    return !this->operator==(that);
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator+=(const difference_type& n) {
    auto count = n;

    // I don't like my code here.  The idea is a BufferIterator should
    // "skip over" the gap when incrementing or decrementing.  I feel like
    // I should be able to express it in terms of Buffer::userToGap or 
    // Buffer::gapToUser but I was unable to get that working correctly.

    if (count >= 0) {
        while (count--) {
            ++_i;
            if (_i == _b._gapStart) {
                _i += (_b._gapEnd - _b._gapStart);
            }
        }
    } else {
        while (count++) {
            --_i;
            if (_i == _b._gapEnd) {
                _i -= (_b._gapEnd - _b._gapStart);
            }
        }
    }

    return *this;
}

template<typename T>
BufferIterator<T> BufferIterator<T>::operator+(const difference_type& n) {
    return BufferIterator<T>(*this += n);
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator++() {
    this->operator+(1);
    return *this;
}

template<typename T>
BufferIterator<T> BufferIterator<T>::operator++(int) {
    BufferIterator<T> tmp(*this);
    operator++();
    return tmp;
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator-=(const difference_type& n) {
    return *this += -n;
}

template<typename T>
    BufferIterator<T> BufferIterator<T>::operator-(const difference_type& n) {
        return BufferIterator<T>(*this - n);
    }

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator--() {
    this->operator-(1);
    return *this;
}

template<typename T>
const BufferIterator<T>& BufferIterator<T>::operator--(int) {
    BufferIterator<T> tmp(*this);
    operator--();
    return tmp;
}

template<typename T>
typename BufferIterator<T>::reference BufferIterator<T>::operator*() const {
    return *_i;
}

template<typename T>
typename BufferIterator<T>::pointer BufferIterator<T>::operator->() const {
    return _i;
}

template<typename T>
typename BufferIterator<T>::reference BufferIterator<T>::operator[](
const difference_type& n) const {
    return *(_i + n);
}

template<typename T>
bool std::operator<(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs) {
    return lhs._i < rhs._i;
}

template<typename T>
bool std::operator>(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs){
    return lhs._i > rhs._i;
}

template<typename T>
bool std::operator<=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs) {
    return !operator>(lhs, rhs);
}

template<typename T>
bool std::operator>=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs) {
    return !operator<(lhs, rhs);
}

template<typename T>
typename BufferIterator<T>::difference_type std::operator+(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs) {
    return lhs._i + rhs._i;
}

template<typename T>
typename BufferIterator<T>::difference_type std::operator-(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs) {
    return lhs._i - rhs._i;
}

template<typename T>
void std::swap(BufferIterator<T>& lhs, BufferIterator<T>& rhs) {
    if (lhs != rhs) {
        lhs._b.swap(rhs._b);
        std::swap(lhs._i, rhs._i);
    }
}
\$\endgroup\$
15
  • \$\begingroup\$ @Incomputable If you believe that the code is obviously broken, then vote to close. Otherwise, please write an answer (even if it is short) rather than answering in comments. \$\endgroup\$ Nov 2, 2017 at 22:37
  • \$\begingroup\$ @Incomputable Can you clarify? g++ 6.0 with -std=c++14 -Wall -Wextra -pedantic didn't warn of anything and the code does work. \$\endgroup\$
    – Jaldhar
    Nov 2, 2017 at 22:41
  • \$\begingroup\$ @Jaldhar, have you tried 1 < translation units (e.g. cppfiles in one compilation)? linker should complain. \$\endgroup\$ Nov 2, 2017 at 22:42
  • \$\begingroup\$ @200_success, I’m not 100% confident, as I never did define functions outside of class definition. If I happen to e correct, I’ll make it an answer. \$\endgroup\$ Nov 2, 2017 at 22:45
  • \$\begingroup\$ As far as I could dig, it seems like compilers mark them inline, but standard doesn’t require that. Sorry for the nitpicking. \$\endgroup\$ Nov 2, 2017 at 22:51

1 Answer 1

3
\$\begingroup\$

Implementation

  • BUFFER could be a defaulted template parameter. This allows for specifying different containers for storage.
  • Any specific reason why Buffer<T>::operator[](difference_type) takes a difference_type instead of a size_type parameter?
  • Buffer<T>::pointSet(BUFFER::iterator) takes an iterator of a private member - but Buffer<T> provides no publicly accessible member function which would return one.
  • Buffer<T>::cbegin() and Buffer<T>::cend() are declared to return a BufferIterator<const T>, but would return a BufferIterator<T> instead.
  • The const_cast<const Buffer<T>&> in Buffer<T>::cbegin() and Buffer<T>::cend() is weird. The called Buffer<T>::begin() and Buffer<T>::end() aren't marked const, so calling them from a const Buffer<T>& isn't possible anyways.
  • The BufferIterator<T> constructor should probably accept a const Buffer<T>& instead of a non-const reference.
  • Buffer<T>::gapToUser() reports incorrectly if p > _gapStart && p <= _gapEnd.
  • BufferIterator<T>::operator=(const BufferIterator<T>&): References (this->b_) cannot be reseated.
  • The comparison operators of BufferIterator<T> don't check whether the underlying Buffer<T> object is the same.
  • std::swap(BufferIterator<T>&, BufferIterator<T>&) doesn't check correctly for referential equality (lhs != rhs instead of &lhs != &rhs).
  • std::swap(BufferIterator<T>&, BufferIterator<T>&): I don't think it's intended to swap the contents of rhs.b_ and lhs.b_. Did you want to exchange the references instead?
  • Rule of 5 violation: You provide custom copy constructors and copy assignment operators for Buffer<T> and BufferIterator<T>, so you should also provide custom move constructors, move assignment operators and possibly destructors.
  • Many member functions should be marked const.

Naming

Many variable have very non-descriptive names. These could be improved for better readability (what tells you more: b_ or buffer_?).


EDIT: To respond to some of the comments.

  • cbegin() and cend(): The easiest and most correct way is to use overloads with const member functions. This requires BufferIterator<T>s constructor to take a const Buffer<T>& instead (shouldn't be a problem, as it doesn't change that buffer through the reference).

    template<typename T>
    class Buffer<T> {
        /* skipping stuff */
    
        // keep non-const begin and end
        iterator begin() { return iterator{*this}; }
        iterator end() { return iterator{*this}; }
    
        // add const overloads
        const_iterator begin() const { return const_iterator{*this}; }
        const_iterator end() const { return const_iterator{*this}; }
    
        // make cbegin and cend const, forward to const version of begin and end
        // This forwards to the right overloads, since this is const
        const_iterator cbegin() const { return begin(); }
        const_iterator cend() const { return end(); }
    };
    
  • "Reseating a reference" is another way to say "change the object a reference is referring to". This isn't allowed! References are seated (= set) once when they are initialized, and cannot legally be changed afterwards. If there is a need to change the pointed to object, pointers must be used instead.

  • I have been thinking about operator+(const BufferIterator<T>&, const BufferIterator<T>&) and operator-(const BufferIterator<T>&, const BufferIterator<T>&) a bit more, and found that there is a use case (basically: determining std::distance(it1, it2) more easily), so keep them (I don't know how I overlooked that one when I wrote the original answer, sorry).
  • Regarding move constructor and move assignment operator: Since you have a user defined copy constructor, the compiler won't generate a move constructor by default. Even if it were to generate the default move constructor by using Buffer(Buffer<T>&&) = default;, it wouldn't move any members that don't have a trivial move constructor themselves (e.g. Buffer<T>::_text).

    template<typename T>
    Buffer<T>::Buffer(Buffer<T>&& that) noexcept : _text(std::move(that._text)),
    _point{that._point}, _gapStart{std::move(that._gapStart)}, _gapEnd{std::move(that._gapEnd)} {
    }
    
    template<typename T>
    Buffer<T>& Buffer<T>::operator=(Buffer<T>&& that) noexcept {
        if (this != &that) {
            this->_text = std::move(that._text);
            this->_point = that._point;
            this->_gapStart = std::move(that._gapStart);
            this->_gapEnd = std::move(that._gapEnd);
        }
        return *this;
    }
    
\$\endgroup\$
9
  • \$\begingroup\$ BUFFER could be a defaulted template parameter. I did this and also BUFFERSIZE for good measure. I renamed BUFFER to Container and BUFFERSIZE to N to match the style of the STL. \$\endgroup\$
    – Jaldhar
    Nov 3, 2017 at 21:44
  • \$\begingroup\$ why Buffer<T>::operator[](difference_type) takes a difference_type I thought it was required but I now see that it should be size_type so I changed it. \$\endgroup\$
    – Jaldhar
    Nov 3, 2017 at 21:50
  • \$\begingroup\$ Buffer<T>::pointSet(BUFFER::iterator) takes an iterator of a private member Yeah it should be a private method. \$\endgroup\$
    – Jaldhar
    Nov 3, 2017 at 21:51
  • \$\begingroup\$ cbegin() and cend() What is the proper way to implement this with a minimum amount of code duplication? \$\endgroup\$
    – Jaldhar
    Nov 3, 2017 at 21:53
  • \$\begingroup\$ BufferIterator<T>::operator=(const BufferIterator<T>&): References (this->b) cannot be reseated._ I'm sorry I don't understand what reseated means. \$\endgroup\$
    – Jaldhar
    Nov 3, 2017 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.