This shows you the differences between two versions of the page.
— |
library:adt [2017/03/24 07:12] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== ABSTRACT DATA TYPES LIBRARY (adt.h, adt.lib) ====== | ||
+ | |||
+ | ^ Header | ||
+ | ^ Source | ||
+ | ^ Include | ||
+ | ^ Linking | ||
+ | ^ Compile | ||
+ | ^ Comments | ||
+ | ^ | performing their functions. | ||
+ | ^ | do so through user-supplied functions as documented on the [[library: | ||
+ | ^ | **2.** Some of the data structures in this library make use of the IX and IY register pairs which can | | ||
+ | ^ | be a problem for some z80 targets. | ||
+ | |||
+ | The [[http:// | ||
+ | |||
+ | Data structures included in this library: | ||
+ | |||
+ | * AVL Tree (not implemented yet, dynamic, a balanced binary tree) | ||
+ | * Byte Circular Buffer (not implemented yet, static, a byte-indexed array) | ||
+ | * Word Circular Buffer (not implemented yet, static, a word-indexed array) | ||
+ | * [[adt# | ||
+ | * Singly Linked List (not implemented yet, static, a single pointer buried in user structs) | ||
+ | * Static Hash Table (not implemented yet, static, an array) | ||
+ | * [[adt# | ||
+ | * Map (not implemented yet, dynamic, using AVL tree) | ||
+ | * [[adt# | ||
+ | * [[adt# | ||
+ | |||
+ | ====== Doubly Linked List (dynamic) ====== | ||
+ | |||
+ | A [[http:// | ||
+ | |||
+ | This linked list type maintains a single internal pointer called the ' | ||
+ | |||
+ | ===== List API ===== | ||
+ | |||
+ | **1. adt_ListCreate()** ; //O(1)// | ||
+ | |||
+ | Creates an empty list and returns a pointer to the list structure. | ||
+ | |||
+ | <code c> | ||
+ | struct adt_List *adt_ListCreate(void); | ||
+ | </ | ||
+ | |||
+ | **2. adt_ListDelete()** ; //O(N)// ; //Uses IX// | ||
+ | |||
+ | Deletes the list. The list handle will be deallocated and will no longer be valid. | ||
+ | |||
+ | <code c> | ||
+ | void adt_ListDelete(struct adt_List *list, void *delete); | ||
+ | // list = pointer to list handle | ||
+ | // delete = void (*delete)(void *item) | ||
+ | // For each item in the list, this function is called with the item as parameter. | ||
+ | // This is meant as an opportunity for user-cleanup of items that are in a non-empty list. | ||
+ | // Set delete = 0 to do no user cleanup on items. | ||
+ | </ | ||
+ | |||
+ | **3. adt_ListCreateS()** ; //O(1)// | ||
+ | |||
+ | Initializes an existing struct_adt_List to create an empty list. This static create option is offered as an alternative to the dynamic version in order to simplify the implicit memory allocation function u_malloc() so that it only has to worry about allocating list nodes. | ||
+ | |||
+ | <code c> | ||
+ | void adt_ListCreateS(struct adt_List *list); | ||
+ | // list = pointer to an exiting struct_adt_List | ||
+ | </ | ||
+ | |||
+ | **4. adt_ListDeleteS()** ; //O(N)// ; //Uses IX// | ||
+ | |||
+ | Deletes the list. The list handle will not be deallocated but will no longer be valid. | ||
+ | |||
+ | <code c> | ||
+ | void adt_ListDeleteS(struct adt_List *list, void *delete); | ||
+ | // list = pointer to list handle | ||
+ | // delete = void (*delete)(void *item) | ||
+ | // For each item in the list, this function is called with the item as parameter. | ||
+ | // This is meant as an opportunity for user-cleanup of items that are in a non-empty list. | ||
+ | // Set delete = 0 to do no user cleanup on items. | ||
+ | </ | ||
+ | |||
+ | **5. adt_ListCount()** ; //O(1)// | ||
+ | |||
+ | Returns number of items in list. | ||
+ | |||
+ | <code c> | ||
+ | unsigned int adt_ListCount(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **6. adt_ListPushBack() //alias adt_ListAppend()// | ||
+ | |||
+ | Adds item to the end of the list. u_malloc is called to allocate a 6-byte node to hold the item. If allocation fails the item is not added to the list and 0 is returned to report failure. | ||
+ | |||
+ | <code c> | ||
+ | int adt_ListPushBack(struct adt_List *list, void *item); | ||
+ | int adt_ListAppend(struct adt_List *list, void *item); | ||
+ | // list = pointer to list handle | ||
+ | // item = item to add to list | ||
+ | </ | ||
+ | |||
+ | **7. adt_ListPushFront() //alias adt_ListPrepend()// | ||
+ | |||
+ | Adds item to the beginning of the list. u_malloc is called to allocate a 6-byte node to hold the item. If allocation fails the item is not added to the list and 0 is returned to report failure. | ||
+ | |||
+ | <code c> | ||
+ | int adt_ListPushFront(struct adt_List *list, void *item); | ||
+ | int adt_ListPrepend(struct adt_List *list, void *item); | ||
+ | // list = pointer to list handle | ||
+ | // item = item to add to list | ||
+ | </ | ||
+ | |||
+ | **8. adt_ListAdd()** ; //O(1)// | ||
+ | |||
+ | Adds item after the the item pointed at by the list's current pointer. | ||
+ | |||
+ | <code c> | ||
+ | int adt_ListAdd(struct adt_List *list, void *item); | ||
+ | // list = pointer to list handle | ||
+ | // item = item to add to list | ||
+ | </ | ||
+ | |||
+ | **9. adt_ListInsert()** ; //O(1)// | ||
+ | |||
+ | Adds item before the item pointed at by the list's current pointer. | ||
+ | |||
+ | <code c> | ||
+ | int adt_ListInsert(struct adt_List *list, void *item); | ||
+ | // list = pointer to list handle | ||
+ | // item = item to add to list | ||
+ | </ | ||
+ | |||
+ | **10. adt_ListFirst()** ; //O(1)// | ||
+ | |||
+ | Makes the list's current pointer point at the first item in the list. Returns the first item or 0 if the list is empty. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListFirst(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **11. adt_ListLast()** ; //O(1)// | ||
+ | |||
+ | Makes the list's current pointer point at the last item in the list. Returns the last item or 0 if the list is empty. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListLast(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **12. adt_ListNext()** ; //O(1)// | ||
+ | |||
+ | Moves the list's current pointer to the next item in the list. Returns this next item or 0 if the current pointer has moved past the end of the list. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListNext(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **13. adt_ListPrev()** ; //O(1)// | ||
+ | |||
+ | Moves the list's current pointer to the previous item in the list. Returns this previous item or 0 if the current pointer has moved past the beginning of the list. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListPrev(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **14. adt_ListCurr()** ; //O(1)// | ||
+ | |||
+ | Returns the item pointed at by the list's current pointer. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListCurr(struct adt_List *list); | ||
+ | // list = pointer too list handle | ||
+ | </ | ||
+ | |||
+ | **15. adt_ListRemove()** ; //O(1)// | ||
+ | |||
+ | Removes the item pointed at by the list's current pointer. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListRemove(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **16. adt_ListPopBack() //alias adt_ListTrim()// | ||
+ | |||
+ | Removes the item at the end of the list and returns it. If the list is empty, 0 is returned and the carry flag is reset. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListPopBack(struct adt_List *list); | ||
+ | void *adt_ListTrim(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **17. adt_ListPopFront()** ; //O(1)// | ||
+ | |||
+ | Removes the item at the front of the list and returns it. If the list is empty, 0 is returned and the carry flag is reset. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListPopFront(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **18. adt_ListConcat()** ; //O(1)// | ||
+ | |||
+ | Concatenates list2 to the end of list1. | ||
+ | |||
+ | <code c> | ||
+ | void adt_ListConcat(struct adt_List *list1, struct adt_List *list2); | ||
+ | // list1 = pointer to list handle | ||
+ | // list2 = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **19. adt_ListSetCurrBefore()** ; //O(1)// | ||
+ | |||
+ | Sets the list's current pointer to point before the start of the list. | ||
+ | |||
+ | <code c> | ||
+ | void adt_ListSetCurrBefore(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **20. adt_ListSetCurrAfter()** ; //O(1)// | ||
+ | |||
+ | Sets the list's current pointer to point after the end of the list. | ||
+ | |||
+ | <code c> | ||
+ | void adt_ListSetCurrAfter(struct adt_List *list); | ||
+ | // list = pointer to list handle | ||
+ | </ | ||
+ | |||
+ | **21. adt_ListSetCurr()** ; //O(1)// | ||
+ | |||
+ | Set the list's current pointer to point at a specific node in the list. This node must be a part of the list and may be obtained from a previous position of the current pointer directly from the struct adt_List. | ||
+ | |||
+ | <code c> | ||
+ | void adt_ListSetCurr(struct adt_List *list, struct adt_ListNode *n); | ||
+ | // list = pointer to list handle | ||
+ | // n = pointer to struct adt_ListNode ; if 0 the list's current pointer is unchanged | ||
+ | </ | ||
+ | |||
+ | **22. adt_ListSearch()** ; //O(N)// ; //Uses IX, IY// | ||
+ | |||
+ | Searches the list FROM THE LIST'S CURRENT POINTER (this is easy to forget; to search the entire list call adt_ListFirst() or adt_ListSetCurrBefore() first). | ||
+ | |||
+ | <code c> | ||
+ | void *adt_ListSearch(struct adt_List *list, void *match, void *item1); | ||
+ | // list = pointer to list handle | ||
+ | // item1 = item to be matched in list | ||
+ | // match = char (*match)(void *item1, void *item2) | ||
+ | // | ||
+ | // This will terminate the list search and return item2 as result. | ||
+ | </ | ||
+ | |||
+ | ===== Code Example 1 ===== | ||
+ | |||
+ | Declarations of the functions u_malloc() and u_free() which perform memory allocation on behalf of the ADT library are not shown. | ||
+ | |||
+ | This code snippet shows a subroutine that takes as input a list and an index N. The subroutine returns the Nth item in the list. adt_ListSearch() is used to perform an iteration over all items in the list, only stopping when the helper function determines that N-1 items have already been passed over. N=0 is used to select the first item in the list. | ||
+ | |||
+ | <code c> | ||
+ | int selectnth_helper(uint *n, void *item) | ||
+ | { | ||
+ | | ||
+ | } | ||
+ | |||
+ | void *SelectNthInList(struct adt_List *ls, int n) | ||
+ | { | ||
+ | adt_ListSetCurrBefore(ls); | ||
+ | return (adt_ListSearch(ls, | ||
+ | } | ||
+ | |||
+ | // example usage | ||
+ | |||
+ | item = SelectNthInList(ls, | ||
+ | </ | ||
+ | |||
+ | ===== Code Example 2 ===== | ||
+ | |||
+ | Declarations of the functions u_malloc() and u_free() which perform memory allocation on behalf of the ADT library are not shown. | ||
+ | |||
+ | This subroutine example takes an unsorted list of items and sorts the list according to a user-provided criteria function. | ||
+ | |||
+ | <code c> | ||
+ | struct adt_List *SortList(struct adt_List *ls, void *criteria) | ||
+ | { | ||
+ | | ||
+ | | ||
+ | uint min, val; | ||
+ | |||
+ | | ||
+ | |||
+ | while (adt_ListCount(ls)) { | ||
+ | | ||
+ | min = (criteria)(adt_ListFirst(ls)); | ||
+ | position = ls-> | ||
+ | | ||
+ | while (adt_ListNext(ls)) { | ||
+ | | ||
+ | val = (criteria)(adt_ListCurr(ls)); | ||
+ | if (val < min) { | ||
+ | min = val; | ||
+ | position = ls-> | ||
+ | } | ||
+ | |||
+ | } | ||
+ | | ||
+ | adt_ListSetCurr(ls, | ||
+ | adt_ListAppend(newlist, | ||
+ | | ||
+ | } | ||
+ | |||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | // example usage | ||
+ | |||
+ | struct { | ||
+ | uint cost; | ||
+ | char *name; | ||
+ | } myItems; | ||
+ | |||
+ | struct adt_List *ls; // list of myItems | ||
+ | |||
+ | uint myCriteria(struct myItems *i) | ||
+ | { | ||
+ | | ||
+ | } | ||
+ | |||
+ | ls = SortList(ls, | ||
+ | </ | ||
+ | |||
+ | ===== Code Example 3 ===== | ||
+ | |||
+ | Declarations of the functions u_malloc() and u_free() which perform memory allocation on behalf of the ADT library are not shown. | ||
+ | |||
+ | This subroutine example shuffles a list into random order. | ||
+ | |||
+ | <code c> | ||
+ | uint RND(uint range) { | ||
+ | | ||
+ | } | ||
+ | |||
+ | struct adt_List *ShuffleList(struct adt_List *ls) | ||
+ | { | ||
+ | | ||
+ | uint n; | ||
+ | |||
+ | | ||
+ | |||
+ | while (n = adt_ListCount(ls)) { | ||
+ | |||
+ | SelectNthInList(ls, | ||
+ | adt_ListAppend(newlist, | ||
+ | | ||
+ | } | ||
+ | |||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | // example usage | ||
+ | |||
+ | ls = ShuffleList(ls); | ||
+ | </ | ||
+ | |||
+ | ====== Heap (static) ====== | ||
+ | |||
+ | A [[http:// | ||
+ | |||
+ | This heap implementation maintains the heap as an array of void*. | ||
+ | |||
+ | The heap algorithm is conducive to using array indices starting at 1 rather than the usual C array which uses 0 as the initial index. | ||
+ | |||
+ | ===== Heap API ===== | ||
+ | |||
+ | **1. adt_Heapify()** ; // | ||
+ | |||
+ | Takes an array of unsorted items as input and sorts it into a heap. | ||
+ | |||
+ | <code c> | ||
+ | void adt_Heapify(void **array, uint n, void *compare); | ||
+ | // array = address of an array of void* | ||
+ | // n = number of items in the array | ||
+ | // compare = char (*compare)(void **item1, void **item2) | ||
+ | // | ||
+ | // | ||
+ | // NOTE: item1 and item2 are addresses within the array not the void* values stored in the array | ||
+ | </ | ||
+ | |||
+ | **2. adt_HeapAdd()** ; // | ||
+ | |||
+ | Adds the item to the heap and increases N by one. | ||
+ | |||
+ | <code c> | ||
+ | void adt_HeapAdd(void *item, void **array, uint *n, void *compare); | ||
+ | // item = item to add to heap | ||
+ | // array = address of an array of void* that is a valid heap | ||
+ | // n = address of an integer holding the number of items in the array | ||
+ | // compare = char (*compare)(void **item1, void **item2) | ||
+ | // | ||
+ | // | ||
+ | // NOTE: item1 and item2 are addresses within the array not the void* values stored in the array | ||
+ | </ | ||
+ | |||
+ | **3. adt_HeapExtract()** ; // | ||
+ | |||
+ | Removes and returns the largest item (max heap) or smallest item (min heap) from the array and decreases N by one. If the heap was | ||
+ | empty to start with, zero is returned. | ||
+ | item in the heap). | ||
+ | |||
+ | This function also writes the extracted item into the end of the heap array where a vacant slot is created by the removal of one | ||
+ | item from the heap. A side effect of this operation is that if the heap is emptied by extracting all items one after the other, | ||
+ | the array left behind will be sorted either in descending order for a min heap or in ascending order for a max heap. This is an | ||
+ | implementation of [[http:// | ||
+ | the end of this section. | ||
+ | processors, since it requires no extra memory or stack space to perform the sort whereas, in worst case, stack usage by quicksort | ||
+ | is proportional to the number of items being sorted. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_HeapExtract(void **array, uint *n, void *compare); | ||
+ | // array = address of an array of void* that is a valid heap | ||
+ | // n = address of an integer holding the number of items in the array | ||
+ | // compare = char (*compare)(void **item1, void **item2) | ||
+ | // | ||
+ | // | ||
+ | // NOTE: item1 and item2 are addresses within the array not the void* values stored in the array | ||
+ | </ | ||
+ | |||
+ | ===== Code Example ===== | ||
+ | |||
+ | <code c> | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | // Example command line compile with ZX Spectrum as target: | ||
+ | // zcc +zx -vn heap.c -o heap -ladt -lndos -create-app | ||
+ | |||
+ | unsigned int n; // number of items in heap | ||
+ | void *heap[101]; | ||
+ | |||
+ | int compare(int *a, int *b) // params passed in are addresses within the heap array | ||
+ | { // the void* stored in the heap array are interpretted as integers | ||
+ | if (*a < *b) | ||
+ | return -1; // this will be a min heap -- smallest items are extracted first | ||
+ | | ||
+ | } | ||
+ | |||
+ | main() | ||
+ | { | ||
+ | int i; | ||
+ | |||
+ | | ||
+ | |||
+ | for (i=1; i!=101; i++) | ||
+ | printf(" | ||
+ | n = 100; // there are 100 items in the heap | ||
+ | |||
+ | | ||
+ | |||
+ | | ||
+ | for (i=1; i!=101; i++) | ||
+ | printf(" | ||
+ | |||
+ | | ||
+ | |||
+ | while (n!=0) | ||
+ | printf(" | ||
+ | |||
+ | | ||
+ | |||
+ | for (i=1; i!=101; i++) | ||
+ | printf(" | ||
+ | |||
+ | | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ====== Stack (dynamic) ====== | ||
+ | |||
+ | A [[http:// | ||
+ | |||
+ | This stack implementation is a linked list of items with nodes holding each item dynamically allocated. | ||
+ | |||
+ | ===== Stack API ===== | ||
+ | |||
+ | **1. adt_StackCreate()** ; //O(1)// | ||
+ | |||
+ | Creates an empty stack and returns a pointer to the stack structure. | ||
+ | |||
+ | <code c> | ||
+ | struct adt_Stack *adt_StackCreate(void); | ||
+ | </ | ||
+ | |||
+ | **2. adt_StackDelete()** ; //O(N)// ; //Uses IX// | ||
+ | |||
+ | Deletes the stack, invalidating the stack handle. u_free() is called to deallocate memory used to store each user item in the stack. | ||
+ | |||
+ | <code c> | ||
+ | void adt_StackDelete(struct adt_Stack *s, void *delete); | ||
+ | // s = address of stack handle | ||
+ | // delete = void (*delete)(void *item) | ||
+ | // For each item in the stack, this function is called with an item as parameter. | ||
+ | // This is meant as an opportunity for user-cleanup of items that are in a non-empty stack. | ||
+ | // Set delete = 0 to do no user cleanup on items. | ||
+ | </ | ||
+ | |||
+ | **3. adt_StackCreateS()** ; //O(1)// | ||
+ | |||
+ | Initializes an existing struct_adt_Stack to create an empty stack. | ||
+ | |||
+ | <code c> | ||
+ | void adt_StackCreateS(struct adt_Stack *s); | ||
+ | // s = pointer to an existing struct_adt_Stack | ||
+ | </ | ||
+ | |||
+ | **4. adt_StackDeleteS()** ; //O(N)// ; //Uses IX// | ||
+ | |||
+ | Deletes the stack. | ||
+ | |||
+ | <code c> | ||
+ | void adt_StackDeleteS(struct adt_Stack *s, void *delete); | ||
+ | // s = address of stack handle | ||
+ | // delete = void (*delete)(void *item) | ||
+ | // For each item in the stack, this function is called with an item as parameter. | ||
+ | // This is meant as an opportunity for user-cleanup of items that are in a non-empty stack. | ||
+ | // Set delete = 0 to do no user cleanup on items. | ||
+ | </ | ||
+ | |||
+ | **5. adt_StackPush()** ; //O(1)// | ||
+ | |||
+ | Pushes the item onto the stack. | ||
+ | allocation is unsuccessful, | ||
+ | |||
+ | <code c> | ||
+ | int adt_StackPush(struct adt_Stack *s, void *item); | ||
+ | // s = address of stack handle | ||
+ | // item = item to be pushed onto stack | ||
+ | </ | ||
+ | |||
+ | **6. adt_StackPop()** ; //O(1)// | ||
+ | |||
+ | Pops the top item on the stack and returns it. If the stack was empty, zero is returned with the carry flag reset. | ||
+ | was popped, u_free() is called to free the stack node used to hold the user item. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_StackPop(struct adt_Stack *s); | ||
+ | // s = address of stack handle | ||
+ | </ | ||
+ | |||
+ | **7. adt_StackPeek()** ; //O(1)// | ||
+ | |||
+ | Returns the top item on the stack without popping it. If the stack was empty, zero is returned. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_StackPeek(struct adt_Stack *s); | ||
+ | // s = address of stack handle | ||
+ | </ | ||
+ | |||
+ | **8. adt_StackCount()** ; //O(1)// | ||
+ | |||
+ | Returns the number of items in the stack. | ||
+ | |||
+ | <code c> | ||
+ | unsigned int adt_StackCount(struct adt_Stack *s); | ||
+ | // s = address of stack handle | ||
+ | </ | ||
+ | |||
+ | ===== Code Example ===== | ||
+ | |||
+ | This example uses the standard malloc() and free() functions for memory allocations. | ||
+ | |||
+ | <code c> | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | // Example command line compile with ZX Spectrum as target: | ||
+ | // zcc +zx -vn stack.c -o stack -ladt -lndos -lmalloc -create-app | ||
+ | |||
+ | // variables | ||
+ | |||
+ | char str[] = "the quick brown fox jumped over the lazy dogs"; | ||
+ | struct adt_Stack *s; | ||
+ | |||
+ | // user-supplied malloc and free functions for use by libraries | ||
+ | // that perform implicit memory allocation | ||
+ | |||
+ | void *u_malloc(unsigned int size) | ||
+ | { | ||
+ | | ||
+ | } | ||
+ | |||
+ | void u_free(void *addr) | ||
+ | { | ||
+ | | ||
+ | } | ||
+ | |||
+ | // z88dk' | ||
+ | |||
+ | long heap; // malloc' | ||
+ | char marray[500]; | ||
+ | |||
+ | main() | ||
+ | { | ||
+ | char *p, c; | ||
+ | |||
+ | // initialize malloc' | ||
+ | |||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | // push chars of string onto stack | ||
+ | |||
+ | | ||
+ | |||
+ | s = adt_StackCreate(); | ||
+ | for (p = str; c = *p; p++) { | ||
+ | printf(" | ||
+ | adt_StackPush(s, | ||
+ | } | ||
+ | |||
+ | // popped letters off stack will be in reverse order | ||
+ | |||
+ | | ||
+ | |||
+ | while (c = (char)(adt_StackPop(s))) | ||
+ | printf(" | ||
+ | |||
+ | | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ====== Queue (dynamic) ====== | ||
+ | |||
+ | A [[http:// | ||
+ | |||
+ | This queue implementation is a linked list of items with nodes holding each item dynamically allocated. | ||
+ | |||
+ | ===== Queue API ===== | ||
+ | |||
+ | **1. adt_QueueCreate()** ; //O(1)// | ||
+ | |||
+ | Creates an empty queue and returns a pointer to the queue structure. | ||
+ | |||
+ | <code c> | ||
+ | struct adt_Queue *adt_QueueCreate(void); | ||
+ | </ | ||
+ | |||
+ | **2. adt_QueueDelete()** ; //O(N)// ; //Uses IX// | ||
+ | |||
+ | Deletes the queue, invalidating the queue handle. u_free() is called to deallocate memory used to store each user item in the queue. | ||
+ | |||
+ | <code c> | ||
+ | void adt_QueueDelete(struct adt_Queue *q, void *delete); | ||
+ | // q = address of queue handle | ||
+ | // delete = void (*delete)(void *item) | ||
+ | // For each item in the queue, this function is called with the item as parameter. | ||
+ | // This is meant as an opportunity for user-cleanup of items that are in a non-empty queue. | ||
+ | // Set delete = 0 to do no user cleanup on items. | ||
+ | </ | ||
+ | |||
+ | **3. adt_QueueCreateS()** ; //O(1)// | ||
+ | |||
+ | Initializes an existing struct_adt_Queue to create an empty queue. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_QueueCreateS(struct adt_Queue *q); | ||
+ | // q = pointer to an existing struct_adt_Queue | ||
+ | </ | ||
+ | |||
+ | **4. adt_QueueDeleteS()** ; //O(N)// ; //Uses IX// | ||
+ | |||
+ | Deletes the queue. | ||
+ | |||
+ | <code c> | ||
+ | void adt_QueueDeleteS(struct adt_Queue *q, void *delete); | ||
+ | // q = address of queue handle | ||
+ | // delete = void (*delete)(void *item) | ||
+ | // For each item in the queue, this function is called with the item as parameter. | ||
+ | // This is meant as an opportunity for user-cleanup of items that are in a non-empty queue. | ||
+ | // Set delete = 0 to do no user cleanup on items. | ||
+ | </ | ||
+ | |||
+ | **5. adt_QueueCount()** ; //O(1)// | ||
+ | |||
+ | Returns the number of items in the queue. | ||
+ | |||
+ | <code c> | ||
+ | unsigned int adt_QueueCount(struct adt_Queue *q); | ||
+ | // q = address of queue handle | ||
+ | </ | ||
+ | |||
+ | **6. adt_QueueFront()** ; //O(1)// | ||
+ | |||
+ | Returns the item at the front of the queue without removing it from the queue. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_QueueFront(struct adt_Queue *q); | ||
+ | // q = address of queue handle | ||
+ | </ | ||
+ | |||
+ | **7. adt_QueueBack()** ; //O(1)// | ||
+ | |||
+ | Returns the item at the end of the queue without removing it from the queue. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_QueueBack(struct adt_Queue *q); | ||
+ | // q = address of queue handle | ||
+ | </ | ||
+ | |||
+ | **8. adt_QueuePushFront()** ; //O(1)// | ||
+ | |||
+ | Adds item to the front of the queue. | ||
+ | |||
+ | <code c> | ||
+ | int adt_QueuePushFront(struct adt_Queue *q, void *item); | ||
+ | // q = address of queue handle | ||
+ | // item = item to add to queue | ||
+ | </ | ||
+ | |||
+ | **9. adt_QueuePopFront()** ; //O(1)// | ||
+ | |||
+ | Removes the item at the front of the queue and returns it. If the queue is empty, 0 is returned and the carry flag is reset. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_QueuePopFront(struct adt_Queue *q); | ||
+ | // q = address of queue handle | ||
+ | </ | ||
+ | |||
+ | **10. adt_QueuePushBack()** ; //O(1)// | ||
+ | |||
+ | Adds item to the end of the queue. | ||
+ | |||
+ | <code c> | ||
+ | int adt_QueuePushBack(struct adt_Queue *q, void *item); | ||
+ | // q = address of queue handle | ||
+ | // item = item to add to queue | ||
+ | </ | ||
+ | |||
+ | **11. adt_QueuePopBack()** ; //O(N)// | ||
+ | |||
+ | Removes the item at the end of the queue and returns it. If the queue is empty, 0 is returned and the carry flag is reset. | ||
+ | |||
+ | <code c> | ||
+ | void *adt_QueuePopBack(struct adt_Queue *q); | ||
+ | // q = address of queue handle | ||
+ | </ | ||
+ | |||
+ | ===== Code Example ===== | ||
+ | |||
+ | This example uses the standard malloc() and free() functions for memory allocations. | ||
+ | |||
+ | ====== Questions & Answers ====== | ||
+ | |||
+ | Post common questions and answers here. Report any bugs or ask a question not listed here on the [[start# | ||
+ | |||