Ordered Dictionary?

Does anyone have any code for a custom Dictionary class that preserves the order of items added? I know that the native Xojo Dictionary does not guarantee the order but I am porting some Java code that uses Java’s LinkedHashSet which is essentially an ordered Dictionary.

except its not QUITE a dictionary
Java’s hashset does nothing IF the key already exists
see https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E)
which is decidedly different than Xojo’s dictionary which would replace the existing key

I don’t really understand why the order of items needs to be preserved, so my answer may be a little off. But can’t you just create a subclass of Dictionary and override methods as needed?

Class OrderedDictionary
Inherits Dictionary

  Sub Clear
    redim self.mPreservedKeyOrder(-1)
  End Sub

  Sub Constructor(ParamArray entries as Pair)
    for each p as Pair in entries
      self.Value(p.Left) = p.Right
    next p
  End Sub

  Function PreservedKeyOrder() as Variant()
    return self.mPreservedKeyOrder
  End Function

  Sub Remove(key as Variant)
    dim index as Integer = self.mPreservedKeyOrder.IndexOf(key)
  End Sub

  Sub Value(key as Variant, Assigns data as Variant)
    // do not replace existing values, as @npalardy mentioned...
    if not self.HasKey(key) then
      super.Value(key) = data
    end if
  End Sub

  Private Property mPreservedKeyOrder() as Variant

End Class

You could then loop through the list of keys returned by PreservedKeyList to retrieve the items in the order they were added.

This code is completely untested, but should get you on the right track (if I understood things right).

1 Like

@npalardy You are indeed correct.

@C-8DO Works like a charm.

One thing this port has taught me (aside from how much more feature-rich Java’s standard library is compared to Xojo’s) is that I really really wish Xojo had better support for generics.

For example, the code I’m porting uses a LinkedHashSet. Amongst other properties, a LinkedHashSet preserves the order of elements added (like the example given above by @C-8DO). One thing Java lets you do is declare the type of the LinkedHashSet. For instance, you can specify that it only stores elements of Class1:

LinkedHashSet<Class1> mySet = new LinkedHashSet<Class1>()

This lets you get back an array of Class1 objects like so:

Class1[] myArray = mySet.toArray()

Whilst it is possible to get back the array used in @C-8DO’s suggestion, it will be of type Variant, not type Class1. There’s no way to force the Xojo compiler to accept that the returned array is of type Class1. Something like:

Var mySet As OrderedDictionary = New OrderedDictionary
// Add some elements. I promise they're all Class1 instances...

Var attempt1() As Class1 = mySet.PreservedKeyOrder() // Nope.
Var attempt2() As Class1 = Class1(mySet.PreservedKeyOrder()) // Nope.
Var attempt3() As Class1 = Class1IsAFuckingArray(mySet.PreservedKeyOrder()) // Nope.

That should be doable also. Add another class property:

Private Property mKeyType as Xojo.Introspection.TypeInfo

And a new constructor:

Sub Constructor(keyType as Xojo.Introspection.TypeInfo)
  self.mKeyType = keyType
End Sub

At the beginning of method Value insert:

Sub Value(key as Variant, Assigns data as Variant)
  dim keyType as Xojo.Introspection.TypeInfo = Xojo.Introspection.GetType(key)
  if not (self.mKeyType Is nil) and (keyType.FullName <> self.mKeyType.FullName) then
    Raise new UnsupportedFormatException
  end if

  // code as shown in my first post goes here
End Sub

Then you can instantiate a new OrderedDictionary like this:

dim dict as new OrderedDictionary(GetTypeInfo(Class1))

Now you can only add keys of type Class1. Any other type will throw an UnsupportedFormatException.

To get the list of keys as an array of type Class1 is a bit ugly. You could write a conversion method that takes/extends an array of Variant and returns an array of Class1.

1 Like

On the other hand you could simply write:

dim keys() as Variant = myDict.PreservedKeyOrder
for each c as Class1 in keys
next c

One thing this port has taught me (aside from how much more feature-rich Java’s standard library is compared to Xojo’s) is that I really really wish Xojo had better support for generics.


Yes - casting an array does not work anything like you expect
Even if you could write

Var attempt2() As Class1 = Class1()(mySet.PreservedKeyOrder()) // Cast to an array of class1

that doesnt work :frowning:

I’ve used type info like this in the constructor to get “generics sort of”
See https://www.great-white-software.com/blog/2019/09/04/generics/
and https://github.com/npalardy/TypedDictionary

Its about as close as you can get with Xojo BUT you still run into issues like casting to an array of X doesnt work and IF you are trying to port code from Java or other languages where that kind of thing does work you’ll have a gnarly time

1 Like

Yes, I know. That’s where I learned of this :wink:

I just had a look at your code for the TypedDictionary and saw you’re simply comparing two TypeInfos instead of comparing their FullNames like I did. Wouldn’t have thought that’d work…

I like the introspection use - clever.

@npalardy It is getting gnarly. What I’ve taken to doing (which I don’t like as it leads to repetition of code) is to make a separate class for each element type. For example, I have LinkedHashSetVector2 class that returns an array of Vector2 objects, a LinkedHashSetMatrix class, etc. Works but is ugly.

The other advantage that Java’s LinkedHashSet has apart from preserved order is that the time taken to remove a key does not increase as the array grows. I think it must use a doubly-linked list instead of a single array as a backing property.

If anyone wants to write a tutorial on creating a doubly linked list please feel free!

typeinfos are per class so that is safe
you wont et different objects for the typeinfo for instances of the same type

Yeah I had at one time thought a “prebuild” script that would hunt all the code for

      dim foo as SomeGenericType<specific element type>

might work
you could write thins in a dim line etc but a method decl wont let you write that as one of the parameter types. if you try to write

        sub foo( param1 as SomeGenericType<<specific element type>) 

you’ll see what I mean

so the BEST that might occur would be to do this in an external editor, run the external preprocessor, load it into Xojo then off you go :frowning:

1 Like

I think in one of the implementation notes I read it did say a double linked list

+1 kudos for the idea of a Xojo preprocessor. I might explore that…

a preprocessor was the only way I could find to do some of it

using it as a method param is still tricky since Xojo will actually NOT let you write a method param type that looks like

     someparam as SomeGeneric<type>

and without being able to do that the preprocessor isnt quite as useful :frowning:

and return types rip out ALL special characters when you leave the return type field - except an empty ()