Andrew T. Duchowski--CPSC 102

CPSC 102-001 Computer Science II
(Advanced C Programming)
Fall 2010
09:05-09:55MW Daniel 415
Lab 13

Objectives:

To implement and exercise the templated list_t class iterators

What to hand in:

A tar.gz archive of your lab13/ directory, including:

A README file containing
1. Course id--section no
2. Name
3. Assignment description
4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
5. Lessons learned, identified interesting features of your program
6. Any special usage instructions
Makefile
source code (.h headers and .cpp source)
~~object code~~ (do a make clean before tar)

How to hand in:

See sendlab notes

Description:

Following lab2, lab8, and class notes,

convert the list_t class in the list.h interface to a doubly-linked list, with link_t *head and link_t *tail nodes,
equip the class with const_iterator and iterator iterators, and

provide the following class member functions:

  // iterator functions
  const_iterator        begin() const;
  const_iterator        end() const;
  iterator              begin();
  iterator              end();

  const_iterator        insert(const_iterator,const T&);
  iterator              erase(iterator);
  iterator              pop_front();

  // members
  bool                  empty() const;

  void                  clear();

noting that all but insert and erase are very short and can be defined in-line in the interface

Your code should be such that the following main() routine works unaltered:

int main(int argc, char *argv[])
{
        list_t<data_t *>                        list;   // list
        list_t<data_t *>                        rlist;  // reverse list
        list_t<data_t *>::const_iterator        citr;   // list iterator
        list_t<data_t *>::iterator              litr;   // list iterator
        data_t                                  *data=NULL;
        std::string                             name;
        int                                     num;

  std::cout << "*** printing empty list with const iterator" << std::endl;
  for(citr = list.begin(); citr != list.end(); ++citr)
    std::cout << *citr;

  // read input file consisting of names and id codes adding entities to list
  std::cout << "*** reading input...";
  citr = rlist.begin();
  while(!std::cin.eof()) {
    std::cin >> name >> num;
    if(std::cin.good()) citr = rlist.insert(citr,new data_t(name,num));
    if(std::cin.good())         list.insert(list.end(),new data_t(name,num));
  }
  std::cout << "done." << std::endl;

  // now play it back
  std::cout << "*** printing reverse list with const iterator" << std::endl;
  for(citr = rlist.begin(); citr != rlist.end(); ++citr)
    std::cout << *citr;

  std::cout << "*** printing list with const iterator" << std::endl;
  for(citr = list.begin(); citr != list.end(); ++citr)
    std::cout << *citr;

  std::cout << "*** printing list with iterator" << std::endl;
  for(litr = list.begin(); litr != list.end(); ++litr)
    std::cout << *litr;

  std::cout << "*** deleting first off list" << std::endl;
  list.pop_front();

  std::cout << "*** printing list with const iterator" << std::endl;
  for(citr = list.begin(); citr != list.end(); ++citr)
    std::cout << *citr;

  // now free all list control structures and the data_t structures as well
  std::cout << "*** deleting list" << std::endl;
  list.clear();

  std::cout << "*** printing list with const iterator" << std::endl;
  for(citr = list.begin(); citr != list.end(); ++citr)
    std::cout << *citr;

  // see if we can delete an empty list
  std::cout << "*** deleting list again" << std::endl;
  list.clear();

  std::cout << "*** printing list with const iterator" << std::endl;
  for(citr = list.begin(); citr != list.end(); ++citr)
    std::cout << *citr;

  // prove we survived
  std::cout << "*** done" << std::endl;
}

Sample input (entered by user):
Mike 1234 Bill 3212 Sarah 1321 John 1021 Carol 3223 Debbie 4231 Gary 9321 Ann 1231 Dale 7231 Lynn 8133 Patty 9999

Sample output:
*** printing empty list with const iterator *** reading input...done. *** printing reverse list with const iterator Patty 9999 Lynn 8133 Dale 7231 Ann 1231 Gary 9321 Debbie 4231 Carol 3223 John 1021 Sarah 1321 Bill 3212 Mike 1234 *** printing list with const iterator Mike 1234 Bill 3212 Sarah 1321 John 1021 Carol 3223 Debbie 4231 Gary 9321 Ann 1231 Dale 7231 Lynn 8133 Patty 9999 *** printing list with iterator Mike 1234 Bill 3212 Sarah 1321 John 1021 Carol 3223 Debbie 4231 Gary 9321 Ann 1231 Dale 7231 Lynn 8133 Patty 9999 *** deleting first off list *** printing list with const iterator Bill 3212 Sarah 1321 John 1021 Carol 3223 Debbie 4231 Gary 9321 Ann 1231 Dale 7231 Lynn 8133 Patty 9999 *** deleting list *** printing list with const iterator *** deleting list again *** printing list with const iterator *** done