50018. Map

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

Problem Description

Write a map package. A map is a function that maps a key to its value. Here we assume that the map is from a 32 bit signed integer to a string of maximum length 127, and a map can store up to 1024 key/value pairs. You need to implement the following functions.

  • void init(Map *map);
    Initialize a map so that it does not contain any key/value pair.
  • int map(Map *map, const int key, const char *value);
    Map a key to a value. You need to copy the contents of value into the map structure with strcpy (char * destination, const char * source);. If a key is mapped multiple times, its value should be the last value. The return value is 1 if the key was not mapped, 0 if it was already mapped.
  • int numPairs(Map *map);
    Return the number of key/value pairs in the map. Note that this function should be extremely efficient because it will be called a huge number of times.
  • void print(Map *map);
    Print all key/value pairs in increasing order of keys. Each key/value is in one line. You can use a bubble sort.
  • const char *getValue(Map *map, const int key);
    Return a pointer to the value of a given key. If the key is not in the map, it should return NULL.
  • int unmap(Map *map, int key);
    Unmap a key so that after this function call if you call getValue() for that key, it will return NULL. If the key was mapped return 1, otherwise return 0.
  • int reverseMap(Map *map, const char *value, int keys[]);
    Return all keys whose values are equal to the given value. These keys should be returned in the array keys in increasing order. The return value is the number of keys returned.

Subtasks

  • 10pt. Implement init and print.
  • 20pt. Implement init, map, and print.
  • 10pt. Implement init, map, getValue, and print.
  • 20pt. Implement init, map, and unmap, and print.
  • 30pt. Implement init, map, and unmap, print, and reverseMap.
  • 10pt. Implement init, map, unmap, and numPairs.

Hint

The function numPairs will be called extremely frequently in the last subtask, so you cannot compute the number on the fly; instead you should use a variable member to store it, and update it when necessary.

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 "map.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
 
void test_all(Map *maps, int map_n) {
    for (int i = 0; i < map_n; i++)
        init(&maps[i]);
    int cmds, mid, cmd, key;
    char val[128];
    int keylist[1024];
    scanf("%d", &cmds);
    for (int i = 0; i < cmds; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d", &mid);
            print(&maps[mid]);
        } else if (cmd == 2) {   
            scanf("%d %d %s", &mid, &key, val);
            int f = map(&maps[mid], key, val);
            printf("mf %d\n", f);
        } else if (cmd == 3) {
            scanf("%d %d", &mid, &key);
            int f = unmap(&maps[mid], key);
            printf("uf %d\n", f);
        } else if (cmd == 4) {
            scanf("%d %s", &mid, val);
            int keylist_n = reverseMap(&maps[mid], val, keylist);
            assert(keylist_n <= 1024);
            printf("list ");
            for (int i = 0; i < keylist_n; i++)
                printf("%d%c", keylist[i], " \n"[i == keylist_n-1]);
        } else if (cmd == 5) {
            scanf("%d", &mid);
            int ret = numPairs(&maps[mid]);
            assert(ret <= 1024);
            printf("size %d\n", ret);
        } else {
            assert(false);
        }
    }
}
int main() {
    int spec;
    int map_n = 1;
    Map *maps = (Map *) malloc(sizeof(Map) * map_n);
    test_all(maps, map_n);
    free(maps);
    return 0;
}

Sample Input

15
1 0
2 0 1 10pt
1 0
2 0 2 10pt
1 0
2 0 2 20pt
2 0 0 god
1 0
3 0 0
2 0 0 pangfeng
1 0
2 0 3 10pt
4 0 10pt
1 0
5 0

Sample Output

----- map begin -----
----- end       -----
mf 1
----- map begin -----
1 10pt
----- end       -----
mf 1
----- map begin -----
1 10pt
2 10pt
----- end       -----
mf 0
mf 1
----- map begin -----
0 god
1 10pt
2 20pt
----- end       -----
uf 1
mf 1
----- map begin -----
0 pangfeng
1 10pt
2 20pt
----- end       -----
mf 1
list 1 3
----- map begin -----
0 pangfeng
1 10pt
2 20pt
3 10pt
----- end       -----
size 4

Discussion