50020. Generic Index Array

I'm a slow walker, but I never walk backwards.

Problem Description

Implement a generic array that supports index starting from any integer. You must implement the following functions.

  • void init(ARRAY *darray, int startIndex, int endIndex);
    Initialize an array so that the index starts and ends at specified locations. It is guaranteed that the starting index is no more than the ending index. All element are considered "not yet set" after initialization.
  • int set(ARRAY *array, int index, int value);
    • if the index is within the range of ARRAY, set the array element at the specified index to the specified value, and return 1. It is guaranteed that we will never set an element to either -2147483648 or -2147483647.
    • If the specified index is out of range then do nothing and return -2147483648.
  • int get(ARRAY *array, int index);
    • If the index is within the range of ARRAY then do the following.
    • If element has been set before then return the value that was set last.
    • If element has not been set before return -2147483647.
    • If the index is out of range return -2147483648.
  • void print(ARRAY *array);
    Print the contents of the ARRAY. The function will print one element per line, from the start to the end of the index range. If an element has never been set before, print "No value" at that line.
  • void sort(ARRAY *array);
    Sort the elements in the ARRAY. Those elements that have not been set before should appear at the beginning of the array after sorting.

Subtasks

  • 10pt. Implement init and print.
  • 30pt. Implement init, set, and get, and the parameter index is always correct.
  • 10pt. Implement init, set, and get, and the parameter index is not always correct.
  • 30pt. Implement init, set, get, and print, and the parameter index is not always correct.
  • 20pt. Implement init, set, get, print and sort, and the parameter index is not always correct.

array.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef _ARRAY_H
#define _ARRAY_H
 
/*
    define structure ARRAY
*/
 
void init(ARRAY *a,  int left, int right);
int set(ARRAY *a, int index, int value);
int get(ARRAY *a, int index);
void print(ARRAY *a);
void sort(ARRAY *a);
 
#endif

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "array.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
#define OUTOFBOUND -2147483648
#define HAVENOTSET -2147483647
#define SETSUCCESS 1
void test_specall() {
    int n, l, r;
    int cmds, cmd, aid;
    int index, value;
    scanf("%d", &n);
    ARRAY *a = (ARRAY *) malloc(sizeof(ARRAY)*n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &l, &r);
        init(&a[i], l, r);
    }
    scanf("%d", &cmds);
    for (int i = 0; i < cmds; i++) {
        scanf("%d %d", &cmd, &aid);
        if (cmd == 1) {
            print(&a[aid]);
        } else if (cmd == 2) {
            scanf("%d %d", &index, &value);
            int ret = set(&a[aid], index, value);
            printf("ARRAY ID %d, set(%d, %d) %s\n", aid, index, value,
                ret == SETSUCCESS ? "SUCCESS" : (ret == OUTOFBOUND ? "OUTOFBOUND" : "HAVENOTSET"));
        } else if (cmd == 3) {
            scanf("%d", &index);
            int ret = get(&a[aid], index);
            printf("ARRAY ID %d, get(%d) ", aid, index);
            if (ret == OUTOFBOUND)   
                printf(": OUTOFBOUND\n");
            else if (ret == HAVENOTSET)
                printf(": HAVENOTSET\n");
            else
                printf("= %d\n", ret);
        } else if (cmd == 4) {
            sort(&a[aid]);
        } else {
            assert(0);
        }
    }
}
int main() {
    int spec = 0;
    void (*FUNC[])() = {test_specall};
    FUNC[spec]();
    return 0;
}

Sample Input

3
0 10
-5 0
1000 2000
24
1 0
2 0 2 4
2 0 3 9
2 0 5 25
1 0
2 1 -1 -1
2 1 -3 -9
2 1 0 0
1 1
3 0 5
3 1 -3
3 0 -1
3 1 1
2 0 -1 3
2 1 5 6
3 0 4
4 0
1 0
4 1
1 1
2 1 -3 514
1 1
4 1
1 1

Sample Output

No value
No value
No value
No value
No value
No value
No value
No value
No value
No value
No value
ARRAY ID 0, set(2, 4) SUCCESS
ARRAY ID 0, set(3, 9) SUCCESS
ARRAY ID 0, set(5, 25) SUCCESS
No value
No value
4
9
No value
25
No value
No value
No value
No value
No value
ARRAY ID 1, set(-1, -1) SUCCESS
ARRAY ID 1, set(-3, -9) SUCCESS
ARRAY ID 1, set(0, 0) SUCCESS
No value
No value
-9
No value
-1
0
ARRAY ID 0, get(5) = 25
ARRAY ID 1, get(-3) = -9
ARRAY ID 0, get(-1) : OUTOFBOUND
ARRAY ID 1, get(1) : OUTOFBOUND
ARRAY ID 0, set(-1, 3) OUTOFBOUND
ARRAY ID 1, set(5, 6) OUTOFBOUND
ARRAY ID 0, get(4) : HAVENOTSET
No value
No value
No value
No value
No value
No value
No value
No value
4
9
25
No value
No value
No value
-9
-1
0
ARRAY ID 1, set(-3, 514) SUCCESS
No value
No value
514
-9
-1
0
No value
No value
-9
-1
0
514

Discussion