ASでHeapを書いてみた。

id::ma38su

最近、sourceforge.jpにアクセス拒否されてるみたい。困った困った。

ASにもJavaのコレクションフレームワークみたいなのを実装してくれないものかなと思いつつ気分転換に書いてたのをせっかくなので晒す。

package org.ma38su.util
{
	/**
	 * ヒープを実装したクラスです。
	 * コンストラクタに比較関数を定義することで、自由に要素の順序を定義することができます。
	 * 比較関数の引数は2、戻り値は、intでもNumberでも比較できる型であればかまいません。
	 * 比較関数の戻り値が0のとき、要素は等しいと判断され、
	 * 0より大きいとき、1番目の引数よりも、2番目の引数が小さいとされ、
	 * 0より大きいとき、1番目の引数よりも、2番目の引数が大きいとされます。
         * @author ma38su
	 */
	public class Heap
	{
		/**
		 * ソートされるオブジェクト
		 */
		private var entries:Array;

		/**
		 * 要素間の比較をする関数
		 */
		private var comparator:Function;

		/**
		 * ヒープのコンストラクタ
		 * @param comparator 比較関数
		 */
		public function Heap(compareFunction:Function=null) {
			entries = new Array();
			entries.push(null);
			this.comparator = compareFunction;
		}

		/**
		 * @param entry 挿入する要素
		 */
		public function add(entry:Object):void {
			entries.push(entry);
			fixUp(entries.length - 1);
		}

		/**
		 * 入れ替える
		 * @param index1
		 * @param index2
		 */
		private function swap(index1:uint, index2:uint):void {
			var tmp:Object = entries;
			entries = entries;
			entries = tmp;
		}

		/**
		 * ヒープの先頭（根）の要素を削除して取り出す
		 * @return ヒープの先頭の要素
		 */
		public function poll():Object {
			if (entries.size == 0) {
				return null;
			}
			var entry:Object = entries<1>;
			if (entries.length > 2) {
				entries<1> = entries.pop();
			} else if (entries.length == 2){
				entries.pop();
			}
			if (entries.length > 2) {
				fixDown(1);
			}
			return entry;
		}

		/**
		 * 削除せずにヒープの先頭（根）の要素を取り出す
		 * @return ヒープの先頭の要素
		 */
		public function peek():Object {
			return entries<1>;
		}

		/**
		 * 子との状態の比較、必要に応じて移動
		 * @param index 比較する要素の添字
		 */
		private function fixDown(index:uint):void {
			var son:uint;
			while ((son = index << 1) < entries.length) {
				var nson:uint = son + 1;
				if (comparator ==  null) {
					if (nson  entries) {
						son = nson;
					}
					if (entries <= entries) {
						break;
					}
				} else {
					if (nson  0) {
						son = nson;
					}
					if (comparator.call(null, entries, entries) > 1) > 0) {
				if (comparator == null) {
					if (entries >= entries
) {
						break;
					}
				} else {
					if (comparator.call(null, entries, entries
) >= 0) {
						break;
					}
				}
				swap(index, parent);
				index = parent;
			}
		}

		/**
		 * ヒープが空かどうかの確認
		 * @return ヒープに空ならtrueを返す
		 */
		public function isEmpty():Boolean {
			return entries.length <= 1;
		}

		/**
		 * ヒープの要素数を返す関数
		 * @return ヒープの要素数
		 */
		public function size():uint {
			return entries.length - 1;
		}
	}
}

あー、一応ラクダの本とか、アルパカの本とかもちょこちょこ目を通してますよ。