Data types I: primitive, string, enum and array addressing

A data type is a set of values and a set of operations defined on those values. This page covers the types that stand “alone” and arrays. The most guaranteed question on the midterm: compute the address of a two-dimensional array element. Anyone who knows the formula and doesn’t forget the lower bounds gets it.

Golden rules:

1. In row-major the row index is multiplied by the number of columns, in column-major the column index is multiplied by the number of rows.
2. If the lower bound is not 0, subtract it first.
3. If you are unsure, count how many elements are in front. The formula does exactly this.
4. Floating-point is approximate, int overflows.

Primitive types

Types that are not defined in terms of other types. Most correspond directly to hardware.

System.out.println('A' + 1);   // char is promoted to int
char c = 'A'; c++;
System.out.println(c);
System.out.println(0.1 + 0.2 == 0.3);
System.out.println(0.1 + 0.2);
int x = Integer.MAX_VALUE; x++;
System.out.println(x);
byte b = (byte) 130;
System.out.println(b);

66
B
false
0.30000000000000004
-2147483648
-126

130 does not fit in the byte range (-128..127); 256 is subtracted: -126. Overflow and approximation are two separate traps: int silently wraps, double silently rounds.

String types

Design questions: (1) is a string a primitive or an array of characters? (2) is its length static or dynamic?

In C a string is not a separate type; it is a char array ending with '\0'. strcpy(dest, src) does not check the size of the destination; overflow is a security hole (buffer overflow). In Java, String is immutable:

String s = "ab"; String t = s; s = s + "c";
System.out.println(t + " " + s);
StringBuilder sb = new StringBuilder("ab"); StringBuilder sb2 = sb;
sb.append("c");
System.out.println(sb2);
System.out.println(new String("hi") == "hi");
System.out.println(new String("hi").equals("hi"));

ab abc
abc
false
true

Enumeration and subrange

An enumeration type lists all possible values as named constants. Readability improves (Day.MON is better than 0) and reliability improves (in Java and C# arithmetic cannot be done on an enum, and out-of-range values cannot be assigned).

enum Day { MON, TUE, WED, THU }
System.out.println(Day.WED.ordinal() + " " + Day.valueOf("THU"));

2 THU

In C, enum values are ints: MON + 1 is valid, and any int can be assigned to an enum variable. A loss of safety.

A subrange type (Ada, Pascal) is a contiguous subset of an ordinal type: type Weekdays is range Mon..Fri;. Going out of range is caught by the compiler/run time.

Arrays

An array is a collection of homogeneous elements accessed by their position relative to the first element (index, subscript). Design questions: what are the index types? Is the index range checked? When is memory allocated? Jagged or rectangular? Is there slicing?

Array categories

Java and C# check the index range on every access; C and C++ do not.

int[] a = new int[3];
try { a[3] = 1; } catch (Exception e) { System.out.println(e.getClass().getSimpleName()); }

ArrayIndexOutOfBoundsException

In a rectangular array every row has the same length (Fortran, C# int[,]). A jagged array is an array of arrays, and row lengths can differ (Java int[][]).

Array address computation

The compiler computes the address of an element with an access function. One dimension, lower bound lb, element size size:

$\text{addr}(a[k]) = \text{base} + (k - lb)\cdot \text{size}$

A two-dimensional array is laid out in memory in two ways:

• Row-major (C, C++, Java, most languages): row by row. First all elements of row 0, then row 1…
• Column-major (Fortran): column by column.

For an array with m rows and n columns:

$\text{row-major: } \text{base} + \big((i - lb_r)\cdot n + (j - lb_c)\big)\cdot \text{size}$

$\text{column-major: } \text{base} + \big((j - lb_c)\cdot m + (i - lb_r)\big)\cdot \text{size}$

Worked example

int A[6][9], base 3000, int 4 bytes, A[4][7].

row-major:  4 full rows in front × 9 = 36, + 7 in this row  → 43 elements
            3000 + 43 × 4 = 3172
col-major:  7 full columns in front × 6 = 42, + 4 in this column  → 46 elements
            3000 + 46 × 4 = 3184

A Fortran array B(1:5, 1:10) with lower bound 1, 8 bytes, base 500, B(3, 4):

subtract the lower bounds: row 3-1 = 2, column 4-1 = 3
col-major, m = 5:  3 × 5 + 2 = 17 elements in front
500 + 17 × 8 = 636

PITFALL · n or m? In row-major, to skip a row you skip all the columns in that row, so you multiply by n (the number of columns). In column-major, to skip a column you skip all the rows in that column, so you multiply by m. If you mix them up, the result is the address of another element, and you can’t check it in the exam.

Slice

A slice is a substructure of an array; not a new data type, but a way to access a part of an existing array. Python a[1:4], Fortran A(2:4). In JavaScript, slice copies a new array:

console.log([10, 20, 30, 40, 50].slice(1, 4));

[ 20, 30, 40 ]

The start is included, the end is excluded.

Associative array

A collection whose elements are unordered and accessed by a key. Perl hash (%h), Python dict, JavaScript Map and objects, Java HashMap.

const m = new Map([["ali", 70], ["ayse", 85]]);
m.set("ali", 90); m.delete("ayse"); m.set("can", 60);
console.log([...m.keys()].join(","), m.get("ali"), m.size);

ali,can 90 2

Assigning to an existing key updates the value, a new key adds an element. Because lookup is done with a hash, it is faster than sequential search; but there is no notion of an “i-th element”.

Common mistakes

System.out.println('A' + 1);
char c = 'A';
c++;
System.out.println(c);

System.out.println(0.1 + 0.2 == 0.3);

int x = Integer.MAX_VALUE;
x++;
System.out.println(x);

String s = "ab";
String t = s;
s = s + "c";
System.out.println(t + " " + s);

System.out.println(new String("hi") == "hi");
System.out.println(new String("hi").equals("hi"));

int[] a = new int[3];
try { a[3] = 1; }
catch (Exception e) { System.out.println(e.getClass().getSimpleName()); }