Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file distributed with this work for additional information regarding copyright ownership. The ASF licenses this file to You under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
 
 
 package org.apache.mahout.cf.taste.impl.common;
 
 
 import java.util.Map;
 import java.util.Set;

 
 public final class FastByIDMap<V> implements SerializableCloneable {
 
   public static final int NO_MAX_SIZE = .;
   private static final double ALLOWED_LOAD_FACTOR = 1.5;

  
Dummy object used to represent a key that has been removed.
 
   private static final long REMOVED = .;
   private static final long NULL = .;
 
   private long[] keys;
   private V[] values;
   private int numEntries;
   private int numSlotsUsed;
   private int maxSize;
   private BitSet recentlyAccessed;
   private final boolean countingAccesses;

  
Creates a new FastByIDMap with default capacity.
 
   public FastByIDMap() {
     this(2, );
   }
 
   public FastByIDMap(int size) {
     this(size);
   }

  
Creates a new FastByIDMap whose capacity can accommodate the given number of entries without rehash.

Parameters:
size desired capacity
maxSize max capacity
Throws:
java.lang.IllegalArgumentException if size is less than 0, maxSize is less than 1, or at least half of org.apache.mahout.common.RandomUtils.MAX_INT_SMALLER_TWIN_PRIME
 
   @SuppressWarnings("unchecked")
   public FastByIDMap(int sizeint maxSize) {
     if (size < 0) {
       throw new IllegalArgumentException("size must be at least 0");
     }
     int max = (int) (. / );
     if (size >= max) {
       throw new IllegalArgumentException("size must be less than " + max);
     }
     if (maxSize < 1) {
       throw new IllegalArgumentException("maxSize must be at least 1");
     }
     int hashSize = RandomUtils.nextTwinPrime((int) ( * size));
      = new long[hashSize];
     Arrays.fill();
      = (V[]) new Object[hashSize];
     this. = maxSize;
     this. = maxSize != .;
     this. =  ? new BitSet(hashSize) : null;
   }
 
   private int find(long key) {
     int theHashCode = (intkey & 0x7FFFFFFF; // make sure it's positive
     long[] keys = this.;
     int hashSize = keys.length;
     int jump = 1 + theHashCode % (hashSize - 2);
     int index = theHashCode % hashSize;
     long currentKey = keys[index];
     while (currentKey !=  && (currentKey ==  || key != currentKey)) {
       if (index < jump) {
         index += hashSize - jump;
      } else {
        index -= jump;
      }
      currentKey = keys[index];
    }
    return index;
  }
  public V get(long key) {
    if (key == ) {
      return null;
    }
    int index = find(key);
    if () {
      .set(index);
    }
    return [index];
  }
  public int size() {
    return ;
  }
  public boolean isEmpty() {
    return  == 0;
  }
  public boolean containsKey(long key) {
    return key !=  && key !=  && [find(key)] != ;
  }
  public boolean containsValue(Object value) {
    if (value == null) {
      return false;
    }
    for (V theValue : ) {
      if (theValue != null && value.equals(theValue)) {
        return true;
      }
    }
    return false;
  }
  public V put(long key, V value) {
    if (key ==  || key == ) {
      throw new IllegalArgumentException();
    }
    if (value == null) {
      throw new NullPointerException();
    }
    // If less than half the slots are open, let's clear it up
      // If over half the slots used are actual entries, let's grow
      if ( *  >= ) {
        growAndRehash();
      } else {
        // Otherwise just rehash to clear REMOVED entries and don't grow
        rehash();
      }
    }
    // Here we may later consider implementing Brent's variation described on page 532
    int index = find(key);
    if ([index] == ) {
      // If size is limited,
      if ( &&  >= ) {
        // and we're too large, clear some old-ish entry
        clearStaleEntry(index);
      }
      [index] = key;
      [index] = value;
      ++;
      ++;
      return null;
    } else {
      V oldValue = [index];
      [index] = value;
      return oldValue;
    }
  }
  private void clearStaleEntry(int index) {
    while (true) {
      long currentKey;
      do {
        if (index == 0) {
          index = . - 1;
        } else {
          index--;
        }
        currentKey = [index];
      } while (currentKey ==  || currentKey == );
      if (.get(index)) {
        .clear(index);
      } else {
        break;
      }
    }
    // Delete the entry
    [index] = ;
    --;
    [index] = null;
  }
  public V remove(long key) {
    if (key ==  || key == ) {
      return null;
    }
    int index = find(key);
    if ([index] == ) {
      return null;
    } else {
      [index] = ;
      --;
      V oldValue = [index];
      [index] = null;
      // don't decrement numSlotsUsed
      return oldValue;
    }
    // Could un-set recentlyAccessed's bit but doesn't matter
  }
  public void clear() {
     = 0;
     = 0;
    Arrays.fill();
    Arrays.fill(null);
    if () {
      .clear();
    }
  }
    return new KeyIterator();
  }
  public Set<Map.Entry<Long, V>> entrySet() {
    return new EntrySet();
  }
  public void rehash() {
    rehash(RandomUtils.nextTwinPrime((int) ( * )));
  }
  private void growAndRehash() {
      throw new IllegalStateException("Can't grow any more");
    }
    rehash(RandomUtils.nextTwinPrime((int) ( * .)));
  }
  private void rehash(int newHashSize) {
    long[] oldKeys = ;
    V[] oldValues = ;
     = 0;
     = 0;
    if () {
       = new BitSet(newHashSize);
    }
     = new long[newHashSize];
    Arrays.fill();
     = (V[]) new Object[newHashSize];
    int length = oldKeys.length;
    for (int i = 0; i < lengthi++) {
      long key = oldKeys[i];
      if (key !=  && key != ) {
        put(keyoldValues[i]);
      }
    }
  }
  void iteratorRemove(int lastNext) {
    if (lastNext >= .) {
      throw new NoSuchElementException();
    }
    if (lastNext < 0) {
      throw new IllegalStateException();
    }
    [lastNext] = null;
    [lastNext] = ;
    --;
  }
  public FastByIDMap<V> clone() {
    FastByIDMap<V> clone;
    try {
      clone = (FastByIDMap<V>) super.clone();
    } catch (CloneNotSupportedException cnse) {
      throw new AssertionError();
    }
    clone.keys = .clone();
    clone.values = .clone();
    clone.recentlyAccessed =  ? new BitSet(.) : null;
    return clone;
  }
  public String toString() {
    if (isEmpty()) {
      return "{}";
    }
    StringBuilder result = new StringBuilder();
    result.append('{');
    for (int i = 0; i < .i++) {
      long key = [i];
      if (key !=  && key != ) {
        result.append(key).append('=').append([i]).append(',');
      }
    }
    result.setCharAt(result.length() - 1, '}');
    return result.toString();
  }
  private final class KeyIterator extends AbstractLongPrimitiveIterator {
    private int position;
    private int lastNext = -1;
    @Override
    public boolean hasNext() {
      goToNext();
      return  < .;
    }
    @Override
    public long nextLong() {
      goToNext();
       = ;
      if ( >= .) {
        throw new NoSuchElementException();
      }
      return [++];
    }
    @Override
    public long peek() {
      goToNext();
      if ( >= .) {
        throw new NoSuchElementException();
      }
      return [];
    }
    private void goToNext() {
      int length = .;
      while ( < length && [] == null) {
        ++;
      }
    }
    @Override
    public void remove() {
    }
    @Override
    public void skip(int n) {
       += n;
    }
  }
  private final class EntrySet extends AbstractSet<Map.Entry<Long, V>> {
    @Override
    public int size() {
      return FastByIDMap.this.size();
    }
    @Override
    public boolean isEmpty() {
      return FastByIDMap.this.isEmpty();
    }
    @Override
    public boolean contains(Object o) {
      return containsKey((Longo);
    }
    @Override
    public Iterator<Map.Entry<Long, V>> iterator() {
      return new EntryIterator();
    }
    @Override
    public boolean add(Map.Entry<Long, V> t) {
      throw new UnsupportedOperationException();
    }
    @Override
    public boolean remove(Object o) {
      throw new UnsupportedOperationException();
    }
    @Override
    public boolean addAll(Collection<? extends Map.Entry<Long, V>> ts) {
      throw new UnsupportedOperationException();
    }
    @Override
    public boolean retainAll(Collection<?> objects) {
      throw new UnsupportedOperationException();
    }
    @Override
    public boolean removeAll(Collection<?> objects) {
      throw new UnsupportedOperationException();
    }
    @Override
    public void clear() {
      FastByIDMap.this.clear();
    }
    private final class MapEntry implements Map.Entry<Long, V> {
      private final int index;
      private MapEntry(int index) {
        this. = index;
      }
      @Override
      public Long getKey() {
        return [];
      }
      @Override
      public V getValue() {
        return [];
      }
      @Override
      public V setValue(V value) {
        if (value == null) {
          throw new IllegalArgumentException();
        }
        V oldValue = [];
        [] = value;
        return oldValue;
      }
    }
    private final class EntryIterator implements Iterator<Map.Entry<Long, V>> {
      private int position;
      private int lastNext = -1;
      @Override
      public boolean hasNext() {
        goToNext();
        return  < .;
      }
      @Override
      public Map.Entry<Long, V> next() {
        goToNext();
         = ;
        if ( >= .) {
          throw new NoSuchElementException();
        }
        return new MapEntry(++);
      }
      private void goToNext() {
        int length = .;
        while ( < length && [] == null) {
          ++;
        }
      }
      @Override
      public void remove() {
        iteratorRemove();
      }
    }
  }
New to GrepCode? Check out our FAQ X