    001: #include <string>
    002: #include <iostream>
    003: #include <cassert>
    004:
    005: using namespace std;
    006:
    007: /* forward declarations */
    008: template<typename T> class List;
    009: template<typename T> class Iterator;
    010:
    011: /**
    012:    A class to hold the nodes of the linked list.
    013: */
    014: template<typename T>
    015: class Node
    016: {
    017: public:
    018:    /**
    019:       Constructs a node for a given data value.
    020:       @param s the data to store in this node
    021:    */
    022:    Node(T s);
    023: private:
    024:    T data;
    025:    Node<T>* previous;
    026:    Node<T>* next;
    027: friend class List<T>;
    028: friend class Iterator<T>;
    029: };
    030:
    031: /**
    032:    An iterator denotes a position in the list or
    033:    past the end of the list.
    034: */
    035: template<typename T>
    036: class Iterator
    037: {
    038: public:
    039:    /**
    040:       Constructs an iterator that is not attached to any list.
    041:    */
    042:    Iterator();
    043:    /**
    044:        Looks up the value at a position.
    045:        @return the value of the Node to which the iterator
    046:        points
    047:    */
    048:    T operator*() const;
    049:    /**
    050:       Advances the iterator to the next position.
    051:    */
    052:    void operator++(int dummy);
    053:    /**
    054:       Moves the iterator to the previous position.
    055:    */
    056:    void operator--(int dummy);
    057:    /**
    058:       Compares two iterators.
    059:       @param b the iterator to compare with this iterator
    060:       @return true if this iterator and b are equal
    061:    */
    062:    bool operator==(Iterator<T> b) const;
    063:    /**
    064:       Compares two iterators.
    065:       @param b the iterator to compare with this iterator
    066:       @return true if this iterator and b are not equal
    067:    */
    068:    bool operator!=(Iterator<T> b) const;
    069: private:
    070:    Node<T>* position;
    071:    Node<T>* last;
    072: friend class List<T>;
    073: };
    074:
    075: /**
    076:    A linked list of values of a given type.
    077:    @param T the type of the list values
    078: */
    079: template<typename T>
    080: class List
    081: {
    082: public:
    083:    /**
    084:       Constructs an empty list.
    085:    */
    086:    List();
    087:    /**
    088:       Constructs a list as a copy of another list.
    089:       @param b the list to copy
    090:    */
    091:    List(const List<T>& b);
    092:    /**
    093:       Deletes all nodes of this list.
    094:    */
    095:    ~List();
    096:    /**
    097:       Assigns another list to this list.
    098:       @param b the list to assign
    099:       @return a reference to this list
    100:    */
    101:    List<T>& operator=(const List<T>& b);
    102:
    103:    /**
    104:       Appends an element to the list.
    105:       @param s the value to append
    106:    */
    107:    void push_back(T s);
    108:    /**
    109:       Inserts an element into the list.
    110:       @param iter the position before which to insert
    111:       @param s the value to append
    112:    */
    113:    void insert(Iterator<T> iter, T s);
    114:    /**
    115:       Removes an element from the list.
    116:       @param i the position to remove
    117:       @return an iterator pointing to the element after the
    118:       erased element
    119:    */
    120:    Iterator<T> erase(Iterator<T> i);
    121:    /**
    122:       Gets the beginning position of the list.
    123:       @return an iterator pointing to the beginning of the list
    124:    */
    125:    Iterator<T> begin();
    126:    /**
    127:       Gets the past-the-end position of the list.
    128:       @return an iterator pointing past the end of the list
    129:    */
    130:    Iterator<T> end();
    131:
    132: private:
    133:    /**
    134:       Copies another list to this list.
    135:       @param b the list to copy
    136:    */
    137:    void copy(const List<T>& b);
    138:    /**
    139:       Deletes all nodes of this list.
    140:    */
    141:    void free();
    142:
    143:    Node<T>* first;
    144:    Node<T>* last;
    145: };
    146:
    147: template<typename T>
    148: List<T>::List()
    149: {
    150:    first = NULL;
    151:    last = NULL;
    152: }
    153:
    154: template<typename T>
    155: List<T>::~List()
    156: {
    157:    free();
    158: }
    159:
    160: template<typename T>
    161: List<T>::List(const List<T>& b)
    162: {
    163:    first = NULL;
    164:    last = NULL;
    165:    copy(b);
    166: }
    167:
    168: template<typename T>
    169: List<T>& List<T>::operator=(const List<T>& b)
    170: {
    171:    if (this != &b)
    172:    {
    173:       free();
    174:       copy(b);
    175:    }
    176:    return *this;
    177: }
    178:
    179:
    180: template<typename T>
    181: void List<T>::push_back(T s)
    182: {
    183:    Node<T>* newnode = new Node<T>(s);
    184:    if (last == NULL) /* list is empty */
    185:    {
    186:       first = newnode;
    187:       last = newnode;
    188:    }
    189:    else
    190:    {
    191:       newnode->previous = last;
    192:       last->next = newnode;
    193:       last = newnode;
    194:    }
    195: }
    196:
    197: template<typename T>
    198: void List<T>::insert(Iterator<T> iter, T s)
    199: {
    200:    if (iter.position == NULL)
    201:    {
    202:       push_back(s);
    203:       return;
    204:    }
    205:
    206:    Node<T>* after = iter.position;
    207:    Node<T>* before = after->previous;
    208:    Node<T>* newnode = new Node<T>(s);
    209:    newnode->previous = before;
    210:    newnode->next = after;
    211:    after->previous = newnode;
    212:    if (before == NULL) /* insert at beginning */
    213:       first = newnode;
    214:    else
    215:       before->next = newnode;
    216: }
    217:
    218: template<typename T>
    219: Iterator<T> List<T>::erase(Iterator<T> i)
    220: {
    221:    Iterator<T> iter = i;
    222:    assert(iter.position != NULL);
    223:    Node<T>* remove = iter.position;
    224:    Node<T>* before = remove->previous;
    225:    Node<T>* after = remove->next;
    226:    if (remove == first)
    227:       first = after;
    228:    else
    229:       before->next = after;
    230:    if (remove == last)
    231:       last = before;
    232:    else
    233:       after->previous = before;
    234:    iter.position = after;
    235:    delete remove;
    236:    return iter;
    237: }
    238:
    239: template<typename T>
    240: Iterator<T> List<T>::begin()
    241: {
    242:    Iterator<T> iter;
    243:    iter.position = first;
    244:    iter.last = last;
    245:    return iter;
    246: }
    247:
    248: template<typename T>
    249: Iterator<T> List<T>::end()
    250: {
    251:    Iterator<T> iter;
    252:    iter.position = NULL;
    253:    iter.last = last;
    254:    return iter;
    255: }
    256:
    257: template<typename T>
    258: Iterator<T>::Iterator()
    259: {
    260:    position = NULL;
    261:    last = NULL;
    262: }
    263:
    264: template<typename T>
    265: T Iterator<T>::operator*() const
    266: {
    267:    assert(position != NULL);
    268:    return position->data;
    269: }
    270:
    271: template<typename T>
    272: void Iterator<T>::operator++(int dummy)
    273: {
    274:    assert(position != NULL);
    275:    position = position->next;
    276: }
    277:
    278: template<typename T>
    279: void Iterator<T>::operator--(int dummy)
    280: {
    281:    if (position == NULL)
    282:       position = last;
    283:    else
    284:       position = position->previous;
    285:    assert(position != NULL);
    286: }
    287:
    288: template<typename T>
    289: bool Iterator<T>::operator==(Iterator<T> b) const
    290: {
    291:    return position == b.position;
    292: }
    293:
    294: template<typename T>
    295: bool Iterator<T>::operator!=(Iterator<T> b) const
    296: {
    297:    return position != b.position;
    298: }
    299:
    300: template<typename T>
    301: Node<T>::Node(T s)
    302: {
    303:    data = s;
    304:    previous = NULL;
    305:    next = NULL;
    306: }
    307:
    308: template<typename T>
    309: void List<T>::copy(const List<T>& b)
    310: {
    311:    for (Iterator<T> p = b.begin(); p != b.end(); p++)
    312:       push_back(*p);
    313: }
    314:
    315: template<typename T>
    316: void List<T>::free()
    317: {
    318:    while (begin() != end())
    319:       erase(begin());
    320: }
    321:
    322: int main()
    323: {
    324:    List<string> staff;
    325:
    326:    staff.push_back("Cracker, Carl");
    327:    staff.push_back("Hacker, Harry");
    328:    staff.push_back("Lam, Larry");
    329:    staff.push_back("Sandman, Susan");
    330:
    331:    /* add a value in fourth place */
    332:
    333:    Iterator<string> pos;
    334:    pos = staff.begin();
    335:    pos++;
    336:    pos++;
    337:    pos++;
    338:
    339:    staff.insert(pos, "Reindeer, Rudolf");
    340:
    341:    /* remove the value in second place */
    342:
    343:    pos = staff.begin();
    344:    pos++;
    345:
    346:    staff.erase(pos);
    347:
    348:    /* print all values */
    349:
    350:    for (pos = staff.begin(); pos != staff.end(); pos++)
    351:       cout << *pos << "\n";
    352:
    353:    return 0;
    354: }