Re: array question

From: Daniel Koepke (dkoepke@CALIFORNIA.COM)
Date: 10/04/97


On Sat, 4 Oct 1997, Brian Williams - Nashak wrote:

-+what my question is is how do i delete a entry from an array, like set
-+array[x] to 0, then delete any values with 0, and fix the array, like:
-+say I have an array[10] =
-+ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }
-+
-+then I set array[4] to 0:
-+ { 1, 2, 3, 4, 0, 6, 7, 8, 9, 0 }
-+
-+then I update the array, what I want it to read now is this:
-+ { 1, 2, 3, 4, 6, 7, 8, 9, 0, 0 }
-+
-+
-+I'm having trouble figuring out a for loop that will do this for me, so
-+any help would be VERY appreciated...

Okay, here's my solution.  I don't think Andrew's skipped backed
to back zeros, so I made certain of accounting for that.  This
is, as always, mailer code, and should be treated as such.  It's
also ugly, so if you're looking for my prettiest piece of code,
cover your eyes...:)

  int array[ARRAY_SIZE], last_zero, i, j;

  /* find the last zero in the array */
  if (array[ARRAY_SIZE-1] != 0)
    last_zero = ARRAY_SIZE;
  else
    for (i = ARRAY_SIZE-1; i >= 0 && !array[i]; i--)
      last_zero = i;

  for (i = 0; i < last_zero; i++)
    if (array[i] == 0) {
      j = i+1;
      while (j < last_zero && array[j] == 0)
        j++;

      if (j < last_zero) {
        array[i] = array[j];
        array[j] = 0;
      }
    }

How it (is supposed to) works is actually fairly simple.  We loop
through the array to find a zero in it.  If and when we find one,
we find the next non-zero in the array (and set j equal to the
index of that non-zero element).  Then, if (and only if) j is in
the array bounds, we swap the two (since array[i] == 0, we just
set array[j] = 0).

Now, despite being ugly, this approach is actually quite fast.
The finding of the last zero speeds it up for large arrays that
aren't full; has barely any negative impact on smaller arrays,
and no impact on large arrays...:)


--
Daniel Koepke -:- dkoepke@california.com -:-  [Shadowlord/Nether]
Think.


     +------------------------------------------------------------+
     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
     +------------------------------------------------------------+



This archive was generated by hypermail 2b30 : 12/08/00 PST