- Characteristics
- Performance
- Supported Element Types
- Declaration
- Literal Syntax
- Access and Assign
- Iteration
- Sorting
- Use as a Stack
- Use as a Queue
- 2D Sequences/Matrix
- Further Information
Sequences are dynamically resized arrays with bounds checking. The collection is often referred to as just 'seq'.
Characteristics
- Preserves order
- Can be sorted
- Small memory footprint
Performance
- Fast indexing (constant time, O(1))
- Fast append (constant time, O(1), except if resize is necessary)
- Slow insert as all elements after the target index must be moved (linear, O(index))
- Slow remove unless removing the last element (linear, O(count - index))
- Slow lookup for indexOf, contains, exclude etc. (linear, O(count))
- Small memory footprint (elementSize*count + small overhead)
When appending a large number of elements, the seq will double its capacity as many times that is necessary, resulting in O(n log n) performance. To work around this you can preallocate or resize the seq before appending.
Supported Element Types
Sequence supports almost any type you can think of. The only exception is for values that are of any other size than 4, 8, 12, 16, 24, 32, or 48 bytes.
Declaration
elementType[] identifier;
Example
Declare a sequence of integers initialized to null:
{
int[] integers;
}
Declare and create an empty sequence (recommended):
{
int[] integers();
}
Same as above, using the new keyword:
{
int[] integers = new int[];
}
It's also possible to create the sequence using the init feature:
{
int[] integers;
...
init integers();
}
You can also specify an initial capacity (measured in the number of elements) for the collection:
{
int[] integers(64);
integers = new int[](64);
init integers(64);
}
Even though the seq will grow incrementally (by doubling its size) as necessary when you append elements, increasing the initial size can improve performance if you know that you will append a large number of elements. Generally speaking, however, you should be conservative with the allocation size.
Literal Syntax
[type: expr1, expr2 .. exprn]
[expr1, expr2 .. exprn]
Example
Create a sequence containing the elements 1, 2, and 3 as doubles:
{
double[] values = [double: 1, 2, 3];
}
Same as above but omits double: since the element type can be inferred from the expressions:
{
double[] values = [1.0, 2.0, 3.0];
}
Access and Assign
There are multiple different ways to access and assign elements in a seq.
Access Example
{
int[] seq = [int: 1, 2, 3, 4];
pln(#seq);
pln(#seq.count);
pln(#seq.any);
pln(#seq.empty);
pln(#seq.first);
pln(#seq.last);
pln(#seq.indexOf(3));
pln(#seq.indexOf(42));
pln(#seq.contains(3));
pln(#seq.contains(42));
pln(#(3 in seq));
pln(#(42 in seq));
pln(#seq[0]);
}
Output: seq=[int, count=4: 1, 2, 3, 4] seq.count=4 seq.any=true seq.empty=false seq.first=1 seq.last=4 seq.indexOf(3)=2 seq.indexOf(42)=-1 seq.contains(3)=true seq.contains(42)=false (3 in seq)=true (42 in seq)=false seq[0]=1
Assign Example
{
int[] seq = [int: 1, 2, 3, 4];
pln(#seq);
seq[3] = 9;
pln(#seq);
seq.insert(0, 31);
seq.insert(1, 32);
pln(#seq);
seq += [int: 34, 35];
pln(#seq);
seq << 31 << 32;
pln(#seq);
seq.exclude(32);
pln(#seq);
seq.remove(0);
seq.remove(0);
pln(#seq);
}
Output: seq=[int, count=4: 1, 2, 3, 4] seq=[int, count=4: 1, 2, 3, 9] seq=[int, count=6: 31, 32, 1, 2, 3, 9] seq=[int, count=8: 31, 32, 1, 2, 3, 9, 34, 35] seq=[int, count=10: 31, 32, 1, 2, 3, 9, .. 31, 32] seq=[int, count=8: 31, 1, 2, 3, 9, 34, 35, 31] seq=[int, count=6: 2, 3, 9, 34, 35, 31]
Iteration
Built-in for iteration is fully supported.
Example
{
int[] seq = [1, 2, 3, 4];
for (z in seq) pln(z);
pln();
for (z in seq, index=i) pln(i, " -> ", z);
pln();
for (z in seq, reverse) pln(z);
pln();
for (z in seq, start=1, end=2) pln(z);
}
Output: 1 2 3 4 0 -> 1 1 -> 2 2 -> 3 3 -> 4 4 3 2 1 2 3
Sorting
Sorting is built into the CM language, using a quick-sort algorithm (with O(n log n) performance).
Default Sorting Example
{
int[] values = [1, 3, 2];
values.sort();
pln(values);
}
Output: [int, count=3: 1, 2, 3]
You may provide your own sorting function to replace the default sorting:
Custom Sorting Example
private int reverseCompare(double a, double b, Object env) { return -compare(a, b); } { double[] values = [1.0, 3.3, 2.3]; values.sort(function reverseCompare, null); pln(values); }
Output: [double, count=3: 3.3, 2.3, 1]
Use as a Stack
A seq can be used as a stack, using the push, pop, and drop methods.
- push: Appends an element last in the seq.
- pop: Removes the last element in the seq and returns it.
- drop: Removes element(s) from the end of the seq. If no argument is given, the last element is removed.
Example
{
str[] stack();
stack.push("aa");
stack.push("bb");
stack.push("cc");
pln(#stack);
pln(#stack.pop());
pln(#stack);
stack.push("dd");
stack.push("ee");
stack.push("ff");
pln(#stack);
stack.drop();
pln(#stack);
stack.drop(2);
pln(#stack);
}
Output: stack=[str, count=3: "aa", "bb", "cc"] stack.pop()=cc stack=[str, count=2: "aa", "bb"] stack=[str, count=5: "aa", "bb", "dd", "ee", "ff"] stack=[str, count=4: "aa", "bb", "dd", "ee"] stack=[str, count=2: "aa", "bb"]
Use as a Queue
It's not efficient to use a seq as a FIFO queue. Please consider using the Queue collection instead.
2D Sequences/Matrix
2D Sequences/Matrix can be initialized using sequences.
Example
Creating an empty 2D sequence/Matrix :
{
(int[])[] matrix();
}
Creating a 2D sequence/Matrix with predefined elements.
{
(int[])[] matrix = [int[]: [int: 1, 2, 3], [int: 4, 5, 6]];
(int[])[] matrix2 = [[1, 2, 3], [4, 5, 6]];
}
Access :
{
(int[])[] matrix = [[1, 2, 3], [4, 5, 6]];
pln(#matrix[0]); // accessing the first list in matrix
pln(#matrix[0][0]); // accessing the first element in the first list
pln(#matrix[0].first); // accessing the first element in the first list
pln(#matrix[0].empty); // return true if first list is empty
}
Further Information
See file your workspace/base/cm/lang/seq.cmz
Comments
0 comments
Please sign in to leave a comment.