ocean.util.container.ebtree.model.Iterators source code

1 /*******************************************************************************
2 
3     Elastic binary tree node iterator classes template
4 
5     Used as mixin in the EBTree classes. The Iterator and PartIterator classes
6     are nested classes of the EBTree class the template is mixed into.
7     Both classes are suitable for memory-friendly 'scope' usage.
8 
9     Copyright:
10         Copyright (c) 2009-2016 dunnhumby Germany GmbH.
11         All rights reserved.
12 
13     License:
14         Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
15         Alternatively, this file may be distributed under the terms of the Tango
16         3-Clause BSD License (see LICENSE_BSD.txt for details).
17 
18 *******************************************************************************/
19 
20 module ocean.util.container.ebtree.model.Iterators;
21 
22 /*******************************************************************************
23 
24     Template with iterator classes.
25 
26     Template parameters:
27         Node = tree node struct type; expected to be an instance of the Node
28                struct template in ocean.util.container.ebtree.model.Node.
29 
30 *******************************************************************************/
31 
32 template Iterators ( Node )
33 {
34     /***************************************************************************
35 
36         Provides 'foreach' and 'foreach_reverse' iteration over the nodes in the
37         tree, starting with the first or last node, respectively.
38 
39     ***************************************************************************/
40 
41     class Iterator
42     {
43         /***********************************************************************
44 
45             Set to true to skip key duplicates. This flag may be changed during
46             iteration.
47 
48         ***********************************************************************/
49 
50         public bool unique = false;
51 
52         /***********************************************************************
53 
54             Constructor
55 
56             Params:
57                 unique = true: skip key duplicates, false: iterate over all
58                          nodes.
59 
60         ***********************************************************************/
61 
62         public this ( bool unique = false )
63         {
64             this.unique = unique;
65         }
66 
67         /***********************************************************************
68 
69             foreach iterator over nodes in the tree. Any tree modification is
70             permitted during iteration.
71 
72         ***********************************************************************/
73 
74         public int opApply ( scope int delegate ( ref Node node ) dg )
75         {
76             int ret = 0;
77 
78             for (Node* node = this.first; node && !ret;
79                        node = this.unique? node.next_unique : node.next)
80             {
81                 ret = dg(*node);
82             }
83 
84             return ret;
85         }
86 
87         /***************************************************************************
88 
89             foreach_reverse iterator over nodes in the tree. Any tree modification
90             is permitted during iteration.
91 
92         ***************************************************************************/
93 
94         public int opApplyReverse ( scope int delegate ( ref Node node ) dg )
95         {
96             int ret = 0;
97 
98             for (Node* node = this.last; node && !ret;
99                        node = this.unique? node.prev_unique : node.prev)
100             {
101                 ret = dg(*node);
102             }
103 
104             return ret;
105         }
106 
107         /***********************************************************************
108 
109             Returns:
110                 the EBTree instance this instance iterates over.
111 
112         ***********************************************************************/
113 
114         public typeof (this.outer) host ( )
115         {
116             return this.outer;
117         }
118 
119         /***********************************************************************
120 
121             Returns:
122                 the first node in the tree or null if there is none.
123 
124         ***********************************************************************/
125 
126         protected Node* first ( )
127         {
128             return this.outer.first;
129         }
130 
131         /***********************************************************************
132 
133             Returns:
134                 the first last in the tree or null if there is none.
135 
136         ***********************************************************************/
137 
138         protected Node* last ( )
139         {
140             return this.outer.last;
141         }
142     }
143 
144     /***************************************************************************
145 
146         Provides 'foreach' and 'foreach_reverse' iteration over the nodes in the
147         tree, starting with the first node whose key is greater or less than a
148         reference key, respectively.
149 
150     ***************************************************************************/
151 
152     class PartIterator : Iterator
153     {
154         /***********************************************************************
155 
156             Reference key. May be changed at any time but becomes effective on
157             the next iteration start.
158 
159         ***********************************************************************/
160 
161         public Key key;
162 
163         /***********************************************************************
164 
165             Constructor
166 
167             Params:
168                 key    = reference key
169                 unique = true: skip key duplicates, false: iterate over all
170                          nodes.
171 
172         ***********************************************************************/
173 
174         public this ( Key key, bool unique = false )
175         {
176             super(unique);
177 
178             this.key = key;
179         }
180 
181         /***********************************************************************
182 
183             Returns:
184                 the first node in the tree whose key is greater than or equal to
185                 the reference key or null if there is none.
186 
187         ***********************************************************************/
188 
189         protected override Node* first ( )
190         {
191             return this.outer.firstGreaterEqual(this.key);
192         }
193 
194         /***********************************************************************
195 
196             Returns:
197                 the first node in the tree whose key is less than or equal to
198                 the reference key or null if there is none.
199 
200         ***********************************************************************/
201 
202         protected override Node* last ( )
203         {
204             return this.outer.firstLessEqual(this.key);
205         }
206     }
207 }