Collections Data Structure Java


 *
 * @see TrieMap
 * @see IntegerMap
 * @see Map
 * 
 * @author David Jurgens
 */
public class CharMap extends AbstractMap 
        implements java.io.Serializable {
    
    private static final long serialVersionUID = 1L;
    /**
     * The keys stored in this map, in sorted order.  The index at which a key
     * is found corresponds to the index at which its value is found.
     */
    char[] keyIndices;
    /**
     * The values stored in this map.
     */
    Object[] values;
    /**
     * Creates a new map.
     */
    public CharMap() {
  keyIndices = new char[0];
  values = new Object[0];
    }
    /**
     * Creates a new map with the mappings contained in {@code m}.
     */
    public CharMap(Map m) {
  // Pre-allocate the arrays for all the mappings needed instead of just
  // one at time
  keyIndices = new char[m.size()];
  values = new Object[m.size()];
  // Get all of the integer keys and sort them to their correct position
  // in the key array
  Iterator it = m.keySet().iterator();
  for (int i = 0; i < m.size(); ++i) {
      keyIndices[i] = it.next();
  }
  Arrays.sort(keyIndices);
  // Then map the values to their respective positions
  for (int i = 0; i < keyIndices.length; ++i) {
      values[i] = m.get(keyIndices[i]);
  }
    }
    
    /**
     * Checks that the key is non-{@code null} and is an {@code Integer} object,
     * and then returns its {@code int} value.
     */
    private char checkKey(Object key) {
  if (key == null) {
      throw new NullPointerException("key cannot be null");
  } else if (!(key instanceof Character)) {
      throw new IllegalArgumentException("key must be an Character");
  }
  else {
      return ((Character)key).charValue();
  }
    }
    /**
     * Removes all of the mappings from this map.
     */
    public void clear() {
  keyIndices = new char[0];
  values = new Object[0];
    }
    /**
     * Returns {@code true} if this map contains a mapping for the specified key.
     */
    public boolean containsKey(Object key) {
  char k = checkKey(key);
  int index = Arrays.binarySearch(keyIndices, k);
  return index >= 0;
    }
    public boolean containsValue(Object value) {
  for (Object o : values) {
      if (o == value || (o != null && o.equals(value))) {
    return true;
      }
  }
  return false;
    }
    /**
     * Returns a {@link Set} view of the mappings contained in this map.
     */
    public Set> entrySet() {
  return new EntrySet();
    }
    /**
     * Returns the value to which the specified key is mapped, or {@code null}
     * if this map contains no mapping for the key.
     */  
    public V get(Object key) {
  char k = checkKey(key);
  return get(k);
    }
    /**
     * Returns the value to which the specified key is mapped, or {@code null}
     * if this map contains no mapping for the key.
     */
    @SuppressWarnings("unchecked")  
    public V get(char key) {
  int pos = Arrays.binarySearch(keyIndices, key);
  return (pos >= 0) ? (V)(values[pos]) : null;  
    }
    /**
     * Returns a {@link Set} view of the keys contained in this map.
     */
    public Set keySet() {
  return new KeySet();
    }
    /**
     * Adds the mapping from the provided key to the value.
     *
     * @param key
     * @param value
     *
     * @throws NullPointerException if the key is {@code null}
     * @throws IllegalArgumentException if the key is not an instance of {@link
     *         Integer}
     */
    public V put(Character key, V value) {
  char k = checkKey(key);
        return put(k, value);
    }
    /**
     * Adds the mapping from the provided key to the value.
     *
     * @param key
     * @param value
     *
     * @throws NullPointerException if the key is {@code null}
     * @throws IllegalArgumentException if the key is not an instance of {@link
     *         Integer}
     */
    @SuppressWarnings("unchecked")
    public V put(char key, V value) {
        char k = key;
  int index = Arrays.binarySearch(keyIndices, k);
  if (index >= 0) {
      V old = (V)(values[index]);
      values[index] = value;
      return old;
  }
  else {
      int newIndex = 0 - (index + 1);      
      Object[] newValues = Arrays.copyOf(values, values.length + 1);
      char[] newIndices = Arrays.copyOf(keyIndices, values.length + 1);
      // shift the elements down to make room for the new value
      for (int i = newIndex; i < values.length; ++i) {
    newValues[i+1] = values[i];
    newIndices[i+1] = keyIndices[i];
      }
      // insert the new value
      newValues[newIndex] = value;
      newIndices[newIndex] = k;
      // switch the arrays with the lengthed versions
      values = newValues;
      keyIndices = newIndices;
      
      return null;
  }
    }
    /**
     * Removes the mapping for a key from this map if it is present and returns
     * the value to which this map previously associated the key, or {@code
     * null} if the map contained no mapping for the key.
     *
     * @param key key whose mapping is to be removed from the map 
     *
     * @return the previous value associated with key, or {@code null} if there
     * was no mapping for key.
     */
    @SuppressWarnings("unchecked")    
    public V remove(Object key) {
  char k = checkKey(key);
        return remove(k);
    }
    /**
     * Removes the mapping for a key from this map if it is present and returns
     * the value to which this map previously associated the key, or {@code
     * null} if the map contained no mapping for the key.
     *
     * @param key key whose mapping is to be removed from the map 
     *
     * @return the previous value associated with key, or {@code null} if there
     * was no mapping for key.
     */
    @SuppressWarnings("unchecked")    
    public V remove(char key) {
        char k = key;
  int index = Arrays.binarySearch(keyIndices, k);
  if (index >= 0) {
      V old = (V)(values[index]);
      Object[] newValues = Arrays.copyOf(values, values.length - 1);
      char[] newIndices = Arrays.copyOf(keyIndices, keyIndices.length - 1);
      // shift the elements up to remove the values
      for (int i = index; i < values.length - 1; ++i) {
    newValues[i] = values[i+1];
    newIndices[i] = keyIndices[i+1];
      }
      // update the arrays with the shorted versions
      values = newValues;
      keyIndices = newIndices;
      return old;
  }
  return null;
    }
    /**
     * Returns the number of key-value mappings in this trie.
     */
    public int size() {
  return keyIndices.length;
    }
    /**
     * Returns a {@link Collection} view of the values contained in this map.
     */
    public Collection values() {
  return new Values();
    }
    private class EntryIterator extends CharMapIterator> {
  public Map.Entry next() {
      return nextEntry();
  }
  
    }
    private class KeyIterator extends CharMapIterator {
  public Character next() {
      return nextEntry().getKey();
  }
  
    }
    private class ValueIterator extends CharMapIterator {
  public V next() {
      return nextEntry().getValue();
  }
  
    }
    abstract class CharMapIterator implements Iterator {
  private int next;
  public CharMapIterator() {
      next = 0;
  }
  public boolean hasNext() {
      return next < size();
  }
  @SuppressWarnings("unchecked")
  public Entry nextEntry() {
      if (next >= size()) {
    throw new NoSuchElementException("no further elements");
      }
      char key = keyIndices[next];
      V value = (V)(values[next]);
      next++;
      return new CharEntry(key, value);
  }
  
  // REMINDER: this class needs to work with the actual indices for the
  // key and value to avoid the logrithmic lookup
  public void remove() {
      throw new UnsupportedOperationException();
  }
    }
    // REMINDER: this class needs to work with the actual indices for the key
    // and value to avoid the logrithmic lookup
    class CharEntry extends SimpleEntry {
  private static final long serialVersionUID = 1L;
  
  public CharEntry(char key, V value) {
      super(key, value);
  }
  public V setValue(V newValue) {
      return CharMap.this.put(getKey(), newValue);
  }
    }
    class EntrySet extends AbstractSet> {
  private static final long serialVersionUID = 1L;
  public void clear() {
      CharMap.this.clear();
  }
  public boolean contains(Object o) {
      if (o instanceof Map.Entry) {
    Map.Entry e = (Map.Entry)o;
    Object key = e.getKey();
    Object val = e.getValue();
    Object mapVal = CharMap.this.get(key);
    return mapVal == val || (val != null && val.equals(mapVal));
      }
      return false;
  }
  public Iterator> iterator() {
      return new EntryIterator();
  }
  
  public int size() {
      return CharMap.this.size();
  }
    }
    class KeySet extends AbstractSet {
  private static final long serialVersionUID = 1L;
  
  public KeySet() { }
  
  public void clear() {
      CharMap.this.clear();
  }
  public boolean contains(Object o) {
      return containsKey(o);
  }
  public Iterator iterator() {
      return new KeyIterator();
  }
  
  public boolean remove(Object o) {
      return CharMap.this.remove(o) != null;
  }
  public int size() {
      return CharMap.this.size();
  }
    }
    /**
     * A {@link Collection} view of the values contained in this trie.
     */
    private class Values extends AbstractCollection {
  private static final long serialVersionUID = 1L;
  
  public void clear() {
      CharMap.this.clear();
  }
  public boolean contains(Object o) {
      return containsValue(o);
  }
  
  public Iterator iterator() {
      return new ValueIterator();
  }
  
  public int size() {
      return CharMap.this.size();
  }
    }
    
}
/*
 * Copyright 2009 David Jurgens
 *
 * This file is part of the S-Space package and is covered under the terms and
 * conditions therein.
 *
 * The S-Space package is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as published
 * by the Free Software Foundation and distributed hereunder to you.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS" AND NO REPRESENTATIONS OR WARRANTIES,
 * EXPRESS OR IMPLIED ARE MADE.  BY WAY OF EXAMPLE, BUT NOT LIMITATION, WE MAKE
 * NO REPRESENTATIONS OR WARRANTIES OF MERCHANT- ABILITY OR FITNESS FOR ANY
 * PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE OR DOCUMENTATION
 * WILL NOT INFRINGE ANY THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER
 * RIGHTS.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see .
 */
/*
package edu.ucla.sspace.util;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import org.junit.Ignore;
import org.junit.Test;
import static org.junit.Assert.*;
// * A collection of unit tests for {@link CharMap} 
public class CharMapTests {
    
    @Test public void testConstructor() {
   CharMap m = new CharMap();
    }
    @Test public void testPut() {
  CharMap m = new CharMap();
  m.put('1', "1");
  String s = m.get('1');
  assertEquals("1", s);
    }
    @Test(expected=NullPointerException.class) 
    public void testPutNullKey() {
  CharMap m = new CharMap();
  m.put(null, "value");
    }
    public void testPutNullValue() {
  CharMap m = new CharMap();
  m.put('0', null);
  String s = m.get('0');
  assertEquals(null, s);
    }
    @Test public void testPutConflict() {
  CharMap m = new CharMap();
  m.put('1', "1");
  m.put('1', "2");
  String s = m.get('1');
  assertEquals("2", s);
    }
    @Test public void testProgressive() {
  CharMap m = new CharMap();
  assertEquals(0, m.size());
  int size = 1024;
  for (int i = 0; i < size; ++i) {
            
      m.put((char)i, Integer.valueOf(i));
      
      // check mapping
      for (Map.Entry e : m.entrySet()) {
    char p = e.getKey();
    Integer q = e.getValue();
    assertEquals(Integer.valueOf(p), q);
      }
  }
    }
    @Test public void testContainsKey() {
  CharMap m = new CharMap();
  m.put('1', "1");
  m.put('2', "2");
  assertTrue(m.containsKey('1'));
  assertTrue(m.containsKey('2'));
    }
    @Test public void testContainsKeyFalse() {
  CharMap m = new CharMap();
  m.put('1', "1");
  m.put('2', "2");
  assertFalse(m.containsKey('3'));
  assertFalse(m.containsKey('4'));
  assertFalse(m.containsKey('0'));
    }
    @Test public void testContainsValue() {
  CharMap m = new CharMap();
  m.put('1', "1");
  m.put('2', "2");
  assertTrue(m.containsValue("1"));
  assertTrue(m.containsValue("2"));
    }
    @Test public void testContainsValueFalse() {
  CharMap m = new CharMap();
  m.put('1', "1");
  m.put('2', "2");
  assertFalse(m.containsValue("3"));
  assertFalse(m.containsValue("4"));
  assertFalse(m.containsValue("5"));
    }
    @Test public void testKeySet() {
  CharMap m = new CharMap();
  m.put('1', "0");
  m.put('2', "1");
  m.put('3', "2");
  m.put('4', "3");
  m.put('5', "4");
  Set test = m.keySet();
  
  assertTrue(test.contains('1'));
  assertTrue(test.contains('2'));
  assertTrue(test.contains('3'));
  assertTrue(test.contains('4'));
  assertTrue(test.contains('5'));
  assertFalse(test.contains('0'));
  assertFalse(test.contains('6'));
    }
    @Test public void testKeyIterator() {
  CharMap m = new CharMap();
  m.put('0', "0");
  m.put('1', "1");
  m.put('2', "2");
  Set control = new HashSet();
  control.add('0');
  control.add('1');
  control.add('2');
  Set test = m.keySet();
  assertTrue(test.containsAll(control));
  assertTrue(control.containsAll(test));
    }
    @Test public void testValueIterator() {
  CharMap m = new CharMap();
  m.put('0', "0");
  m.put('1', "1");
  m.put('2', "2");
  Set control = new HashSet();
  control.add("0");
  control.add("1");
  control.add("2");
  Collection test = m.values();
  
  assertEquals(control.size(), test.size());
  for (String s : test) {      
      assertTrue(control.contains(s));
  }
    }
    @Test public void testIteratorHasNext() {
  
  CharMap m = new CharMap();
  Iterator it = m.keySet().iterator();
  assertFalse(it.hasNext());
  m.put('0', "0");
  m.put('1', "1");
  m.put('2', "2");
  it = m.keySet().iterator();
  Set control = new HashSet();
  while (it.hasNext()) {
      control.add(it.next());
  }
  Set test = m.keySet();
  assertTrue(test.containsAll(control));
  assertTrue(control.containsAll(test));
    }
    @Test(expected=NoSuchElementException.class)
    public void testIteratorNextError() {
  
  CharMap m = new CharMap();
  m.put('0', "0");
  Iterator it = m.keySet().iterator();
  it.next();
  it.next(); // error
    }
    @Test(expected=NoSuchElementException.class)
    public void testEmptyIntIteratorNextError() {
  
  CharMap m = new CharMap();
  Iterator it = m.keySet().iterator();
  it.next(); // error
    }
    @Test public void testRemove() {
  CharMap m = new CharMap();
  m.put('0', "0");
  assertTrue(m.containsKey('0'));
  m.remove('0');
  assertFalse(m.containsKey('0'));
  assertEquals(0, m.size());
    }
    @Test public void testMultipleRemoves() {
  CharMap m = new CharMap();
  Set control = new HashSet();
  
  LinkedList list = new LinkedList();
  for (int i = 0; i < 512; ++i) {
      list.add((char)i);
  }
  for (Character c : list) {
      m.put(c, String.valueOf(c));
      control.add(c);
  }
  assertEquals(control.size(), m.size());
  assertTrue(control.containsAll(m.keySet()));
  // remove half
  int half = control.size();
  for (int i = 0; i < half; ++i) {
      Character j = list.poll();
      control.remove(j);
      m.remove(j);
  }
  assertEquals(control.size(), m.size());
  assertTrue(control.containsAll(m.keySet()));  
    }    
    @Test public void testSize() {
  CharMap m = new CharMap();
  assertEquals(0, m.size());
  m.put('0', "0");
  assertEquals(1, m.size());
  m.put('1', "1");
  assertEquals(2, m.size());
  m.put('2', "2");
  assertEquals(3, m.size());
    }
    @Test public void testIsEmpty() {
  CharMap m = new CharMap();
  assertTrue(m.isEmpty());
  m.put('0', "0");
  assertFalse(m.isEmpty());
  
  m.clear();
  assertTrue(m.isEmpty());
    }
    @Test public void testClear() {
  CharMap m = new CharMap();
  m.put('0', "0");
  m.put('1', "1");
  m.put('2', "2");
  m.clear();
  assertEquals(0, m.size());
  assertFalse(m.containsKey('0'));
  assertFalse(m.containsKey('1'));
  assertFalse(m.containsKey('2'));
    }
    public static void main(String args[]) {
  org.junit.runner.JUnitCore.main(CharMapTests.class.getName());
    }
}
*/