containers/safe_iterator.hpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#ifndef STLPLUS_SAFE_ITERATOR
#define STLPLUS_SAFE_ITERATOR
////////////////////////////////////////////////////////////////////////////////
 
//   Author:    Andy Rushton
//   Copyright: (c) Southampton University 1999-2004
//              (c) Andy Rushton           2004 onwards
//   License:   BSD License, see ../docs/license.html
 
//   The STLplus safe_iterator superclasses. This implements the STLplus safe
//   iterator principles. Data structures can then be built using subclasses
//   of safe_iterator for their iterator objects and they will inherit the
//   safe iterator behaviour.
 
//   The data structure must contain a master iterator for each node in the
//   structure. When an iterator is returned to the user, it must be created
//   by the master iterator. When a node is removed from the data structure,
//   its master iterator is destroyed. This sets all iterators pointing to the
//   master iterator to end iterators.
 
////////////////////////////////////////////////////////////////////////////////
#include "containers_fixes.hpp"
#include "exceptions.hpp"
 
namespace stlplus
{
 
  ////////////////////////////////////////////////////////////////////////////////
  // internals
 
  template<typename O, typename N>
  class safe_iterator_body;
 
  template<typename O, typename N>
  class safe_iterator;
 
  ////////////////////////////////////////////////////////////////////////////////
  // Master Iterator
  // Create one of these in each node in the data structure
  // Generate iterators by obtaining a safe-iterator object from the master iterator
  ////////////////////////////////////////////////////////////////////////////////
 
  template<typename O, typename N>
  class master_iterator
  {
  public:
 
    // construct a valid master iterator connected to the node
    master_iterator(const O* owner, N* node) ;
 
    // destructor - disconnects all iterators from the node
    ~master_iterator(void) ;
 
    // dereference
    N* node(void) const ;
    const O* owner(void) const ;
 
    // when you move a node from one owner to another, call this on the node's master iterator
    // this effectively moves all other iterators to the node so that they are owned by the new owner too
    void change_owner(const O* owner) ;
 
    friend class safe_iterator<O,N>;
  private:
    master_iterator(const master_iterator&) ;
    master_iterator& operator=(const master_iterator&) ;
    safe_iterator_body<O,N>* m_body;
  };
 
  ////////////////////////////////////////////////////////////////////////////////
  // Safe Iterator
  ////////////////////////////////////////////////////////////////////////////////
 
  template<typename O, typename N>
  class safe_iterator
  {
  public:
    // constructors
    // an iterator has three possible states: null, valid or end
    // null iterators are not owned, valid and end iterators are owned and can only be used on the owner data structure
    // constructors for each of theses states
 
    // construct a null iterator
    safe_iterator(void) ;
 
    // construct a valid iterator from the owner node's master iterator
    safe_iterator(const master_iterator<O,N>&) ;
 
    // construct an end iterator
    safe_iterator(const O* owner) ;
 
    // copy operators
 
    // copy constructor creates a safe iterator with the same properties as the source
    safe_iterator(const safe_iterator<O,N>&) ;
 
    // copy an iterator by assignment
    safe_iterator<O,N>& operator=(const safe_iterator<O,N>&) ;
 
    // destructor
    ~safe_iterator(void) ;
 
    // changing the state of an iterator, e.g. during traversal
 
    // reassignment to another node - used in increment/decrement operation
    void set(const master_iterator<O,N>&) ;
 
    // change to an end iterator - e.g. as a result of incrementing off the end
    void set_end(void) ;
 
    // change to a null iterator - i.e. one that does not belong to any object
    void set_null(void) ;
 
    // dereference operators to access the internal state
 
    // get the node that this iterator points to
    N* node(void) const ;
    // get the owner data structure
    const O* owner(void) const ;
 
    ////////////////////////////////////////////////////////////////////////////////
    // status tests
 
    // comparison
    bool equal(const safe_iterator<O,N>& right) const ;
    int compare(const safe_iterator<O,N>& right) const ;
 
    // a null iterator is one that has not been initialised with a value yet
    // i.e. you just declared it but didn't assign to it
    bool null(void) const ;
 
    // an end iterator is one that points to the end element of the list of nodes
    // in STL conventions this is one past the last valid element and must not be dereferenced
    bool end(void) const ;
 
    // a valid iterator is one that can be dereferenced
    // i.e. non-null and non-end
    bool valid(void) const ;
 
    // check ownership of an iterator
    bool owned_by(const O* owner) const;
 
    // check the rules for an iterator
 
    // assert the rules for a valid iterator
    // optionally also check that the iterator is owned by the owner
    // exceptions: wrong_object,null_dereference,end_dereference
    void assert_valid(const O* owner = 0) const ;
    // assert the rules for a non-null iterator - i.e. valid or end, values that occur in increment operations
    // optionally also check that the iterator is owned by the owner
    // exceptions: wrong_object,null_dereference
    void assert_non_null(const O* owner = 0) const ;
    // assert that this iterator is owned by this container
    // exceptions: wrong_object
    void assert_owner(const O* owner) const ;
 
    ////////////////////////////////////////////////////////////////////////////////
 
    friend class master_iterator<O,N>;
  private:
    safe_iterator_body<O,N>* m_body;
  };
 
  ////////////////////////////////////////////////////////////////////////////////
 
} // end namespace stlplus
 
#include "safe_iterator.tpp"
#endif