# Unique number allocator for JavaScript.

## How to use

```
const NumberAllocator = require('number-allocator').NumberAllocator
// Construct a NumerAllocator that has [0-10] numbers.
// All numbers are vacant.
const a = new NumberAllocator(0, 10)
// Allocate the least vacant number.
const num0 = a.alloc()
console.log(num0) // 0
// Allocate the least vacant number.
const num1 = a.alloc()
console.log(num1) // 1
// Use any vacant number.
const ret1 = a.use(5) // 5 is marked as used(occupied) in the NumberAllocator.
console.log(ret1) // true
// If use the used number, then return false.
const ret2 = a.use(1) // 1 has already been used, then return false
console.log(ret2) // false
// Free the used number.
a.free(1)
// Now 1 becomes vacant again.
const ret3 = a.use(1)
console.log(ret3) // true
// Get the lowest vacant number without marking used.
const num2 = a.firstVacant()
console.log(num2) // 2
// Clear all used mark. Now [0-10] are allocatable again.
a.clear()
```

## Reference

### NumberAllocator(min, max)

Constructor

- min: Number
- The maximum number of allocatable. The number must be integer.

- max: Number
- The minimum number of allocatable. The number must be integer.

The all numbers are set to vacant status.

Time Complexity O(1)

### firstVacant()

Get the first vacant number. The status of the number is not updated.

Time Complexity O(1)

- return: Number
- The first vacant number. If all numbers are occupied, return null. When alloc() is called then the same value will be allocated.

### alloc()

Allocate the first vacant number. The number become occupied status.

Time Complexity O(1)

- return: Number
- The first vacant number. If all numbers are occupied, return null.

### use(num)

Use the number. The number become occupied status.

If the number has already been occupied, then return false.

Time Complexity O(logN) : N is the number of intervals (not numbers)

- num: Number
- The number to request use.

- return: Boolean
- If
`num`

was not occupied, then return true, otherwise return false.

- If

### free(num)

Deallocate the number. The number become vacant status.

Time Complexity O(logN) : N is the number of intervals (not numbers)

- num: Number
- The number to deallocate. The number must be occupied status. In other words, the number must be allocated by alloc() or occupied be use().

### clear()

Clear all occupied numbers. The all numbers are set to vacant status. Time Complexity O(1)

### intervalCount()

Get the number of intervals. Interval is internal structure of this library.

This function is for debugging.

Time Complexity O(1)

- return: Number
- The number of intervals.

### dump()

Dump the internal structor of the library.

This function is for debugging.

Time Complexity O(N) : N is the number of intervals (not numbers)

## Internal structure

NumberAllocator has a sorted-set of Interval.

Interval has `low`

and `high`

property.

I use `[low-high]`

notation to describe Interval.

When NumberAllocator is constructed, it has only one Interval(min, max).

Let's say `new NumberAllocator(1, 9)`

then the internal structure become as follows:

```
[1-------9]
```

When `alloc()`

is called, the first Interval.low is returned.

And then the interval is shrinked.

```
alloc()
return 1
[2------9]
```

When `use(5)`

is called, the interval is separated to the two intervals.

```
use(5)
[2-4] [6--9]
```

When `alloc()`

is called again, the first Interval.low is returned.

And then the interval is shrinked.

```
alloc()
return 2
[3-4] [6--9]
```

When `free(1)`

is called. the interval is inseted.

```
free(1)
[1] [3-4] [6--9]
```

When `free(2)`

is called. the interval is inseted.

And check the left and right intervals. If they are continuours, then concatinate to them.

```
free(1)
[1][2][3-4] [6--9]
[1-------4] [6--9]
```

When `clear()`

is called, then reset the interval as follows:

```
[1-------9]
```

When `intervalCount()`

is called, then the number of intervals is retuned.

In the following case, return 3.

```
intervalCount()
return 3
[1] [3-4] [6--9]
```

Interval management (insertion/concatination/shrinking) is using efficient way. Insert/Delete operation to sorted-set is minimized. Some of operations requires O(logN) time complexity. N is number of intervals. If the maximum count of allocatable values is M, N is at most floor((M + 1) / 2),

In this example, M is 9 so N is at most 5 as follows:

```
[1] [3] [5] [7] [9]
```