[6152] | 1 | /* |
---|
| 2 | Copyright 2006 by Sean Luke |
---|
| 3 | Licensed under the Academic Free License version 3.0 |
---|
| 4 | See the file "LICENSE" for more information |
---|
| 5 | */ |
---|
| 6 | |
---|
| 7 | |
---|
| 8 | package ec.gp; |
---|
| 9 | import ec.*; |
---|
| 10 | import ec.util.*; |
---|
| 11 | |
---|
| 12 | /* |
---|
| 13 | * ADFStack.java |
---|
| 14 | * |
---|
| 15 | * Created: Mon Oct 25 19:48:12 1999 |
---|
| 16 | * By: Sean Luke |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | /** |
---|
| 20 | * ADFStack is a special data object used to hold ADF data. |
---|
| 21 | * This object is a weird beast and takes some explaining. |
---|
| 22 | * It consists of a main stack, a secondary "substack", and a "reserve" area |
---|
| 23 | * (also implemented as a stack, |
---|
| 24 | * but it doesn't have to be). The reserve is used to "recycle" objects |
---|
| 25 | * rather than having to create then new every time. |
---|
| 26 | * |
---|
| 27 | * <P>When an ADF is evaluated, it first |
---|
| 28 | * evaluates its children, then it calls push() on the ADFstack. |
---|
| 29 | * push() either creates a new ADFContext, or it fetches one from the |
---|
| 30 | * reserve if possible. It then pushes the context on the main stack, |
---|
| 31 | * and also returns the context. The ADF fills the context's arguments |
---|
| 32 | * with the results of its childrens' evaluation, and sets numargs to |
---|
| 33 | * the number of |
---|
| 34 | * arguments, then evaluates the |
---|
| 35 | * ADF's associated function tree, |
---|
| 36 | * |
---|
| 37 | * <p>When an ADM is evaluated, it calls push() on the ADFstack. |
---|
| 38 | * The ADM then fills the context's adm node with itself, and sets numargs |
---|
| 39 | * to the number of children it has. Then it calls the ADM's associated |
---|
| 40 | * function tree. |
---|
| 41 | * |
---|
| 42 | * <p>In that tree, if an argument terminal of value <i>n</i> is evaluated, |
---|
| 43 | * the argument terminal calls evaluate(...) on the top context |
---|
| 44 | * on the ADF stack and returns the result. |
---|
| 45 | * This method does different things depending on whether the top context |
---|
| 46 | * represented an ADF or an ADM. If it was an ADF, the context simply sets |
---|
| 47 | * input to the value of argument <i>n</i> in the context's argument list, |
---|
| 48 | * and returns input. If it was an ADM, the context pops itself off the |
---|
| 49 | * stack and pushes itself on the substack (to set up the right context |
---|
| 50 | * for evaluating an original child of the ADM), then evaluates child <i>n</i> |
---|
| 51 | * of the ADM, then pops itself off the substack and pushes itself back |
---|
| 52 | * on the stack to restore the context. Input is set to the evaluated |
---|
| 53 | * results, and input is returned. |
---|
| 54 | * |
---|
| 55 | <p><b>Parameters</b><br> |
---|
| 56 | <table> |
---|
| 57 | <tr><td valign=top><i>base</i>.<tt>context</tt><br> |
---|
| 58 | <font size=-1>classname, inherits and != ec.gp.GPContext</font></td> |
---|
| 59 | <td valign=top>(the stack's GPContext class)</td></tr> |
---|
| 60 | </table> |
---|
| 61 | |
---|
| 62 | <p><b>Parameters</b><br> |
---|
| 63 | gp.adf-stack |
---|
| 64 | |
---|
| 65 | <p><b>Parameter bases</b><br> |
---|
| 66 | <table> |
---|
| 67 | <tr><td valign=top><i>base</i>.<tt>context</tt><br> |
---|
| 68 | <td valign=top>(context_proto)</td></tr> |
---|
| 69 | </table> |
---|
| 70 | |
---|
| 71 | * @author Sean Luke |
---|
| 72 | * @version 1.0 |
---|
| 73 | */ |
---|
| 74 | |
---|
| 75 | public class ADFStack implements Prototype |
---|
| 76 | { |
---|
| 77 | public static final String P_ADFSTACK = "adf-stack"; |
---|
| 78 | public static final String P_ADF = "adf"; |
---|
| 79 | public static final String P_CONTEXT = "context"; |
---|
| 80 | public ADFContext context_proto; |
---|
| 81 | public static final int INITIAL_STACK_SIZE = 2; // seems like a good size |
---|
| 82 | protected int onStack; |
---|
| 83 | protected int onSubstack; |
---|
| 84 | protected int inReserve; |
---|
| 85 | protected ADFContext[] stack; |
---|
| 86 | protected ADFContext[] substack; |
---|
| 87 | protected ADFContext[] reserve; |
---|
| 88 | |
---|
| 89 | public ADFStack() |
---|
| 90 | { |
---|
| 91 | stack = new ADFContext[INITIAL_STACK_SIZE]; |
---|
| 92 | substack = new ADFContext[INITIAL_STACK_SIZE]; |
---|
| 93 | reserve = new ADFContext[INITIAL_STACK_SIZE]; |
---|
| 94 | onStack=0; |
---|
| 95 | onSubstack = 0; |
---|
| 96 | inReserve = 0; |
---|
| 97 | } |
---|
| 98 | |
---|
| 99 | public Parameter defaultBase() |
---|
| 100 | { |
---|
| 101 | return GPDefaults.base().push(P_ADFSTACK); |
---|
| 102 | } |
---|
| 103 | |
---|
| 104 | public void setup(final EvolutionState state, final Parameter base) |
---|
| 105 | { |
---|
| 106 | // load our prototype |
---|
| 107 | |
---|
| 108 | Parameter p = base.push(P_CONTEXT); |
---|
| 109 | Parameter d = defaultBase().push(P_CONTEXT); |
---|
| 110 | |
---|
| 111 | context_proto = (ADFContext) |
---|
| 112 | (state.parameters.getInstanceForParameterEq(p,d,ADFContext.class)); |
---|
| 113 | context_proto.setup(state,p); |
---|
| 114 | } |
---|
| 115 | |
---|
| 116 | public Object clone() |
---|
| 117 | { |
---|
| 118 | try |
---|
| 119 | { |
---|
| 120 | ADFStack myobj = (ADFStack) (super.clone()); |
---|
| 121 | |
---|
| 122 | // deep-cloned stuff |
---|
| 123 | myobj.context_proto = (ADFContext)(context_proto.clone()); |
---|
| 124 | |
---|
| 125 | // clone the stack arrays -- dunno if this is faster than new ADFContext[...] |
---|
| 126 | myobj.stack = (ADFContext[])(stack.clone()); |
---|
| 127 | myobj.substack = (ADFContext[])(substack.clone()); |
---|
| 128 | myobj.reserve = (ADFContext[])(reserve.clone()); |
---|
| 129 | |
---|
| 130 | // fill 'em up |
---|
| 131 | for(int x=0;x<onStack;x++) |
---|
| 132 | myobj.stack[x] = (ADFContext)(stack[x].clone()); |
---|
| 133 | for(int x=0;x<onSubstack;x++) |
---|
| 134 | myobj.substack[x] = (ADFContext)(substack[x].clone()); |
---|
| 135 | for(int x=0;x<inReserve;x++) |
---|
| 136 | myobj.reserve[x] = (ADFContext)(reserve[x].clone()); |
---|
| 137 | return myobj; |
---|
| 138 | } |
---|
| 139 | catch (CloneNotSupportedException e) |
---|
| 140 | { throw new InternalError(); } // never happens |
---|
| 141 | } |
---|
| 142 | |
---|
| 143 | /** Returns an ADFContext from the stack's reserve, or creates one |
---|
| 144 | fresh if there are none in reserve. While you can throw this |
---|
| 145 | ADFContext away if you like, it'd be good if you actually didn't |
---|
| 146 | call this function unless you expected to push the |
---|
| 147 | context onto the stack with push(ADFContext obj) -- karma! |
---|
| 148 | */ |
---|
| 149 | public final ADFContext get() |
---|
| 150 | { |
---|
| 151 | // Remove one from reserve |
---|
| 152 | |
---|
| 153 | ADFContext obj; |
---|
| 154 | if (inReserve>0) obj = reserve[--inReserve]; |
---|
| 155 | else obj = (ADFContext)(context_proto.clone()); // hopefully that doesn't have to happen too many times |
---|
| 156 | return obj; |
---|
| 157 | } |
---|
| 158 | |
---|
| 159 | |
---|
| 160 | /** Pushes an ADFContext onto the main stack. The best way to get an |
---|
| 161 | ADFContext to push onto the stack is with get(). Returns obj. */ |
---|
| 162 | |
---|
| 163 | public final ADFContext push(ADFContext obj) |
---|
| 164 | { |
---|
| 165 | // Double stack if necessary |
---|
| 166 | if (onStack==stack.length) |
---|
| 167 | { |
---|
| 168 | ADFContext[] newstack = new ADFContext[stack.length * 2]; |
---|
| 169 | System.arraycopy(stack,0,newstack,0,stack.length); |
---|
| 170 | stack = newstack; |
---|
| 171 | } |
---|
| 172 | |
---|
| 173 | // Add to stack |
---|
| 174 | stack[onStack++] = obj; |
---|
| 175 | |
---|
| 176 | // return it |
---|
| 177 | return obj; |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | |
---|
| 181 | /** Pops off <i>n</i> items from the stack, if possible. Returns |
---|
| 182 | the number of items actually popped off. */ |
---|
| 183 | public final int pop(int n) |
---|
| 184 | { |
---|
| 185 | int x; |
---|
| 186 | for(x = 0 ; x < n; x++) |
---|
| 187 | { |
---|
| 188 | // Anything left on the stack? |
---|
| 189 | if (onStack==0) break; |
---|
| 190 | |
---|
| 191 | // Remove one from stack |
---|
| 192 | ADFContext obj = stack[--onStack]; |
---|
| 193 | |
---|
| 194 | // Double reserve if necessary |
---|
| 195 | if (inReserve==reserve.length) |
---|
| 196 | { |
---|
| 197 | ADFContext[] newreserve = new ADFContext[reserve.length * 2]; |
---|
| 198 | System.arraycopy(reserve,0,newreserve,0,reserve.length); |
---|
| 199 | reserve = newreserve; |
---|
| 200 | } |
---|
| 201 | |
---|
| 202 | // Add to reserve |
---|
| 203 | reserve[inReserve++] = obj; |
---|
| 204 | } |
---|
| 205 | return x; |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | |
---|
| 209 | |
---|
| 210 | |
---|
| 211 | /** Returns the <i>n</i>th item in the stack (0-indexed), or null if |
---|
| 212 | this goes to the bottom of the stack. */ |
---|
| 213 | public final ADFContext top(int n) |
---|
| 214 | { |
---|
| 215 | // is this beyond the stack? |
---|
| 216 | if (onStack-n <= 0) return null; |
---|
| 217 | else return stack[onStack-n-1]; |
---|
| 218 | } |
---|
| 219 | |
---|
| 220 | |
---|
| 221 | /** Moves <i>n</i> items onto the substack (pops them off the stack and pushes them onto the substack). Returns the actual number of items for which this was done. */ |
---|
| 222 | public final int moveOntoSubstack(int n) |
---|
| 223 | { |
---|
| 224 | int x; |
---|
| 225 | for(x=0;x<n;x++) |
---|
| 226 | { |
---|
| 227 | // is the stack empty? |
---|
| 228 | if (onStack==0) break; // uh oh |
---|
| 229 | |
---|
| 230 | // Remove one from stack |
---|
| 231 | ADFContext obj = stack[--onStack]; |
---|
| 232 | |
---|
| 233 | // Double substack if necessary |
---|
| 234 | if (onSubstack == substack.length) |
---|
| 235 | { |
---|
| 236 | ADFContext[] newsubstack = new ADFContext[substack.length * 2]; |
---|
| 237 | System.arraycopy(substack,0,newsubstack,0,substack.length); |
---|
| 238 | substack = newsubstack; |
---|
| 239 | } |
---|
| 240 | |
---|
| 241 | // Add to substack |
---|
| 242 | substack[onSubstack++] = obj; |
---|
| 243 | } |
---|
| 244 | return x; |
---|
| 245 | } |
---|
| 246 | |
---|
| 247 | /** Moves <i>n</i> items onto the stack (popss them off the substack and pushes them onto the stack). Returns the actual number of items moved from the Substack onto the main stack */ |
---|
| 248 | public final int moveFromSubstack(int n) |
---|
| 249 | { |
---|
| 250 | int x; |
---|
| 251 | for(x=0;x<n;x++) |
---|
| 252 | { |
---|
| 253 | // is the substack empty? |
---|
| 254 | if (onSubstack==0) break; // uh oh |
---|
| 255 | |
---|
| 256 | // Remove one from stack |
---|
| 257 | ADFContext obj = substack[--onSubstack]; |
---|
| 258 | |
---|
| 259 | // Double stack if necessary |
---|
| 260 | if (onStack==stack.length) |
---|
| 261 | { |
---|
| 262 | ADFContext[] newstack = new ADFContext[stack.length * 2]; |
---|
| 263 | System.arraycopy(stack,0,newstack,0,stack.length); |
---|
| 264 | stack = newstack; |
---|
| 265 | } |
---|
| 266 | |
---|
| 267 | // Add to stack |
---|
| 268 | stack[onStack++] = obj; |
---|
| 269 | } |
---|
| 270 | return x; |
---|
| 271 | } |
---|
| 272 | |
---|
| 273 | /** Pops off all items on the stack and the substack. */ |
---|
| 274 | public final void reset() |
---|
| 275 | { |
---|
| 276 | if (onSubstack>0) moveFromSubstack(onSubstack); |
---|
| 277 | if (onStack>0) pop(onStack); |
---|
| 278 | } |
---|
| 279 | |
---|
| 280 | } |
---|