User Tools

Site Tools


This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
creating_an_algorithm [2012/09/01 12:28]
will created
creating_an_algorithm [2015/02/02 08:28] (current)
Line 1: Line 1:
-An algorithm is stored in a single page in the Algorithm namespace. Different variants ​require ​different pages. For example Factorial recursive and Factorial iterative.+====== Creating algorithms ====== 
 +===== Including an algorithm in a page ===== 
 +An algorithm is stored in a single page in the Algorithm namespace. Different variants ​of the same algorithm are stored on different pages. For  
 +example Factorial recursive and Factorial iterative.
-====== Including an algorithm in a page ====== +You include an algorithm on a different page using the algorithm tag. The last part of the tag is the title of the algorithm page. 
-You include an algorithm on a different page using the algorithm tag. The title attribute ​is set to the title of the algorithm page. +<code
-<pre+[algorithm Fisher-Yates shuffle] 
-<algorithm ​title="​Fisher-Yates shuffle" height=200></​algorithm>​ +</code>
 This transcludes the algorithm from [[Algorithm:​Fisher-Yates shuffle]]. This transcludes the algorithm from [[Algorithm:​Fisher-Yates shuffle]].
-====== Creating an algorithm page ====== +===== Creating an algorithm page ===== 
-An algorithm page is split into three sections: +An algorithm page is split into five sections: ​Source, ​Support, Unit Tests, Options, and Visualisation. Each section is editable in a tabbed code editor at the bottom of the algorithm page.
-<​pre>​ +
-====== Algorithm ====== +
-====== ​Support ​====== +
-====== ​Visualisation ​====== +
-Each of these sections contains code wrapped in &​lt;​code&​gt;​ tags.+{{ :​editor-tabs.png?nolink |}}
-====== Algorithm ​====== +==== Algorithm ==== 
-The 1st section contains the algorithm. This is the code that the user sees in the interactive environment.+The 1st section contains the algorithm. This is the code that the user sees in the interactive environment. For example, this is the code for the Fisher-Yates shuffle algorithm.
 <​code>​ <​code>​
 function shuffle(a) { function shuffle(a) {
Line 31: Line 28:
 </​code>​ </​code>​
-====== Support ​====== +==== Support ==== 
-The 2nd section contains the support code. This is support ​code, such as functions ​that the main algorithm ​uses. If it also includes a run() function this function is called when running the algorithm.+The 2nd section contains the support code. This is code that the main algorithm ​makes use of, for example utility functions. If the support code also includes a ''​run()'' ​function ​then this function is called when running the algorithm, instead of running the algorithm code from line 1.
 <​code>​ <​code>​
 function swap(a, i, j) { function swap(a, i, j) {
Line 43: Line 40:
 </​code>​ </​code>​
-====== ​Visualisation ​====== +==== Unit Tests ==== 
-The 3rd section contains the visualisation codeThis is a complete webpage that contains an update() functionwhich is called for every new line when running ​the algorithm. The update function takes two arguments, ​the current node in the AST and an execution context.+The unit tests section should contain unit tests to ensure the algorithm is correct. Each function in this section whose name has a '​test'​ prefix will be run on a web-worker thread. If there is any exception thrown during running the function the test fails. 
 +==== Options ​==== 
 +The 4rd section contains ​options in JSON format. Available options are 
 +  * ''​title''​ -- The title algorithm. 
 +  * ''​height''​ -- The height of the transcluded algorithm. 
 +  * ''​preRunSource''​ -- If true, the algorithm ​source will be run at load time and the debugger buttons will initially be disabled. The debug controls enable when ''​runScript("​..."​)''​ is called from the visualisation. For an example of this in use see [[algorithm:​linked-list]]. 
 +  * ''​persistentGlobals''​ -- This is an array of strings referring to global variablesThese are passed to web-workers each time ''​runScript''​ is called. 
 +  * ''​import''​ -- An array of strings of algorithm pages that will be imported as support code.  
 +A simple example is:
 <​code>​ <​code>​
-<​html>​ +{ 
-  <​head>​ +    "title":"​Fisher-Yates shuffle", 
-    ​<script type="text/​javascript"+    "height":"270px
-        function update(n, x) { +}
-            var element = document.getElementById("​container"​);​ +
-            var i = x.lookupInScope("​i"​);​ +
-            var j = x.lookupInScope("​j"​);​ +
-            var a = x.lookupInScope("​a"​);​ +
-            var xValue = x.lookupInScope("​x"​);​ +
-            if (i) { +
-               var arrayString = "​[";​ +
-               for (var k=0; k<​a.length;​k++) { +
-                   ​arrayString += i===k? "<​span style=\"​color:red\">"​+a[k]+"</​span>"​ : j===k? "<​span style=\"​color:​blue\">"​+a[k]+"</​span>"​ : a[k]; +
-                   if (k < a.length-1) arrayString += ", ​"; +
-               } +
-               ​arrayString += "]"+
-               ​element.innerHTML = "a = " ​+ arrayString + "<​br>"​+"​i = "+i; +
-           ​} +
-        } +
-    </​script>​ +
-  </​head>​ +
-  <​body>​ +
-  <pre id="​container"></​pre>​ +
-  </​body>​ +
 </​code>​ </​code>​
 +For a more complex example see [[algorithm:​hash_set-open_hashing|λ Hash set open-hashing]].
 +==== Visualisation ====
 +The 4th section contains the visualisation code. This code is a self contained webpage, it is embedded in an iframe when displayed alongside the code.
 +The webpage must provide a global ''​update()''​ function, which is called at each new line when running the algorithm. The update function takes several arguments, ​
 +  * ''​n''​ the current node in the AST (This should be used very rarely)
 +  * ''​x''​ the execution context.
 +  * ''​isRunning''​ is the debugger in the middle of running code?
 +  * ''​duration''​ if the visualisation animates, how long it should take. If ''​duration''​ is below 0 then visualising can be skipped if the update function is stateless.
 +  * ''​prev''​ the prev continuation,​ if the visualisation is undo-able it should return a new prev continuation that calls this.
 +Two other functions are optional: ''​globals()''​ and ''​args()''​. If the visualisation contains a global function ''​args()''​ then the return value of calling that function will be passed into the ''​run()''​ support function. This allows the visualisation to supply the input to the algorithm. If a ''​globals()''​ function is provided then it returns an object whose keys are added to the globals of the interpreter.
creating_an_algorithm.1346527686.txt.gz · Last modified: 2015/02/02 08:24 (external edit)