Class: SortedContainers::SortedSet

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

Overview

SortedSet is a set that maintains its elements in sorted order.

SortedSet has most of the same methods as Set, but also has the following additional methods:

  • #bisect_left

  • #bisect_right

  • #delete_at

  • #last

  • #[]

Addtionally, there are methods that work differently than their Set counterparts. Generally, methods that use Entry Order will use the sort order of the keys instead. For example:

s = Set.new
s.add(2)
s.add(1)
s.first # => 2

ss = SortedSet.new
ss.add(2)
ss.add(1)
ss.first # => 1

Class Method Summary collapse

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.



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

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

Class Method Details

.[](*args) ⇒ SortedSet

Creates a new instance of the SortedSet class.

Parameters:

  • args (Array) —

    The initial elements of the sorted set.

Returns:

  • (SortedSet) —

    A new instance of the SortedSet class.



51
52
53
 
# File 'lib/sorted_containers/sorted_set.rb', line 51

def self.[](*args)
  new(args)
end

Instance Method Details

#<=>(other) ⇒ Object

See Also:

  • Set#<=>


111
112
113
 
# File 'lib/sorted_containers/sorted_set.rb', line 111

def <=>(other)
  @set <=> other.set
end

#==(other) ⇒ Object

See Also:

  • Set#==


116
117
118
 
# File 'lib/sorted_containers/sorted_set.rb', line 116

def ==(other)
  @set == other.set
end

#=== ⇒ Object

See Also:

  • Set#===


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#[] ⇒ Object

See Also:



69
70
71
72
73
74
75
76
 
# File 'lib/sorted_containers/sorted_set.rb', line 69

def_delegators :@list,
:[],
:to_a,
:join,
:first,
:last,
:bisect_left,
:bisect_right

#^(other) ⇒ Object

See Also:

  • Set#^


169
170
171
 
# File 'lib/sorted_containers/sorted_set.rb', line 169

def ^(other)
  SortedSet.new(@set ^ other.set, load_factor: @list.load_factor)
end

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

See Also:

  • Set#add


196
197
198
199
200
201
 
# File 'lib/sorted_containers/sorted_set.rb', line 196

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

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

#add?(item) ⇒ Boolean

Returns:

  • (Boolean)

See Also:

  • Set#add?


205
206
207
208
209
210
211
 
# File 'lib/sorted_containers/sorted_set.rb', line 205

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

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

#bisect_left ⇒ Object

See Also:



69
70
71
72
73
74
75
76
 
# File 'lib/sorted_containers/sorted_set.rb', line 69

def_delegators :@list,
:[],
:to_a,
:join,
:first,
:last,
:bisect_left,
:bisect_right

#bisect_right ⇒ Object

See Also:



69
70
71
72
73
74
75
76
 
# File 'lib/sorted_containers/sorted_set.rb', line 69

def_delegators :@list,
:[],
:to_a,
:join,
:first,
:last,
:bisect_left,
:bisect_right

#classify ⇒ Object

See Also:

  • Set#classify


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#clear ⇒ SortedSet

Clears the sorted set. Removes all elements.

Returns:



175
176
177
178
179
 
# File 'lib/sorted_containers/sorted_set.rb', line 175

def clear
  @set.clear
  @list.clear
  self
end

#collect! ⇒ Object Also known as: map!

See Also:

  • Set#collect!


182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/sorted_containers/sorted_set.rb', line 182

def collect!
  return enum_for(:collect!) unless block_given?

  @list.collect! do |item|
    new_item = yield(item)
    @set.delete(item)
    @set.add(new_item)
    new_item
  end
  self
end

#delete(item) ⇒ Object

See Also:

  • Set#delete


222
223
224
225
226
227
228
 
# File 'lib/sorted_containers/sorted_set.rb', line 222

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

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

#delete?(item) ⇒ Boolean

Returns:

  • (Boolean)

See Also:

  • Set#delete?


231
232
233
234
235
236
237
 
# File 'lib/sorted_containers/sorted_set.rb', line 231

def delete?(item)
  return unless @set.include?(item) # rubocop:disable Style/ReturnNilInPredicateMethodDefinition

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

#delete_at(index) ⇒ Object

Removes the item at the specified index.

Parameters:

  • index (Integer) —

    The index of the item to remove.



257
258
259
260
261
262
263
 
# File 'lib/sorted_containers/sorted_set.rb', line 257

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

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

#delete_if ⇒ Object

See Also:

  • Set#delete_if


240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/sorted_containers/sorted_set.rb', line 240

def delete_if
  return enum_for(:delete_if) unless block_given?

  @list.delete_if do |item|
    if yield(item)
      @set.delete(item)
      true
    else
      false
    end
  end
  self
end

#difference(other) ⇒ Object Also known as: -

See Also:

  • Set#difference


163
164
165
 
# File 'lib/sorted_containers/sorted_set.rb', line 163

def difference(other)
  SortedSet.new(@set - other.set, load_factor: @list.load_factor)
end

#disjoint? ⇒ Object

See Also:

  • Set#disjoint?


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#divide ⇒ Object

See Also:

  • Set#divide


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#each(&block) ⇒ Object

See Also:

  • Set#each


266
267
268
269
270
271
 
# File 'lib/sorted_containers/sorted_set.rb', line 266

def each(&block)
  return enum_for(:each) unless block_given?

  @list.each(&block)
  self
end

#empty? ⇒ Object

See Also:

  • Set#empty?


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#first ⇒ Object

See Also:



69
70
71
72
73
74
75
76
 
# File 'lib/sorted_containers/sorted_set.rb', line 69

def_delegators :@list,
:[],
:to_a,
:join,
:first,
:last,
:bisect_left,
:bisect_right

#flatten(level = 1) ⇒ Object

See Also:

  • Set#flatten


290
291
292
 
# File 'lib/sorted_containers/sorted_set.rb', line 290

def flatten(level = 1)
  SortedSet.new(@list.flatten(level), load_factor: @list.load_factor)
end

#flatten!(level = 1) ⇒ Object

See Also:

  • Set#flatten!


295
296
297
298
299
300
 
# File 'lib/sorted_containers/sorted_set.rb', line 295

def flatten!(level = 1)
  @set.clear
  @list.flatten!(level)
  @set.merge(@list)
  self
end

#include? ⇒ Object

See Also:

  • Set#include?


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#intersect?(other) ⇒ Boolean

Returns:

  • (Boolean)

See Also:

  • Set#intersect?


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

def intersect?(other)
  @set.intersect?(other.set)
end

#intersection(other) ⇒ Object Also known as: &

See Also:

  • Set#intersection


150
151
152
 
# File 'lib/sorted_containers/sorted_set.rb', line 150

def intersection(other)
  SortedSet.new(@set & other.set, load_factor: @list.load_factor)
end

#join ⇒ Object

See Also:



69
70
71
72
73
74
75
76
 
# File 'lib/sorted_containers/sorted_set.rb', line 69

def_delegators :@list,
:[],
:to_a,
:join,
:first,
:last,
:bisect_left,
:bisect_right

#keep_if ⇒ Object

See Also:

  • Set#keep_if


303
304
305
306
307
308
309
310
311
312
313
314
315
 
# File 'lib/sorted_containers/sorted_set.rb', line 303

def keep_if
  return enum_for(:keep_if) unless block_given?

  @list.keep_if do |item|
    if yield(item)
      @set.delete(item)
      true
    else
      false
    end
  end
  self
end

#last ⇒ Object

See Also:



69
70
71
72
73
74
75
76
 
# File 'lib/sorted_containers/sorted_set.rb', line 69

def_delegators :@list,
:[],
:to_a,
:join,
:first,
:last,
:bisect_left,
:bisect_right

#length ⇒ Object

See Also:

  • Set#length


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#member? ⇒ Object

See Also:

  • Set#member?


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#merge(other) ⇒ Object

See Also:

  • Set#merge


318
319
320
321
322
323
 
# File 'lib/sorted_containers/sorted_set.rb', line 318

def merge(other)
  @set.merge(other.set)
  @list.clear
  @list.update(@set)
  self
end

#proper_subset?(other) ⇒ Boolean Also known as: <

Returns:

  • (Boolean)

See Also:

  • Set#proper_subset?


138
139
140
 
# File 'lib/sorted_containers/sorted_set.rb', line 138

def proper_subset?(other)
  @set.proper_subset?(other.set)
end

#proper_superset?(other) ⇒ Boolean Also known as: >

Returns:

  • (Boolean)

See Also:

  • Set#proper_superset?


144
145
146
 
# File 'lib/sorted_containers/sorted_set.rb', line 144

def proper_superset?(other)
  @set.proper_superset?(other.set)
end

#reject! ⇒ Object

See Also:

  • Set#reject!


328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
 
# File 'lib/sorted_containers/sorted_set.rb', line 328

def reject!
  return enum_for(:reject!) unless block_given?

  changed = false
  @list.reject! do |item|
    if yield(item)
      @set.delete(item)
      changed = true
      true
    else
      false
    end
  end
  changed ? self : nil
end

#replace(other) ⇒ Object

See Also:

  • Set#replace


347
348
349
350
351
352
 
# File 'lib/sorted_containers/sorted_set.rb', line 347

def replace(other)
  @set.replace(other.set)
  @list.clear
  @list.update(@set)
  self
end

#reset ⇒ Object

See Also:

  • Set#reset


355
356
357
358
359
360
361
362
 
# File 'lib/sorted_containers/sorted_set.rb', line 355

def reset
  values = @list.to_a
  @set.clear
  @list.clear
  @set.merge(values)
  @list.update(values)
  self
end

#select! ⇒ Object Also known as: filter!

See Also:

  • Set#select!


274
275
276
277
278
279
280
281
282
283
284
285
286
 
# File 'lib/sorted_containers/sorted_set.rb', line 274

def select!
  return enum_for(:select!) unless block_given?

  @list.filter! do |item|
    if yield(item)
      @set.delete(item)
      true
    else
      false
    end
  end
  self
end

#size ⇒ Object

See Also:

  • Set#size


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#subset?(other) ⇒ Boolean Also known as: <=

Returns:

  • (Boolean)

See Also:

  • Set#subset?


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

def subset?(other)
  @set.subset?(other.set)
end

#subtract(other) ⇒ Object

See Also:

  • Set#subtract


365
366
367
368
369
370
 
# File 'lib/sorted_containers/sorted_set.rb', line 365

def subtract(other)
  @set.subtract(other.set)
  @list.clear
  @list.update(@set)
  self
end

#superset?(other) ⇒ Boolean Also known as: >=

Returns:

  • (Boolean)

See Also:

  • Set#superset?


132
133
134
 
# File 'lib/sorted_containers/sorted_set.rb', line 132

def superset?(other)
  @set.superset?(other.set)
end

#to_a ⇒ Object

See Also:



69
70
71
72
73
74
75
76
 
# File 'lib/sorted_containers/sorted_set.rb', line 69

def_delegators :@list,
:[],
:to_a,
:join,
:first,
:last,
:bisect_left,
:bisect_right

#to_s ⇒ String Also known as: inspect

Returns a string representation of the sorted set.

Returns:

  • (String) —

    A string representation of the sorted set.



216
217
218
 
# File 'lib/sorted_containers/sorted_set.rb', line 216

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

#to_set ⇒ Object

See Also:

  • Set#to_set


98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/sorted_containers/sorted_set.rb', line 98

def_delegators :@set,
:===,
:classify,
:include?,
:member?,
:size,
:length,
:disjoint?,
:divide,
:empty?,
:to_set

#union(other) ⇒ Object Also known as: +, |

See Also:

  • Set#union


156
157
158
 
# File 'lib/sorted_containers/sorted_set.rb', line 156

def union(other)
  SortedSet.new(@set + other.set, load_factor: @list.load_factor)
end