ozeigermann 2004/10/27 07:30:27
Added: proposals/dfa-cache/src/org/apache/slide/util
TableDFAMap.java DFAMap.java DFAMapTest.java
Log:
Added bad DFA map to keep anyone from trying it.
It does not work for realistically sized maps as too many states
get created.
Revision Changes Path
1.1
jakarta-slide/proposals/dfa-cache/src/org/apache/slide/util/TableDFAMap.java
Index: TableDFAMap.java
===================================================================
package org.apache.slide.util;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/*
* Created on 01.12.2003
*
* To change the template for this generated file go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
/**
* @author olli
*
* To change the template for this generated type comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
public class TableDFAMap implements Map {
String symbols;
State startState;
Map symbolsCache = null;
public TableDFAMap(String symbols) {
this.symbols = symbols;
// HACK
this.symbols = "key-valu0123456789";
startState = new State();
// createSymbolsCache();
}
void createSymbolsCache() {
symbolsCache = new HashMap();
for (int i = 0; i < symbols.length(); i++) {
char c = symbols.charAt(i);
symbolsCache.put(new Character(c), new Integer(i));
}
}
int charToSymbol(char c) {
// HACK
switch (c) {
case 'k' : return 0;
case 'e' : return 1;
case 'y' : return 2;
case '-' : return 3;
case 'v' : return 4;
case 'a' : return 5;
case 'l' : return 6;
case 'u' : return 7;
case '0' : return 8;
case '1' : return 9;
case '2' : return 10;
case '3' : return 11;
case '4' : return 12;
case '5' : return 13;
case '6' : return 14;
case '7' : return 15;
case '8' : return 16;
case '9' : return 17;
}
if (symbolsCache == null) {
for (int i = 0; i < symbols.length(); i++) {
if (symbols.charAt(i) == c) {
return i;
}
}
} else {
return ((Integer) symbolsCache.get(new
Character(c))).intValue();
}
throw new RuntimeException(
"character '" + c + "' is not part of symbols '" + symbols +
"'");
}
private class State {
Object value = null;
Object key = null;
State[] transitStates = new State[symbols.length()];
State transit(Character c) {
int symbol = charToSymbol(c.charValue());
return transitStates[symbol];
}
void putTransition(Character c, State state) {
int symbol = charToSymbol(c.charValue());
transitStates[symbol] = state;
}
Object get(char[] key, int pos) {
if (pos == key.length) {
return value;
} else {
Character c = new Character(key[pos]);
State nextState = transit(c);
if (nextState == null) {
return null;
} else {
return nextState.get(key, pos + 1);
}
}
}
Object remove(char[] key, int pos) {
// XXX simply overwrite
return put(key, pos, null);
}
Object put(char[] key, int pos, Object value) {
if (pos == key.length) {
this.key = new String(key);
Object oldValue = this.value;
this.value = value;
return oldValue;
} else {
Character c = new Character(key[pos]);
State nextState = transit(c);
if (nextState == null) {
nextState = new State();
putTransition(c, nextState);
}
return nextState.put(key, pos + 1, value);
}
}
}
/* (non-Javadoc)
* @see java.util.Map#size()
*/
public int size() {
// TODO Auto-generated method stub
return 0;
}
/* (non-Javadoc)
* @see java.util.Map#isEmpty()
*/
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
/* (non-Javadoc)
* @see java.util.Map#containsKey(java.lang.Object)
*/
public boolean containsKey(Object key) {
// TODO Auto-generated method stub
return false;
}
/* (non-Javadoc)
* @see java.util.Map#containsValue(java.lang.Object)
*/
public boolean containsValue(Object value) {
// TODO Auto-generated method stub
return false;
}
/* (non-Javadoc)
* @see java.util.Map#get(java.lang.Object)
*/
public Object get(Object key) {
return startState.get(key.toString().toCharArray(), 0);
}
/* (non-Javadoc)
* @see java.util.Map#put(java.lang.Object, java.lang.Object)
*/
public Object put(Object key, Object value) {
return startState.put(key.toString().toCharArray(), 0, value);
}
/* (non-Javadoc)
* @see java.util.Map#remove(java.lang.Object)
*/
public Object remove(Object key) {
return put(key, null);
}
/* (non-Javadoc)
* @see java.util.Map#putAll(java.util.Map)
*/
public void putAll(Map t) {
// TODO Auto-generated method stub
}
/* (non-Javadoc)
* @see java.util.Map#clear()
*/
public void clear() {
// TODO Auto-generated method stub
}
/* (non-Javadoc)
* @see java.util.Map#keySet()
*/
public Set keySet() {
// TODO Auto-generated method stub
return null;
}
/* (non-Javadoc)
* @see java.util.Map#values()
*/
public Collection values() {
// TODO Auto-generated method stub
return null;
}
/* (non-Javadoc)
* @see java.util.Map#entrySet()
*/
public Set entrySet() {
// TODO Auto-generated method stub
return null;
}
}
1.1
jakarta-slide/proposals/dfa-cache/src/org/apache/slide/util/DFAMap.java
Index: DFAMap.java
===================================================================
package org.apache.slide.util;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/*
* Created on 01.12.2003
*
* To change the template for this generated file go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
/**
* @author olli
*
* To change the template for this generated type comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
public class DFAMap implements Map {
State startState = new State();
/* (non-Javadoc)
* @see java.util.Map#size()
*/
public int size() {
// TODO Auto-generated method stub
return 0;
}
/* (non-Javadoc)
* @see java.util.Map#isEmpty()
*/
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
/* (non-Javadoc)
* @see java.util.Map#containsKey(java.lang.Object)
*/
public boolean containsKey(Object key) {
// TODO Auto-generated method stub
return false;
}
/* (non-Javadoc)
* @see java.util.Map#containsValue(java.lang.Object)
*/
public boolean containsValue(Object value) {
// TODO Auto-generated method stub
return false;
}
/* (non-Javadoc)
* @see java.util.Map#get(java.lang.Object)
*/
public Object get(Object key) {
return startState.get(key.toString().toCharArray(), 0);
}
/* (non-Javadoc)
* @see java.util.Map#put(java.lang.Object, java.lang.Object)
*/
public Object put(Object key, Object value) {
return startState.put(key.toString().toCharArray(), 0, value);
}
/* (non-Javadoc)
* @see java.util.Map#remove(java.lang.Object)
*/
public Object remove(Object key) {
return startState.remove(key.toString().toCharArray(), 0);
}
/* (non-Javadoc)
* @see java.util.Map#putAll(java.util.Map)
*/
public void putAll(Map t) {
// TODO Auto-generated method stub
}
/* (non-Javadoc)
* @see java.util.Map#clear()
*/
public void clear() {
startState = new State();
}
/* (non-Javadoc)
* @see java.util.Map#keySet()
*/
public Set keySet() {
// TODO Auto-generated method stub
return null;
}
/* (non-Javadoc)
* @see java.util.Map#values()
*/
public Collection values() {
// TODO Auto-generated method stub
return null;
}
/* (non-Javadoc)
* @see java.util.Map#entrySet()
*/
public Set entrySet() {
// TODO Auto-generated method stub
return null;
}
private class State {
Object value = null;
Object key = null;
// XXX uses HashMap itself
// Character --> State
Map transitions = new HashMap();
State transit(Character c) {
return (State) transitions.get(c);
}
void putTransition(Character c, State state) {
transitions.put(c, state);
}
Object get(char[] key, int pos) {
if (pos == key.length) {
return value;
} else {
Character c = new Character(key[pos]);
State nextState = transit(c);
if (nextState == null) {
return null;
} else {
return nextState.get(key, pos + 1);
}
}
}
Object remove(char[] key, int pos) {
// XXX simply overwrite
return put(key, pos, null);
}
Object put(char[] key, int pos, Object value) {
if (pos == key.length) {
this.key = new String(key);
Object oldValue = this.value;
this.value = value;
return oldValue;
} else {
Character c = new Character(key[pos]);
State nextState = transit(c);
if (nextState == null) {
nextState = new State();
putTransition(c, nextState);
}
return nextState.put(key, pos + 1, value);
}
}
}
}
1.1
jakarta-slide/proposals/dfa-cache/src/org/apache/slide/util/DFAMapTest.java
Index: DFAMapTest.java
===================================================================
package org.apache.slide.util;
import java.util.Map;
import java.util.HashMap;
/*
* Created on 01.12.2003
*
* To change the template for this generated file go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
/**
* @author olli
*
* To change the template for this generated type comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
public class DFAMapTest {
public static void main(String[] args) {
// Map map = new HashMap(); Map map2 = new HashMap(); Map map3 = new
HashMap();
Map map = new DFAMap(); Map map2 = new DFAMap(); Map map3 = new DFAMap();
// Map map = new TableDFAMap("key-valu0123456789"); Map map2 = new
TableDFAMap("key-valu0123456789"); Map map3 = new TableDFAMap("key-valu0123456789");
System.gc();
long put = System.currentTimeMillis();
System.out.println("PUT START");
for (int i = 0; i < 100000; i++) {
String key = "key-" + i;
String value = "value-" + i;
map.put(key, value);
}
System.out.println("TOOK: " + (System.currentTimeMillis() - put));
long get = System.currentTimeMillis();
System.out.println("GET START");
for (int i = 0; i < 100000; i++) {
String key = "key-" + i;
String expected = "value-" + i;
String value = (String) map.get(key);
if (!expected.equals(value)) {
System.out.println("**** Expected: " + expected + ", got: " + value);
}
}
System.out.println("TOOK: " + (System.currentTimeMillis() - get));
map = null;
System.gc();
put = System.currentTimeMillis();
System.out.println("PUT START #2");
for (int i = 100000 - 1; i >= 0 ; i--) {
String key = "key-" + i;
String value = "value-" + i;
map2.put(key, value);
}
System.out.println("TOOK: " + (System.currentTimeMillis() - put));
get = System.currentTimeMillis();
System.out.println("GET START #2");
for (int i = 100000 - 1; i >= 0 ; i--) {
String key = "key-" + i;
String expected = "value-" + i;
String value = (String) map2.get(key);
if (!expected.equals(value)) {
System.out.println("**** Expected: " + expected + ", got: " + value);
}
}
System.out.println("TOOK: " + (System.currentTimeMillis() - get));
map2 = null;
System.gc();
put = System.currentTimeMillis();
System.out.println("PUT START #3");
for (int i = 0; i < 100000; i++) {
String key = i+"-key";
String value = i+"-value";
map3.put(key, value);
}
System.out.println("TOOK: " + (System.currentTimeMillis() - put));
get = System.currentTimeMillis();
System.out.println("GET START #3");
for (int i = 0; i < 100000; i++) {
String key = i+"-key";
String expected = i+"-value";
String value = (String) map3.get(key);
if (!expected.equals(value)) {
System.out.println("**** Expected: " + expected + ", got: " + value);
}
}
System.out.println("TOOK: " + (System.currentTimeMillis() - get));
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
