doubly_linked_list.h

Go to the documentation of this file.

#ifndef DOUBLY_LINKED_LIST_CLASS
#define DOUBLY_LINKED_LIST_CLASS
 
/*
*  Name   : doubly_linked_list
*  Author : Chris Koeritz
**
* Copyright (c) 1998-$now By Author.  This program is free software; you can
* redistribute it and/or modify it under the terms of the GNU General Public
* License as published by the Free Software Foundation; either version 2 of
* the License or (at your option) any later version.  This is online at:
*     http://www.fsf.org/copyleft/gpl.html
* Please send any updates to: fred@gruntose.com
*/
 
namespace nodes {
 
class node;  // forward.
 
 
//hmmm: is this class really for real?  it's doing all sorts of stuff with nodes, rather than with the list object itself.
// consider dropping the current implementation and providing more standard list operations, on an object that is actually using itself in its definition, rather than a different class (node).
// this would be easy to do if we just break down and define the dl list as a node itself.  then we have something to work with.
 
//current iterator implementation here is bunk.
 
 
class doubly_linked_list
{
public:
  doubly_linked_list();
 
  ~doubly_linked_list();
 
  int elements() const;
 
  bool empty() const;
 
 
  class iterator {
  public:
    iterator(const doubly_linked_list *mgr, node *start) : _cursor(start), _manager(mgr) {}
 
    void operator ++();  
    void operator --();  
    void operator ++(int) { ++(*this); }  
    void operator --(int) { --(*this); }  
 
  
    void next() { (*this)++; }  
    void previous() { (*this)--; }  
 
    bool operator ==(const iterator &to_compare) const;
 
    bool is_head() const;
 
    bool is_tail() const;
 
    void jump_head();  
    void jump_tail();  
 
    const node *observe();  
    node *access();  
 
  private:
    node *_cursor;  
    friend class doubly_linked_list;  
    const doubly_linked_list *_manager;  
  };
 
  iterator head() const { return iterator(this, _head); }
  iterator tail() const { return iterator(this, _tail); }
 
  int index(const iterator &it) const { return items_from_head(it); }
 
  bool set_index(iterator &to_set, int new_index);
 
  // storage and retrieval actions.
  // Note: all of these methods shift the iterator onto the next valid node
  // if it is positioned at the beginning or end of the list.
 
  void append(iterator &where, node *new_node);
 
  void insert(iterator &where, node *new_node);
 
  node *remove(iterator &where);
 
  void zap(iterator &where);
 
  void zap_all();
 
  // the following positioning functions could fail if the request is out of
  // bounds.  for example, forward cannot go beyond the end of the list.  in
  // such cases, false is returned and the list pointer is not moved.
 
  bool forward(iterator &where, int count);
 
  bool backward(iterator &where, int count);
 
  int items_from_head(const iterator &where) const;
 
  int items_from_tail(const iterator &where) const;
 
private:
  friend class iterator;
  node *_head;  
  node *_tail;  
 
  bool skip_or_ignore(iterator &where, int count);
 
  // not permitted.
  doubly_linked_list(const doubly_linked_list &);
  doubly_linked_list &operator =(const doubly_linked_list &);
};
 
} // namespace.
 
#endif