Applied Prototype $() performance patches (#4465, #4477) and updated script.aculo.us [Sam Stephenson, Thomas Fuchs]

git-svn-id: http://svn-commit.rubyonrails.org/rails/trunk@4122 5ecf4fe2-1ee6-0310-87b1-e25e094e27de

8 files changed, 608 insertions, 150 deletions

diff --git a/actionpack/CHANGELOG b/actionpack/CHANGELOG
index 7b3b44f7cb..61eb7c20cf 100644
--- a/actionpack/CHANGELOG
+++ b/actionpack/CHANGELOG
@@ -1,5 +1,7 @@
 *SVN*
 
+* Applied Prototype $() performance patches (#4465, #4477) and updated script.aculo.us [Sam Stephenson, Thomas Fuchs]
+
 * Added automated timestamping to AssetTagHelper methods for stylesheets, javascripts, and images when Action Controller is run under Rails [DHH]. Example:
 
     image_tag("rails.png") # => '<img alt="Rails" src="/images/rails.png?1143664135" />'
diff --git a/actionpack/lib/action_view/helpers/javascripts/dragdrop.js b/actionpack/lib/action_view/helpers/javascripts/dragdrop.js
index f1dc7ea2ab..a01b7be207 100644
--- a/actionpack/lib/action_view/helpers/javascripts/dragdrop.js
+++ b/actionpack/lib/action_view/helpers/javascripts/dragdrop.js
@@ -1,4 +1,5 @@
 // Copyright (c) 2005 Thomas Fuchs (http://script.aculo.us, http://mir.aculo.us)
+//           (c) 2005 Sammi Williams (http://www.oriontransfer.co.nz, sammi@oriontransfer.co.nz)
 // 
 // See scriptaculous.js for full license.
 
@@ -15,7 +16,8 @@ var Droppables = {
     element = $(element);
     var options = Object.extend({
       greedy:     true,
-      hoverclass: null  
+      hoverclass: null,
+      tree:       false
     }, arguments[1] || {});
 
     // cache containers
@@ -37,12 +39,27 @@ var Droppables = {
 
     this.drops.push(options);
   },
+  
+  findDeepestChild: function(drops) {
+    deepest = drops[0];
+      
+    for (i = 1; i < drops.length; ++i)
+      if (Element.isParent(drops[i].element, deepest.element))
+        deepest = drops[i];
+    
+    return deepest;
+  },
 
   isContained: function(element, drop) {
-    var parentNode = element.parentNode;
-    return drop._containers.detect(function(c) { return parentNode == c });
+    var containmentNode;
+    if(drop.tree) {
+      containmentNode = element.treeNode; 
+    } else {
+      containmentNode = element.parentNode;
+    }
+    return drop._containers.detect(function(c) { return containmentNode == c });
   },
-
+  
   isAffected: function(point, element, drop) {
     return (
       (drop.element!=element) &&
@@ -68,18 +85,22 @@ var Droppables = {
 
   show: function(point, element) {
     if(!this.drops.length) return;
+    var affected = [];
     
     if(this.last_active) this.deactivate(this.last_active);
     this.drops.each( function(drop) {
-      if(Droppables.isAffected(point, element, drop)) {
-        if(drop.onHover)
-           drop.onHover(element, drop.element, Position.overlap(drop.overlap, drop.element));
-        if(drop.greedy) { 
-          Droppables.activate(drop);
-          throw $break;
-        }
-      }
+      if(Droppables.isAffected(point, element, drop))
+        affected.push(drop);
     });
+        
+    if(affected.length>0) {
+      drop = Droppables.findDeepestChild(affected);
+      Position.within(drop.element, point[0], point[1]);
+      if(drop.onHover)
+        drop.onHover(element, drop.element, Position.overlap(drop.overlap, drop.element));
+      
+      Droppables.activate(drop);
+    }
   },
 
   fire: function(event, element) {
@@ -207,8 +228,10 @@ Draggable.prototype = {
 
     this.element = $(element);
     
-    if(options.handle && (typeof options.handle == 'string'))
-      this.handle = Element.childrenWithClassName(this.element, options.handle, true)[0];  
+    if(options.handle && (typeof options.handle == 'string')) {
+      var h = Element.childrenWithClassName(this.element, options.handle, true);
+      if(h.length>0) this.handle = h[0];
+    }
     if(!this.handle) this.handle = $(options.handle);
     if(!this.handle) this.handle = this.element;
     
@@ -412,6 +435,7 @@ Draggable.prototype = {
     if(this.scrollInterval) {
       clearInterval(this.scrollInterval);
       this.scrollInterval = null;
+      Draggables._lastScrollPointer = null;
     }
   },
   
@@ -440,7 +464,14 @@ Draggable.prototype = {
     Position.prepare();
     Droppables.show(Draggables._lastPointer, this.element);
     Draggables.notify('onDrag', this);
-    this.draw(Draggables._lastPointer);    
+    Draggables._lastScrollPointer = Draggables._lastScrollPointer || $A(Draggables._lastPointer);
+    Draggables._lastScrollPointer[0] += this.scrollSpeed[0] * delta / 1000;
+    Draggables._lastScrollPointer[1] += this.scrollSpeed[1] * delta / 1000;
+    if (Draggables._lastScrollPointer[0] < 0)
+      Draggables._lastScrollPointer[0] = 0;
+    if (Draggables._lastScrollPointer[1] < 0)
+      Draggables._lastScrollPointer[1] = 0;
+    this.draw(Draggables._lastScrollPointer);
     
     if(this.options.change) this.options.change(this);
   },
@@ -492,30 +523,41 @@ SortableObserver.prototype = {
 }
 
 var Sortable = {
-  sortables: new Array(),
+  sortables: {},
   
-  options: function(element){
-    element = $(element);
-    return this.sortables.detect(function(s) { return s.element == element });
+  _findRootElement: function(element) {
+    while (element.tagName != "BODY") {  
+      if(element.id && Sortable.sortables[element.id]) return element;
+      element = element.parentNode;
+    }
+  },
+
+  options: function(element) {
+    element = Sortable._findRootElement($(element));
+    if(!element) return;
+    return Sortable.sortables[element.id];
   },
   
   destroy: function(element){
-    element = $(element);
-    this.sortables.findAll(function(s) { return s.element == element }).each(function(s){
+    var s = Sortable.options(element);
+    
+    if(s) {
       Draggables.removeObserver(s.element);
       s.droppables.each(function(d){ Droppables.remove(d) });
       s.draggables.invoke('destroy');
-    });
-    this.sortables = this.sortables.reject(function(s) { return s.element == element });
+      
+      delete Sortable.sortables[s.element.id];
+    }
   },
-  
+
   create: function(element) {
     element = $(element);
     var options = Object.extend({ 
       element:     element,
       tag:         'li',       // assumes li children, override with tag: 'tagname'
       dropOnEmpty: false,
-      tree:        false,      // fixme: unimplemented
+      tree:        false,
+      treeTag:     'ul',
       overlap:     'vertical', // one of 'vertical', 'horizontal'
       constraint:  'vertical', // one of 'vertical', 'horizontal', false
       containment: element,    // also takes array of elements (or id's); or false
@@ -565,9 +607,17 @@ var Sortable = {
     var options_for_droppable = {
       overlap:     options.overlap,
       containment: options.containment,
+      tree:        options.tree,
       hoverclass:  options.hoverclass,
-      onHover:     Sortable.onHover,
-      greedy:      !options.dropOnEmpty
+      onHover:     Sortable.onHover
+      //greedy:      !options.dropOnEmpty
+    }
+    
+    var options_for_tree = {
+      onHover:      Sortable.onEmptyHover,
+      overlap:      options.overlap,
+      containment:  options.containment,
+      hoverclass:   options.hoverclass
     }
 
     // fix for gecko engine
@@ -576,12 +626,9 @@ var Sortable = {
     options.draggables = [];
     options.droppables = [];
 
-    // make it so
-
     // drop on empty handling
-    if(options.dropOnEmpty) {
-      Droppables.add(element,
-        {containment: options.containment, onHover: Sortable.onEmptyHover, greedy: false});
+    if(options.dropOnEmpty || options.tree) {
+      Droppables.add(element, options_for_tree);
       options.droppables.push(element);
     }
 
@@ -592,11 +639,20 @@ var Sortable = {
       options.draggables.push(
         new Draggable(e, Object.extend(options_for_draggable, { handle: handle })));
       Droppables.add(e, options_for_droppable);
+      if(options.tree) e.treeNode = element;
       options.droppables.push(e);      
     });
+    
+    if(options.tree) {
+      (Sortable.findTreeElements(element, options) || []).each( function(e) {
+        Droppables.add(e, options_for_tree);
+        e.treeNode = element;
+        options.droppables.push(e);
+      });
+    }
 
     // keep reference
-    this.sortables.push(options);
+    this.sortables[element.id] = options;
 
     // for onupdate
     Draggables.addObserver(new SortableObserver(element, options.onUpdate));
@@ -605,24 +661,21 @@ var Sortable = {
 
   // return all suitable-for-sortable elements in a guaranteed order
   findElements: function(element, options) {
-    if(!element.hasChildNodes()) return null;
-    var elements = [];
-    var only = options.only ? [options.only].flatten() : null;
-    $A(element.childNodes).each( function(e) {
-      if(e.tagName && e.tagName.toUpperCase()==options.tag.toUpperCase() &&
-        (!only || (Element.classNames(e).detect(function(v) { return only.include(v) }))))
-          elements.push(e);
-      if(options.tree) {
-        var grandchildren = this.findElements(e, options);
-        if(grandchildren) elements.push(grandchildren);
-      }
-    });
-
-    return (elements.length>0 ? elements.flatten() : null);
+    return Element.findChildren(
+      element, options.only, options.tree ? true : false, options.tag);
+  },
+  
+  findTreeElements: function(element, options) {
+    return Element.findChildren(
+      element, options.only, options.tree ? true : false, options.treeTag);
   },
 
   onHover: function(element, dropon, overlap) {
-    if(overlap>0.5) {
+    if(Element.isParent(dropon, element)) return;
+
+    if(overlap > .33 && overlap < .66 && Sortable.options(dropon).tree) {
+      return;
+    } else if(overlap>0.5) {
       Sortable.mark(dropon, 'before');
       if(dropon.previousSibling != element) {
         var oldParentNode = element.parentNode;
@@ -645,13 +698,37 @@ var Sortable = {
       }
     }
   },
-
-  onEmptyHover: function(element, dropon) {
-    if(element.parentNode!=dropon) {
-      var oldParentNode = element.parentNode;
-      dropon.appendChild(element);
+  
+  onEmptyHover: function(element, dropon, overlap) {
+    var oldParentNode = element.parentNode;
+    var droponOptions = Sortable.options(dropon);
+        
+    if(!Element.isParent(dropon, element)) {
+      var index;
+      
+      var children = Sortable.findElements(dropon, {tag: droponOptions.tag});
+      var child = null;
+            
+      if(children) {
+        var offset = Element.offsetSize(dropon, droponOptions.overlap) * (1.0 - overlap);
+        
+        for (index = 0; index < children.length; index += 1) {
+          if (offset - Element.offsetSize (children[index], droponOptions.overlap) >= 0) {
+            offset -= Element.offsetSize (children[index], droponOptions.overlap);
+          } else if (offset - (Element.offsetSize (children[index], droponOptions.overlap) / 2) >= 0) {
+            child = index + 1 < children.length ? children[index + 1] : null;
+            break;
+          } else {
+            child = children[index];
+            break;
+          }
+        }
+      }
+      
+      dropon.insertBefore(element, child);
+      
       Sortable.options(oldParentNode).onChange(element);
-      Sortable.options(dropon).onChange(element);
+      droponOptions.onChange(element);
     }
   },
 
@@ -683,6 +760,75 @@ var Sortable = {
     
     Element.show(Sortable._marker);
   },
+  
+  _tree: function(element, options, parent) {
+    var children = Sortable.findElements(element, options) || [];
+  
+    for (var i = 0; i < children.length; ++i) {
+      var match = children[i].id.match(options.format);
+
+      if (!match) continue;
+      
+      var child = {
+        id: encodeURIComponent(match ? match[1] : null),
+        element: element,
+        parent: parent,
+        children: new Array,
+        position: parent.children.length,
+        container: Sortable._findChildrenElement(children[i], options.treeTag.toUpperCase())
+      }
+      
+      /* Get the element containing the children and recurse over it */
+      if (child.container)
+        this._tree(child.container, options, child)
+      
+      parent.children.push (child);
+    }
+
+    return parent; 
+  },
+
+  /* Finds the first element of the given tag type within a parent element.
+    Used for finding the first LI[ST] within a L[IST]I[TEM].*/
+  _findChildrenElement: function (element, containerTag) {
+    if (element && element.hasChildNodes)
+      for (var i = 0; i < element.childNodes.length; ++i)
+        if (element.childNodes[i].tagName == containerTag)
+          return element.childNodes[i];
+  
+    return null;
+  },
+
+  tree: function(element) {
+    element = $(element);
+    var sortableOptions = this.options(element);
+    var options = Object.extend({
+      tag: sortableOptions.tag,
+      treeTag: sortableOptions.treeTag,
+      only: sortableOptions.only,
+      name: element.id,
+      format: sortableOptions.format
+    }, arguments[1] || {});
+    
+    var root = {
+      id: null,
+      parent: null,
+      children: new Array,
+      container: element,
+      position: 0
+    }
+    
+    return Sortable._tree (element, options, root);
+  },
+
+  /* Construct a [i] index for a particular node */
+  _constructIndex: function(node) {
+    var index = '';
+    do {
+      if (node.id) index = '[' + node.position + ']' + index;
+    } while ((node = node.parent) != null);
+    return index;
+  },
 
   sequence: function(element) {
     element = $(element);
@@ -705,20 +851,63 @@ var Sortable = {
     });
    
     new_sequence.each(function(ident) {
-        var n = nodeMap[ident];
-        if (n) {
-            n[1].appendChild(n[0]);
-            delete nodeMap[ident];
-        }
+      var n = nodeMap[ident];
+      if (n) {
+        n[1].appendChild(n[0]);
+        delete nodeMap[ident];
+      }
     });
   },
-
+  
   serialize: function(element) {
     element = $(element);
+    var options = Object.extend(Sortable.options(element), arguments[1] || {});
     var name = encodeURIComponent(
       (arguments[1] && arguments[1].name) ? arguments[1].name : element.id);
-    return Sortable.sequence(element, arguments[1]).map( function(item) {
-      return name + "[]=" + encodeURIComponent(item);
-    }).join('&');
+    
+    if (options.tree) {
+      return Sortable.tree(element, arguments[1]).children.map( function (item) {
+        return [name + Sortable._constructIndex(item) + "=" + 
+                encodeURIComponent(item.id)].concat(item.children.map(arguments.callee));
+      }).flatten().join('&');
+    } else {
+      return Sortable.sequence(element, arguments[1]).map( function(item) {
+        return name + "[]=" + encodeURIComponent(item);
+      }).join('&');
+    }
   }
 }
+
+/* Returns true if child is contained within element */
+Element.isParent = function(child, element) {
+  if (!child.parentNode || child == element) return false;
+
+  if (child.parentNode == element) return true;
+
+  return Element.isParent(child.parentNode, element);
+}
+
+Element.findChildren = function(element, only, recursive, tagName) {    
+  if(!element.hasChildNodes()) return null;
+  tagName = tagName.toUpperCase();
+  if(only) only = [only].flatten();
+  var elements = [];
+  $A(element.childNodes).each( function(e) {
+    if(e.tagName && e.tagName.toUpperCase()==tagName &&
+      (!only || (Element.classNames(e).detect(function(v) { return only.include(v) }))))
+        elements.push(e);
+    if(recursive) {
+      var grandchildren = Element.findChildren(e, only, recursive, tagName);
+      if(grandchildren) elements.push(grandchildren);
+    }
+  });
+
+  return (elements.length>0 ? elements.flatten() : []);
+}
+
+Element.offsetSize = function (element, type) {
+  if (type == 'vertical' || type == 'height')
+    return element.offsetHeight;
+  else
+    return element.offsetWidth;
+}
\ No newline at end of file
diff --git a/actionpack/lib/action_view/helpers/javascripts/effects.js b/actionpack/lib/action_view/helpers/javascripts/effects.js
index bcf836b83c..927400502d 100644
--- a/actionpack/lib/action_view/helpers/javascripts/effects.js
+++ b/actionpack/lib/action_view/helpers/javascripts/effects.js
@@ -77,9 +77,12 @@ Element.getInlineOpacity = function(element){
 }  
 
 Element.childrenWithClassName = function(element, className, findFirst) {
-  return [$A($(element).getElementsByTagName('*'))[findFirst ? 'detect' : 'select']( function(c) { 
-    return c.className ? Element.hasClassName(c, className) : false;
-  })].flatten();
+  var classNameRegExp = new RegExp("(^|\\s)" + className + "(\\s|$)");
+  var results = $A($(element).getElementsByTagName('*'))[findFirst ? 'detect' : 'select']( function(c) { 
+    return (c.className && c.className.match(classNameRegExp));
+  });
+  if(!results) results = [];
+  return results;
 }
 
 Element.forceRerendering = function(element) {
@@ -91,11 +94,6 @@ Element.forceRerendering = function(element) {
   } catch(e) { }
 };
 
-['setOpacity','getOpacity','getInlineOpacity','forceRerendering','setContentZoom',
- 'collectTextNodes','collectTextNodesIgnoreClass','childrenWithClassName'].each( 
-  function(f) { Element.Methods[f] = Element[f]; } 
-);
-
 /*--------------------------------------------------------------------------*/
 
 Array.prototype.call = function() {
@@ -943,11 +941,18 @@ Effect.Fold = function(element) {
         effect.element.setStyle(oldStyle);
       } });
   }}, arguments[1] || {}));
-}
+};
+
+['setOpacity','getOpacity','getInlineOpacity','forceRerendering','setContentZoom',
+ 'collectTextNodes','collectTextNodesIgnoreClass','childrenWithClassName'].each( 
+  function(f) { Element.Methods[f] = Element[f]; }
+);
 
 Element.Methods.visualEffect = function(element, effect, options) {
   s = effect.gsub(/_/, '-').camelize();
   effect_class = s.charAt(0).toUpperCase() + s.substring(1);
   new Effect[effect_class](element, options);
   return $(element);
-};
\ No newline at end of file
+};
+
+Element.addMethods();
\ No newline at end of file
diff --git a/actionpack/lib/action_view/helpers/javascripts/prototype.js b/actionpack/lib/action_view/helpers/javascripts/prototype.js
index 2d4ba34c18..56817066b6 100644
--- a/actionpack/lib/action_view/helpers/javascripts/prototype.js
+++ b/actionpack/lib/action_view/helpers/javascripts/prototype.js
@@ -900,13 +900,14 @@ if (!window.Element)
 
 Element.extend = function(element) {
   if (!element) return;
+  if (_nativeExtensions) return element;
 
   if (!element._extended && element.tagName && element != window) {
-    var methods = Element.Methods;
+    var methods = Element.Methods, cache = Element.extend.cache;
     for (property in methods) {
       var value = methods[property];
       if (typeof value == 'function')
-        element[property] = value.bind(null, element);
+        element[property] = cache.findOrStore(value);
     }
   }
 
@@ -914,6 +915,14 @@ Element.extend = function(element) {
   return element;
 }
 
+Element.extend.cache = { 
+  findOrStore: function(value) { 
+    return this[value] = this[value] || function() { 
+      return value.apply(null, [this].concat($A(arguments))); 
+    } 
+  }
+}
+
 Element.Methods = {
   visible: function(element) {
     return $(element).style.display != 'none';
@@ -1105,6 +1114,30 @@ Element.Methods = {
 
 Object.extend(Element, Element.Methods);
 
+var _nativeExtensions = false;
+
+if(!HTMLElement && /Konqueror|Safari|KHTML/.test(navigator.userAgent)) {
+  var HTMLElement = {}
+  HTMLElement.prototype = document.createElement('div').__proto__;
+}
+
+Element.addMethods = function(methods) {
+  Object.extend(Element.Methods, methods || {});
+  
+  if(typeof HTMLElement != 'undefined') {
+    var methods = Element.Methods, cache = Element.extend.cache;
+    for (property in methods) {
+      var value = methods[property];
+      if (typeof value == 'function') {
+        HTMLElement.prototype[property] = cache.findOrStore(value);
+      }
+    }
+    _nativeExtensions = true;
+  }
+}
+
+Element.addMethods();
+
 var Toggle = new Object();
 Toggle.display = Element.toggle;
 
diff --git a/railties/CHANGELOG b/railties/CHANGELOG
index e77b59d170..9ecc07813d 100644
--- a/railties/CHANGELOG
+++ b/railties/CHANGELOG
@@ -1,5 +1,7 @@
 *SVN*
 
+* Applied Prototype $() performance patches (#4465, #4477) and updated script.aculo.us [Sam Stephenson, Thomas Fuchs]
+
 * Use --simple-prompt instead of --prompt-mode simple for console compatibility with Windows/Ruby 1.8.2 #4532 [starr@starrnhorne.com]
 
 * Make Rails::VERSION implicitly loadable #4491. [Nicholas Seckar]
diff --git a/railties/html/javascripts/dragdrop.js b/railties/html/javascripts/dragdrop.js
index f1dc7ea2ab..a01b7be207 100644
--- a/railties/html/javascripts/dragdrop.js
+++ b/railties/html/javascripts/dragdrop.js
@@ -1,4 +1,5 @@
 // Copyright (c) 2005 Thomas Fuchs (http://script.aculo.us, http://mir.aculo.us)
+//           (c) 2005 Sammi Williams (http://www.oriontransfer.co.nz, sammi@oriontransfer.co.nz)
 // 
 // See scriptaculous.js for full license.
 
@@ -15,7 +16,8 @@ var Droppables = {
     element = $(element);
     var options = Object.extend({
       greedy:     true,
-      hoverclass: null  
+      hoverclass: null,
+      tree:       false
     }, arguments[1] || {});
 
     // cache containers
@@ -37,12 +39,27 @@ var Droppables = {
 
     this.drops.push(options);
   },
+  
+  findDeepestChild: function(drops) {
+    deepest = drops[0];
+      
+    for (i = 1; i < drops.length; ++i)
+      if (Element.isParent(drops[i].element, deepest.element))
+        deepest = drops[i];
+    
+    return deepest;
+  },
 
   isContained: function(element, drop) {
-    var parentNode = element.parentNode;
-    return drop._containers.detect(function(c) { return parentNode == c });
+    var containmentNode;
+    if(drop.tree) {
+      containmentNode = element.treeNode; 
+    } else {
+      containmentNode = element.parentNode;
+    }
+    return drop._containers.detect(function(c) { return containmentNode == c });
   },
-
+  
   isAffected: function(point, element, drop) {
     return (
       (drop.element!=element) &&
@@ -68,18 +85,22 @@ var Droppables = {
 
   show: function(point, element) {
     if(!this.drops.length) return;
+    var affected = [];
     
     if(this.last_active) this.deactivate(this.last_active);
     this.drops.each( function(drop) {
-      if(Droppables.isAffected(point, element, drop)) {
-        if(drop.onHover)
-           drop.onHover(element, drop.element, Position.overlap(drop.overlap, drop.element));
-        if(drop.greedy) { 
-          Droppables.activate(drop);
-          throw $break;
-        }
-      }
+      if(Droppables.isAffected(point, element, drop))
+        affected.push(drop);
     });
+        
+    if(affected.length>0) {
+      drop = Droppables.findDeepestChild(affected);
+      Position.within(drop.element, point[0], point[1]);
+      if(drop.onHover)
+        drop.onHover(element, drop.element, Position.overlap(drop.overlap, drop.element));
+      
+      Droppables.activate(drop);
+    }
   },
 
   fire: function(event, element) {
@@ -207,8 +228,10 @@ Draggable.prototype = {
 
     this.element = $(element);
     
-    if(options.handle && (typeof options.handle == 'string'))
-      this.handle = Element.childrenWithClassName(this.element, options.handle, true)[0];  
+    if(options.handle && (typeof options.handle == 'string')) {
+      var h = Element.childrenWithClassName(this.element, options.handle, true);
+      if(h.length>0) this.handle = h[0];
+    }
     if(!this.handle) this.handle = $(options.handle);
     if(!this.handle) this.handle = this.element;
     
@@ -412,6 +435,7 @@ Draggable.prototype = {
     if(this.scrollInterval) {
       clearInterval(this.scrollInterval);
       this.scrollInterval = null;
+      Draggables._lastScrollPointer = null;
     }
   },
   
@@ -440,7 +464,14 @@ Draggable.prototype = {
     Position.prepare();
     Droppables.show(Draggables._lastPointer, this.element);
     Draggables.notify('onDrag', this);
-    this.draw(Draggables._lastPointer);    
+    Draggables._lastScrollPointer = Draggables._lastScrollPointer || $A(Draggables._lastPointer);
+    Draggables._lastScrollPointer[0] += this.scrollSpeed[0] * delta / 1000;
+    Draggables._lastScrollPointer[1] += this.scrollSpeed[1] * delta / 1000;
+    if (Draggables._lastScrollPointer[0] < 0)
+      Draggables._lastScrollPointer[0] = 0;
+    if (Draggables._lastScrollPointer[1] < 0)
+      Draggables._lastScrollPointer[1] = 0;
+    this.draw(Draggables._lastScrollPointer);
     
     if(this.options.change) this.options.change(this);
   },
@@ -492,30 +523,41 @@ SortableObserver.prototype = {
 }
 
 var Sortable = {
-  sortables: new Array(),
+  sortables: {},
   
-  options: function(element){
-    element = $(element);
-    return this.sortables.detect(function(s) { return s.element == element });
+  _findRootElement: function(element) {
+    while (element.tagName != "BODY") {  
+      if(element.id && Sortable.sortables[element.id]) return element;
+      element = element.parentNode;
+    }
+  },
+
+  options: function(element) {
+    element = Sortable._findRootElement($(element));
+    if(!element) return;
+    return Sortable.sortables[element.id];
   },
   
   destroy: function(element){
-    element = $(element);
-    this.sortables.findAll(function(s) { return s.element == element }).each(function(s){
+    var s = Sortable.options(element);
+    
+    if(s) {
       Draggables.removeObserver(s.element);
       s.droppables.each(function(d){ Droppables.remove(d) });
       s.draggables.invoke('destroy');
-    });
-    this.sortables = this.sortables.reject(function(s) { return s.element == element });
+      
+      delete Sortable.sortables[s.element.id];
+    }
   },
-  
+
   create: function(element) {
     element = $(element);
     var options = Object.extend({ 
       element:     element,
       tag:         'li',       // assumes li children, override with tag: 'tagname'
       dropOnEmpty: false,
-      tree:        false,      // fixme: unimplemented
+      tree:        false,
+      treeTag:     'ul',
       overlap:     'vertical', // one of 'vertical', 'horizontal'
       constraint:  'vertical', // one of 'vertical', 'horizontal', false
       containment: element,    // also takes array of elements (or id's); or false
@@ -565,9 +607,17 @@ var Sortable = {
     var options_for_droppable = {
       overlap:     options.overlap,
       containment: options.containment,
+      tree:        options.tree,
       hoverclass:  options.hoverclass,
-      onHover:     Sortable.onHover,
-      greedy:      !options.dropOnEmpty
+      onHover:     Sortable.onHover
+      //greedy:      !options.dropOnEmpty
+    }
+    
+    var options_for_tree = {
+      onHover:      Sortable.onEmptyHover,
+      overlap:      options.overlap,
+      containment:  options.containment,
+      hoverclass:   options.hoverclass
     }
 
     // fix for gecko engine
@@ -576,12 +626,9 @@ var Sortable = {
     options.draggables = [];
     options.droppables = [];
 
-    // make it so
-
     // drop on empty handling
-    if(options.dropOnEmpty) {
-      Droppables.add(element,
-        {containment: options.containment, onHover: Sortable.onEmptyHover, greedy: false});
+    if(options.dropOnEmpty || options.tree) {
+      Droppables.add(element, options_for_tree);
       options.droppables.push(element);
     }
 
@@ -592,11 +639,20 @@ var Sortable = {
       options.draggables.push(
         new Draggable(e, Object.extend(options_for_draggable, { handle: handle })));
       Droppables.add(e, options_for_droppable);
+      if(options.tree) e.treeNode = element;
       options.droppables.push(e);      
     });
+    
+    if(options.tree) {
+      (Sortable.findTreeElements(element, options) || []).each( function(e) {
+        Droppables.add(e, options_for_tree);
+        e.treeNode = element;
+        options.droppables.push(e);
+      });
+    }
 
     // keep reference
-    this.sortables.push(options);
+    this.sortables[element.id] = options;
 
     // for onupdate
     Draggables.addObserver(new SortableObserver(element, options.onUpdate));
@@ -605,24 +661,21 @@ var Sortable = {
 
   // return all suitable-for-sortable elements in a guaranteed order
   findElements: function(element, options) {
-    if(!element.hasChildNodes()) return null;
-    var elements = [];
-    var only = options.only ? [options.only].flatten() : null;
-    $A(element.childNodes).each( function(e) {
-      if(e.tagName && e.tagName.toUpperCase()==options.tag.toUpperCase() &&
-        (!only || (Element.classNames(e).detect(function(v) { return only.include(v) }))))
-          elements.push(e);
-      if(options.tree) {
-        var grandchildren = this.findElements(e, options);
-        if(grandchildren) elements.push(grandchildren);
-      }
-    });
-
-    return (elements.length>0 ? elements.flatten() : null);
+    return Element.findChildren(
+      element, options.only, options.tree ? true : false, options.tag);
+  },
+  
+  findTreeElements: function(element, options) {
+    return Element.findChildren(
+      element, options.only, options.tree ? true : false, options.treeTag);
   },
 
   onHover: function(element, dropon, overlap) {
-    if(overlap>0.5) {
+    if(Element.isParent(dropon, element)) return;
+
+    if(overlap > .33 && overlap < .66 && Sortable.options(dropon).tree) {
+      return;
+    } else if(overlap>0.5) {
       Sortable.mark(dropon, 'before');
       if(dropon.previousSibling != element) {
         var oldParentNode = element.parentNode;
@@ -645,13 +698,37 @@ var Sortable = {
       }
     }
   },
-
-  onEmptyHover: function(element, dropon) {
-    if(element.parentNode!=dropon) {
-      var oldParentNode = element.parentNode;
-      dropon.appendChild(element);
+  
+  onEmptyHover: function(element, dropon, overlap) {
+    var oldParentNode = element.parentNode;
+    var droponOptions = Sortable.options(dropon);
+        
+    if(!Element.isParent(dropon, element)) {
+      var index;
+      
+      var children = Sortable.findElements(dropon, {tag: droponOptions.tag});
+      var child = null;
+            
+      if(children) {
+        var offset = Element.offsetSize(dropon, droponOptions.overlap) * (1.0 - overlap);
+        
+        for (index = 0; index < children.length; index += 1) {
+          if (offset - Element.offsetSize (children[index], droponOptions.overlap) >= 0) {
+            offset -= Element.offsetSize (children[index], droponOptions.overlap);
+          } else if (offset - (Element.offsetSize (children[index], droponOptions.overlap) / 2) >= 0) {
+            child = index + 1 < children.length ? children[index + 1] : null;
+            break;
+          } else {
+            child = children[index];
+            break;
+          }
+        }
+      }
+      
+      dropon.insertBefore(element, child);
+      
       Sortable.options(oldParentNode).onChange(element);
-      Sortable.options(dropon).onChange(element);
+      droponOptions.onChange(element);
     }
   },
 
@@ -683,6 +760,75 @@ var Sortable = {
     
     Element.show(Sortable._marker);
   },
+  
+  _tree: function(element, options, parent) {
+    var children = Sortable.findElements(element, options) || [];
+  
+    for (var i = 0; i < children.length; ++i) {
+      var match = children[i].id.match(options.format);
+
+      if (!match) continue;
+      
+      var child = {
+        id: encodeURIComponent(match ? match[1] : null),
+        element: element,
+        parent: parent,
+        children: new Array,
+        position: parent.children.length,
+        container: Sortable._findChildrenElement(children[i], options.treeTag.toUpperCase())
+      }
+      
+      /* Get the element containing the children and recurse over it */
+      if (child.container)
+        this._tree(child.container, options, child)
+      
+      parent.children.push (child);
+    }
+
+    return parent; 
+  },
+
+  /* Finds the first element of the given tag type within a parent element.
+    Used for finding the first LI[ST] within a L[IST]I[TEM].*/
+  _findChildrenElement: function (element, containerTag) {
+    if (element && element.hasChildNodes)
+      for (var i = 0; i < element.childNodes.length; ++i)
+        if (element.childNodes[i].tagName == containerTag)
+          return element.childNodes[i];
+  
+    return null;
+  },
+
+  tree: function(element) {
+    element = $(element);
+    var sortableOptions = this.options(element);
+    var options = Object.extend({
+      tag: sortableOptions.tag,
+      treeTag: sortableOptions.treeTag,
+      only: sortableOptions.only,
+      name: element.id,
+      format: sortableOptions.format
+    }, arguments[1] || {});
+    
+    var root = {
+      id: null,
+      parent: null,
+      children: new Array,
+      container: element,
+      position: 0
+    }
+    
+    return Sortable._tree (element, options, root);
+  },
+
+  /* Construct a [i] index for a particular node */
+  _constructIndex: function(node) {
+    var index = '';
+    do {
+      if (node.id) index = '[' + node.position + ']' + index;
+    } while ((node = node.parent) != null);
+    return index;
+  },
 
   sequence: function(element) {
     element = $(element);
@@ -705,20 +851,63 @@ var Sortable = {
     });
    
     new_sequence.each(function(ident) {
-        var n = nodeMap[ident];
-        if (n) {
-            n[1].appendChild(n[0]);
-            delete nodeMap[ident];
-        }
+      var n = nodeMap[ident];
+      if (n) {
+        n[1].appendChild(n[0]);
+        delete nodeMap[ident];
+      }
     });
   },
-
+  
   serialize: function(element) {
     element = $(element);
+    var options = Object.extend(Sortable.options(element), arguments[1] || {});
     var name = encodeURIComponent(
       (arguments[1] && arguments[1].name) ? arguments[1].name : element.id);
-    return Sortable.sequence(element, arguments[1]).map( function(item) {
-      return name + "[]=" + encodeURIComponent(item);
-    }).join('&');
+    
+    if (options.tree) {
+      return Sortable.tree(element, arguments[1]).children.map( function (item) {
+        return [name + Sortable._constructIndex(item) + "=" + 
+                encodeURIComponent(item.id)].concat(item.children.map(arguments.callee));
+      }).flatten().join('&');
+    } else {
+      return Sortable.sequence(element, arguments[1]).map( function(item) {
+        return name + "[]=" + encodeURIComponent(item);
+      }).join('&');
+    }
   }
 }
+
+/* Returns true if child is contained within element */
+Element.isParent = function(child, element) {
+  if (!child.parentNode || child == element) return false;
+
+  if (child.parentNode == element) return true;
+
+  return Element.isParent(child.parentNode, element);
+}
+
+Element.findChildren = function(element, only, recursive, tagName) {    
+  if(!element.hasChildNodes()) return null;
+  tagName = tagName.toUpperCase();
+  if(only) only = [only].flatten();
+  var elements = [];
+  $A(element.childNodes).each( function(e) {
+    if(e.tagName && e.tagName.toUpperCase()==tagName &&
+      (!only || (Element.classNames(e).detect(function(v) { return only.include(v) }))))
+        elements.push(e);
+    if(recursive) {
+      var grandchildren = Element.findChildren(e, only, recursive, tagName);
+      if(grandchildren) elements.push(grandchildren);
+    }
+  });
+
+  return (elements.length>0 ? elements.flatten() : []);
+}
+
+Element.offsetSize = function (element, type) {
+  if (type == 'vertical' || type == 'height')
+    return element.offsetHeight;
+  else
+    return element.offsetWidth;
+}
\ No newline at end of file
diff --git a/railties/html/javascripts/effects.js b/railties/html/javascripts/effects.js
index bcf836b83c..927400502d 100644
--- a/railties/html/javascripts/effects.js
+++ b/railties/html/javascripts/effects.js
@@ -77,9 +77,12 @@ Element.getInlineOpacity = function(element){
 }  
 
 Element.childrenWithClassName = function(element, className, findFirst) {
-  return [$A($(element).getElementsByTagName('*'))[findFirst ? 'detect' : 'select']( function(c) { 
-    return c.className ? Element.hasClassName(c, className) : false;
-  })].flatten();
+  var classNameRegExp = new RegExp("(^|\\s)" + className + "(\\s|$)");
+  var results = $A($(element).getElementsByTagName('*'))[findFirst ? 'detect' : 'select']( function(c) { 
+    return (c.className && c.className.match(classNameRegExp));
+  });
+  if(!results) results = [];
+  return results;
 }
 
 Element.forceRerendering = function(element) {
@@ -91,11 +94,6 @@ Element.forceRerendering = function(element) {
   } catch(e) { }
 };
 
-['setOpacity','getOpacity','getInlineOpacity','forceRerendering','setContentZoom',
- 'collectTextNodes','collectTextNodesIgnoreClass','childrenWithClassName'].each( 
-  function(f) { Element.Methods[f] = Element[f]; } 
-);
-
 /*--------------------------------------------------------------------------*/
 
 Array.prototype.call = function() {
@@ -943,11 +941,18 @@ Effect.Fold = function(element) {
         effect.element.setStyle(oldStyle);
       } });
   }}, arguments[1] || {}));
-}
+};
+
+['setOpacity','getOpacity','getInlineOpacity','forceRerendering','setContentZoom',
+ 'collectTextNodes','collectTextNodesIgnoreClass','childrenWithClassName'].each( 
+  function(f) { Element.Methods[f] = Element[f]; }
+);
 
 Element.Methods.visualEffect = function(element, effect, options) {
   s = effect.gsub(/_/, '-').camelize();
   effect_class = s.charAt(0).toUpperCase() + s.substring(1);
   new Effect[effect_class](element, options);
   return $(element);
-};
\ No newline at end of file
+};
+
+Element.addMethods();
\ No newline at end of file
diff --git a/railties/html/javascripts/prototype.js b/railties/html/javascripts/prototype.js
index 2d4ba34c18..56817066b6 100644
--- a/railties/html/javascripts/prototype.js
+++ b/railties/html/javascripts/prototype.js
@@ -900,13 +900,14 @@ if (!window.Element)
 
 Element.extend = function(element) {
   if (!element) return;
+  if (_nativeExtensions) return element;
 
   if (!element._extended && element.tagName && element != window) {
-    var methods = Element.Methods;
+    var methods = Element.Methods, cache = Element.extend.cache;
     for (property in methods) {
       var value = methods[property];
       if (typeof value == 'function')
-        element[property] = value.bind(null, element);
+        element[property] = cache.findOrStore(value);
     }
   }
 
@@ -914,6 +915,14 @@ Element.extend = function(element) {
   return element;
 }
 
+Element.extend.cache = { 
+  findOrStore: function(value) { 
+    return this[value] = this[value] || function() { 
+      return value.apply(null, [this].concat($A(arguments))); 
+    } 
+  }
+}
+
 Element.Methods = {
   visible: function(element) {
     return $(element).style.display != 'none';
@@ -1105,6 +1114,30 @@ Element.Methods = {
 
 Object.extend(Element, Element.Methods);
 
+var _nativeExtensions = false;
+
+if(!HTMLElement && /Konqueror|Safari|KHTML/.test(navigator.userAgent)) {
+  var HTMLElement = {}
+  HTMLElement.prototype = document.createElement('div').__proto__;
+}
+
+Element.addMethods = function(methods) {
+  Object.extend(Element.Methods, methods || {});
+  
+  if(typeof HTMLElement != 'undefined') {
+    var methods = Element.Methods, cache = Element.extend.cache;
+    for (property in methods) {
+      var value = methods[property];
+      if (typeof value == 'function') {
+        HTMLElement.prototype[property] = cache.findOrStore(value);
+      }
+    }
+    _nativeExtensions = true;
+  }
+}
+
+Element.addMethods();
+
 var Toggle = new Object();
 Toggle.display = Element.toggle;