Search code examples
arraysoptimizationabstraction

How to Simulate array.remove(int) in a Language that only Allows array.add(int)


I am trying to implement an algorithm in an exotic programming language that requires that I remove an element from a one-dimensional array, but the language does not have a method for removing element x at index i.

These methods are available for array.[method]() :

  • add(x) --- push x and resize length + 1
  • resize(x) --- new length = x
  • count() --- returns the length of the array

Is there a way I can write my own array method or remove method, using primitive data types, basic control flow, and variables?

I have considered to use an array with both retained and discarded items together with an array of booleans to represent include == true/false. The arrays would share the same index, but I am not sure this would be the most computationally effective way to approach this.


Solution

  • Update: Staighforward solution which use no additional array. Run time and amount of memory used is depend on count and resize subroutines and access by index [] implementation details which aren't described in documentation:

    sub
       remove( array< int,1 >& initial_array, int item_to_remove )
    begin
       loop
          int i = 1
          int removed_count = 0
          int count = initial_array.count()
       until
          i > count - removed_count;
       begin
          if( initial_array[i] != item_to_remove ) then
             # remove item by replacing it with the item from the tail
             initial_array[i] = initial_array[count - removed_count];
             removed_count = removed_count + 1
             continue;
          end;
          i = i + 1;
       end;
       # cut the tail
       initial_array.resize(count - removed_count);
    end;
    
    array<int> foo[] = { 1, 2, 3, 2, 3 };
    remove( foo, 3 );  # after execution foo must contain { 1, 2, 2 }
    

    More complication solution will be to implement more appropriate for your purposes data structure. As my undersanding goes you can achive this by implementing PCL Extension

    As @iAdjunct pointed out it is interesting why array doesn't have this method in first place.