第二十七课再论智能指针（上）(代码片段)

  1 #ifndef LINKLIST_H
  2 #define LINKLIST_H
  3 
  4 #include "List.h"
  5 #include "Exception.h"
  6 #include "SmartPointer.h"
  7 
  8 namespace DTLib
  9 
 10 
 11 template < typename T >
 12 class LinkList : public List<T>
 13 
 14 protected:
 15     struct Node : public Object
 16     
 17         T value;
 18         SmartPointer<Node> next;
 19     ;
 20 
 21     mutable struct : public Object
 22     
 23         char reserved[sizeof(T)];
 24         SmartPointer<Node> next;
 25     m_header;
 26 
 27     int m_length;
 28     int m_step;
 29     SmartPointer<Node> m_current;
 30 
 31     Node* position(int i) const    //  O(n)
 32     
 33         //Node* ret = reinterpret_cast<Node*>(&m_header);
 34         SmartPointer<Node> ret = reinterpret_cast<Node*>(&m_header);
 35 
 36         for(int p = 0; p < i; p++)
 37         
 38             ret = ret->next;
 39         
 40 
 41         return ret.get();
 42     
 43 
 44     virtual Node* create()
 45     
 46         return new Node();
 47     
 48 
 49     virtual void destroy(Node* pn)
 50     
 51         delete pn;
 52     
 53 
 54 public:
 55     LinkList()
 56     
 57         m_header.next = NULL;
 58         m_length = 0;
 59         m_step = 1;
 60         m_current = NULL;
 61     
 62 
 63     bool insert(const T& e)
 64     
 65         return insert(m_length, e);
 66     
 67 
 68     bool insert(int i, const T& e)   // O(n)
 69     
 70         bool ret = ((0 <= i) && (i <= m_length));
 71 
 72         if( ret )
 73         
 74             Node* node = create();
 75 
 76             if( node != NULL )
 77             
 78                 Node* current = position(i);
 79 
 80                 node->value = e;
 81                 node->next = current->next;
 82                 current->next = node;
 83 
 84                 m_length++;
 85             
 86             else
 87             
 88                 THROW_EXCEPTION(NoEnoughMemoryException, "No memery to insert new element...");
 89             
 90         
 91 
 92         return ret;
 93     
 94 
 95     bool remove(int i)   // O(n)
 96     
 97         bool ret = ((0 <= i) && (i < m_length));
 98 
 99         if( ret )
100         
101             SmartPointer<Node> current = position(i);
102 
103             SmartPointer<Node> toDel = current->next;
104 
105             if( m_current == toDel )
106             
107                 m_current = toDel->next;
108             
109 
110             current->next = toDel->next;
111 
112             m_length--;
113 
114             // destroy(toDel);
115 
116         
117 
118         return ret;
119     
120 
121     bool set(int i, const T& e)   //  O(n)
122     
123         bool ret = ((0 <= i) && (i < m_length));
124 
125         if( ret )
126         
127             position(i)->next->value = e;
128         
129 
130         return ret;
131     
132 
133     T get(int i) const
134     
135         T ret;
136 
137         if( get(i, ret) )
138         
139             return ret;
140         
141         else
142         
143             THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
144         
145 
146         return ret;
147     
148 
149     bool get(int i, T& e) const    // O(n)
150     
151         bool ret = ((0 <= i) && (i < m_length));
152 
153         if( ret )
154         
155             e = position(i)->next->value;
156         
157 
158         return ret;
159     
160 
161     int find(const T& e) const    //  O(n)
162     
163         int ret = -1;
164         int i = 0;
165 
166         SmartPointer<Node> node = m_header.next;
167 
168         //while( node )
169         while( node.isNull() )
170         
171             if( node->value == e )
172             
173                 ret = i;
174                 break;
175             
176             else
177             
178                 node = node->next;
179                 i++;
180             
181         
182 
183         return ret;
184     
185 
186     int length() const   // O(1)
187     
188         return m_length;
189     
190 
191     void clear()    //  O(n)
192     
193         //while( m_header.next )
194         while( m_header.next.isNull() )
195         
196             //Node* toDel = m_header.next;
197             SmartPointer<Node> toDel = m_header.next;
198 
199             m_header.next = toDel->next;
200 
201             m_length--;
202 
203             // destroy(toDel);
204         
205 
206         // m_length = 0;
207     
208 
209     bool move(int i, int step = 1)
210     
211         bool ret = (0 <= i) && (i < m_length) && (step > 0);
212 
213         if( ret )
214         
215             m_current = position(i)->next;
216             m_step = step;
217         
218 
219         return ret;
220     
221 
222     bool end()
223     
224         //return (m_current == NULL);
225         return m_current.isNull();
226     
227 
228     T current()
229     
230         if( !end() )
231         
232             return m_current->value;
233         
234         else
235         
236             THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
237         
238     
239 
240     bool next()   //每次移动step步
241     
242         int i = 0;
243 
244         while((i < m_step) && !end())
245         
246             m_current = m_current->next;
247             i++;
248         
249 
250         return (i == m_step);
251     
252 
253     ~LinkList()   //  O(n)
254     
255         clear();
256     
257 ;
258 
259 
260 
261 #endif // LINKLIST_H

 1 #include <iostream>
 2 #include "LinkList.h"
 3 
 4 using namespace std;
 5 using namespace DTLib;
 6 
 7 
 8 int main()
 9 
10     LinkList<int> list;
11 
12     for(int i = 0; i < list.length(); i++)
13     
14         list.insert(i);
15     
16 
17     for(list.move(0); !list.end(); list.next())
18     
19         cout << list.current() << endl;
20     
21 
22     return 0;
23