Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: =?UTF-8?Q?Arne_Vajh=c3=b8j?= <arne@vajhoej.dk>
Newsgroups: comp.lang.java.programmer
Subject: Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*?
Date: Wed, 17 May 2017 15:35:23 -0400
Organization: Aioe.org NNTP Server
Lines: 200
Message-ID: <ofi8lp$1q4d$1@gioia.aioe.org>
References: <cb71d7e4-c6fb-4716-9506-588247d35b4a@googlegroups.com> <07a2714d-79c4-4a77-834d-261c1b8bf3e2@googlegroups.com> <a735f04b-d2a4-4157-908c-b08ed95f51ab@googlegroups.com> <ofg73d$dje$1@gioia.aioe.org>
NNTP-Posting-Host: PBuS014lhzVyHjLbXmo/ZQ.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Complaints-To: abuse@aioe.org
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.lang.java.programmer:36641

On 5/16/2017 8:56 PM, Arne Vajhøj wrote:
> Just for the fun of it I tried writing a Map implementation
> with no allocation in put ever. It is not nice code. And
> I have not tested it. But just in case - it is attached below.

And below if you always want int key and can live with not
implementing Map.

Arne

package intmap;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

// Map implementation not allocating objects in put and not requiring 
boxing of int key
// not good code - very limited functionality and very old style
public class IntMap<T> {
     private int maxsize;
     private int[] keys;
     private Object[] values;
     private int[] next;
     private int scale;
     private int free;
     private int count;
     private void add(int key, Object value, int ix) {
         keys[ix] = key;
         values[ix] = value;
         count++;
     }
     private void move(int target, int source) {
         if(source < scale) {
             keys[target] = 0;
             values[target] = null;
             next[target] = 0;
         } else {
             keys[target] = keys[source];
             values[target] = values[source];
             move(source, next[source]);
         }
     }
     public void dump() {
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 System.err.printf("%d : %d %s %d\n", i, keys[i], 
values[i].toString(), next[i]);
             }
         }
     }
     public IntMap(int maxsize) {
         this.maxsize = maxsize;
         keys = new int[maxsize];
         values = new Object[maxsize];
         next = new int[maxsize];
         scale = maxsize / 2;
         free = scale;
         count = 0;
     }
     public int size() {
         return count;
     }
     public boolean isEmpty() {
         return (count == 0);
     }
     public boolean containsKey(int key) {
         return (get(key) != null);
     }
     public boolean containsValue(Object value) {
         throw new RuntimeException("Not implemented yet");
     }
     @SuppressWarnings("unchecked")
     public T get(int key) {
         if(key == 0) {
             throw new RuntimeException("Key zero not allowed");
         }
         int ix = key % scale;
         if(keys[ix] == 0) {
             return null;
         } else {
             do {
                 if(keys[ix] == key) {
                     return (T)values[ix];
                 } else {
                     ix = next[ix];
                 }
             } while(ix >= scale);
             return null;
         }
     }
     @SuppressWarnings("unchecked")
     public T put(int key, T value) {
         if(key == 0) {
             throw new RuntimeException("Key zero not allowed");
         }
         int ix = key % scale;
         int oldix;
         if(keys[ix] == 0) {
             add(key, value, ix);
             return null;
         } else {
             do {
                 if(keys[ix] == key) {
                     Object res = values[ix];
                     values[ix] = value;
                     return (T)res;
                 } else {
                     oldix = ix;
                     ix = next[ix];
                 }
             } while(ix >= scale);
             if(free >= maxsize) {
                 throw new RuntimeException("Maximum size exceeded");
             }
             add(key, value, free);
             next[oldix] = free;
             free++;
             return null;
         }
     }
     @SuppressWarnings("unchecked")
     public T remove(int key) {
         if(key == 0l) {
             throw new RuntimeException("Key zero not allowed");
         }
         int ix = key % scale;
         if(keys[ix] == 0) {
             return null;
         } else {
             do {
                 if(keys[ix] == key) {
                     Object res = values[ix];
                     move(ix, next[ix]);
                     count--;
                     while(free > scale && keys[free-1] == 0) {
                         free--;
                     }
                     return (T)res;
                 } else {
                     ix = next[ix];
                 }
             } while(ix >= scale);
             return null;
         }
     }
     public void putAll(IntMap<? extends T> m) {
         Iterator<? extends Map.Entry<Integer, ? extends T>> it = 
m.entrySet().iterator();
         while(it.hasNext()) {
             Map.Entry<Integer, ? extends T> ent = it.next();
             put(ent.getKey(), ent.getValue());
         }
     }
     public void clear() {
         for(int i = 0; i < maxsize; i++) {
             keys[i] = 0;
             values[i] = null;
             next[i] = 0;
         }
         free = scale;
         count = 0;
     }
     public Set<Integer> keySet() {
         Set<Integer> res = new HashSet<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 res.add(keys[i]);
             }
         }
         return res;
     }
     @SuppressWarnings("unchecked")
     public Collection<T> values() {
         List<T> res = new ArrayList<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 res.add((T)values[i]);
             }
         }
         return res;
     }
     @SuppressWarnings("unchecked")
     public Set<Map.Entry<Integer,T>> entrySet() {
         Set<Map.Entry<Integer,T>> res = new HashSet<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 res.add(new AbstractMap.SimpleEntry<Integer,T>(keys[i], 
(T)values[i]));
             }
         }
         return res;
     }
}