Fully implements shuffle.

3 files changed, 153 insertions, 5 deletions

diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java
index f7893be..ccfc525 100644
--- a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java
+++ b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java
@@ -23,6 +23,7 @@ import tonkadur.wyrd.v1.lang.instruction.SetPC;
 import tonkadur.wyrd.v1.compiler.util.BinarySearch;
 import tonkadur.wyrd.v1.compiler.util.IfElse;
 import tonkadur.wyrd.v1.compiler.util.If;
+import tonkadur.wyrd.v1.compiler.util.Shuffle;
 import tonkadur.wyrd.v1.compiler.util.RemoveAt;
 import tonkadur.wyrd.v1.compiler.util.CreateCons;
 import tonkadur.wyrd.v1.compiler.util.IterativeSearch;
@@ -2059,7 +2060,39 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor
    )
    throws Throwable
    {
-      /* TODO */
+      final ComputationCompiler address_compiler;
+      final Address collection_address;
+      final Register result;
+
+      result = reserve(TypeCompiler.compile(compiler, n.get_type()));
+      result_as_address = result.get_address();
+      result_as_computation = result.get_value();
+
+      address_compiler = new ComputationCompiler(compiler);
+
+      n.get_collection().get_visited_by(address_compiler);
+
+      if (address_compiler.has_init())
+      {
+         init_instructions.add(address_compiler.get_init());
+      }
+
+      init_instructions.add
+      (
+         new SetValue(result_as_address, address_compiler.get_computation())
+      );
+
+      address_compiler.release_registers(init_instructions);
+
+      init_instructions.add
+      (
+         Shuffle.generate
+         (
+            compiler.registers(),
+            compiler.assembler(),
+            result_as_address
+         )
+      );
    }
 
    @Override
diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java
index c8488d8..1f47d8f 100644
--- a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java
+++ b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java
@@ -48,6 +48,7 @@ import tonkadur.wyrd.v1.compiler.util.IfElse;
 import tonkadur.wyrd.v1.compiler.util.InstructionManager;
 import tonkadur.wyrd.v1.compiler.util.NOP;
 import tonkadur.wyrd.v1.compiler.util.While;
+import tonkadur.wyrd.v1.compiler.util.Shuffle;
 import tonkadur.wyrd.v1.compiler.util.Clear;
 import tonkadur.wyrd.v1.compiler.util.IterativeSearch;
 import tonkadur.wyrd.v1.compiler.util.RemoveAllOf;
@@ -572,19 +573,15 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor
 
       collection_address = address_compiler.get_address();
 
-      /*
-       * TODO
       result.add
       (
          Shuffle.generate
          (
             compiler.registers(),
             compiler.assembler(),
-            new Size(collection_address),
             collection_address
          )
       );
-      */
 
       address_compiler.release_registers(result);
    }
diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/util/Shuffle.java b/src/core/src/tonkadur/wyrd/v1/compiler/util/Shuffle.java
new file mode 100644
index 0000000..45dbd81
--- /dev/null
+++ b/src/core/src/tonkadur/wyrd/v1/compiler/util/Shuffle.java
@@ -0,0 +1,118 @@
+package tonkadur.wyrd.v1.compiler.util;
+
+import java.util.List;
+import java.util.ArrayList;
+
+import tonkadur.wyrd.v1.lang.Register;
+
+import tonkadur.wyrd.v1.lang.type.Type;
+import tonkadur.wyrd.v1.lang.type.MapType;
+
+import tonkadur.wyrd.v1.lang.meta.Instruction;
+
+import tonkadur.wyrd.v1.lang.computation.Cast;
+import tonkadur.wyrd.v1.lang.computation.Constant;
+import tonkadur.wyrd.v1.lang.computation.Operation;
+import tonkadur.wyrd.v1.lang.computation.Address;
+import tonkadur.wyrd.v1.lang.computation.RelativeAddress;
+import tonkadur.wyrd.v1.lang.computation.ValueOf;
+import tonkadur.wyrd.v1.lang.computation.Size;
+
+import tonkadur.wyrd.v1.lang.instruction.SetValue;
+
+import tonkadur.wyrd.v1.compiler.util.registers.RegisterManager;
+
+public class Shuffle
+{
+   /* Utility Class */
+   private Shuffle () {}
+
+   /* Uses Durstenfeld's shuffling algorithm */
+   public static Instruction generate
+   (
+      final RegisterManager registers,
+      final InstructionManager assembler,
+      final Address collection
+   )
+   {
+      final List<Instruction> result, while_body;
+      final Type element_type;
+      final Register iterator, target_index;
+      final Register storage;
+      final Address a_i, a_j;
+
+      result = new ArrayList<Instruction>();
+      while_body = new ArrayList<Instruction>();
+
+      element_type =
+         ((MapType) collection.get_target_type()).get_member_type();
+
+      iterator = registers.reserve(Type.INT, result);
+      target_index = registers.reserve(Type.INT, result);
+      storage = registers.reserve(element_type, result);
+
+      a_i =
+         new RelativeAddress
+         (
+            collection,
+            new Cast(iterator.get_value(), Type.STRING),
+            element_type
+         );
+
+      a_j =
+         new RelativeAddress
+         (
+            collection,
+            new Cast(target_index.get_value(), Type.STRING),
+            element_type
+         );
+
+      while_body.add
+      (
+         new SetValue
+         (
+            target_index.get_address(),
+            Operation.rand(Constant.ZERO, iterator.get_value())
+         )
+      );
+
+      while_body.add(new SetValue(storage.get_address(), new ValueOf(a_i)));
+      while_body.add(new SetValue(a_i, new ValueOf(a_j)));
+      while_body.add(new SetValue(a_j, storage.get_value()));
+
+      while_body.add
+      (
+         new SetValue
+         (
+            iterator.get_address(),
+            Operation.minus(iterator.get_value(), Constant.ONE)
+         )
+      );
+
+      result.add
+      (
+         new SetValue
+         (
+            iterator.get_address(),
+            Operation.minus(new Size(collection), Constant.ONE)
+         )
+      );
+
+      result.add
+      (
+         While.generate
+         (
+            registers,
+            assembler,
+            Operation.greater_than(iterator.get_value(), Constant.ZERO),
+            assembler.merge(while_body)
+         )
+      );
+
+      registers.release(iterator, result);
+      registers.release(target_index, result);
+      registers.release(storage, result);
+
+      return assembler.merge(result);
+   }
+}