1	/* Karel the Robot, a computer language learning game after Pattis            */
     2	/* Author:      Andreas Krall                                                 */
     3	/* Last Change: 96/03/28                                                      */
     4
     5	interface Globals {
     6
     7	    // error and return codes
     8
     9	    static final int simple_instr_finished     = -1;  // must be < 0
    10	    static final int no_error                  =  0;  // must be 0
    11	    static final int robot_made_turnoff        =  1;
    12	    static final int double_definition_error   =  2;
    13	    static final int incomplete_program_error  =  3;
    14	    static final int blocked_robot_error       =  4;
    15	    static final int end_of_world_error        =  5;
    16	    static final int no_beeper_error           =  6;
    17	    static final int empty_bag_error           =  7;
    18	    static final int missing_turnoff_error     =  8;
    19	    static final int back_end_reached_error    =  9;
    20	    static final int stack_overflow_error      = 10;
    21	    static final int internal_program_error    = 11;
    22
    23	    // test codes and names
    24
    25	    static final int undef_test           =  0;       // must be 0
    26	    static final int front_is_clear       =  1;       // must be previous + 1
    27	    static final int left_is_clear        =  2;
    28	    static final int right_is_clear       =  3;
    29	    static final int next_to_a_beeper     =  4;
    30	    static final int facing_north         =  5;       // north must be east - 1
    31	    static final int facing_east          =  6;       // east must be south - 1
    32	    static final int facing_south         =  7;       // south must be west - 1
    33	    static final int facing_west          =  8;       // west must be south + 1
    34	    static final int any_beepers_in_bag   =  9;
    35	    static final int front_is_blocked     = 10;
    36	    static final int left_is_blocked      = 11;
    37	    static final int right_is_blocked     = 12;
    38	    static final int not_next_to_a_beeper = 13;
    39	    static final int not_facing_north     = 14;
    40	    static final int not_facing_east      = 15;
    41	    static final int not_facing_south     = 16;
    42	    static final int not_facing_west      = 17;
    43	    static final int no_beepers_in_bag    = 18;
    44
    45	    static final String test_names[] = {
    46	        "<test>",
    47	        "front_is_clear",
    48	        "left_is_clear",
    49	        "right_is_clear",
    50	        "next_to_a_beeper",
    51	        "facing_north",
    52	        "facing_east",
    53	        "facing_south",
    54	        "facing_west",
    55	        "any_beepers_in_bag",
    56	        "front_is_blocked",
    57	        "left_is_blocked",
    58	        "right_is_blocked",
    59	        "not_next_to_a_beeper",
    60	        "not_facing_north",
    61	        "not_facing_east",
    62	        "not_facing_south",
    63	        "not_facing_west",
    64	        "no_beepers_in_bag"
    65	    };
    66
    67	    // basic instruction codes and names
    68
    69	    static final int undef_instr      = 0;     // must be 0
    70	    static final int move_instr       = 1;     // must be previous + 1
    71	    static final int turnleft_instr   = 2;
    72	    static final int putbeeper_instr  = 3;
    73	    static final int pickbeeper_instr = 4;
    74	    static final int turnoff_instr    = 5;
    75
    76	    static final String instruction_names[] = {
    77	        "<instr>", "move", "turnleft", "putbeeper", "pickbeeper", "turnoff"
    78	    };
    79
    80	    // node codes and node element description codes
    81
    82	    static final int is_undef          =  0;   // must be less than is_number
    83	    static final int program_node      =  1;   // must be less than is_number
    84	    static final int define_node       =  2;   // must be less than is_number
    85	    static final int execution_node    =  3;   // must be less than is_number
    86	    static final int block_node        =  4;   // must be less than is_number
    87	    static final int while_node        =  5;   // must be less than is_number
    88	    static final int iterate_node      =  6;   // must be less than is_number
    89	    static final int if_then_else_node =  7;   // must be less than is_number
    90	    static final int call_node         =  8;   // must be less than is_number
    91	    static final int basic_instr_node  =  9;   // must be less than is_number
    92	    static final int is_program        = 10;   // must be less than is_number
    93	    static final int is_execution      = 11;   // must be less than is_number
    94	    static final int is_def_list       = 12;   // must be less than is_number
    95	    static final int is_stmt           = 13;   // must be less than is_number
    96	    static final int is_stmt_list      = 14;   // must be less than is_number
    97	    static final int is_number         = 15;
    98	    static final int is_test           = 16;   // must be greater than is_number
    99	    static final int is_name           = 17;   // must be greater than is_number
   100	    static final int is_instr          = 18;   // must be greater than is_number
   101	}
   102
   103
   104	final class KarelTheRobot implements Globals{
   105
   106	    static int offset = 0;                     // offset of current instruction
   107	    static Node instruction = null;            // current instruction
   108
   109	    // left searches to the next left position
   110
   111	    static void left() {
   112	        Node instr = instruction;
   113
   114	        if (offset == 0) {                        // find previous node in list
   115	            while (instruction.offset == 0)       // find last node in list
   116	                instruction = instruction.next;
   117	            offset = instruction.offset - 1;      // set parent offset
   118	            instruction = instruction.next;       // set parent node
   119	            if (instruction.get_node_at_pos(offset) == instr)
   120	                offset--;                         // original node is list head
   121	            else {
   122	                instruction = instruction.get_node_at_pos(offset);
   123	                while (instruction.next != instr) // find previous node in list
   124	                    instruction = instruction.next;
   125	                offset = instruction.length();    // offset of last element
   126	            }
   127	        } else
   128	            offset--;
   129	        if (offset == 0)
   130	            return;
   131	        // go down the tree to the rightmost node of the tree
   132	        while ((instruction.description(offset) < is_number) &&
   133	               (instruction.get_node_at_pos(offset) != null)) {
   134	            // go down the tree
   135	            instruction = instruction.get_node_at_pos(offset);
   136	            while (instruction.offset == 0)       // find last node in list
   137	                instruction = instruction.next;
   138	            offset = instruction.length();        // offset of last element
   139	        }
   140	    }
   141
   142	    //right searches to next right position
   143
   144	    static void right() {
   145	        offset++;
   146	        while (offset >= instruction.length()) { // while behind last element
   147	            offset = instruction.offset;         // set parents offset and
   148	            instruction = instruction.next;      // go up to parent node
   149	        }
   150	        if ((offset != 0) &&                     // go down to child node
   151	            (instruction.description(offset) < is_number) &&
   152	            (instruction.get_node_at_pos(offset) != null)) {
   153	            instruction = instruction.get_node_at_pos(offset);
   154	            offset = 0;                          // first position in child node
   155	        }
   156	    }
   157
   158	    // insert_node insert a node at the current position
   159
   160	    static void insert_node(int node_code) {
   161	        Node node, help;
   162
   163	        node = null;
   164	        switch (node_code) {
   165	            case program_node:
   166	                offset = 0;
   167	                instruction = new ProgramNode();
   168	                return;
   169	            case define_node:
   170	                node = new DefineNode();
   171	                break;
   172	            case execution_node:
   173	                node = new ExecutionNode();
   174	                break;
   175	            case block_node:
   176	                node = new BlockNode();
   177	                break;
   178	            case while_node:
   179	                node = new WhileNode();
   180	                break;
   181	            case iterate_node:
   182	                node = new IterateNode();
   183	                break;
   184	            case if_then_else_node:
   185	                node = new IfThenElseNode();
   186	                break;
   187	            case call_node:
   188	                node = new CallNode();
   189	                break;
   190	            case basic_instr_node:
   191	                node = new BasicInstrNode();
   192	                break;
   193	        }
   194	        if (instruction.description(offset) == is_undef) {
   195	            node.offset = instruction.offset;                 // middle of list
   196	            node.next = instruction.next;
   197	            instruction.offset = 0;
   198	            instruction.next = node;
   199	        } else if ((help = instruction.get_node_at_pos(offset)) == null) {
   200	            instruction.put_object_at_pos(offset, node);      // empty
   201	            node.offset = offset + 1;
   202	            node.next = instruction;
   203	        } else {
   204	            instruction.put_object_at_pos(offset, node);      // head of list
   205	            node.offset = help.offset;
   206	            node.next = help.next;
   207	        }
   208	        offset = 0;
   209	        instruction = node;
   210	    }
   211
   212	    static public void print(int level, String text) {
   213	        while (--level >= 0)
   214	            System.out.print("   ");
   215	        System.out.print(text);
   216	    }
   217
   218	    static public void println(int level, String text) {
   219	        while (--level >= 0)
   220	            System.out.print("   ");
   221	        System.out.println(text);
   222	    }
   223
   224	    static public void print_instr(int level, Node instr) {
   225
   226	        if (instr == null)
   227	            KarelTheRobot.println(level + 1, "<instruction>");
   228	        else
   229	            while (instr != null) {
   230	                instr.print(level + 1);
   231	                if (instr.offset != 0)
   232	                    return;
   233	                instr = instr.next;
   234	            }
   235	    }
   236
   237	    static public void main(String args[])
   238	    throws java.io.IOException {
   239	        ProgramNode program;
   240	        Node n1, n2, n3;
   241	        IfThenElseNode if_stmt;
   242	        int error;
   243	        int ch;
   244
   245	        n1 = new BasicInstrNode(turnleft_instr);
   246	        n1.next = new BasicInstrNode(turnleft_instr);
   247	        n3 = n1.next.next = new BasicInstrNode(turnleft_instr);
   248	        n2 = new BlockNode();
   249	        ((BlockNode) n2).instruction = n1;
   250	        n3.next = n2;
   251	        n3.offset = 2;
   252	        n1 = new DefineNode();
   253	        ((DefineNode) n1).name =
   254	                      Name.enter_name("turnright", (DefineNode) n1);
   255	        ((DefineNode) n1).instruction = n2;
   256	        program = new ProgramNode();
   257	        program.define = (DefineNode) n1;
   258	        n2.offset = 3;
   259	        n2.next = program.execution;
   260	        program.execution.instruction = if_stmt = new IfThenElseNode();
   261	        if_stmt.test = 3;
   262	        if_stmt.next = new BasicInstrNode(turnoff_instr);
   263	        if_stmt.next.offset = 2;
   264	        if_stmt.next.next = program.execution;
   265	        n1 = if_stmt.then_stmt = new CallNode();
   266	        n1.offset = 3;
   267	        n1.next = if_stmt;
   268	        ((CallNode) n1).definition = program.define.name;
   269	        n1 = if_stmt.else_stmt = new IterateNode();
   270	        n1.offset = 4;
   271	        n1.next = if_stmt;
   272	        ((IterateNode) n1).count = 3;
   273
   274	        program.print(0);
   275
   276	        offset = 0;
   277	        instruction = program;
   278
   279	        BackBuffer.reset();
   280	        DefineNode.reset();
   281	        IterateNode.reset();
   282
   283	        ch = 'c';
   284	        while ((error = instruction.exec_step()) <= 0) {
   285	            //ch = System.in.read();
   286	            if (ch != 'c')
   287	                break;
   288	        }
   289
   290	        System.out.println("Ergebnis des Programmes: " + error);
   291	    }
   292	}
   293
   294
   295	final class KarelsWorld implements Globals{
   296
   297	    // world's bit 0 = north wall, bit 1 = east wall, bit 2 .. 15 = beeper count
   298
   299	    private static short world[][] = new short[100][100];
   300	    private static final int north_wall = 1;
   301	    private static final int east_wall = 2;
   302
   303	    private static int x = 0;                 // Karels x position
   304	    private static int y = 0;                 // Karels y position
   305	    private static int facing = facing_north; // Karels facing
   306	    private static int bag = 0;               // number of beepers in Karels bag
   307
   308	    static void set_karel(int x, int y, int facing) {
   309	        if (x < 0)
   310	            x = 0;
   311	        if (x >= world.length)
   312	            x = world.length - 1;
   313	        KarelsWorld.x = x;
   314	        if (y < 0)
   315	            y = 0;
   316	        if (y >= world[0].length)
   317	            y = world[0].length - 1;
   318	        KarelsWorld.y = y;
   319	        KarelsWorld.facing = facing_north;
   320	        if ((facing == facing_north) ||
   321	            (facing == facing_east)  ||
   322	            (facing == facing_south) ||
   323	            (facing == facing_west))
   324	            KarelsWorld.facing = facing;
   325	    }
   326
   327	    static void fill_bag(int count) {
   328	        if (count < 0)
   329	            count = 0;
   330	        bag = count;
   331	    }
   332
   333	    private static boolean position_out_of_bounds(int x, int y) {
   334	        if ((x < 0) || (x >= world.length) || (y < 0) || (y >= world[0].length))
   335	            return true;
   336	        return false;
   337	    }
   338
   339	    static void set_north_wall(int x, int y) {
   340	        if (position_out_of_bounds(x, y))
   341	            return;
   342	        world[x][y] |= north_wall;
   343	    }
   344
   345	    static void set_east_wall(int x, int y) {
   346	        if (position_out_of_bounds(x, y))
   347	            return;
   348	        world[x][y] |= east_wall;
   349	    }
   350
   351	    static void clear_north_wall(int x, int y) {
   352	        if (position_out_of_bounds(x, y))
   353	            return;
   354	        world[x][y] &= ~north_wall;
   355	    }
   356
   357	    static void clear_east_wall(int x, int y) {
   358	        if (position_out_of_bounds(x, y))
   359	            return;
   360	        world[x][y] &= ~east_wall;
   361	    }
   362
   363	    static boolean test(int test) {
   364	        switch (test) {
   365	            case front_is_clear:
   366	                switch (facing){
   367	                    case facing_north:
   368	                        return ((world[x][y] & north_wall) == 0);
   369	                    case facing_east:
   370	                        return ((world[x][y] & east_wall) == 0);
   371	                    case facing_south:
   372	                        if (y == 0)
   373	                            return false;
   374	                        return ((world[x][y-1] & north_wall) == 0);
   375	                    case facing_west:
   376	                        if (x == 0)
   377	                            return false;
   378	                        return ((world[x-1][y] & east_wall) == 0);
   379	                }
   380	                break;
   381	            case left_is_clear:
   382	                switch (facing){
   383	                    case facing_north:
   384	                        if (x == 0)
   385	                            return false;
   386	                        return ((world[x-1][y] & east_wall) == 0);
   387	                    case facing_east:
   388	                        return ((world[x][y] & north_wall) == 0);
   389	                    case facing_south:
   390	                        return ((world[x][y] & east_wall) == 0);
   391	                    case facing_west:
   392	                        if (y == 0)
   393	                            return false;
   394	                        return ((world[x][y-1] & north_wall) == 0);
   395	                }
   396	                break;
   397	            case right_is_clear:
   398	                switch (facing){
   399	                    case facing_north:
   400	                        return ((world[x][y] & east_wall) == 0);
   401	                    case facing_east:
   402	                        if (y == 0)
   403	                            return false;
   404	                        return ((world[x][y-1] & north_wall) == 0);
   405	                    case facing_south:
   406	                        if (x == 0)
   407	                            return false;
   408	                        return ((world[x-1][y ] & east_wall) == 0);
   409	                    case facing_west:
   410	                        return ((world[x][y] & north_wall) == 0);
   411	                }
   412	                break;
   413	            case next_to_a_beeper:
   414	                return ((world[x][y] >>> 2) > 0);
   415	            case facing_north:
   416	                return (facing == facing_north);
   417	            case facing_east:
   418	                return (facing == facing_east);
   419	            case facing_south:
   420	                return (facing == facing_south);
   421	            case facing_west:
   422	                return (facing == facing_west);
   423	            case any_beepers_in_bag:
   424	                return (bag > 0);
   425	            case front_is_blocked:
   426	                return ! test(front_is_clear);
   427	            case left_is_blocked:
   428	                return ! test(left_is_clear);
   429	            case right_is_blocked:
   430	                return ! test(right_is_clear);
   431	            case not_next_to_a_beeper:
   432	                return ((world[x][y] >>> 2) <= 0);
   433	            case not_facing_north:
   434	                return (facing != facing_north);
   435	            case not_facing_east:
   436	                return (facing != facing_east);
   437	            case not_facing_south:
   438	                return (facing != facing_south);
   439	            case not_facing_west:
   440	                return (facing != facing_west);
   441	            case no_beepers_in_bag:
   442	                return (bag <= 0);
   443	        }
   444	        return false;
   445	    }
   446
   447	    static int exec_instr(int instr) {
   448	        switch (instr) {
   449	            case undef_instr:
   450	                return incomplete_program_error;
   451	            case move_instr:
   452	                System.out.println("move");
   453	                if (test(front_is_clear))
   454	                    switch (facing) {
   455	                        case facing_north:
   456	                            if (y >= world[0].length)
   457	                                return end_of_world_error;
   458	                            y++;
   459	                            return 0;
   460	                        case facing_south:
   461	                            if (y <= 0)
   462	                                return blocked_robot_error;
   463	                            y--;
   464	                            return 0;
   465	                        case facing_east:
   466	                            if (x >= world.length)
   467	                                return end_of_world_error;
   468	                            x++;
   469	                            return 0;
   470	                        case facing_west:
   471	                            if (x <= 0)
   472	                                return blocked_robot_error;
   473	                            x--;
   474	                            return 0;
   475	                        default:
   476	                            return internal_program_error;
   477	                    }
   478	                else
   479	                    return blocked_robot_error;
   480	            case turnleft_instr:
   481	                System.out.println("turnleft");
   482	                if (--facing < facing_north)
   483	                    facing = facing_west;
   484	                return 0;
   485	            case putbeeper_instr:
   486	                System.out.println("putbeeper");
   487	                if (bag <= 0)
   488	                    return empty_bag_error;
   489	                bag--;
   490	                world[x][y] += 4;
   491	                return 0;
   492	            case pickbeeper_instr:
   493	                System.out.println("pickbeeper");
   494	                if ((world[x][y] >>> 2) <= 0)
   495	                    return no_beeper_error;
   496	                world[x][y] -= 4;
   497	                bag++;
   498	                return 0;
   499	            case turnoff_instr:
   500	                System.out.println("turnoff");
   501	                return robot_made_turnoff;
   502	        }
   503	        return 0;
   504	    }
   505	}
   506
   507
   508	class BackBuffer {
   509	    static long buffer = 0;
   510	    static int elements = 0;
   511
   512	    static void reset() {
   513	        elements = 0;
   514	    }
   515
   516	    static void push(boolean val) {
   517	        if (elements < 64)
   518	            elements++;
   519	        buffer = buffer << 1;
   520	        if (val)
   521	            buffer += 1;
   522	    }
   523
   524	    static boolean pop() {
   525	        boolean retval;
   526
   527	        retval = (buffer & 1) != 0;
   528	        if (elements > 0)
   529	            elements--;
   530	        buffer = buffer >>> 1;
   531	        return retval;
   532	    }
   533	}
   534
   535
   536	abstract class Node implements Globals{
   537	    int  offset;
   538	    Node next;
   539
   540	    Node() {
   541	        offset = 0;
   542	        next = null;
   543	    }
   544
   545	    int length() {
   546	        return 1;
   547	    }
   548
   549	    abstract int description(int pos);
   550
   551	    int get_int_at_pos(int pos) {
   552	        return 0;
   553	    }
   554
   555	    Name get_name_at_pos(int pos){
   556	        return null;
   557	    }
   558
   559	    Node get_node_at_pos(int pos){
   560	        return null;
   561	    }
   562
   563	    void put_object_at_pos(int pos, int val) {
   564	    }
   565
   566	    void put_object_at_pos(int pos, Name name) {
   567	    }
   568
   569	    void put_object_at_pos(int pos, Node node) {
   570	    }
   571
   572	    abstract void print(int level);
   573	    abstract int exec_step();
   574	}
   575
   576
   577	final class ProgramNode extends Node implements Globals {
   578
   579	    static final int description[] =
   580	        {program_node, is_def_list, is_execution, is_undef, is_undef};
   581
   582	    DefineNode    define;
   583	    ExecutionNode execution;
   584
   585	    ProgramNode() {
   586	        define = null;
   587	        execution = new ExecutionNode();
   588	        execution.next = this;
   589	        execution.offset = 3;
   590	    }
   591
   592	    int length() {
   593	        return 2;
   594	    }
   595
   596	    int description(int pos) {
   597	        return description[pos];
   598	    }
   599
   600	    Node get_node_at_pos(int pos){
   601	        if (pos == 1)
   602	            return define;
   603	        else if (pos == 2)
   604	            return execution;
   605	        return null;
   606	    }
   607
   608	    void put_object_at_pos(int pos, Node node) {
   609	        if (pos == 1)
   610	            define = (DefineNode) node;
   611	        else if (pos == 2)
   612	            execution = (ExecutionNode) node;
   613	    }
   614
   615	    void print(int level) {
   616	        KarelTheRobot.println(level, "BEGINNING-OF-PROGRAM");
   617	        if (define == null)
   618	            KarelTheRobot.println(level + 1, "<definition>");
   619	        else
   620	            define.print(level + 1);
   621	        execution.print(level + 1);
   622	        KarelTheRobot.println(level, "END-OF-PROGRAM");
   623	    }
   624
   625	    int exec_step() {
   626	        if (KarelTheRobot.offset != 0)
   627	            return missing_turnoff_error;
   628	        if (execution == null)
   629	            return incomplete_program_error;
   630	        KarelTheRobot.instruction = execution;
   631	        return 0;
   632	    }
   633	}
   634
   635
   636	final class DefineNode extends Node implements Globals {
   637
   638	    static final int description[] =
   639	        {define_node, is_name, is_stmt, is_undef, is_undef};
   640
   641	    Name name;
   642	    Node instruction;
   643
   644	    static CallNode stack[] = new CallNode[1024];
   645	    static int top = 0;
   646
   647	    DefineNode() {
   648	        name = null;
   649	        instruction = null;
   650	    }
   651
   652	    static void reset() {
   653	        top = 0;
   654	    }
   655
   656	    int length() {
   657	        return 2;
   658	    }
   659
   660	    int description(int pos) {
   661	        return description[pos];
   662	    }
   663
   664	    Name get_name_at_pos(int pos){
   665	        if (pos == 1)
   666	            return name;
   667	        return null;
   668	    }
   669
   670	    void put_object_at_pos(int pos, Name name) {
   671	        if (pos == 1)
   672	            this.name = name;
   673	    }
   674
   675	    Node get_node_at_pos(int pos){
   676	        if (pos == 2)
   677	            return instruction;
   678	        return null;
   679	    }
   680
   681	    void put_object_at_pos(int pos, Node node) {
   682	        if (pos == 2)
   683	            instruction = node;
   684	    }
   685
   686	    void print(int level) {
   687	        KarelTheRobot.print(level, "DEFINE-NEW-INSTRUCTION ");
   688	        if (name == null)
   689	            KarelTheRobot.print(0, "<name>");
   690	        else
   691	            KarelTheRobot.print(0, name.get_name());
   692	        KarelTheRobot.println(0, " AS");
   693	        instruction.print(level + 1);
   694	    }
   695
   696	    static int push(CallNode caller) {
   697	        top++;
   698	        if (top >= stack.length)
   699	            return stack_overflow_error;
   700	        stack[top] = caller;
   701	        KarelTheRobot.instruction = caller.definition.define.instruction;
   702	        return 0;
   703	    }
   704
   705	    int exec_step() {
   706	        if (KarelTheRobot.offset == 0)
   707	            return internal_program_error;
   708	        KarelTheRobot.offset = stack[top].offset;
   709	        KarelTheRobot.instruction = stack[top].next;
   710	        top--;
   711	        return 0;
   712	    }
   713	}
   714
   715
   716	final class Name implements Globals{
   717
   718	    private static Name name_list = null;
   719
   720	    String       name;
   721	    DefineNode   define;
   722	    private Name next;
   723
   724	    Name(String name, DefineNode define) {
   725	        this.name = name;
   726	        this.define = define;
   727	        this.next = name_list;
   728	        name_list = this;
   729	    }
   730
   731	    public String get_name() {
   732	        return this.name;
   733	    }
   734
   735	    public static Name enter_name(String name, DefineNode definition) {
   736	        Name nlist = name_list;
   737	        while (nlist != null) {
   738	            if (nlist.name.equals(name))
   739	                if (nlist.define == null) {
   740	                    nlist.define = definition;
   741	                    return nlist;
   742	                } else
   743	                    return null;
   744	            nlist = nlist.next;
   745	        }
   746	        return new Name(name, definition);
   747	    }
   748
   749	    public static DefineNode find_name(String name) {
   750	        Name nlist = name_list;
   751	        while (nlist != null) {
   752	            if (nlist.name.equals(name))
   753	                return nlist.define;
   754	            nlist = nlist.next;
   755	        }
   756	        new Name(name, null);
   757	        return null;
   758	    }
   759	}
   760
   761
   762	final class ExecutionNode extends Node implements Globals {
   763
   764	    static final int description[] =
   765	        {execution_node, is_stmt_list, is_undef, is_undef, is_undef};
   766
   767	    Node instruction;
   768
   769	    ExecutionNode() {
   770	        instruction = null;
   771	    }
   772
   773	    int description(int pos) {
   774	        return description[pos];
   775	    }
   776
   777	    Node get_node_at_pos(int pos){
   778	        if (pos == 1)
   779	            return instruction;
   780	        return null;
   781	    }
   782
   783	    void put_object_at_pos(int pos, Node node) {
   784	        if (pos == 1)
   785	            instruction = node;
   786	    }
   787
   788	    void print(int level) {
   789	        KarelTheRobot.println(level, "BEGINNING-OF-EXECUTION");
   790	        KarelTheRobot.print_instr(level, instruction);
   791	        KarelTheRobot.println(level, "END-OF-EXECUTION");
   792	    }
   793
   794	    int exec_step() {
   795	        if (KarelTheRobot.offset == 0) {
   796	            if (instruction == null)
   797	                return incomplete_program_error;
   798	            KarelTheRobot.instruction = instruction;
   799	        } else {
   800	            KarelTheRobot.offset = 0;
   801	            KarelTheRobot.instruction = instruction;
   802	        }
   803	        return 0;
   804	    }
   805	}
   806
   807
   808	final class BlockNode extends Node implements Globals {
   809
   810	    static final int description[] =
   811	        {block_node, is_stmt_list, is_undef, is_undef, is_undef};
   812
   813	    Node instruction;
   814
   815	    BlockNode() {
   816	        instruction = null;
   817	    }
   818
   819	    int description(int pos) {
   820	        return description[pos];
   821	    }
   822
   823	    Node get_node_at_pos(int pos){
   824	        if (pos == 1)
   825	            return instruction;
   826	        return null;
   827	    }
   828
   829	    void put_object_at_pos(int pos, Node node) {
   830	        if (pos == 1)
   831	            instruction = node;
   832	    }
   833
   834	    void print(int level) {
   835	        KarelTheRobot.println(level, "BEGIN");
   836	        KarelTheRobot.print_instr(level, instruction);
   837	        KarelTheRobot.println(level, "END");
   838	    }
   839
   840	    int exec_step() {
   841	        if (KarelTheRobot.offset == 0) {
   842	            if (instruction == null)
   843	                return incomplete_program_error;
   844	            KarelTheRobot.instruction = instruction;
   845	        } else {
   846	            KarelTheRobot.offset = 0;
   847	            KarelTheRobot.instruction = instruction;
   848	        }
   849	        return 0;
   850	    }
   851	}
   852
   853
   854	final class WhileNode extends Node implements Globals {
   855
   856	    static final int description[] =
   857	        {while_node, is_test, is_stmt, is_undef, is_undef};
   858
   859	    int  test;
   860	    Node instruction;
   861
   862	    WhileNode() {
   863	        test = undef_test;
   864	        instruction = null;
   865	    }
   866
   867	    int length() {
   868	        return 2;
   869	    }
   870
   871	    int description(int pos) {
   872	        return description[pos];
   873	    }
   874
   875	    int get_int_at_pos(int pos){
   876	        if (pos == 1)
   877	            return test;
   878	        return 0;
   879	    }
   880
   881	    void put_object_at_pos(int pos, int val) {
   882	        if (pos == 1)
   883	            test = val;
   884	    }
   885
   886	    Node get_node_at_pos(int pos){
   887	        if (pos == 2)
   888	            return instruction;
   889	        return null;
   890	    }
   891
   892	    void put_object_at_pos(int pos, Node node) {
   893	        if (pos == 2)
   894	            instruction = node;
   895	    }
   896
   897	    void print(int level) {
   898	        KarelTheRobot.println(level, "WHILE " + test_names[test] + " DO");
   899	        KarelTheRobot.print_instr(level, instruction);
   900	    }
   901
   902	    int exec_step() {
   903	        if (test == 0)
   904	            return incomplete_program_error;
   905	        if (KarelTheRobot.offset == 0)
   906	            BackBuffer.push(true);
   907	        else
   908	            BackBuffer.push(false);
   909	        KarelTheRobot.offset = 0;
   910	        if (KarelsWorld.test(test)) {
   911	            if (instruction == null)
   912	                return incomplete_program_error;
   913	            KarelTheRobot.instruction = instruction;
   914	        } else {
   915	            KarelTheRobot.offset = offset;
   916	            KarelTheRobot.instruction = next;
   917	        }
   918	        return 0;
   919	    }
   920	}
   921
   922
   923	final class IterateNode extends Node implements Globals {
   924
   925	    static final int description[] =
   926	        {iterate_node, is_number, is_stmt, is_undef, is_undef};
   927
   928	    int  count;
   929	    Node instruction;
   930
   931	    static int stack[] = new int[1024];
   932	    static int top = 0;
   933
   934	    IterateNode() {
   935	        count = 0;
   936	        instruction = null;
   937	    }
   938
   939	    static void reset() {
   940	        top = 0;
   941	    }
   942
   943	    int length() {
   944	        return 2;
   945	    }
   946
   947	    int description(int pos) {
   948	        return description[pos];
   949	    }
   950
   951	    int get_int_at_pos(int pos){
   952	        if (pos == 1)
   953	            return count;
   954	        return 0;
   955	    }
   956
   957	    void put_object_at_pos(int pos, int val) {
   958	        if (pos == 1)
   959	            count = val;
   960	    }
   961
   962	    Node get_node_at_pos(int pos){
   963	        if (pos == 2)
   964	            return instruction;
   965	        return null;
   966	    }
   967
   968	    void put_object_at_pos(int pos, Node node) {
   969	        if (pos == 2)
   970	            instruction = node;
   971	    }
   972
   973	    void print(int level) {
   974	        if (count == 0)
   975	            KarelTheRobot.println(level, "ITERATE <number> TIMES");
   976	        else
   977	            KarelTheRobot.println(level, "ITERATE " + count + " TIMES");
   978	        KarelTheRobot.print_instr(level, instruction);
   979	    }
   980
   981	    int exec_step() {
   982	        if (KarelTheRobot.offset == 0) {
   983	            if ((count == 0) || (instruction == null))
   984	                return incomplete_program_error;
   985	            top++;
   986	            if (top >= stack.length)
   987	                return stack_overflow_error;
   988	            stack[top] = count;
   989	            KarelTheRobot.instruction = instruction;
   990	        } else {
   991	            if (--stack[top] > 0) {
   992	                KarelTheRobot.offset = 0;
   993	                KarelTheRobot.instruction = instruction;
   994	            } else {
   995	                top--;
   996	                KarelTheRobot.offset = offset;
   997	                KarelTheRobot.instruction = next;
   998	            }
   999	        }
  1000	        return 0;
  1001	    }
  1002	}
  1003
  1004
  1005	class IfThenElseNode extends Node implements Globals {
  1006
  1007	    static final int description[] =
  1008	        {if_then_else_node, is_test, is_stmt, is_stmt, is_undef};
  1009
  1010	    int  test;
  1011	    Node then_stmt;
  1012	    Node else_stmt;
  1013
  1014	    IfThenElseNode() {
  1015	        test = undef_test;
  1016	        then_stmt = null;
  1017	        else_stmt = null;
  1018	    }
  1019
  1020	    int length() {
  1021	        return 3;
  1022	    }
  1023
  1024	    int description(int pos) {
  1025	        return description[pos];
  1026	    }
  1027
  1028	    int get_int_at_pos(int pos){
  1029	        if (pos == 1)
  1030	            return test;
  1031	        return 0;
  1032	    }
  1033
  1034	    void put_object_at_pos(int pos, int val) {
  1035	        if (pos == 1)
  1036	            test = val;
  1037	    }
  1038
  1039	    Node get_node_at_pos(int pos){
  1040	        if (pos == 2)
  1041	            return then_stmt;
  1042	        else if (pos == 3)
  1043	            return else_stmt;
  1044	        return null;
  1045	    }
  1046
  1047	    void put_object_at_pos(int pos, Node node) {
  1048	        if (pos == 2)
  1049	            then_stmt = node;
  1050	        else if (pos == 3)
  1051	            else_stmt = node;
  1052	    }
  1053
  1054	    void print(int level) {
  1055	        KarelTheRobot.println(level, "IF " + test_names[test]);
  1056	        KarelTheRobot.println(level, "THEN");
  1057	        KarelTheRobot.print_instr(level, then_stmt);
  1058	        KarelTheRobot.println(level, "ELSE");
  1059	        KarelTheRobot.print_instr(level, else_stmt);
  1060	    }
  1061
  1062	    int exec_step() {
  1063	        if (test == 0)
  1064	            return incomplete_program_error;
  1065	        if (KarelTheRobot.offset == 0) {
  1066	            if (KarelsWorld.test(test)) {
  1067	                if (then_stmt == null)
  1068	                    return incomplete_program_error;
  1069	                KarelTheRobot.instruction = then_stmt;
  1070	            } else {
  1071	                if (else_stmt == null)
  1072	                    return incomplete_program_error;
  1073	                KarelTheRobot.instruction = else_stmt;
  1074	            }
  1075	        } else {
  1076	            if (KarelTheRobot.offset == 4)
  1077	                BackBuffer.push(true);
  1078	            else
  1079	                BackBuffer.push(false);
  1080	            KarelTheRobot.offset = offset;
  1081	            KarelTheRobot.instruction = next;
  1082	        }
  1083	        return 0;
  1084	    }
  1085	}
  1086
  1087
  1088	final class CallNode extends Node implements Globals {
  1089
  1090	    static final int description[] =
  1091	        {call_node, is_name, is_undef, is_undef, is_undef};
  1092
  1093	    Name definition;
  1094
  1095	    CallNode() {
  1096	        definition = null;
  1097	    }
  1098
  1099	    int description(int pos) {
  1100	        return description[pos];
  1101	    }
  1102
  1103	    Name get_name_at_pos(int pos){
  1104	        if (pos == 1)
  1105	            return definition;
  1106	        return null;
  1107	    }
  1108
  1109	    void put_object_at_pos(int pos, Name name) {
  1110	        if (pos == 1)
  1111	            this.definition = name;
  1112	    }
  1113
  1114	    void print(int level) {
  1115	        KarelTheRobot.println(level, definition.get_name());
  1116	    }
  1117
  1118	    int exec_step() {
  1119	        if (KarelTheRobot.offset != 0)
  1120	            return internal_program_error;
  1121	        if ((definition == null) || (definition.define.instruction == null))
  1122	            return incomplete_program_error;
  1123	        return definition.define.push(this);
  1124	    }
  1125	}
  1126
  1127
  1128	final class BasicInstrNode extends Node implements Globals {
  1129
  1130	    static final int description[] =
  1131	        {basic_instr_node, is_instr, is_undef, is_undef, is_undef};
  1132
  1133	    int instruction;
  1134
  1135	    BasicInstrNode() {
  1136	        instruction = undef_instr;
  1137	    }
  1138
  1139	    BasicInstrNode(int instr) {
  1140	        instruction = instr;
  1141	    }
  1142
  1143	    int description(int pos) {
  1144	        return description[pos];
  1145	    }
  1146
  1147	    int get_int_at_pos(int pos){
  1148	        if (pos == 1)
  1149	            return instruction;
  1150	        return 0;
  1151	    }
  1152
  1153	    void put_object_at_pos(int pos, int val) {
  1154	        if (pos == 1)
  1155	            instruction = val;
  1156	    }
  1157
  1158	    void print(int level) {
  1159	        KarelTheRobot.println(level, instruction_names[instruction]);
  1160	    }
  1161
  1162	    int exec_step() {
  1163	        int retval;
  1164
  1165	        retval = KarelsWorld.exec_instr(instruction);
  1166	        KarelTheRobot.offset = offset;
  1167	        KarelTheRobot.instruction = next;
  1168	        return retval;
  1169	    }
  1170	}