struct AVLTree::SortedSet(T)

• AVLTree::SortedSet(T)
• Struct
• Value
• Object

Overview

SortedSet implements a Set that guarantees that its elements are yielded in sorted order (according to the return values of their #<=> methods) when iterating over them.

SortedSet utilizes an internally implemented SortedMap using an AVL tree.

While it often has slower computational speed compared to a Set implemented using a hash-based approach, it offers potential optimizations for operations related to order. For example, retrieving the maximum and minimum values of the set can be performed in logarithmic time.

SortedSet does not allow duplicates and only stores unique values.

Example

require "avltree"

set = AVLTree::SortedSet.new [3, 1, 4]
set.to_a == [1, 3, 4] # => true
set.to_a == [3, 1, 4] # => false

set << 1 << 5
set                 # => SortedSet{1, 3, 4, 5}
set.min             # => 1  (O(logN))
set.max             # => 5  (O(logN))
set.index(4)        # => 2  (O(logN))
set.upper_bound(2)  # => 1  (O(logN))
set.upper_bound(3)  # => 1  (O(logN))
set.upper_bound(10) # => 4  (O(logN))

Included Modules

• Enumerable(T)
• Indexable(T)
• Iterable(T)

Defined in:

Constructors

• .new(other : Indexable(T))
• .new(enumerable : Enumerable(T))
• .new

Instance Method Summary

• #&(other : Set)
• #+(other : Set(U)) forall U
• #-(other : Set)
• #-(other : Enumerable)
• #<<(object : T)
• #==(other : SortedSet)
• #===(object : T)
• #^(other : SortedSet(U)) forall U
• #^(other : Enumerable(U)) forall U
• #|(other : SortedSet(U)) forall U
• #add(object : T)
• #add?(object : T)
• #at(index : Int)

  Returns the element at the index-th.

• #at(index : Int, &)

  Returns the element at the index-th.

• #at?(index : Int)

  Like #at, but returns nil if trying to access an element outside the set's range.

• #clear
• #clone
• #concat(elems)
• #count(range : Range(T | Nil, T | Nil))

  Returns the number of elements in the set that exist within the range.

• #count(object)

  Returns the number of times that the passed item is present in the collection.

• #delete(object)
• #delete_at(index : Int, &)
• #delete_at(index : Int)
• #delete_at?(index : Int)
• #dup

  Returns a shallow copy of this object.

• #each(&)

  Calls the given block once for each element in self, passing that element as a parameter.

• #each

  Must return an Iterator over the elements in this collection.

• #empty?

  Returns true if self is empty, false otherwise.

• #fetch(index : Int, &)

  Returns the element at the given index, if in bounds, otherwise executes the given block with the index and returns its value.

• #fetch(index : Int, default)
• #first

  Returns the first element in the collection.

• #first?

  Returns the first element in the collection.

• #greater_equal_index(object) : Int32 | Nil

  See SortedMap#greater_equal_index

• #greater_equal_object(object) : T | Nil

  See SortedMap#greater_equal_item

• #greater_equal_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#greater_equal_item_with_index

• #greater_index(object) : Int32 | Nil

  See SortedMap#greater_index

• #greater_object(object) : T | Nil

  See SortedMap#greater_item

• #greater_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#greater_item_with_index

• #hash(hasher)

  See Object#hash(hasher)

• #includes?(object)

  Returns true if the collection contains obj, false otherwise.

• #index(object)

  Returns the index of the first appearance of object in self starting from the given offset, or nil if object is not in self.

• #index!(object)

  Returns the index of the first appearance of obj in self starting from the given offset.

• #inspect(io : IO) : Nil

  Appends this struct's name and instance variables names and values to the given IO.

• #intersects?(other : Set)
• #last

  Returns the last element of self if it's not empty, or raises IndexError.

• #last?

  Returns the last element of self if it's not empty, or nil.

• #less_equal_index(object) : Int32 | Nil

  See SortedMap#less_equal_index

• #less_equal_object(object) : T | Nil

  See SortedMap#less_equal_item

• #less_equal_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#less_equal_item_with_index

• #less_index(object) : Int32 | Nil

  See SortedMap#less_index

• #less_object(object) : T | Nil

  See SortedMap#less_item

• #less_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#less_item_with_index

• #lower_bound(object) : Int32

  set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"} set # => SortedSet{"A", "B", "C", "E"} set.lower_bound("@") # => 0 set.lower_bound("A") # => 0 set.lower_bound("B") # => 1 set.lower_bound("C") # => 2 set.lower_bound("D") # => 3 set.lower_bound("E") # => 3 set.lower_bound("F") # => 4 set.lower_bound("Z") # => 4

• #max

  Returns the element with the maximum value in the collection.

• #max?

  Like #max but returns nil if the collection is empty.

• #min

  Returns the element with the minimum value in the collection.

• #min?

  Like #min but returns nil if the collection is empty.

• #object_id
• #pop : T
• #pop(&)
• #pop? : T | Nil
• #pretty_print(pp) : Nil
• #proper_subset_of?(other : SortedSet)
• #proper_superset_of?(other : SortedSet)
• #same?(other : SortedSet)
• #shift : T
• #shift(&)
• #shift? : T | Nil
• #size

  Returns the number of elements in this container.

• #subset_of?(other : SortedSet)
• #subtract(other : Enumerable)
• #superset_of?(other : SortedSet)
• #to_a

  Returns an Array with all the elements in the collection.

• #to_s(io : IO) : Nil

  Same as #inspect(io).

• #unordered_each(&)

  Yields each element of the set, and returns self.

• #unsafe_fetch(index : Int)

  Returns the element at the given index, without doing any bounds check.

• #upper_bound(object) : Int32

  set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"} set # => SortedSet{"A", "B", "C", "E"} set.upper_bound("@") # => 0 set.upper_bound("A") # => 1 set.upper_bound("B") # => 2 set.upper_bound("C") # => 3 set.upper_bound("D") # => 3 set.upper_bound("E") # => 4 set.upper_bound("F") # => 4 set.upper_bound("Z") # => 4

Constructor Detail

Instance Method Detail

set = AVLTree::SortedSet(Int32){3, 1, 4, 1, 5, 9}
set.count(2..3)  # => 1
set.count(2...3) # => 0
set.count(2..9)  # => 4
set.count(2...9) # => 3
set.count(2...)  # => 4
set.count(...)   # => 5
set.count(...9)  # => 4

[1, 2, 3, 4].count(3) # => 1

a = ["a", "b", "c"]
a.each { |x| print x, " -- " }

a -- b -- c --

([] of Int32).empty? # => true
([1]).empty?         # => false

a = [:foo, :bar]
a.fetch(0) { :default_value }    # => :foo
a.fetch(2) { :default_value }    # => :default_value
a.fetch(2) { |index| index * 3 } # => 6

([1, 2, 3]).first   # => 1
([] of Int32).first # raises Enumerable::EmptyError

([1, 2, 3]).first?   # => 1
([] of Int32).first? # => nil

[1, 2, 3].includes?(2) # => true
[1, 2, 3].includes?(5) # => false

[1, 2, 3, 1, 2, 3].index(2, offset: 2) # => 4

[1, 2, 3, 1, 2, 3].index!(2, offset: 2) # => 4

struct Point
  def initialize(@x : Int32, @y : Int32)
  end
end

p1 = Point.new 1, 2
p1.to_s    # "Point(@x=1, @y=2)"
p1.inspect # "Point(@x=1, @y=2)"

([1, 2, 3]).last   # => 3
([] of Int32).last # raises IndexError

([1, 2, 3]).last?   # => 3
([] of Int32).last? # => nil

set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"}
set                  # => SortedSet{"A", "B", "C", "E"}
set.lower_bound("@") # => 0
set.lower_bound("A") # => 0
set.lower_bound("B") # => 1
set.lower_bound("C") # => 2
set.lower_bound("D") # => 3
set.lower_bound("E") # => 3
set.lower_bound("F") # => 4
set.lower_bound("Z") # => 4

[1, 2, 3].max        # => 3
["Alice", "Bob"].max # => "Bob"

[1, 2, 3].min        # => 1
["Alice", "Bob"].min # => "Alice"

{1, 2, 3}.to_a # => [1, 2, 3]

set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"}
set                  # => SortedSet{"A", "B", "C", "E"}
set.upper_bound("@") # => 0
set.upper_bound("A") # => 1
set.upper_bound("B") # => 2
set.upper_bound("C") # => 3
set.upper_bound("D") # => 3
set.upper_bound("E") # => 4
set.upper_bound("F") # => 4
set.upper_bound("Z") # => 4