Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #36641

Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*?

Show key headers only | View raw

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;
     }
}

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? latencyfighter@mail.com - 2017-05-13 20:21 -0700
  Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? lewbloch@gmail.com - 2017-05-14 08:48 -0700
    Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? J Crawford <latencyfighter@mail.com> - 2017-05-14 10:55 -0700
      Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? Arne Vajhøj <arne@vajhoej.dk> - 2017-05-16 20:56 -0400
        Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? Arne Vajhøj <arne@vajhoej.dk> - 2017-05-17 15:35 -0400
    Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? v_borchert@despammed.com (Volker Borchert) - 2017-05-14 17:09 +0000

csiph-web