Class: SortedContainers::SortedSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/sorted_containers/sorted_set.rb

Overview

The SortedSet class is a sorted set implementation.

Instance Method Summary collapse

Constructor Details

#initialize(iterable = [], load_factor: SortedArray::DEFAULT_LOAD_FACTOR) ⇒ SortedSet

Initializes a new instance of the SortedSet class.



16
17
18
19
 
# File 'lib/sorted_containers/sorted_set.rb', line 16

def initialize(iterable = [], load_factor: SortedArray::DEFAULT_LOAD_FACTOR)
  @set = Set.new(iterable)
  @list = SortedContainers::SortedArray.new(@set.to_a, load_factor: load_factor)
end

Instance Method Details

#[](index) ⇒ Object

Retrieves the item at the specified index.



35
36
37
 
# File 'lib/sorted_containers/sorted_set.rb', line 35

def [](index)
  @list[index]
end

#add(item) ⇒ Object Also known as: <<

Adds an item to the sorted set.



24
25
26
27
28
29
 
# File 'lib/sorted_containers/sorted_set.rb', line 24

def add(item)
  return if @set.include?(item)

  @set.add(item)
  @list.add(item)
end

#bisect_left(value) ⇒ Integer

Returns an index to insert value in the sorted list.

If the value is already present, the insertion point will be before (to the left of) any existing values.

Runtime complexity: ‘O(log(n))` – approximate.

See Also:



106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 106

def bisect_left(value)
  @list.bisect_left(value)
end

#bisect_right(value) ⇒ Integer

Returns an index to insert value in the sorted list.

If the value is already present, the insertion point will be after (to the right of) any existing values.

Runtime complexity: ‘O(log(n))` – approximate.

See Also:



120
121
122
 
# File 'lib/sorted_containers/sorted_set.rb', line 120

def bisect_right(value)
  @list.bisect_right(value)
end

#delete(item) ⇒ Object

Removes an item from the sorted set.



63
64
65
66
67
68
 
# File 'lib/sorted_containers/sorted_set.rb', line 63

def delete(item)
  return unless @set.include?(item)

  @set.delete(item)
  @list.delete(item)
end

#delete_at(index) ⇒ Object

Removes the item at the specified index.



73
74
75
76
77
78
79
 
# File 'lib/sorted_containers/sorted_set.rb', line 73

def delete_at(index)
  return if index.abs >= @list.size

  item = @list.delete_at(index)
  @set.delete(item)
  item
end

#each {|item| ... } ⇒ Object

Iterates over each item in the sorted set.

Yields:

  • (item) —

    Gives each item to the block.



134
135
136
 
# File 'lib/sorted_containers/sorted_set.rb', line 134

def each(&block)
  @list.each(&block)
end

#first ⇒ Object

Retrieves the first item in the sorted set.



49
50
51
 
# File 'lib/sorted_containers/sorted_set.rb', line 49

def first
  @list.first
end

#include?(item) ⇒ Boolean

Checks if an item is included in the sorted set.



92
93
94
 
# File 'lib/sorted_containers/sorted_set.rb', line 92

def include?(item)
  @set.include?(item)
end

#last ⇒ Object

Retrieves the last item in the sorted set.



56
57
58
 
# File 'lib/sorted_containers/sorted_set.rb', line 56

def last
  @list.last
end

#size ⇒ Integer

Returns the number of items in the sorted set.



84
85
86
 
# File 'lib/sorted_containers/sorted_set.rb', line 84

def size
  @list.size
end

#to_a ⇒ Array

Returns the items in the sorted set as an array.



127
128
129
 
# File 'lib/sorted_containers/sorted_set.rb', line 127

def to_a
  @list.to_a
end

#to_s ⇒ String

Returns a string representation of the sorted set.



42
43
44
 
# File 'lib/sorted_containers/sorted_set.rb', line 42

def to_s
  "SortedSet(#{to_a.join(", ")})"
end