[Flash] HashMap

  • HashMap

    • Download:HashMap.zip

    原先遇到HashMap結構時我都直接使用polygonal網站上所提供的，但因為設計上的需求，需要更改HashMap裡的key/value pair的次序性，所以只好自己重新實做一個。下載包裡面包含了以下五個原始檔：

    -------------------------------------------------------

    • HashMapNode.as：A double linkedlist node for hash structure
    • Map.as：Interface for Map structure
    • HashMap.as：HashMap Class
    • Iterator.as：Interface for Iterator
    • HashIterator.as：HashIterator Class

    -------------------------------------------------------

    使用Double LinkedList Node結構比較方便之後的功能擴充

    /* HashMapNode.as */
    package xinyu.collection{
    public class HashMapNode{
    public var key:*;
    public var obj:*;

    public var prev:HashMapNode;
    public var next:HashMapNode;

    public function HashMapNode(key:* = null, obj:* = null, prev:HashMapNode = null, next:HashMapNode = null){
    this.key = key;
    this.obj = obj;
    this.prev = prev;
    this.next = next;
    }
    }
    }

    Map結構的介面，定義了一些Map結構該有的基本功能。

    /* Map.as */
    package xinyu.collection{
    public interface Map{
    function insert(key:*, obj:*):Boolean;
    function find(key:*):*;
    function remove(key:*):Boolean;
    function keySet():Array;
    function entrySet():Array;
    function clear():void;
    function isEmpty():Boolean;
    function iterator():Iterator;
    function containsValue(obj:*):Boolean;
    function containsKey(key:*):Boolean;
    }
    }

    有別於ploygonal的HashMap，我將Dictionary給移除，僅只有在entrySet()裡有使用到（回傳不重複的entrySet），其餘的操作皆以Double LinkedList結構來運作，目的是要控制key/value 的次序性，所以我還多了moveUp()跟moveDown()這兩個方法來移動entry的位置。

    /* HashMap.as */
    package xinyu.collection{
    import flash.utils.Dictionary;

    import xinyu.collection.Map;
    import xinyu.collection.HashMapNode;
    import xinyu.collection.Iterator;
    import xinyu.collection.HashIterator;

    public class HashMap implements Map {
    private var head:HashMapNode = new HashMapNode();
    private var tail:HashMapNode = new HashMapNode();

    public function HashMap() {
    head.next = tail;
    tail.prev = head;
    }

    public function insert(key:*, obj:*):Boolean {
    if (key == null || obj == null) return false;
    if (searchByKey(key) != null) return false;

    var node:HashMapNode = new HashMapNode(key, obj, tail.prev, tail);
    node.prev.next = node;
    tail.prev = node;

    return true;
    }

    public function find(key:*):*{
    var node:HashMapNode = searchByKey(key);
    if(node) return node.obj;
    return null;
    }

    public function remove(key:*):Boolean{
    var node:HashMapNode = searchByKey(key);
    if(node == null) return false;

    node.prev.next = node.next;
    node.next.prev = node.prev;
    return true;
    }

    public function keySet():Array{
    var array:Array = new Array();
    var curr:HashMapNode = head.next;

    while(curr!=tail){
    array.push(curr.key);
    curr = curr.next;
    }

    return array;
    }

    public function entrySet():Array{
    var array:Array = new Array();
    var node:HashMapNode = head.next;
    var dict:Dictionary = new Dictionary(true);

    while(node != tail){
    if(dict[node.obj] == undefined){
    dict[node.obj] = 1;
    array.push(node.obj);
    }
    node = node.next;
    }
    return array;
    }

    public function clear():void{
    var curr:HashMapNode = head.next;
    var nextPtr:*;
    while(curr!=tail){
    curr.key = null;
    curr.obj = null;
    nextPtr = curr.next;
    curr.next = curr.prev = null;
    curr = nextPtr;
    }

    head.next = tail;
    tail.prev = head;
    }

    public function swap(key1:*, key2:*):Boolean{
    if (key1 == null||key2 == null) return false;

    var node1:HashMapNode = searchByKey(key1);
    var node2:HashMapNode = searchByKey(key2);
    if(node1 == null || node2 == null) return false;

    var temp:HashMapNode = new HashMapNode();
    temp.key = node1.key;
    temp.obj = node1.obj;

    node1.key = node2.key;
    node1.obj = node2.obj;

    node2.key = temp.key;
    node2.obj = temp.obj;

    return true;
    }

    public function isEmpty():Boolean {
    if (head.next == tail) return true;
    return false;
    }

    public function moveUp(key:*):Boolean{
    if(key == null) return false;

    var node:HashMapNode = searchByKey(key);
    if(node == null) return false;
    if(node.prev == head) return false;

    return swap(key, node.prev.key);
    }

    public function moveDown(key:*):Boolean{
    if(key == null) return false;

    var node:HashMapNode = searchByKey(key);
    if(node == null) return false;
    if(node.next == tail) return false;

    return swap(key, node.next.key);
    }

    public function get size():int{
    var count:int = 0;
    var curr:HashMapNode = head.next;

    while(curr!=tail){
    count++;
    curr=curr.next;
    }

    return count;
    }

    public function containsKey(key:*):Boolean{
    if(searchByKey(key)) return true;
    return false;
    }

    public function containsValue(obj:*):Boolean{
    var curr:HashMapNode = new HashMapNode();
    curr = head.next;

    while(curr!=tail){
    if(curr.obj === obj) return true;
    curr = curr.next;
    }

    return false;
    }

    private function searchByKey(key:*):HashMapNode{
    var curr:HashMapNode = new HashMapNode();
    curr = head.next;

    while(curr!=tail){
    if(curr.key === key) return curr;
    curr = curr.next;
    }

    return null;
    }

    public function iterator():Iterator{
    return new HashIterator(head,tail);
    }
    }
    }

    Iterator介面的部份只有簡單定義幾個基本的功能。

    /* Iterator */
    package xinyu.collection{
    public interface Iterator{
    function hasNext():Boolean;
    function next():*;
    function remove():void;
    function rewind():void;
    }
    }

    HashIterator就依照著Iterator介面去實做，並沒有增加額外的功能，有別於Java的Iterator，我多了rewind()。因為我在其他設計專案中需要將iterator重新指向一開始，所以多了這個功能。

    /* HashIterator */
    package xinyu.collection{
    import xinyu.collection.Iterator;
    import xinyu.collection.HashMapNode;

    public class HashIterator implements Iterator{
    private var head:HashMapNode;
    private var tail:HashMapNode;
    private var curr:HashMapNode;

    public function HashIterator(head:HashMapNode, tail:HashMapNode){
    this.head = head;
    this.tail = tail;
    curr = head.next;
    }

    public function hasNext():Boolean{
    return (curr != tail);
    }

    public function next():*{
    if(curr != tail){
    var obj:* = curr.obj;
    curr = curr.next;
    return obj;
    }
    return null;
    }

    public function rewind():void{
    curr = head.next;
    }

    public function remove():void{
    tail.prev = tail.prev.prev;
    tail.prev.next = tail;
    }
    }
    }

    底下是一個很簡單的範例用來展示上面的HashMap的用法

    package{
    import flash.display.Sprite;

    import xinyu.collection.HashMap;
    import xinyu.collection.Iterator;
    import xinyu.collection.HashIterator;

    public class HashMapDemo extends Sprite{
    public function HashMapDemo(){
    var hashMap:HashMap = new HashMap();

    var obj1:Object = new Object();
    obj1.name = "object_1";
    var obj2:Object = new Object();
    obj2.name = "object_2";

    hashMap.insert("1", obj1);
    hashMap.insert("2", obj2);
    trace("isEmpty (after insertion): "+hashMap.isEmpty());
    trace("Size of hashmap: "+hashMap.size);

    trace("\nKeySet (before swap): "+hashMap.keySet());
    trace("Key 1's Object: "+hashMap.find("1").name);
    trace("Key 2's Object: "+hashMap.find("2").name);
    trace("EntrySet"+hashMap.entrySet());

    hashMap.swap("1","2");
    trace("\nKeySet (after swap): "+hashMap.keySet());
    trace("Key 1's Object: "+hashMap.find("1").name);
    trace("Key 2's Object: "+hashMap.find("2").name);


    trace("\nIteration result before move up the key 1:");
    var iter:Iterator = hashMap.iterator();
    while(iter.hasNext()){
    trace(iter.next().name);
    }

    hashMap.moveUp("1");

    trace("\nIteration result after move up the key 1:");
    iter.rewind();
    while(iter.hasNext()){
    trace(iter.next().name);
    }

    iter.remove();
    trace("\nSize of hashmap(after remove a node): "+hashMap.size);

    hashMap.clear();
    trace("\nisEmpty (after clear): "+hashMap.isEmpty());
    trace("Size of hashmap: "+hashMap.size);
    }
    }
    }

    輸出畫面如下：

    isEmpty (after insertion): false
    Size of hashmap: 2

    KeySet (before swap): 1,2
    Key 1's Object: object_1
    Key 2's Object: object_2
    EntrySet[object Object],[object Object]

    KeySet (after swap): 2,1
    Key 1's Object: object_1
    Key 2's Object: object_2

    Iteration result before move up the key 1:
    object_2
    object_1

    Iteration result after move up the key 1:
    object_1
    object_2

    Size of hashmap(after remove a node): 1

    isEmpty (after clear): true
    Size of hashmap: 0

-
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Orange - data analysis tool

Installation pip install orange3 Run orange python -m Orange.canvas

  • [C/C++] Socket Connection
    Socket Connection 節錄自筆者的Network Programming其中的資料，一般在Windows底下如果要寫網路程式多半會想到Microsoft MFC提供的相關API，而Linux底下則多使用Unix Socket來實現，這裡筆者要簡短的介紹如何使用最基礎...
  • [C/C++] system("pause") for linux
    system("pause") for linux 在windows底下如果不想藉由開發工具做debug時，筆者我多數使用system("pause")這個指令，但是一到了linux之後，這個指令完全無效，因為linux的termainl底...
  • [C/C++] pthread-win32
    pthread-win32 Download: pthread_win32.zip pthread這麼好用的一個API要是能夠在Windows底下執行也能開發那該有多好，感謝有人去做這個API的平台移植，現在你可以到下面這個網頁去下載pthread-win32，讓你在Window...