Module: collections.ordered_map

Source: ./collections/ordered_map.reef

Overview

collections/ordered_map — OrderedMap[K, V], insertion-ordered.

Collections 0.9.2 / D9. One generic map replaces IntOrderedMap, StringOrderedMap and PtrOrderedMap, all of which were string-keyed and differed only in value type.

Iteration order is INSERTION order, which is the whole reason this type exists separately from collections.hashmap: a hash map's keys() come back in probe order, and probe order changes on rehash. Order is a different data structure, not a flag on the map (D9).

Layout: a dense insertion array (keys/values, indices 0 .. len-1) plus a bucket table of indices into it for O(1) lookup. The dense array is what makes key_at(i)/value_at(i) meaningful and what keeps keys() and values() ordered.

Usage: import collections.ordered_map as omap let m = omap.create:string, int m.set("first", 1) m.set("second", 2) match m.key_at(0) Option_Some(k) => println(k) end // "first" Option_None() => end end match

AUTO-GROWS. The typed versions silently dropped an entry when the backing array was full — set_int simply returned without inserting. set() now grows and returns a bool, and never drops.

KEYS ARE COMPARED WITH ==, which is reference identity for structs (D3); see the note in collections.hashmap.

Factories: createK, V -> OrderedMap[K, V] 16 entries, 32 buckets create_with_capacityK, V -> OrderedMap[K, V] cap < 1 clamps to 1

Methods: set(key, value) -> bool insert or update; true on success get(key) -> option.Option[V] has(key) -> bool remove(key) -> bool true if it existed; preserves order len() / capacity() / is_empty() / clear() key_at(i) -> option.Option[K] None if i is out of range value_at(i) -> option.Option[V] None if i is out of range keys() -> [K] / values() -> [V] INSERTION order

Performance: O(1) average get/set/has; remove is O(n) because it closes the gap in the dense array to preserve order.

Types

OrderedMap

Fields:

Functions

fn create(): OrderedMap[K, V]

fn create_with_capacity(cap: int): OrderedMap[K, V]

cap < 1 clamps to 1 (BUG-062). The bucket table starts at twice the entry capacity so the 70% rule has room before the first reindex.

Generated by reefc doc