Yit Phang Khoo avatar Yit Phang Khoo committed a690340

Add insert and remove functions to SAList.

Comments (0)

Files changed (3)

Source/Adapton/SAList.ml

             | `Cons ( x', xs' ) -> update_const xs (force xs'); x'
             | `Nil -> failwith "pop"
 
+        (** Update the [k]th element of a self-adjusting list to insert a value [x]. *)
+        let insert k x xs =
+            if k < 0 then invalid_arg "insert";
+            let rec insert k xs = match force xs with
+                | `Cons ( _, xs ) when k > 0 -> insert (k - 1) xs
+                | `Nil when k > 0 -> failwith "insert"
+                | `Cons _ | `Nil -> push x xs
+            in
+            insert k xs
+
+        (** Update the [k]th element of a self-adjusting list to remove a value and return it. *)
+        let remove k xs =
+            if k < 0 then invalid_arg "remove";
+            let rec remove k xs = match force xs with
+                | `Cons ( _, xs ) when k > 0 -> remove (k - 1) xs
+                | `Cons _ -> pop xs
+                | `Nil -> failwith "remove"
+            in
+            remove k xs
+
         (** Create memoizing constructor that concatenate two self-adjusting lists. *)
         let memo_append =
             memo2 (module L) (module L) begin fun append xs ys -> match force xs with

Source/Adapton/Signatures.ml

         val of_list : data list -> t
         val push : data -> t -> unit
         val pop : t -> data
+        val insert : int -> data -> t -> unit
+        val remove : int -> t -> data
         val memo_append : t -> t -> t
         val memo_filter : (data -> bool) -> (t -> t)
         val memo_filter_with_key

Test/TestAdapton/TestSAList.ml

                         end else
                             let k = abs k mod n in
                             if i then begin
-                                let rec insert k xs' = match I.force xs' with
-                                    | `Cons ( x', xs' ) when k > 0 -> insert (pred k) xs'
-                                    | _ -> I.push x xs'
-                                in
-                                insert k xs';
+                                I.insert k x xs';
                                 succ n
                             end else begin
-                                let rec delete k xs' = match I.force xs' with
-                                    | `Cons ( x', xs' ) when k > 0 -> delete (pred k) xs'
-                                    | `Cons _ -> ignore (I.pop xs')
-                                    | `Nil -> failwith "delete"
-                                in
-                                delete k xs';
+                                ignore (I.remove k xs');
                                 pred n
                             end
                     end n ks end;
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.