Menu Close

Articles

Level: Dynamic Collections

Dynamic collections are composite types. These collections are dynamic because we can add or remove elements very quick with minimum impact on memory relocation. Vectors and Matrices are simple and fast to access using index, but they have fixed capacity. When we resize a vector or a matrix we have to move all data into a new location. Dynamic collections can grow and shrink capacity very fast but searching elements in dynamic collections is slower.

Define

We define for Level these dynamic collections: {List, Map, Set }. For each of these collections we use a special literal inspired from mathematics notation. We have avoid to use {…} as code block to be able to use this notation for Map and Set collections.

List

A List is a consecutive sequence of elements having a dynamic capacity. The elements of a List must have the same type. For a list with n elements each element can be identified using an integer index in range (0..n-1). Unlike Julia where the range is (1..n). We have chosen this convention for compatibility in thinking with Java, Python and C++. Software developers count from 0 to 9.

Declaration syntax:

variable <list_name>: List of <type_name>;

Different Lists:

type
  Person: Record of (name: String, age: Integer);
variables
  n_list: List of Integer;
  s_list: List of String;
  p_list: List of Person;

List literals:

A list is similar to a mathematical set, except that it can contain duplicate elements. Also the elements of a list are ordered by a numeric subscript index. Initialization of a list can be done using define symbol “=” and List literals. String literals are comma separated enumerations of enclosed in square brackets: [,,,].

variable
  c_list = ['a','b','c','c','c'];
  n_list = [1,2,3,1,2,3];

Concatenation

List concatenation operator “&” can be used to concatenate two lists. Can be used to combine a string with a list. This will automatically convert the list elements  into coma separated string.

print ([1,2,3]  & [4,5]);   --will print:[1,2,3,4,5]
print ([1,2,3]  & "4,5");   --will print:"1,2,3,4,5"
print ("1,2,3," & [4,5]);   --will print:"1,2,3,4,5"

Joining

The join function receive a list and convert elements into a string separated be specified character. join(lst list, sep separator) result string;

let
  str:String;
  lst=[1,2,3]:List;
do
  str := list.join(lst,"-");
  print(str); --> "1-2-3"
end do;

Empty list

To create an empty list using type inference we can use empty list symbol [].
Elements of the list can be a created later using list operators.

c_list=[]:List of String;
n_list=[]:List of Integer;

List operations

We can add elements to a List or remove elements using methods.

  • append() – can append an element and return the index of the element
  • clear() – can delete all elements or a specific index element.
  • insert() – can insert an element at specified index

Other methods:

  • count() – retrieve the number of elements
  • first() – retrieve the first element
  • last() – retrieve the last element
  • next() – retrieve the next element
  • current() – retrieve the current element

List comprehension

You can define elements of a sub-list from a list using the following construction:

<sub_list> = [ <var> | <var> in <list_name> and <filter_expression>]

Symbol “|” is the filter operator and is derived from mathematics. We can use <var> to create the <filter_expression>.

Example of a list comprehension operation:

let
  my_list = [0,1,2,3,4,5,6,7,8,9]: List of Integer;
job
  sub_list= [ x | x in my_list and x%2 = 0];
  print(sub_list); 
end job;

=> [0,2,4,6,8]


Map

A Map is a set of (key:value) pairs. The key must be one of {integer, string} and is unique. Map literals are represented as list of pairs enclosed in curly brackets separated by comma. Each key is separated from the value using colon “:” symbol having interpretation “paired up”.

type declaration …

type StringMap: Map of (String, String);

map literals …

{key:value[,key:value]...}

map of strings…

variable str_map: Map of (String, String);

map of integers…

variable 
  int_map Map of (String, Integer);

example of initialization …

variable
  int_map = {'one':1, 'two':2};

declare an empty map

variable 
  map_name={}: Map of (String, String);

Methods

  • append();
  • update();
  • remove()
  • clear();
  • count();
  • first();
  • last();

check if a key is present in a map …

if key_value in map then
   pass;
else
   fail;
end if;

retrieve a value from a map using the key.

<variable> := <map_name>[key_value];

Example

Using [key] to access elements is usable for creation of new elements. If element is not found a new element is created.

procedure main is
  animals:Map of (String, String);
begin
  animals[“Bear”] := “dog”;
  animals[“Kiwi”] := “bird”;
  print(animals);
end procedure;

=> {“Bear”:”dog”,“Kiwi”:”bird”};

Type inference

The map literal is similar to a JSON literal. We can use type inference for maps with at least one member. If we use {} we do not create a Map but a Set. This may be inconvenient therefore we can use partial inference:

Partial inference

  • m={} : Map;
  • s={} : Set;

Example

procedure main is
   animals: Map;
begin
  --create first elements
  animals["Fido"]:="dog";
  animals["Rover"]:="dog";

  --use direct assignment to create 2 more element
  animals[“Bear”] := “dog”;
  animals[“Kiwi”] := “bird”;
  print(animals);
  
  -- clean collection from memory (re-initialize)
  animals:= {}; --> we can empty a collection 
  print(animals);
end program;

=> {“Fido”:”dog”,“Rover”:”dog”,“Bear”:”dog,“Kiwi”:”bird”};
=> {}

Notes:

Map values are sorted in memory by key for fast search. It is more difficult to search by value because is not unique and not sorted. To search by value one must create a loop and verify every element. This is not recommended.


Set

In mathematics a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. Sets are fast to search, add or remove elements. However, you have to know the element value in order to search for it or to remove it from the set.

A set is defined using:

<set_name>: Set of <type>;

Set restrictions

  • All elements of a set must have the same type
  • Set elements can have only comparable types: {numbers, strings};
  • Elements of a set can be defined using curly brackets and comma separation {, , ,}.

Example:

To define a set we can use the partial type inference and initialization.

my_set={0,1,2,3,4,5,6,7,8,9}: Set;

equivalent to:

my_set={0,1,2,3,4,5,6,7,8,9}: Set of Integer;

Math deviation

In Level language elements of a set are ordered unlike the mathematical set. This makes the set more useful and has all the features of a mathematical set. When a new member is created a verification is made first. The new member is created only if no other member already exists.

Member operators:

operatordescription
intest if one value is member
not intest if one value is member
is Emptytest if a set is empty
is VoidNotice dynamic collections are never void. Only reference to collections can be Void.

Empty and Void

An Empty set is represented like this: {} and can be assigned to a set if you wish to remove all elements of the set: A Void Set  can exist only if we use :=Void assignment. We can have Empty collections. A reference to a collection can be Void if is not assigned or initialized.

OperationDescription
my_set:={}forget the old set and create a new one
my_set.clear()remove all elements from a set
my_set:=Voidmake a collection Void

Mutability

A set can be modified in memory during run-time. For this a set must implement several procedures and functions.

  • append(); append a new value to a set
  • delete(); remove a specific element from a set
  • clear(); remove all elements from a set, equivalent to :={}

Scalar operations

Using a single numeric value (scalar) is possible to modify all elements of the collection in a single operation. Scalar operators are: {+, -, *, /, ^, %}. Using this operation, all elements of a collections are operated with the scalar value. The only restriction is for members to be numeric.

Example:

print ({1,2,3} * 2); -- will print {2,4,6}

Union

Adding an element to a set is possible using union operator ‘||’. Unlike list concatenation the union operator will not duplicate elements. This operator also work for maps.

my_set:{0,1,2,3,4,5,6,7,8,9} Set of Integer;
sub_set: sub_set || {0,1,2,10};
print(sub_set) ; 

=> {0,1,2,3,4,5,6,7,8,9,10}

Intersection

Two sets can be intersected, so that common elements are stored into a new set using the set intersection operator ‘&&’. The result is also a set and can be an empty set when collections do not have common elements.

print ({1,2,3,4} && {3,4,5}); -- this will print {3,4}

Set comprehension

You can define elements of a subset from a set using the following construction:

<sub_set> = { <var> | <var> in <set_name> and <filter_expression>}

Symbol “|” is the filter operator and is derived from mathematics. We can use <var> to create the <filter_expression>.

Example of a list comprehension operation:

let
  my_set={0,1,2,3,4,5,6,7,8,9}: Set of Integer;
  sub_set={} Set of Integers;  
do
  sub_set = { x | x in my_set and x%2 = 0};
  print(sub_set); 
end do;

=> {0,2,4,6,8}

Example:

Using casting function “set” we can convert a List into a Set.

procedure main is
   my_list=[0,1,2,2,2,2] : List;
   my_set1={0,1} : Set;
   my_set2:Set of Integer;
begin
   my_set2 := my_set1 && set(my_list);  
   print(my_set2); --> {0,1,2}
end program;

lev:>run test

{0,1,2}

Set operators

In following table A, B are two sets and x is a member type: numeric or string

OperatorResultDescription
is Emptylogicalverify if a set has elements
x in Alogicalverify if x is a member
x not in Alogicalverify if x is not a member
A == Blogicalverify is all elements from A are found in B
A <= Blogicalverify is A is subset of B
A >= Blogicalverify if B is subset of A
A ~= Blogicalverifi if set A is not equal to set B
A += Blogicalmodify set A is by adding new elements found in B
A -= Blogicalmodify set A is by removing elements found also in B
A && BsetUnion of A with B, use like: C: A && B (return a new set)
A || BsetIntersect A with B, use like: C: A || B (return a new set)

Collection Casting

Sometimes we need to convert a collection from one type to other. This conversion is called casting and is similar to coercion. Level uses casting functions to convert one kind of collection into another kind.

Casting functions

Cast operation is performed by using a function from a literal or expression. Collection casting can produce a string or another collection of different type. All elements of the old collection are transfer to the new collection. Observe list and set are functions are not type constructors or anything like that.

Cast syntax:

s = set([1,2,3]);
l = list({1,2,3});

Comprehension Operator (“|”)

It is common for one collection to be created based on elements from another collection. Collection members can be copy into the new collection using a comprehension operator: “|”.

Example:

let
   my_list=[0,1,2,2,2,2]: List;
   my_copy: List of Integer;
   my_set1: Set of Integer;
   my_set2: Set of Integer;
do
   my_set1 := set(my_list); --will create set {0,1,2} 
   my_copy := [ x | x in my_list ]; -- my_copy = [0,1,2,2,2,2]
   my_set2 := { x | x in my_list }; -- my_set2 = {0,1,2} 
end do;

Type inference

This is a logical deduction of variable type from literals. The literal can provide enough information for the variable to be defined and initialized in one statement. We usually define variables in the declaration area. For Level 2 we can declare variables in the program executable area using type inference. These types are local to the current section scope.

Example:

-- Define a list of 10 elements using type inference:
program test is
  ls=[0,1,2,3,4,5,6,7,8,9]; 
begin
  print(type(ls[0]));
  print(type(ls));
  print(ls);
end program;

If we run this in Level console:

lev:>run test
Integer
List
[0,1,2,3,4,5,6,7,8,9]

lev:>


Empty collections:

When we use type inference we can create an empty collection using the zero value. This is described below:

LiteralType
[]Empty List
{}Empty Set or Map
<>Empty xml
“”Empty Unicode string
Empty ASCII string

Non empty collections:

LiteralType
(“a”,”b”,”c”)Tuple
(1,2,3)Tuple
{“a”:”b”}Map
{0:”a”,1:”b”}Map
[‘a’,’b’]List
{‘a’,’b’}Set

Partial Inference

When we declare a collection using type inference we do not have to verify the member type but we need to specify the composition category: {Record, Map, List, Tuple, Set}. Only the last part of the type can be inferred. This is for a good  reasons: Improved readability!

Examples of type inference:

program test is
  -- region inference (variable)
  v=TRUE; 
  r=(name:"test", age:"24"): Record; 
  m={"key1":"value1","ley2":"value2"}:Map;
begin
  -- check variable types using introspection
  print("v is of type " & type(v));
  print("r is of type " & type(r));
  print("m is of type " & type(m));
end program test
lev:> run test
v is of type Logical
r is of type Record
m is of type Map

Read next: Level: Object Oriented