{"action":"created","comment":{"url":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/comments/26449861","id":26449861,"diff_hunk":"@@ -0,0 +1,201 @@\n+/**\n+ * This file is part of Scalacaster project,\n+ * https://github.com/vkostyukov/scalacaster and written by Amanj Sherwany,\n+ * http://www.amanj.me\n+ *\n+ * AA tree http://en.wikipedia.org/wiki/AA_tree\n+ *\n+ * Performance: (From Wikipedia)\n+ * The performance of an AA tree is equivalent to the performance of a\n+ * red-black tree. While an AA tree makes more rotations than a red-black tree,\n+ * the simpler algorithms tend to be faster, and all of this balances out to\n+ * result in similar performance. A red-black tree is more consistent in its\n+ * performance than an AA tree, but an AA tree tends to be flatter, which\n+ * results in slightly faster search times\n+ *\n+ * Insert - O(log n)\n+ * Lookup - O(log n)  \n+ * Remove - O(log n)\n+ */\n+\n+\n+sealed abstract class AATree[+T: Ordering] {\n+  import AATree._\n+\n+  val value: T\n+  val level: Int\n+  val left: AATree[T]\n+  val right: AATree[T]\n+\n+  def member[B >: T: Ordering](a: B): Boolean = this match {\n+    case Empty                                                => false\n+    case Fork(v, _, l, r) if a == v                           => true\n+    case Fork(v, _, l, r) if implicitly[Ordering[B]].lt(a, v) => l.member(v)\n+    case Fork(v, _, l, r)                                     => r.member(v)\n+  }\n+\n+  def insert[B >: T: Ordering](a: B): AATree[B] = this match {\n+    case Empty                                                 =>\n+      Fork(a, 1, Empty, Empty)\n+    case Fork(v, lv, l, r) if implicitly[Ordering[B]].lt(a, v) => \n+      Fork(v, lv, l.insert(a), r).rebalanceTree\n+    case Fork(v, lv, l, r) if implicitly[Ordering[B]].gt(a, v) => \n+      Fork(v, lv, l, r.insert(a)).rebalanceTree\n+    case _                                                     =>\n+      this\n+  }\n+\n+  def merge[B >: T: Ordering](that: AATree[B]): AATree[B] = \n+    if(this == Empty) that\n+    else if(that == Empty) this\n+    else {\n+      left.merge(right.merge(that)).insert(value)\n+    }\n+\n+\n+  // Let's make our tree an instance of functor, and monad\n+  def map[B: Ordering](f: T => B): AATree[B] = this match {\n+    case Empty            => Empty\n+    case Fork(v, _, l, r) =>\n+      val mappedL = l.map(f)\n+      val mappedR = r.map(f)\n+      mappedL.merge(mappedR).insert(f(v))\n+  }\n+\n+  def flatMap[B: Ordering](f: T => AATree[B]): AATree[B] = this match {\n+    case Empty            => Empty\n+    case Fork(v, _, l, r) =>\n+      val mappedL = l.flatMap(f)\n+      val mappedR = r.flatMap(f)\n+      mappedL.merge(mappedR).merge(f(v))\n+  }\n+\n+  def fold[B: Ordering](f: (T, B, B) => B, z: B): B = this match {\n+    case Empty            => z\n+    case Fork(v, _, l, r) =>\n+      f(v, l.fold(f, z), r.fold(f, z))\n+  }\n+\n+  def delete[B >: T: Ordering](a: B): AATree[B] = this match {\n+    case Empty                                                 => \n+      Empty\n+    case Fork(v, lv, l, r) if implicitly[Ordering[B]].gt(a, v) => \n+      Fork(v, lv, l, r.delete(a)).rebalanceAfterDelete\n+    case Fork(v, lv, l, r) if implicitly[Ordering[B]].lt(a, v) => \n+      Fork(v, lv, l.delete(a), r).rebalanceAfterDelete\n+    case Fork(_, _, Empty, Empty)                              =>\n+      Empty\n+    case Fork(_, lv, Empty, r)                                 =>\n+      val succ = successor\n+      val r2 = r.delete(succ)\n+      Fork(succ, lv, Empty, r2).rebalanceAfterDelete\n+    case Fork(_, lv, l, r)                                     =>\n+      val pred = predecessor\n+      val l2 = l.delete(pred)\n+      Fork(pred, lv, l2, r).rebalanceAfterDelete\n+  }\n+\n+  \n+  // some helper functions\n+  protected def rebalanceTree[B >: T: Ordering]: AATree[B] = skew.split\n+\n+  protected def rebalanceAfterDelete[B >: T: Ordering]: AATree[B] = {\n+    val t1 = decreaseLevel.skew\n+    val t2 = t1.right.skew\n+    val t3 = t2 match {\n+      case Fork(v1, lv1, l1, Fork(v2, lv2, l2, r2)) =>\n+        Fork(v1, lv1, l1, Fork(v2, lv2, l2, r2.skew))\n+      case _                                        =>\n+        t2\n+    }\n+    val t4 = t3.split\n+    t4 match {\n+      case Fork(v, lv, l, r) => Fork(v, lv, l, r.split)\n+      case _                 => t4\n+    }\n+  }\n+\n+  protected def successor[B >: T: Ordering]: B = {\n+    def successor2(t: AATree[B]): B = this match {","path":"src/tree/AATree.scala","position":119,"original_position":119,"commit_id":"7b239c2853afc3f35c3e6ed1cf938ddae28cd785","original_commit_id":"7b239c2853afc3f35c3e6ed1cf938ddae28cd785","user":{"login":"amanjpro","id":3101099,"avatar_url":"https://avatars.githubusercontent.com/u/3101099?v=3","gravatar_id":"","url":"https://api.github.com/users/amanjpro","html_url":"https://github.com/amanjpro","followers_url":"https://api.github.com/users/amanjpro/followers","following_url":"https://api.github.com/users/amanjpro/following{/other_user}","gists_url":"https://api.github.com/users/amanjpro/gists{/gist_id}","starred_url":"https://api.github.com/users/amanjpro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amanjpro/subscriptions","organizations_url":"https://api.github.com/users/amanjpro/orgs","repos_url":"https://api.github.com/users/amanjpro/repos","events_url":"https://api.github.com/users/amanjpro/events{/privacy}","received_events_url":"https://api.github.com/users/amanjpro/received_events","type":"User","site_admin":false},"body":"Do you mean the inner function?","created_at":"2015-03-15T17:34:53Z","updated_at":"2015-03-15T17:34:53Z","html_url":"https://github.com/vkostyukov/scalacaster/pull/14#discussion_r26449861","pull_request_url":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14","_links":{"self":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/comments/26449861"},"html":{"href":"https://github.com/vkostyukov/scalacaster/pull/14#discussion_r26449861"},"pull_request":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14"}}},"pull_request":{"url":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14","id":31189422,"html_url":"https://github.com/vkostyukov/scalacaster/pull/14","diff_url":"https://github.com/vkostyukov/scalacaster/pull/14.diff","patch_url":"https://github.com/vkostyukov/scalacaster/pull/14.patch","issue_url":"https://api.github.com/repos/vkostyukov/scalacaster/issues/14","number":14,"state":"open","locked":false,"title":"Add an implementation of AATree ","user":{"login":"amanjpro","id":3101099,"avatar_url":"https://avatars.githubusercontent.com/u/3101099?v=3","gravatar_id":"","url":"https://api.github.com/users/amanjpro","html_url":"https://github.com/amanjpro","followers_url":"https://api.github.com/users/amanjpro/followers","following_url":"https://api.github.com/users/amanjpro/following{/other_user}","gists_url":"https://api.github.com/users/amanjpro/gists{/gist_id}","starred_url":"https://api.github.com/users/amanjpro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amanjpro/subscriptions","organizations_url":"https://api.github.com/users/amanjpro/orgs","repos_url":"https://api.github.com/users/amanjpro/repos","events_url":"https://api.github.com/users/amanjpro/events{/privacy}","received_events_url":"https://api.github.com/users/amanjpro/received_events","type":"User","site_admin":false},"body":"I have added AATree implementation, it is basically a direct translation from the imperative algorithm shown in Wikipedia.  I've also added some useful functions like toList, inssertAll, map, filter, fold, foreach and merge.\r\n\r\nMy implementation goes for clarity not efficiency.","created_at":"2015-03-14T20:18:18Z","updated_at":"2015-03-15T17:34:53Z","closed_at":null,"merged_at":null,"merge_commit_sha":"c4b6722e56f5002416dcdcedd9a80d03b1aaa212","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14/commits","review_comments_url":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14/comments","review_comment_url":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/comments{/number}","comments_url":"https://api.github.com/repos/vkostyukov/scalacaster/issues/14/comments","statuses_url":"https://api.github.com/repos/vkostyukov/scalacaster/statuses/7b239c2853afc3f35c3e6ed1cf938ddae28cd785","head":{"label":"amanjpro:master","ref":"master","sha":"7b239c2853afc3f35c3e6ed1cf938ddae28cd785","user":{"login":"amanjpro","id":3101099,"avatar_url":"https://avatars.githubusercontent.com/u/3101099?v=3","gravatar_id":"","url":"https://api.github.com/users/amanjpro","html_url":"https://github.com/amanjpro","followers_url":"https://api.github.com/users/amanjpro/followers","following_url":"https://api.github.com/users/amanjpro/following{/other_user}","gists_url":"https://api.github.com/users/amanjpro/gists{/gist_id}","starred_url":"https://api.github.com/users/amanjpro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amanjpro/subscriptions","organizations_url":"https://api.github.com/users/amanjpro/orgs","repos_url":"https://api.github.com/users/amanjpro/repos","events_url":"https://api.github.com/users/amanjpro/events{/privacy}","received_events_url":"https://api.github.com/users/amanjpro/received_events","type":"User","site_admin":false},"repo":{"id":32229320,"name":"scalacaster","full_name":"amanjpro/scalacaster","owner":{"login":"amanjpro","id":3101099,"avatar_url":"https://avatars.githubusercontent.com/u/3101099?v=3","gravatar_id":"","url":"https://api.github.com/users/amanjpro","html_url":"https://github.com/amanjpro","followers_url":"https://api.github.com/users/amanjpro/followers","following_url":"https://api.github.com/users/amanjpro/following{/other_user}","gists_url":"https://api.github.com/users/amanjpro/gists{/gist_id}","starred_url":"https://api.github.com/users/amanjpro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amanjpro/subscriptions","organizations_url":"https://api.github.com/users/amanjpro/orgs","repos_url":"https://api.github.com/users/amanjpro/repos","events_url":"https://api.github.com/users/amanjpro/events{/privacy}","received_events_url":"https://api.github.com/users/amanjpro/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/amanjpro/scalacaster","description":"Purely Functional Algorithms and Data Structures in Scala","fork":true,"url":"https://api.github.com/repos/amanjpro/scalacaster","forks_url":"https://api.github.com/repos/amanjpro/scalacaster/forks","keys_url":"https://api.github.com/repos/amanjpro/scalacaster/keys{/key_id}","collaborators_url":"https://api.github.com/repos/amanjpro/scalacaster/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/amanjpro/scalacaster/teams","hooks_url":"https://api.github.com/repos/amanjpro/scalacaster/hooks","issue_events_url":"https://api.github.com/repos/amanjpro/scalacaster/issues/events{/number}","events_url":"https://api.github.com/repos/amanjpro/scalacaster/events","assignees_url":"https://api.github.com/repos/amanjpro/scalacaster/assignees{/user}","branches_url":"https://api.github.com/repos/amanjpro/scalacaster/branches{/branch}","tags_url":"https://api.github.com/repos/amanjpro/scalacaster/tags","blobs_url":"https://api.github.com/repos/amanjpro/scalacaster/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/amanjpro/scalacaster/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/amanjpro/scalacaster/git/refs{/sha}","trees_url":"https://api.github.com/repos/amanjpro/scalacaster/git/trees{/sha}","statuses_url":"https://api.github.com/repos/amanjpro/scalacaster/statuses/{sha}","languages_url":"https://api.github.com/repos/amanjpro/scalacaster/languages","stargazers_url":"https://api.github.com/repos/amanjpro/scalacaster/stargazers","contributors_url":"https://api.github.com/repos/amanjpro/scalacaster/contributors","subscribers_url":"https://api.github.com/repos/amanjpro/scalacaster/subscribers","subscription_url":"https://api.github.com/repos/amanjpro/scalacaster/subscription","commits_url":"https://api.github.com/repos/amanjpro/scalacaster/commits{/sha}","git_commits_url":"https://api.github.com/repos/amanjpro/scalacaster/git/commits{/sha}","comments_url":"https://api.github.com/repos/amanjpro/scalacaster/comments{/number}","issue_comment_url":"https://api.github.com/repos/amanjpro/scalacaster/issues/comments{/number}","contents_url":"https://api.github.com/repos/amanjpro/scalacaster/contents/{+path}","compare_url":"https://api.github.com/repos/amanjpro/scalacaster/compare/{base}...{head}","merges_url":"https://api.github.com/repos/amanjpro/scalacaster/merges","archive_url":"https://api.github.com/repos/amanjpro/scalacaster/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/amanjpro/scalacaster/downloads","issues_url":"https://api.github.com/repos/amanjpro/scalacaster/issues{/number}","pulls_url":"https://api.github.com/repos/amanjpro/scalacaster/pulls{/number}","milestones_url":"https://api.github.com/repos/amanjpro/scalacaster/milestones{/number}","notifications_url":"https://api.github.com/repos/amanjpro/scalacaster/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/amanjpro/scalacaster/labels{/name}","releases_url":"https://api.github.com/repos/amanjpro/scalacaster/releases{/id}","created_at":"2015-03-14T19:55:10Z","updated_at":"2015-03-15T10:46:21Z","pushed_at":"2015-03-15T10:46:20Z","git_url":"git://github.com/amanjpro/scalacaster.git","ssh_url":"git@github.com:amanjpro/scalacaster.git","clone_url":"https://github.com/amanjpro/scalacaster.git","svn_url":"https://github.com/amanjpro/scalacaster","homepage":"http://www.slideshare.net/vkostyukov/purely-functional-data-structures-in-scala-26175521","size":294,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"vkostyukov:master","ref":"master","sha":"54629190d2fd98799bb56da778c71ebb3ee0d456","user":{"login":"vkostyukov","id":1098539,"avatar_url":"https://avatars.githubusercontent.com/u/1098539?v=3","gravatar_id":"","url":"https://api.github.com/users/vkostyukov","html_url":"https://github.com/vkostyukov","followers_url":"https://api.github.com/users/vkostyukov/followers","following_url":"https://api.github.com/users/vkostyukov/following{/other_user}","gists_url":"https://api.github.com/users/vkostyukov/gists{/gist_id}","starred_url":"https://api.github.com/users/vkostyukov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vkostyukov/subscriptions","organizations_url":"https://api.github.com/users/vkostyukov/orgs","repos_url":"https://api.github.com/users/vkostyukov/repos","events_url":"https://api.github.com/users/vkostyukov/events{/privacy}","received_events_url":"https://api.github.com/users/vkostyukov/received_events","type":"User","site_admin":false},"repo":{"id":7326767,"name":"scalacaster","full_name":"vkostyukov/scalacaster","owner":{"login":"vkostyukov","id":1098539,"avatar_url":"https://avatars.githubusercontent.com/u/1098539?v=3","gravatar_id":"","url":"https://api.github.com/users/vkostyukov","html_url":"https://github.com/vkostyukov","followers_url":"https://api.github.com/users/vkostyukov/followers","following_url":"https://api.github.com/users/vkostyukov/following{/other_user}","gists_url":"https://api.github.com/users/vkostyukov/gists{/gist_id}","starred_url":"https://api.github.com/users/vkostyukov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vkostyukov/subscriptions","organizations_url":"https://api.github.com/users/vkostyukov/orgs","repos_url":"https://api.github.com/users/vkostyukov/repos","events_url":"https://api.github.com/users/vkostyukov/events{/privacy}","received_events_url":"https://api.github.com/users/vkostyukov/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/vkostyukov/scalacaster","description":"Purely Functional Algorithms and Data Structures in Scala","fork":false,"url":"https://api.github.com/repos/vkostyukov/scalacaster","forks_url":"https://api.github.com/repos/vkostyukov/scalacaster/forks","keys_url":"https://api.github.com/repos/vkostyukov/scalacaster/keys{/key_id}","collaborators_url":"https://api.github.com/repos/vkostyukov/scalacaster/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/vkostyukov/scalacaster/teams","hooks_url":"https://api.github.com/repos/vkostyukov/scalacaster/hooks","issue_events_url":"https://api.github.com/repos/vkostyukov/scalacaster/issues/events{/number}","events_url":"https://api.github.com/repos/vkostyukov/scalacaster/events","assignees_url":"https://api.github.com/repos/vkostyukov/scalacaster/assignees{/user}","branches_url":"https://api.github.com/repos/vkostyukov/scalacaster/branches{/branch}","tags_url":"https://api.github.com/repos/vkostyukov/scalacaster/tags","blobs_url":"https://api.github.com/repos/vkostyukov/scalacaster/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/vkostyukov/scalacaster/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/vkostyukov/scalacaster/git/refs{/sha}","trees_url":"https://api.github.com/repos/vkostyukov/scalacaster/git/trees{/sha}","statuses_url":"https://api.github.com/repos/vkostyukov/scalacaster/statuses/{sha}","languages_url":"https://api.github.com/repos/vkostyukov/scalacaster/languages","stargazers_url":"https://api.github.com/repos/vkostyukov/scalacaster/stargazers","contributors_url":"https://api.github.com/repos/vkostyukov/scalacaster/contributors","subscribers_url":"https://api.github.com/repos/vkostyukov/scalacaster/subscribers","subscription_url":"https://api.github.com/repos/vkostyukov/scalacaster/subscription","commits_url":"https://api.github.com/repos/vkostyukov/scalacaster/commits{/sha}","git_commits_url":"https://api.github.com/repos/vkostyukov/scalacaster/git/commits{/sha}","comments_url":"https://api.github.com/repos/vkostyukov/scalacaster/comments{/number}","issue_comment_url":"https://api.github.com/repos/vkostyukov/scalacaster/issues/comments{/number}","contents_url":"https://api.github.com/repos/vkostyukov/scalacaster/contents/{+path}","compare_url":"https://api.github.com/repos/vkostyukov/scalacaster/compare/{base}...{head}","merges_url":"https://api.github.com/repos/vkostyukov/scalacaster/merges","archive_url":"https://api.github.com/repos/vkostyukov/scalacaster/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/vkostyukov/scalacaster/downloads","issues_url":"https://api.github.com/repos/vkostyukov/scalacaster/issues{/number}","pulls_url":"https://api.github.com/repos/vkostyukov/scalacaster/pulls{/number}","milestones_url":"https://api.github.com/repos/vkostyukov/scalacaster/milestones{/number}","notifications_url":"https://api.github.com/repos/vkostyukov/scalacaster/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/vkostyukov/scalacaster/labels{/name}","releases_url":"https://api.github.com/repos/vkostyukov/scalacaster/releases{/id}","created_at":"2012-12-26T12:05:30Z","updated_at":"2015-03-15T16:15:04Z","pushed_at":"2015-03-13T20:24:38Z","git_url":"git://github.com/vkostyukov/scalacaster.git","ssh_url":"git@github.com:vkostyukov/scalacaster.git","clone_url":"https://github.com/vkostyukov/scalacaster.git","svn_url":"https://github.com/vkostyukov/scalacaster","homepage":"http://www.slideshare.net/vkostyukov/purely-functional-data-structures-in-scala-26175521","size":1150,"stargazers_count":334,"watchers_count":334,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":65,"mirror_url":null,"open_issues_count":2,"forks":65,"open_issues":2,"watchers":334,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14"},"html":{"href":"https://github.com/vkostyukov/scalacaster/pull/14"},"issue":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/issues/14"},"comments":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/issues/14/comments"},"review_comments":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14/comments"},"review_comment":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/pulls/14/commits"},"statuses":{"href":"https://api.github.com/repos/vkostyukov/scalacaster/statuses/7b239c2853afc3f35c3e6ed1cf938ddae28cd785"}}}}