Developer diaries #2 2D Iterators

October 19, 2018

One of the first thing, that people learn about programming is control flow and, in particular, loops. I can clearly recall how we have implemented two dimensional loop in qbasic in middle school. It’s very simple task, nevertheless, recently I have found a way to make it complex and cumbersome. May be task, that I will explain below, would be good for a interview.
Let’s imagine, that we have two-dimensional array W x H. Simplest way to iterate throw would be double loop directly from 6th grade:

for(int i1 = 0; i1 < H; i1++)  
       for(int i2 = 0; i2 < W; i2++)  
	      var el = array[i1 * W + i2];  

I hope I didn’t make a mistakes here, I haven’t checked this
But what if we need to get chunks of data from left to right?

var container = array[]
for(int i1 = 0; i1 < H; i1++)
    for(int i2 = 0; i2 < W; i2++)
	    container.add(array[i1 * W + i2]);

This is basically transforms one array to another, not good. We need to use iterators. What is iterators? Here is abstract interface:

protocol BaseIterator
{
   T? next();
   func clear();
}

We should have ability to create iterators from containers and call next() until it will not return null (or nil or whatever crap, which mean, that array is over). Internally it should store some counter or pointer to next element. clear() function set counter back to the beginning of collection.
For one dimensional array, that allocates in memory lineally, such pointer is trivial. But what should we do in case two dimensional array?

protocol CellsIterator {
    
    func next() -> LineCellsContainer?
}

class BaseCellsIterator {
    
    internal let gameModel : GameModel
    internal var line = LineCellsContainer()
    
    internal var y: Int = 0
    internal var x: Int = 0
    internal var w: Int { return self.gameModel.fieldWidth }
    internal var h: Int { return self.gameModel.fieldHeight }
}

Here is cropped version on baseIterator in my game and also protocol for cells iterator. I use them both because protocols with associated types (PAT) exist and annoy me, but that is a theme for another post.
So, here I store:

• link to god object (gameModel), that is completely unrelated to the topic
• container (line), that will store result of current iteration
• two integers (x, y) as pointer to current iterator position
• two integers (w, h), that describe the size the matrix Here is implementation of simple iterator x from 0 to w and y from 0 to h

    func next() -> LineCellsContainer? {
        // clear container
        line.clear()

        // if end of line, increment to next one        
        if x >= w {
            x = 0
            y += 1
        }

        // if it was last line, then we need to stop        
        if y >= h {
            return nil;
        }

        // iterate through end of the line        
        for _ in x ..< w {
            
            let cell = getCell(x, y)
            
            x += 1
            
            if(cell.isBlocked) {
                break
            }

            line.add(cell)
        }
 
        // return container
        return line;
    }

I have added comments to make it more readable, although it is already pretty simple. Unfortunately, swift doesn’t allow creation of for loops with outside variable, otherwise it would be even simpler for(;x<w;x++).
Another remark: because of the game logic (cell.isBlocked), it is possible, that loop should stop, return current container and continue with new one.
This all seems very simple, however it took for me several days to figure out how to do it right. And now I have iterators not only for 4 directions (up, down, left, right), but also by diagonals. I’m using this to check game logic for player move and at another place, to check, can player make any move at all.
DRY