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.

Parameters:

  • iterable (Array) (defaults to: []) —

    The initial elements of the sorted set.

  • load_factor (Integer) (defaults to: SortedArray::DEFAULT_LOAD_FACTOR) —

    The load factor for the sorted set.



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.

Parameters:

  • index (Integer) —

    The index of the item to retrieve.



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.

Parameters:

  • item (Object) —

    The item to be added.



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.

Parameters:

  • value (Object) —

    The value to insert.

Returns:

  • (Integer) —

    The index to insert the value.

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.

Parameters:

  • value (Object) —

    The value to insert.

Returns:

  • (Integer) —

    The index to insert the value.

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.

Parameters:

  • item (Object) —

    The item to be removed.



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.

Parameters:

  • index (Integer) —

    The index of the item to remove.



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.

Returns:

  • (Object) —

    The first item.



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.

Parameters:

  • item (Object) —

    The item to be checked.

Returns:

  • (Boolean) —

    true if the item is included, false otherwise.



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.

Returns:

  • (Object) —

    The last item.



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.

Returns:

  • (Integer) —

    The number of items.



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.

Returns:

  • (Array) —

    The items in the sorted set.



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.

Returns:

  • (String) —

    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