codesimian
Class ListFindIndexFast

java.lang.Object
  codesimian.CS<CSGeneric>
      codesimian.DefaultCS
          codesimian.SimpleList
              codesimian.ListFindIndexFast

All Implemented Interfaces:

CodeSimian

public class ListFindIndexFast
extends SimpleList

Same as SimpleList except indexP(CS) and indexPName(String) use a CS-to-int and String-to-int hashtable to quickly find the index of most CSs contained in the list.

Because CS.indexPName(String) searches for any CS with a certain String returned by CS.name(), and because a CSs name may change at any time (use setName(String)), IT IS NOT POSSIBLE TO GET 100% ACCURACY WITH A HASHTABLE (BUT 99% CAN BE DONE), therefore it is necessary for ListFindIndexFast.indexPName(String) to call CS.name() on any CS it looks up using an index in the hashtable.
IF THE NAME HAS CHANGED, A LINEAR-SEARCH OF THIS WHOLE LIST IS DONE TO FIND IT (OR VERIFY ITS NOT IN THE LIST ANYMORE), THEN UPDATE THE HASHTABLE. linear search

If the names do not match, update the hashtable so they match. If the name does not change, next time that name is searched for, quickly return the int from the hashtable.

Similar things can be done to fix problems with indexP(CS).

If a listFindIndexFast does not contain a CS, a linear search is necessary to verify that. But (with some error) a list of the last 100 CSs, that were searched for but not found, might help. Do that in a subclass, but make it clear that it has ERRORS and approximates to get better speed. ListFindIndexFast is fast but only when searching for things it contains.

MODIFICATION NEEDED TO DECREASE BIG-O OF INSERT AND DELETE FROM LINEAR TO CONSTANT: This class should be modified to store child CSs in a TREE instead of the CS[] array in DefaultCS, so that INSERT and DELETE operations dont require sliding down (on average) half the contents of the list. It would probably be better to make that treelist as some other class and make this class subclass it.

Field Summary

Fields inherited from class codesimian.CS

DESCRIPTION, END, EXECPROXY, HEAP, JAVACODE, MYFUEL, NAME, NEWINSTANCE, NULL, PARENT, PARSEPRIORITY, PREV, TESTER, THIS

Constructor Summary

ListFindIndexFast()

Method Summary

int	indexP(CS findMe) uses a hashtable to lookup ints instead of searching for them, but linear search if not found
int	indexPName(java.lang.String findACSWithThisName) uses a hashtable to lookup ints instead of searching for them, but linear search if not found
java.lang.String	javaCode(CS listOfCodeAlreadyTraversed) unlike SimpleList, ListFindIndexFast is too complex to usefully convert to java code
java.lang.String	keyword() For the CodeSimian language as a String. CodeSimian language keyword, like "+" "*" "max" ">" etc. Override this function if you want to specify a keyword other than how I derive them from the class name, like + for Add. Some CSs might never be intended to be used in the language by their keyword. The best example (4/05) is Num, because it is used in the language like "3.4" instead of "num()".
static int	linearSearch(CS list, CS findMe) returns index found at or -1 if not found
static int	linearSearch(CS list, java.lang.String findThisName) returns index found at or -1 if not found
int	maxP() Maximum quantity of Params
int	minP() For DForProxy(). Minimum number of parameters in param[] needed to call DForProxy(). Defines which indexs of param[] DForProxy() can use. Functions with a different number of parameters must override this. OVERRIDE THIS FUNCTION IF EXEC USES A DIFFERENT NUMBER OF PARAMETERS. Default is 1.
CS	P(int index) ListFindIndexFast overrides P(int) to fix a bug that has not yet been fixed because it would slow the program down: WARNING: if add CSs then delete them, they are still in the DefaultCS.param[] array and can be returned in this function, despite them being out of valid range: index at least countP().

Methods inherited from class codesimian.SimpleList

DForProxy

Methods inherited from class codesimian.DefaultCS

B, C, countP, decrementMyFuel, deleteP, description, F, fuel, getExec, getObject, heap, I, insertB, insertC, insertD, insertF, insertI, insertJ, insertL, insertL, insertL1, insertP, insertS, insertZ, J, LForProxy, LForProxy, myFuel, name, newInstance, objectToCS, objectToCSArray, objectToCSArray, prevD, prevL, PType, S, setB, setC, setCountP, setD, setD, setExec, setF, setFuel, setI, setJ, setL, setL, setL, setL1, setMyFuel, setName, setObject, setP, setPrevExec, setPType, setS, setZ, start, toString, V, Z

Methods inherited from class codesimian.CS

addB, addC, addD, addF, addI, addJ, addL, addP, addP, addP, addP, addP, addS, addZ, BForProxy, CForProxy, clone, cost, D, deleteP, FForProxy, GETB, GETC, GETD, GETF, GETI, GETJ, GETL, GETS, GETZ, IForProxy, isIllusion, JForProxy, L, L, L, L, L, maxD, minD, overwrites, parent, parsePriority, PB, PC, PD, PF, PI, PJ, PL, prevB, prevC, prevF, prevI, prevJ, prevS, prevZ, proxyOf, PS, PZ, reflect, reflect, reflect6, setB, SETB, setC, SETC, setCost, SETD, setDescription, setF, SETF, setHeap, setI, SETI, setJ, SETJ, SETL, setL, setL, setParent, setParsePriority, setProxyOf, setS, SETS, setTester, setZ, SETZ, SForProxy, tester, toJavaCode, VForProxy, voidReflect, ZForProxy

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

ListFindIndexFast

public ListFindIndexFast()

Method Detail

indexP

public int indexP(CS findMe)

uses a hashtable to lookup ints instead of searching for them, but linear search if not found

Overrides:

indexP in class DefaultCS

indexPName

public int indexPName(java.lang.String findACSWithThisName)

uses a hashtable to lookup ints instead of searching for them, but linear search if not found

Overrides:

indexPName in class DefaultCS

See Also:

CS.name(), CS.setName(String), CS.indexP(CS)

linearSearch

public static int linearSearch(CS list,
                               CS findMe)

returns index found at or -1 if not found

linearSearch

public static int linearSearch(CS list,
                               java.lang.String findThisName)

returns index found at or -1 if not found

keyword

public java.lang.String keyword()

Description copied from class: DefaultCS

For the CodeSimian language as a String.
CodeSimian language keyword, like "+" "*" "max" ">" etc.

Override this function if you want to specify a keyword other than how I derive them from the class name, like + for Add.

Some CSs might never be intended to be used in the language by their keyword.
The best example (4/05) is Num, because it is used in the language like "3.4" instead of "num()".
Default: Returns class name, minus package name (and its dots), and change the first letter to lowercase.

For example, CS.MaxParams does not override keyword(), which returns "maxP".

Overrides:

keyword in class SimpleList

See Also:

CS.parent(), CS.newInstance(), CS.name()

minP

public int minP()

Description copied from class: DefaultCS

For DForProxy().
Minimum number of parameters in param[] needed to call DForProxy().
Defines which indexs of param[] DForProxy() can use.
Functions with a different number of parameters must override this.
OVERRIDE THIS FUNCTION IF EXEC USES A DIFFERENT NUMBER OF PARAMETERS.
Default is 1.

Overrides:

minP in class SimpleList

maxP

public int maxP()

Description copied from class: CS

Maximum quantity of Params

Overrides:

maxP in class SimpleList

javaCode

public java.lang.String javaCode(CS listOfCodeAlreadyTraversed)

unlike SimpleList, ListFindIndexFast is too complex to usefully convert to java code

Overrides:

javaCode in class DefaultCS

P

public CS P(int index)

ListFindIndexFast overrides P(int) to fix a bug that has not yet been fixed because it would slow the program down:
WARNING: if add CSs then delete them, they are still in the DefaultCS.param[] array and can be returned in this function, despite them being out of valid range: index at least countP().

Overrides:

P in class DefaultCS

Parameters:

index - range 0 (or neg?) to countP()-1 inclusive

See Also:

CS.heap()