|
1 /* |
|
2 * Copyright (c) 2002-2004 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: Iterates over a tree, breadth first search algorithm |
|
15 * |
|
16 */ |
|
17 |
|
18 |
|
19 #ifndef XNBREADTHFIRSTTREEITERATOR_H |
|
20 #define XNBREADTHFIRSTTREEITERATOR_H |
|
21 |
|
22 // INCLUDES |
|
23 #include <e32base.h> |
|
24 #include <e32cmn.h> |
|
25 #include "xnchilditerator.h" |
|
26 |
|
27 |
|
28 // Constants |
|
29 /** |
|
30 * Queue granularity value |
|
31 */ |
|
32 const TInt KMemoryAlocQ = 64; |
|
33 |
|
34 template < class T > |
|
35 class CXnBreadthFirstTreeIterator: public CBase, public MXnChildIterator |
|
36 { |
|
37 public: |
|
38 |
|
39 /** |
|
40 * Two-phased constructor. |
|
41 * @param aStartNode object to iterate over |
|
42 * @param aDepth with default parameter value 0. |
|
43 */ |
|
44 static CXnBreadthFirstTreeIterator< T >* NewL( T& aStartNode, |
|
45 TUint aDepth = 0 ); |
|
46 |
|
47 /** |
|
48 * Destructor. |
|
49 */ |
|
50 virtual ~CXnBreadthFirstTreeIterator(); |
|
51 |
|
52 /** |
|
53 * Get the next iterator value. |
|
54 * @return Next object or NULL if no more values. |
|
55 */ |
|
56 T* NextL(); |
|
57 |
|
58 /** |
|
59 * Get the current iterator value. |
|
60 * @return Current object |
|
61 */ |
|
62 T* Value(); |
|
63 |
|
64 /** |
|
65 * Get the previous iterator value. Obsolete! |
|
66 * @return NULL |
|
67 */ |
|
68 T* PreviousL(); |
|
69 |
|
70 /** |
|
71 * Get the current iterator index. Obsolete! |
|
72 * @return value 0 |
|
73 */ |
|
74 TUint Index() const; |
|
75 |
|
76 protected: |
|
77 |
|
78 /** |
|
79 * C++ default constructor. |
|
80 */ |
|
81 CXnBreadthFirstTreeIterator( T* aStartNode, TUint aDepth = 0 ); |
|
82 |
|
83 /** |
|
84 * 2nd phase constructor. |
|
85 */ |
|
86 void ConstructL(); |
|
87 |
|
88 private: //Data |
|
89 // Queue |
|
90 RPointerArray< T > iQueue; |
|
91 // Object to iterate over |
|
92 T* iStart; |
|
93 // Current object |
|
94 T* iCurrent; |
|
95 // Tree depth |
|
96 TUint iDepth; |
|
97 // Current index |
|
98 TUint iIndex; |
|
99 }; |
|
100 |
|
101 |
|
102 |
|
103 // ----------------------------------------------------------------------------- |
|
104 // CXnBreadthFirstTreeIterator< T >::NewL() |
|
105 // ----------------------------------------------------------------------------- |
|
106 // |
|
107 template< class T > CXnBreadthFirstTreeIterator< T >* |
|
108 CXnBreadthFirstTreeIterator< T >::NewL( T& aStartNode, TUint aDepth ) |
|
109 { |
|
110 CXnBreadthFirstTreeIterator< T >* p = |
|
111 new ( ELeave )CXnBreadthFirstTreeIterator< T >( &aStartNode, |
|
112 aDepth ); |
|
113 CleanupStack::PushL( p ); |
|
114 p->ConstructL(); |
|
115 CleanupStack::Pop(); |
|
116 return p; |
|
117 } |
|
118 |
|
119 |
|
120 // ----------------------------------------------------------------------------- |
|
121 // XnBreadthFirstTreeIterator< T >::CXnBreadthFirstTreeIterator() |
|
122 // C++ default constructor |
|
123 // ----------------------------------------------------------------------------- |
|
124 // |
|
125 template< class T > |
|
126 CXnBreadthFirstTreeIterator< T >::CXnBreadthFirstTreeIterator( |
|
127 T* aStartNode, TUint aDepth ) : iQueue( KMemoryAlocQ ), iStart( |
|
128 aStartNode ),iCurrent( aStartNode ),iDepth( aDepth ) |
|
129 { |
|
130 |
|
131 } |
|
132 |
|
133 // ----------------------------------------------------------------------------- |
|
134 // CXnBreadthFirstTreeIterator< T >::~CXnBreadthFirstTreeIterator() |
|
135 // C++ default destructor. |
|
136 // ----------------------------------------------------------------------------- |
|
137 // |
|
138 template< class T > |
|
139 CXnBreadthFirstTreeIterator< T >::~CXnBreadthFirstTreeIterator() |
|
140 { |
|
141 iQueue.Close(); |
|
142 } |
|
143 |
|
144 // ----------------------------------------------------------------------------- |
|
145 // CXnBreadthFirstTreeIterator< T >::ConstructL() |
|
146 // Symbian 2nd phase constructor can leave. |
|
147 // ----------------------------------------------------------------------------- |
|
148 // |
|
149 template< class T > |
|
150 void CXnBreadthFirstTreeIterator< T >::ConstructL() |
|
151 { |
|
152 iQueue.AppendL( iStart ); |
|
153 iIndex = 0; |
|
154 } |
|
155 |
|
156 // ----------------------------------------------------------------------------- |
|
157 // CXnBreadthFirstTreeIterator< T >::NextL() |
|
158 // ----------------------------------------------------------------------------- |
|
159 // |
|
160 template< class T > T* CXnBreadthFirstTreeIterator< T >::NextL() |
|
161 { |
|
162 if( iQueue.Count() ) |
|
163 { |
|
164 // Dequeue |
|
165 if ( !iDepth ) |
|
166 { |
|
167 iCurrent = iQueue[0]; |
|
168 iQueue.Remove(0); |
|
169 } |
|
170 |
|
171 RPointerArray< T > currentChildNodes = iCurrent->ChildrenL(); |
|
172 TInt currentChildCount( currentChildNodes.Count() ); |
|
173 |
|
174 if ( iDepth ) |
|
175 { |
|
176 if ( (iIndex + 1) < currentChildCount ) |
|
177 { |
|
178 for ( TUint tmp = iIndex; (tmp + 1) < currentChildCount; ) |
|
179 { |
|
180 T* tmpObject = currentChildNodes[++tmp]; |
|
181 iIndex = tmp; |
|
182 currentChildNodes.Reset(); |
|
183 return tmpObject; |
|
184 } |
|
185 } |
|
186 else |
|
187 { |
|
188 currentChildNodes.Reset(); |
|
189 return NULL; |
|
190 } |
|
191 } |
|
192 // Enqueue |
|
193 for( TInt i = 0; i < currentChildCount; ++i ) |
|
194 { |
|
195 iQueue.AppendL( currentChildNodes[i] ); |
|
196 } |
|
197 currentChildNodes.Reset(); |
|
198 } |
|
199 else |
|
200 { |
|
201 iCurrent = NULL; |
|
202 iQueue.Reset(); |
|
203 iQueue.AppendL( iStart ); |
|
204 } |
|
205 return iCurrent; |
|
206 } |
|
207 |
|
208 // ----------------------------------------------------------------------------- |
|
209 // CXnBreadthFirstTreeIterator< T >::Value() |
|
210 // ----------------------------------------------------------------------------- |
|
211 // |
|
212 template< class T > T* CXnBreadthFirstTreeIterator< T >::Value() |
|
213 { |
|
214 return iCurrent; |
|
215 } |
|
216 |
|
217 // ----------------------------------------------------------------------------- |
|
218 // CXnBreadthFirstTreeIterator< T >::PreviousL() |
|
219 // ----------------------------------------------------------------------------- |
|
220 // |
|
221 template< class T > T* CXnBreadthFirstTreeIterator< T >::PreviousL() |
|
222 { |
|
223 return NULL; |
|
224 } |
|
225 |
|
226 // ----------------------------------------------------------------------------- |
|
227 // CXnBreadthFirstTreeIterator< T >::Index() |
|
228 // ----------------------------------------------------------------------------- |
|
229 // |
|
230 template< class T > TUint CXnBreadthFirstTreeIterator< T >::Index() const |
|
231 { |
|
232 return 0; |
|
233 } |
|
234 |
|
235 #endif // CXNBREADTHFIRSTTREEITERATOR_H |
|
236 |
|
237 // End of File |