container/Fixed_Capacity_Array.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature container.Fixed_Capacity_Array
#
# -----------------------------------------------------------------------

# Fixed_Capacity_Array -- a mutable dynamic array with fixed internal capacity
#
# It is created with a fixed internal capacity and never reallocates.
# Elements can be added to and removed from the end in worst-case O(1) time,
# rather than amortized O(1) time.
# The length may vary, but it must never exceed the internal capacity.
#
module:public Fixed_Capacity_Array(

  # the mutate effect
  #
  public LM type : mutate,

  # element type
  #
  public T type,

  # contents of the array
  #
  data LM.new (LM.array T),

  # length -- number of elements in data that are in use,
  #           i.e. store actual elements
  len LM.new i64

) ref : Dynamic_Array LM T data len
is


  public redef may_shrink bool => false

  public redef may_grow   bool => false



  # initialize a Fixed_Capacity_Array
  #
  public redef type.new
   (
    # length of the array to create, it is also the maximum capacity
    length i64,

    # function to create initial values for elements
    init i64->T

   ) container.Dynamic_Array LM T
  =>
    d := container.Fixed_Capacity_Array LM T .empty length
    for i in i64.zero..(length-1) do
      d.add (init i)
    d


  # initialize a Fixed_Capacity_Array from a Sequence, capacity is set to the length of the Sequence
  #
  public redef type.from_sequence(s Sequence T) container.Dynamic_Array LM T =>
    arr := s.as_array_backed

    d := container.Fixed_Capacity_Array LM T (LM.env.new (LM.array T .empty arr.count.as_i64)) (LM.env.new i64 0)

    for e in arr do d.add e

    d


  # initialize an empty Fixed_Capacity_Array of type T with default capacity of `min_length`
  #
  public redef type.empty container.Dynamic_Array LM T =>
    container.Fixed_Capacity_Array LM T (LM.env.new (LM.array T .empty min_length)) (LM.env.new i64 0)


  # initialize an empty Fixed_Capacity_Array of type T with the given capacity
  #
  public redef type.empty(capacity i64) container.Dynamic_Array LM T =>
    container.Fixed_Capacity_Array LM T (LM.env.new (LM.array T .empty capacity)) (LM.env.new i64 0)