Commits

Michael Ludwig committed 08d1a68

Implement EntitySetComponent relying only on primitive int[] and binary search.

  • Participants
  • Parent commits 2fce329

Comments (0)

Files changed (1)

File ferox-scene/src/main/java/com/ferox/scene/EntitySetComponent.java

 package com.ferox.scene;
 
 import java.util.Arrays;
-import java.util.HashSet;
-import java.util.Set;
 
-import com.googlecode.entreri.Component;
-import com.googlecode.entreri.EntitySystem;
-import com.googlecode.entreri.property.Factory;
-import com.googlecode.entreri.property.IntProperty;
-import com.googlecode.entreri.property.ObjectProperty;
-import com.googlecode.entreri.property.Parameter;
-import com.googlecode.entreri.property.PropertyFactory;
+import com.lhkbob.entreri.ComponentData;
+import com.lhkbob.entreri.annot.ElementSize;
+import com.lhkbob.entreri.annot.Factory;
+import com.lhkbob.entreri.property.IntProperty;
+import com.lhkbob.entreri.property.ObjectProperty;
+import com.lhkbob.entreri.property.PropertyFactory;
 
-public abstract class EntitySetComponent extends Component {
-    private static final int CACHE_SIZE = 9;
+public abstract class EntitySetComponent<T extends EntitySetComponent<T>> extends ComponentData<T> {
+    private static final int CACHE_SIZE = 6;
+    private static final int CACHE_OFFSET = 2;
+    private static final int SCALE = CACHE_SIZE + CACHE_OFFSET;
     
-    @Parameter(type=int.class, value="9")
-    private IntProperty firstCache; // 0 = size, 1-9 = up to 8 cached entity ids
+    @ElementSize(SCALE)
+    private IntProperty firstCache; // 0 = 1st size, 1 = 2nd size, and 6 cached entity ids
+
+    // entity ids that don't fit in firstCache, the length of the array is 
+    // greater than or equal to the second cache size at offset 1
+    @Factory(CloningFactory.class)
+    private ObjectProperty<int[]> secondCache; 
     
-    @Factory(CloningFactory.class)
-    private ObjectProperty<Set<Integer>> secondCache; // entity ids that don't fit in firstCache
+    protected EntitySetComponent() { }
     
-    protected EntitySetComponent(EntitySystem system, int index) {
-        super(system, index);
+    protected boolean contains(int entityId) {
+        final int[] ids = firstCache.getIndexedData();
+        final int index = getIndex() * SCALE;
+        
+        int size = ids[index];
+        if (contains(entityId, ids, index + CACHE_OFFSET, index + size + CACHE_OFFSET))
+            return true;
+        
+        size = ids[index + 1];
+        if (size > 0)
+            return contains(entityId, secondCache.get(getIndex(), 0), 0, size);
+        
+        return false;
     }
     
-    @Override
-    protected void init(Object... initParams) {
-        // make sure count says 0, to begin with
-        // we don't care about other indices
-        firstCache.set(0, getIndex(), 0);
-        
-        secondCache.set(null, getIndex(), 0);
+    private boolean contains(int entityId, int[] array, int from, int to) {
+        return Arrays.binarySearch(array, from, to, entityId) >= 0;
     }
     
-    protected boolean contains(int entityId) {
-        int index = getIndex();
+    private int put(int entityId, int[] array, int cacheSize, int from, int to) {
+        int maxSize = to - from;
+        if (cacheSize == 0 || (cacheSize < maxSize - 1 && entityId > array[from + cacheSize - 1])) {
+            // append the entity to the end, since there is room, and it will
+            // remain in sorted order.
+            // - since the size was 0, or it the entity was strictly greater than
+            //   the previously greatest item we know it hasn't been seen before
+            array[from + cacheSize] = entityId;
+            return -1;
+        }
         
-        int[] ids = firstCache.getIndexedData();
-        int size = ids[index * CACHE_SIZE];
-        int discoveredIndex = Arrays.binarySearch(ids, index * CACHE_SIZE + 1, index * CACHE_SIZE + size + 1, entityId);
-        if (discoveredIndex >= 0)
-            return true;
+        // search for the insert index into the array, to maintain sorted order
+        int insertIndex = Arrays.binarySearch(array, from, from + cacheSize, entityId);
+        if (insertIndex >= 0) {
+            // the entity is already in this array
+            return -1;
+        }
+        insertIndex = -insertIndex + 1; // convert to the actual index it should be
         
-        // not found in first cache, check second
-        Set<Integer> objCache = secondCache.get(index, 0);
-        return (objCache != null ? objCache.contains(entityId) : false);
+        if (insertIndex < to) {
+            // the entity belongs within this array
+            int evicted = -1;
+            int shift = from + cacheSize;
+            
+            if (cacheSize == maxSize) {
+                // in order to insert the new entity, the last entity gets evicted,
+                // so we decrement the shift to prevent bleeding into outside indices,
+                // and remember the last element to return
+                evicted = array[--shift];
+            }
+            
+            // we can safely shift and insert the entity
+            for (int i = shift; i > insertIndex; i--)
+                array[i] = array[i - 1];
+            array[insertIndex] = entityId;
+
+            return evicted;
+        } else {
+            // the array has no more room, so return the entity id to signal
+            // it must be added to another array
+            return entityId;
+        }
     }
     
     protected void put(int entityId) {
-        int index = getIndex();
+        int[] ids = firstCache.getIndexedData();
+        int index = getIndex() * SCALE;
         
-        int[] ids = firstCache.getIndexedData();
-        int size = ids[index * CACHE_SIZE];
-        
-        int discoveredIndex = Arrays.binarySearch(ids, index * CACHE_SIZE + 1, index * CACHE_SIZE + size + 1, entityId);
-        if (discoveredIndex >= 0)
-            return; // already found it
-        
-        if (size < CACHE_SIZE - 1) {
-            // have room in the int cache, insert 
-            int insertIndex = -discoveredIndex + 1;
+        int secondInsert = put(entityId, ids, ids[index], index + CACHE_OFFSET, index + CACHE_OFFSET + CACHE_SIZE);
+        if (secondInsert < 0) {
+            // entityId was successfully inserted into the first cache,
+            // so we have to increment the size
+            ids[index]++;
+        } else {
+            // secondInsert must be added to the second cache, this might
+            // be the new entity or an evicted entity
+            int[] ids2 = secondCache.get(getIndex(), 0);
+            int size = ids[index + 1];
             
-            // shift over all other entity ids
-            for (int i = index * CACHE_SIZE + size + 1; i > insertIndex; i--)
-                ids[i] = ids[i - 1];
-            ids[insertIndex] = entityId; // store in cache
-            ids[index * CACHE_SIZE] = size + 1; // update size count
-        } else {
-            // must use secondary cache
-            Set<Integer> objCache = secondCache.get(index, 0);
-            if (objCache == null) {
-                objCache = new HashSet<Integer>();
-                secondCache.set(objCache, index, 0);
+            if (ids2 == null || size == ids2.length) {
+                // expand the 2nd cache
+                int[] newIds2 = new int[size + CACHE_SIZE];
+                for (int i = 0; i < size; i++)
+                    newIds2[i] = ids[i];
+                ids2 = newIds2;
+                secondCache.set(newIds2, getIndex(), 0);
             }
             
-            objCache.add(entityId);
+            if (put(secondInsert, ids2, size, 0, ids2.length) < 0) {
+                // entity was added to the second cache, so update that size
+                ids[index + 1]++;
+            } // otherwise entity was in the 2nd cache already
         }
     }
     
     protected void remove(int entityId) {
-        int index = getIndex();
+        int index = getIndex() * SCALE;
+        int[] ids = firstCache.getIndexedData();
         
-        int[] ids = firstCache.getIndexedData();
-        int size = ids[index * CACHE_SIZE];
-        
-        int discoveredIndex = Arrays.binarySearch(ids, index * CACHE_SIZE + 1, index * CACHE_SIZE + size + 1, entityId);
-        if (discoveredIndex >= 0) {
-            // found it in first cache, so remove it
-            
-            // shift over all other entity ids
-            for (int i = discoveredIndex; i < index * CACHE_SIZE + size; i++)
-                ids[i] = ids[i + 1];
-            ids[index * CACHE_SIZE] = size - 1; // update size count
+        int firstSize = ids[index];
+        if (remove(entityId, ids, index + CACHE_OFFSET, index + CACHE_OFFSET + firstSize)) {
+            // entity was removed from the first cache, so the size must be updated
+            // or an element moved from the second to the first if available
+            if (ids[index + 1] > 0) {
+                // transfer from second to first cache
+                int[] second = secondCache.get(getIndex(), 0);
+                ids[index + CACHE_OFFSET + CACHE_SIZE - 1] = second[0];
+                // shift over remaining values
+                for (int i = ids[index + 1] - 1; i > 0; i--)
+                    ids[i - 1] = ids[i];
+                ids[index + 1]--;
+            } else {
+                // decrease size of first cache
+                ids[index]--;
+            }
         } else {
-            // check secondary cache
-            Set<Integer> objCache = secondCache.get(index, 0);
-            if (objCache != null)
-                objCache.remove(entityId);
+            // entity might be in the second cache
+            if (ids[index + 1] > 0) {
+                if (remove(entityId, secondCache.get(getIndex(), 0), 0, ids[index + 1]))
+                    ids[index + 1]--;
+            }
+        }
+    }
+    
+    protected boolean remove(int entityId, int[] array, int from, int to) {
+        int index = Arrays.binarySearch(array, from, to, entityId);
+        if (index >= 0) {
+            // found it in this array
+            if (index < to - 1) {
+                // shift over elements when not removing the last element
+                for (int i = index; i < to; i++)
+                    array[i] = array[i + 1];
+            }
+            return true;
+        } else {
+            // not in this array
+            return false;
         }
     }
     
     protected void clear() {
-        int index = getIndex();
+        int index = getIndex() * SCALE;
 
-        // reset first cache count to 0, and null the second cache
-        firstCache.getIndexedData()[index * CACHE_SIZE] = 0;
+        // reset cache counts to 0, and null the second cache
+        firstCache.getIndexedData()[index] = 0;
+        firstCache.getIndexedData()[index + 1] = 0;
         secondCache.set(null, index, 0);
     }
 
     /**
      * A PropertyFactory with copying semantics for the visibility set.
      */
-    // FIXME: figure out a way to make this private
-    public static class CloningFactory implements PropertyFactory<ObjectProperty<Set<Integer>>> {
+    private static class CloningFactory implements PropertyFactory<ObjectProperty<int[]>> {
         @Override
-        public ObjectProperty<Set<Integer>> create() {
-            return new ObjectProperty<Set<Integer>>(1);
+        public ObjectProperty<int[]> create() {
+            return new ObjectProperty<int[]>(1);
         }
 
         @Override
-        public void setValue(ObjectProperty<Set<Integer>> property, int index) {
+        public void setDefaultValue(ObjectProperty<int[]> property, int index) {
             property.set(null, index, 0);
         }
 
         @Override
-        public void clone(ObjectProperty<Set<Integer>> src, int srcIndex,
-                          ObjectProperty<Set<Integer>> dst, int dstIndex) {
-            Set<Integer> original = src.get(srcIndex, 0);
+        public void clone(ObjectProperty<int[]> src, int srcIndex, ObjectProperty<int[]> dst,
+                          int dstIndex) {
+            int[] original = src.get(srcIndex, 0);
             if (original != null)
-                dst.set(new HashSet<Integer>(original), dstIndex, 0);
+                dst.set(Arrays.copyOf(original, original.length), dstIndex, 0);
             else
                 dst.set(null, dstIndex, 0);
         }