Sorting structure by number and keep search option by string

Question

So I have an data structure I am trying to convert to gdscript, its searchable by key:String, but can be ordered by a int and a float value.

This is whay I got so far :

var arrayValues = []  # [floatvalue, intvalue, stringname]
var dictData = {}     # { key:String , arrayValuesIdx:int , datastructure }

To get all the data :

var x = dictData["string"]
var floatvalue = arrayValues[x.arrayValuesIdx].floatvalue
var intvalue   = arrayValues[x.arrayValuesIdx].intvalue

The value of the float and intvalue will change in update cycle, but I also need to show in screen the values ordered by intvalue,floatvalue :
arrayValues.sort_custom(func(a, b): return (a[1]==b[1] and b[0]>=a[0]) or (a[1]>b[1]))

After sorting, how can I keep a relation with dictData and arrayValues ?
Is there another way to have a sorted data by numbers but still be able to find it by a string somehow ?

Obs: The number of itens is large so it needs to be fast search by key:string and fast sorting.

Doings

Answer 1

Objects are always accessed by reference in GDScript. This means that you can have multiple "lists" of the same bunch of objects. In your case you can maintain a dictionary and two sorted arrays, all 3 of them containing the same set of object references.

Beira

Answer 2

So Dictionaries are unordered, sort of similar to a hash table. You index by the key.

If you need both structures, than you'd have to update the array index in the Dictionary after every time you sorted it.

But maybe you can explain what you are doing, because this seems like a strange and inefficient data structure setup.

Quincey

Answer 3

Right, that would work if they were Objects or some class that derived from an Object. Not just loose strings or integers.

Quincey

Answer 4

It would also make a difference how often you are sorting and how many objects you actually need to access. For example, if you just need to find a few objects, then searching through a Dictionary may be okay, without any arrays. Or if you need all the objects every frame, then you need to do the sort anyhow, no matter what, in which case you don't need anything other than the Dictionary (the sorted list can be a temporary, since there is no value to saving it if you sort every frame).

Quincey

Answer 5

I am not sure I understood , did you mean something like that :

class TObject:
	floatvalue
	intvalue
	stringkey
	someotherdata

arrayf[ TObject ] -> sorted by float + int
dict[ string, TObject ]

Meaning I can update the floatvalue and intvalue inside dict[ stringkey ] , and resort the arrayf every few frames ? And still use the dict to get the update key ?
So if it works as reference it will work with a single array and a single dict, why I need another array ?

The porpoise of this is to have multiplayer scores for different kind of games, this particular one is a race game, so floatvalue is the amount of meeters each car is in a lap, and intvalue is the lap, but this structure can also be used for any other kind of game ( if we ignore the intvalue ).
So, for this game for example, I need to update the floatvalue and the intvalue every few frames for each car, where I will do it by the dict( car_name ), then reorder the array, and show in screen.

Doings

Answer 6

So I come up with this :

class_name TMultSort
extends Node

class TObject:
	var floatIdx:float
	var intIdx:int
	var stringkey:String
	var someotherref:Object

var dic = {} # mult sort dict, key is String, reference TObject
var arr: Array[TObject] # will be custom sorted

# Add new object, it will link it in the array and dict
func addObject( o: TObject ):
	arr.append( o )
	dic[ o.stringkey ] = o

# Get the object, can be updated in realtime since it works as reference
func getObject( stringkey: String )->TObject:
	return dic[ stringkey ]

# Get object by the ordered array
func getObjectFromArray( orderIdx:int )->TObject:
	return arr[ orderIdx ]

# Sort for games like car racing, a[0]=floatidx=mettersInRace , a[1]=intIdx=Lap
func sortByFloatAndInt():
	arr.sort_custom(func(a, b): return (a.intIdx==b.intIdx and b.floatIdx>=a.floatIdx) or (a.intIdx>b.intIdx))

I just tested and it seems to be working, is this the best way ?

Doings

Answer 7

why I need another array ?

I thought you said you want it sorted by some int property and some float property. The point is you can organize the same set of references into as many containers (arrays, dicts, linked lists, trees etc...) as you need.

I just tested and it seems to be working, is this the best way ?

Yes.

Beira