Lists

Lists vs arrays problem

Blockly allows users to utilise Lists in its original sense with add/remove/insert/delete operations possible as well as varying length. We have different implementations for different robot platforms partially because of language limitations like NXC and partially because of implementation specifics, like Calliope.

Here we summarise all the discussions on this topic. Let's begin with a picture.

Concept for all robots

Overview

Robot	Language	List support wanted	Notes
EV3Lejos	Java	✔	java.util.List
EV3dev	Python	✔	standard python list []
Microbit	Python	✔	standard python list []
NAO	Python	✔	standard python list []
Calliope	C++	✔	STL std::list
BOB3	C++	✔	Decision needed ❓
Arduino	C++ subset	✔	ArduinoSTL std::list
Bot'n Roll	C++ subset	✔	ArduinoSTL std::list
NXT	NXC	✘	no implementation possible
WeDo	Javascript	✘	not wanted
Simulations	Javascript	✔	Javascript object

ArduinoSTL

I have tested ArduinoSTL (a port that can be installed directly through the Arduino IDE) on Arduino UNO, which has ATMega328p CPU.

empty sketch: Sketch uses 444 bytes (1%) of program storage space. Maximum is 32256 bytes. Global variables use 9 bytes (0%) of dynamic memory, leaving 2039 bytes for local variables. Maximum is 2048 bytes.

including stl + list: Sketch uses 3864 bytes (11%) of program storage space. Maximum is 32256 bytes. Global variables use 420 bytes (20%) of dynamic memory, leaving 1628 bytes for local variables. Maximum is 2048 bytes.

adding 16 int values to the list and printing them to serial: Sketch uses 4884 bytes (15%) of program storage space. Maximum is 32256 bytes. Global variables use 463 bytes (22%) of dynamic memory, leaving 1585 bytes for local variables. Maximum is 2048 bytes.

BOB3 uses 88p, which has 8k in-system flash and 512 bytes of SRAM, so here we may run into issues. This requires more close research.

List operations

Indices start from 0

Block	Options	Meaning
		Creates an empty list.
		Creates a list with the specified elements.
		Creates a list with the specified element repeated x times.
		Returns the length of the list.
		Returns true if the list is empty, false if it has elements.
		Returns the index of the first occurrence of the element.
		Returns the index of the last occurrence of the element.
		Returns the element at the specified index.
		Removes the element at the specified index and returns its value.
		Removes the element at the specified index.
		Sets the element at the specified index to the specified value.
		Inserts the specified value at the specified position. Insert at first means prepend. Insert at last means append.
		Returns the sublist specified by the positions. The from is inclusive, the to is exclusive.
		How to handle removing or adding elements: Decision needed ❓
		Assignment, copy or deep copy: Decision needed ❓

List comparison

Here it says that comparison operators for std::list are overloaded, so that equal/not equal:

Checks if the contents of lhs and rhs are equal, that is, they have the same number of elements and each element in lhs compares equal with the element in rhs at the same position.

and less/greater and the company:

Compares the contents of lhs and rhs lexicographically. The comparison is performed by a function equivalent to std::lexicographical_compare.

for java lists:

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface.

for python there is a topic on stackoverflow

All implementations have to be checked!

Other thoughts

• Random should be removed from all options: the specific random block can be used.
• Functions should take references, not local copies.
• List functions from BlocklyMethods should be extracted into one-liners, if possible.
• Printing lists should be possible.
• Check APIs for acceptance of used list implementations.
• Checking index out of bounds should be left to the user.
• Setting or inserting out of bounds should be documented per language.
• Setting or inserting out of bounds in the simulation should follow the behaviour of the real robot.

Plan of Attack

1. Start with Java implementation.
2. Enable the same list blocks for supported robots (see list).
3. Write a test program covering all of the operations and the expected results, according to the specifications.
4. Implement C++ list operations in accordance to the test program.
5. Implement Python list operations in accordance to the test program.