Abstract data type

Abstract data type is type defined by its behaviour, not its representation.

A data type is abstract if it exposes in its public interface only high-level operations and hides all low-level implementation details.

1. table[index2] return *(grid+index2), an object of Row (not a pointer).
2. row[index1] return *(array+index1), an object of TableElem.
3. To allow assignment on LHS, object return by reference (Row& and TabelElem&).

Implenting stack with fixed size array need to guard overflow and underflow.

template <class StackElem>
void Stack<StackElem>::Push(StackElem e)
{
  if (currentPointer_ > stackTopPointer_)
    printf("Error: stack overflow.");
  else
    *currentPointer_++ = e;
}

template <class StackElem>
StackElem Stack<StackElem>::Pop()
{
  if (currentPointer_ <= stackBottomPointer_)
    printf("Error: stack underflow.");
  else
    return *(--currentPointer_);
}

// Singly integer linked list

class ilist_item {
public:
  ilist_item(int value, ilist_item *item_to_link_to = NULL)
    : _value(value)
  {
    if (item == NULL)
      _next = NULL;
    else {
      _next = item->_next;
      item->_next = this;
    }
  }

  int value() { return _value; }
  ilist_item* next() { return _next; }
  void next(ilist_item *link) { _next = link; }
  void value(int new_value) { _value = new_value; }

private:
  int _value;
  ilist_item *_next;
};

class ilist {
public:
  ilist() : _at_front(NULL), _at_end(NULL), _size(NULL), _current(NULL) {}
  ilist(const ilist&);
  ilist& operator=(const ilist&);
  ~list() { remove_all(); }

  int size() { return _size; }

  void insert_front(int value);
  void insert_end(int value);
  void insert(ilist_item *ptr, int value);

  void remove_front();
  int remove(int value);
  void remove_all();

  void display(ostream &os = cout);

  ilist_item* find(int value);

  void concat(const ilist &il);
  void reverse();

  // support iteration
  // for (ilist_item *iter=mylist.init_iter(); iter!=NULL; iter=mylist.next_iter())
  //   do_something(iter->value());
  ilist_item* init_iter(ilist_item *it = NULL);
  ilist_item* next_iter();

protected:
  ilist_item *_at_front;
  ilist_item *_at_end;
  int _size;

  ilist_item *_current;

  // encapsulate tightly coupling of _size and size() in other member function
  void bump_up_size() { ++_size; }
  void bump_down_size() { --_size; }

  void insert_all(const ilist &rhs);
};

void ilist::insert_all(const ilist &rhs)
{
  ilist_item *pt = rhs._at_front;
  while (pt != NULL) {
    insert_end(pt->value());
    pt = pt->next();
  }
}
inline ilist::ilist(const ilist &rhs)
  : _at_front(NULL), _at_end(NULL)
{
 insert_all(rhs);
}
inline ilist& ilist::operator=(const ilist &rhs)
{
  if (this != &rhs) {
    remove_all();
    insert_all(rhs);
  }
  return *this;
}

inline void ilist::insert_front(int value)
{
  ilist_item *ptr = new ilist_item(value);
  if (_at_front == NULL)
    _at_front = _at_end = ptr;
  else {
    ptr->next(_at_front);
    _at_front = ptr;
  }
  bump_up_size();
}
inline void ilist::insert_end(int value)
{
  if (_at_end == NULL)
    _at_end = _at_front = new ilist_item(value);
  else
    _at_end = new ilist_item(value, _at_end);
  bump_up_size();
}
inline void ilist::insert(ilist_item *ptr, int value)
{
  if (ptr == NULL)
    insert_front(value);
  else {
    bump_up_size();
    new ilist_item(value, ptr);
  }
}

inline void ilist::remove_front()
{
  if (_at_front != NULL) {
    ilist_item *ptr = _at_front;
    _at_front = _at_front->next();
    // don't want current to point to a deleted item
    if (_current == ptr)
      _current = _at_front;
    bump_down_size();
    delete ptr;
  }
}
int ilist::remove(int value)
{
  ilist_item *plist = _at_front;
  int elem_cnt = 0;
  while (plist!=NULL && plist->value()==value)
  {
    plist = plist->next();
    remove_front();
    ++elem_cnt;
  }
  if (plist == NULL)
    return elem_cnt;
  ilist_item *prev = plist;
  plist = plist->next();
  while (plist != NULL)
  {
    if (plist->value() == value)
    {
      prev->next(plist->next());
      if (_current == plist)
        _current = prev->next();
      delete plist;
      ++elem_cnt;
      bump_down_size();
      plist = prev->next();
      if (plist == NULL)
      {
        _at_end = prev;
        return elem_cnt;
      }
    }
    else
    {
      prev = plist;
      plist = plist->next();
    }
  }
  return elem_cnt;
}
void ilist::remove_all()
{
  while (_at_front != NULL)
    remove_front();
  _size = NULL;
  _at_front = _at_end = NULL;
}

void ilist::display(ostream &os)
{
  os << "\n( " << _size << " )( ";
  ilist_item *ptr = _at_front;
  while (ptr != NULL) {
    os << ptr->value() << " ";
    ptr = ptr->next();
  }
  os << ")\n";
}

ilist_item* ilist::find(int value)
{
  ilist_item *ptr = _at_front;
  while (ptr != NULL)
  {
    if (ptr->value() == value)
      break;
    ptr = ptr->next();
  }
  return ptr;
}

void ilist::concat(const ilist &il)
{
  ilist_item *ptr = il._at_front;
  while (ptr != NULL) {
    insert_end(ptr->value());
    ptr = ptr->next();
  }
}

void ilist::reverse()
{
  ilist_item *ptr = _at_front;
  ilist_item *prev = NULL;
  _at_front = _at_end;
  _at_end = ptr;
  while (ptr != _at_front)
  {
    ilist_item *tmp = ptr->next();
    ptr->next(prev);
    prev = ptr;
    ptr = tmp;
  }
  _at_front->next(prev);
}

inline ilist_item* ilist::init_iter(ilist_item *it)
{
  return _current = it ? it : _at_front;
}
inline ilist_item* ilist::next_iter()
{
  ilist_item *next = _current
                     ? _current = _current->next()
                     : _current;
  return next;
}

The simplest implementation of size() is to iterate across the list, returning a count of the elements traversed. A somewhat more complex implementation stores the size of the list as a data member, if user query of size() is likely to be frequent and must therefore necessarily be fast. The additional complexity is the need to update the member with each element insertion and deletion.

Iterator is slightly more than a pointer, because it remembers the current item of the iteration, is able to return a next item and is able to recognize the completion of an iteration. init_iter() by default initializes the iterator to _at_front. Optionally, the user can pass in an ilist_item pointer with which to start the iteration. next_iter() returns the next item in the list, or NULL if the iteration is complete.

Support for iteration could be problematic if the item pointed to by _current is removed. One solution is to modify remove_front() and remove() to test whether _current addresses the item being removed. If it does, _current is advanced to address the next item (or no item if the item removed is the last on the list). If all the items are removed, then _current is set to point to no item.

If an item is inserted in front of the item _current addresses, do not modify _current. To resynchronize the iteration, the user needs to invoke init_iter(). On the other hand, when initialize or copy one ilist class object with another, _current is not copied but rather is reset to address no object.