Anonymous avatar Anonymous committed f60abf0

Improve performance of [head].

Comments (0)

Files changed (1)

   OF THE POSSIBILITY OF SUCH DAMAGE. 
  *---------------------------------------------------------------------------*)
 
-    
 type 'a node_t = 'a tree_t list
 and 'a tree_t = N of int * 'a * 'a list * 'a node_t
 
     
     let merge ts1 ts2 = merge_trees_ (normalize_ ts1) (normalize_ ts2)
     
+    let rec shift_tree_ = function
+        | [] -> raise Not_found
+        | x :: [] -> x
+        | hd :: tl ->
+            let hd' = shift_tree_ tl in
+            let x = root_ hd and y = root_ hd' in
+            if N.compare x y < 0 then hd else hd'
+    
+    let head ts = root_ (shift_tree_ ts)
+
     let rec remove_tree_ = function
         | [] -> raise Not_found
         | x :: [] -> x, []
             if N.compare x y < 0
                 then hd, tl
                 else hd', hd :: tl'
-    
-    let head ts = root_ (fst (remove_tree_ ts))
-    
+        
     let rec tail_loop_ ts = function
         | x :: xs' -> tail_loop_ (put x ts) xs'
         | [] -> ts
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.