[RESOURCE] LIHO/HILO Queue

[Axo-Tak]

Basically, these are two queue classes that take in and out values at the ends of the queue. You can not add anything into the queue between the ends.
Pushing is a resource-intensive operation at the lowest point of the queue, it has to loop through all of the items on the queue in order to do the desired operation.

Popping is a non-resource-intensive operation at the highest point of the queue, it doesn't loop through the items.

Lowest In Highest Out:
Given a LIHO queue with 5 items:
0 << Point where queue SO pushes in an item, and has to loop through the other 4.
1
2
3
4 << Point where queue SO pops out an item.
In order to replicate this set on a LIHO queue, you would have to push in the set {4, 3, 2, 1, 0}.

Highest In Lowest Out:
Given a HILO queue with 5 items:
0 << Point where queue SO pushes out an item, and has to loop through the other 4.
1
2
3
4 << Point where queue SO pops in an item.
In order to replicate this set on a HILO queue, you would have to pop in the set {0, 1, 2, 3, 4}.

Stack Limitations
For both example queues, the middle items {1, 2, 3} can NOT be changed.

Source

Code: [Select]

//lowest in highest out
function LIHOStackSO::onAdd(%this)
{
%this.size = 0;
}

function LIHOStackSO::pushIn(%this,%val)
{
for(%i=%this.size-1;%i>=0;%i--)
{
%m = %this.element[%i];
%this.element[%i] = "";
%this.element[%i+1] = %m;
}
%this.element[0] = %val;
%this.size++;
}

function LIHOStackSO::popOut(%this)
{
if(%this.size <= 0)
{
%this.size = 0;
return;
}

%e = %this.element[%this.size-1];
%this.element[%this.size-1] = "";
%this.size--;
return %e;
}

//highest in lowest out
function HILOStackSO::onAdd(%this)
{
%this.size = 0;
}

function HILOStackSO::popIn(%this,%val)
{
%this.element[%this.size] = %val;
%this.size++;
}

function HILOStackSO::pushOut(%this)
{
if(%this.size <= 0)
{
%this.size = 0;
return;
}

%e = %this.element[0];
for(%i=0;%i<%this.size;%i++)
{
%m = %this.element[%i];
%this.element[%i] = "";
%this.element[%i-1] = %m;
}
%this.size--;
return %e;
}

[Ad Bot]

[Lugnut]

CompSci newb - what is this form of data structure good for, specifically at this high of a level?

[Axo-Tak]

CompSci newb - what is this form of data structure good for, specifically at this high of a level?

For queues with variable access timing. This is a limitation that the schedule system probably doesn't cover.

EDIT: actually hold on, I'll think about this because the schedule system might cover this.
EDIT2: actually no, the schedule system doesn't cover it.

If you do a container search on a high amount of bricks, you should add them onto a queue if you want to do operations on them with minimal lag. Over time, you can do the operations on the bricks using the queue.

[Greek2me]

Good resource. It's something I always find myself remaking.

[$trinick]

CompSci newb - what is this form of data structure good for, specifically at this high of a level?

Any kind of constantly mutating list is best stored as a stack. For example, a lot of my bot implementations have a stack system where you push actions to the stack (look here, shoot, etc) to be executed then popped off the stack. This is an example of a FIFO stack (not included in this resource), but there's also uses for HILO/LIHO stacks.

[Axo-Tak]

You could take out of stacks even if it was 0, thus making them negative.

I fixed that.

[portify]

You should use a head/tail structure for O(1) pushing.

[Headcrab Zombie]

CompSci newb - what is this form of data structure good for, specifically at this high of a level?

The undo system uses a stack - you push actions performed to the stack, and then pop them every time you undo something
Personally I've never heard the terms LIHO/HILO, i've always used FIFO/FILO

Also, aren't stacks supposed to push and pop from the same end, while what you've made (pushing and popping from opposite ends) is a queue?

[Axo-Tak]

You should use a head/tail structure for O(1) pushing.

I'm not sure how I'd do a deque, but I am thinking about how I'd do it.

EDIT: I'll just do a deque with wrapping if someone were to get a bound to go over 999999 or under -999999.
EDIT2: The fruity case of new ScriptObject(SO); for(%i=-999999;%i<=999999;%i++){SO.element[%i]="";} will only use 50MB of RAM. When that object were to get deleted, Blockland would keep that 50MB RAM but it'll allow another object to fill it up.

[portify]

You don't need to handle wrapping as a normal queue would overflow too anyway.
Something like this:

%this.head = -1;
%this.tail = 0;

push(%value)
{
  %this.value[%this.head++] = %value;
}

pop()
{
  if (%this.head < %this.tail)
  {
    return "";
  }

  %value = %this.value[%this.tail];

  %this.value[%this.tail] = "";
  %this.tail++;

  if (%this.tail > %this.head)
  {
    %this.head = -1;
    %this.tail = 0;
  }

  return %value;
}

[Ipquarx]

why did you not include the function keywords

[$trinick]

why did you not include the function keywords

He's used to using other languages I guess. Don't ask me what language lacks a keyword identifier for functions.

[Ipquarx]

He's used to using other languages I guess. Don't ask me what language lacks a keyword identifier for functions.

Well he quite obviously wrote everything else in torquescript, literally all he missed was the function keyword. It really doesn't make much sense at all unless he purposely left them out, which begs the question why.

[portify]

why did you not include the function keywords

Because it wasn't intended to be complete code. There's no "%this, " or QueueClassName:: either; it's just to demonstrate.

[$trinick]

Because it wasn't intended to be complete code. There's no "%this, " or QueueClassName:: either; it's just to demonstrate.

Idk, other than your function definitions it seems to be complete code.