Data Structures

Let's have a go at building some useful data structures, namely Stack, Queue and PriorityQueue:

Before we begin, recall that defining a function with type instead of var and const simply ensures that the typename of the returned object is the same as that of the function. (Calling info() on the object will expose its typename, so we can do some basic runtime type checking if we need to)

It's good practice to define all constructor functions (functions that define and return an object) with the keyword type.

Stack

We'll begin with the most basic structure, the Stack.

stack.vtx

type Stack = (max = None) => ({
    data: [],
    max: max,
    push: (x) => {
        if (!this.max or (this.data.length() < this.max)) {
            this.data.append(x)
        }
    },
    pop: () => {
        var value = this.data[this.data.length()-1]
        this.data.remove(this.data.length()-1)
        return value
    },
    clear: () => {
        this.data = []
    },
    size: () => this.data.length(),
    front: () => this.data[this.data.length()-1],
    back: () => this.data[0]
})

Now that we've defined our Stack constructor, we can go ahead and use it to generate a new Struct object.

stack.vtx

const s = Stack()

s.push(0)
s.push(1)
s.push(2)

println(s.data) // [0, 1, 2]

s.pop()
s.pop()

println(s.data) // [0]

Great, we were able to successfully push and pop off our new stack.

Note that we also provided a parameter (max) to our constructor, and defaulted it to None.

Since we constructed the stack without providing a value to max, our stack can get infinitely large (within the limits of of the physical realm, of course). Let's try creating a stack with a specified max size.

const limited_s = Stack(3)

limited_s.push(0)
limited_s.push(1)
limited_s.push(2)
limited_s.push(3)
limited_s.push(5)

println(limited_s.data) // [0, 1, 2]

We've successfully capped our stack!

Queue

Let's move on to a slightly different data structure: Queue

Queues are different to Stacks in that they are First In, First Out rather than First In, Last Out.

queue.vtx

type Queue = (max = None) => ({
    data: [],
    max: max,
    enqueue: (x) => {
        if (!this.max or this.data.length() < this.max) {
            this.data.append(x)
        }
    },
    dequeue: () => {
        var value = this.data[0]
        this.data.remove(0)
        return value
    },
    clear: () => {
        this.data = []
    },
    size: () => this.data.length(),
    front: () => this.data[0],
    back: () => this.data[this.data.length()-1]
})

The only real difference is that instead of pushing and popping, we are enqueuing and dequeuing.

queue.vtx

const q = Queue()

q.enqueue(0)
q.enqueue(1)
q.enqueue(2)

println(q.data) // [0, 1, 2]

q.dequeue()
q.dequeue()

println(q.data) // [2]

As with the Stack, we can also set a max size by passing in a number to the max parameter on construction.

Priority Queue

Now for something a little more complicated, a Priority Queue.

A priority queue maintains a sorted list from high priority to low priority.

pqueue.vtx

import [] : functional

type PriorityQueue = (max = None) => ({
    data: [],
    max: max,
    enqueue: (value, priority = 0) => {
        if (!this.max or (this.data.length() < this.max)) {
            var _value = [value, priority]
            this.data.append(_value)
            this.data = this.data.sort((a, b) => a[1] < b[1])
        }
    },
    dequeue: () => {
        var value = this.data[0][0]
        this.data.remove(0)
        return value
    },
    clear: () => {
        this.data = []
    },
    get: () => this.data.map((e) => e[0]),
    size: () => this.data.length(),
    front: () => (this.data[0])[0],
    back: () => (this.data[this.data.length()-1])[0]
})

This time, every time we enqueue a value, we need to pass alongside it a priority value. The queue then sorts the value into its correct spot.

Bear in mind, this is a naive implementation of a priority queue, and there exist more complex and efficient algorithms than simply sorting on enqueue.

Notice we also provide a get function that returns our values without their priorities. We needed to import functional to make use of map here.

pqueue.vtx

const q = PriorityQueue()

q.enqueue("A", 1)
q.enqueue("B", 2)
q.enqueue("C", 1)
q.enqueue("D", 0)

println(q.get()) // [D, A, C, B]

Let's walk through the flow.

We add "A" with a priority of 1 -> ["A"]

We add "B" with a priority of 2 -> ["A", "B"]

We add "C" with a priority of 1 -> ["A", "C", "B"]

We add "D" with a priority of 0 -> ["D", "A", "C", "B"]

And just like that, we've built out three useful structures that you can re-use in your own codebase!

Copy the code and modify it to experiment with how things work.

If you wanted to type check a value before adding it to the Stack or Queue, how would you do it? (Hint: check out the list of built-in functions for the answer)