Table View – Spacers (Part 3 of 6)

Making a scrolling list of cells isn’t that hard. Making a list that only creates as many cells as is necessary for display is slightly harder. Using a single component which can elegantly handle variations like whether or not the cell size can change or what direction the scrolling will occur, is pretty advanced. The best way to approach this kind of challenge is to break it down into manageable pieces.

Divide and Conquer

One of the basic ideas of programming is to encapsulate change. In other words when we look at the features of our TableView I can see areas of code that will “vary” depending on what selections the implementor has picked. For example, let’s say that I have two tableviews, where most every feature is the same: they both scroll vertically, and they both flow from top to bottom. The only difference in these two table views is that one of them always uses uniform cell sizes, and the other uses non-uniform cell sizes.

As the scroll view changes its scroll position, the table view will need to determine what the new range of visible cells is. Any cells which have scrolled out of view need to be pooled (for reuse) and any cells which have have scrolled into view need to be displayed (reused from the pool if possible). Determining the range of cells when the sizes are uniform is trivial and can have very efficient code driven by math. In contrast determining the range of cells when the sizes are unique requires us to parse the heights of the cells.

In practice, this “branching” of logic usually begins inside the original class. It is hard to predict all the places you will need specialized code and where you can use the same code. It wouldn’t be surprising to see a method like this in my TableView class while it was early in development:

void UpdateVisibleRange ()
{
	if (usingUniformCellSizes)
	{
		// Easy
	}
	else
	{
		// Not so easy
	}
}

It is when you start seeing that same “if statement” litered throughout your code that you begin to realize there is not only an opportunity to refactor, but that you probably should. One way to make this work is to program to an “interface” – I know that my table view needs to be able to determine which cells are visible, but I dont care “how” it determines which cells are visible. When I initialize the tableview I can also instantiate an object which conforms to the interface, and which does so according to the unique features that were requested.

In following along with this lesson, you will see the end result of what I chose to encapsulate, but you wont have the benefit of working through this cleanup process without having tried it yourself.

ISpacer

Since I started with the example of cell sizes as the concept to encapsulate, I will show you the end result of this first. The code below is taken from the “ISpacer.cs” script (located in “Scripts/Common/UI/TableView/ISpacer/”):

using UnityEngine;
using System.Collections;

namespace TableViewHelpers
{
	public interface ISpacer
	{
		int TotalSize { get; }
		int GetSize (int index);
		int GetPosition (int index);
		void Insert (int index);
		void Remove (int index);
		Point GetVisibleCellRange (int screenStart, int screenEnd);
	}
}

Here we have created an interface. By convention, the interface name is prefixed with a capital “I” for “interface”, although it is not technically required. The keyword “interface” instead of “class” is the true difference. An interface is not something I have used much in any of my previous blogs, so let’s take a small detour to introduce them.

You can think of an interface like an abstract base class – it defines methods and/or properties which concrete implementors must provide. You make use of polymorphism so that you can access the methods defined at the base level without needing to know the class which implemented it.

One of the key differences between an interface and an abstract base class is that a class can only inherit from one other base class, but it can implement as many interfaces as you like. On the flip-side, abstract base classes are still quite valuable becuase they can provide a default implementation for the methods whereas an interface can not. If you try to provide an implementation for an interface you will get an error: error CS0531: interface members cannot have a definition. Abstract base classes can also define fields whereas interfaces can not. If you try to include a field you will get another error: error CS0525: Interfaces cannot contain fields or constants.

Note that I don’t specify public or private on anything in the interface. Everything is assumed to be public – in fact you can’t make them private, or you will get a compiler error: error CS0106: The modifier `private’ is not valid for this item. Hopefully this should be obvious anyway – what would be the point of an interface you couldn’t see?

I wrapped the interface in a “namespace” to help avoid naming conflicts. This was not required, but ISpacer seemed like a name as likely as any to be reused somewhere else.

Take a moment to look over the methods defined in the interface:

  • TotalSize – a property returning an “int” which is the total size a container would need to be in order to hold all the items of the tableView. This can be calculated when the cell size is uniform, but I will need to maintain a sum otherwise.
  • GetSize – a method which takes the “index” of a cell and returns the size of the indicated cell. For a uniform implementation I can return a constant value. For a non-uniform implementation I will need to look up the value.
  • GetPosition – a method which takes the “index” of a cell and says where to place it within the “container”. This can be calculated when the cell size is uniform, but I will need to maintain a sum otherwise.
  • Insert – a method which informs the object that a new cell has been added to the collection and at what index it was added. This allows the object a chance to update any information which might be used to determine the container size or position of elements, etc.
  • Remove – like insert, this method indicates that a cell has been removed from the collection and provides an opportunity for maintaining my data.
  • GetVisibleCellRange – Given a start and end viewport coordinate, the object should be able to determine which cells fall within that space. I return a “Point” which is a struct with two “int” fields: “x” to represent the first cell index which is visible and “y” to represent the last cell index which is visible.

Uniform Spacer

The first class which implements the “ISpacer” interface is the “UniformSpacer.cs” script. You can open and review the completed script from the project, but I will point out and comment on several code snippets here.

namespace TableViewHelpers
{
	public class UniformSpacer : ISpacer
	{
		int CellSize;
		int CellCount;

		public UniformSpacer (int rowHeight, int rowCount)
		{
			CellSize = rowHeight;
			CellCount = rowCount;
		}
		
		// ... other code hidden
	}
}

Here I have defined the class “UniformSpacer” to implement the interface “ISpacer”. Normally you would list the interfaces after the class you wish to inherit from, but this class doesn’t inherit from a base class so the interface appears immediately. If there were a base class, the interface would be listed afterward, following a comma, and additional interfaces could also be listed separated by commas if needed.

The implementation for this class is so simple that I can implement everything as long as I know two simple things: the size for the cells, and the number of cells contained in the table. Both of those are required parameters in the constructor. Note that the understood “size” of the cell is variant based on the implementation of the table. When creating a vertical table view, the spacing I care about is along the y-axis, so “size” would be referring to “height”. When creating a horizontal table view, the spacing I care about is along the x-axis, so “size” would be referring to “width”. The ability to be used for either pattern is why I chose a more generic term such as “size”.

Next let’s examine the implementation of the interface elements:

public int TotalSize
{
	get
	{
		return CellCount * CellSize;
	}
}

Here, I have decided to implement the interface’s property as a calculated return-only property. Note that it isn’t necessary to have a backing field for your properties. I could have created one, but then anywhere that I change the “CellCount” I would also have to remember to change the TotalSize. In this example, there are three places that value could change: the constructor, insert, and remove. If I should forget to keep the value up to date in any of those locations it could cause a bug. Since this property is calculated, it will always be correct without my need to maintain it.

public int GetSize (int index)
{
	return CellSize;
}

Since all of the cell sizes are uniform in this case, I don’t care what index is referred to. I can simply return a constant value – the same one passed along in the constructor.

public int GetPosition (int index)
{
	return index * CellSize;	
}

In this case, the index does matter, but the location of any cell is still easy to calculate. For example, a cell at index zero would appear at position zero because anything multiplied by zero is zero. Like with CellSize, the Cell’s position needs to be understood in the context of its implementation. When creating a vertical table view, the position would be referring to the y-coordinate. When creating a horizontal table view, the position would be referring to the x-coordinate.

public void Insert (int index)
{
	CellCount++;
}

public void Remove (int index)
{
	CellCount--;
}

Insert and remove are also very simple. All that is necessary is that I either increment or decrement the number of cells the spacer is tracking. In this way, future calls to TotalSize for example, will still return the correct value.

public Point GetVisibleCellRange (int screenStart, int screenEnd)
{
	Point range = new Point(int.MaxValue, int.MinValue);
	if (CellCount == 0)
		return range;

	range.x = Mathf.Max( (screenStart / CellSize), 0 );
	range.y = Mathf.Min( (screenEnd / CellSize), CellCount - 1 );
	return range;
}

The final method, GetVisibleCellRange, is worthy of a bit more commentary. This method takes two parameters, a start and end coordinate. Those parameters also need to be thought of in relation to the kind of tableview that is being implemented. A vertical tableview would be passing along the coordinates that represented the first y-coordinate pixel that is on screen (which happens to be how far the content has scrolled in that direction) and then the other parameter would be the first paramter’s value plus the height of the scroll rect.

The value I will attempt to return is a structure which holds two integers, an “x” and “y” where the “x” will represent the index of the first cell which should be visible and the “y” will represent the index of the last cell which should be visible. Initially I set this value to something “invalid” because I say that the first index visible is greater than the last index visible. I can use this to my advantage by using a normal c-style for loop, where I only loop while the first value is less than or equal to the second. When no cells should be displayed, this “invalid” initial setting will cause the “for loop” to be skipped.

If there are cells to be displayed, I update the values in the return value. Note that I am using integer math, which “floors” the value. For example say that I have scrolled “22” pixels in the scroll rect and that the cell size is “44”. With real numbers, the division would result in a value of “0.5”. In this case I know that only half of the cell has slid off-screen, so that cell must still be visible. This is why I allow the value to be “floored” rather than “rounded” so that it returns index zero. This way the first cell (index zero) would still be displayed in the example.

After calculating the index, I also clamp the values. I make sure that the first cell that can be shown is index zero, because negative values don’t make sense in this conext. I also make sure that the highest value that can be shown would be the last index of the cell in my tableview. Don’t forget that indices are zero-based, meaning that if you have ten items, their indices are zero to nine. This is why I use CellCount - 1 as the value to clamp to.

Non-Uniform Spacer

The second class which implements the “ISpacer” interface is the “NonUniformSpacer.cs” script. You can open and review the completed script from the project, but I will point out and comment on several code snippets here.

public int TotalSize { get; private set; }
List<int> Sizes;
List<int> Positions;
Func<int, int> SizeForIndex;

public NonUniformSpacer (Func<int, int> sizeForIndex, int cellCount)
{
	Sizes = new List<int>(cellCount);
	Positions = new List<int>(cellCount);
	SizeForIndex = sizeForIndex;

	TotalSize = 0;
	for (int i = 0; i < cellCount; ++i)
	{
		int size = SizeForIndex(i);
		Sizes.Add(size);
		Positions.Add(TotalSize);
		TotalSize += size;
	}
}

For this implementation, I keep a running sum of all the cell heights – I made the TotalSize property into an auto-implemented one. This means there is an actual field backing the property even though you don’t see it. Since I can’t easily calculate cell positions, I decided to cache them. I am actually storing parallel lists, one for the cell sizes (height or width depending on scenario) and one for the cell positions (an ‘X’ or ‘Y’ coordinate position also depending on the scenario). Finally, I keep a reference to a special kind of delegate called a “Func”. This delegate will take an “int” for the cell index and return an “int” for the cell size.

The constructor requires two bits of information like our first implementation did. Instead of a constant for the cell size though, I pass in the “Func” to allow me to query cell sizes as needed. Note that there is no error handling for null delegates here. You may decide to include that on your own. The second bit of information is the starting number of cells in our table view.

Using the “cellCount” input parameter I can initialize the caches with an appropriate capacity. Then I loop through the number of cells building a sum for the content size and also recording heights and positions as I go. I record the data needed for the entire tableview in a single setup pass.

public int GetSize (int index)
{
	return Sizes[index];	
}

public int GetPosition (int index)
{
	return Positions[index];	
}

Since I cached the sizes and positions of the cells in the constructor, I can simply pass along the data directly by index in the list. For simple lists it might not have been terrible to determine the position of a cell as needed, but I wanted to make sure that a large list would always be as efficient as possible. You don’t want your tableviews stuttering as new cells come into view.

public void Insert (int index)
{
	int size = SizeForIndex(index);
	TotalSize += size;

	if (Sizes.Count == index)
	{
		if (Positions.Count == 0)
			Positions.Add(0);
		else
			Positions.Add((Positions.Last() + Sizes.Last()));
		Sizes.Add(size);
	}
	else
	{
		Sizes.Insert(index, size);
		Positions.Insert(index, Positions[index]);

		for (int i = index + 1; i < Positions.Count; ++i)
			Positions[i] += size;
	}
}

There is a lot to do when Inserting new cells. Initially I must grab the size of the cell which has just been added. I will increment the TotalSize field so my container size can be updated. Then I need to Add or Insert a new height and position entry into my lists. When adding, I need to determine the position of the cell by adding the last cell’s size and position together (or setting it to zero if there were no other cells). If the specified index is less than the count of the lists then I need to loop over all subsequent entries and increment their positions by the size of the added cell.

public void Remove (int index)
{
	int size = Sizes[index];
	TotalSize -= size;
	Sizes.RemoveAt(index);
	Positions.RemoveAt(index);

	for (int i = index; i < Positions.Count; ++i)
		Positions[i] -= size;
}

When removing cells I also have a bit of maintenance. I need to check the size of the cell which is about to be removed, then update the container size and remove an entry from both the size and position lists at the specified index. When the list count is greater than the index, I need to loop from the index to the end of the list and decrement all positions by the height of the cell that was removed.

public Point GetVisibleCellRange (int screenStart, int screenEnd)
{
	Point range = new Point(int.MaxValue, int.MinValue);
	if (Sizes.Count == 0)
		return range;

	for (int i = 0; i < Sizes.Count; ++i)
	{
		int size = Sizes[i];
		int position = Positions[i];
		bool isVisible = !(position + size < screenStart || position > screenEnd);
		if (isVisible)
		{
			range.x = Mathf.Min(range.x, i);
			range.y = i;
		}
		if (position + size > screenEnd)
			break;
	}

	return range;
}

The implementation for “GetVisibleCellRange” shares several implementation details from the previous version. For example, I begin with the “invalid” return value range which can be returned when there are no cells in the table.

When there are cells in the table, I need to start looping over the cells to figure out where the first cell index is located that will be onscreen. Within each step of the loop I update the range as long as the cell is determined to be visible, lowering the min index (only valid the first time it finds a cell) and updating the max index. Once I have passed the current screen area I can exit the loop early.

There are probably ways that I could optimize this algorithm but the current process is performant enough for now, and is probably significantly easier to understand. If you look at other people’s code often you may see that sometimes there is an unfortunate habit of over-engineering and or premature optimization. It’s great to have efficient code, but not necessarily at the risk of making it harder to read and maintain – a problem which might also allow the introduction of new bugs.

Summary

In Part 3 (of 6) we introduced a strategy for creating something “complex” where we break functionality down into smaller parts. In this post we focused on how to control the spacing of cells within their container based on whether or not they had a uniform size. The actual implementation involved the creation of an “interface” and a few new “classes” which we discussed in detail.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s