# 5 Hashtables and Sets¶

## 5.1. Hashtables¶

The rewriting paradigm of Stratego is functional in nature, which is somewhat contradictory to the imperative nature of hashtables. Normally, this doesn’t present any practical problems, but remember that changes to hashtables “stick”, i.e. they are changed by side-effect.

The Stratego hashtable API is pretty straightforward. Hashtables are created by `new-hastable`

and destroyed by `hashtable-destroy`

.

```
stratego> import lib
stratego> new-hashtable => h
Hashtable(136604296)
```

The result `Hashtable(136604296)`

here is a handle to the actual hashtable. Consider it a pointer, if you will. The content of the hashtable must be retrieved with the `hashtable-*`

strategies, which we introduce here. The strategy `hashtable-copy`

can be used to copy a hashtable.

Adding a key with value to the table is done with `hashtable-put(|k,v)`

, where `k`

is the key, `v`

is the value. Retrieving the value again can be done by `hashtable-get(|k)`

.

```
stratego> <hashtable-put(|"one", 1)> h
Hashtable(136604296)
stratego> <hashtable-get(|"one")
1
```

The contents of the hashtable can be inspected with `hashtable-values`

and `hashtable-keys`

.

Nesting is also supported by the Stratego hashtables. Using `hashtable-push(|k,v)`

, a new “layer” can be added to an existing key (or an initial layer can be added to a non-existing key). Removing a layer for a key can be done with `hashtable-pop(|k)`

.

```
stratego> <hashtable-push("one",2)> h
Hashtable(136604296)
stratego> <hashtable-get("one")> h
[2,1]
stratego> <hashtable-pop(|"one")> h
Hashtable(136604296)
stratego> <hashtable-get(|"one")> h
[1]
stratego> <hashtable-remove(|"one")> h
Hashtable(136604296)
stratego> <hashtable-values> h
[]
```

## 5.2. Indexed Sets¶

The library provides a rather feature complete implementation of indexed sets, based on hashtables. A lightweight implementation of sets, based on lists, is explained in the chapter on lists.

Similar to hashtables, indexed sets are created with the `new-iset`

strategy, copied with `iset-copy`

and destroyed with `iset-destroy`

.

```
stratego> new-iset => i
IndexedSet(136662256)
```

The resulting term, `IndexedSet(136662256)`

, is a handle to the actual indexed set, which can only be manipulated through the `iset-*`

strategies.

Adding a single element to a set is done with `iset-add(|e)`

, whereas an entire list can be added with the `iset-addlist(|es)`

. Its elements can be returned as a list using `iset-elements`

.

```
stratego> <iset-addlist(|[1,2,3,4,4])> i
IndexedSet(136662256)
stratego> iset-elements
[1,2,3,4]
```

Notice that the result is indeed a set: every value is only represented once.

Using `iset-get-index(|e)`

, the index of a given element `e`

can be found. Similarly, `iset-get-elem(|i)`

is used to get the value for a particular index.

```
stratego> <iset-get-index(|3)> i
2
stratego> <iset-get-elem(|3)> i
4
```

Note that the indexes start at 0.

The set intersection between two sets can be computed with the `iset-isect(|set2)`

strategy. The strategy `iset-union(|set2)`

calculates the union of two sets, whereas `iset-subset(|set2)`

checks if one set is a subset of another. Equality between two sets is checked by `iset-eq(|set2)`

. These strategies are all used in a similar way:

```
stratego> <iset-eq(|set2)> set1
```

A single element can be removed from the set with `iset-remove(|e)`

. `iset-clear`

will remove all elements in a set, thus emptying it.