codesimian
Class ListFindIndexFast

java.lang.Object
  extended by codesimian.CS
      extended by codesimian.DefaultCS
          extended by codesimian.NothingList
              extended by codesimian.ListFindIndexFast
All Implemented Interfaces:
CodeSimian, java.io.Serializable

public class ListFindIndexFast
extends NothingList

Same as NothingList 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.

See Also:
Serialized Form

Field Summary
 
Fields inherited from class codesimian.CS
DESCRIPTION, END, EXECPROXY, FUEL, HEAP, JAVACODE, MYFUEL, NAME, NEWINSTANCE, NULL, PARENT, PARSEPRIORITY, PREV, TESTER
 
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 NothingList, 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.NothingList
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, setS, setZ, start, toString, V, Z
 
Methods inherited from class codesimian.CS
addP, addP, addP, addP, addP, BForProxy, CForProxy, clone, cost, D, deleteP, FForProxy, IForProxy, isIllusion, javaCode, 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, setB, setC, setCost, setDescription, setF, setHeap, setI, setJ, setL, setL, setParent, setParsePriority, setProxyOf, setPType, setS, setTester, setZ, SForProxy, tester, 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 NothingList
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 NothingList

maxP

public int maxP()
Description copied from class: CS
Maximum quantity of Params

Overrides:
maxP in class NothingList

javaCode

public java.lang.String javaCode(CS listOfCodeAlreadyTraversed)
unlike NothingList, ListFindIndexFast is too complex to usefully convert to java code

Overrides:
javaCode in class NothingList
Returns:
String of Java code, or null if this CS does not know how to convert itself to Java code.

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 to countP()-1 inclusive
See Also:
CS.heap()