From: Michael Edgar <adgar@...>
Date: 2011-04-07T13:49:04+09:00
Subject: [ruby-core:35639] [Ruby 1.9 - Feature #4553][Open] [PATCH] Add Set#pick and Set#pop


--Apple-Mail-2--425497306
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

I put this on the 1.9 redmine, but for some reason it appears no e-mail =
went out to the mailing list, so I've re-sent this feature request.

http://redmine.ruby-lang.org/issues/4553

------------------------------

A very common operation on sets is to take an arbitrary element from =
them at O(1) cost. I know typically it's suggested that library =
additions go out as a gem to see community review. However, to me it =
seems to be a glaring omission to lack such an operation on a built-in, =
fundamental data structure, so I've gone straight to the bug tracker.

I wasn't too sure which method names to use as I've often heard "take" =
in lieu of "pop," so I just used the names Wikipedia uses. Consider them =
flexible. "pick" selects an arbitrary element, and "pop" both selects =
and deletes it.

I've provided a very simple patch that implements the necessary =
behavior. Thoughts?

Michael Edgar
adgar@carboni.ca
http://carboni.ca/



--Apple-Mail-2--425497306
Content-Type: multipart/mixed;
	boundary=Apple-Mail-3--425497306


--Apple-Mail-3--425497306
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=us-ascii

<html><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =
-webkit-line-break: after-white-space; "><div>I put this on the 1.9 =
redmine, but for some reason it appears no e-mail went out to the =
mailing list,&nbsp;so I've re-sent this feature =
request.</div><div><br></div><div><a =
href=3D"http://redmine.ruby-lang.org/issues/4553">http://redmine.ruby-lang=
.org/issues/4553</a></div><div><br></div><div>----------------------------=
--</div><div><br></div>A very common operation on sets is to take an =
arbitrary element from them at O(1) cost. I know typically it's =
suggested that library&nbsp;additions go out as a gem to see community =
review. However, to me it seems to be a glaring omission to lack such an =
operation on a built-in, fundamental data structure, so I've gone =
straight to the bug tracker.<br><br>I wasn't too sure which method names =
to use as I've often heard "take" in lieu of "pop," so I just used the =
names Wikipedia uses.&nbsp;Consider them flexible. "pick" selects an =
arbitrary element, and "pop" both selects and deletes it.<br><br>I've =
provided a very simple patch that implements the necessary behavior. =
Thoughts?<br><br><div>Michael Edgar<br><a =
href=3D"mailto:adgar@carboni.ca">adgar@carboni.ca</a><br>http://carboni.ca=
/<br></div><div><br></div><br><div></div></body></html>=

--Apple-Mail-3--425497306
Content-Disposition: attachment;
	filename=pick_pop.diff
Content-Type: application/octet-stream;
	name="pick_pop.diff"
Content-Transfer-Encoding: 7bit

Index: lib/set.rb
===================================================================
--- lib/set.rb	(revision 31238)
+++ lib/set.rb	(working copy)
@@ -223,6 +223,20 @@
     self
   end
 
+  # Picks an arbitrary element from the set and returns it. Use +pop+ to
+  # pick and delete simultaneously.
+  def pick
+    @hash.first.first
+  end
+
+  # Picks an arbitrary element from the set and deletes it. Use +pick+ to
+  # pick without deletion.
+  def pop
+    key = pick
+    @hash.delete(key)
+    key
+  end
+
   # Adds the given object to the set and returns self.  Use +merge+ to
   # add many elements at once.
   def add(o)
@@ -1027,6 +1041,24 @@
     }
   end
 
+  def test_pick
+    set = Set[5,3,1]
+    assert_equal(true, set.include?(set.pick))
+  end
+
+  def test_pop
+    total = Set[9,1,8,2,7]
+    
+    current = Set[9,1,8,2,7]
+    removed = Set[]
+    
+    until current.empty?
+      removed << current.pop
+      assert_equal(total, current | removed)
+      assert_equal(true, (current & removed).empty?)
+    end
+  end
+
   def test_add
     set = Set[1,2,3]
 

--Apple-Mail-3--425497306
Content-Transfer-Encoding: 7bit
Content-Type: text/html;
	charset=us-ascii

<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div></div></body></html>
--Apple-Mail-3--425497306--

--Apple-Mail-2--425497306--