Documentation

Std.Data.ExtDTreeMap.Basic

Extensional dependent tree maps #

This file develops the type Std.ExtDTreeMap of extensional dependent tree maps.

Lemmas about the operations on Std.ExtDTreeMap will be available in the module Std.Data.ExtDTreeMap.Lemmas.

See the module Std.Data.DTreeMap.Raw.Basic for a variant of this type which is safe to use in nested inductive types.

structure Std.ExtDTreeMap (α : Type u) (β : αType v) (cmp : ααOrdering := by exact compare) :
Type (max u v)

Extensional dependent tree maps.

A tree map stores an assignment of keys to values. It depends on a comparator function that defines an ordering on the keys and provides efficient order-dependent queries, such as retrieval of the minimum or maximum.

To ensure that the operations behave as expected, the comparator function cmp should satisfy certain laws that ensure a consistent ordering:

  • If a is less than (or equal) to b, then b is greater than (or equal) to a and vice versa (see the OrientedCmp typeclass).
  • If a is less than or equal to b and b is, in turn, less than or equal to c, then a is less than or equal to c (see the TransCmp typeclass).

Keys for which cmp a b = Ordering.eq are considered the same, i.e., there can be only one entry with key either a or b in a tree map. Looking up either a or b always yields the same entry, if any is present. The get operations of the dependent tree map additionally require a LawfulEqCmp instance to ensure that cmp a b = .eq always implies a = b, so that their respective value types are equal.

To avoid expensive copies, users should make sure that the tree map is used linearly.

Internally, the tree maps are represented as size-bounded trees, a type of self-balancing binary search tree with efficient order statistic lookups.

In contrast to regular dependent tree maps, Std.ExtDTreeMap offers several extensionality lemmas and therefore has more lemmas about equality of tree maps. This doesn't affect the amount of supported functions though: Std.ExtDTreeMap supports all operations from Std.DTreeMap.

In order to use most functions, a TransCmp instance is required. This is necessary to make sure that the functions are congruent, i.e. equivalent tree maps as parameters produce equivalent return values.

These tree maps contain a bundled well-formedness invariant, which means that they cannot be used in nested inductive types. For these use cases, Std.DTreeMap.Raw and Std.DTreeMap.Raw.WF unbundle the invariant from the tree map. When in doubt, prefer ExtDTreeMap over DTreeMap.Raw.

Instances For
    @[reducible, inline]
    abbrev Std.ExtDTreeMap.mk {α : Type u} {β : αType v} {cmp : ααOrdering} (t : DTreeMap α β cmp) :
    ExtDTreeMap α β cmp

    Implementation detail of the tree map

    Equations
    Instances For
      @[reducible, inline]
      abbrev Std.ExtDTreeMap.lift {α : Type u} {β : αType v} {cmp : ααOrdering} {γ : Sort w} (f : DTreeMap α β cmpγ) (h : ∀ (a b : DTreeMap α β cmp), a.Equiv bf a = f b) (t : ExtDTreeMap α β cmp) :
      γ

      Implementation detail of the tree map

      Equations
      Instances For
        @[reducible, inline]
        abbrev Std.ExtDTreeMap.liftOn₂ {α : Type u} {β : αType v} {cmp : ααOrdering} {γ : Sort w} (t₁ t₂ : ExtDTreeMap α β cmp) (f : DTreeMap α β cmpDTreeMap α β cmpγ) (h : ∀ (a b c d : DTreeMap α β cmp), a.Equiv cb.Equiv df a b = f c d) :
        γ

        Implementation detail of the tree map

        Equations
        Instances For
          @[reducible, inline]
          abbrev Std.ExtDTreeMap.pliftOn {α : Type u} {β : αType v} {cmp : ααOrdering} {γ : Sort w} (t : ExtDTreeMap α β cmp) (f : (x : DTreeMap α β cmp) → t = mk xγ) (h : ∀ (a b : DTreeMap α β cmp) (h₁ : t = mk a) (h₂ : t = mk b), a.Equiv bf a h₁ = f b h₂) :
          γ

          Implementation detail of the tree map

          Equations
          Instances For
            theorem Std.ExtDTreeMap.sound {α : Type u} {β : αType v} {cmp : ααOrdering} {t₁ t₂ : DTreeMap α β cmp} (h : t₁.Equiv t₂) :
            mk t₁ = mk t₂
            theorem Std.ExtDTreeMap.exact {α : Type u} {β : αType v} {cmp : ααOrdering} {t₁ t₂ : DTreeMap α β cmp} (h : mk t₁ = mk t₂) :
            t₁.Equiv t₂
            theorem Std.ExtDTreeMap.inductionOn {α : Type u} {β : αType v} {cmp : ααOrdering} {motive : ExtDTreeMap α β cmpProp} (t : ExtDTreeMap α β cmp) (mk : ∀ (a : DTreeMap α β cmp), motive (mk a)) :
            motive t
            theorem Std.ExtDTreeMap.inductionOn₂ {α : Type u} {β : αType v} {cmp : ααOrdering} {motive : ExtDTreeMap α β cmpExtDTreeMap α β cmpProp} (t₁ t₂ : ExtDTreeMap α β cmp) (mk : ∀ (a b : DTreeMap α β cmp), motive (mk a) (mk b)) :
            motive t₁ t₂
            @[inline]
            def Std.ExtDTreeMap.empty {α : Type u} {β : αType v} {cmp : ααOrdering} :
            ExtDTreeMap α β cmp

            Creates a new empty tree map. It is also possible and recommended to use the empty collection notations and {} to create an empty tree map. simp replaces empty with .

            Equations
            Instances For
              instance Std.ExtDTreeMap.instEmptyCollection {α : Type u} {β : αType v} {cmp : ααOrdering} :
              Equations
              instance Std.ExtDTreeMap.instInhabited {α : Type u} {β : αType v} {cmp : ααOrdering} :
              Equations
              @[simp]
              theorem Std.ExtDTreeMap.empty_eq_emptyc {α : Type u} {β : αType v} {cmp : ααOrdering} :
              @[inline]
              def Std.ExtDTreeMap.insert {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) :
              ExtDTreeMap α β cmp

              Inserts the given mapping into the map. If there is already a mapping for the given key, then both key and value will be replaced.

              Equations
              Instances For
                instance Std.ExtDTreeMap.instSingletonSigmaOfTransCmp {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] :
                Singleton ((a : α) × β a) (ExtDTreeMap α β cmp)
                Equations
                instance Std.ExtDTreeMap.instInsertSigmaOfTransCmp {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] :
                Insert ((a : α) × β a) (ExtDTreeMap α β cmp)
                Equations
                instance Std.ExtDTreeMap.instLawfulSingletonSigma {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] :
                LawfulSingleton ((a : α) × β a) (ExtDTreeMap α β cmp)
                @[inline]
                def Std.ExtDTreeMap.insertIfNew {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) :
                ExtDTreeMap α β cmp

                If there is no mapping for the given key, inserts the given mapping into the map. Otherwise, returns the map unaltered.

                Equations
                Instances For
                  @[inline]
                  def Std.ExtDTreeMap.containsThenInsert {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) :
                  Bool × ExtDTreeMap α β cmp

                  Checks whether a key is present in a map and unconditionally inserts a value for the key.

                  Equivalent to (but potentially faster than) calling contains followed by insert.

                  Equations
                  Instances For
                    @[inline]
                    def Std.ExtDTreeMap.containsThenInsertIfNew {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) :
                    Bool × ExtDTreeMap α β cmp

                    Checks whether a key is present in a map and inserts a value for the key if it was not found. If the returned Bool is true, then the returned map is unaltered. If the Bool is false, then the returned map has a new value inserted.

                    Equivalent to (but potentially faster than) calling contains followed by insertIfNew.

                    Equations
                    Instances For
                      @[inline]
                      def Std.ExtDTreeMap.getThenInsertIfNew? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (b : β a) :
                      Option (β a) × ExtDTreeMap α β cmp

                      Checks whether a key is present in a map, returning the associated value, and inserts a value for the key if it was not found.

                      If the returned value is some v, then the returned map is unaltered. If it is none, then the returned map has a new value inserted.

                      Equivalent to (but potentially faster than) calling get? followed by insertIfNew.

                      Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                      Equations
                      Instances For
                        @[inline]
                        def Std.ExtDTreeMap.contains {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) :

                        Returns true if there is a mapping for the given key a or a key that is equal to a according to the comparator cmp. There is also a Prop-valued version of this: a ∈ t is equivalent to t.contains a = true.

                        Observe that this is different behavior than for lists: for lists, uses = and contains uses == for equality checks, while for tree maps, both use the given comparator cmp.

                        Equations
                        Instances For
                          instance Std.ExtDTreeMap.instMembershipOfTransCmp {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] :
                          Membership α (ExtDTreeMap α β cmp)
                          Equations
                          instance Std.ExtDTreeMap.instDecidableMem {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] {m : ExtDTreeMap α β cmp} {a : α} :
                          Equations
                          @[inline]
                          def Std.ExtDTreeMap.size {α : Type u} {β : αType v} {cmp : ααOrdering} (t : ExtDTreeMap α β cmp) :

                          Returns the number of mappings present in the map.

                          Equations
                          Instances For
                            @[inline]
                            def Std.ExtDTreeMap.isEmpty {α : Type u} {β : αType v} {cmp : ααOrdering} (t : ExtDTreeMap α β cmp) :

                            Returns true if the tree map contains no mappings.

                            Equations
                            Instances For
                              @[simp]
                              theorem Std.ExtDTreeMap.isEmpty_iff {α : Type u} {β : αType v} {cmp : ααOrdering} {t : ExtDTreeMap α β cmp} [TransCmp cmp] :
                              @[simp]
                              theorem Std.ExtDTreeMap.isEmpty_eq_false_iff {α : Type u} {β : αType v} {cmp : ααOrdering} {t : ExtDTreeMap α β cmp} [TransCmp cmp] :
                              @[inline]
                              def Std.ExtDTreeMap.erase {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) :
                              ExtDTreeMap α β cmp

                              Removes the mapping for the given key if it exists.

                              Equations
                              Instances For
                                @[inline]
                                def Std.ExtDTreeMap.get? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) :
                                Option (β a)

                                Tries to retrieve the mapping for the given key, returning none if no such mapping is present.

                                Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                Equations
                                Instances For
                                  @[inline]
                                  def Std.ExtDTreeMap.get {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (h : a t) :
                                  β a

                                  Given a proof that a mapping for the given key is present, retrieves the mapping for the given key.

                                  Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                  Equations
                                  Instances For
                                    @[inline]
                                    def Std.ExtDTreeMap.get! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) [Inhabited (β a)] :
                                    β a

                                    Tries to retrieve the mapping for the given key, panicking if no such mapping is present.

                                    Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                    Equations
                                    Instances For
                                      @[inline]
                                      def Std.ExtDTreeMap.getD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (fallback : β a) :
                                      β a

                                      Tries to retrieve the mapping for the given key, returning fallback if no such mapping is present.

                                      Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                      Equations
                                      Instances For
                                        @[inline]
                                        def Std.ExtDTreeMap.getKey? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) :

                                        Checks if a mapping for the given key exists and returns the key if it does, otherwise none. The result in the some case is guaranteed to be pointer equal to the key in the map.

                                        Equations
                                        Instances For
                                          @[inline]
                                          def Std.ExtDTreeMap.getKey {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (h : a t) :
                                          α

                                          Retrieves the key from the mapping that matches a. Ensures that such a mapping exists by requiring a proof of a ∈ m. The result is guaranteed to be pointer equal to the key in the map.

                                          Equations
                                          Instances For
                                            @[inline]
                                            def Std.ExtDTreeMap.getKey! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (a : α) :
                                            α

                                            Checks if a mapping for the given key exists and returns the key if it does, otherwise panics. If no panic occurs the result is guaranteed to be pointer equal to the key in the map.

                                            Equations
                                            Instances For
                                              @[inline]
                                              def Std.ExtDTreeMap.getKeyD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (a fallback : α) :
                                              α

                                              Checks if a mapping for the given key exists and returns the key if it does, otherwise fallback. If a mapping exists the result is guaranteed to be pointer equal to the key in the map.

                                              Equations
                                              Instances For
                                                @[inline]
                                                def Std.ExtDTreeMap.minEntry? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :
                                                Option ((a : α) × β a)

                                                Tries to retrieve the key-value pair with the smallest key in the tree map, returning none if the map is empty.

                                                Equations
                                                Instances For
                                                  @[inline]
                                                  def Std.ExtDTreeMap.minEntry {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ) :
                                                  (a : α) × β a

                                                  Given a proof that the tree map is not empty, retrieves the key-value pair with the smallest key.

                                                  Equations
                                                  Instances For
                                                    @[inline]
                                                    def Std.ExtDTreeMap.minEntry! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited ((a : α) × β a)] (t : ExtDTreeMap α β cmp) :
                                                    (a : α) × β a

                                                    Tries to retrieve the key-value pair with the smallest key in the tree map, panicking if the map is empty.

                                                    Equations
                                                    Instances For
                                                      @[inline]
                                                      def Std.ExtDTreeMap.minEntryD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : (a : α) × β a) :
                                                      (a : α) × β a

                                                      Tries to retrieve the key-value pair with the smallest key in the tree map, returning fallback if the tree map is empty.

                                                      Equations
                                                      Instances For
                                                        @[inline]
                                                        def Std.ExtDTreeMap.maxEntry? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :
                                                        Option ((a : α) × β a)

                                                        Tries to retrieve the key-value pair with the largest key in the tree map, returning none if the map is empty.

                                                        Equations
                                                        Instances For
                                                          @[inline]
                                                          def Std.ExtDTreeMap.maxEntry {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ) :
                                                          (a : α) × β a

                                                          Given a proof that the tree map is not empty, retrieves the key-value pair with the largest key.

                                                          Equations
                                                          Instances For
                                                            @[inline]
                                                            def Std.ExtDTreeMap.maxEntry! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited ((a : α) × β a)] (t : ExtDTreeMap α β cmp) :
                                                            (a : α) × β a

                                                            Tries to retrieve the key-value pair with the largest key in the tree map, panicking if the map is empty.

                                                            Equations
                                                            Instances For
                                                              @[inline]
                                                              def Std.ExtDTreeMap.maxEntryD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : (a : α) × β a) :
                                                              (a : α) × β a

                                                              Tries to retrieve the key-value pair with the largest key in the tree map, returning fallback if the tree map is empty.

                                                              Equations
                                                              Instances For
                                                                @[inline]
                                                                def Std.ExtDTreeMap.minKey? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :

                                                                Tries to retrieve the smallest key in the tree map, returning none if the map is empty.

                                                                Equations
                                                                Instances For
                                                                  @[inline]
                                                                  def Std.ExtDTreeMap.minKey {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ) :
                                                                  α

                                                                  Given a proof that the tree map is not empty, retrieves the smallest key.

                                                                  Equations
                                                                  Instances For
                                                                    @[inline]
                                                                    def Std.ExtDTreeMap.minKey! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) :
                                                                    α

                                                                    Tries to retrieve the smallest key in the tree map, panicking if the map is empty.

                                                                    Equations
                                                                    Instances For
                                                                      @[inline]
                                                                      def Std.ExtDTreeMap.minKeyD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : α) :
                                                                      α

                                                                      Tries to retrieve the smallest key in the tree map, returning fallback if the tree map is empty.

                                                                      Equations
                                                                      Instances For
                                                                        @[inline]
                                                                        def Std.ExtDTreeMap.maxKey? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :

                                                                        Tries to retrieve the largest key in the tree map, returning none if the map is empty.

                                                                        Equations
                                                                        Instances For
                                                                          @[inline]
                                                                          def Std.ExtDTreeMap.maxKey {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (h : t ) :
                                                                          α

                                                                          Given a proof that the tree map is not empty, retrieves the largest key.

                                                                          Equations
                                                                          Instances For
                                                                            @[inline]
                                                                            def Std.ExtDTreeMap.maxKey! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) :
                                                                            α

                                                                            Tries to retrieve the largest key in the tree map, panicking if the map is empty.

                                                                            Equations
                                                                            Instances For
                                                                              @[inline]
                                                                              def Std.ExtDTreeMap.maxKeyD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (fallback : α) :
                                                                              α

                                                                              Tries to retrieve the largest key in the tree map, returning fallback if the tree map is empty.

                                                                              Equations
                                                                              Instances For
                                                                                @[inline]
                                                                                def Std.ExtDTreeMap.entryAtIdx? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) :
                                                                                Option ((a : α) × β a)

                                                                                Returns the key-value pair with the n-th smallest key, or none if n is at least t.size.

                                                                                Equations
                                                                                Instances For
                                                                                  @[inline]
                                                                                  def Std.ExtDTreeMap.entryAtIdx {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (h : n < t.size) :
                                                                                  (a : α) × β a

                                                                                  Returns the key-value pair with the n-th smallest key.

                                                                                  Equations
                                                                                  Instances For
                                                                                    @[inline]
                                                                                    def Std.ExtDTreeMap.entryAtIdx! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited ((a : α) × β a)] (t : ExtDTreeMap α β cmp) (n : Nat) :
                                                                                    (a : α) × β a

                                                                                    Returns the key-value pair with the n-th smallest key, or panics if n is at least t.size.

                                                                                    Equations
                                                                                    Instances For
                                                                                      @[inline]
                                                                                      def Std.ExtDTreeMap.entryAtIdxD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (fallback : (a : α) × β a) :
                                                                                      (a : α) × β a

                                                                                      Returns the key-value pair with the n-th smallest key, or fallback if n is at least t.size.

                                                                                      Equations
                                                                                      Instances For
                                                                                        @[inline]
                                                                                        def Std.ExtDTreeMap.keyAtIdx? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) :

                                                                                        Returns the n-th smallest key, or none if n is at least t.size.

                                                                                        Equations
                                                                                        Instances For
                                                                                          @[inline]
                                                                                          def Std.ExtDTreeMap.keyAtIdx {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (h : n < t.size) :
                                                                                          α

                                                                                          Returns the n-th smallest key.

                                                                                          Equations
                                                                                          Instances For
                                                                                            @[inline]
                                                                                            def Std.ExtDTreeMap.keyAtIdx! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (n : Nat) :
                                                                                            α

                                                                                            Returns the n-th smallest key, or panics if n is at least t.size.

                                                                                            Equations
                                                                                            Instances For
                                                                                              @[inline]
                                                                                              def Std.ExtDTreeMap.keyAtIdxD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (n : Nat) (fallback : α) :
                                                                                              α

                                                                                              Returns the n-th smallest key, or fallback if n is at least t.size.

                                                                                              Equations
                                                                                              Instances For
                                                                                                @[inline]
                                                                                                def Std.ExtDTreeMap.getEntryGE? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                Option ((a : α) × β a)

                                                                                                Tries to retrieve the key-value pair with the smallest key that is greater than or equal to the given key, returning none if no such pair exists.

                                                                                                Equations
                                                                                                Instances For
                                                                                                  @[inline]
                                                                                                  def Std.ExtDTreeMap.getEntryGT? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                  Option ((a : α) × β a)

                                                                                                  Tries to retrieve the key-value pair with the smallest key that is greater than the given key, returning none if no such pair exists.

                                                                                                  Equations
                                                                                                  Instances For
                                                                                                    @[inline]
                                                                                                    def Std.ExtDTreeMap.getEntryLE? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                    Option ((a : α) × β a)

                                                                                                    Tries to retrieve the key-value pair with the largest key that is less than or equal to the given key, returning none if no such pair exists.

                                                                                                    Equations
                                                                                                    Instances For
                                                                                                      @[inline]
                                                                                                      def Std.ExtDTreeMap.getEntryLT? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                      Option ((a : α) × β a)

                                                                                                      Tries to retrieve the key-value pair with the largest key that is less than the given key, returning none if no such pair exists.

                                                                                                      Equations
                                                                                                      Instances For
                                                                                                        @[inline]
                                                                                                        def Std.ExtDTreeMap.getEntryGE {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t (cmp a k).isGE = true) :
                                                                                                        (a : α) × β a

                                                                                                        Given a proof that such a mapping exists, retrieves the key-value pair with the smallest key that is greater than or equal to the given key.

                                                                                                        Equations
                                                                                                        Instances For
                                                                                                          @[inline]
                                                                                                          def Std.ExtDTreeMap.getEntryGT {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t cmp a k = Ordering.gt) :
                                                                                                          (a : α) × β a

                                                                                                          Given a proof that such a mapping exists, retrieves the key-value pair with the smallest key that is greater than the given key.

                                                                                                          Equations
                                                                                                          Instances For
                                                                                                            @[inline]
                                                                                                            def Std.ExtDTreeMap.getEntryLE {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t (cmp a k).isLE = true) :
                                                                                                            (a : α) × β a

                                                                                                            Given a proof that such a mapping exists, retrieves the key-value pair with the largest key that is less than or equal to the given key.

                                                                                                            Equations
                                                                                                            Instances For
                                                                                                              @[inline]
                                                                                                              def Std.ExtDTreeMap.getEntryLT {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t cmp a k = Ordering.lt) :
                                                                                                              (a : α) × β a

                                                                                                              Given a proof that such a mapping exists, retrieves the key-value pair with the largest key that is less than the given key.

                                                                                                              Equations
                                                                                                              Instances For
                                                                                                                @[inline]
                                                                                                                def Std.ExtDTreeMap.getEntryGE! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                (a : α) × β a

                                                                                                                Tries to retrieve the key-value pair with the smallest key that is greater than or equal to the given key, panicking if no such pair exists.

                                                                                                                Equations
                                                                                                                Instances For
                                                                                                                  @[inline]
                                                                                                                  def Std.ExtDTreeMap.getEntryGT! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                  (a : α) × β a

                                                                                                                  Tries to retrieve the key-value pair with the smallest key that is greater than the given key, panicking if no such pair exists.

                                                                                                                  Equations
                                                                                                                  Instances For
                                                                                                                    @[inline]
                                                                                                                    def Std.ExtDTreeMap.getEntryLE! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                    (a : α) × β a

                                                                                                                    Tries to retrieve the key-value pair with the largest key that is less than or equal to the given key, panicking if no such pair exists.

                                                                                                                    Equations
                                                                                                                    Instances For
                                                                                                                      @[inline]
                                                                                                                      def Std.ExtDTreeMap.getEntryLT! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited (Sigma β)] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                      (a : α) × β a

                                                                                                                      Tries to retrieve the key-value pair with the largest key that is less than the given key, panicking if no such pair exists.

                                                                                                                      Equations
                                                                                                                      Instances For
                                                                                                                        @[inline]
                                                                                                                        def Std.ExtDTreeMap.getEntryGED {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) :
                                                                                                                        (a : α) × β a

                                                                                                                        Tries to retrieve the key-value pair with the smallest key that is greater than or equal to the given key, returning fallback if no such pair exists.

                                                                                                                        Equations
                                                                                                                        Instances For
                                                                                                                          @[inline]
                                                                                                                          def Std.ExtDTreeMap.getEntryGTD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) :
                                                                                                                          (a : α) × β a

                                                                                                                          Tries to retrieve the key-value pair with the smallest key that is greater than the given key, returning fallback if no such pair exists.

                                                                                                                          Equations
                                                                                                                          Instances For
                                                                                                                            @[inline]
                                                                                                                            def Std.ExtDTreeMap.getEntryLED {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) :
                                                                                                                            (a : α) × β a

                                                                                                                            Tries to retrieve the key-value pair with the largest key that is less than or equal to the given key, returning fallback if no such pair exists.

                                                                                                                            Equations
                                                                                                                            Instances For
                                                                                                                              @[inline]
                                                                                                                              def Std.ExtDTreeMap.getEntryLTD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (fallback : Sigma β) :
                                                                                                                              (a : α) × β a

                                                                                                                              Tries to retrieve the key-value pair with the largest key that is less than the given key, returning fallback if no such pair exists.

                                                                                                                              Equations
                                                                                                                              Instances For
                                                                                                                                @[inline]
                                                                                                                                def Std.ExtDTreeMap.getKeyGE? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :

                                                                                                                                Tries to retrieve the smallest key that is greater than or equal to the given key, returning none if no such key exists.

                                                                                                                                Equations
                                                                                                                                Instances For
                                                                                                                                  @[inline]
                                                                                                                                  def Std.ExtDTreeMap.getKeyGT? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :

                                                                                                                                  Tries to retrieve the smallest key that is greater than the given key, returning none if no such key exists.

                                                                                                                                  Equations
                                                                                                                                  Instances For
                                                                                                                                    @[inline]
                                                                                                                                    def Std.ExtDTreeMap.getKeyLE? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :

                                                                                                                                    Tries to retrieve the largest key that is less than or equal to the given key, returning none if no such key exists.

                                                                                                                                    Equations
                                                                                                                                    Instances For
                                                                                                                                      @[inline]
                                                                                                                                      def Std.ExtDTreeMap.getKeyLT? {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) :

                                                                                                                                      Tries to retrieve the largest key that is less than the given key, returning none if no such key exists.

                                                                                                                                      Equations
                                                                                                                                      Instances For
                                                                                                                                        @[inline]
                                                                                                                                        def Std.ExtDTreeMap.getKeyGE {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t (cmp a k).isGE = true) :
                                                                                                                                        α

                                                                                                                                        Given a proof that such a mapping exists, retrieves the smallest key that is greater than or equal to the given key.

                                                                                                                                        Equations
                                                                                                                                        Instances For
                                                                                                                                          @[inline]
                                                                                                                                          def Std.ExtDTreeMap.getKeyGT {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t cmp a k = Ordering.gt) :
                                                                                                                                          α

                                                                                                                                          Given a proof that such a mapping exists, retrieves the smallest key that is greater than the given key.

                                                                                                                                          Equations
                                                                                                                                          Instances For
                                                                                                                                            @[inline]
                                                                                                                                            def Std.ExtDTreeMap.getKeyLE {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t (cmp a k).isLE = true) :
                                                                                                                                            α

                                                                                                                                            Given a proof that such a mapping exists, retrieves the largest key that is less than or equal to the given key.

                                                                                                                                            Equations
                                                                                                                                            Instances For
                                                                                                                                              @[inline]
                                                                                                                                              def Std.ExtDTreeMap.getKeyLT {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k : α) (h : (a : α), a t cmp a k = Ordering.lt) :
                                                                                                                                              α

                                                                                                                                              Given a proof that such a mapping exists, retrieves the largest key that is less than the given key.

                                                                                                                                              Equations
                                                                                                                                              Instances For
                                                                                                                                                @[inline]
                                                                                                                                                def Std.ExtDTreeMap.getKeyGE! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                                                α

                                                                                                                                                Tries to retrieve the smallest key that is greater than or equal to the given key, panicking if no such key exists.

                                                                                                                                                Equations
                                                                                                                                                Instances For
                                                                                                                                                  @[inline]
                                                                                                                                                  def Std.ExtDTreeMap.getKeyGT! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                                                  α

                                                                                                                                                  Tries to retrieve the smallest key that is greater than the given key, panicking if no such key exists.

                                                                                                                                                  Equations
                                                                                                                                                  Instances For
                                                                                                                                                    @[inline]
                                                                                                                                                    def Std.ExtDTreeMap.getKeyLE! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                                                    α

                                                                                                                                                    Tries to retrieve the largest key that is less than or equal to the given key, panicking if no such key exists.

                                                                                                                                                    Equations
                                                                                                                                                    Instances For
                                                                                                                                                      @[inline]
                                                                                                                                                      def Std.ExtDTreeMap.getKeyLT! {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Inhabited α] (t : ExtDTreeMap α β cmp) (k : α) :
                                                                                                                                                      α

                                                                                                                                                      Tries to retrieve the largest key that is less than the given key, panicking if no such key exists.

                                                                                                                                                      Equations
                                                                                                                                                      Instances For
                                                                                                                                                        @[inline]
                                                                                                                                                        def Std.ExtDTreeMap.getKeyGED {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k fallback : α) :
                                                                                                                                                        α

                                                                                                                                                        Tries to retrieve the smallest key that is greater than or equal to the given key, returning fallback if no such key exists.

                                                                                                                                                        Equations
                                                                                                                                                        Instances For
                                                                                                                                                          @[inline]
                                                                                                                                                          def Std.ExtDTreeMap.getKeyGTD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k fallback : α) :
                                                                                                                                                          α

                                                                                                                                                          Tries to retrieve the smallest key that is greater than the given key, returning fallback if no such key exists.

                                                                                                                                                          Equations
                                                                                                                                                          Instances For
                                                                                                                                                            @[inline]
                                                                                                                                                            def Std.ExtDTreeMap.getKeyLED {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k fallback : α) :
                                                                                                                                                            α

                                                                                                                                                            Tries to retrieve the largest key that is less than or equal to the given key, returning fallback if no such key exists.

                                                                                                                                                            Equations
                                                                                                                                                            Instances For
                                                                                                                                                              @[inline]
                                                                                                                                                              def Std.ExtDTreeMap.getKeyLTD {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (k fallback : α) :
                                                                                                                                                              α

                                                                                                                                                              Tries to retrieve the largest key that is less than the given key, returning fallback if no such key exists.

                                                                                                                                                              Equations
                                                                                                                                                              Instances For
                                                                                                                                                                @[inline]
                                                                                                                                                                def Std.ExtDTreeMap.Const.getThenInsertIfNew? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (a : α) (b : β) :
                                                                                                                                                                Option β × ExtDTreeMap α (fun (x : α) => β) cmp

                                                                                                                                                                Checks whether a key is present in a map, returning the associated value, and inserts a value for the key if it was not found.

                                                                                                                                                                If the returned value is some v, then the returned map is unaltered. If it is none, then the returned map has a new value inserted.

                                                                                                                                                                Equivalent to (but potentially faster than) calling get? followed by insertIfNew.

                                                                                                                                                                Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                                                                                                                                                Equations
                                                                                                                                                                • One or more equations did not get rendered due to their size.
                                                                                                                                                                Instances For
                                                                                                                                                                  @[inline]
                                                                                                                                                                  def Std.ExtDTreeMap.Const.get? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (a : α) :

                                                                                                                                                                  Tries to retrieve the mapping for the given key, returning none if no such mapping is present.

                                                                                                                                                                  Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                                                                                                                                                  Equations
                                                                                                                                                                  Instances For
                                                                                                                                                                    @[inline]
                                                                                                                                                                    def Std.ExtDTreeMap.Const.get {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (a : α) (h : a t) :
                                                                                                                                                                    β

                                                                                                                                                                    Given a proof that a mapping for the given key is present, retrieves the mapping for the given key.

                                                                                                                                                                    Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                                                                                                                                                    Equations
                                                                                                                                                                    Instances For
                                                                                                                                                                      @[inline]
                                                                                                                                                                      def Std.ExtDTreeMap.Const.get! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (a : α) [Inhabited β] :
                                                                                                                                                                      β

                                                                                                                                                                      Tries to retrieve the mapping for the given key, panicking if no such mapping is present.

                                                                                                                                                                      Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                                                                                                                                                      Equations
                                                                                                                                                                      Instances For
                                                                                                                                                                        @[inline]
                                                                                                                                                                        def Std.ExtDTreeMap.Const.getD {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (a : α) (fallback : β) :
                                                                                                                                                                        β

                                                                                                                                                                        Tries to retrieve the mapping for the given key, returning fallback if no such mapping is present.

                                                                                                                                                                        Uses the LawfulEqCmp instance to cast the retrieved value to the correct type.

                                                                                                                                                                        Equations
                                                                                                                                                                        Instances For
                                                                                                                                                                          @[inline]
                                                                                                                                                                          def Std.ExtDTreeMap.Const.minEntry? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                          Option (α × β)

                                                                                                                                                                          Tries to retrieve the key-value pair with the smallest key in the tree map, returning none if the map is empty.

                                                                                                                                                                          Equations
                                                                                                                                                                          Instances For
                                                                                                                                                                            @[inline]
                                                                                                                                                                            def Std.ExtDTreeMap.Const.minEntry {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (h : t ) :
                                                                                                                                                                            α × β

                                                                                                                                                                            Given a proof that the tree map is not empty, retrieves the key-value pair with the smallest key.

                                                                                                                                                                            Equations
                                                                                                                                                                            Instances For
                                                                                                                                                                              @[inline]
                                                                                                                                                                              def Std.ExtDTreeMap.Const.minEntry! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                              α × β

                                                                                                                                                                              Tries to retrieve the key-value pair with the smallest key in the tree map, panicking if the map is empty.

                                                                                                                                                                              Equations
                                                                                                                                                                              Instances For
                                                                                                                                                                                @[inline]
                                                                                                                                                                                def Std.ExtDTreeMap.Const.minEntryD {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (fallback : α × β) :
                                                                                                                                                                                α × β

                                                                                                                                                                                Tries to retrieve the key-value pair with the smallest key in the tree map, returning fallback if the tree map is empty.

                                                                                                                                                                                Equations
                                                                                                                                                                                Instances For
                                                                                                                                                                                  @[inline]
                                                                                                                                                                                  def Std.ExtDTreeMap.Const.maxEntry? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                                  Option (α × β)

                                                                                                                                                                                  Tries to retrieve the key-value pair with the largest key in the tree map, returning none if the map is empty.

                                                                                                                                                                                  Equations
                                                                                                                                                                                  Instances For
                                                                                                                                                                                    @[inline]
                                                                                                                                                                                    def Std.ExtDTreeMap.Const.maxEntry {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (h : t ) :
                                                                                                                                                                                    α × β

                                                                                                                                                                                    Given a proof that the tree map is not empty, retrieves the key-value pair with the largest key.

                                                                                                                                                                                    Equations
                                                                                                                                                                                    Instances For
                                                                                                                                                                                      @[inline]
                                                                                                                                                                                      def Std.ExtDTreeMap.Const.maxEntry! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                                      α × β

                                                                                                                                                                                      Tries to retrieve the key-value pair with the largest key in the tree map, panicking if the map is empty.

                                                                                                                                                                                      Equations
                                                                                                                                                                                      Instances For
                                                                                                                                                                                        @[inline]
                                                                                                                                                                                        def Std.ExtDTreeMap.Const.maxEntryD {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (fallback : α × β) :
                                                                                                                                                                                        α × β

                                                                                                                                                                                        Tries to retrieve the key-value pair with the largest key in the tree map, returning fallback if the tree map is empty.

                                                                                                                                                                                        Equations
                                                                                                                                                                                        Instances For
                                                                                                                                                                                          @[inline]
                                                                                                                                                                                          def Std.ExtDTreeMap.Const.entryAtIdx? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (n : Nat) :
                                                                                                                                                                                          Option (α × β)

                                                                                                                                                                                          Returns the key-value pair with the n-th smallest key, or none if n is at least t.size.

                                                                                                                                                                                          Equations
                                                                                                                                                                                          Instances For
                                                                                                                                                                                            @[inline]
                                                                                                                                                                                            def Std.ExtDTreeMap.Const.entryAtIdx {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (n : Nat) (h : n < t.size) :
                                                                                                                                                                                            α × β

                                                                                                                                                                                            Returns the key-value pair with the n-th smallest key.

                                                                                                                                                                                            Equations
                                                                                                                                                                                            Instances For
                                                                                                                                                                                              @[inline]
                                                                                                                                                                                              def Std.ExtDTreeMap.Const.entryAtIdx! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (n : Nat) :
                                                                                                                                                                                              α × β

                                                                                                                                                                                              Returns the key-value pair with the n-th smallest key, or panics if n is at least t.size.

                                                                                                                                                                                              Equations
                                                                                                                                                                                              Instances For
                                                                                                                                                                                                @[inline]
                                                                                                                                                                                                def Std.ExtDTreeMap.Const.entryAtIdxD {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (n : Nat) (fallback : α × β) :
                                                                                                                                                                                                α × β

                                                                                                                                                                                                Returns the key-value pair with the n-th smallest key, or fallback if n is at least t.size.

                                                                                                                                                                                                Equations
                                                                                                                                                                                                Instances For
                                                                                                                                                                                                  @[inline]
                                                                                                                                                                                                  def Std.ExtDTreeMap.Const.getEntryGE? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                  Option (α × β)

                                                                                                                                                                                                  Tries to retrieve the key-value pair with the smallest key that is greater than or equal to the given key, returning none if no such pair exists.

                                                                                                                                                                                                  Equations
                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                    @[inline]
                                                                                                                                                                                                    def Std.ExtDTreeMap.Const.getEntryGT? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                    Option (α × β)

                                                                                                                                                                                                    Tries to retrieve the key-value pair with the smallest key that is greater than the given key, returning none if no such pair exists.

                                                                                                                                                                                                    Equations
                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                      @[inline]
                                                                                                                                                                                                      def Std.ExtDTreeMap.Const.getEntryLE? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                      Option (α × β)

                                                                                                                                                                                                      Tries to retrieve the key-value pair with the largest key that is less than or equal to the given key, returning none if no such pair exists.

                                                                                                                                                                                                      Equations
                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                        @[inline]
                                                                                                                                                                                                        def Std.ExtDTreeMap.Const.getEntryLT? {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                        Option (α × β)

                                                                                                                                                                                                        Tries to retrieve the key-value pair with the largest key that is less than the given key, returning none if no such pair exists.

                                                                                                                                                                                                        Equations
                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                          @[inline]
                                                                                                                                                                                                          def Std.ExtDTreeMap.Const.getEntryGE {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (h : (a : α), a t (cmp a k).isGE = true) :
                                                                                                                                                                                                          α × β

                                                                                                                                                                                                          Given a proof that such a mapping exists, retrieves the key-value pair with the smallest key that is greater than or equal to the given key.

                                                                                                                                                                                                          Equations
                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                            @[inline]
                                                                                                                                                                                                            def Std.ExtDTreeMap.Const.getEntryGT {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (h : (a : α), a t cmp a k = Ordering.gt) :
                                                                                                                                                                                                            α × β

                                                                                                                                                                                                            Given a proof that such a mapping exists, retrieves the key-value pair with the smallest key that is greater than the given key.

                                                                                                                                                                                                            Equations
                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                              @[inline]
                                                                                                                                                                                                              def Std.ExtDTreeMap.Const.getEntryLE {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (h : (a : α), a t (cmp a k).isLE = true) :
                                                                                                                                                                                                              α × β

                                                                                                                                                                                                              Given a proof that such a mapping exists, retrieves the key-value pair with the largest key that is less than or equal to the given key.

                                                                                                                                                                                                              Equations
                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                @[inline]
                                                                                                                                                                                                                def Std.ExtDTreeMap.Const.getEntryLT {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (h : (a : α), a t cmp a k = Ordering.lt) :
                                                                                                                                                                                                                α × β

                                                                                                                                                                                                                Given a proof that such a mapping exists, retrieves the key-value pair with the largest key that is less than the given key.

                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                  @[inline]
                                                                                                                                                                                                                  def Std.ExtDTreeMap.Const.getEntryGE! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                                  α × β

                                                                                                                                                                                                                  Tries to retrieve the key-value pair with the smallest key that is greater than or equal to the given key, panicking if no such pair exists.

                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                    @[inline]
                                                                                                                                                                                                                    def Std.ExtDTreeMap.Const.getEntryGT! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                                    α × β

                                                                                                                                                                                                                    Tries to retrieve the key-value pair with the smallest key that is greater than the given key, panicking if no such pair exists.

                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                      @[inline]
                                                                                                                                                                                                                      def Std.ExtDTreeMap.Const.getEntryLE! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                                      α × β

                                                                                                                                                                                                                      Tries to retrieve the key-value pair with the largest key that is less than or equal to the given key, panicking if no such pair exists.

                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                        @[inline]
                                                                                                                                                                                                                        def Std.ExtDTreeMap.Const.getEntryLT! {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] [Inhabited (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) :
                                                                                                                                                                                                                        α × β

                                                                                                                                                                                                                        Tries to retrieve the key-value pair with the largest key that is less than the given key, panicking if no such pair exists.

                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                          @[inline]
                                                                                                                                                                                                                          def Std.ExtDTreeMap.Const.getEntryGED {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (fallback : α × β) :
                                                                                                                                                                                                                          α × β

                                                                                                                                                                                                                          Tries to retrieve the key-value pair with the smallest key that is greater than or equal to the given key, returning fallback if no such pair exists.

                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                            @[inline]
                                                                                                                                                                                                                            def Std.ExtDTreeMap.Const.getEntryGTD {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (fallback : α × β) :
                                                                                                                                                                                                                            α × β

                                                                                                                                                                                                                            Tries to retrieve the key-value pair with the smallest key that is greater than the given key, returning fallback if no such pair exists.

                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                              @[inline]
                                                                                                                                                                                                                              def Std.ExtDTreeMap.Const.getEntryLED {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (fallback : α × β) :
                                                                                                                                                                                                                              α × β

                                                                                                                                                                                                                              Tries to retrieve the key-value pair with the largest key that is less than or equal to the given key, returning fallback if no such pair exists.

                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                @[inline]
                                                                                                                                                                                                                                def Std.ExtDTreeMap.Const.getEntryLTD {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (k : α) (fallback : α × β) :
                                                                                                                                                                                                                                α × β

                                                                                                                                                                                                                                Tries to retrieve the key-value pair with the largest key that is less than the given key, returning fallback if no such pair exists.

                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                  @[inline]
                                                                                                                                                                                                                                  def Std.ExtDTreeMap.filter {α : Type u} {β : αType v} {cmp : ααOrdering} (f : (a : α) → β aBool) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                  ExtDTreeMap α β cmp

                                                                                                                                                                                                                                  Removes all mappings of the map for which the given function returns false.

                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                    @[inline]
                                                                                                                                                                                                                                    def Std.ExtDTreeMap.filterMap {α : Type u} {β : αType v} {γ : αType w} {cmp : ααOrdering} (f : (a : α) → β aOption (γ a)) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                    ExtDTreeMap α γ cmp

                                                                                                                                                                                                                                    Updates the values of the map by applying the given function to all mappings, keeping only those mappings where the function returns some value.

                                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                                      @[inline]
                                                                                                                                                                                                                                      def Std.ExtDTreeMap.map {α : Type u} {β : αType v} {γ : αType w} {cmp : ααOrdering} (f : (a : α) → β aγ a) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                      ExtDTreeMap α γ cmp

                                                                                                                                                                                                                                      Updates the values of the map by applying the given function to all mappings.

                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                                        @[inline]
                                                                                                                                                                                                                                        def Std.ExtDTreeMap.foldlM {α : Type u} {β : αType v} {cmp : ααOrdering} {δ : Type w} {m : Type w → Type w₂} [Monad m] [LawfulMonad m] [TransCmp cmp] (f : δ(a : α) → β am δ) (init : δ) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                        m δ

                                                                                                                                                                                                                                        Folds the given monadic function over the mappings in the map in ascending order.

                                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                                          @[inline]
                                                                                                                                                                                                                                          def Std.ExtDTreeMap.foldl {α : Type u} {β : αType v} {cmp : ααOrdering} {δ : Type w} [TransCmp cmp] (f : δ(a : α) → β aδ) (init : δ) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                          δ

                                                                                                                                                                                                                                          Folds the given function over the mappings in the map in ascending order.

                                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                                            @[inline]
                                                                                                                                                                                                                                            def Std.ExtDTreeMap.foldrM {α : Type u} {β : αType v} {cmp : ααOrdering} {δ : Type w} {m : Type w → Type w₂} [Monad m] [LawfulMonad m] [TransCmp cmp] (f : (a : α) → β aδm δ) (init : δ) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                            m δ

                                                                                                                                                                                                                                            Folds the given monadic function over the mappings in the map in descending order.

                                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                                              @[inline]
                                                                                                                                                                                                                                              def Std.ExtDTreeMap.foldr {α : Type u} {β : αType v} {cmp : ααOrdering} {δ : Type w} [TransCmp cmp] (f : (a : α) → β aδδ) (init : δ) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                              δ

                                                                                                                                                                                                                                              Folds the given function over the mappings in the map in descending order.

                                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                                @[inline]
                                                                                                                                                                                                                                                def Std.ExtDTreeMap.partition {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (f : (a : α) → β aBool) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                                ExtDTreeMap α β cmp × ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                Partitions a tree map into two tree maps based on a predicate.

                                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                                • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                                  @[inline]
                                                                                                                                                                                                                                                  def Std.ExtDTreeMap.forM {α : Type u} {β : αType v} {cmp : ααOrdering} {m : Type w → Type w₂} [Monad m] [LawfulMonad m] [TransCmp cmp] (f : (a : α) → β am PUnit) (t : ExtDTreeMap α β cmp) :

                                                                                                                                                                                                                                                  Carries out a monadic action on each mapping in the tree map in ascending order.

                                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                                    @[inline]
                                                                                                                                                                                                                                                    def Std.ExtDTreeMap.forIn {α : Type u} {β : αType v} {cmp : ααOrdering} {δ : Type w} {m : Type w → Type w₂} [Monad m] [LawfulMonad m] [TransCmp cmp] (f : (a : α) → β aδm (ForInStep δ)) (init : δ) (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                                    m δ

                                                                                                                                                                                                                                                    Support for the for loop construct in do blocks. Iteration happens in ascending order.

                                                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                                                      instance Std.ExtDTreeMap.instForMSigmaOfTransCmpOfLawfulMonad {α : Type u} {β : αType v} {cmp : ααOrdering} {m : Type w → Type w₂} [TransCmp cmp] [inst : Monad m] [LawfulMonad m] :
                                                                                                                                                                                                                                                      ForM m (ExtDTreeMap α β cmp) ((a : α) × β a)
                                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                                      • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                      instance Std.ExtDTreeMap.instForInSigmaOfTransCmpOfLawfulMonad {α : Type u} {β : αType v} {cmp : ααOrdering} {m : Type w → Type w₂} [TransCmp cmp] [inst : Monad m] [LawfulMonad m] :
                                                                                                                                                                                                                                                      ForIn m (ExtDTreeMap α β cmp) ((a : α) × β a)
                                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                                      • One or more equations did not get rendered due to their size.

                                                                                                                                                                                                                                                      We do not define ForM and ForIn instances that are specialized to constant β. Instead, we define uncurried versions of forM and forIn that will be used in the Const lemmas and to define the ForM and ForIn instances for ExtDTreeMap.

                                                                                                                                                                                                                                                      @[inline]
                                                                                                                                                                                                                                                      def Std.ExtDTreeMap.Const.forMUncurried {α : Type u} {cmp : ααOrdering} {m : Type w → Type w₂} [Monad m] [LawfulMonad m] {β : Type v} [TransCmp cmp] (f : α × βm PUnit) (t : ExtDTreeMap α (fun (x : α) => β) cmp) :

                                                                                                                                                                                                                                                      Carries out a monadic action on each mapping in the tree map in ascending order.

                                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                                                        @[inline]
                                                                                                                                                                                                                                                        def Std.ExtDTreeMap.Const.forInUncurried {α : Type u} {cmp : ααOrdering} {δ : Type w} {m : Type w → Type w₂} [Monad m] [LawfulMonad m] {β : Type v} [TransCmp cmp] (f : α × βδm (ForInStep δ)) (init : δ) (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                                                                                                        m δ

                                                                                                                                                                                                                                                        Support for the for loop construct in do blocks. Iteration happens in ascending order.

                                                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                                                          @[inline]
                                                                                                                                                                                                                                                          def Std.ExtDTreeMap.any {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (p : (a : α) → β aBool) :

                                                                                                                                                                                                                                                          Check if any element satisfes the predicate, short-circuiting if a predicate fails.

                                                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                                                            @[inline]
                                                                                                                                                                                                                                                            def Std.ExtDTreeMap.all {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) (p : (a : α) → β aBool) :

                                                                                                                                                                                                                                                            Check if all elements satisfy the predicate, short-circuiting if a predicate fails.

                                                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                                                              @[inline]
                                                                                                                                                                                                                                                              def Std.ExtDTreeMap.keys {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                                              List α

                                                                                                                                                                                                                                                              Returns a list of all keys present in the tree map in ascending order.

                                                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                                                @[inline]
                                                                                                                                                                                                                                                                def Std.ExtDTreeMap.keysArray {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :

                                                                                                                                                                                                                                                                Returns an array of all keys present in the tree map in ascending order.

                                                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                                                  @[inline]
                                                                                                                                                                                                                                                                  def Std.ExtDTreeMap.values {α : Type u} {cmp : ααOrdering} [TransCmp cmp] {β : Type v} (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                                                                                                                  List β

                                                                                                                                                                                                                                                                  Returns a list of all values present in the tree map in ascending order.

                                                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                                                    @[inline]
                                                                                                                                                                                                                                                                    def Std.ExtDTreeMap.valuesArray {α : Type u} {cmp : ααOrdering} [TransCmp cmp] {β : Type v} (t : ExtDTreeMap α (fun (x : α) => β) cmp) :

                                                                                                                                                                                                                                                                    Returns an array of all values present in the tree map in ascending order.

                                                                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                                                                      @[inline]
                                                                                                                                                                                                                                                                      def Std.ExtDTreeMap.toList {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                                                      List ((a : α) × β a)

                                                                                                                                                                                                                                                                      Transforms the tree map into a list of mappings in ascending order.

                                                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                                                                        @[inline]
                                                                                                                                                                                                                                                                        def Std.ExtDTreeMap.ofList {α : Type u} {β : αType v} (l : List ((a : α) × β a)) (cmp : ααOrdering := by exact compare) :
                                                                                                                                                                                                                                                                        ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                                        Transforms a list of mappings into a tree map.

                                                                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                                                                          @[inline]
                                                                                                                                                                                                                                                                          def Std.ExtDTreeMap.toArray {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] (t : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                                                          Array ((a : α) × β a)

                                                                                                                                                                                                                                                                          Transforms the tree map into a list of mappings in ascending order.

                                                                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                                                                            @[inline]
                                                                                                                                                                                                                                                                            def Std.ExtDTreeMap.ofArray {α : Type u} {β : αType v} (a : Array ((a : α) × β a)) (cmp : ααOrdering := by exact compare) :
                                                                                                                                                                                                                                                                            ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                                            Transforms an array of mappings into a tree map.

                                                                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                                                                              @[inline]
                                                                                                                                                                                                                                                                              def Std.ExtDTreeMap.modify {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (f : β aβ a) :
                                                                                                                                                                                                                                                                              ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                                              Modifies in place the value associated with a given key.

                                                                                                                                                                                                                                                                              This function ensures that the value is used linearly.

                                                                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                                                                @[inline]
                                                                                                                                                                                                                                                                                def Std.ExtDTreeMap.alter {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (t : ExtDTreeMap α β cmp) (a : α) (f : Option (β a)Option (β a)) :
                                                                                                                                                                                                                                                                                ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                                                Modifies in place the value associated with a given key, allowing creating new values and deleting values via an Option valued replacement function.

                                                                                                                                                                                                                                                                                This function ensures that the value is used linearly.

                                                                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                                                                  @[inline]
                                                                                                                                                                                                                                                                                  def Std.ExtDTreeMap.mergeWith {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [LawfulEqCmp cmp] (mergeFn : (a : α) → β aβ aβ a) (t₁ t₂ : ExtDTreeMap α β cmp) :
                                                                                                                                                                                                                                                                                  ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                                                  Returns a map that contains all mappings of t₁ and t₂. In case that both maps contain the same key k with respect to cmp, the provided function is used to determine the new value from the respective values in t₁ and t₂.

                                                                                                                                                                                                                                                                                  This function ensures that t₁ is used linearly. It also uses the individual values in t₁ linearly if the merge function uses the second argument (i.e. the first of type β a) linearly. Hence, as long as t₁ is unshared, the performance characteristics follow the following imperative description: Iterate over all mappings in t₂, inserting them into t₁ if t₁ does not contain a conflicting mapping yet. If t₁ does contain a conflicting mapping, use the given merge function to merge the mapping in t₂ into the mapping in t₁. Then return t₁.

                                                                                                                                                                                                                                                                                  Hence, the runtime of this method scales logarithmically in the size of t₁ and linearly in the size of t₂ as long as t₁ is unshared.

                                                                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                                                                    @[inline]
                                                                                                                                                                                                                                                                                    def Std.ExtDTreeMap.Const.toList {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                                                                                                                                    List (α × β)

                                                                                                                                                                                                                                                                                    Transforms the tree map into a list of mappings in ascending order.

                                                                                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                                                                                      @[inline]
                                                                                                                                                                                                                                                                                      def Std.ExtDTreeMap.Const.ofList {α : Type u} {β : Type v} (l : List (α × β)) (cmp : ααOrdering := by exact compare) :
                                                                                                                                                                                                                                                                                      ExtDTreeMap α (fun (x : α) => β) cmp

                                                                                                                                                                                                                                                                                      Transforms a list of mappings into a tree map.

                                                                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                                                                                        @[inline]
                                                                                                                                                                                                                                                                                        def Std.ExtDTreeMap.Const.toArray {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                                                                                                                                        Array (α × β)

                                                                                                                                                                                                                                                                                        Transforms the tree map into a list of mappings in ascending order.

                                                                                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                                                                                          @[inline]
                                                                                                                                                                                                                                                                                          def Std.ExtDTreeMap.Const.ofArray {α : Type u} {β : Type v} (a : Array (α × β)) (cmp : ααOrdering := by exact compare) :
                                                                                                                                                                                                                                                                                          ExtDTreeMap α (fun (x : α) => β) cmp

                                                                                                                                                                                                                                                                                          Transforms a list of mappings into a tree map.

                                                                                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                                                                                            @[inline]
                                                                                                                                                                                                                                                                                            def Std.ExtDTreeMap.Const.unitOfList {α : Type u} (l : List α) (cmp : ααOrdering := by exact compare) :
                                                                                                                                                                                                                                                                                            ExtDTreeMap α (fun (x : α) => Unit) cmp

                                                                                                                                                                                                                                                                                            Transforms a list of keys into a tree map.

                                                                                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                                                                                              @[inline]
                                                                                                                                                                                                                                                                                              def Std.ExtDTreeMap.Const.unitOfArray {α : Type u} (a : Array α) (cmp : ααOrdering := by exact compare) :
                                                                                                                                                                                                                                                                                              ExtDTreeMap α (fun (x : α) => Unit) cmp

                                                                                                                                                                                                                                                                                              Transforms an array of keys into a tree map.

                                                                                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                                                                                @[inline]
                                                                                                                                                                                                                                                                                                def Std.ExtDTreeMap.Const.modify {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (a : α) (f : ββ) :
                                                                                                                                                                                                                                                                                                ExtDTreeMap α (fun (x : α) => β) cmp

                                                                                                                                                                                                                                                                                                Modifies in place the value associated with a given key.

                                                                                                                                                                                                                                                                                                This function ensures that the value is used linearly.

                                                                                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                                                                                  @[inline]
                                                                                                                                                                                                                                                                                                  def Std.ExtDTreeMap.Const.alter {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (a : α) (f : Option βOption β) :
                                                                                                                                                                                                                                                                                                  ExtDTreeMap α (fun (x : α) => β) cmp

                                                                                                                                                                                                                                                                                                  Modifies in place the value associated with a given key, allowing creating new values and deleting values via an Option valued replacement function.

                                                                                                                                                                                                                                                                                                  This function ensures that the value is used linearly.

                                                                                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                                                                                    @[inline]
                                                                                                                                                                                                                                                                                                    def Std.ExtDTreeMap.Const.mergeWith {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] (mergeFn : αβββ) (t₁ t₂ : ExtDTreeMap α (fun (x : α) => β) cmp) :
                                                                                                                                                                                                                                                                                                    ExtDTreeMap α (fun (x : α) => β) cmp

                                                                                                                                                                                                                                                                                                    Returns a map that contains all mappings of t₁ and t₂. In case that both maps contain the same key k with respect to cmp, the provided function is used to determine the new value from the respective values in t₁ and t₂.

                                                                                                                                                                                                                                                                                                    This function ensures that t₁ is used linearly. It also uses the individual values in t₁ linearly if the merge function uses the second argument (i.e. the first of type β a) linearly. Hence, as long as t₁ is unshared, the performance characteristics follow the following imperative description: Iterate over all mappings in t₂, inserting them into t₁ if t₁ does not contain a conflicting mapping yet. If t₁ does contain a conflicting mapping, use the given merge function to merge the mapping in t₂ into the mapping in t₁. Then return t₁.

                                                                                                                                                                                                                                                                                                    Hence, the runtime of this method scales logarithmically in the size of t₁ and linearly in the size of t₂ as long as t₁ is unshared.

                                                                                                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                                                                                                    • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                                                                                                      @[inline]
                                                                                                                                                                                                                                                                                                      def Std.ExtDTreeMap.insertMany {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] {ρ : Type u_1} [ForIn Id ρ ((a : α) × β a)] (t : ExtDTreeMap α β cmp) (l : ρ) :
                                                                                                                                                                                                                                                                                                      ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                                                                      Inserts multiple mappings into the tree map by iterating over the given collection and calling insert. If the same key appears multiple times, the last occurrence takes precedence.

                                                                                                                                                                                                                                                                                                      Note: this precedence behavior is true for TreeMap, DTreeMap, TreeMap.Raw and DTreeMap.Raw. The insertMany function on TreeSet and TreeSet.Raw behaves differently: it will prefer the first appearance.

                                                                                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                                                                                      • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                                                                                                        @[inline]
                                                                                                                                                                                                                                                                                                        def Std.ExtDTreeMap.eraseMany {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] {ρ : Type u_1} [ForIn Id ρ α] (t : ExtDTreeMap α β cmp) (l : ρ) :
                                                                                                                                                                                                                                                                                                        ExtDTreeMap α β cmp

                                                                                                                                                                                                                                                                                                        Erases multiple mappings from the tree map by iterating over the given collection and calling erase.

                                                                                                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                                                                                                        • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                                                                                                          @[inline]
                                                                                                                                                                                                                                                                                                          def Std.ExtDTreeMap.Const.insertMany {α : Type u} {cmp : ααOrdering} {β : Type v} [TransCmp cmp] {ρ : Type u_1} [ForIn Id ρ (α × β)] (t : ExtDTreeMap α (fun (x : α) => β) cmp) (l : ρ) :
                                                                                                                                                                                                                                                                                                          ExtDTreeMap α (fun (x : α) => β) cmp

                                                                                                                                                                                                                                                                                                          Inserts multiple mappings into the tree map by iterating over the given collection and calling insert. If the same key appears multiple times, the last occurrence takes precedence.

                                                                                                                                                                                                                                                                                                          Note: this precedence behavior is true for TreeMap, DTreeMap, TreeMap.Raw and DTreeMap.Raw. The insertMany function on TreeSet and TreeSet.Raw behaves differently: it will prefer the first appearance.

                                                                                                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                                                                                                          • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                                                                                                            @[inline]
                                                                                                                                                                                                                                                                                                            def Std.ExtDTreeMap.Const.insertManyIfNewUnit {α : Type u} {cmp : ααOrdering} [TransCmp cmp] {ρ : Type u_1} [ForIn Id ρ α] (t : ExtDTreeMap α (fun (x : α) => Unit) cmp) (l : ρ) :
                                                                                                                                                                                                                                                                                                            ExtDTreeMap α (fun (x : α) => Unit) cmp

                                                                                                                                                                                                                                                                                                            Inserts multiple elements into the tree map by iterating over the given collection and calling insertIfNew. If the same key appears multiple times, the first occurrence takes precedence.

                                                                                                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                                                                                                            • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                                                                                                              instance Std.ExtDTreeMap.instReprOfTransCmp {α : Type u} {β : αType v} {cmp : ααOrdering} [TransCmp cmp] [Repr α] [(a : α) → Repr (β a)] :
                                                                                                                                                                                                                                                                                                              Repr (ExtDTreeMap α β cmp)
                                                                                                                                                                                                                                                                                                              Equations