{"action":"created","issue":{"url":"https://api.github.com/repos/Matt-Esch/virtual-dom/issues/197","labels_url":"https://api.github.com/repos/Matt-Esch/virtual-dom/issues/197/labels{/name}","comments_url":"https://api.github.com/repos/Matt-Esch/virtual-dom/issues/197/comments","events_url":"https://api.github.com/repos/Matt-Esch/virtual-dom/issues/197/events","html_url":"https://github.com/Matt-Esch/virtual-dom/pull/197","id":58555081,"number":197,"title":"Rewrite reorder","user":{"login":"Matt-Esch","id":1058839,"avatar_url":"https://avatars.githubusercontent.com/u/1058839?v=3","gravatar_id":"","url":"https://api.github.com/users/Matt-Esch","html_url":"https://github.com/Matt-Esch","followers_url":"https://api.github.com/users/Matt-Esch/followers","following_url":"https://api.github.com/users/Matt-Esch/following{/other_user}","gists_url":"https://api.github.com/users/Matt-Esch/gists{/gist_id}","starred_url":"https://api.github.com/users/Matt-Esch/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Matt-Esch/subscriptions","organizations_url":"https://api.github.com/users/Matt-Esch/orgs","repos_url":"https://api.github.com/users/Matt-Esch/repos","events_url":"https://api.github.com/users/Matt-Esch/events{/privacy}","received_events_url":"https://api.github.com/users/Matt-Esch/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":17,"created_at":"2015-02-23T08:07:19Z","updated_at":"2015-03-01T04:20:07Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/Matt-Esch/virtual-dom/pulls/197","html_url":"https://github.com/Matt-Esch/virtual-dom/pull/197","diff_url":"https://github.com/Matt-Esch/virtual-dom/pull/197.diff","patch_url":"https://github.com/Matt-Esch/virtual-dom/pull/197.patch"},"body":"I have decided the reordering logic needs to be rewritten. I effectively take a bubble sort style approach to get the nodes in the correct shape. The offset counting is very error prone and difficult to debug so I've avoided that where possible.\r\n\r\nAs an extension to this, I would like to extend the capability of virtual-dom to insert at an index. Currently we use the `diff(null, newVnode)` feature to create the inserts. I would like to avoid inserting the items at the end and insert all new items at the correct index at creation time.\r\n\r\nHaving better insert semantics will remove all re-order overhead for inserts. We really need some benchmarks for this. I am interested to see how more or less efficient this becomes."},"comment":{"url":"https://api.github.com/repos/Matt-Esch/virtual-dom/issues/comments/76573571","html_url":"https://github.com/Matt-Esch/virtual-dom/pull/197#issuecomment-76573571","issue_url":"https://api.github.com/repos/Matt-Esch/virtual-dom/issues/197","id":76573571,"user":{"login":"neonstalwart","id":84763,"avatar_url":"https://avatars.githubusercontent.com/u/84763?v=3","gravatar_id":"","url":"https://api.github.com/users/neonstalwart","html_url":"https://github.com/neonstalwart","followers_url":"https://api.github.com/users/neonstalwart/followers","following_url":"https://api.github.com/users/neonstalwart/following{/other_user}","gists_url":"https://api.github.com/users/neonstalwart/gists{/gist_id}","starred_url":"https://api.github.com/users/neonstalwart/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/neonstalwart/subscriptions","organizations_url":"https://api.github.com/users/neonstalwart/orgs","repos_url":"https://api.github.com/users/neonstalwart/repos","events_url":"https://api.github.com/users/neonstalwart/events{/privacy}","received_events_url":"https://api.github.com/users/neonstalwart/received_events","type":"User","site_admin":false},"created_at":"2015-03-01T04:20:07Z","updated_at":"2015-03-01T04:20:07Z","body":"I have another thought I want to pursue when I get a chance this coming week. \r\n\r\nthe basis of it involves changing the patch to be 2 phases:\r\n\r\n1. remove all nodes to be reordered. maintain a hash of these nodes that allows us to retrieve each one by their key during the next phase. \r\n1. insert all nodes in their final position\r\n\r\nI believe the diff can then be done in O(N) with 2 passes\r\n\r\n1. iterate from right to left over the simulate array and identify the nodes that are out of position, record that they need to be removed (an array of indices) and splice them from the array. by working right to left, the effect of removing an item minimizes the impact on the indices of the unvisited part of the array. in order to determine if a node is out of position, this pass needs to maintain some counters to help calculate the effective position of a node.\r\n\r\n1. iterate from left to right over the simulate array to determine the insert index for each of the nodes. record this as a list of `{ key, index}` objects\r\n\r\nsolutions involving using counters to help determine effective positions have proven to be harder than they first seem but I'm willing to try another one in the hope we can achieve O(N)"}}