Use DynamicOneDimensionalArray in ArrayStack

[czgdp1807]

Description of the problem

Currently we use fixed size arrays in ArrayStack which is nothing but wastage of memory. To reduce that problem, DynamicOneDimensionalArrayshould be used inside the methods of ArrayStack.

The way of using is left to the one who will fix the issue.

Example of the problem

References/Other comments

[Saptashrungi]

I am willing to work on this issue. Is an Arraystack a static one dimensional array?

[czgdp1807]

Yes, currently we are using, OneDimensionalArray inside ArrayStack which needs maxsize to be given for creating the object.
May be, we need to make the changes without affecting the API. See the examples of DynamicOneDimensionalArray to understand its usage.

[Saptashrungi]

I went through one of the example for dynamic array. It used ctype module and doubled the size of array when it's capacity was full.

[czgdp1807]

The DynamicOneDimensionalArray doesn't use any external module named ctype.
Yes, the size of the array is doubled everytime it becomes full to keep the amortized cost of insertion, O(1). Similarly in the case of deletion we half the size of the array when only 1/4 of the total capacity is used to keep the amortized cost of deletion, O(1).
Read more about it at the following links,
[1] http://www.cs.nthu.edu.tw/~wkhon/algo09/lectures/lecture16.pdf
[2] https://www.cs.cornell.edu/courses/cs3110/2013sp/lectures/lec21-amortized/lec21.html

[czgdp1807]

The working of DynamicOneDimensionalArray shouldn't be our concern while using it in ArrayStack. We just need to figure out how to use it's public methods i.e., append and delete in pop and push of ArrayStack.

[Saptashrungi]

I read about amortized cost. We need to use already existing methods of Arraystack in DynamicOneDimensionalArray right?
Where while appending we will check if the size is full. If yes we will double the size and similarly we can do while deletion.

[czgdp1807]

We need to use already existing methods of Arraystack in DynamicOneDimensionalArray right?

You are thinking the opposite of what is required. We need to use the methods of DynamicOneDimensionalArray in ArrayStack.
For example in the following line, replace OneDimensionalArray with DynamicOneDimensionalArray

pydatastructs/pydatastructs/miscellaneous_data_structures/stack.py

Line 93 in a8e2a96

items = OneDimensionalArray(dtype, maxsize)

Similarly the following push,

pydatastructs/pydatastructs/miscellaneous_data_structures/stack.py

Lines 104 to 108 in a8e2a96

	def push(self, x):
	if self.top == self.maxsize:
	raise ValueError("Stack is full.")
	self.items[self.top] = self.dtype(x)
	self.top += 1

can be re-written as,

def push(self, x):
    self.items.append(self.dtype(x))

In fact, the above suggests that once we start using DynamicOneDimensionalArray in ArrayStack, there is no need for top data member.
In a similar manner, you have to see what changes are required in other methods of ArrayStack.

[Saptashrungi]

There is no need of top because we are appending right?
The append function is not user defined I assume.

[czgdp1807]

There is no need of top because we are appending right?

Yes, the purpose of top will be fulfilled by self.items._last_pos_filled.

The append function is not user defined I assume.

The append function is the one defined in DynamicOneDimensionalArray. We are just using it in ArrayStack as I showed in #67 (comment)

[Saptashrungi]

For pop I suggest the following like the example given by you;

Current pop function:

def pop(self):
        if self.top == 0:
            raise ValueError("Stack is already empty.")
        self.top -= 1
        r = self.items[self.top]
        self.items[self.top] = None
        return r

Modified pop function:

 def pop(self):
        self.items.delete(-1)

#assuming the delete function displays the item before deleting.

[czgdp1807]

May be we can use deepcopy to copy the top most element before deleting it. Something like,

def pop(self):
    top_element = copy.deepcopy(self.items[self._last_pos_filled])
    self.items.delete(self._last_pos_filled)
    return top_element

What do you say?

[Saptashrungi]

Why not a simple copy? Is the item having a subclass(child class objects)?

[czgdp1807]

We don't know what will be there in the stack. It can be anything. May be an object(in which case deepcopy is necessary, otherwise, a reference will be created which will be modified on deletion and at the end wrong value will be returned). IMHO, we have to generalise.
I am not sure deepcopy will work in all cases, but that shouldn't be our problem as it is inbuilt, so python should take care of it.

Why not a simple copy?

Can you try this out on your system? Does pop return correct values?

[Saptashrungi]

Okay, then using deepcopy would be better. You want me to try and check pop with deepcopy right?

[czgdp1807]

Well, if deepcopy is the only option we have, then you can go for a PR, if there's nothing more to discuss.

[Saptashrungi]

Yes because a simple copy won't clone the values of child objects.

[Saptashrungi]

May be we should try this also:

''' def pop(self):
top_element = self.items[self._last_pos_filled]
self.items.delete(self._last_pos_filled)
return top_element'''

Here there references will be different but values will be same.

[czgdp1807]

I think it would create shallow copy which will be changed on deletion. top_element will be a reference to self.items[self._last_pos_filled] which will be made None by self.items.delete(self._last_pos_filled) and hence user will always receive None as the return value, which we don't want.
However, you can still try that out, if that works for user defined class objects then we can go for it.