1

I have prototypes to recreate how array methods work, pop/push/shift/etc, and I would like to extend the functionality to do the following:

  1. Push/Pop/shift/unshift multiple values array.push(0); array.push(1); array.push(2); expect(array.pop()).to.be(2); expect(array.pop()).to.be(1); expect(array.pop()).to.be(0);

  2. Push/Pop/unshift/etc single values array.push(0); array.push(1); expect([0,1]); array.pop(1); expect([0]);

My assumption is that I would need a global array variable to store the elements. Is that the right?

Here is my code:

var mainArray = [];  // array no longer destroyed after fn() runs
function YourArray(value) {
  this.arr = mainArray;  // looks to global for elements | function?
  this.index = 0;
  var l = mainArray.length;

  if(this.arr === 'undefined')
    mainArray += value;        //  add value if array is empty
  else
    for(var i = 0; i < l ; i++)             // check array length
        mainArray += mainArray[i] = value;  // create array index & val

  return this.arr;
}

YourArray.prototype.push = function( value ) {
  this.arr[ this.index++ ] = value;
  return this;
};

YourArray.prototype.pop = function( value ) {
  this.arr[ this.index-- ] = value;
  return this;
};

var arr = new YourArray();
arr.push(2);
console.log(mainArray);
Improve this question

2 Answers 2

Reset to default
1

My assumption is that I would need a global array variable to store the elements. Is that the right?

No. That is not right.

You want each array object to have its own, independent set of data. Otherwise, how can you have multiple arrays in your program?

function YourArray(value) {
  this.arr = [];  // This is the data belonging to this instance. 
  this.index = 0;
  if(typeof(value) != 'undefined')) {
    this.arr = [value];
    this.index = 1;
  }
}

////////////////////////////////////
// Add prototype methods here
///////////////////////////////////

var array1 = new YourArray();
var array2 = new YourArray();
array1.push(2);
array1.push(4);
array2.push(3);
array2.push(9);
// Demonstrate that the values of one array
// are unaffected by the values of a different array
expect(array1.pop()).to.be(4);
expect(array2.pop()).to.be(9);
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Yes, you can have multiple array in the program, even with a global array. But you have to write your own management for it. I did it once for my Bigint library in the hope that it would be faster (nope, wasn't) and used the very simple K&R malloc algorithm from the book. Caused a lot of gray hairs. Ah, still have it and got it uploaded to github.com/czurnieden/Little/blob/master/libs/malloc.js. Please beware: it's not for the faint of heart ;-)
Is there a way to push multiple elements? For example push(2) then push(4) returns [2,4]. As far as i understand once the function finishes executing the array object is destroyed.
If the storage is encapsulated in the object as suggested, then it will not be destroyed unless the object itself is destroyed. And for pushing multiple elements, if you want you can write a push that takes an array argument.
1

It's a bit late for this party, admitted but it nagged me. Is there no easy (for some larger values of "easy") way to do it in one global array?

The standard array functions work as in the following rough(!) sketch:

function AnotherArray() {
  this.arr = [];
  // points to end of array
  this.index = 0;
  if(arguments.length > 0) {
    for(var i=0;i<arguments.length;i++){
      // adapt if you want deep copies of objects
      // and/or take a given array's elements as 
      // individual elements
      this.arr[i] = arguments[i];
      this.index++;
    }
  }
}
AnotherArray.prototype.push = function() {
  // checks and balances ommitted
  for(var i=0;i<arguments.length;i++){
    this.arr[ this.index++ ] = arguments[i];
  }
  return this;
};
AnotherArray.prototype.pop = function() {
  this.index--;
  return this;
};
AnotherArray.prototype.unshift = function() {
  // checks and balances ommitted
  var tmp = [];
  var alen = arguments.length;

  for(var i=0;i<this.index;i++){
    tmp[i] = this.arr[i];
  }
  for(var i=0;i<alen;i++){
    this.arr[i] = arguments[i];
    this.index++;
  }
  for(var i=0;i<tmp.length + alen;i++){
    this.arr[i + alen] = tmp[i];
  }
  return this;
};
AnotherArray.prototype.shift = function() {
  var tmp = [];
  for(var i=1;i<this.index;i++){
    tmp[i - 1] = this.arr[i];
  }
  this.arr = tmp;
  this.index--;
  return this;
};
AnotherArray.prototype.isAnotherArray = function() {
  return true;
}
AnotherArray.prototype.clear = function() {
  this.arr = [];
  this.index = 0;
}
AnotherArray.prototype.fill = function(value,length) {
  var len = 0;
  if(arguments.length > 1)
    len = length;
  for(var i=0;i<this.index + len;i++){
    this.arr[i] = value;
  }
  if(len != 0)
    this.index += len;
  return this;
}
// to simplify this example
AnotherArray.prototype.toString = function() {
  var delimiter = arguments.length > 0 ? arguments[0] : ",";
  var output = "";
  for(var i=0;i<this.index;i++){
    output += this.arr[i];
    if(i < this.index - 1)
     output += delimiter;
  }
  return output;
}
var yaa = new AnotherArray(1,2,3);
yaa.toString(); // 1,2,3
yaa.push(4,5,6).toString(); // 1,2,3,4,5,6
yaa.pop().toString(); // 1,2,3,4,5
yaa.unshift(-1,0).toString(); // -1,0,1,2,3,4,5
yaa.shift().toString(); // 0,1,2,3,4,5
var yaa2 = new AnotherArray();
yaa2.fill(1,10).toString(); // 1,1,1,1,1,1,1,1,1,1

Quite simple and forward and took only about 20 minutes to write (yes, I'm a slow typist). I would exchange the native JavaScript array in this.arr with a double-linked list if the content can be arbitrary JavaScript objects which would make shift and unshift a bit less memory hungry but that is obviously more complex and slower, too.

But to the main problem, the global array. If we want to use several individual chunks of the same array we need to have information about the starts and ends of the individual parts. Example:

var globalArray = [];
var globalIndex = [[0,0]];
function YetAnotherArry(){
  // starts at the end of the last one
  this.start = globalIndex[globalIndex.length-1][1];
  this.index = this.start;
  // position of the information in the global index
  this.pos = globalIndex.length;
  globalIndex[globalIndex.length] = [this.start,this.index];
}

So far, so well. We can handle the first array without any problems. We can even make a second one but the moment the first one wants to expand its array we get in trouble: there is no space for that. The start of the second array is the end of the first one, without any gap.

One simple solution is to use an array of arrays

globalArray = [
                ["first subarray"],
                ["second subarray"],
                ...
              ];

We can than reuse what we already wrote in that case

var globalArray = [];
function YetAnotherArray(){
  // open a new array
  globalArray[globalArray.length] = [];
  // point to that array
  this.arr = globalArray[globalArray.length - 1];
  this.index = 0;
}
YetAnotherArray.prototype.push = function() {
  for(var i=0;i<arguments.length;i++){
    this.arr[ this.index++ ] = arguments[i];
  }
  return this;
};
// and so on

But for every new YetAnotherArray you add another array to the global array pool and every array you abandon is still there and uses memory. You need to manage your arrays and delete every YetAnotherArray you don't need anymore and you have to delete it fully to allow the GC to do its thing.

That will leave nothing but gaps in the global array. You can leave it as it is but if you want to use and delete thousands you are left with a very sparse global array at the end. Or you can clean up. Problem:

var globalArray = [];
function YetAnotherArray(){
  // add a new subarray to the end of the global array
  globalArray[globalArray.length] = [];
  this.arr = globalArray[globalArray.length - 1];
  this.index = 0;
  this.pos = globalArray.length - 1;
}
YetAnotherArray.prototype.push = function() {
  for(var i=0;i<arguments.length;i++){
    this.arr[ this.index++ ] = arguments[i];
  }
  return this;
};
YetAnotherArray.prototype.toString = function() {
  var delimiter = arguments.length > 0 ? arguments[0] : ",";
  var output = "";
  for(var i=0;i<this.index;i++){
    output += this.arr[i];
    if(i < this.index - 1)
     output += delimiter;
  }
  return output;
}
// we need a method to delete an instance
YetAnotherArray.prototype.clear = function() {
  globalArray[this.pos] = null;
  this.arr = null;
  this.index = null;
};
YetAnotherArray.delete = function(arr){
    arr.clear();
    delete(arr);
};
// probably won't work, just a hint in case of asynch. use
var mutex = false;
YetAnotherArray.gc = function() {
  var glen, indexof, next_index, sub_len;

  indexof = function(arr,start){
    for(var i = start;i<arr.length;i++){
      if (arr[i] == null || arr[i] == undefined)
        return i;
    }
    return -1;
  };

  mutex = true;
  glen = globalArray.length;
  sublen = 0;
  for(var i = 0;i<glen;i++){
    if(globalArray[i] == null || globalArray[i] == undefined){
      next_index = indexof(globalArray,i);
      if(next_index == -1){
        break;
      }
      else {
        globalArray[i] = globalArray[next_index + 1];
        globalArray[next_index + 1] = null;
        sublen++;
      }
    }
  }
  globalArray.length -= sublen - 1;
  mutex = false;
};

var yaa_1 = new YetAnotherArray();
var yaa_2 = new YetAnotherArray();
var yaa_3 = new YetAnotherArray();
var yaa_4 = new YetAnotherArray();

yaa_1.push(1,2,3,4,5,6,7,8,9).toString(); // 1,2,3,4,5,6,7,8,9
yaa_2.push(11,12,13,14,15,16).toString(); // 11,12,13,14,15,16
yaa_3.push(21,22,23,24,25,26,27,28,29).toString();// 21,22,23,24,25,26,27,28,29
yaa_4.push(311,312,313,314,315,316).toString(); // 311,312,313,314,315,316


globalArray.join("\n");
/*
1,2,3,4,5,6,7,8,9
11,12,13,14,15,16
21,22,23,24,25,26,27,28,29
311,312,313,314,315,316
*/
YetAnotherArray.delete(yaa_2);
globalArray.join("\n");
/*
1,2,3,4,5,6,7,8,9

21,22,23,24,25,26,27,28,29
311,312,313,314,315,316
*/
YetAnotherArray.gc();
globalArray.join("\n");
/*
1,2,3,4,5,6,7,8,9
21,22,23,24,25,26,27,28,29
311,312,313,314,315,316
*/

But, as you might have guessed already: it doesn't work.

YetAnotherArray.delete(yaa_3); // yaa_3 was 21,22,23,24,25,26,27,28,29
globalArray.join("\n");
/*
1,2,3,4,5,6,7,8,9
21,22,23,24,25,26,27,28,29

*/

We would need another array to keep all positions. Actual implementation as an exercise for the reader but if you want to implement a JavaScript like array, that is for arbitrary content you really, really, really should use a doubly-linked list. Or a b-tree. A b+-tree maybe?

Oh, btw: yes, you can do it quite easily with a {key:value} object, but that would have squeezed all the fun out of the job, wouldn't it? ;-)

Improve this answer

2 Comments

Looks like your having fun. You appear to be using the javascript engine to create a new layer to perform the tasks the javascript engine is already performing :-)
In parts is was me, having some fun, yes, but the original idea was by the OP. Also: as long as TypedArrays are fixed in length and lack much of the things a normal Array has there is a reason to try to work around. It would have been more reasonable to base my examples on typed arrays, admitted, but that would have made them overly complex without a good reason. Most of the methods described here are also generally applicable and not bound to Javascript but I hope that's not too much against the rules here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.