number-allocator

What is number-allocator?

The number-allocator npm package is designed to manage the allocation and release of numbers within a specified range. It is particularly useful in scenarios where you need to dynamically allocate unique numbers, such as in resource management, ticketing systems, or any application requiring unique identifiers.

What are number-allocator's main functionalities?

Allocate a number

This feature allows you to allocate a number from a specified range. In this example, a number between 1 and 100 is allocated.

const { NumberAllocator } = require('number-allocator');
const allocator = new NumberAllocator(1, 100);
const allocatedNumber = allocator.allocate();
console.log(`Allocated number: ${allocatedNumber}`);

Release a number

This feature allows you to release a previously allocated number, making it available for future allocations. In this example, the number 50 is released.

const { NumberAllocator } = require('number-allocator');
const allocator = new NumberAllocator(1, 100);
allocator.allocate();
allocator.release(50);
console.log('Number 50 released');

Check available numbers

This feature allows you to check which numbers are currently available for allocation. In this example, the available numbers within the range are printed.

const { NumberAllocator } = require('number-allocator');
const allocator = new NumberAllocator(1, 100);
allocator.allocate();
const availableNumbers = allocator.available();
console.log(`Available numbers: ${availableNumbers}`);

Check status of a specific number

This feature allows you to check whether a specific number is currently allocated. In this example, the status of number 50 is checked.

const { NumberAllocator } = require('number-allocator');
const allocator = new NumberAllocator(1, 100);
allocator.allocate();
const isAllocated = allocator.isAllocated(50);
console.log(`Is number 50 allocated? ${isAllocated}`);

Other packages similar to number-allocator

node-uuid

The node-uuid package is used to generate unique identifiers (UUIDs). While it does not manage a range of numbers like number-allocator, it serves a similar purpose in generating unique identifiers for resources.

shortid

The shortid package generates short, unique, non-sequential ids. It is useful for creating unique identifiers in a more compact form compared to UUIDs, but it does not manage a range of numbers like number-allocator.

nanoid

The nanoid package is a tiny, secure URL-friendly unique string ID generator. It is similar to shortid and node-uuid in that it generates unique identifiers, but it does not manage a range of numbers.

README

Unique number allocator for JavaScript.

Version 1.0.11

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]