Decoded: OpenTTD (2003) v1.8 (2018)
Source file: multimap.hpp
Line-by-line code walkthrough by MaiZure

multimap.hpp defines a deterministic map-like class and iterator

Original code:
https://github.com/MaiZure/OpenTTD-1.8/blob/master/src/core/multimap.hpp


NOTE: This code could stand for a few more typedefs to hide these ugly templates.
      Boilerplate incoming!


1     COMMENT (*)
2     BLANK (-)
3     *
4     *
5     *
6     *
7     *
8     *
9     -
10    *
11    -
12    Header guard
13    Header guard  
14    -
15    Includes STL map header
16    Includes STL list header
17    -
18    Sets up a class template with 3 arguments: a key type, value type, and
      comparator type
19    Forward declares the MultiMap class
20    -
21    *
22    *
23    *
24    *
25    *
26    *
27    *
28    *
29    Sets up a class template with 5 parameters -- all input types
30    BLOCK START - MultiMapIterator
31    Begins the protected section of MultiMapIterator
32    Declares a MultiMap of matching types as a friend of the iterator class
33    Add an easy typedef for the iterator as Self
34    -
35    Declares a type-specific list iterator
36    Declares a type specific map iterator
37    *
38    *
39    *
40    *
41    *
42    *
43    *
44    *
45    *
46    *
47    Declares a flag for if the list is valid
48    -
49    Begins the public section of the iterator class
50    *
51    *
52    *
53    Defines the default constructor to initialize the list to invalid
54    -
55    *
56    *
57    *
58    *
59    *
60    *
61    Sets up a template with 1 parameter: the iterator type
62    Defines a parameterized constructor with the iterator type and an initialization
      list
63    -
64    *
65    *
66    *
67    *
68    *
69    *
70    *
71    Defines another parameterized constuctor with two arguments to specify
      both the map and the list
72    BLOCK START - MultiMapIterator constructor
73    The list is valid if the passed map/lists are usable
74    BLOCK END - MultiMapIterator constructor
75    -
76    *
77    *
78    *
79    *
80    *
81    *
82    Sets up a function template with one parameter: iterator type
83    Defines an overloaded assignment operator
84    BLOCK START - MultiMapIterator = operator overload
85    Assigns the map as passed
86    Invalidates the list
87    Returns a pointer to self
88    BLOCK END - MultiMapIterator = operator overload
89    -
90    *
91    *
92    *
93    *
94    *
95    Defines an overloaded dereference operator
96    BLOCK START - MultiMapIterator * operator overload
97    Checks that the map exists
98    If the list is valid...
99    Return the list
100   Otherwise...return the 
101   BLOCK END - MultiMapIterator * operator overload
102   -
103   *
104   *
105   *
106   *
107   Defines an overloaded member access operator
108   BLOCK START - MultiMapIterator -> operator overload
109   Checks that the map isn't empty
110   If the list is valid...
111   Return a pointer to the list
112   Otherwise, return a pointer to the map
113   BLOCK END - MultiMapIterator -> operator overload
114   -
115   Defines MultiMapIterator::GetMapIter to return the map
116   Defines MultiMapIterator::GetListIter to return the list
117   Defines MultiMapIterator::ListValid to return list validity flag
118   -
119   Defines MultiMapIterator::GetKey to return the key list
120   -
121   *
122   *
123   *
124   *
125   *
126   *
127   Defines an overloaded prefix increment operator
128   BLOCK START - MultiMapIterator ++x operator overload
129   Check that the key isn't empty
130   If the list is valid...
131   If this is the end of the list...
132   Move to the next map item
133   This new list isn't valid yet
134   End check for end of the list
135   Otherwise the list isn't valid so...
136   Move to the next mapped list
137   If this is the end of the list
138   Increment to the next map item
139   Otherwise this list exists so...
140   This list must be valid
141   End check for end of list
142   End check for valid lists
143   Return a pointer to this iterator
144   BLOCK END - MultiMapIterator ++x operator overload
145   -
146   *
147   *
148   *
149   *
150   *
151   *
152   Defines an overloaded postfix increment operator
153   BLOCK START - MultiMapIterator x++ operator overload
154   Stores the current iterator value
155   Increments the iterator
156   Returns the previous value
157   BLOCK END - MultiMapIterator x++ operator overload
158   -
159   *
160   *
161   *
162   *
163   *
164   Defines an overloaded prefix decrement operator
165   BLOCK START - MultiMapIterator --x operator overload
166   Checks that the key list isn't empty
167   If the list isn't valid...
168   Need to move to the previous map
169   Update the list iterator to the end of the previous map
170   Confirm that this list isn't empty
171   End check for invalid list
172   -
173   The new ist is valid if the new position isn't the beginning of the changed
      list
174   Returns the updated iterator
175   BLOCK END - MultiMapIterator --x operator overload
176   -
177   *
178   *
179   *
180   *
181   *
182   *
183   Defines an overloaded postfix decrement operator
184   BLOCK START - MultiMapIterator x-- operator overload
185   Store the current iterator 
186   Decrement the iterator
187   Return the previous value
188   BLOCK END - MultiMapIterator x-- operator overload
189   BLOCK END - MultiMapIterator
190   -
191   *
192   -
193   *
194   *
195   *
196   *
197   *
198   *
199   *
200   *
201   *
202   *
203   *

In general, we need to be able to compare two iterators because each multimap
      consists of a list of lists and two iterators are required.

204   Sets up a function template for two MultiMap iterator defitions
205   Defines an overloaded equality operator to test iterators
206   BLOCK START - Overloaded == operator for iterators
207   If both iterators have different maps, they aren't equal
208   If both iterators have different list validity, they arent equal
209   Iterators are equal if ...
210   They both match list iterators
211   BLOCK END - Overloaded == operator for iterators
212   -
213   *
214   *
215   *
216   *
217   *
218   *
219   *
220   *
221   Sets up a function template for two MultiMap iterator defitions
222   Defines an overloaded inequality operator to test iterators
223   BLOCK START - Overloaded != operator for iterators
224   Insert snarky tautology about tauologies here
225   BLOCK END - Overloaded != operator for iterators
226   -
227   *
228   *
229   *
230   *
231   *
232   *
233   *
234   *
235   Sets up a function template for two MultiMap iterator defitions
236   Defines an overloaded equality operator to test iterator positions
237   BLOCK START - Overloaded == operator for iterators
238   Checks if the list is at the beginning of the map
239   BLOCK END - Overloaded == operator for iterators
240   -
241   *
242   * This comment is wrong
243   *
244   *
245   *
246   *
247   Sets up a function template for two MultiMap iterator defitions
248   Defines an overloaded inequality operator to test iterator positions
249   BLOCK START - Overloaded != operator for iterators
250   Returns true if the we're not at the beginning of the list
251   BLOCK END - Overloaded != operator for iterators
252   -
253   *
254   *
255   *
256   *
257   *
258   *
259   Sets up a function template for two MultiMap iterator defitions
260   Defines an overloaded equality operator to test iterator positions
261   BLOCK START - Overloaded == operator for iterators
262   Checks if the list is at the beginning of the map
263   BLOCK END - Overloaded == operator for iterators
264   -
265   *
266   *
267   *
268   *
269   *
270   *
271   Sets up a function template for two MultiMap iterator defitions
272   Defines an overloaded inequality operator to test iterator positions
273   BLOCK START - Overloaded != operator for iterators
274   Returns true if the we're not at the beginning of the list
275   BLOCK END - Overloaded != operator for iterators
276   -
277   -
278   *
279   *
280   *
281   *
282   *
283   *
284   *
285   Sets up a class template with 3 arguments: key, value, and comparator
286   Defines MultiMap class as an extension of std::map
287   Starts the public section of MultiMap
288   Defines a typedef of std::list as List for ease of use
289   Defines a typedef of List::iterator for ease of use
290   Defines a typedef of List::const_iterator for ease of use
291   -
292   Defines a typedef of std::map for this type
293   Defines a typedef of Map::iterator for ease of use
294   Defines a typedef of Map::const_iterator for ease of use
295   -
296   Defines a typedef of this iterator type to simplify the signature
297   Defines a typedef of this constant iterator type to simplify the signature
298   -
299   *
300   *
301   *
302   *
303   *
304   Defines MultiMapIterator::erase for this type and one argument
305   BLOCK START - MultiMapIterator::erase, removes the element and moves the
      iterator
306   Get the current list iterator
307   Ensure that the list isn't empty (nothing to erase!)
308   If the list is valid...
309   Erase the current value
310   *
311   *
312   If the iterator is at the end of the list...
313   Move the map iterator to a new list
314   Invalidate the list
315   End check for the end of the list
316   Otherwise the list wasn't valid so...
317   Remove the list!
318   If the list is empty, Move the map iterator to a new list (invalid?)
319   End check for a valid list
320   Return the iterator
321   BLOCK END - MultiMapIterator::erase
322   -
323   *
324   *
325   *
326   *
327   *
328   Defines MultiMap::Insert with two arguments: a key and a value
329   BLOCK START - MultiMap::Insert, adds a new key/value pair
330   Get the list for the key
331   Add the new value to the end of the list
332   Ensure that the list isn't empty
333   BLOCK END - MultiMap::Insert
334   -
335   *
336   *
337   *
338   *
339   Defines MultiMap::size with no arguments
340   BLOCK START - MultiMap::size
341   Assume the map is empty
342   Loop through the entire map
343   Add the size of the second list
344   Repeat for all maps
345   Return the total size
346   BLOCK END - MultiMap::size
347   -
348   *
349   *
350   *
351   *
352   Defines MultiMap::MapSize with no arguments
353   BLOCK START - MultiMap::MapSize, counts key matches
354   Returns the size of this particular map
355   BLOCK END - MultiMap::MapSize
356   -
357   *
358   *
359   *
360   *
361   *
362   Defines MultiMap::equal_range with one argument: the key
363   BLOCK START - MultiMap::equal_range, matches the key and collects values
364   Starts the map iterator at the first possible key match
365   If we're not at the end and the key matches...
366   Mark the end as the current point
367   Return the matching pair (match)
368   End check for match
369   Returns this start case (no match)
370   BLOCK END - MultiMap::equal_range
371   -
372   *
373   *
374   *
375   *
376   *
377   Defines MultiMap::equal_range with one argument: the key
378   BLOCK START - MultiMap::equal_range
379   Starts the map iterator at the first possible key match
380   If we're not at the end and the key matches...
381   Mark the end as the current point
382   Return the matching pair (match)
383   End check for match
384   Returns this start case (no match)
385   BLOCK END - MultiMap::equal_range
386   BLOCK END - MultiMap
387   -
388   Header guard end