struct AVLTree::SortedMultiset(T)

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

Overview

SortedMultiset implements a collection of sorted values with possible duplicates.

Sample

require "avltree"

mset = AVLTree::SortedMultiset(Int32).new
mset << 3 << 1 << 4 << 1 << 5 << 9

mset # => SortedMultiset{1, 1, 3, 4, 5, 9}

mset[0] # => 1
mset[1] # => 1
mset[2] # => 3  (SortedMultiset#[k] returns the kth object)

mset.lower_bound(-1) # => 0
mset.lower_bound(2)  # => 2
mset.lower_bound(3)  # => 2
mset.lower_bound(9)  # => 5
mset.lower_bound(10) # => 6

mset.delete(1)
mset # => SortedMultiset{1, 3, 4, 5, 9}

Included Modules

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

Defined in:

Constructors

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

Instance Method Summary

• #&(other : SortedMultiset)
• #+(other : SortedMultiset(U)) forall U
• #-(other : SortedMultiset)
• #-(other : Enumerable)
• #<<(object : T)
• #==(other : SortedMultiset)
• #===(object : T)
• #^(other : SortedMultiset(U)) forall U
• #^(other : Enumerable(U)) forall U
• #|(other : SortedMultiset(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 multiset'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(object)
• #delete_at?(object)
• #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
• #greater_equal_object(object) : T | Nil
• #greater_equal_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)
• #greater_index(object) : Int32 | Nil
• #greater_object(object) : T | Nil
• #greater_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)
• #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 : SortedMultiset)
• #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
• #less_equal_object(object) : T | Nil
• #less_equal_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)
• #less_index(object) : Int32 | Nil
• #less_object(object) : T | Nil
• #less_object_with_index(object) : Tuple(T | Nil, Int32 | Nil)
• #lower_bound(object) : Int32
• #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 : SortedMultiset)
• #proper_superset?(other : SortedMultiset)
• #rindex(object)

  Returns the index of the last appearance of value in self, or nil if the value is not in self.

• #rindex!(object)

  Returns the index of the last appearance of value in self, or nil if the value is not in self.

• #same?(other : SortedMultiset)
• #shift : T
• #shift(&)
• #shift? : T | Nil
• #size

  Returns the number of elements in this container.

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

  Returns an Array with all the elements in the collection.

• #to_s(io : IO) : Nil

  Same as #inspect(io).

• #unordered_each(&)
• #unsafe_fetch(index : Int)

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

• #upper_bound(object) : Int32

Constructor Detail

Instance Method Detail

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

[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

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

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

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

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

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