Quadcap Embeddable Server

com/quadcap/util/collections/IntMap.java

Go to the documentation of this file.

package com.quadcap.util.collections;

/* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.util.Iterator;

/**
 * A map with integer keys
 *
 * @author Stan Bailes
 */
public class IntMap {
    int                         size;
    Entry[]                     entries;
    Entry                       freeList;
    
    public IntMap(int initSize) {
        this.size = initSize | 1;
        while (!isPrime(size)) size += 2;
        entries = new Entry[size];
    }
    
    public final Object get(int key) {
        int h = hash(key);
        for (Entry entry = entries[h]; entry != null; entry = entry.next) {
            if (entry.key == key) return entry.val;
        }
        return null;
    }

    public final void put(int key, Object val) {
        int h = hash(key);
        Entry entry = getEntry(key, val);
        entry.next = entries[h];
        entries[h] = entry;
    }

    public final void remove(int key) {
        int h = hash(key);
        Entry prev = null;
        for (Entry entry = entries[h]; entry != null; entry = entry.next) {
            if (entry.key == key) {
                if (prev == null) {
                    entries[h] = entry.next;
                } else {
                    prev.next = entry.next;
                }
                freeEntry(entry);
            }
            prev = entry;
        }
    }

    final Entry getEntry(int key, Object val) {
        Entry entry = freeList;
        if (entry == null) {
            entry = new Entry();
        } else {
            freeList = entry.next;
        }
        entry.key = key;
        entry.val = val;
        return entry;
    }

    final void freeEntry(Entry entry) {
        entry.next = freeList;
        freeList = entry;
    }

    public final static boolean isPrime(int x) {
        if ((x & 1) == 0) return false;
        for (int i = 3; i*i <= x; i += 2) {
            if ((x % i) == 0) return false;
        }
        return true;
    }

    public Iterator keys() {
        return new IntMapIterator(this);
    }

    final int hash(int key) {
        int h = key % size;
        if (h < 0) {
            h = 0 - h;
        }
        return h;
    }

    class Entry {
        int             key;
        Object          val;
        Entry           next;
    }

    class IntMapIterator implements Iterator {
        IntMap                  map;
        int                     epos            = 0;
        Entry                   entry           = null;
        
        public IntMapIterator(IntMap map) { this.map = map; }

        public boolean hasNext() {
            while (epos < map.size && entry == null) {
                entry = map.entries[epos++];
            }
            return entry != null;
        }

        public Object next() {
            Integer ret = null;
            if (hasNext()) {
                ret = new Integer(entry.key);
                entry = entry.next;
            }
            return ret;
        }

        public void remove() {}
    }
        
}