+++
title = "1b: Tree Addressing"
weight = 2
template = "doc.html"
+++

Check out the Nock [explanation](/docs/nock/) for more
information on the tree-addressing system.

## `++cap`

Tree head

Tests whether the tree address `a` is in the head or the tail of a [`noun`](/docs/glossary/noun).
Produces the constant [`atom`](/docs/glossary/atom) `%2` if it is within the head (subtree `+2`), or
the constant [`atom`](/docs/glossary/atom) `%3` if it is within the tail (subtree `+3`).

#### Accepts

`a` is an [`atom`](/docs/glossary/atom).

#### Produces

A constant [`atom`](/docs/glossary/atom).

#### Source

```hoon
++  cap
  ~/  %cap
  |=  a=@
  ^-  ?(%2 %3)
  ?-  a
    %2        %2
    %3        %3
    ?(%0 %1)  !!
    *         $(a (div a 2))
  ==
```

#### Examples

```
> (cap 4)
%2
```

```
> (cap 6)
%3
```

```
> (cap (add 10 9))
%2
```

```
> (cap 1)    ::address '1' is in neither the head nor the tail
! exit
```

```
> (cap 0x40))
%2
> `@`0x40
64
```

```
> (cap 'a')
%3
> `@`'a'
97
```

---

## `++mas`

Address within head/tail

Computes the tree address of [`atom`](/docs/glossary/atom) `a` within either the head (`+2`) or tail
(`+3`) of a [`noun`](/docs/glossary/noun).

#### Accepts

`a` is an [`atom`](/docs/glossary/atom).

#### Produces

An [`atom`](/docs/glossary/atom).

#### Source

```hoon
++  mas
  ~/  %mas
  |=  a=@
  ^-  @
  ?-  a
    ?(%2 %3)  1
    ?(%0 %1)  !!
    *         (add (mod a 2) (mul $(a (div a 2)) 2))
  ==
```

#### Examples

```
> (mas 3)
1
```

```
> (mas 4)
2
```

```
> (mas 5)
3
> (cap 5)    ::`(cap a)` computes whether address `a` is in the head or the tail
%2
```

```
> (mas 7)
3
> (cap 7)
%3
```

```
> (mas 11)
7
```

```
> (mas (mas 11))
3
```

```
> (cap (mas 6))
%3
```

```
> (mas 0)    ::address `0` is in neither the head nor the tail
! exit
```

```
> (mas 1)    ::address `1` is in neither the head nor the tail
! exit
```

#### Discussion

```
            1
          /   \
         /     \
        2       3              <--here are the head (`+2`) and the tail (`+3`)
       / \      /\
      4   5    6  7
     /\   /\  /\  /\
     (continues...)
```

Running `(mas 7)` in the [`Dojo`](/docs/glossary/dojo) will return `3`, because address `+3` is what
`+7` now occupies. The tree below helps illustrate the relationship. With
parentheses are `a` values (if `a` is in subtree `+3`), and without parentheses
are the values returned with `(mas a)`.

```
            1(3)                       ::new/(old) addresses
           /    \
          2       3
         (6)     (7)
        / \       /\
       /   \     /  \
      4     5   6    7
     (12) (13) (14) (15)
    / \    / \ / \   / \
       (continues...)
```

Notice how the old values in the head (subtree `+2`) were not illustrated in
this case, because `+7` is within the tail (subtree `+3`).

---

## `++peg`

Address within address

Computes the absolute address of `b`, a relative address within the subtree
`a`.

#### Accepts

`a` is an [`atom`](/docs/glossary/atom).

`b` is an [`atom`](/docs/glossary/atom).

#### Produces

An [`atom`](/docs/glossary/atom).

#### Source

```hoon
++  peg
  ~/  %peg
  |=  [a=@ b=@]
  ?<  =(0 a)
  ^-  @
  ?-  b
    %1  a
    %2  (mul a 2)
    %3  +((mul a 2))
    *   (add (mod b 2) (mul $(b (div b 2)) 2))
  ==
```

#### Examples

```
> (peg 4 1)
4
```

```
> (peg 1 4)
4
```

```
> (peg 4 2)
8
```

```
> (peg 4 8)
32
```

```
> (peg 4 (4 2))
32
```

```
> (peg 8 45)
269
```

```
> (cap (peg 4 2))    ::`(cap a)` computes whether address `a` is in the head or the tail
%2
```

#### Discussion

In other words, the subtree at address `a` is treated as a tree in its own
right (starting with root `+1`, head `+2`, and tail `+3`). Relative address
`b` is found with respect to `a`, and then its absolute address, within the
greater tree, is returned.

Running `(peg 3 4)` in the [`Dojo`](/docs/glossary/dojo), for example, will return `12`. Looking at
a tree diagram makes it easy to see why.

```
                 1
              /     \
             /       \
            /         \
           2           3       <- here is the subtree `+3`. The subtree address is `a` in `(peg a b)`
          / \         / \
         /   \       /   \
        4     5     6     7
       / \   / \   / \   / \
      8  9  10 11 12 13 14  15
     /\  /\ /\ /\ /\ /\ /\  /\
         (continues...)
```

When we consider subtree at address `+3` by itself, it has relative addresses
that are structured in the same way as its parent tree's absolute addresses.
The absolute addresses are given in parentheses in the diagram below.
Notice how relative address `+4` is at the same position as absolute address
`+12`.

```
            1(3)                        ::new/(old) addresses
           /    \
          2       3
         (6)     (7)
        / \       /\
       /   \     /  \
      4     5   6    7
    (12) (13) (14)  (15)
    / \    / \ / \   / \
       (continues...)
```

---