Packages

sorted_set

0.2.0
1.1.0 1.0.0 0.2.0 0.1.1 0.1.0

SortedSet implementation for Elixir

HexDocs

Current section

5 Versions

Jump to
Readme
5 Versions
0 Dependencies
Dependants
Files
Activity
Hide whitespace

Compare versions

5 files changed
+638 additions
-73 deletions
  @@ -1,12 +1,14 @@
1 1 {<<"app">>,<<"sorted_set">>}.
2 + {<<"build_tools">>,[<<"mix">>]}.
2 3 {<<"contributors">>,[<<"Seneca Systems">>]}.
3 4 {<<"description">>,<<"SortedSet implementation for Elixir">>}.
4 5 {<<"elixir">>,<<"~> 1.0">>}.
5 6 {<<"files">>,
6 - [<<"lib/sorted_set.ex">>,<<"mix.exs">>,<<"README.md">>,<<"LICENSE">>]}.
7 + [<<"lib/red_black_tree.ex">>,<<"lib/red_black_tree/node.ex">>,
8 + <<"lib/sorted_set.ex">>,<<"mix.exs">>,<<"README.md">>,<<"LICENSE">>]}.
7 9 {<<"licenses">>,[<<"MIT">>]}.
8 10 {<<"links">>,
9 11 [{<<"GitHub">>,<<"https://github.com/SenecaSystems/sorted_set">>}]}.
10 12 {<<"name">>,<<"sorted_set">>}.
11 13 {<<"requirements">>,[]}.
12 - {<<"version">>,<<"0.1.1">>}.
14 + {<<"version">>,<<"0.2.0">>}.
  @@ -0,0 +1,606 @@
1 + defmodule RedBlackTree do
2 + @moduledoc """
3 + Red-black trees are key-value stores.
4 + While not guaranteed to be perfectly balanced, they guarantee O(log(n)) search
5 + time.
6 +
7 + The RedBlackTree module contains an eponymous struct and various useful
8 + functions.
9 +
10 + Nodes know their depth (automatically updated on insert/delete)
11 + """
12 + alias RedBlackTree.Node
13 +
14 + defstruct root: nil, size: 0
15 +
16 + @key_hash_bucket 4294967296
17 +
18 + # Inline key hashing
19 + @compile {:inline, key_less_than?: 2, hash_key: 1, fallback_key_hash: 1}
20 +
21 + def new() do
22 + %RedBlackTree{}
23 + end
24 +
25 + def new(values) when is_list(values) do
26 + new(%RedBlackTree{}, values)
27 + end
28 +
29 + defp new(tree, []) do
30 + tree
31 + end
32 +
33 + # Allow initialization with key/value tuples
34 + defp new(tree, [{key, value}|tail]) do
35 + new(RedBlackTree.insert(tree, key, value), tail)
36 + end
37 +
38 + # Allow initialization with individual values, in which case they will be both
39 + # the key and the value
40 + defp new(tree, [key|tail]) do
41 + new(RedBlackTree.insert(tree, key, key), tail)
42 + end
43 +
44 + def size(%RedBlackTree{size: size}) do
45 + size
46 + end
47 +
48 + def put(tree, key, value) do
49 + insert(tree, key, value)
50 + end
51 +
52 + def insert(%RedBlackTree{root: nil}, key, value) do
53 + %RedBlackTree{root: Node.new(key, value), size: 1}
54 + end
55 +
56 + def insert(%RedBlackTree{root: root, size: size}=tree, key, value) do
57 + {nodes_added, new_root} = do_insert(root, key, value, 1)
58 + %RedBlackTree{
59 + tree |
60 + root: make_node_black(new_root),
61 + size: size + nodes_added
62 + }
63 + end
64 +
65 + def delete(%RedBlackTree{root: root, size: size}=tree, key) do
66 + {nodes_removed, new_root} = do_delete(root, key)
67 + %RedBlackTree{
68 + tree |
69 + root: new_root,
70 + size: size - nodes_removed
71 + }
72 + end
73 +
74 + def fetch(tree, key) do
75 + search(tree, key)
76 + end
77 +
78 + def search(%RedBlackTree{root: root}, key) do
79 + do_search(root, key)
80 + end
81 +
82 + defp do_search(nil, _key) do
83 + nil
84 + end
85 +
86 + defp do_search(%Node{key: node_key, value: value}, search_key) when node_key === search_key do
87 + value
88 + end
89 +
90 + defp do_search(%Node{key: node_key, left: left}, search_key) when search_key < node_key do
91 + do_search(left, search_key)
92 + end
93 +
94 + defp do_search(%Node{key: node_key, right: right}, search_key) when search_key > node_key do
95 + do_search(right, search_key)
96 + end
97 +
98 + # For cases when `insert_key !== node_key` but `insert_key == node_key` (e.g.
99 + # `1` and `1.0`,) hash the keys to provide consistent ordering.
100 + defp do_search(%Node{key: node_key, left: left, right: right}, search_key) when search_key == node_key do
101 + if key_less_than?(search_key, node_key) do
102 + do_search(left, search_key)
103 + else
104 + do_search(right, search_key)
105 + end
106 + end
107 +
108 + def has_key?(%RedBlackTree{root: root}, key) do
109 + do_has_key?(root, key)
110 + end
111 +
112 + defp do_has_key?(nil, _key) do
113 + false
114 + end
115 +
116 + defp do_has_key?(%Node{key: node_key}, search_key) when node_key === search_key do
117 + true
118 + end
119 +
120 + defp do_has_key?(%Node{key: node_key, left: left}, search_key) when search_key < node_key do
121 + do_has_key?(left, search_key)
122 + end
123 +
124 + defp do_has_key?(%Node{key: node_key, right: right}, search_key) when search_key > node_key do
125 + do_has_key?(right, search_key)
126 + end
127 +
128 + # For cases when `insert_key !== node_key` but `insert_key == node_key` (e.g.
129 + # `1` and `1.0`,) hash the keys to provide consistent ordering.
130 + defp do_has_key?(%Node{key: node_key, left: left, right: right}, search_key) when search_key == node_key do
131 + if key_less_than?(search_key, node_key) do
132 + do_has_key?(left, search_key)
133 + else
134 + do_has_key?(right, search_key)
135 + end
136 + end
137 +
138 +
139 + def balance(%RedBlackTree{root: root}=tree) do
140 + %RedBlackTree{tree | root: do_balance(root)}
141 + end
142 +
143 + def to_list(%RedBlackTree{}=tree) do
144 + reduce(tree, [], fn (node, members) ->
145 + [{node.key, node.value} | members]
146 + end) |> Enum.reverse
147 + end
148 +
149 + @doc """
150 + For each node, calls the provided function passing in (node, acc)
151 + Optionally takes an order as the first argument which can be one of
152 + `:in_order`, `:pre_order`, or `:post_order`.
153 +
154 + Defaults to `:in_order` if no order is given.
155 + """
156 + def reduce(tree, acc, fun) do
157 + reduce(:in_order, tree, acc, fun)
158 + end
159 +
160 + def reduce(_order, %RedBlackTree{root: nil}, acc, _fun) do
161 + acc
162 + end
163 +
164 + def reduce(order, %RedBlackTree{root: root}, acc, fun) do
165 + do_reduce(order, root, acc, fun)
166 + end
167 +
168 + ## Helpers
169 +
170 + defp make_node_black(%Node{}=node) do
171 + %Node{node | color: :black}
172 + end
173 +
174 + # ¡This is only used as a tiebreaker!
175 + # For cases when `insert_key !== node_key` but `insert_key == node_key` (e.g.
176 + # `1` and `1.0`,) hash the keys to provide consistent ordering.
177 + defp hash_key(key) do
178 + :erlang.phash2(key, @key_hash_bucket)
179 + end
180 +
181 + # In the case that `hash_key(key1) == hash_key(key2)` we can fall back again
182 + # to the slower phash function distributed over @key_hash_bucket integers.
183 + # If these two collide, go home.
184 + defp fallback_key_hash(key) do
185 + :erlang.phash(key, @key_hash_bucket)
186 + end
187 +
188 + # Should only be used when `key1 !== key2 and key1 == key2`. In the case
189 + defp key_less_than?(key1, key2) do
190 + hashed_key1 = hash_key(key1)
191 + hashed_key2 = hash_key(key2)
192 + cond do
193 + hashed_key1 === hashed_key2 ->
194 + fallback_key_hash(key1) < fallback_key_hash(key2)
195 + hashed_key1 < hashed_key2 -> true
196 + true -> false
197 + end
198 + end
199 +
200 + ### Operations
201 +
202 + #### Insert
203 +
204 + defp do_insert(nil, insert_key, insert_value, depth) do
205 + {
206 + 1,
207 + %Node{
208 + Node.new(insert_key, insert_value, depth) |
209 + color: :red
210 + }
211 + }
212 +
213 + end
214 +
215 + defp do_insert(%Node{key: node_key}=node, insert_key, insert_value, _depth) when node_key === insert_key do
216 + {0, %Node{node | value: insert_value}}
217 + end
218 +
219 + defp do_insert(%Node{key: node_key}=node, insert_key, insert_value, depth) when insert_key < node_key do
220 + do_insert_left(node, insert_key, insert_value, depth)
221 + end
222 +
223 + defp do_insert(%Node{key: node_key}=node, insert_key, insert_value, depth) when insert_key > node_key do
224 + do_insert_right(node, insert_key, insert_value, depth)
225 + end
226 +
227 + # For cases when `insert_key !== node_key` but `insert_key == node_key` (e.g.
228 + # `1` and `1.0`,) hash the keys to provide consistent ordering.
229 + defp do_insert(%Node{key: node_key}=node, insert_key, insert_value, depth) when insert_key == node_key do
230 + if key_less_than?(insert_key, node_key) do
231 + do_insert_left(node, insert_key, insert_value, depth)
232 + else
233 + do_insert_right(node, insert_key, insert_value, depth)
234 + end
235 + end
236 +
237 + defp do_insert_left(%Node{left: left}=node, insert_key, insert_value, depth) do
238 + {nodes_added, new_left} = do_insert(left, insert_key, insert_value, depth + 1)
239 + {nodes_added, %Node{node | left: do_balance(new_left)}}
240 + end
241 +
242 + defp do_insert_right(%Node{right: right}=node, insert_key, insert_value, depth) do
243 + {nodes_added, new_right} = do_insert(right, insert_key, insert_value, depth + 1)
244 + {nodes_added, %Node{node | right: do_balance(new_right)}}
245 + end
246 +
247 + #### Delete
248 +
249 + # If we reach a leaf and the key never matched, do nothing
250 + defp do_delete(nil, _key) do
251 + {0, nil}
252 + end
253 +
254 + # If both the right and left are nil, the new tree is nil. For example,
255 + # deleting A in the following tree results in B having no left
256 + #
257 + # B
258 + # / \
259 + # A C
260 + #
261 + defp do_delete(%Node{key: node_key, left: nil, right: nil}, delete_key) when node_key === delete_key do
262 + {1, nil}
263 + end
264 +
265 + # If left is nil and there is a right, promote the right. For example,
266 + # deleting C in the following tree results in B's right becoming D
267 + #
268 + # B
269 + # / \
270 + # A C
271 + # \
272 + # D
273 + #
274 + defp do_delete(%Node{key: node_key, left: nil, right: right}, delete_key) when node_key === delete_key do
275 + {1, %Node{right | depth: right.depth - 1}}
276 + end
277 +
278 + # If there is a left promote it. For example,
279 + # deleting B in the following tree results in C's left becoming A
280 + #
281 + # C
282 + # / \
283 + # B D
284 + # /
285 + # A
286 + #
287 + defp do_delete(%Node{key: node_key, left: left, right: nil}, delete_key) when node_key === delete_key do
288 + {1, %Node{left | depth: left.depth - 1}}
289 + end
290 +
291 + # If there are both left and right nodes, recursively promote the left-most
292 + # nodes. For example, deleting E below results in the following:
293 + #
294 + # G => G
295 + # / \ / \
296 + # E H => C H
297 + # / \ / \
298 + # C F => B D
299 + # / \ / \
300 + # A D => A F
301 + # \
302 + # B
303 + #
304 + #
305 + defp do_delete(%Node{key: node_key, left: left, right: right}, delete_key) when node_key === delete_key do
306 + {
307 + 1,
308 + do_balance(%Node{
309 + left |
310 + depth: left.depth - 1,
311 + left: do_balance(promote(left)),
312 + right: right
313 + })
314 + }
315 + end
316 +
317 + defp do_delete(%Node{key: node_key}=node, delete_key) when delete_key < node_key do
318 + do_delete_left(node, delete_key)
319 + end
320 +
321 + defp do_delete(%Node{key: node_key}=node, delete_key) when delete_key > node_key do
322 + do_delete_right(node, delete_key)
323 + end
324 +
325 + # For cases when `delete_key !== node_key` but `delete_key == node_key` (e.g.
326 + # `1` and `1.0`,) hash the keys to provide consistent ordering.
327 + defp do_delete(%Node{key: node_key}=node, delete_key) when delete_key == node_key do
328 + if key_less_than?(delete_key, node_key) do
329 + do_delete_left(node, delete_key)
330 + else
331 + do_delete_right(node, delete_key)
332 + end
333 + end
334 +
335 + defp do_delete_left(%Node{left: left}=node, delete_key) do
336 + {nodes_removed, new_left} = do_delete(left, delete_key)
337 + {
338 + nodes_removed,
339 + %Node{
340 + node |
341 + left: do_balance(new_left)
342 + }
343 + }
344 + end
345 +
346 + defp do_delete_right(%Node{right: right}=node, delete_key) do
347 + {nodes_removed, new_right} = do_delete(right, delete_key)
348 + {
349 + nodes_removed,
350 + %Node{
351 + node |
352 + right: do_balance(new_right)
353 + }
354 + }
355 + end
356 +
357 + defp promote(nil) do
358 + nil
359 + end
360 +
361 + defp promote(%Node{left: nil, right: nil, depth: depth}=node) do
362 + %Node{ node | color: :red, depth: depth - 1 }
363 + end
364 +
365 + defp promote(%Node{left: left, right: nil, depth: depth}) do
366 + %Node{ left | color: :red, depth: depth - 1}
367 + end
368 +
369 + defp promote(%Node{left: nil, right: right, depth: depth}) do
370 + %Node{ right | color: :red, depth: depth - 1}
371 + end
372 +
373 + defp promote(%Node{left: left, right: right, depth: depth}) do
374 + balance(%Node{
375 + left |
376 + depth: depth - 1,
377 + left: do_balance(promote(left)),
378 + right: right
379 + })
380 + end
381 +
382 + #### Balance
383 +
384 + # If we have a tree that looks like this:
385 + # B (Black)
386 + # / \
387 + # A D (Red)
388 + # / \
389 + # C F (Red)
390 + # / \
391 + # E G
392 + #
393 + #
394 + # Rotate to balance and look like this:
395 + #
396 + # D (Red)
397 + # / \
398 + # B (Black) F (Black)
399 + # / \ / \
400 + # A C E G
401 + #
402 + #
403 + defp do_balance(
404 + %Node{
405 + color: :black,
406 + left: a_node,
407 + right: %Node{
408 + color: :red,
409 + left: c_node,
410 + right: %Node{
411 + color: :red,
412 + left: e_node,
413 + right: g_node
414 + }=f_node
415 + }=d_node
416 + }=b_node) do
417 +
418 + balanced_tree(a_node, b_node, c_node, d_node, e_node, f_node, g_node)
419 + end
420 +
421 + # If we have a tree that looks like this:
422 + #
423 + # B (Black)
424 + # / \
425 + # A F (Red)
426 + # / \
427 + # D (Red) G
428 + # / \
429 + # C E
430 + #
431 + # Rotate to balance like so:
432 + #
433 + # D (Red)
434 + # / \
435 + # B (Black) F (Black)
436 + # / \ / \
437 + # A C E G
438 + #
439 + #
440 + #
441 + defp do_balance(
442 + %Node{
443 + color: :black,
444 + left: a_node,
445 + right: %Node{
446 + color: :red,
447 + left: %Node{
448 + color: :red,
449 + left: c_node,
450 + right: e_node
451 + }=d_node,
452 + right: g_node
453 + }=f_node
454 + }=b_node) do
455 +
456 + balanced_tree(a_node, b_node, c_node, d_node, e_node, f_node, g_node)
457 + end
458 +
459 + # If we have a tree that looks like this:
460 + #
461 + #
462 + # F (Black)
463 + # / \
464 + # D (Red) G
465 + # / \
466 + # B (Red) E
467 + # / \
468 + # A C
469 + #
470 + #
471 + # Rebalance to look like so:
472 + #
473 + # D (Red)
474 + # / \
475 + # B (Black) F (Black)
476 + # / \ / \
477 + # A C E G
478 + #
479 + defp do_balance(%Node{
480 + color: :black,
481 + left: %Node{
482 + color: :red,
483 + left: %Node{
484 + color: :red,
485 + left: a_node,
486 + right: c_node
487 + }=b_node,
488 + right: e_node
489 + }=d_node,
490 + right: g_node
491 + }=f_node) do
492 +
493 + balanced_tree(a_node, b_node, c_node, d_node, e_node, f_node, g_node)
494 + end
495 +
496 + # If we have a tree that looks like this:
497 + #
498 + # F (Black)
499 + # / \
500 + # B (Red) G
501 + # / \
502 + # A D (Red)
503 + # / \
504 + # C E
505 + #
506 + # Rebalance to look like this:
507 + #
508 + # D (Red)
509 + # / \
510 + # B (Black) F (Black)
511 + # / \ / \
512 + # A C E G
513 + #
514 + defp do_balance(%Node{
515 + color: :black,
516 + left: %Node{
517 + color: :red,
518 + left: a_node,
519 + right: %Node{
520 + color: :red,
521 + left: c_node,
522 + right: e_node
523 + }=d_node
524 + }=b_node,
525 + right: g_node
526 + }=f_node) do
527 +
528 + balanced_tree(a_node, b_node, c_node, d_node, e_node, f_node, g_node)
529 + end
530 +
531 +
532 + defp do_balance(node) do
533 + node
534 + end
535 +
536 + defp balanced_tree(a_node, b_node, c_node, d_node, e_node, f_node, g_node) do
537 + min_depth = min_depth([a_node, b_node, c_node, d_node, e_node, f_node, g_node])
538 + %Node {
539 + d_node |
540 + color: :red,
541 + depth: min_depth,
542 + left: %Node{b_node | color: :black, depth: min_depth + 1,
543 + left: %Node{a_node | depth: min_depth + 2},
544 + right: %Node{c_node | depth: min_depth + 2}},
545 + right: %Node{f_node | color: :black, depth: min_depth + 1,
546 + left: %Node{e_node | depth: min_depth + 2},
547 + right: %Node{g_node | depth: min_depth + 2},}
548 + }
549 + end
550 +
551 + defp min_depth(list_of_nodes) do
552 + Enum.reduce(list_of_nodes, -1, fn (node, acc) ->
553 + if acc == -1 || node.depth < acc do
554 + node.depth
555 + else
556 + acc
557 + end
558 + end)
559 + end
560 +
561 + defp do_reduce(_order, nil, acc, _fun) do
562 + acc
563 + end
564 +
565 + # self, left, right
566 + defp do_reduce(:pre_order, %Node{left: left, right: right}=node, acc, fun) do
567 + acc_after_self = fun.(node, acc)
568 + acc_after_left = do_reduce(:pre_order, left, acc_after_self, fun)
569 + do_reduce(:pre_order, right, acc_after_left, fun)
570 + end
571 +
572 + # left, self, right
573 + defp do_reduce(:in_order, %Node{left: left, right: right}=node, acc, fun) do
574 + acc_after_left = do_reduce(:in_order, left, acc, fun)
575 + acc_after_self = fun.(node, acc_after_left)
576 + do_reduce(:in_order, right, acc_after_self, fun)
577 + end
578 +
579 + # left, right, self
580 + defp do_reduce(:post_order, %Node{left: left, right: right}=node, acc, fun) do
581 + acc_after_left = do_reduce(:post_order, left, acc, fun)
582 + acc_after_right = do_reduce(:post_order, right, acc_after_left, fun)
583 + fun.(node, acc_after_right)
584 + end
585 + end
586 +
587 + defimpl Access, for: RedBlackTree do
588 + def get(tree, key) do
589 + RedBlackTree.search(tree, key)
590 + end
591 +
592 + def get_and_update(tree, key, fun) do
593 + {get, update} = fun.(RedBlackTree.search(tree, key))
594 + {get, RedBlackTree.insert(tree, key, update)}
595 + end
596 + end
597 +
598 + defimpl Collectable, for: RedBlackTree do
599 + def into(original) do
600 + {original, fn
601 + tree, {:cont, {key, value}} -> RedBlackTree.insert(tree, key, value)
602 + tree, :done -> tree
603 + _, :halt -> :ok
604 + end}
605 + end
606 + end
  @@ -0,0 +1,14 @@
1 + defmodule RedBlackTree.Node do
2 + defstruct(
3 + color: :black,
4 + depth: 1,
5 + key: nil,
6 + value: nil,
7 + left: nil,
8 + right: nil
9 + )
10 +
11 + def new(key, value, depth \\ 1) do
12 + %__MODULE__{key: key, value: value, depth: depth}
13 + end
14 + end
  @@ -1,4 +1,5 @@
1 1 defmodule SortedSet do
2 + alias RedBlackTree
2 3 @moduledoc """
3 4 A Set implementation that always remains sorted.
4 5
  @@ -10,9 +11,9 @@ defmodule SortedSet do
10 11
11 12 # Define the type as opaque
12 13
13 - @opaque t :: %__MODULE__{members: list, size: non_neg_integer}
14 + @opaque t :: %__MODULE__{members: RedBlackTree, size: non_neg_integer}
14 15 @doc false
15 - defstruct size: 0, members: []
16 + defstruct members: RedBlackTree.new, size: 0
16 17
17 18 @doc ~S"""
18 19 Returns a new `SortedSet`, initialized with the unique, sorted values of
  @@ -53,7 +54,8 @@ defmodule SortedSet do
53 54 [1,3,5]
54 55 """
55 56 def to_list(%SortedSet{members: members}) do
56 - members
57 + RedBlackTree.to_list(members)
58 + |> Enum.map(fn ({key, _value}) -> key end)
57 59 end
58 60
59 61 @doc ~S"""
  @@ -69,9 +71,9 @@ defmodule SortedSet do
69 71 iex> SortedSet.to_list SortedSet.put(set, 2)
70 72 [1,2,3,5]
71 73 """
72 - def put(%SortedSet{members: members, size: size}, element) do
73 - {new_members, members_added} = do_put(members, element)
74 - %SortedSet{members: new_members, size: size + members_added}
74 + def put(%SortedSet{members: members}, element) do
75 + new_tree = RedBlackTree.insert members, element, element
76 + %SortedSet{members: new_tree, size: new_tree.size}
75 77 end
76 78
77 79 @doc ~S"""
  @@ -91,9 +93,9 @@ defmodule SortedSet do
91 93 iex> SortedSet.to_list SortedSet.delete(set, 2)
92 94 []
93 95 """
94 - def delete(%SortedSet{members: members, size: size}, element) do
95 - {new_members, members_removed} = do_delete(members, element)
96 - %SortedSet{members: new_members, size: size - members_removed}
96 + def delete(%SortedSet{members: members}, element) do
97 + new_tree = RedBlackTree.delete members, element
98 + %SortedSet{members: new_tree, size: new_tree.size}
97 99 end
98 100
99 101 ## SortedSet predicate methods
  @@ -111,8 +113,8 @@ defmodule SortedSet do
111 113 iex> SortedSet.member?(set, 0)
112 114 false
113 115 """
114 - def member?(%SortedSet{}=set, element) do
115 - do_member?(to_list(set), element)
116 + def member?(%SortedSet{members: tree}, element) do
117 + RedBlackTree.has_key? tree, element
116 118 end
117 119
118 120 # If the sizes are not equal, no need to check members
  @@ -280,65 +282,6 @@ defmodule SortedSet do
280 282 def difference(%SortedSet{}=set1, %SortedSet{size: 0}) do
281 283 set1
282 284 end
283 -
284 - ## Private helper functions
285 -
286 - # SortedSet put
287 -
288 - defp do_put([head|tail], element) when element > head do
289 - {tail_members, members_added} = do_put(tail, element)
290 - {[head | tail_members], members_added}
291 - end
292 -
293 - defp do_put([head|_tail]=sorted_set, element) when element < head do
294 - {[element | sorted_set], 1}
295 - end
296 -
297 - defp do_put([head|_tail]=sorted_set, element) when element == head do
298 - {sorted_set, 0}
299 - end
300 -
301 - defp do_put([], element), do: {[element], 1}
302 -
303 - # SortedSet delete
304 -
305 - # If the element is less than the one we are looking at, we can safely
306 - # know it was never in the set
307 - defp do_delete([head|_tail]=members, element) when element < head do
308 - {members, 0}
309 - end
310 -
311 - # If the element is greater than the current head, we haven't reached where it
312 - # might exist in the set. Recur again on the tail.
313 - defp do_delete([head|tail], element) when element > head do
314 - {tail_members, members_removed} = do_delete(tail, element)
315 - {[head | tail_members], members_removed}
316 - end
317 -
318 - # If the element matches the head, drop it
319 - defp do_delete([head|tail], element) when element == head do
320 - {tail, 1}
321 - end
322 -
323 - defp do_delete([], _element) do
324 - {[], 0}
325 - end
326 -
327 - # SortedSet member?
328 -
329 - defp do_member?([head|_tail], element) when element < head do
330 - false
331 - end
332 -
333 - defp do_member?([head|tail], element) when element > head do
334 - do_member?(tail, element)
335 - end
336 -
337 - defp do_member?([head|_tail], element) when element == head do
338 - true
339 - end
340 -
341 - defp do_member?([], _element), do: false
342 285 end
343 286
344 287 defimpl Enumerable, for: SortedSet do
  @@ -3,7 +3,7 @@ defmodule SortedSet.Mixfile do
3 3
4 4 def project do
5 5 [app: :sorted_set,
6 - version: "0.1.1",
6 + version: "0.2.0",
7 7 source_url: "https://github.com/SenecaSystems/sorted_set",
8 8 elixir: "~> 1.0",
9 9 description: "SortedSet implementation for Elixir",