INVENTORS: September 2017

Place this in an header file, called list.h

/*
* File:   list.h
* Author: hp
*
* Created on September 3, 2017, 2:41 AM
*/

#ifndef LIST_H
#define    LIST_H

#ifdef    __cplusplus
extern "C" {
#endif

typedef struct Node {
    struct Node* next;
    struct Node* prev;
    void* val;
}Node;

typedef struct List {
     int length;
    struct Node* firstNode;
    struct Node* lastNode;
    struct List* subList;

    struct List* parent;

    //This indices are -1 if the sublist field is NULL
    int startIndex;
    int endIndex;
}List;

List* newList();
Node* initNode(Node* prev, void* val, Node* next);
void ToArray(List* list,void* result[]) ;
void addNode(List* list,Node *elem);
void AddArray(List* list, void* *array, int len);
void Add(List* list,void* val);
bool addNodeAt(List* list,Node* elem,int index );
bool AddVal(List* list,void* val, int index);
bool removeNode(List* list,Node* elem);
void RemoveAll(List* list,List* lst);
bool AddAll(List* list,List* lst);
bool IsEmpty(List* list);
bool AddAllAt(List* list,int index, List *lst);
bool Remove(List* list,void* val);
bool RemoveIndex(List* list,int index);
List* SubList(List* list,int startIndex, int endIndex);
Node* getNode(List* list,int index);
void* Get(List* list,int index);
Node* getLastNode(List* list);
void* LastElement(List* list);
int IndexOf(List* list,void* val);
bool isSubList(List* list);
/**
*
* Pass the list and an empty array of size 2. When the function returns, the array contains pointers to the boundary nodes
*/
void getBoundaryNodes(List* list,Node* bounds[]);
int indexOfNode(List* list,Node* node);
bool containsNode(List* list,Node* node);
void prepend(List* list,void* val);
void append(List* list,void* val);
Node* insertBefore(List* list,void* e, Node* succ);
Node* insertAfter(List* list, void* e, Node* succ);
bool Contains(List* list,void* val);

void Clear(List* list);
void removeLinkedRange(List* list, Node* startNode, Node* stopNode);
void Log(List* list,char* optionalLabel);

void syncRemoval(List* list, int index);
void syncAdditions(List* list, int index);
char* concatStrAndInt(char* str, int val);
char* concat(char*str, char* str1);
char* prependInt(int num, char* str2);
char* appendInt( char* str , int num);
char* concatOnInt( char* str , int num, char* str2);




#ifdef    __cplusplus
}
#endif

#endif    /* LIST_H */

Now, save this in another file called list.c

#include
#include
#include
#include
#include "booldef.h"
#include "list.h"
#include

List* newList() {

    List* list = (List*) malloc(sizeof (List));

    list->length = 0;
    list->firstNode = NULL;
    list->lastNode = NULL;
    list->subList = NULL;
    list->parent = NULL;
    list->startIndex = -1;
    list->endIndex = -1;

    return list;
}

Node* initNode(Node* prev, void* val, Node* next) {
    Node* node = (Node*) malloc(sizeof (Node));
    if (node == NULL) {
        printf("Error creating a new node.\n");
        exit(0);
    }
    node->prev = prev;
    node->next = next;
    node->val = val;

    return node;
}

//[]int{1,4,293,4,9}
//TESTED

bool isSubList(List* list) {
    return list->parent != NULL;
}

/**
*
* @param list The Linked list
* @param result An array initialized to the size of the linked list
* @return the passed array with the contents of the Linked List
*/
void ToArray(List* list, void* result[]) {

    if (isSubList(list)) {

        int i = 0;
        Node* x = getNode(list->parent, list->startIndex);
        for (; i < list->length; x = x->next) {
            result[i] = x->val;
            i++;
        }
        return;
    } else {

        int i = 0;
        for (Node *x = list->firstNode; x != NULL; x = x->next) {
            result[i] = x->val;
            i++;
        }
        return;
    }

}

//TESTED

void addNode(List* list, Node* elem) {

    if (isSubList(list)) {

        addNodeAt(list->parent, elem, list->endIndex);
        list->length++;
        list->endIndex++;

    } else {

        Node* oldLastNode = list->lastNode;

        list->lastNode = elem;
        if (oldLastNode == NULL) {
            list->firstNode = elem;
        } else {
            oldLastNode->next = elem;
            elem->prev = oldLastNode;
        }
        list->length++;

    }
}

//TESTED

//TESTED

void AddArray(List* list, void* *array, int len) {

    if (isSubList(list)) {

        Node* endNode = initNode(NULL, NULL, NULL);
        bool skipFirst = false;

        if (IsEmpty(list)) {
            if (list->startIndex == 0) {
                endNode = insertBefore(list->parent, *array, list->parent->firstNode);
                list->length++;
                list->endIndex++;
                skipFirst = true;
            } else {
                endNode = getNode(list->parent, list->startIndex - 1);
            }

        } else {
            endNode = getNode(list, list->length - 1);
        }

        if (skipFirst) {
            *(array++);
        }
        for (int i = 0; i < len; i++) {
            endNode = insertAfter(list->parent, *(array++), endNode);
            list->length++;
            list->endIndex++;

        }

    } else {
        for (int i = 0; i < len; i++) {
            append(list, *(array++));
        }

    }

}

//TESTED

void Add(List* list, void* val) {
    if (isSubList(list)) {

        if (list->length == 0) {
            AddVal(list->parent, val, list->startIndex);
        } else {
            AddVal(list->parent, val, list->endIndex);
        }
        //list->parent.AddVal(val, list->endIndex+1)
        list->length++;
        list->endIndex++;
    } else {
        append(list, val);
    }

}
/**
* Only parent lists should ever call this function!
* @param list The list
* @param elem The node to add
* @param index The index at which the node is to be added
* @return true if the node was added successfully
*/
//TESTED

bool addNodeAt(List* list, Node* elem, int index) {

    if (list->parent == NULL) {
        if (index == list->length) {
            addNode(list, elem);
        } else {

            Node* succ = getNode(list, index);

            // assert succ != NULL;
            Node* prev = succ->prev;

            elem->prev = succ->prev;
            elem->next = succ;
            succ->prev = elem;

            if (prev == NULL) {
                list->firstNode = elem;
            } else {
                prev->next = elem;
            }
            list->length++;
        }
        syncAdditions(list, index);

        return true;
    }
    return false;

}

//TESTED

bool AddVal(List* list, void* val, int index) {

    if (isSubList(list)) {
        bool success = AddVal(list->parent, val, index + list->startIndex);
        list->length++;
        list->endIndex++;
        return success;

    } else {
        Node* elem = initNode(NULL, NULL, NULL);
        elem->next = NULL;
        elem->val = val;

        return addNodeAt(list, elem, index);
    }

}

bool removeNode(List* list, Node* elem) {

    if (isSubList(list)) {

        if (containsNode(list, elem)) {

            bool succ = removeNode(list->parent, elem);
            list->length--;
            list->endIndex--;
            return succ;

        }
        return false;
    } else {

        Node* next = elem->next;
        Node* prev = elem->prev;

        if (prev == NULL) {
            list->firstNode = next;
        } else {
            prev->next = next;
            elem->prev = NULL;
        }

        if (next == NULL) {
            list->lastNode = prev;
        } else {
            next->prev = prev;
            elem->next = NULL;
        }

        elem->val = NULL;
        list->length--;
        return true;
    }

}

//TESTED

void RemoveAll(List* list, List* lst) {
    //empty list

    if (isSubList(list)) {

        Node* x = initNode(NULL, NULL, NULL);
        if (isSubList(lst)) {
            x = getNode(lst, 0);
        } else {
            x = lst->firstNode;
        }

        for (int i = 0; i < lst->length; i++) {
            Remove(list, x->val);
            x = x->next;
        }

    } else {

        Node* x = initNode(NULL, NULL, NULL);
        if (isSubList(lst)) {
            x = getNode(lst, 0);
        } else {
            x = lst->firstNode;
        }
        for (int i = 0; i < lst->length; i++) {
            Remove(list, x->val);
            x = x->next;
        }

    }
}

//TESTED

bool AddAll(List* list, List* lst) {

    //empty list

    if (isSubList(lst)) {
        if (lst->length == 0) {
            return false;
        }
    } else {
        if (lst->firstNode == NULL) {
            return false;
        }
    }

    return AddAllAt(list, list->length, lst);

}

bool IsEmpty(List* list) {
    return list->length == 0 && list->firstNode == NULL;
}

bool AddAllAt(List* list, int index, List* lst) {

    if (isSubList(list)) {
        bool succ = AddAllAt(list->parent, list->startIndex + index, lst);
        list->length += lst->length;
        list->endIndex = list->startIndex + list->length - 1;
        return succ;
    } else {

        //empty list
        if (lst->firstNode == NULL || index >= list->length || index < 0) {
            printf("Bad value for index or badly initialized list\n");
            return false;
        }

        int numNew = lst->length;
        if (numNew == 0) {
            return false;
        }
        Node* prev = initNode(NULL, NULL, NULL);
        Node* succ = initNode(NULL, NULL, NULL);
        if (index == list->length) {
            succ = NULL;
            prev = list->lastNode;
        } else {
            succ = getNode(list, index);
            prev = succ->prev;
        }

        Node* x = lst->firstNode;

        for (int i = 0; i < numNew; i++) {
            void* e = x->val;
            Node* newNode = initNode(prev, e, NULL);
            if (prev == NULL) {
                list->firstNode = newNode;
            } else {
                prev->next = newNode;
            }
            prev = newNode;
            x = x->next;
        }

        if (succ == NULL) {
            list->lastNode = prev;
        } else {
            prev->next = succ;
            succ->prev = prev;
        }

        list->length += numNew;
        return true;
    }
}

/**
* Remove the first node that has
* the same value as the parameter
*/
bool Remove(List*list, void* val) {

    if (isSubList(list)) {
        int ind = IndexOf(list, val);
        if (ind == -1) {
            return false;
        } else {
            RemoveIndex(list, ind);

            list->length--;
            list->endIndex--;
            return true;
        }

    } else {
        //empty list
        if (list->firstNode == NULL) {
            return false;
        }

        Node* x = list->firstNode;
        for (int i = 0; i < list->length; i++) {
            if (x->val == val) {
                bool succ = removeNode(list, x);

                if (succ) {
                    syncRemoval(list, i);
                }

                return succ;

            }

            x = x->next;
        }

        return false;
    }

}

bool RemoveIndex(List* list, int index) {

    if (isSubList(list)) {
        return RemoveIndex(list->parent, index + list->startIndex);
    } else {

        Node* x = list->firstNode;
        for (int i = 0; i <= index; i++) {
            if (index == i) {

                bool succ = removeNode(list, x);

                if (succ) {
                    syncRemoval(list, index);
                }

                return succ;
            }
            x = x->next;

        }
        return false;

    }
}

/**
* Reflects changes in the parent list on the sublist when removals are made from the parent list
*/
void syncRemoval(List* list, int index) {
    if (list->subList != NULL) {

        if (index <= list->subList->startIndex) {
            list->subList->startIndex--;
            list->subList->endIndex--;
        } else if (index > list->subList->startIndex && index <= list->subList->endIndex) {
            list->subList->endIndex--;
            list->subList->length--;
        }

    }
}

/**
* Reflects changes in the parent list on the sublist when additions are made to the parent list
*/
void syncAdditions(List* list, int index) {
    if (list->subList != NULL) {

        if (index <= list->subList->startIndex) {
            list->subList->startIndex++;
            list->subList->endIndex++;
        } else if (index > list->subList->startIndex && index <= list->subList->endIndex) {
            list->subList->endIndex++;
            list->subList->length++;
        }

    }
}
//Not backed
//Calling obj, Methodname, firstparam, secondparam return type

List* SubList(List* list, int startIndex, int endIndex) {

    if (endIndex > list->length) {

        printf("endIndex(%d) > list-length(%d) is not allowed\n", endIndex, list->length);
        return NULL;
    }

    if (startIndex < 0) {
        printf("%d < 0 \n", startIndex);
        return NULL;
    }
    if (endIndex < 0) {
        printf("%d < 0 is not allowed\n", endIndex);
        return NULL;
    }
    if (isSubList(list)) {
        printf("Sublist Chaining not allowed. Sublists of sublists cannot be made\n");
        return NULL;
    }

    list->subList = newList();
    list->subList = newList();
    list->subList->firstNode = NULL;
    list->subList->lastNode = NULL;
    list->subList->parent = list;

    list->subList->length = endIndex - startIndex;

    list->subList->startIndex = startIndex;
    list->subList->endIndex = endIndex - 1;

    return list->subList;

}

/**
* Returns the (non-NULL) Node at the specified element index.
*/
Node* getNode(List* list, int index) {
    if (index < 0) {
        printf("Index=(%d) < 0 is not allowed\n", index);
        return NULL;
    }

    if (index > list->length) {
        printf("Index=(%d) > list-length(%d) is not allowed\n", index, list->length);
        return NULL;
    }

    if (isSubList(list)) {
        return getNode(list->parent, list->startIndex + index);
    }

    // NOTE x >> y is same as x ÷ 2^y

    if (index < (list->length >> 1)) {
        Node *x = list->firstNode;
        for (int i = 0; i < index; i++) {
            x = x->next;
        }
        return x;
    } else {
        Node *x = list->lastNode;
        for (int i = list->length - 1; i > index; i--) {
            x = x->prev;
        }
        return x;
    }
}

/**
* Returns the (non-NULL) Node at the specified element index.
* The bounds parameter is a pointer to an array that will hold the
* pointers to the boundary nodes
*/
void getBoundaryNodes(List* list, Node* bounds[]) {

    if (isSubList(list)) {

        int start = list->startIndex;
        int end = list->endIndex;

        Node* first = getNode(list, 0);
        Node* last = initNode(NULL, NULL, NULL);

        Node* x = first;

        int i = start;

        if (list->length > list->parent->length - list->endIndex) {

            last = getLastNode(list);

        } else {
            for (; i < end; i++) {
                x = x->next;
            }
            last = x;

        }
        bounds[0] = first;
        bounds[1] = last;

    } else {
        bounds[0] = list->firstNode;
        bounds[1] = list->lastNode;

    }

}

void* Get(List* list, int index) {
    return getNode(list, index)->val;

}

Node* getLastNode(List* list) {
    if (isSubList(list)) {
        return getNode(list->parent, list->endIndex);
    } else {
        return list->lastNode;
    }
}

void* LastElement(List* list) {
    return getLastNode(list)->val;
}

int IndexOf(List* list, void* val) {

    if (isSubList(list)) {
        Node* startNode = getNode(list, 0);

        int i = 0;
        for (Node* x = startNode; i < list->length; x = x->next) {

            if (val == x->val) {
                return i;
            }
            i++;
        }
        return -1;

    } else {

        Node* x = list->firstNode;

        if (x->val == val) {
            return 0;
        }

        for (int i = 0; i < list->length; i++) {

            if (val == x->val) {
                return i;
            }

            x = x->next;
        }

        return -1;
    }

}

int indexOfNode(List* list, Node* node) {

    if (isSubList(list)) {
        Node* startNode = getNode(list, 0);

        int i = 0;
        for (Node* x = startNode; i < list->length; x = x->next) {

            if (node == x) {
                return i;
            }
            i++;
        }
        return -1;

    } else {

        Node* x = list->firstNode;

        if (x == node) {
            return 0;
        }

        for (int i = 0; i < list->length; i++) {

            if (node == x) {
                return i;
            }

            x = x->next;
        }

        return -1;
    }

}

bool Contains(List* list, void* val) {
    return IndexOf(list, val) != -1;
}

bool containsNode(List* list, Node* node) {
    return indexOfNode(list, node) != -1;
}

/**
* Links val as first element.
*/
void prepend(List* list, void* val) {
    Node* f = list->firstNode;
    Node* newNode = initNode(NULL, val, f);
    list->firstNode = newNode;
    if (f == NULL) {
        list->lastNode = newNode;
    } else {
        f->prev = newNode;
    }
    list->length++;
}

/**
* Links val as last element.
*/
void append(List* list, void* val) {
    Node* l = list->lastNode;
    Node* newNode = initNode(l, val, NULL);
    list->lastNode = newNode;
    if (l == NULL) {
        list->firstNode = newNode;
    } else {
        l->next = newNode;
    }
    list->length++;
}

/**
* Inserts element e before non-null Node succ.
* ONLY TO BE CALLED BY BASE PARENT LISTS
* Return a pointer to the new node that was inserted.
* This will help with spontaneous insertions
*/
Node* insertBefore(List* list, void* e, Node* succ) {

    Node* prev = succ->prev;

    Node* newNode = initNode(prev, e, succ);

    succ->prev = newNode;
    if (prev == NULL) {
        list->firstNode = newNode;
    } else {
        prev->next = newNode;
    }
    list->length++;
    return newNode;
}

/**
* Inserts element e after non-null Node succ.
*
* ONLY TO BE CALLED BY BASE PARENT LISTS
* Return a pointer to the new node that was inserted.
* This will help with spontaneous insertions
*/
Node* insertAfter(List* list, void* e, Node* succ) {
    Node* next = succ->next;
    Node* newNode = initNode(succ, e, succ->next);
    succ->next = newNode;
    if (next == NULL) {
        list->lastNode = newNode;
    } else {
        next->prev = newNode;
    }
    list->length++;
    return newNode;
}

void Clear(List* list) {

    if (isSubList(list)) {
        Node * bounds[2];
        getBoundaryNodes(list, bounds);
        Node* begin = bounds[0];
        Node* end = bounds[1];
        //The node just before this sublist's first node
        Node* leftBound = begin->prev;

        //The node just after this range's last node
        Node* rightBound = end->next;

        if (leftBound != NULL) {
            leftBound->next = rightBound;
        } else {
            list->parent->firstNode = rightBound;
        }

        if (rightBound != NULL) {
            rightBound->prev = leftBound;
        } else {
            list->parent->lastNode = leftBound;
        }

        removeLinkedRange(list, begin, end);

        list->parent->length -= list->length;
        list->endIndex = list->startIndex;
        list->length = 0;

    } else {
        Node* x = list->firstNode;

        for (; x != NULL;) {
            Node* next = x->next;
            x->val = NULL;
            x->next = NULL;
            x->prev = NULL;
            x = next;
        }

        list->firstNode = NULL;
        list->lastNode = NULL;
        list->length = 0;

        if (list->subList != NULL) {
            list->subList->startIndex = 0;
            list->subList->endIndex = 0;
            list->subList->length = 0;
        }
    }

}

void removeLinkedRange(List* list, Node* startNode, Node* stopNode) {

    for (Node* x = startNode; x != stopNode; x = x->next) {

        x->val = NULL;
        if (x != startNode) {
            x->prev = NULL;
        }

    }

}

void Log(List* list, char* optionalLabel) {

    void* res[list->length];

    ToArray(list, res);

    printf("\n%s:\n [", optionalLabel);
    int ctr = 0;
    for (int i = 0; i < list->length; i++) {
        printf("%d, ", *(res + ctr++));
    }
    printf("], len: %d, startIndex: %d, endIndex: %d\n", list->length, list->startIndex, list->endIndex);

}

char* concatStrAndInt(char* str, int val) {
    sprintf(str, "%d", val);
    return str;
}

char* concat(char* str, char* str2) {
    while (*str) str++;
    while (*str++ = *str2++);
    return --str;
}

char* prependInt(int num, char* str2) {
    char* str = concatStrAndInt("", num);

    return concat(str, str2);
}

char* appendInt(char* str, int num) {

    char* str2 = concatStrAndInt("", num);

    return concat(str, str2);
}

char* concatOnInt(char* str, int num, char* str2) {

    char* str1 = concatStrAndInt(str, num);

    return concat(str1, str2);
}

/**
void dispose(node *head)
{
    node *cursor, *tmp;

    if(head != NULL)
    {
        cursor = head->next;
        head->next = NULL;
        while(cursor != NULL)
        {
            tmp = cursor->next;
            free(cursor);
            cursor = tmp;
        }
    }
}
*/

This is the code for the doubly-linked linked list.

Now create a c file called listmain.c that will test the list:

void quickAddInt(List* list , int num){
void* num_ptr = #
Add(list , num_ptr);
}

int main() {

List* list = newList();

Add(list, (void *)3);
Add(list, (void *)8);

srand(time(0));
int TEST_SIZE = 25;

int n = 200000;
/* Assign pointers into appropriate parts of matrix. */
for (int i = 0; i < TEST_SIZE; i++) {
int rnd = rand() % n;
void* p = &rnd;
Add(list , p);
}

List* small_list = SubList(list , 5 , 12);

Log(list, "LIST");
Log(small_list, "SUB list");

Clear(small_list);

Log(list, "AFTER CLEARING SUB, list");
Log(small_list, "SUB list");

List* second = newList();
quickAddInt(second , 5);
quickAddInt(second , 205);
quickAddInt(second , 502);
quickAddInt(second , 45);
quickAddInt(second , 67);
quickAddInt(second , 99);
quickAddInt(second , 510);
quickAddInt(second , 1020);
quickAddInt(second , 5008);
quickAddInt(second , 30042);
quickAddInt(second , 20014);
quickAddInt(second , 30041);
quickAddInt(second , 10518902);

Log(second, "SECOND list");

AddAll(small_list, second);

Log(small_list, "ADD second_list to SUB list...SUB list is now");
Log(list, "LIST is now");

void* arr[9] = {(void*)10,(void*)4,(void*)1,(void*)9,(void*)8,(void*)12,(void*)34,(void*)4,(void*)58};
int siz = sizeof(arr)/sizeof(arr[0]);
AddArray( small_list , arr, siz );

Log(small_list, "AddValues called on SUB list...SUB list is now");
Log(list, "LIST is now");

void* array[4] = {(void*)1245,(void*)90,(void*)42,(void*)89};
AddArray(list , array ,4);

Log(list, "LIST");

RemoveAll(list, SubList(second,0,7));

Log(list, "LIST");

return (EXIT_SUCCESS);
}

INVENTORS

Monday, September 11, 2017

LinkedList implementation in C with java.util.ArrayList like sublist capability

LinkedList implementation in C with java.util.ArrayList like sublist capability

Followers

My Blog List