I have the problem of shifting array elements and I''ve determined I can''t use a linked list because the traversal algorithm won''t suit my needs. So can i shift around array elements using memcpy()? For instance I want to get rid of array[1] and shift array[2] to array[1] and array[3] to array[2]. Can i do this? nevermind it may be bad practice - just let me know. ============================== "Need more eeenput..." - #5, "Short Circuit" Blade Edge Software ==============================

Let''s say your array is size N:

You want to copy a block of size N-1 starting at the second element in the array, and copy that to the memory location where the first element begins.

Oh... my... god... that is sloppy.

Or, you could simply shift the elements, ala bubble sort, one by one. That wouldn''t be so bad.

I''m guessing you''re using an array because you want constant-time access, whereas the access time of a linked list would depend on which element you''re looking for, thereby taking a little more time.

If you''re going to be doing this shifing alot, then you should try a structure that lends itself more to sorting.

memcpy(&Array[1], &Array[2], sizeof(TYPE) * NumberOfElementsToShift);

You'd better use memmove, to make sure the overlapping memory areas don't get mixed up. Like this:


memmove(&Array[1], &Array[2], sizeof(TYPE) * NumberOfElementsToShift);


But maybe it would be even better to use an array to hold the data (like you already did), and use a pointer to point to the first element of the array. Shifting should then only move the pointer to the new first element, and the traversal algorithm should then keep in mind that it has to wrap around to the beginning of the array, when reaching the end (this can be done with some simple modulo calculation). Simple example (untested code):

    // Adapt this typedef to your needs...typdef int ArrayData;// Array sizeint arraySize = 100;// Array data: don't forget to delete it afterwardsArrayData *array = new ArrayData [arraySize];// Pointer to first elementArrayData *first = array;void ShiftArray(int newFirstIndex) {  // Very simple shifting, and no copy needed  first = array[newFirstIndex];}void Traverse() {  // Array traversal algorithm:  // Determine the index of the first element  int firstIdx = (first-array) / sizeof(ArrayData);  int currIdx = firstIdx;  // Loop through all array cells  while (currIdx+1 != firstIdx) {    // Do something with the current array cell    // ...    // Go to next cell, keeping in mind possible wraparound    currIdx = (currIdx + 1) % arraySize;  }}    

There, that wasn't so hard now was it? The shifting has become much cheaper (only one value to change), and the traversal algorithm is basically the same, except with an extra "% arraySize" at the end. (Oh yeah, I haven't tested the code, so it's possbile it contains some tiny little bugs .)

Dormeur


Edited by - Dormeur on January 8, 2001 2:59:39 AM

This boils down to what you do most often, that is what you need to optimize. This means if you're using an array you have constant time to access each individual element (using a), but linear time to remove an arbitrary element (that is you must go through the whole array, since you must copy (or shift) the elements afterward).<br>In the case of a double-linked list (that is each element points both to the next and the previous) you have linear time to access an individual element (since you need to go through all elements to find the one you want), but constant time to remove an arbitrary element (you only need to change a couple of pointers).<br>So if you access individual elements most frequently you should go with the array-implementation, but if you need to do the shift more often you might want to use a double-linked list implementation.<br>In case you use the array-implementation I recommend that you use memmove() as a previous post suggest, because of the reasons given in that post!<br><br>/Andreas <br><br>Edited by - amag on January 8, 2001 5:49:55 AM

yes, i access the array a lot and shift only when a ball is removed from the game (and then, only when there is more than one ball - which is even rarer since first the player has to get a three ball capsule). So the shift operation is so much easier than implementing a linked list (or a double linked list - which I had honestly forgotten about). Thanks for your input.

==============================
"Need more eeenput..."
- #5, "Short Circuit"
Blade Edge Software
==============================

Ok, but when you say access the list a lot, do you then go through the whole list (ie traversing)? If that''s the case a double-linked list might be a pretty good option, since the time to traverse the linked list is the same as the time to traverse an array (linear).

/Andreas