You cannot submit for this problem because the homework's deadline is due.

Description

Implement the seven basic operations of dictionary using sorted double link lists. The seven basic operations are search insert delete maximum minimum successor predecessor. Besides, we will require you to implement some easy extra functions in order to test your code.

Header file

In order to test your code, we have specified the interface of your implemetation.

#ifndef DICTIONARY_DICTIONARY_H
#define DICTIONARY_DICTIONARY_H
void *initializer();
// EFFECT: Initialize an empty dictionary

void *search(void* dictionary, int key);
// EFFECT: Given a dictionary, return the pointer to the element(key-value pair) specified by the key, return NULL if not found.

void insert(void* dictionary, int key, int value);
// EFFECT: If the key does not exist, insert an element(a key-value pair) to this dictionary. If key already exists, update the value.

void delete(void* dictionary,int key);
// EFFECT: Delete an element(key-value pair) specified by the key. If it does not exist, do nothing

void *minimum(void* dictionary);
// EFFECT: return the element(key-value pair) with the smallest key

void *maximum(void* dictionary);
// EFFECT: return the element(key-value pair) with the largest key

void *predecessor(void* dictionary, int key);
// EFFECT: retrieve the pointer to the element(key-value pair) just before a given key

void *successor(void* dictionary, int key);
// EFFECT: retrieve the pointer to the element(key-value pair) just after a given key

void free_dict(void* dictionary);
// EFFECT: free the memory allocated for this dictionary

int getkey(void* element);
// EFFECT: Given a pointer to the element, return the key

int getvalue(void* element);
// EFFECT: Given a pointer to the element, return the value

void free_dict(void* dictionary);
// EFFECT: free the memory allocated for the dictionary
#endif //DICTIONARY_DICTIONARY_H

Submission

Requirement

You should implement the function according to the complexity stated in Dictionary using linked structures (Page 22 of c1.pdf).

Files

You should submit a tar or zip file containing a c source file named as dictionary.c. It should be like:

// define your only data structure here, you may define dictionary, elements, etc...
void *initializer()
{
    // your code here
}

void *search(void *dictionary, int key)
{
    // your code here
}

void insert(void *dictionary, int key, int value)
{
    // your code here
}

void delete(void *dictionary, int key)
{
    // your code here
}

void *minimum(void *dictionary)
{
    // your code here
}

void *maximum(void *dictionary)
{
    // your code here
}

void *predecessor(void *dictionary, int key)
{
    // your code here
}

void *successor(void *dictionary, int key)
{
    // your code here
}


int getkey(void *element)
{
    // your code here
}

int getvalue(void *element)
{
    // your code here
}

void free_dict(void *dictionary)
{
    // your code here
}

Testing

Test Program

We will test your dictionary with a testing program. You don't need to consider too much about it, only for a reference.

#include <stdio.h>
#include <string.h>
#include "dictionary.h"

void print(void *dictionary)
{
    printf("Original: {");
    void *element = minimum(dictionary);
    while (element != NULL)
    {
        int key = getkey(element);
        int value = getvalue(element);
        printf("%d:%d, ", key, value);
        element = successor(dictionary, key);
    }
    printf("}.\n");
}

void print_reverse(void *dictionary)
{
    printf("Reversed: {");
    void *element = maximum(dictionary);
    while (element != NULL)
    {
        int key = getkey(element);
        int value = getvalue(element);
        printf("%d:%d, ", key, value);
        element = predecessor(dictionary, key);
    }
    printf("}.\n");
}


int main()
{
    void *dictionary = initializer();
    int n; // n is the number of operations performed to the dictionary
    scanf("%d", &n);
    char buffer[100];
    for (int i = 0; i < n; ++i)
    {
        printf("%d\n", i);
        scanf("%s", buffer);
        if (strcmp(buffer, "insert") == 0)
        {
            int key, value;
            scanf("%d", &key);
            scanf("%d", &value);
            insert(dictionary, key, value);
        } else if (strcmp(buffer, "delete") == 0)
        {
            int key;
            scanf("%d", &key);
            delete(dictionary, key);
        } else if (strcmp(buffer, "search") == 0)
        {
            int key;
            scanf("%d", &key);
            void* element=search(dictionary, key);
            if(element!=NULL)
            {
                int value=getvalue(element);
                printf("The value is %d.\n",value);
            }
        }
        printf("***Print Dictionary***\n");
        print(dictionary);
        print_reverse(dictionary);
        printf("****Print Finished****\n");
    }
    free_dict(dictionary);
    return 0;
}

IO format

Input

the number of operations \(n\) on the first line.
an operation on the next \(n\) lines

Output

the ordered dictionary at that time.
try the test program yourselves to get the output

Sample IO

Input

1
insert 0 0

Output

0
***Print Dictionary***
Original: {0:0, }.
Reversed: {0:0, }.
****Print Finished****