1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4// ---------------------------------------------------------------------------
5// Iterator.h
6// ---------------------------------------------------------------------------
7
8// ================================================================================
9// Iterator pattern:
10//
11// This pattern is similar to the STL iterator pattern. It basically consists of
12// wrapping an "iteration variable" in an object, and providing pointer-like operators
13// on the iterator. Example usage:
14//
15// for (Iterator start = foo->Begin(), end = foo->End(); start != end; start++)
16// {
17// // use foo, start
18// }
19//
20// There are 3 levels of iterator functionality
21// 1. Enumerator (STL forward) - only go forward one at a time
22// Enumerators have the following operations:
23// operator * : access current element as ref
24// operator -> : access current element as ptr
25// operator++ : go to the next element
26// operator==, operator!= : compare to another enumerator
27//
28//
29// 2. Scanner (STL bidirectional) - backward or forward one at a time
30// Scanners have all the functionality of enumerators, plus:
31// operator-- : go backward one element
32//
33// 3. Indexer (STL random access) - skip around arbitrarily
34// Indexers have all the functionality of scanners, plus:
35// operator[] : access the element at index from iterator as ref
36// operator+= : advance iterator by index
37// operator+ : return new iterator at index from iterator
38// operator-= : rewind iterator by index
39// operator- : return new iterator at index back from iterator
40// operator <, operator <=, operator >, operator>= :
41// range comparison on two indexers
42//
43// The object being iterated should define the following methods:
44// Begin() return an iterator starting at the first element
45// End() return an iterator just past the last element
46//
47// Iterator types are normally defined as member types named "Iterator", no matter
48// what their functionality level is.
49// ================================================================================
50
51
52#ifndef ITERATOR_H_
53#define ITERATOR_H_
54
55#include "contract.h"
56
57namespace HIDDEN {
58// These prototypes are not for direct use - they are only here to illustrate the
59// iterator pattern
60
61template <typename CONTAINER, typename ELEMENT>
62class ScannerPrototype
63{
64 public:
65
66 typedef ScannerPrototype<CONTAINER, ELEMENT> Iterator;
67
68 ELEMENT &operator*();
69 ELEMENT *operator->();
70
71 Iterator &operator++();
72 Iterator operator++(int);
73 Iterator &operator--();
74 Iterator operator--(int);
75
76 bool operator==(const Iterator &i);
77 bool operator!=(const Iterator &i);
78};
79
80template <typename CONTAINER, typename ELEMENT>
81class EnumeratorPrototype
82{
83 public:
84
85 typedef EnumeratorPrototype<CONTAINER, ELEMENT> Iterator;
86
87 ELEMENT &operator*();
88 ELEMENT *operator->();
89
90 Iterator &operator++();
91 Iterator operator++(int);
92
93 bool operator==(const Iterator &i);
94 bool operator!=(const Iterator &i);
95};
96
97template <typename CONTAINER, typename ELEMENT>
98class IndexerPrototype
99{
100 public:
101 typedef IndexerPrototype<CONTAINER, ELEMENT> Iterator;
102
103 ELEMENT &operator*();
104 ELEMENT *operator->();
105 ELEMENT &operator[](int index);
106
107 Iterator &operator++();
108 Iterator operator++(int);
109 Iterator &operator--();
110 Iterator operator--(int);
111
112 Iterator &operator+=(SCOUNT_T index);
113 Iterator &operator-=(SCOUNT_T index);
114
115 Iterator operator+(SCOUNT_T index);
116 Iterator operator-(SCOUNT_T index);
117
118 SCOUNT_T operator-(Iterator &i);
119
120 bool operator==(const Iterator &i);
121 bool operator!=(const Iterator &i);
122 bool operator<(const Iterator &i);
123 bool operator<=(const Iterator &i);
124 bool operator>(const Iterator &i);
125 bool operator>=(const Iterator &i);
126};
127
128template <typename ELEMENT>
129class EnumerablePrototype
130{
131 typedef EnumeratorPrototype<EnumerablePrototype, ELEMENT> Iterator;
132
133 Iterator Begin();
134 Iterator End();
135};
136
137template <typename ELEMENT>
138class ScannablePrototype
139{
140 typedef ScannerPrototype<ScannablePrototype, ELEMENT> Iterator;
141
142 Iterator Begin();
143 Iterator End();
144};
145
146template <typename ELEMENT>
147class IndexablePrototype
148{
149 typedef IndexerPrototype<IndexablePrototype, ELEMENT> Iterator;
150
151 Iterator Begin();
152 Iterator End();
153};
154
155};
156
157// --------------------------------------------------------------------------------
158// EnumeratorBase, ScannerBase, and IndexerBase are abstract classes
159// describing basic operations for iterator functionality at the different levels.
160//
161// You
162// 1. Use the classes as a pattern (don't derive from them), and plug in your own
163// class into the Enumerator/Scanner/Indexer templates below.
164// 2. Subclass the AbstractEnumerator/AbstractScanner/AbstractIndexer classes
165// --------------------------------------------------------------------------------
166
167namespace HIDDEN
168{
169// These prototypes are not for direct use - they are only here to illustrate the
170// pattern of the BASE class for the Iterator templates
171
172template <typename ELEMENT, typename CONTAINER>
173class EnumeratorBasePrototype
174{
175 protected:
176 EnumeratorBasePrototype(CONTAINER *container, BOOL begin);
177 ELEMENT &Get() const;
178 void Next();
179 BOOL Equal(const EnumeratorBasePrototype &i) const;
180 CHECK DoCheck() const;
181};
182
183template <typename ELEMENT, typename CONTAINER>
184class ScannerBasePrototype
185{
186 protected:
187 ScannerBasePrototype(CONTAINER *container, BOOL begin);
188 ELEMENT &Get() const;
189 void Next();
190 void Previous();
191 BOOL Equal(const ScannerBasePrototype &i) const;
192 CHECK DoCheck() const;
193};
194
195template <typename ELEMENT, typename CONTAINER>
196class IndexerBasePrototype
197{
198 protected:
199 IndexerBasePrototype(CONTAINER *container, SCOUNT_T delta);
200 ELEMENT &GetAt(SCOUNT_T delta) const;
201 void Skip(SCOUNT_T delta);
202 SCOUNT_T Subtract(const IndexerBasePrototype &i) const;
203 CHECK DoCheck(SCOUNT_T delta) const;
204};
205
206};
207
208
209template <typename CONTAINER>
210class CheckedIteratorBase
211{
212 protected:
213#if defined(_DEBUG)
214 const CONTAINER *m_container;
215 int m_revision;
216#endif
217
218 CHECK CheckRevision() const
219 {
220 LIMITED_METHOD_CONTRACT;
221 SUPPORTS_DAC;
222#if defined(_DEBUG)
223 __if_exists(CONTAINER::m_revision)
224 {
225 CHECK_MSG(m_revision == m_container->m_revision,
226 "Use of Iterator after container has been modified");
227 }
228#endif
229 CHECK_OK;
230 }
231
232 CheckedIteratorBase()
233 {
234 LIMITED_METHOD_DAC_CONTRACT;
235#if defined(_DEBUG)
236 m_container = NULL;
237#endif
238 }
239
240 CheckedIteratorBase(const CONTAINER *container)
241 {
242 LIMITED_METHOD_CONTRACT;
243#if defined(_DEBUG)
244 m_container = container;
245 __if_exists(CONTAINER::m_revision)
246 {
247 m_revision = m_container->m_revision;
248 }
249#endif
250 }
251
252 void Resync(const CONTAINER *container)
253 {
254 LIMITED_METHOD_DAC_CONTRACT;
255
256#if defined(_DEBUG)
257 __if_exists(CONTAINER::m_revision)
258 {
259 m_revision = m_container->m_revision;
260 }
261#endif
262 }
263
264#if defined(_DEBUG)
265 const CONTAINER *GetContainerDebug() const
266 {
267 LIMITED_METHOD_CONTRACT;
268 return m_container;
269 }
270#endif
271
272 public:
273 CHECK Check() const
274 {
275 WRAPPER_NO_CONTRACT;
276 SUPPORTS_DAC;
277 CHECK(CheckRevision());
278 CHECK_OK;
279 }
280
281 CHECK CheckContainer(const CONTAINER *container) const
282 {
283 WRAPPER_NO_CONTRACT;
284#if defined(_DEBUG)
285 CHECK(container == m_container);
286#endif
287 CHECK_OK;
288 }
289
290};
291
292
293// --------------------------------------------------------------------------------
294// Enumerator, Scanner, and Indexer provide a template to produce an iterator
295// on an existing class with a single iteration variable.
296//
297// The template takes 3 type parameters:
298// CONTAINER - type of object being interated on
299// ELEMENT - type of iteration
300// BASE - base type of the iteration. This type must follow the pattern described
301// by the above Prototypes
302// --------------------------------------------------------------------------------
303
304template <typename ELEMENT, typename SUBTYPE>
305class Enumerator
306{
307 private:
308 const SUBTYPE *This() const
309 {
310 return (const SUBTYPE *) this;
311 }
312
313 SUBTYPE *This()
314 {
315 return (SUBTYPE *)this;
316 }
317
318 public:
319
320 Enumerator()
321 {
322 }
323
324 CHECK CheckIndex() const
325 {
326#if defined(_DEBUG)
327 CHECK(This()->DoCheck());
328#endif
329 CHECK_OK;
330 }
331
332 ELEMENT &operator*() const
333 {
334 PRECONDITION(CheckPointer(This()));
335 PRECONDITION(This()->CheckIndex());
336
337 return This()->Get();
338 }
339 ELEMENT *operator->() const
340 {
341 PRECONDITION(CheckPointer(This()));
342 PRECONDITION(This()->CheckIndex());
343
344 return &(This()->Get());
345 }
346 SUBTYPE &operator++()
347 {
348 PRECONDITION(CheckPointer(This()));
349
350 This()->Next();
351 return *This();
352 }
353 SUBTYPE operator++(int)
354 {
355 PRECONDITION(CheckPointer(This()));
356
357 SUBTYPE i = *This();
358 This()->Next();
359 return i;
360 }
361 bool operator==(const SUBTYPE &i) const
362 {
363 PRECONDITION(CheckPointer(This()));
364 PRECONDITION(i.Check());
365
366 return This()->Equal(i);
367 }
368 bool operator!=(const SUBTYPE &i) const
369 {
370 PRECONDITION(CheckPointer(This()));
371 PRECONDITION(i.Check());
372
373 return !This()->Equal(i);
374 }
375};
376
377template <typename ELEMENT, typename SUBTYPE>
378class Scanner
379{
380 private:
381 const SUBTYPE *This() const
382 {
383 return (const SUBTYPE *)this;
384 }
385
386 SUBTYPE *This()
387 {
388 return (SUBTYPE *)this;
389 }
390
391 public:
392
393 Scanner()
394 {
395 }
396
397 CHECK CheckIndex() const
398 {
399#if defined(_DEBUG)
400 CHECK(This()->DoCheck());
401#endif
402 CHECK_OK;
403 }
404
405 ELEMENT &operator*() const
406 {
407 PRECONDITION(CheckPointer(This()));
408 PRECONDITION(This()->CheckIndex());
409
410 return This()->Get();
411 }
412 ELEMENT *operator->() const
413 {
414 PRECONDITION(CheckPointer(This()));
415 PRECONDITION(This()->CheckIndex());
416
417 return &This()->Get();
418 }
419 SUBTYPE &operator++()
420 {
421 PRECONDITION(CheckPointer(This()));
422
423 This()->Next();
424 return *This();
425 }
426 SUBTYPE operator++(int)
427 {
428 PRECONDITION(CheckPointer(This()));
429
430 SUBTYPE i = *This();
431 This()->Next();
432 return i;
433 }
434 SUBTYPE &operator--()
435 {
436 PRECONDITION(CheckPointer(This()));
437
438 This()->Previous();
439 return *This();
440 }
441 SUBTYPE operator--(int)
442 {
443 PRECONDITION(CheckPointer(this));
444
445 SUBTYPE i = *This();
446 This()->Previous();
447 return i;
448 }
449 bool operator==(const SUBTYPE &i) const
450 {
451 PRECONDITION(CheckPointer(This()));
452 PRECONDITION(i.Check());
453
454 return This()->Equal(i);
455 }
456 bool operator!=(const SUBTYPE &i) const
457 {
458 PRECONDITION(CheckPointer(This()));
459 PRECONDITION(i.Check());
460
461 return !This()->Equal(i);
462 }
463};
464
465template <typename ELEMENT, typename SUBTYPE>
466class Indexer
467{
468 private:
469 const SUBTYPE *This() const
470 {
471 return (const SUBTYPE *)this;
472 }
473
474 SUBTYPE *This()
475 {
476 return (SUBTYPE *)this;
477 }
478
479 public:
480
481 Indexer()
482 {
483 LIMITED_METHOD_DAC_CONTRACT;
484 }
485
486 CHECK CheckIndex() const
487 {
488#if defined(_DEBUG)
489 CHECK(This()->DoCheck(0));
490#endif
491 CHECK_OK;
492 }
493
494 CHECK CheckIndex(int index) const
495 {
496#if defined(_DEBUG)
497 CHECK(This()->DoCheck(index));
498#endif
499 CHECK_OK;
500 }
501
502 ELEMENT &operator*() const
503 {
504 WRAPPER_NO_CONTRACT;
505 PRECONDITION(CheckPointer(This()));
506 PRECONDITION(This()->CheckIndex(0));
507
508 return *(ELEMENT*)&This()->GetAt(0);
509 }
510 ELEMENT *operator->() const
511 {
512 WRAPPER_NO_CONTRACT;
513 PRECONDITION(CheckPointer(This()));
514 PRECONDITION(This()->CheckIndex(0));
515
516 return &This()->GetAt(0);
517 }
518 ELEMENT &operator[](int index) const
519 {
520 WRAPPER_NO_CONTRACT;
521 PRECONDITION(CheckPointer(This()));
522 PRECONDITION(This()->CheckIndex(index));
523 return *(ELEMENT*)&This()->GetAt(index);
524 }
525 SUBTYPE &operator++()
526 {
527 WRAPPER_NO_CONTRACT;
528 PRECONDITION(CheckPointer(This()));
529 This()->Skip(1);
530 return *This();
531 }
532 SUBTYPE operator++(int)
533 {
534 WRAPPER_NO_CONTRACT;
535 PRECONDITION(CheckPointer(This()));
536 SUBTYPE i = *This();
537 This()->Skip(1);
538 return i;
539 }
540 SUBTYPE &operator--()
541 {
542 WRAPPER_NO_CONTRACT;
543 PRECONDITION(CheckPointer(This()));
544 This()->Skip(-1);
545 return *This();
546 }
547 SUBTYPE operator--(int)
548 {
549 WRAPPER_NO_CONTRACT;
550 PRECONDITION(CheckPointer(This()));
551 SUBTYPE i = *This();
552 This()->Skip(-1);
553 return i;
554 }
555 SUBTYPE &operator+=(SCOUNT_T index)
556 {
557 WRAPPER_NO_CONTRACT;
558 PRECONDITION(CheckPointer(This()));
559 This()->Skip(index);
560 return *This();
561 }
562 SUBTYPE operator+(SCOUNT_T index) const
563 {
564 WRAPPER_NO_CONTRACT;
565 PRECONDITION(CheckPointer(This()));
566 SUBTYPE i = *This();
567 i.Skip(index);
568 return i;
569 }
570 SUBTYPE &operator-=(SCOUNT_T index)
571 {
572 WRAPPER_NO_CONTRACT;
573 PRECONDITION(CheckPointer(This()));
574 This()->Skip(-index);
575 return *This();
576 }
577 SUBTYPE operator-(SCOUNT_T index) const
578 {
579 WRAPPER_NO_CONTRACT;
580 PRECONDITION(CheckPointer(This()));
581 SUBTYPE i = *This();
582 i.Skip(-index);
583 return i;
584 }
585 SCOUNT_T operator-(const SUBTYPE &i) const
586 {
587 WRAPPER_NO_CONTRACT;
588 PRECONDITION(CheckPointer(This()));
589 PRECONDITION(i.Check());
590
591 return This()->Subtract(i);
592 }
593 bool operator==(const SUBTYPE &i) const
594 {
595 WRAPPER_NO_CONTRACT;
596 PRECONDITION(CheckPointer(This()));
597 PRECONDITION(i.Check());
598
599 return This()->Subtract(i) == 0;
600 }
601 bool operator!=(const SUBTYPE &i) const
602 {
603 WRAPPER_NO_CONTRACT;
604 PRECONDITION(CheckPointer(This()));
605 PRECONDITION(i.Check());
606
607 return This()->Subtract(i) != 0;
608 }
609 bool operator<(const SUBTYPE &i) const
610 {
611 WRAPPER_NO_CONTRACT;
612 PRECONDITION(CheckPointer(This()));
613 PRECONDITION(i.Check());
614 return This()->Subtract(i) < 0;
615 }
616 bool operator<=(const SUBTYPE &i) const
617 {
618 WRAPPER_NO_CONTRACT;
619 PRECONDITION(CheckPointer(This()));
620 PRECONDITION(i.Check());
621 return This()->Subtract(i) <= 0;
622 }
623 bool operator>(const SUBTYPE &i) const
624 {
625 WRAPPER_NO_CONTRACT;
626 PRECONDITION(CheckPointer(This()));
627 PRECONDITION(i.Check());
628 return This()->Subtract(i) > 0;
629 }
630 bool operator>=(const SUBTYPE &i) const
631 {
632 WRAPPER_NO_CONTRACT;
633 PRECONDITION(CheckPointer(This()));
634 PRECONDITION(i.Check());
635 return This()->Subtract(i) >= 0;
636 }
637};
638
639#endif // ITERATOR_H_
640