Moved UpdateList algorithm to Appendix ldpatch
authorAlexandre Bertails <alexandre@bertails.org>
Sun, 14 Dec 2014 11:15:24 -0500
branchldpatch
changeset 924 25c11f178ac4
parent 923 cdee523c6f10
child 925 3f6caeb73213
Moved UpdateList algorithm to Appendix
ldpatch.html
--- a/ldpatch.html	Sat Dec 13 19:08:22 2014 -0500
+++ b/ldpatch.html	Sun Dec 14 11:15:24 2014 -0500
@@ -638,95 +638,10 @@
               <li><code>..</code> denotes the empty slice located at the end of the list</li>
           </ul>
 
-         <section id="updatelist-algo">
-           <h3>Algorithm</h3>
-           <p>
-               Below is an algorithm explaining how <code>UpdateList s p i<sub>min</sub>..i<sub>max</sub> collection</code> can be processed.
-           </p>
-           <ul>
-             <li>
-               <b class="algo">Let</b> <var>s<sub>pre</sub></var> be <var>s</var>, <var>p<sub>pre</sub></var> be <var>p</var> and <var>o<sub>pre</sub></var> the object of the triple (<var>s</var>, <var>p</var>, ?) from the <a>target graph</a>.
-             </li>
-             <li>
-               <b class="algo">Repeat</b> <var>i<sub>min</sub></var> times:
-               <ul>
-                 <li>
-                   <b class="algo">Set</b> <var>s<sub>pre</sub></var> to <var>o<sub>pre</sub></var>, <var>p<sub>pre</sub></var> to <code>rdf:rest</code> and <var>o<sub>pre</sub></var> to the object of the triple (<var>o<sub>pre</sub></var>, <code>rdf:rest</code>, ?) from the <a>target graph</a>.
-                 </li>
-               </ul>
-             </li>
-             <li>
-               <b class="algo">Let</b> <var>s<sub>post</sub></var> be <var>s<sub>pre</sub></var>, <var>p<sub>post</sub></var> be <var>p<sub>pre</sub></var> and <var>o<sub>post</sub></var> be <var>o<sub>pre</sub></var>.
-             </li>
-             <li>
-               <b class="algo">Repeat</b> (<var>i<sub>max</sub></var>-<var>i<sub>min</sub></var>) times:
-               <ul>
-                 <li>
-                   Remove from the <a>target graph</a> the arcs (<var>s<sub>post</sub></var>, <var>p<sub>post</sub></var>, <var>o<sub>post</sub></var>).
-                 </li>
-                 <li>
-                   <b class="algo">Let</b> <var>elt</var> be the object of the triple (<var>o<sub>post</sub></var>, <code>rdf:first</code>, ?). Remove from the <a>target graph</a> the arc (<var>o<sub>post</sub></var>, <code>rdf:first</code>, <var>elt</var>). <b class="algo">If</b> <var>elt</var> is a blank node, <b class="algo">Then</b> apply the <a>Cut</a> operation on <var>elt</var>.
-                 </li>
-                 <li>
-                   <b class="algo">Set</b> <var>s<sub>post</sub></var> to <var>o<sub>post</sub></var>, <var>p<sub>post</sub></var> to <code>rdf:rest</code> and <var>o<sub>post</sub></var> to the object of the triple (<var>o<sub>post</sub></var>, <code>rdf:rest</code>, ?) from the <a>target graph</a>.
-                 </li>
-               </ul>
-             </li>
-             <li>
-               Remove from the <a>target graph</a> the arcs (<var>s<sub>pre</sub></var>, <var>p<sub>pre</sub></var>, <var>o<sub>pre</sub></var>) and (<var>s<sub>post</sub></var>, <var>p<sub>post</sub></var>, <var>o<sub>post</sub></var>). (NB: in some situations, they may be the same arc, or have already been removed by a previous step)
-             </li>
-             <li>
-               <b class="algo">If</b> <var>col</var> is the empty collection
-               <ul>
-                 <li>
-                   <b class="algo">Then</b>
-                   <ul>
-                     <li>
-                       Add in the <a>target graph</a> the arc (<var>s<sub>pre</sub></var>, <var>p<sub>pre</sub></var>, <var>o<sub>post</sub></var>).
-                     </li>
-                   </ul>
-                 </li>
-                 <li>
-                   <b class="algo">Else</b>
-                   <ul>
-                     <li>
-                       Add all the arcs resulting from the parsing of <var>col</var> to the target graph, let <var>fst</var> be the first node of the corresponding new collection, and <var>lst</var> the last node of that collection (excluding <code>rdf:nil</code>).
-                     </li>
-                     <li>
-                       Remove from the <a>target graph</a> the arc (<var>lst</var>, <code>rdf:rest</code>, <code>rdf:nil</code>).
-                     </li>
-                     <li>
-                       Add in the <a>target graph</a> the arcs (<var>s<sub>pre</sub></var>, <var>p<sub>pre</sub></var>, <var>fst</var>) and (<var>lst</var>, <code>rdf:rest</code>, <var>o<sub>post</sub></var>).
-                     </li>
-                   </ul>
-                 </li>
-               </ul>
-             </li>
-             
-          </section>
+          <p>
+              <a href="#updatelist-algo">Appendix A</a> contains a detailed algorithm for implementing the <a>UpdateList</a> logic using reified <code>rdf:List</code>.
+          </p>
 
-          <section>
-            <h3>Example</h3>
-
-            <p>
-                Here is an illustration of the <a href="#updatelist-algo">algorithm introduced previously</a>.
-            </p>
-            <p>
-                Consider the graph represented in <a href="#fig-graph-containing-a-collection"></a>. The result of applying the operation <code>UpdateList :s :p 2..4 ("foo" "bar" "baz").</code> on the collection in that graph can be seen in <a href="#fig-updatelist-result"></a>.
-            </p>
-
-            <figure id="fig-graph-containing-a-collection">
-              <img src="fig-alt-update-list.svg" alt="( &quote;lorem&quote; &quote;ipsum&quote; &quote;dolor&quote; &quote;sit&quote; &quote;amet&quote; ) ( &quote;foo&quote; &quote;bar&quote; &quote;baz&quote; )">
-              <figcaption>Graph with a collection</figcaption>
-            </figure>
-
-            <figure id="fig-updatelist-result">
-              <img src="fig-alt-update-list-2.svg" alt="( &quote;lorem&quote; &quote;ipsum&quote; &quote;dolor&quote; &quote;sit&quote; &quote;amet&quote; ) ( &quote;foo&quote; &quote;bar&quote; &quote;baz&quote; )">
-              <figcaption>Applying <code>UpdateList</code></figcaption>
-            </figure>
-          </section>
-
-        </section>
       </section>
 
 
@@ -1229,6 +1144,97 @@
 
     </section>
 
+
+    <section class="appendix informative" id="updatelist-algo">
+      <h2>UpdateList Algorithm</h2>
+
+      <p>
+          Below is an algorithm explaining how <code>UpdateList s p i<sub>min</sub>..i<sub>max</sub> collection</code> can be processed in the presence of a reified <code>rdf:List</code>, i.e. encoded with <code>rdf:first</code> and <code>rdf:rest</code>. Implementers may take advantage of a more native encoding for <code>rdf:List</code>.
+      </p>
+      <ul>
+          <li>
+              <b class="algo">Let</b> <var>s<sub>pre</sub></var> be <var>s</var>, <var>p<sub>pre</sub></var> be <var>p</var> and <var>o<sub>pre</sub></var> the object of the triple (<var>s</var>, <var>p</var>, ?) from the <a>target graph</a>.
+          </li>
+          <li>
+              <b class="algo">Repeat</b> <var>i<sub>min</sub></var> times:
+              <ul>
+                  <li>
+                      <b class="algo">Set</b> <var>s<sub>pre</sub></var> to <var>o<sub>pre</sub></var>, <var>p<sub>pre</sub></var> to <code>rdf:rest</code> and <var>o<sub>pre</sub></var> to the object of the triple (<var>o<sub>pre</sub></var>, <code>rdf:rest</code>, ?) from the <a>target graph</a>.
+                  </li>
+              </ul>
+          </li>
+          <li>
+              <b class="algo">Let</b> <var>s<sub>post</sub></var> be <var>s<sub>pre</sub></var>, <var>p<sub>post</sub></var> be <var>p<sub>pre</sub></var> and <var>o<sub>post</sub></var> be <var>o<sub>pre</sub></var>.
+          </li>
+          <li>
+              <b class="algo">Repeat</b> (<var>i<sub>max</sub></var>-<var>i<sub>min</sub></var>) times:
+              <ul>
+                  <li>
+                      Remove from the <a>target graph</a> the arcs (<var>s<sub>post</sub></var>, <var>p<sub>post</sub></var>, <var>o<sub>post</sub></var>).
+                  </li>
+                  <li>
+                      <b class="algo">Let</b> <var>elt</var> be the object of the triple (<var>o<sub>post</sub></var>, <code>rdf:first</code>, ?). Remove from the <a>target graph</a> the arc (<var>o<sub>post</sub></var>, <code>rdf:first</code>, <var>elt</var>). <b class="algo">If</b> <var>elt</var> is a blank node, <b class="algo">Then</b> apply the <a>Cut</a> operation on <var>elt</var>.
+                  </li>
+                  <li>
+                      <b class="algo">Set</b> <var>s<sub>post</sub></var> to <var>o<sub>post</sub></var>, <var>p<sub>post</sub></var> to <code>rdf:rest</code> and <var>o<sub>post</sub></var> to the object of the triple (<var>o<sub>post</sub></var>, <code>rdf:rest</code>, ?) from the <a>target graph</a>.
+                  </li>
+              </ul>
+          </li>
+          <li>
+              Remove from the <a>target graph</a> the arcs (<var>s<sub>pre</sub></var>, <var>p<sub>pre</sub></var>, <var>o<sub>pre</sub></var>) and (<var>s<sub>post</sub></var>, <var>p<sub>post</sub></var>, <var>o<sub>post</sub></var>). (NB: in some situations, they may be the same arc, or have already been removed by a previous step)
+          </li>
+          <li>
+              <b class="algo">If</b> <var>col</var> is the empty collection
+              <ul>
+                  <li>
+                      <b class="algo">Then</b>
+                      <ul>
+                          <li>
+                              Add in the <a>target graph</a> the arc (<var>s<sub>pre</sub></var>, <var>p<sub>pre</sub></var>, <var>o<sub>post</sub></var>).
+                          </li>
+                      </ul>
+                  </li>
+                  <li>
+                      <b class="algo">Else</b>
+                      <ul>
+                          <li>
+                              Add all the arcs resulting from the parsing of <var>col</var> to the target graph, let <var>fst</var> be the first node of the corresponding new collection, and <var>lst</var> the last node of that collection (excluding <code>rdf:nil</code>).
+                          </li>
+                          <li>
+                              Remove from the <a>target graph</a> the arc (<var>lst</var>, <code>rdf:rest</code>, <code>rdf:nil</code>).
+                          </li>
+                          <li>
+                              Add in the <a>target graph</a> the arcs (<var>s<sub>pre</sub></var>, <var>p<sub>pre</sub></var>, <var>fst</var>) and (<var>lst</var>, <code>rdf:rest</code>, <var>o<sub>post</sub></var>).
+                          </li>
+                      </ul>
+                  </li>
+              </ul>
+          </li>
+      </ul>          
+
+      <p>
+          Here is an illustration of the previous algorithm.
+      </p>
+      <p>
+          Consider the graph represented in <a href="#fig-graph-containing-a-collection"></a>. The result of applying the operation <code>UpdateList :s :p 2..4 ("foo" "bar" "baz").</code> on the collection in that graph can be seen in <a href="#fig-updatelist-result"></a>.
+      </p>
+          
+      <figure id="fig-graph-containing-a-collection">
+          <img src="fig-alt-update-list.svg" alt="( &quote;lorem&quote; &quote;ipsum&quote; &quote;dolor&quote; &quote;sit&quote; &quote;amet&quote; ) ( &quote;foo&quote; &quote;bar&quote; &quote;baz&quote; )">
+          <figcaption>Graph with a collection</figcaption>
+      </figure>
+      
+      <figure id="fig-updatelist-result">
+          <img src="fig-alt-update-list-2.svg" alt="( &quote;lorem&quote; &quote;ipsum&quote; &quote;dolor&quote; &quote;sit&quote; &quote;amet&quote; ) ( &quote;foo&quote; &quote;bar&quote; &quote;baz&quote; )">
+          <figcaption>Applying <code>UpdateList</code></figcaption>
+      </figure>
+
+    </section>
+    
+
+
+
+
     <section class="appendix" id="media-registration">
       <h2>Internet Media Type, File Extension and Macintosh File Type</h2>