New Power Management

# npm

## number-allocator

1.0.10 • Public • Published

# Unique number allocator for JavaScript.

Version 1.0.10

## 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.

### 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]
``````

## Keywords

### Install

`npm i number-allocator`

### Repository

github.com/redboltz/number-allocator

187,622

1.0.10

MIT

28.6 kB

13