Index: lams_common/src/flash/org/springsoft/aslib/BinaryTree.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/BinaryTree.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/BinaryTree.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,331 @@ +/* + +BinaryTree is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Binary Tree +===================================================================== +*/ + +import org.springsoft.aslib.BinaryTreeObject; +import org.springsoft.aslib.TreeNode; +import org.springsoft.aslib.ObjectTreeNode; + +// BinaryTree Class +class org.springsoft.aslib.BinaryTree +{ + // Tree root + private var treeRoot_:TreeNode; + + /** + * BinaryTree Constructor + */ + function BinaryTree() + { + treeRoot_ = null; + } + + /** + * Iterative insert + * + * @param data The data to insert into the tree + */ + public function insertIter(data:BinaryTreeObject):Void + { + var runner:TreeNode = treeRoot_; + var node:ObjectTreeNode = new ObjectTreeNode(data); + + if(isEmpty()) { + treeRoot_ = node; + return; + } + + while(true) { + if(node.getKey() == runner.getKey()) { + return; + } + else if(node.getKey() < runner.getKey()) { + + if(runner.getLeft() == null ) { + runner.setLeft(node); + return; + } + else + runner = runner.getLeft(); + } + else if(node.getKey() > runner.getKey()){ + if(runner.getRight() == null ) { + + runner.setRight(node); + return; + } + else + runner = runner.getRight(); + } + } + } + + /** + * Recursive insert + * + * @param data The data to insert into the tree + */ + public function insert(data:BinaryTreeObject):Void + { + if(isEmpty()) { + treeRoot_ = new ObjectTreeNode(data); + return; + } + insertHelper(new ObjectTreeNode(data), treeRoot_); + } + + /** + * Search the binary tree for a key + * + * @param key The key to search for in the tree + * @returns BinaryTreeObject if key was found. Otherwise returns null. + */ + public function search(key:Number):BinaryTreeObject + { + if(isEmpty()) { + return null; + } + + return searchHelper(treeRoot_, key); + } + + /** + * Print tree PreOrder + * + * @param tree Any tree node starting at the root + */ + public function printPreOrder(Void):Void + { + printPreOrderHelper(treeRoot_); + } + + /** + * Print tree PostOrder + * + * @param tree Any tree node starting at the root + */ + public function printPostOrder(Void):Void + { + printPostOrderHelper(treeRoot_); + } + + /** + * Print tree InOrder + * + * @param tree Any tree node starting at the root + */ + public function printInOrder(Void):Void + { + printInOrderHelper(treeRoot_); + } + + /** + * Remove node + * + * @param key The key to search for and to remove it from the tree + */ + public function remove(key:Number):Void + { + var tmpNode:TreeNode = null; + + // Test if we remove root node + if(key == treeRoot_.getKey()) { + if(isEmpty() && treeRoot_.isLeave()) { + treeRoot_ = null; + } + else if(null == treeRoot_.getLeft()) { + tmpNode = treeRoot_; + treeRoot_ = treeRoot_.getRight(); + tmpNode = null; + } + else if(null == treeRoot_.getRight()) { + tmpNode = treeRoot_; + treeRoot_ = treeRoot_.getLeft(); + tmpNode = null; + } + else { + tmpNode = treeRoot_.getLeft(); + while(tmpNode.getRight()) { + tmpNode = tmpNode.getRight(); + } + tmpNode.setRight(treeRoot_.getRight()); + tmpNode = treeRoot_; + treeRoot_ = treeRoot_.getLeft(); + tmpNode.setLeft(null); + tmpNode.setRight(null); + tmpNode = null; + } + } + else { + removeHelper(key, treeRoot_); + } + } + + /** + * Test if tree is empty + * + * @returns true if tree is empty. Otherwise returns false. + */ + private function isEmpty(Void):Boolean + { + return (null == treeRoot_) ? true : false; + } + + /** + * Helper Print tree PreOrder + * + * @param tree Any tree node starting at the root + */ + private function printPreOrderHelper(tree:TreeNode):Void + { + if(null != tree) { + trace(tree.toString()); + printPreOrderHelper(tree.getLeft()); + printPreOrderHelper(tree.getRight()); + } + } + + /** + * Helper Print tree InOrder + * + * @param tree Any tree node starting at the root + */ + private function printInOrderHelper(tree:TreeNode):Void + { + if(null != tree) { + printInOrderHelper(tree.getLeft()); + trace(tree.toString()); + printInOrderHelper(tree.getRight()); + } + } + + /** + * Helper recursive insert + * + * @param node The data to insert into the tree + * @param tree Any tree node starting at the root + */ + private function insertHelper(node:TreeNode, tree:TreeNode):Void + { + if(node.getKey() < tree.getKey()) { + if(tree.getLeft() == null) { + tree.setLeft(node); + } + else { + insertHelper(node, tree.getLeft()); + } + } + else if(node.getKey() > tree.getKey()) { + if(tree.getRight() == null) { + tree.setRight(node); + } + else { + insertHelper(node, tree.getRight()); + } + } + } + + /** + * Helper search binary tree + * + * @param tree Any tree node starting at the root + * @param key The key to search for in the tree + * @returns BinaryTreeObject if key was found. Otherwise returns null. + */ + private function searchHelper(tree:TreeNode, key:Number):BinaryTreeObject + { + if(key == tree.getKey()) { + return tree.get(); + } + else if(key < tree.getKey()) { + return searchHelper(tree.getLeft(), key); + } + else if(key > tree.getKey()) { + return searchHelper(tree.getRight(), key); + } + } + + /** + * Helper Print tree PostOrder + * + * @param tree Any tree node starting at the root + */ + private function printPostOrderHelper(tree:TreeNode):Void + { + if(null != tree) { + printPostOrderHelper(tree.getLeft()); + printPostOrderHelper(tree.getRight()); + trace(tree.toString()); + } + } + + /** + * Helper remove node + * + * @param key The key to search for and to remove in the tree + * @param tree Any tree node starting at the root + */ + private function removeHelper(key:Number, tree:TreeNode):TreeNode + { + var tmpNode:TreeNode = null; + var findNode:TreeNode = null; + + if(null == tree) { + return null; + } + + if(key == tree.getKey()) { + tmpNode = tree.getLeft(); + if(!tree.getLeft()) { + tmpNode = tree.getRight(); + } + else if(tree.getRight()) { + findNode = tree.getLeft(); + while(findNode.getRight()) { + findNode = findNode.getRight(); + } + findNode.setRight(tree.getRight()); + } + return tmpNode; + } + else if(key < tree.getKey()) { + tree.setLeft(removeHelper(key, tree.getLeft())); + } + else { + tree.setRight(removeHelper(key, tree.getRight())); + } + return tree; + } +} + Index: lams_common/src/flash/org/springsoft/aslib/BinaryTreeObject.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/BinaryTreeObject.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/BinaryTreeObject.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,52 @@ +/* + +BinaryTreeObject is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + BinaryTreeObject Interface +===================================================================== +*/ + +interface org.springsoft.aslib.BinaryTreeObject +{ + /** + * Get key + * + * @returns object key + */ + public function getKey(Void):Number; + + /** + * Data string representation + * + * @returns object string representation + */ + public function toString(Void):String; +} + Index: lams_common/src/flash/org/springsoft/aslib/Debug.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/Debug.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/Debug.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,69 @@ +/* + +Debug is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Provides output debugging method +===================================================================== +*/ + +class org.springsoft.aslib.Debug +{ + // Static member to indicate if debugging features are turned on or off + private static var isActive_:Boolean = false; + + /** + * Trace method prints a debugging message + * + * @param msg String holding the message + */ + static function trace(msg:String):Void + { + if(isActive_) { + trace("DEBUG: " + msg); + } + } + + /** + * Turn on debugging features + */ + static function turnOn(Void):Void + { + isActive_ = true; + } + + /** + * Turn off debugging features + */ + static function turnOff(Void):Void + { + isActive_ = false; + } +} + Index: lams_common/src/flash/org/springsoft/aslib/HashTable.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/HashTable.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/HashTable.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,153 @@ +/* + +HashTable is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + HashTable class +===================================================================== +*/ + +import org.springsoft.aslib.SingleLinkedList; +import org.springsoft.aslib.HashTableObject; + +class org.springsoft.aslib.HashTable +{ + // HashTable array default size + private var size_:Number = 50; + + // Array of SingleLinkedLists + private var hashTable_:Array; + + // Keep tarck of HashTable's size + private var numItems_:Number = 0; + + /** + * HashTable Constructor + * + * @param size The HashTable array size + */ + function HashTable(size:Number) + { + size_ = size; + + // Create the array of single linked lists + hashTable_ = new Array(size_); + + for(var i = 0; i < size; i++) { + hashTable_[i] = new SingleLinkedList(); + } + } + + /** + * Put item in HashTable + * + * @param key Hash key + * @param data Data object + */ + public function put(key:Number, data:HashTableObject):Void + { + var index:Number = key % size_; + hashTable_[index].insert(data); + numItems_++; + } + + /** + * Get an item from the HashTable + * + * @param key The hash key + * @returns data object + */ + public function get(key:Number):HashTableObject + { + var index:Number = key % size_; + // Access SLL and get the node via the SLL's get method. + // Then we call get on the node to extract the data object. + return HashTableObject(hashTable_[index].get(key).get()); + } + + /** + * Remove an item from the HashTable + * + * @param key The hash key + */ + public function remove(key:Number):Void + { + var index:Number = key % size_; + hashTable_[index].remove(key); + numItems_--; + } + + /** + * Remove all items from the HashTable + */ + public function removeAll(Void):Void + { + for(var i = 0; i < size_; i++) { + hashTable_[i].removeAll(); + } + numItems_ = 0; + } + + /** + * Get the size of the HashTable + * + * @returns size of HashTable + */ + public function size(Void):Number + { + return numItems_; + } + + /** + * Check if the HashTable is empty + * + * @returns true if HashTable is empty. Otherwise returns false. + */ + public function isEmpty(Void):Boolean + { + return (0 < numItems_) ? false : true; + } + + /** + * Print HashTable + */ + public function print(Void):Void + { + if(isEmpty()) { + trace("HastTable is empty!"); + } + + for(var i:Number = 0; i < hashTable_.length; i++) { + if(!hashTable_[i].isEmpty()) { + trace("HashTable[" + i + "]:"); + hashTable_[i].print(); + } + } + } +} Index: lams_common/src/flash/org/springsoft/aslib/HashTableObject.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/HashTableObject.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/HashTableObject.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,40 @@ +/* + +HashTableObject is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + HashTableObject Interface +===================================================================== +*/ + +import org.springsoft.aslib.SingleLinkedListObject; + +interface org.springsoft.aslib.HashTableObject extends SingleLinkedListObject +{ +} Index: lams_common/src/flash/org/springsoft/aslib/ListNode.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/ListNode.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/ListNode.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,82 @@ +/* + +ListNode is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + ListNode interface used with single linked list class +===================================================================== +*/ + + +import org.springsoft.aslib.SingleLinkedListObject; + +interface org.springsoft.aslib.ListNode +{ + /** + * Set ListNode data + * + * @param data Object data + */ + public function set(data:SingleLinkedListObject):Void; + + /** + * Get ListNode data + * + * @returns object data + */ + public function get(Void):SingleLinkedListObject; + + /** + * Set next ListNode + * + * @param node Node to be linked by the next reference + */ + public function setNext(node:ListNode):Void; + + /** + * Get next ListNode + * + * @returns the next list node + */ + public function getNext(Void):ListNode; + + /** + * ListNode string representation + * + * @returns the list node's string representation + */ + public function toString(Void):String; + + /** + * Return ListNode key + * + * @returns the list node's key + */ + public function getKey(Void):Number; +} Index: lams_common/src/flash/org/springsoft/aslib/ObjectListNode.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/ObjectListNode.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/ObjectListNode.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,118 @@ +/* + +ObjectListNode is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Object Node is an implementation of the Node class. + Used for stack class. +===================================================================== +*/ + +import org.springsoft.aslib.ListNode; +import org.springsoft.aslib.SingleLinkedListObject; + +class org.springsoft.aslib.ObjectListNode implements ListNode +{ + // Reference to next node + private var next_:ObjectListNode; + + // Node data member + private var data_:SingleLinkedListObject; + + /** + * ObjectListNode Constructor + * + * @param data Object data + */ + function ObjectListNode(data:SingleLinkedListObject) + { + next_ = null; + data_ = data; + } + + /** + * Implement get method + * + * @returns object data + */ + public function get(Void):SingleLinkedListObject + { + return data_; + } + + /** + * Implement getNext method + * + * @returns the next list node + */ + public function getNext(Void):ListNode + { + return next_; + } + + /** + * Implement setNext method + * + * @param node Node to be linked by the next reference + */ + public function setNext(node:ListNode):Void + { + next_ = ObjectListNode(node); + } + + /** + * Implement set method + * + * @param data Object data + */ + public function set(data:SingleLinkedListObject):Void + { + data_ = data; + } + + /** + * Implement toString method + * + * @returns the list node's string representation + */ + public function toString(Void):String + { + return data_.toString(); + } + + /** + * Implement getKey method + * + * @returns the list node's key + */ + public function getKey(Void):Number + { + return data_.getKey(); + } +} Index: lams_common/src/flash/org/springsoft/aslib/ObjectTreeNode.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/ObjectTreeNode.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/ObjectTreeNode.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,158 @@ +/* + +ObjectTreeNode is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Tree Node: Object Tree Node +===================================================================== +*/ + +import org.springsoft.aslib.TreeNode; +import org.springsoft.aslib.BinaryTreeObject; + +class org.springsoft.aslib.ObjectTreeNode implements TreeNode +{ + + // Reference to left node + private var left_:ObjectTreeNode; + + // Reference to right node + private var right_:ObjectTreeNode; + + // Node data member + private var data_:BinaryTreeObject; + + /** + * ObjectTreeNode Constructor + * + * @param data The object's data + */ + function ObjectTreeNode(data:BinaryTreeObject) + { + left_ = null; + right_ = null; + data_ = data; + } + + /** + * Implementation set left node + * + * @param node The node referenced by the left child + */ + public function setLeft(node:TreeNode):Void + { + left_ = ObjectTreeNode(node); + } + + /** + * Implementation set right node + * + * @param node The node referenced by the right child + */ + public function setRight(node:TreeNode):Void + { + right_ = ObjectTreeNode(node); + } + + /** + * Implementation set method + * + * @param data Object data + */ + public function set(data:BinaryTreeObject):Void + { + data_ = data; + } + + /** + * Implementation get left node + * + * @returns left child node + */ + public function getLeft(Void):TreeNode + { + return left_; + } + + /** + * Implementation get right node + * + * @returns right child node + */ + public function getRight(Void):TreeNode + { + return right_; + } + + /** + * Implementation get method + * + * @returns object data + */ + public function get(Void):BinaryTreeObject + { + return data_; + } + + /** + * Implementation toString method + * + * @returns the tree node's string representation + */ + public function toString(Void):String + { + return data_.toString(); + } + + /** + * Implementation getKey method + * + * @returns the tree node's key + */ + public function getKey(Void):Number + { + return data_.getKey(); + } + + /** + * Implementation isLeave method + * + * @returns true if node is a leave. Otherwise returns false. + */ + public function isLeave(Void):Boolean + { + if(null == left_ && null == right_) { + return true; + } + else { + return false; + } + } +} + Index: lams_common/src/flash/org/springsoft/aslib/Queue.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/Queue.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/Queue.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,90 @@ +/* + +Queue is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Queue class +===================================================================== +*/ + +import org.springsoft.aslib.SingleLinkedList; +import org.springsoft.aslib.QueueObject; + +class org.springsoft.aslib.Queue +{ + // The SingleLinkedList queue representation + private var list_:SingleLinkedList; + + /** + * Queue Constructor + */ + function Queue() + { + list_ = new SingleLinkedList(); + } + + /** + * Put item into queue + * + * @param item Data object + */ + public function enqueue(item:QueueObject):Void + { + list_.insertTail(item); + } + + /** + * Remove item from queue + * + * @returns data object + */ + public function dequeue(Void):QueueObject + { + // Get the ObjectListNode and then the data with get() + return QueueObject(list_.getFront(true).get()); + } + + /** + * Test if queue is empty + * + * @returns true if queue is empty. Otherwise returns false. + */ + public function isEmpty(Void):Boolean + { + return list_.isEmpty(); + } + + /** + * Print the queue + */ + public function print(Void):Void + { + list_.print(); + } +} Index: lams_common/src/flash/org/springsoft/aslib/QueueObject.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/QueueObject.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/QueueObject.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,41 @@ +/* + +QueueObject is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + QueueObject Interface +===================================================================== +*/ + +import org.springsoft.aslib.SingleLinkedListObject; + +interface org.springsoft.aslib.QueueObject extends SingleLinkedListObject +{ +} + Index: lams_common/src/flash/org/springsoft/aslib/SingleLinkedList.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/SingleLinkedList.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/SingleLinkedList.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,448 @@ +/* + +SingleLinkedList is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Single Linked List class +===================================================================== +*/ + +import org.springsoft.aslib.SingleLinkedListObject; +import org.springsoft.aslib.ListNode; +import org.springsoft.aslib.ObjectListNode; + +class org.springsoft.aslib.SingleLinkedList +{ + + // Head of list + private var head_:ListNode; + + /** + * SingleLinkedList Constructor + */ + function SingleLinkedList() + { + head_ = null; + } + + /** + * Test for empty list + * + * @returns true if the linked list is empty. Otherwise returns false. + */ + public function isEmpty(Void):Boolean + { + return (null == head_) ? true : false; + } + + /** + * Insert a SingleLinkedListObject. By default we insert at front of list + * + * @param data The SingleLinkedListObject's data object + */ + public function insert(data:SingleLinkedListObject):Void + { + insertFront(new ObjectListNode(data)); + } + + /** + * Insert a SingleLinkedListObject at tail + * + * @param data The SingleLinkedListObject's data object + */ + public function insertTail(data:SingleLinkedListObject):Void + { + if(isEmpty()) { + insert(data); + } + else { + var tailNode:ListNode = null; + for(var tempNode:ListNode = head_; tempNode != null; tailNode = tempNode, tempNode = tempNode.getNext()) { } + insertEnd(new ObjectListNode(data), tailNode); + } + } + + /** + * Get a node reference + * + * @param key The numeric key for finding node + * @returns ListNode if we find the key. Otherwise returns null. + */ + public function get(key:Number):ListNode + { + var tempNode:ListNode = head_; + + // Loop through the list and if we have a math, stop and return. + // If there is not a match, returning null since tempNode will point to null + for(; tempNode != null; tempNode = tempNode.getNext()) { + if(key == tempNode.getKey()) { + break; + } + } + + return tempNode; + } + + /** + * Get a SingleLinkedListObject data object reference + * + * @param key The numeric key to find SingleLinkedListObject + * @returns SingleLinkedListObject if we find the key. Otherwise returns null. + */ + public function getData(key:Number):SingleLinkedListObject + { + return this.get(key).get(); + } + + /** + * Get a node at index + * + * @param index The numeric index to locate node + * @returns ListNode if we locate the index. Otherwise returns null. + */ + public function getAt(index:Number):ListNode + { + var tempNode:ListNode = head_; + var position:Number = 0; + + // Loop through the list and if we reach the index, stop and return. + // If we have an invalid index, returning null since tempNode will point to null + for(; tempNode != null; tempNode = tempNode.getNext()) { + if(index == position) { + break; + } + position++; + } + + return tempNode; + } + + /** + * Get a SingleLinkedListObject data object reference + * + * @param index The numeric index to locate SingleLinkedListObject + * @returns SingleLinkedListObject if we locate the index. Otherwise returns null. + */ + public function getDataAt(index:Number):SingleLinkedListObject + { + return this.getAt(index).get(); + } + + /** + * Remove a node + * + * @param key The numeric key to find and remove node + * @returns ListNode if list is not empty. Otherwise returns null. + */ + public function remove(key:Number):ListNode + { + var previousTempNode:ListNode = head_; + + for(var tempNode:ListNode = head_; tempNode != null; previousTempNode = tempNode, tempNode = tempNode.getNext()) { + if(key == tempNode.getKey()) { + if(isFront(tempNode)) { + return removeFront(); + } + else if(isEnd(tempNode)) { + return removeEnd(previousTempNode); + } + else { + return removeMiddle(previousTempNode); + } + } + } + + return null; + } + + + /** + * Remove a SingleLinkedListObject + * + * @param key The numeric key to find and remove SingleLinkedListObject + * @returns SingleLinkedListObject if list is not empty. Otherwise returns null. + */ + public function removeData(key:Number):SingleLinkedListObject + { + return this.remove(key).get(); + } + + /** + * Remove a node at index + * + * @param index The numeric index to locate and remove node + * @returns ListNode if list is not empty. Otherwise returns null. + */ + public function removeAt(index:Number):ListNode + { + var previousTempNode:ListNode = head_; + var position:Number = 0; + + for(var tempNode:ListNode = head_; tempNode != null; previousTempNode = tempNode, tempNode = tempNode.getNext()) { + if(index == position) { + if(isFront(tempNode)) { + return removeFront(); + } + else if(isEnd(tempNode)) { + return removeEnd(previousTempNode); + } + else { + return removeMiddle(previousTempNode); + } + } + + position++; + } + + return null; + } + + /** + * Remove a SingleLinkedListObject at index + * + * @param index The numeric index to locate and remove SingleLinkedListObject + * @returns SingleLinkedListObject if list is not empty. Otherwise returns null. + */ + public function removeDataAt(index:Number):SingleLinkedListObject + { + return this.removeAt(index).get(); + } + + /** + * Remove all nodes + */ + public function removeAll():Void + { + var previousTempNode:ListNode = head_; + + for(var tempNode:ListNode = head_; tempNode != null; previousTempNode = tempNode, tempNode = tempNode.getNext()) { + if(null == tempNode.getNext() && null != previousTempNode.getNext()) { + tempNode = null; + } + + if(previousTempNode != tempNode) { + previousTempNode.setNext(null); + previousTempNode = null; + } + } + + if(null != head_) { + head_.setNext(null); + head_ = null; + } + } + + /** + * Return the front node and delete front node if canDelete is set to true + * + * @param canDelete Flag that indicates if we can delete the front node + * @returns ListNode if list is not empty. Otherwise returns null. + */ + public function getFront(canDelete:Boolean):ListNode + { + var node:ListNode = head_; + if(canDelete) { + removeFront(); + } + + return node; + } + + /** + * Return the front SingleLinkedListObject and delete front SingleLinkedListObject if canDelete is set to true + * + * @param canDelete Flag that indicates if we can delete the front SingleLinkedListObject + * @returns SingleLinkedListObject if list is not empty. Otherwise returns null. + */ + public function getFrontData(canDelete:Boolean):SingleLinkedListObject + { + return this.getFront(canDelete).get(); + } + + /** + * Print linked list + */ + public function print(Void):Void + { + trace("=======================") + trace("Single Linked List HEAD"); + for(var tempNode:ListNode = head_; tempNode != null; tempNode = tempNode.getNext()) { + trace(tempNode.toString()); + } + trace("Single Linked List TAIL"); + trace("=======================") + } + + /** + * Gets the size of the list + * + * @returns the number of nodes in the list + */ + public function size(Void):Number + { + var tempNode:ListNode = head_; + var size:Number = 0; + + // Loop through the list and count each node + for(; tempNode != null; tempNode = tempNode.getNext()) { + size++; + } + + return size; + } + + /** + * Test for front node + * + * @param node Test for front node + * @returns true if node is front node. Otherwise returns false. + */ + private function isFront(node:ListNode):Boolean + { + return (head_ == node) ? true : false; + } + + /** + * Test for end node + * + * @param node Test for end node + * @returns true if node is end node. Otherwise returns false. + */ + private function isEnd(node:ListNode):Boolean + { + return(null == node.getNext()) ? true : false; + } + + /** + * Test if list has only one node + * + * @returns true if list has only one node. Otherwise returns false. + */ + private function hasOneNode(Void):Boolean + { + if((null == head_.getNext()) && (isEmpty())) { + return true; + } + else { + return false; + } + } + + /** + * Insert at front + * + * @param node Insert node at front of list + */ + private function insertFront(node:ListNode):Void + { + if(isEmpty()) { + head_ = node; + node.setNext(null); + } + else { + node.setNext(head_); + head_ = node; + } + } + + /** + * Remove node from front of list + * + * @returns ListNode if list is not empty. Otherwise returns false. + */ + private function removeFront():ListNode + { + var listNode:ListNode = null; + + if(isEmpty()) { + // Don't do anything + } + else if(hasOneNode()) { + listNode = head_; + head_ = null; + } + else { + + listNode = head_; + head_ = head_.getNext(); + } + + return listNode; + } + + /** + * Insert at middle + * + * @param node Node that needs to be inserted + * @param targetNode Insert node after targetNode + */ + private function insertMiddle(node:ListNode, targetNode:ListNode):Void + { + node.setNext(targetNode.getNext()); + targetNode.setNext(node); + } + + /** + * Remove from middle + * + * @param previous Node before node that needs to be removed + * @returns ListNode + */ + private function removeMiddle(previous:ListNode):ListNode + { + var listNode:ListNode = previous.getNext(); + previous.setNext(listNode.getNext()); + return listNode; + } + + /** + * Insert at end + * + * @param node Node that needs to be inserted + * @param targetNode Insert node after targetNode + */ + private function insertEnd(node:ListNode, targetNode:ListNode):Void + { + targetNode.setNext(node); + node.setNext(null); + } + + /** + * Remove from end + * + * @param previous Node before node that needs to be removed + * @returns ListNode + */ + private function removeEnd(previous:ListNode):ListNode + { + var listNode:ListNode = previous.getNext(); + previous.setNext(null); + return listNode; + } +} Index: lams_common/src/flash/org/springsoft/aslib/SingleLinkedListObject.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/SingleLinkedListObject.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/SingleLinkedListObject.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,52 @@ +/* + +SingleLinkedListObject is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + SingleLinkedListObject Interface +===================================================================== +*/ + +interface org.springsoft.aslib.SingleLinkedListObject +{ + /** + * Get key + * + * @returns object key + */ + public function getKey(Void):Number; + + /** + * Data string representation + * + * @returns object string representation + */ + public function toString(Void):String; +} + Index: lams_common/src/flash/org/springsoft/aslib/Stack.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/Stack.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/Stack.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,93 @@ +/* + +Stack is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Stack class +===================================================================== +*/ + +import org.springsoft.aslib.SingleLinkedList; +import org.springsoft.aslib.StackObject; + +class org.springsoft.aslib.Stack +{ + // The SingleLinkedList stack representation + private var list_:SingleLinkedList; + + /** + * Stack Constructor + */ + function Stack() + { + list_ = new SingleLinkedList(); + } + + /** + * Push item on stack + * + * @param item Object to be pushed on stack + */ + public function push(item:StackObject):Void + { + list_.insert(item); + } + + /** + * Pop item from stack + * + * @returns object + */ + public function pop(Void):StackObject + { + // Get the ObjectListNode and then the data with get(). + // Also making sure to delete the object from the stack by passing true to getFront + return StackObject(list_.getFront(true).get()); + } + + /** + * Peek, return top of stack without removing it + * + * @returns object + */ + public function peek(Void):StackObject + { + // Get the ObjectListNode and then the data with get() + // Also making sure to not delete the object from the stack by passing false to getFront + return StackObject(list_.getFront(false).get()); + } + + /** + * Print the stack + */ + public function print(Void):Void + { + list_.print(); + } +} Index: lams_common/src/flash/org/springsoft/aslib/StackObject.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/StackObject.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/StackObject.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,41 @@ +/* + +StackObject is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + StackObject Interface +===================================================================== +*/ + +import org.springsoft.aslib.SingleLinkedListObject; + +interface org.springsoft.aslib.StackObject extends SingleLinkedListObject +{ +} + Index: lams_common/src/flash/org/springsoft/aslib/TreeNode.as =================================================================== diff -u --- lams_common/src/flash/org/springsoft/aslib/TreeNode.as (revision 0) +++ lams_common/src/flash/org/springsoft/aslib/TreeNode.as (revision 11b2d4aa3b87b4d2268778e28906ecb7e4a455d6) @@ -0,0 +1,103 @@ +/* + +TreeNode is part of ASLib + +Copyright (C) 2004 Thomas P. Amsler + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Thomas Amsler +tamsler@cal.berkeley.edu + +*/ + +/* +===================================================================== + Requires: + ActionScript 2.0 + + Description: + Binary Tree: Tree Node +===================================================================== +*/ + + +import org.springsoft.aslib.BinaryTreeObject; + +interface org.springsoft.aslib.TreeNode +{ + /** + * Set left node + * + * @param node The node referenced by the left child + */ + public function setLeft(node:TreeNode):Void; + + /** + * Set right node + * + * @param node The node referenced by the right child + */ + public function setRight(node:TreeNode):Void; + + /** + * Set node data + * + * @param data Object data + */ + public function set(data:BinaryTreeObject):Void; + + /** + * Get left node + * + * @returns left child node + */ + public function getLeft(Void):TreeNode; + + /** + * Get right node + * + * @returns right child node + */ + public function getRight(Void):TreeNode; + + /** + * Get node data + * + * @returns object data + */ + public function get(Void):BinaryTreeObject; + + /** + * TreeNode string representation + * + * @returns the tree node's string representation + */ + public function toString(Void):String; + + /** + * Return node key + * + * @returns the tree node's key + */ + public function getKey(Void):Number; + + /** + * Test if node is a leave + * + * @returns true if node is a leave. Otherwise returns false. + */ + public function isLeave(Void):Boolean; +}