TrieNode.as

package iv.collections {

	import flash.events.IEventDispatcher;
	import flash.utils.Dictionary;
	
	import mx.collections.IList;
	import mx.events.CollectionEvent;
	import mx.events.CollectionEventKind;
	import mx.events.PropertyChangeEvent;
	
	/*
	 * Usage: This is a self building Node object that creates a tree index on each of the characters of a property
	 * of collection of data.
	 * Example:
	 *			Using the AssetList ListLoader
	 *			var tree:Node = new Node('fleet_id', assets.value)
	 *			Once this is done, you can start using the tree index
	 * 
	 * Note: The constructor takes an extra parameter called treeDepth. You should never enter a value
	 * 		 got this parameter, otherwise the Node may not work properly.
	 *
	 * ToDo1: Refactor treeDepth out of constructor so users do not accidently set it and mess up the Node
	 *
	 */
	
	public class TrieNode { 
		
		private var hash:Object;
		private var list:Dictionary;
		private var depth:int;	
		private var isRoot:Boolean = false;
		private var maxDepth:int = 5;
		
		public function TrieNode(proName:String = null, collection:IList = null, treeDepth:int = 0) {
			hash = {};
			list = new Dictionary();
			depth = treeDepth;
			_propertyName = proName;
			if (depth == 0) {
				isRoot = true;
			}
			dataProvider = collection;
		}
		
		/****** The public methods *******/
		
		public function getAllValueObjects():Array {
			var valueObjects:Array = new Array();
			for (var child:String in hash) {
				var node:TrieNode = hash[child];
				valueObjects = valueObjects.concat(node.getAllValueObjects());
			}
			valueObjects = valueObjects.concat(getValueObjectsForNode());
			return valueObjects;
		}
		
		public function getValueObjects(keyToFind:String = null):Array {
			var allValueObjects:Array = getAllValueObjects();
			var valuesObjects:Array = [];
			for each (var key:Object in allValueObjects) {
				if (keyToFind) {
					if (matchesKey(keyToFind, key[_propertyName])) {
						valuesObjects.push(key);
					}
				} else {
					valuesObjects.push(list[key]);
				}
			}  
			return valuesObjects;
		}
		
		public function getValueObject(key:String):Object {
			for each (var obj:Object in list) {
				if (list[obj][_propertyName] == key) {
					return list[obj];
				}
			}  
			return null;
		}
		
		public function insert(id:String, valueObject:Object):Boolean {
			var node:TrieNode = traverse(id);
			if (node) {
				node.addValueObject(valueObject);
				if (valueObject is IEventDispatcher) {
					(valueObject as IEventDispatcher).addEventListener(PropertyChangeEvent.PROPERTY_CHANGE,processUpdate,false,0,true);
				}
				return true;
			}
			return false;
		}
		
		public function find(id:String):TrieNode {
			return traverse(id, false);
			
			/* var node:TreeNode = traverse(id, false);
			return (node.getValueObject(id)) ? node : null; */
		}
		
		public function remove(obj:Object):Boolean {
			var node:TrieNode = find(obj[_propertyName]);
			if (node) {
				node.removeValueObject(obj);
				return true;
			}	
			return false;
		} 
		
		public function containsKey(key:String):Boolean {
			return hash[key] != null;
		}
		
		public function containsValues():Boolean {
			for each (var key:Object in list) {
				return true;
			}  
			return false;
		}
		
		public function toString():String {
			var dump:String = "";
			
			for each (var key:Object in list) {
				dump += " - value objects = { " +list[key][_propertyName] + " }";
			}  
			
			for (var child:String in hash) {
				dump += "\n" + stringFill(depth);
				dump += child;
				dump += hash[child].toString();
			}
			return dump;
		}
		
		/****** Private functions *******/
		
		private function getValueObjectsForNode():Array {
			var valuesObjects:Array = [];
			for each (var key:Object in list) {
				valuesObjects.push(list[key]);
			}  
			return valuesObjects;
		}
		
		private function matchesKey(keyToFind:String, objectKey:String):Boolean {
			var keyToFindArray:Array = keyToFind.split("");
			var objectKeyArray:Array = objectKey.toLowerCase().split("");
			var count:int = 0;
			for (var i:int = 0; i < keyToFindArray.length; i++) {
				if (keyToFindArray[i] == objectKeyArray[i]) {
					count++;
				}
			}
			return count == keyToFindArray.length;
		}
		
		private function removeValueObject(value:Object):void {
			if (value is IEventDispatcher) {
				(value as IEventDispatcher).removeEventListener(PropertyChangeEvent.PROPERTY_CHANGE,processUpdate);
			}
			delete list[value];
		}
		
		private function addValueObject(value:Object):void {
			list[value] = value;
		}
		
		private function traverse(value:String, creationMode:Boolean = true):TrieNode {
			var letters:Array = value.split("");
			var key:String = letters[0];
			key = key.toLowerCase();
			letters = letters.slice(1, letters.length);
			var truncatedString:String = letters.join("");
			
			if (containsKey(key)) {
				if (validKey(truncatedString)) {
					return hash[key].traverse(truncatedString, creationMode);
				} else {
					return hash[key];
				}
			} else {
				if (creationMode) {
					if ((depth+1) > maxDepth) {
						return this;
					}
					
					var newNode:TrieNode = new TrieNode(_propertyName, null, depth+1);
					hash[key] = newNode;
					
					if (!validKey(truncatedString)) {
						return newNode;
					}
					return newNode.traverse(truncatedString, creationMode);
				}
				
				if (containsValues()) {
					return this; 
				}
				return null;
				
			}
		}
		
		private function validKey(key:String):Boolean {
			return (key.length == 0) ? false : true;
		}
		
		private function buildTree():void {
			if (isRoot && _dataProvider && _propertyName) {
				var item:Object;
				var itemIndex:int; 
				for (itemIndex = 0; itemIndex < _dataProvider.length; itemIndex++) {
					item = _dataProvider.getItemAt(itemIndex);
					insert(item[_propertyName], item);
				}
			}
		}
		
		private function stringFill(spaces:int):String {
			var str:String = "";
			for (var i:int = 0; i < spaces; i++) {
				str += " ";
			}
			return str;
		}
		
		/****** Event Handlers *******/
		
		public function onCollectionChange(event:CollectionEvent):void {
			var item:Object;
			
			switch (event.kind) {
				case CollectionEventKind.ADD:
					for each (item in event.items) {
						insert(item[_propertyName], item);
					}
					break;
				case CollectionEventKind.REMOVE:
					for each (item in event.items) {
						remove(item);
					}
					break;
				case CollectionEventKind.UPDATE:
					for each (var itemChangeEvent:PropertyChangeEvent in event.items) {
						if (itemChangeEvent.property == propertyName) {
							remove(itemChangeEvent.target);
							insert(itemChangeEvent.target[_propertyName], itemChangeEvent.target);
						} 
					}
					break;
				case CollectionEventKind.RESET:
				case CollectionEventKind.REFRESH:
					buildTree();
					break;
				case CollectionEventKind.MOVE:
					break;
				default:
					throw new Error ("Node was not expecting to receive this event: "+event.kind, 097472806393);
			}
		}
		
		private function processUpdate(event:PropertyChangeEvent):void { 
			if (event.property == _propertyName) {
				var node:TrieNode = find(String(event.oldValue));
				var objToRemove:Object;
				if (node) {
					objToRemove = node.getValueObject(event.target[_propertyName]);
					node.removeValueObject(objToRemove);
				}
			} else {
				remove(event.target);
			}
			insert(event.target[_propertyName], event.target);
		}
		
		/****** Setters and Getters *******/
		
		private var _propertyName:String;
		
		[Inspectable]
		public function get propertyName():String {
			return _propertyName;
		}
		
		public function set propertyName(value:String):void {
			if (value && value != _propertyName) {
				_propertyName = value;
				buildTree();
			}
		}
		
		private var _dataProvider:IList;
		
		[Inspectable]
		public function get dataProvider():IList {
			return _dataProvider;
		}
		
		public function set dataProvider(value:IList):void {
			if (value && value != _dataProvider) {
				if (_dataProvider) {
					_dataProvider.removeEventListener(CollectionEvent.COLLECTION_CHANGE, onCollectionChange);
				}
				_dataProvider = value;
				_dataProvider.addEventListener(CollectionEvent.COLLECTION_CHANGE, onCollectionChange, false, 0, true);
				buildTree();		
			}
		}
		
	}
		
}