<commit_before>%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%%     http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%
%% Copyright (C) 2006-2016 <NAME> and Ericsson AB
%%
%% @author <NAME> <<EMAIL>>
%% @author <NAME> <<EMAIL>>
%%
%% @doc Functional, extendible arrays. Arrays can have fixed size, or
%% can grow automatically as needed. A default value is used for entries
%% that have not been explicitly set.
%%
%% Arrays uses <b>zero</b> based indexing. This is a deliberate design
%% choice and differs from other erlang datastructures, e.g. tuples. 
%%
%% Unless specified by the user when the array is created, the default
%% value is the atom `undefined'. There is no difference between an
%% unset entry and an entry which has been explicitly set to the same
%% value as the default one (cf. {@link reset/2}). If you need to
%% differentiate between unset and set entries, you must make sure that
%% the default value cannot be confused with the values of set entries.
%%
%% The array never shrinks automatically; if an index `I' has been used
%% successfully to set an entry, all indices in the range [0,`I'] will
%% stay accessible unless the array size is explicitly changed by
%% calling {@link resize/2}.
%% 
%% Examples:
%% ```
%% %% Create a fixed-size array with entries 0-9 set to 'undefined'
%% A0 = array:new(10).
%% 10 = array:size(A0).
%%
%% %% Create an extendible array and set entry 17 to 'true',
%% %% causing the array to grow automatically
%% A1 = array:set(17, true, array:new()).
%% 18 = array:size(A1).
%%
%% %% Read back a stored value
%% true = array:get(17, A1).
%%
%% %% Accessing an unset entry returns the default value
%% undefined = array:get(3, A1).
%%
%% %% Accessing an entry beyond the last set entry also returns the
%% %% default value, if the array does not have fixed size
%% undefined = array:get(18, A1).
%%
%% %% "sparse" functions ignore default-valued entries
%% A2 = array:set(4, false, A1).
%% [{4, false}, {17, true}] = array:sparse_to_orddict(A2).
%%
%% %% An extendible array can be made fixed-size later
%% A3 = array:fix(A2).
%%
%% %% A fixed-size array does not grow automatically and does not
%% %% allow accesses beyond the last set entry
%% {'EXIT',{badarg,_}} = (catch array:set(18, true, A3)).
%% {'EXIT',{badarg,_}} = (catch array:get(18, A3)).
%% '''

%% @type array(). A functional, extendible array. The representation is
%% not documented and is subject to change without notice. Note that
%% arrays cannot be directly compared for equality.

-module(array).

-export([new/0, new/1, new/2, is_array/1, set/3, get/2, size/1,
	 sparse_size/1, default/1, reset/2, to_list/1, sparse_to_list/1,
	 from_list/1, from_list/2, to_orddict/1, sparse_to_orddict/1,
	 from_orddict/1, from_orddict/2, map/2, sparse_map/2, foldl/3,
	 foldr/3, sparse_foldl/3, sparse_foldr/3, fix/1, relax/1, is_fix/1,
	 resize/1, resize/2]).

-export_type([array/0, array/1]).

%%-define(TEST,1).
-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").
-endif.


%% Developers: 
%% 
%% For OTP devs: Both tests and documentation is extracted from this
%% file, keep and update this file, 
%% test are extracted with array_SUITE:extract_tests().
%% Doc with docb_gen array.erl
%%  
%% The key to speed is to minimize the number of tests, on
%% large input. Always make the most probable path as short as possible.
%% In particular, keep in mind that for large trees, the probability of
%% a leaf node is small relative to that of an internal node.
%%
%% If you try to tweak the set_1 and get_1 loops: Measure, look at the
%% generated Beam code, and measure again! The argument order matters!


%% Representation:
%%
%% A tree is either a leaf, with LEAFSIZE elements (the "base"), an
%% internal node with LEAFSIZE+1 elements, or an unexpanded tree,
%% represented by a single integer: the number of elements that may be
%% stored in the tree when it is expanded. The last element of an
%% internal node caches the number of elements that may be stored in
%% each of its subtrees.
%% 
%% Note that to update an entry in a tree of height h = log[b] n, the
%% total number of written words is (b+1)+(h-1)*(b+2), since tuples use
%% a header word on the heap. 4 is the optimal base for minimizing the
%% number of words written, but causes higher trees, which takes time.
%% The best compromise between speed and memory usage seems to lie
%% around 8-10. Measurements indicate that the optimum base for speed is
%% 24 - above that, it gets slower again due to the high memory usage.
%% Base 10 is a good choice, giving 2/3 of the possible speedup from
%% base 4, but only using 1/3 more memory. (Base 24 uses 65% more memory
%% per write than base 10, but the speedup is only 21%.)

-define(DEFAULT, undefined).
-define(LEAFSIZE, 10).		% the "base"
-define(NODESIZE, ?LEAFSIZE).   % (no reason to have a different size)
-define(NODEPATTERN(S), {_,_,_,_,_,_,_,_,_,_,S}). % NODESIZE+1 elements!
-define(NEW_NODE(E,S),  % general case (currently unused)
        setelement((?NODESIZE+1),erlang:make_tuple((?NODESIZE+1),(E)),(S))).
-define(NEW_NODE(S), erlang:make_tuple((?NODESIZE+1),(S))).  % when E = S
-define(NEW_LEAF(D), erlang:make_tuple(?LEAFSIZE,(D))).
-define(NODELEAFS, ?NODESIZE*?LEAFSIZE).

%% These make the code a little easier to experiment with.
%% It turned out that using shifts (when NODESIZE=2^n) was not faster.
-define(reduce(X), ((X) div (?NODESIZE))).
-define(extend(X), ((X) * (?NODESIZE))).

%%--------------------------------------------------------------------------

-type element_tuple(T) ::
        {T, T, T, T, T, T, T, T, T, T}
      | {element_tuple(T), element_tuple(T), element_tuple(T),<commit_msg>Clarify comments in array module<commit_after>%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%%     http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%
%% Copyright (C) 2006-2016 <NAME> and Ericsson AB
%%
%% @author <NAME> <<EMAIL>>
%% @author <NAME> <<EMAIL>>
%%
%% @doc Functional, extendible arrays. Arrays can have fixed size, or
%% can grow automatically as needed. A default value is used for entries
%% that have not been explicitly set.
%%
%% Arrays uses <b>zero</b> based indexing. This is a deliberate design
%% choice and differs from other erlang datastructures, e.g. tuples. 
%%
%% Unless specified by the user when the array is created, the default
%% value is the atom `undefined'. There is no difference between an
%% unset entry and an entry which has been explicitly set to the same
%% value as the default one (cf. {@link reset/2}). If you need to
%% differentiate between unset and set entries, you must make sure that
%% the default value cannot be confused with the values of set entries.
%%
%% The array never shrinks automatically; if an index `I' has been used
%% successfully to set an entry, all indices in the range [0,`I'] will
%% stay accessible unless the array size is explicitly changed by
%% calling {@link resize/2}.
%% 
%% Examples:
%% ```
%% %% Create a fixed-size array with entries 0-9 set to 'undefined'
%% A0 = array:new(10).
%% 10 = array:size(A0).
%%
%% %% Create an extendible array and set entry 17 to 'true',
%% %% causing the array to grow automatically
%% A1 = array:set(17, true, array:new()).
%% 18 = array:size(A1).
%%
%% %% Read back a stored value
%% true = array:get(17, A1).
%%
%% %% Accessing an unset entry returns the default value
%% undefined = array:get(3, A1).
%%
%% %% Accessing an entry beyond the last set entry also returns the
%% %% default value, if the array does not have fixed size
%% undefined = array:get(18, A1).
%%
%% %% "sparse" functions ignore default-valued entries
%% A2 = array:set(4, false, A1).
%% [{4, false}, {17, true}] = array:sparse_to_orddict(A2).
%%
%% %% An extendible array can be made fixed-size later
%% A3 = array:fix(A2).
%%
%% %% A fixed-size array does not grow automatically and does not
%% %% allow accesses beyond the last set entry
%% {'EXIT',{badarg,_}} = (catch array:set(18, true, A3)).
%% {'EXIT',{badarg,_}} = (catch array:get(18, A3)).
%% '''

%% @type array(). A functional, extendible array. The representation is
%% not documented and is subject to change without notice. Note that
%% arrays cannot be directly compared for equality.

-module(array).

-export([new/0, new/1, new/2, is_array/1, set/3, get/2, size/1,
	 sparse_size/1, default/1, reset/2, to_list/1, sparse_to_list/1,
	 from_list/1, from_list/2, to_orddict/1, sparse_to_orddict/1,
	 from_orddict/1, from_orddict/2, map/2, sparse_map/2, foldl/3,
	 foldr/3, sparse_foldl/3, sparse_foldr/3, fix/1, relax/1, is_fix/1,
	 resize/1, resize/2]).

-export_type([array/0, array/1]).

%%-define(TEST,1).
-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").
-endif.


%% Developers: 
%% 
%% For OTP devs: Both tests and documentation is extracted from this
%% file, keep and update this file, 
%% test are extracted with array_SUITE:extract_tests().
%% Doc with docb_gen array.erl
%%  
%% The key to speed is to minimize the number of tests, on
%% large input. Always make the most probable path as short as possible.
%% In particular, keep in mind that for large trees, the probability of
%% a leaf node is small relative to that of an internal node.
%%
%% If you try to tweak the set_1 and get_1 loops: Measure, look at the
%% generated Beam code, and measure again! The argument order matters!


%% Representation:
%%
%% A tree is either a leaf, with LEAFSIZE elements (the "base"), an
%% internal node with LEAFSIZE+1 elements, or an unexpanded tree,
%% represented by a single integer: the number of elements that may be
%% stored in the tree when it is expanded. The last element of an
%% internal node caches the number of elements that may be stored in
%% each of its subtrees.
%% 
%% Note that to update an entry in a tree of height h = log[b] n, the
%% total number of written words is (b+1)+(h-1)*(b+2), since tuples use
%% a header word on the heap. 4 is the optimal base for minimizing the
%% number of words written, but causes higher trees, which takes time.
%% The best compromise between speed and memory usage seems to lie
%% around 8-10. Measurements indicate that the optimum base for speed is
%% 24 - above that, it gets slower again due to the high memory usage.
%% Base 10 is a good choice, giving 2/3 of the possible speedup from
%% base 4, but only using 1/3 more memory. (Base 24 uses 65% more memory
%% per write than base 10, but the speedup is only 21%.)

-define(DEFAULT, undefined).
-define(LEAFSIZE, 10).         % the "base" (assumed to be > 1)
-define(NODESIZE, ?LEAFSIZE).  % must not be LEAFSIZE-1; keep same as leaf
-define(NODEPATTERN(S), {_,_,_,_,_,_,_,_,_,_,S}). % NODESIZE+1 elements!
-define(NEW_NODE(E,S),  % general case (currently unused)
        setelement((?NODESIZE+1),erlang:make_tuple((?NODESIZE+1),(E)),(S))).
-define(NEW_NODE(S), erlang:make_tuple((?NODESIZE+1),(S))).  % when E = S
-define(NEW_LEAF(D), erlang:make_tuple(?LEAFSIZE,(D))).
-define(NODELEAFS, ?NODESIZE*?LEAFSIZE).

%% These make the code a little easier to experiment with.
%% It turned out that using shifts (when NODESIZE=2^n) was not faster.
-define(reduce(X), ((X) div (?NODESIZE))).
-define(extend(X), ((X) * (?NODESIZE))).

%%--------------------------------------------------------------------------

-type element_tuple(T) ::
        {T, T, T, T, T, T, T, T, T, T}
      | {element_tuple(T), element_tuple(T), element_tuple(T),
{'fraction_non_alphanumeric': 0.14296175752644427, 'fraction_numerical': 0.01969080553295362, 'mean_word_length': 4.008557457212714, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1040199', 'n_tokens_mistral': 3891, 'n_tokens_neox': 3737, 'n_words': 1616}