IndexableList: Indexing For Faster Lookup

02.05.2011

In my last post, Collections And Chaining For Separate Presentation, I mentioned a few data structures for holding a group of objects. These are great for their purpose but sometimes they can be enhanced for a particular project. In this post, I’ll show you a great way to maintain a custom index for a group of items for easy and efficient lookup.

In most every project I have a bunch of value objects that I need to access frequently by ID or some other property they might have. There are a million different ways of doing so, but let’s look at some of the ways it could be done:

Whenever I need to find an object, I could loop through all the objects in the ArrayCollection, finding the one with the matching ID. Something like this:

var matchingWidget:Widget;
for each (var widget:Widget in widgets)
{
	if (widget.id == idToMatch)
	{
		matchingWidget = widget;
		break;
	}
}
// Do what I need to do with the widget

First of all, I really don’t want to be doing this in all the various classes where I need to find a widget with a particular ID. It’s duplicate code all over the place. Maybe I have a model that’s generally accessible throughout the application that contains my ArrayCollection. I could put a function there instead:

package
{
	import mx.collections.ArrayCollection;
 
	public class AppModel
	{
		public var widgets:ArrayCollection;
 
		public function getWidgetById(id:uint):Widget
		{
			for each (var widget:Widget in widgets)
			{
				if (widget.id == id)
				{
					return widget;
				}
			}
		}
	}
}

Now all our various classes can use this single function. That’s a step up, but we’re still potentially looping through a lot of widgets each time we want to find one with a particular ID.

What if we used a dictionary to index the widgets by ID? Something like this…

package
{
	import flash.utils.Dictionary;
 
	import mx.collections.ArrayCollection;
	import mx.events.CollectionEvent;
 
	public class AppModel
	{
		private var _widgets:ArrayCollection;
 
		public function get widgets():ArrayCollection
		{
			return _widgets;
		}
 
		public function set widgets(value:ArrayCollection):void
		{
			if (_widgets != value)
			{
				var widget:Widget;
 
				if (_widgets)
				{
					_widgets.removeEventListener(CollectionEvent.COLLECTION_CHANGE, 
							widgets_collectionChangeHandler);
 
					for each (widget in _widgets)
					{
						removeWidgetFromIndex(widget);
					}
				}
 
				_widgets = value;
 
				if (_widgets)
				{
					_widgets.addEventListener(CollectionEvent.COLLECTION_CHANGE, 
							widgets_collectionChangeHandler, false, 0, true);
 
					for each (widget in _widgets)
					{
						addWidgetFromIndex(widget);
					}
				}
			}
		}
 
		protected var widgetById:Dictionary = new Dictionary();
 
		protected function removeWidgetFromIndex(widget:Widget):void
		{
			delete widgetById[widget.id];
		}
 
		protected function addWidgetToIndex(widget:Widget):void
		{
			widgetById[widget.id] = widget;
		}
 
		public function getWidgetById(id:uint):Widget
		{
			return widgetById[id];
		}
 
		protected function widgets_collectionChangeHandler(event:CollectionEvent):void
		{
			// All the various logic to update the dictionary when the
			// collection changes using the info contained in the event.
		}
	}
}

This is generally going to be more efficient, but that’s a lot of boilerplate and it’s a pain to keep the dictionary updated. I didn’t even bother writing out the code for handling a collection change event because it’s a laborious chore to do it right. It gets nigh unto impossible if you also want to track changes to the property you’re indexing on like if you wanted to make sure your dictionary was updated when a widget’s ID changes. Doing so doesn’t really make any sense when we’re talking about IDs but it’s quite likely on another property like maybe mode, color, type, or some other property that’s likely to change. That’s a whole different discussion though so let’s get back to the story.

Wouldn’t it be nice if there was an easier way? There is–it’s called IndexableList. IndexableList implements IList so it’s eligible to be a data provider for data provider components like List, DataGroup, etc. It gives you all the capabilities of ArrayList but instead of extending ArrayList it wraps ArrayList and extends Proxy to give you for…each iteration power. The best part is it’s much easier to maintain any custom indexes and accessors by extending it and overriding the addToIndex() and removeFromIndex() functions like so:

package com.aaronhardy
{
	import flash.utils.Dictionary;
 
	/**
	 * A list with accessors to its contained objects by id.
	 */
	public class IdIndexedList extends IndexableList
	{
		public function IdIndexedList(source:Array=null)
		{
			super(source);
		}
 
		protected var objectById:Dictionary = new Dictionary();
 
		/**
		 * Retrieves an object by id.
		 */
		public function getById(id:uint):Object
		{
			return objectById[id];
		}
 
		/**
		 * Retrieves an object's index by id.
		 */
		public function getIndexById(id:uint):int
		{
			return getItemIndex(getById(id));
		}
 
		/**
		 * @inheritDoc
		 */
		override protected function addToIndex(item:Object):void
		{
			super.addToIndex(item);
			if (item.hasOwnProperty('id'))
			{
				objectById[item['id']] = item;
			}
		}
 
		/**
		 * @inheritDoc
		 */
		override protected function removeFromIndex(item:Object):void
		{
			super.removeFromIndex(item);
			if (item.hasOwnProperty('id'))
			{
				delete objectById[item['id']];
			}
		}
	}
}

Now we have a generic list of objects that is indexed by ID and we don’t have to deal with CollectionEvents to update our indexes. To get an object by ID I call myItems.getById(id). I could likewise implement getByColor(), getByType(), or getByWhatever().

Here’s the code for IndexableList:

package com.aaronhardy
{
	import flash.events.Event;
	import flash.events.EventDispatcher;
	import flash.events.IEventDispatcher;
	import flash.utils.Proxy;
	import flash.utils.flash_proxy;
 
	import mx.collections.ArrayList;
	import mx.collections.IList;
	import mx.events.CollectionEvent;
 
	[Event(name="collectionChange", type="mx.events.CollectionEvent")]
 
	/**
	 * A list with easily overridable functions for adding and removing items from indexes.
	 * This is generally extended to provide effecient accessors to objects by using indexes.
	 * @see http://aaronhardy.com
	 */
	public class IndexableList extends Proxy implements IEventDispatcher, IList
	{
		public function IndexableList(source:Array = null)
		{
			dispatcher = new EventDispatcher(this);
			this.source = source;
		}
 
		private var _list:IList
 
		public function get list():IList
		{
			return _list;
		}
 
		public function set list(value:IList):void
		{
			if (_list != value)
			{
				var item:Object;
 
				if (_list)
				{
					_list.removeEventListener(CollectionEvent.COLLECTION_CHANGE, 
						list_collectionChangeHandler);
 
				}
 
				for each (item in this)
				{
					removeFromIndex(item);
				}
 
				_list = value;
 
				if (_list)
				{
					_list.addEventListener(CollectionEvent.COLLECTION_CHANGE, 
						list_collectionChangeHandler, false, 0, true);
 
				}
 
				for each (item in this)
				{
					addToIndex(item);
				}
			}
		}
 
		/**
		 * @inheritDoc
		 */
		public function get source():Array
		{
			if (list && (list is ArrayList))
			{
				return ArrayList(list).source;
			}
			return null;
		}
 
		/**
		 *  @private
		 */
		public function set source(s:Array):void
		{
			list = new ArrayList(s);
		}
 
		/**
		 * @inheritDoc
		 */
		public function get length():int
		{
			return list ? list.length : 0;
		}
 
		/**
		 * @inheritDoc
		 */
		public function addItem(item:Object):void
		{
			addItemAt(item, length);
		}
 
		/**
		 * @inheritDoc
		 */
		public function addItemAt(item:Object, index:int):void
		{
			list.addItemAt(item, index);
			addToIndex(item);
		}
 
		/**
		 * @inheritDoc
		 */
		public function getItemAt(index:int, prefetch:int = 0):Object
		{
			return list.getItemAt(index, prefetch);
		}
 
		/**
		 * @inheritDoc
		 */
		public function getItemIndex(item:Object):int
		{
			return list.getItemIndex(item);
		}
 
		/**
		 * @inheritDoc
		 */
		public function itemUpdated(item:Object, property:Object = null, 
			oldValue:Object = null, newValue:Object = null):void
		{
			list.itemUpdated(item, property, oldValue, newValue);
		}
 
		/**
		 * @inheritDoc
		 */
		public function removeAll():void
		{
			for (var i:uint; i < list.length; i++)
			{
				removeFromIndex(list.getItemAt(i));
			}
 
			list.removeAll();
		}
 
		/**
		 * @inheritDoc
		 */
		public function removeItemAt(index:int):Object
		{
			var item:Object = list.removeItemAt(index);
			removeFromIndex(item);
			return item;
		}
 
		/**
		 * Removes an item from the list.  Throws an error if the item doesn't exist.
		 */
		public function removeItem(item:Object):void
		{
			removeItemAt(getItemIndex(item));
		}
 
		/**
		 * @inheritDoc
		 */
		public function setItemAt(item:Object, index:int):Object
		{
			var previous:Object = list.setItemAt(item, index);
			removeFromIndex(previous);
			addToIndex(item);
			return previous;
		}
 
		/**
		 * @inheritDoc
		 */
		public function toArray():Array
		{
			return list.toArray();
		}
 
		/**
		 * @private
		 */
		protected function list_collectionChangeHandler(event:CollectionEvent):void
		{
			dispatchEvent(event);
		}
 
		////////////////////////////////////////////////
 
		// Overrides of proxy to provide for...each support.
 
		override flash_proxy function deleteProperty(name:*):Boolean {
			return false;
		}
 
		override flash_proxy function getProperty(name:*):* {
			return null;
		}
 
		override flash_proxy function hasProperty(name:*):Boolean {
			return true;
		}
 
		override flash_proxy function nextNameIndex(index:int):int {
			return index < length ? index + 1 : 0;
		}
 
		override flash_proxy function nextName(index:int):String {
			return (index - 1).toString();
		}
 
		override flash_proxy function nextValue(index:int):* {
			return getItemAt(index - 1);
		}
 
		////////////////////////////////////////////////
 
		private var dispatcher:EventDispatcher;
 
		public function addEventListener(type:String, listener:Function, useCapture:Boolean = false, 
			priority:int = 0, useWeakReference:Boolean = false):void{
			dispatcher.addEventListener(type, listener, useCapture, priority);
		}
 
		public function dispatchEvent(evt:Event):Boolean{
			return dispatcher.dispatchEvent(evt);
		}
 
		public function hasEventListener(type:String):Boolean{
			return dispatcher.hasEventListener(type);
		}
 
		public function removeEventListener(type:String, listener:Function, 
			useCapture:Boolean = false):void{
			dispatcher.removeEventListener(type, listener, useCapture);
		}
 
		public function willTrigger(type:String):Boolean {
			return dispatcher.willTrigger(type);
		}
 
		////////////////////////////////////////////////
 
		/**
		 * Adds an item to any indexes.
		 */
		protected function addToIndex(item:Object):void
		{
			// For easy overriding.
		}
 
		/**
		 * Removes an item from any indexes.
		 */
		protected function removeFromIndex(item:Object):void
		{
			// For easy overriding.
		}
	}
}

Note that it does not implement ICollectionView so you can’t use sorting, filtering, or cursors on it unless you feed it into a ListCollectionView object (see my previous post for more info).

I hope that saves someone some time and anguish. Have fun with it and let me know if you have suggestions or questions.

Tags: , , , ,


Comments

02.05.2011 / Rasheed Abdul-Aziz said:

Our ‘ListIndex’ lets you initialise it with a list to follow, and a field to index on.

This code is really old, possibly brittle and not very cleanly written, however, our software has used this class in pivitol solutions without any incidence, so it’s pretty much stable.

http://bit.ly/hPUqJ6

What I like about it is that we keep a single list and augment it from services, so it’s in fact really efficient, always up to date, and doesn’t try to be a list itself.

02.05.2011 / Nate Ross said:

Chicken skin. Thanks for the component!

12.03.2011 / flex developer said:

I tried this code and it is working. Thank for sharing great code.


Leave a Comment

Your email address is required but will not be published.




Comment