1. Characteristics
2. Performance
3. Declaration
4. Literal Syntax
5. Access
6. Iteration
7. Sorting
8. About Duplicates
9. Further Information

The index generic data type is a sorted container of key/value pairs and is useful for associating values with other values while maintaining a fixed order of iteration. It is also called a sorted map. It is similar to the map type, but the same key can occur multiple times and the order is predictable (sorted) when iterating over an index. It is implemented with a treap.

Characteristics

• Ordered (always kept sorted)
• May contain key duplicates (see below)

Performance

• Semi-fast append/put/insert (logarithmic, O(log(count)), except if resize is necessary)
• Semi-fast lookup for key contains test (logarithmic, O(log(count))
• Semi-fast remove (logarithmic, O(log(count))

In comparison to a map, it's slower in every aspect, because it's always sorted. It's also slower than a sequence for append, but faster for contains test. If you need a collection that it's always sorted, and you expect continuous changes, an Index will be a better choice. If you only need to sort the collection once, a seq will most likely be faster.

The memory footprint is about the same as maps.

Declaration

sorted keyElementType->valueElementType identifier;

Example

Declare an index from str to Object initialized to null:

sorted str->Object index;

Declare and create an empty index in two equivalent ways:

sorted str->Object index();
sorted str->Object index = new sorted str->Object();

It's also possible to create the index using the init feature:

sorted str->Object index;
...
init index();

It's not possible to specify an initial capacity for an index.

Literal Syntax

sorted str->int string2int = ["one"->1, "two"->2];
sorted int->bool int2Bool = [1->false, 2->true];
sorted double->str[] double2StrArr = [1.3->["haha", "bbbb"]];

Access

{
    sorted int->str index();
    index.put(1, "aa");
    index.put(2, "bb");
    index.put(3, "cc");
    pln(#index);
    pln(#index.count);
    
    pln(#index.get(1));
    pln(#index.get(3));
    pln(#index.get(42));
    
    pln(#index.contains(1));
    pln(#index.contains(3));
    pln(#index.contains(42));
    
    index.remove(1);
    pln(#index);
}

Iteration

for (k, v in index) pln(k, " -> ", v);
for (k, v in index, index=i) pln(#i; k, " -> ", v);
for (k, v in index, reverse) pln(k, " -> ", v);

Sorting

The index (key elements) is always kept sorted. The order can be controlled using a custom compare function (but the most simple way is usually just to use str key elements and produce keys according to your desired order).

About Duplicates

The index can contain duplicate key elements, but only if you append them using the insert method. If you use the put method, the specified key element will be replaced if it already exists. (Note that the order of the values with duplicate keys is not deterministic!)

Further Information

See file your workspace/base/cm/lang/sortedMap.cmz