No LinkedList, Queue, or null?

Development Programming & Scripting
,
1

I’m trying to make a breadth first search algorithm and it seems like I need LinkedLists and Queues to create it. It doesn’t seem like either are in Verse, so I was going to create a class to make them. This brought up another issue where “null” doesn’t exist.

My question - do these types exist somewhere in Verse and aren’t documented? Is there a “null” equivalent? Thanks!

2

Hi @BrendannnD:

Verse currently doesn’t have some of these convenience data structures. But you can implement your own the way you’d like for the time being. I don’t have a handy example of a linked list specifically on-hand, but I did write an example internally for a binary search tree a long time ago that makes use of Verse optionals to act as a “nullable” type.

Keep in mind that this is not production-ready code and is provided purely as an example.

VerseDataStructures<public> := module:
    BSTNode<public>:= class:
        var left<public>:?BSTNode = false
        var right<public>:?BSTNode = false
        val<public>:int = 0

var TraversalResult:[]int = array{}
Inorder(maybe_t:?VerseDataStructures.BSTNode):void=
    if (not (t := maybe_t?)):
        return
    if (n := maybe_t?):
        Inorder(n.left)
        set TraversalResult += array{n.val}
        Inorder(n.right)
    
    return 

InorderTraversal(maybe_t:?VerseDataStructures.BSTNode):[]int=
    set TraversalResult = array{}
    Inorder(maybe_t)
    return TraversalResult

# Test cases
TestInorderTraversal():logic=
    c:VerseDataStructures.BSTNode = VerseDataStructures.BSTNode{val:=3}
    b:VerseDataStructures.BSTNode = VerseDataStructures.BSTNode{val:=2, left:=option{c}}
    a:VerseDataStructures.BSTNode = VerseDataStructures.BSTNode{val:=1, right:=option{b}}
    Result:[]int = InorderTraversal(option{a})
    if (Result = array{1, 3, 2}):
        return true
    else:
        return false

TestInorderTraversal1():logic=
    Result:[]int = InorderTraversal(false)
    if (Result.Length = 0):
        return true
    else:
        return false

TestInorderTraversal2():logic=
    a:VerseDataStructures.BSTNode = VerseDataStructures.BSTNode{val:=1}
    Result:[]int = InorderTraversal(option{a})
    if (Result = array{1}):
        return true
    else:
        return false

I don’t have an example of a queue data structure on-hand in Verse unfortunately, but you should be able to implement one using the existing built-in array in Verse.

3

Thanks for the info. I didn’t know about the option type and it’s super useful! If I had an array of custom class object types and wanted to make a function to return one of the objects available in that array, is this the way I’d do it?

GetAvailableItem() : ?Item = {
        for (Index := 0..Items.Length-1):
            if (Items[Index].Available = true):
                if(set Items[Index].Available = false):
                if(ReturnItem := Items[Index]): 
                    return option{ReturnItem}       
        return false
    }

When I try to use the returned Item in other functions it won’t let me because it says its a ?Item. Is there some way to convert it back or return just a normal item if it doesn’t fail?

Edit: I was able to get it work by putting a ? after the call to the function. Thank you again!

1 Like
4

This topic is old, but maybe some people would be interested in this :

1 Like