    001: #include <string>
    002: #include <iostream>
    003: #include <cassert>
    004:
    005: using namespace std;
    006:
    007: class List;
    008: class Iterator;
    009:
    010: class Node
    011: {
    012: public:
    013:    /*
    014:       Constructs a node with a given data value.
    015:       @param s the data to store in this node
    016:    */
    017:    Node(string s);
    018: private:
    019:    string data;
    020:    Node* previous;
    021:    Node* next;
    022: friend class List;
    023: friend class Iterator;
    024: };
    025:
    026: class List
    027: {
    028: public:
    029:    /**
    030:       Constructs an empty list;
    031:    */
    032:    List();
    033:    /**
    034:       Appends an element to the list.
    035:       @param s the value to append
    036:    */
    037:    void push_back(string s);
    038:    /**
    039:       Inserts an element into the list.
    040:       @param iter the position before which to insert
    041:       @param s the value to append
    042:    */
    043:    void insert(Iterator iter, string s);
    044:    /**
    045:       Removes an element from the list.
    046:       @param i the position to remove
    047:       @return an iterator pointing to the element after the
    048:       erased element
    049:    */
    050:    Iterator erase(Iterator i);
    051:    /**
    052:       Gets the beginning position of the list.
    053:       @return an iterator pointing to the beginning of the list
    054:    */
    055:    Iterator begin();
    056:    /**
    057:       Gets the past-the-end position of the list.
    058:       @return an iterator pointing past the end of the list
    059:    */
    060:    Iterator end();
    061: private:
    062:    Node* first;
    063:    Node* last;
    064: };
    065:
    066: class Iterator
    067: {
    068: public:
    069:    /**
    070:       Constructs an iterator that does not point into any list.
    071:    */
    072:    Iterator();
    073:    /**
    074:       Looks up the value at a position.
    075:       @return the value of the node to which the iterator points
    076:    */
    077:    string get() const;
    078:    /**
    079:       Advances the iterator to the next node.
    080:    */
    081:    void next();
    082:    /**
    083:       Moves the iterator to the previous node.
    084:    */
    085:    void previous();
    086:    /**
    087:       Compares two iterators
    088:       @param b the iterator to compare with this iterator
    089:       @return true if this iterator and b are equal
    090:    */
    091:    bool equals(Iterator b) const;
    092: private:
    093:    Node* position;
    094:    Node* last;
    095: friend class List;
    096: };
    097:
    098: Node::Node(string s)
    099: {
    100:    data = s;
    101:    previous = NULL;
    102:    next = NULL;
    103: }
    104:
    105: List::List()
    106: {
    107:    first = NULL;
    108:    last = NULL;
    109: }
    110:
    111: void List::push_back(string s)
    112: {
    113:    Node* newnode = new Node(s);
    114:    if (last == NULL) /* list is empty */
    115:    {
    116:       first = newnode;
    117:       last = newnode;
    118:    }
    119:    else
    120:    {
    121:       newnode->previous = last;
    122:       last->next = newnode;
    123:       last = newnode;
    124:    }
    125: }
    126:
    127: void List::insert(Iterator iter, string s)
    128: {
    129:    if (iter.position == NULL)
    130:    {
    131:       push_back(s);
    132:       return;
    133:    }
    134:
    135:    Node* after = iter.position;
    136:    Node* before = after->previous;
    137:    Node* newnode = new Node(s);
    138:    newnode->previous = before;
    139:    newnode->next = after;
    140:    after->previous = newnode;
    141:    if (before == NULL) /* insert at beginning */
    142:       first = newnode;
    143:    else
    144:       before->next = newnode;
    145: }
    146:
    147: Iterator List::erase(Iterator i)
    148: {
    149:    Iterator iter = i;
    150:    assert(iter.position != NULL);
    151:    Node* remove = iter.position;
    152:    Node* before = remove->previous;
    153:    Node* after = remove->next;
    154:    if (remove == first)
    155:       first = after;
    156:    else
    157:       before->next = after;
    158:    if (remove == last)
    159:       last = before;
    160:    else
    161:       after->previous = before;
    162:    iter.position = after;
    163:    delete remove;
    164:    return iter;
    165: }
    166:
    167: Iterator List::begin()
    168: {
    169:    Iterator iter;
    170:    iter.position = first;
    171:    iter.last = last;
    172:    return iter;
    173: }
    174:
    175: Iterator List::end()
    176: {
    177:    Iterator iter;
    178:    iter.position = NULL;
    179:    iter.last = last;
    180:    return iter;
    181: }
    182:
    183: Iterator::Iterator()
    184: {
    185:    position = NULL;
    186:    last = NULL;
    187: }
    188:
    189: string Iterator::get() const
    190: {
    191:    assert(position != NULL);
    192:    return position->data;
    193: }
    194:
    195: void Iterator::next()
    196: {
    197:    assert(position != NULL);
    198:    position = position->next;
    199: }
    200:
    201: void Iterator::previous()
    202: {
    203:    if (position == NULL)
    204:       position = last;
    205:    else
    206:       position = position->previous;
    207:    assert(position != NULL);
    208: }
    209:
    210: bool Iterator::equals(Iterator b) const
    211: {
    212:    return position == b.position;
    213: }
    214:
    215: int main()
    216: {
    217:    List staff;
    218:
    219:    staff.push_back("Cracker, Carl");
    220:    staff.push_back("Hacker, Harry");
    221:    staff.push_back("Lam, Larry");
    222:    staff.push_back("Sandman, Susan");
    223:
    224:    /* add a value in fourth place */
    225:
    226:    Iterator pos;
    227:    pos = staff.begin();
    228:    pos.next();
    229:    pos.next();
    230:    pos.next();
    231:
    232:    staff.insert(pos, "Reindeer, Rudolf");
    233:
    234:    /* remove the value in second place */
    235:
    236:    pos = staff.begin();
    237:    pos.next();
    238:
    239:    staff.erase(pos);
    240:
    241:    /* print all values */
    242:
    243:    for (pos = staff.begin(); !pos.equals(staff.end()); pos.next())
    244:       cout << pos.get() << "\n";
    245:
    246:    return 0;
    247: }
    248: