I’ve just begun to convert a number of DS&A from Java into AS2 and it got me thinking...

I’m sure others have some they have used/developed. It would be great if we could gather them together in a thread for other developers to learn from/use. This will also give the chance for others to suggest possible improvements.

To keep code easily referenced and readable, it would be good if we could follow a format similar to this
-----------
Title: Name of DS or A (if an optimized version of one already posted, then indicate this)
1: (Optional) Overview of DS or A
2: Code dump
3: How to use it
4: (Optional) Further examples of use

when in doubt, leave it out - Josh Bloch

[Mike]

Note I've not been able to beat the built in performance of Array.sort or Array.sortOn functions (unsurprisingly I guess) which I'm sure both use a quicksort, so this is really for you geeks who want to study/play with it.

Sort algorithm using divide-and-conquer technique. Array is partitioned into 3 segments, left (west), middle (pivot) and right (east). The pivot segment contains only one element. No element on to the left of the pivot contains a key larger than the pivot, and no element on the right of the pivot contains a key less than the pivot. Now we sort left and right partitions using recursive quick sort.

QuickSort
{
    private function QuickSort(){}
    
    // a = array to be sorted
    // param = parameter to sort on (must hold a num or string)
    public static function sort(a:Array, p:String):Void
    {
        if(a == undefined || a.length <= 1) {
            return;
        }
        
        // Only done simple checking
        if(p != undefined && (typeof(a[0][p]) == "string" || 
                typeof(a[0][p]) == "number" || typeof(a[0][p]) == "boolean")) {
          doObjSort(a, 0, a.length - 1, p);
        }
        else if(typeof(a[0]) == "string" || typeof(a[0]) == "number" || 
                                        typeof(a[0]) == "boolean") {
          doPrimSort(a, 0, a.length - 1);
        }
    }
    
    // Note: Recursively passing in "a" and "p" appears faster 
    // than setting them as a class property.
    // we/ee = west/east end 
    // wc/ec = west-east/east-west cursor
    // Recursive quick sort on property p of object array
    private static function doObjSort(a, we:Number, ee:Number, p):Void
    {
        var wc:Number = we;
        var ec:Number = ee; 
        var pivot:Object = a[Math.round((we+ee)/2)][p];
        var t:Object;
 
        while (true)
        {
            while (a[wc][p] < pivot) wc++;
            while (a[ec][p] > pivot) ec--;
            if (wc > ec) {break;}// not pretty but seems quicker
            t = a[wc];
            a[wc++] = a[ec];
            a[ec--] = t;
        }
        if(we < ec) doObjSort(a, we, ec, p);
       if(ee > wc) doObjSort(a, wc, ee, p); 
    }
    
    // Recursive quick sort on array of primitives
    private static function doPrimSort(a, we:Number, ee:Number):Void
    {
        var wc:Number = we;
        var ec:Number = ee; 
        var pivot:Object = a[we];
        var t:Object;
        
        while (true)
        {
            while (a[wc] < pivot) wc++;
            while (a[ec] > pivot) ec--;
            if (wc > ec) {break;}
            t = a[wc];
            a[wc++] = a[ec];
            a[ec--] = t;
        }
     if(we < ec) doPrimSort(a, we, ec);
       if(ee > wc) doPrimSort(a, wc, ee); 
    } 

How to use it:

// Can be an array of Boolean, String or Numeric values
var numArray:Array = new Array(2,5,3,6,8,5,3,59,87,23,4,634);
QuickSort.sort(numArray);
trace(numArray); // Gives: 2,3,3,4,5,5,6,8,23,59,87,634
 
// You can also sort on an array of common objects by one 
// of their properties, as long as this property is of type 
// Boolean, String or Number. For instance, if you had an 
// array of MovieClips "clipArray" you could sort these 
// on their names like so:
 
QuickSort.sort(clipArray, "_name"); 

If you linked this up with the Layout class and related classes I posted in this thread(with help from Rampage & senocular)(second large code dump half way down) and added some tweening to the arrange functions:
http://<a href="http://www.ultrashoc...adid=66958</a>
You could create something along the lines of product sort here:
http://www.crew9.net/flash.html

[Mike]

FIFO Queue (simple but worth a post)

// Generic Queue Interface
interface IQueue
{
   public function peek():Object
   public function dequeue():Object
   public function enqueue(element:Object):Void
   public function isEmpty():Boolean
} 

class ArrayQueue implements IQueue
{
   var queue:Array;
 
   public function ArrayQueue(initCapac:Number)
   {
       if(initCapac == undefined || initCapac <= 0) {
           queue = new Array();
       }
       else {queue = new Array(initCapac);}
   }
 
   // Return front of queue but don't remove it
   public function peek():Object
   {
      if (isEmpty()) {return null;}
      return queue[queue.length-1]; 
   }
   
   // Remove and return front element of queue
   public function dequeue():Object
   {
      if (isEmpty()) {return null;}
      return queue.pop();
   }
   
   // Insert element at the rear of queue
   public function enqueue(element:Object):Void
   {queue.unshift(element);}
   
   // Check if queue is empty
   public function isEmpty():Boolean
   {return !queue.length;}
   
   public function toString():String
   {return queue.toString();}
} 

How to use it:

// Example...
var q:ArrayQueue = new ArrayQueue();
trace("empty "+q.isEmpty()); // empty true
q.enqueue("A");
q.enqueue("B");
q.enqueue(1);
q.enqueue(2);
 
trace("queue "+q); // queue 2,1,B,A
trace("peek "+q.peek()); // peek A
trace("dequeue "+q.dequeue()); // dequeue A
trace("queue "+q); // queue 2,1,B
q.enqueue("X");
trace("queue "+q); // queue X,2,1,B 
 

[Mike]

I converted a Java example found at the site bellow and I believe it is correct. From tests the Quick Sort seems WAY faster than the Flash Sort when it comes to an array of strings (at any size), but when it comes to larger arrays (300+) of numbers, FlashSort wins. As the array size increases, so does the performance gap between the two. (Oh, and the name Flash Sort has nothing to do with MM Flash! )

Find out more about this sort here: http://www.neubert.net/Flacodes/FLACodes.html

/**
 * Translation of Karl-Dietrich Neubert's algorithm into AS2.0   
 * Conversion made from Rosanne Zhang's Java code
 */
class FlashSort 
{
    public static function sort(a:Array):Void
    {
        stageOneFlashSort(a);
        stageTwoInsertionSort(a);
    }
 
    private static function stageOneFlashSort(a:Array):Void
    {
        var n = a.length;
        
        //Number of groups into which the elements are classified
      //Neubert suggests 0.2 to 0.5 times the number of elements in the array.
        var m = Math.round(n*0.3);
        if(m <= 0 ) m = 1;
        var l = new Array(m);
        var i = 0, j = 0, k = 0;
        var anmin = a[0];
        var nmax  = 0;
        for(var x = 0; x<m; x++) l[x]=0; // init vector values
        for (i=1; i < n; i++)
        {
            if (a[i] < anmin) anmin=a[i];
            if (a[i] > a[nmax]) nmax=i;            
        }
 
        if (anmin == a[nmax]) return;
        var c1 = (m - 1)/(a[nmax] - anmin);
 
        for (i=0; i < n; i++)
        {
            k=Math.round(c1*(a[i] - anmin));
            l[k]++;
        }
 
        for (k=1; k < m; k++)
        {
          l[k] += l[k-1];
        }
 
        var hold = a[nmax];
        a[nmax]=a[0];
        a[0]=hold;
 
        var nmove = 0;
        var flash;
        j=0;
        k=m-1;
 
        while (nmove < n-1)
        {
            while (j > (l[k]-1))
            {
                j++;
                k = Math.round(c1 * (a[j] - anmin));
            }
            flash = a[j];
            
            // 
            while (j != l[k])
            {
                k = Math.round(c1 * (flash - anmin));
                hold = a[l[k]-1];
                a[l[k]-1]=flash;
                flash = hold;
                l[k]--; // dec pointer to next index
                nmove++;
            }
        }
    }
    
    // Now we have our partially ordered array,
    // we do an insertion sort to order the remainder.
    private static function stageTwoInsertionSort(a:Array):Void
    {
        var i:Number;
        var j:Number;
        var h:Number;
        
        for (i=a.length-3; i>=0; i--)
        {
            if (a[i+1] < a[i]) {
                h = a[i];
                j=i;
                while (a[j+1] < h) 
                {
                    a[j] = a[j+1];
                    j++;
                }
                a[j] = h;
            }
        }
    }
} 

How to use it:

// Recommend using FlashSort only on large (300+) array of nums
// QuickSort otherwise
var numArray:Array = new Array(2,5,3,6,8,5,3,59,87,23,4,634);
FlashSort.sort(numArray);
trace(numArray); // Gives: 2,3,3,4,5,5,6,8,23,59,87,634 
 

[Mike]

Updated to use bitwise shift to half and floor m, cheers Nutrox

This may well be floating about Ultrashock somewhere, but I couldn’t find it. Anyway, this is (divide and conquer) binary search on an array sorted in ascending order. This is obviously a lot faster than a sequential search (on average). If you have not come across this before and wish to find out more, you can Google it for loads of result.

AS2 Version

class BinarySearch
{
    private function BinarySearch(){}
    
    public static function search(a:Array, x:Object):Number
    {
        if(a == undefined || x == undefined) return -1;
        var m, w = 0, e = a.length;
        while(w<=e) {
            m = (w+e) >> 1;
            if(x == a[m]) return m;
            if(x < a[m]) e = m-1;
            else w = m+1;
        }
        return -1;
    }
} 

How to use it:

var resultIndex:Number = BinarySearch.search(sortedArray, searchValue); 

Array.prototype version

Array.prototype.binarySearch = function(x) {
    if(x == undefined) return -1;
    var m, w = 0, e = this.length;
    while(w<=e) {
        m = (w+e) >> 1;
        if(x == this[m]) return m;
        if(x < this[m]) e = m-1;
        else w = m+1;
    }
    return -1;
} 

How to use it:

var resultIndex:Number = sortedArray.binarySearch(searchValue) 

[Codemonkey]

Very cool, Mike. Could you maybe create some fictional scenarios where you would specifically pick one of these? I never have the feeling like "hmm, binary search would really speed things up here" (and what about hashtables, splay trees, HOT queues and whatnot?).

[Nutrox]

Yar, very nice.

I assume, in Layman's terms, that "Data Structures & Algorithms" simply means "utility classes"... unless I've missed something.

Either way, I've made this thread sticky because it looks like it will end up being a good resource.

[Mike]

Cheers Nutrox,

They do fall under the umbrella of util classes. Data structures encapsulating a specific collection of data and operations allowed on them. Algorithms providing some sort of working on data structures.

Of course there are hundreds more data structures and algorithms out there. I haven't had the need for all of them in Flash just yet. Although it's always good to view the inner workings I think.

I hope others feel free to post more (or other versions) so we can build up a nice collection.

As for scenarios, well each algorithm has it's own forte. I've posted, along with each algorithm, where and on when it is useful.

Data structures I use when I want to hide operations I'm doing on a collection and help clarify my code (for hash table I tend to use a native object as it's pretty much how I would want it).