0
# Memory-Efficient Collections
1

2
High-performance data structures that dynamically optimize their internal representation based on size, designed specifically for native images and low-memory environments.
3

4
## Capabilities
5

6
### Economic Maps
7

8
Memory-efficient map implementation that uses different internal representations based on size, optimizing for both small and large collections.
9

10
```java { .api }
11
/**
12
 * Memory-efficient map with dynamic internal representation
13
 */
14
public interface EconomicMap<K, V> extends UnmodifiableEconomicMap<K, V> {
15
    /** Create empty map with default equivalence strategy */
16
    static <K, V> EconomicMap<K, V> create();
17
    
18
    /** Create empty map with custom equivalence strategy */
19
    static <K, V> EconomicMap<K, V> create(Equivalence strategy);
20
    
21
    /** Create empty map with expected size hint */
22
    static <K, V> EconomicMap<K, V> create(int expectedSize);
23
    
24
    /** Create map from existing java.util.Map */
25
    static <K, V> EconomicMap<K, V> wrapMap(Map<K, V> map);
26
    
27
    /** Create map with single key-value pair */
28
    static <K, V> EconomicMap<K, V> of(K key, V value);
29
    
30
    /** Create map with multiple key-value pairs */
31
    static <K, V> EconomicMap<K, V> of(K k1, V v1, K k2, V v2);
32
    
33
    /** Put key-value pair, returning previous value */
34
    V put(K key, V value);
35
    
36
    /** Put key-value pair only if key is absent */
37
    V putIfAbsent(K key, V value);
38
    
39
    /** Add all entries from another economic map */
40
    void putAll(EconomicMap<K, V> other);
41
    
42
    /** Add all entries from standard map */
43
    void putAll(Map<K, V> other);
44
    
45
    /** Remove key and return associated value */
46
    V removeKey(K key);
47
    
48
    /** Remove all entries */
49
    void clear();
50
    
51
    /** Replace all values using provided function */
52
    void replaceAll(BiFunction<? super K, ? super V, ? extends V> function);
53
}
54

55
/**
56
 * Read-only view of economic map
57
 */
58
public interface UnmodifiableEconomicMap<K, V> {
59
    /** Get value for key, or null if not present */
60
    V get(K key);
61
    
62
    /** Get value for key, or default if not present */
63
    V get(K key, V defaultValue);
64
    
65
    /** Check if key is present in map */
66
    boolean containsKey(K key);
67
    
68
    /** Get number of entries */
69
    int size();
70
    
71
    /** Check if map is empty */
72
    boolean isEmpty();
73
    
74
    /** Get collection of all values */
75
    Iterable<V> getValues();
76
    
77
    /** Get collection of all keys */
78
    Iterable<K> getKeys();
79
    
80
    /** Get collection of all entries */
81
    Iterable<MapCursor<K, V>> getEntries();
82
    
83
    /** Convert to standard java.util.Map */
84
    Map<K, V> toMap();
85
}
86
```
87

88
**Usage Examples:**
89

90
```java
91
import org.graalvm.collections.*;
92

93
public class MapUsageExample {
94
    public void demonstrateEconomicMap() {
95
        // Create with default settings
96
        EconomicMap<String, Integer> counts = EconomicMap.create();
97
        
98
        // Add entries
99
        counts.put("apple", 5);
100
        counts.put("banana", 3);
101
        counts.put("cherry", 8);
102
        
103
        // Safe access with default
104
        int appleCount = counts.get("apple", 0);
105
        int orangeCount = counts.get("orange", 0); // Returns 0
106
        
107
        // Iterate over entries
108
        for (MapCursor<String, Integer> entry : counts.getEntries()) {
109
            System.out.println(entry.getKey() + ": " + entry.getValue());
110
        }
111
        
112
        // Use custom equivalence strategy
113
        EconomicMap<String, String> caseInsensitive = 
114
            EconomicMap.create(Equivalence.IDENTITY);
115
        
116
        // Create with size hint for better performance
117
        EconomicMap<Integer, String> largeCounts = 
118
            EconomicMap.create(1000);
119
    }
120
}
121
```
122

123
### Economic Sets
124

125
Memory-efficient set implementation with dynamic representation optimization.
126

127
```java { .api }
128
/**
129
 * Memory-efficient set with dynamic internal representation
130
 */
131
public interface EconomicSet<E> extends UnmodifiableEconomicSet<E> {
132
    /** Create empty set with default equivalence strategy */
133
    static <E> EconomicSet<E> create();
134
    
135
    /** Create empty set with custom equivalence strategy */
136
    static <E> EconomicSet<E> create(Equivalence strategy);
137
    
138
    /** Create empty set with expected size hint */
139
    static <E> EconomicSet<E> create(int expectedSize);
140
    
141
    /** Add element to set, return true if added */
142
    boolean add(E element);
143
    
144
    /** Remove element from set, return true if removed */
145
    boolean remove(E element);
146
    
147
    /** Add all elements from collection */
148
    boolean addAll(Collection<? extends E> collection);
149
    
150
    /** Add all elements from another economic set */
151
    boolean addAll(EconomicSet<E> set);
152
    
153
    /** Remove all elements in collection */
154
    boolean removeAll(Collection<?> collection);
155
    
156
    /** Retain only elements in collection */
157
    boolean retainAll(Collection<?> collection);
158
    
159
    /** Remove all elements */
160
    void clear();
161
}
162

163
/**
164
 * Read-only view of economic set
165
 */
166
public interface UnmodifiableEconomicSet<E> extends Iterable<E> {
167
    /** Check if element is present */
168
    boolean contains(E element);
169
    
170
    /** Get number of elements */
171
    int size();
172
    
173
    /** Check if set is empty */
174
    boolean isEmpty();
175
    
176
    /** Convert to array */
177
    Object[] toArray();
178
    
179
    /** Convert to typed array */
180
    <T> T[] toArray(T[] array);
181
    
182
    /** Get iterator over elements */
183
    Iterator<E> iterator();
184
    
185
    /** Convert to standard java.util.Set */
186
    Set<E> toSet();
187
    
188
    /** Get empty economic set */
189
    static <E> UnmodifiableEconomicSet<E> emptySet();
190
}
191
```
192

193
**Usage Examples:**
194

195
```java
196
public class SetUsageExample {
197
    public void demonstrateEconomicSet() {
198
        // Create set for tracking unique items
199
        EconomicSet<String> uniqueNames = EconomicSet.create();
200
        
201
        // Add elements
202
        uniqueNames.add("Alice");
203
        uniqueNames.add("Bob");
204
        uniqueNames.add("Charlie");
205
        uniqueNames.add("Alice"); // Duplicate, won't be added
206
        
207
        System.out.println("Size: " + uniqueNames.size()); // 3
208
        
209
        // Check containment
210
        if (uniqueNames.contains("Bob")) {
211
            System.out.println("Bob is present");
212
        }
213
        
214
        // Iterate elements
215
        for (String name : uniqueNames) {
216
            System.out.println("Name: " + name);
217
        }
218
        
219
        // Set operations
220
        EconomicSet<String> otherNames = EconomicSet.create();
221
        otherNames.add("Bob");
222
        otherNames.add("Diana");
223
        
224
        uniqueNames.addAll(otherNames); // Union
225
        uniqueNames.retainAll(Arrays.asList("Alice", "Bob")); // Intersection
226
    }
227
}
228
```
229

230
### Map Cursors
231

232
Efficient iteration over map entries with mutable access to values.
233

234
```java { .api }
235
/**
236
 * Mutable cursor for iterating over map entries
237
 */
238
public interface MapCursor<K, V> extends UnmodifiableMapCursor<K, V> {
239
    /** Set value for current entry */
240
    void setValue(V value);
241
}
242

243
/**
244
 * Read-only cursor for map iteration
245
 */
246
public interface UnmodifiableMapCursor<K, V> {
247
    /** Move to next entry, return true if successful */
248
    boolean advance();
249
    
250
    /** Get key of current entry */
251
    K getKey();
252
    
253
    /** Get value of current entry */
254
    V getValue();
255
}
256
```
257

258
**Usage Examples:**
259

260
```java
261
public class CursorExample {
262
    public void demonstrateCursor() {
263
        EconomicMap<String, Integer> map = EconomicMap.create();
264
        map.put("a", 1);
265
        map.put("b", 2);
266
        map.put("c", 3);
267
        
268
        // Read-only iteration
269
        for (UnmodifiableMapCursor<String, Integer> cursor : map.getEntries()) {
270
            System.out.println(cursor.getKey() + " = " + cursor.getValue());
271
        }
272
        
273
        // Mutable iteration - double all values
274
        for (MapCursor<String, Integer> cursor : map.getEntries()) {
275
            cursor.setValue(cursor.getValue() * 2);
276
        }
277
    }
278
}
279
```
280

281
### Equivalence Strategies
282

283
Pluggable comparison strategies for customizing equality and hashing behavior.
284

285
```java { .api }
286
/**
287
 * Abstract base class for custom comparison strategies
288
 */
289
public abstract class Equivalence {
290
    /** Default equivalence using Object.equals() and Object.hashCode() */
291
    public static final Equivalence DEFAULT;
292
    
293
    /** Identity equivalence using == and System.identityHashCode() */
294
    public static final Equivalence IDENTITY;
295
    
296
    /** Identity equivalence with system hash code optimization */
297
    public static final Equivalence IDENTITY_WITH_SYSTEM_HASHCODE;
298
    
299
    /** Test equality of two objects */
300
    public abstract boolean equals(Object a, Object b);
301
    
302
    /** Compute hash code for object */
303
    public abstract int hashCode(Object o);
304
}
305
```
306

307
**Usage Examples:**
308

309
```java
310
public class EquivalenceExample {
311
    // Custom equivalence for case-insensitive strings
312
    public static final Equivalence CASE_INSENSITIVE = new Equivalence() {
313
        @Override
314
        public boolean equals(Object a, Object b) {
315
            if (a == b) return true;
316
            if (a == null || b == null) return false;
317
            return a.toString().equalsIgnoreCase(b.toString());
318
        }
319
        
320
        @Override
321
        public int hashCode(Object o) {
322
            return o == null ? 0 : o.toString().toLowerCase().hashCode();
323
        }
324
    };
325
    
326
    public void demonstrateCustomEquivalence() {
327
        EconomicMap<String, String> caseInsensitiveMap = 
328
            EconomicMap.create(CASE_INSENSITIVE);
329
        
330
        caseInsensitiveMap.put("Hello", "World");
331
        String value = caseInsensitiveMap.get("HELLO"); // Returns "World"
332
        
333
        // Identity-based map for object instances
334
        EconomicMap<String, Integer> identityMap = 
335
            EconomicMap.create(Equivalence.IDENTITY);
336
        
337
        String s1 = new String("key");
338
        String s2 = new String("key");
339
        identityMap.put(s1, 1);
340
        identityMap.put(s2, 2); // Different entry due to identity comparison
341
    }
342
}
343
```
344

345
### Utility Data Structures
346

347
Additional specialized collections for specific use cases.
348

349
```java { .api }
350
/**
351
 * Immutable pair container for two related values
352
 */
353
public final class Pair<L, R> {
354
    /** Create pair with left and right values */
355
    public static <L, R> Pair<L, R> create(L left, R right);
356
    
357
    /** Get left value */
358
    public L getLeft();
359
    
360
    /** Get right value */
361
    public R getRight();
362
    
363
    /** Create pair with null values */
364
    public static <L, R> Pair<L, R> empty();
365
}
366

367
/**
368
 * Thread-safe object pool for reusing expensive objects
369
 */
370
public final class LockFreePool<T> {
371
    /** Create pool with factory function */
372
    public static <T> LockFreePool<T> create(Supplier<T> factory);
373
    
374
    /** Get object from pool or create new one */
375
    public T get();
376
    
377
    /** Return object to pool for reuse */
378
    public void put(T object);
379
    
380
    /** Clear all pooled objects */
381
    public void clear();
382
}
383

384
/**
385
 * Lock-free radix tree for string keys
386
 */
387
public final class LockFreePrefixTree {
388
    /** Create empty prefix tree */
389
    public static LockFreePrefixTree create();
390
    
391
    /** Put key-value pair */
392
    public void put(String key, Object value);
393
    
394
    /** Get value for key */
395
    public Object get(String key);
396
    
397
    /** Remove key */
398
    public Object remove(String key);
399
    
400
    /** Check if key exists */
401
    public boolean containsKey(String key);
402
    
403
    /** Get all keys with given prefix */
404
    public Set<String> getKeysWithPrefix(String prefix);
405
}
406

407
/**
408
 * Sequential lock-based prefix tree with consistent reads
409
 */
410
public final class SeqLockPrefixTree {
411
    /** Create empty sequential lock prefix tree */
412
    public static SeqLockPrefixTree create();
413
    
414
    /** Put key-value pair */
415
    public void put(String key, Object value);
416
    
417
    /** Get value for key with consistent read */
418
    public Object get(String key);
419
    
420
    /** Remove key */
421
    public Object remove(String key);
422
    
423
    /** Get size of tree */
424
    public int size();
425
}
426
```
427

428
**Usage Examples:**
429

430
```java
431
public class UtilityExample {
432
    public void demonstrateUtilities() {
433
        // Pair usage
434
        Pair<String, Integer> nameAge = Pair.create("Alice", 30);
435
        System.out.println(nameAge.getLeft() + " is " + nameAge.getRight());
436
        
437
        // Object pool for expensive resources
438
        LockFreePool<StringBuilder> builderPool = 
439
            LockFreePool.create(() -> new StringBuilder(256));
440
        
441
        StringBuilder sb = builderPool.get();
442
        try {
443
            sb.append("Hello").append(" World");
444
            String result = sb.toString();
445
        } finally {
446
            sb.setLength(0); // Reset for reuse
447
            builderPool.put(sb);
448
        }
449
        
450
        // Prefix tree for fast string lookups
451
        LockFreePrefixTree tree = LockFreePrefixTree.create();
452
        tree.put("apple", "fruit");
453
        tree.put("application", "software");
454
        tree.put("apply", "action");
455
        
456
        // Find all keys starting with "app"
457
        Set<String> appKeys = tree.getKeysWithPrefix("app");
458
        // Returns: ["apple", "application", "apply"]
459
    }
460
}
461
```
462

463
## Types
464

465
```java { .api }
466
// Map wrapper implementation
467
public final class EconomicMapWrap<K, V> implements EconomicMap<K, V> {
468
    /** Wrap existing java.util.Map as EconomicMap */
469
    public static <K, V> EconomicMap<K, V> create(Map<K, V> map);
470
}
471

472
// Iterator types
473
public interface Iterator<E> {
474
    boolean hasNext();
475
    E next();
476
    void remove();
477
}
478

479
// Collection operation results
480
public interface Collection<E> extends Iterable<E> {
481
    int size();
482
    boolean isEmpty();
483
    boolean contains(Object o);
484
    Object[] toArray();
485
    <T> T[] toArray(T[] a);
486
    boolean add(E e);
487
    boolean remove(Object o);
488
}
489
```