Class Deque<E, R>

Operations at Both Ends: Supports adding and removing elements at both the front and back of the queue. This allows it to be used as a stack (last in, first out) and a queue (first in, first out).
Efficient Random Access: Being based on an array, it offers fast random access capability, allowing constant time access to any element.
Continuous Memory Allocation: Since it is based on an array, all elements are stored contiguously in memory, which can bring cache friendliness and efficient memory access.
Efficiency: Adding and removing elements at both ends of a deque is usually very fast. However, when the dynamic array needs to expand, it may involve copying the entire array to a larger one, and this operation has a time complexity of O(n).
Performance jitter: Deque may experience performance jitter, but DoublyLinkedList will not

Type Parameters

E = any
R = any

Hierarchy

IterableElementBase<E, R, Deque<E, R>>
- Deque

Constructors

constructor

new Deque<E, R>(elements?, options?): Deque<E, R>
The constructor initializes a Deque object with optional iterable of elements and options.
Type Parameters
- E = any
- R = any
Parameters
- elements: IterableWithSizeOrLength<E> | IterableWithSizeOrLength<R> = []
  An iterable object (such as an array or a Set) that contains the initial elements to be added to the deque. It can also be an object with a length or size property that represents the number of elements in the iterable object. If no elements are provided, an empty deque
- Optional options: DequeOptions<E, R>
  The options parameter is an optional object that can contain configuration options for the deque. In this code, it is used to set the bucketSize option, which determines the size of each bucket in the deque. If the bucketSize option is not provided or is not a number
Returns Deque<E, R>
Overrides IterableElementBase.constructor
- Defined in queue/deque.ts:31

Accessors

bucketCount

get bucketCount(): number
The function returns the number of buckets.

Returns number
The number of buckets.
- Defined in queue/deque.ts:124

bucketFirst

get bucketFirst(): number
The function returns the value of the protected variable _bucketFirst.

Returns number
The value of the _bucketFirst property.
- Defined in queue/deque.ts:82

bucketLast

get bucketLast(): number
The function returns the value of the protected variable _bucketLast.

Returns number
The value of the _bucketLast property, which is a number.
- Defined in queue/deque.ts:103

bucketSize

get bucketSize(): number
The bucketSize function returns the size of the bucket.

Returns number
The size of the bucket
- Defined in queue/deque.ts:72

buckets

get buckets(): E[][]
The buckets function returns the buckets property of the object.

Returns E[][]
The buckets property
- Defined in queue/deque.ts:134

first

get first(): undefined | E
The function returns the first element in a collection if it exists, otherwise it returns undefined.

Returns undefined | E
The first element of the collection, of type E, is being returned.
- Defined in queue/deque.ts:153

firstInBucket

get firstInBucket(): number
The function returns the value of the protected variable _firstInBucket.

Returns number
The method is returning the value of the variable _firstInBucket, which is of type number.
- Defined in queue/deque.ts:93

last

get last(): undefined | E
The last function returns the last element in the queue.

Returns undefined | E
The last element in the array
- Defined in queue/deque.ts:162

lastInBucket

get lastInBucket(): number
The function returns the value of the protected variable _lastInBucket.

Returns number
The method is returning the value of the variable _lastInBucket, which is of type number.
- Defined in queue/deque.ts:114

size

get size(): number
The size function returns the number of items in the stack.

Returns number
The number of values in the set
Overrides IterableElementBase.size
- Defined in queue/deque.ts:144

toElementFn

get toElementFn(): undefined | ((rawElement) => E)
The function returns the _toElementFn property, which is a function that converts a raw element to a specific type.

Returns undefined | ((rawElement) => E)
The function get toElementFn() is returning either a function that takes a raw element rawElement of type R and returns an element E, or undefined if no function is assigned to _toElementFn.
Inherited from IterableElementBase.toElementFn
- Defined in base/iterable-element-base.ts:28

Methods

[iterator]

[iterator](...args): IterableIterator<E>
Time Complexity: O(n) Space Complexity: O(1)

The function is an implementation of the Symbol.iterator method that returns an IterableIterator.
Parameters
- Rest ...args: any[]
  The args parameter in the code snippet represents a rest parameter. It allows the function to accept any number of arguments as an array. In this case, the args parameter is used to pass any number of arguments to the _getIterator method.
Returns IterableIterator<E>
Inherited from IterableElementBase.[iterator]
- Defined in base/iterable-element-base.ts:45

`Protected` _getBucketAndPosition

_getBucketAndPosition(pos): {
bucketIndex: number;
indexInBucket: number;
}
Time Complexity: O(1) Space Complexity: O(1)

The function calculates the bucket index and index within the bucket based on the given position.
Parameters
- pos: number
  The pos parameter represents the position within the data structure. It is a number that indicates the index or position of an element within the structure.
Returns {
bucketIndex: number;
indexInBucket: number;
}
an object with two properties: "bucketIndex" and "indexInBucket".
- bucketIndex: number
- indexInBucket: number
- Defined in queue/deque.ts:893

`Protected` _getIterator

_getIterator(): IterableIterator<E>
Time Complexity: O(n) Space Complexity: O(1)

The above function is an implementation of the iterator protocol in TypeScript, allowing the object to be iterated over using a for...of loop.

Returns IterableIterator<E>
Overrides IterableElementBase._getIterator
- Defined in queue/deque.ts:837

`Protected` _reallocate

_reallocate(needBucketNum?): void
Time Complexity: O(n) Space Complexity: O(n)

The _reallocate function reallocates the buckets in an array, adding new buckets if needed.
Parameters
- Optional needBucketNum: number
  The needBucketNum parameter is an optional number that specifies the number of new buckets needed. If not provided, it will default to half of the current bucket count (this._bucketCount >> 1) or 1 if the current bucket count is less than 2.
Returns void
- Defined in queue/deque.ts:857

addAt

addAt(pos, element, num?): boolean
Time Complexity: O(n) Space Complexity: O(n)

The addAt function inserts one or more elements at a specified position in an array-like data structure.
Parameters
- pos: number
  The pos parameter represents the position at which the element(s) should be inserted. It is of type number.
- element: E
  The element parameter represents the element that you want to insert into the array at the specified position.
- Optional num: number = 1
  The num parameter represents the number of times the element should be inserted at the specified position (pos). By default, it is set to 1, meaning that the element will be inserted once. However, you can provide a different value for num if you want
Returns boolean
The size of the array after the insertion is being returned.
- Defined in queue/deque.ts:416

at

at(pos): E
Time Complexity: O(1) Space Complexity: O(1)

The at function retrieves an element at a specified position in an array-like data structure.
Parameters
- pos: number
  The pos parameter represents the position of the element that you want to retrieve from the data structure. It is of type number and should be a valid index within the range of the data structure.
Returns E
The element at the specified position in the data structure is being returned.
- Defined in queue/deque.ts:368

begin

begin(): Generator<E, any, unknown>
The below function is a generator that yields elements from a collection one by one.

Returns Generator<E, any, unknown>
- Defined in queue/deque.ts:333

clear

clear(): void
Time Complexity: O(1) Space Complexity: O(1)

The clear() function resets the state of the object by initializing all variables to their default values.

Returns void
Overrides IterableElementBase.clear
- Defined in queue/deque.ts:323

clone

clone(): Deque<E, R>
Time Complexity: O(n) Space Complexity: O(n)

The clone() function returns a new instance of the Deque class with the same elements and bucket size as the original instance.

Returns Deque<E, R>
The clone() method is returning a new instance of the Deque class with the same elements as the original deque (this) and the same bucket size.
Overrides IterableElementBase.clone
- Defined in queue/deque.ts:754

cut

cut(pos, isCutSelf?): Deque<E, any>
Time Complexity: O(1) Space Complexity: O(1)

The cut function updates the state of the object based on the given position and returns the updated size.
Parameters
- pos: number
  The pos parameter represents the position at which the string should be cut. It is a number that indicates the index of the character where the cut should be made.
- isCutSelf: boolean = false
  If true, the original deque will not be cut, and return a new deque
Returns Deque<E, any>
The method is returning the updated size of the data structure.
- Defined in queue/deque.ts:451

cutRest

cutRest(pos, isCutSelf?): Deque<E, any>
Time Complexity: O(1) Space Complexity: O(1) or O(n)

The cutRest function cuts the elements from a specified position in a deque and returns a new deque with the cut elements.
Parameters
- pos: number
  The pos parameter represents the position from which to cut the Deque. It is a number that indicates the index of the element in the Deque where the cut should start.
- Optional isCutSelf: boolean = false
  isCutSelf is a boolean parameter that determines whether the original Deque should be modified or a new Deque should be created. If isCutSelf is true, the original Deque will be modified by cutting off elements starting from the specified position. If isCutSelf is false, a new De
Returns Deque<E, any>
The function cutRest returns either the modified original deque (this) or a new deque (newDeque) depending on the value of the isCutSelf parameter.
- Defined in queue/deque.ts:493

delete

delete(element): boolean
Time Complexity: O(n) Space Complexity: O(1)

The delete function removes all occurrences of a specified element from an array-like data structure.
Parameters
- element: E
  The element parameter represents the element that you want to delete from the data structure.
Returns boolean
The size of the data structure after the element has been deleted.
- Defined in queue/deque.ts:564

deleteAt

deleteAt(pos): boolean
Time Complexity: O(n) Space Complexity: O(1) or O(n)

The deleteAt function removes an element at a specified position in an array-like data structure.
Parameters
- pos: number
  The pos parameter in the deleteAt function represents the position at which an element needs to be deleted from the data structure. It is of type number and indicates the index of the element to be deleted.
Returns boolean
The size of the data structure after the deletion operation is performed.
- Defined in queue/deque.ts:531

every

every(predicate, thisArg?): boolean
Time Complexity: O(n) Space Complexity: O(1)

The every function checks if every element in the array satisfies a given predicate.
Parameters
- predicate: ElementCallback<E, R, boolean, Deque<E, R>>
  The predicate parameter is a callback function that takes three arguments: the current element being processed, its index, and the array it belongs to. It should return a boolean value indicating whether the element satisfies a certain condition or not.
- Optional thisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as this when executing the predicate function. If thisArg is provided, it will be passed as the this value to the predicate function. If thisArg is
Returns boolean
The every method is returning a boolean value. It returns true if every element in the array satisfies the provided predicate function, and false otherwise.
Inherited from IterableElementBase.every
- Defined in base/iterable-element-base.ts:83

filter

filter(predicate, thisArg?): Deque<E, R>
Time Complexity: O(n) Space Complexity: O(n)

The filter function creates a new deque containing elements from the original deque that satisfy a given predicate function.
Parameters
- predicate: ElementCallback<E, R, boolean, Deque<E, R>>
  The predicate parameter is a callback function that takes three arguments: the current element being iterated over, the index of the current element, and the deque itself. It should return a boolean value indicating whether the element should be included in the filtered deque or not.
- Optional thisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as this when executing the predicate function. If thisArg is provided, it will be passed as the this value to the predicate function. If thisArg is
Returns Deque<E, R>
The filter method is returning a new Deque object that contains the elements that satisfy the given predicate function.
Overrides IterableElementBase.filter
- Defined in queue/deque.ts:779

find

find(callbackfn, thisArg?): undefined | E
Time Complexity: O(n) Space Complexity: O(1)

The find function iterates over the elements of an array-like object and returns the first element that satisfies the provided callback function.
Parameters
- callbackfn: ElementCallback<E, R, boolean, Deque<E, R>>
  The callbackfn parameter is a function that will be called for each element in the array. It takes three arguments: the current element being processed, the index of the current element, and the array itself. The function should return a boolean value indicating whether the current element matches the desired condition.
- Optional thisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as this when executing the callbackfn function. If thisArg is provided, it will be passed as the this value to the callbackfn function. If thisArg @returns The findmethod returns the first element in the array that satisfies the provided callback function. If no element satisfies the callback function,undefined` is returned.
Returns undefined | E
Inherited from IterableElementBase.find
- Defined in base/iterable-element-base.ts:172

forEach

forEach(callbackfn, thisArg?): void
Time Complexity: O(n) Space Complexity: O(1)

The forEach function iterates over each element in an array-like object and calls a callback function for each element.
Parameters
- callbackfn: ElementCallback<E, R, void, Deque<E, R>>
  The callbackfn parameter is a function that will be called for each element in the array. It takes three arguments: the current element being processed, the index of the current element, and the array that forEach was called upon.
- Optional thisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as this when executing the callbackfn function. If thisArg is provided, it will be passed as the this value to the callbackfn function. If `thisArg
Returns void
Inherited from IterableElementBase.forEach
- Defined in base/iterable-element-base.ts:144

has

has(element): boolean
Time Complexity: O(n) Space Complexity: O(1)

The function checks if a given element exists in a collection.
Parameters
- element: E
  The parameter "element" is of type E, which means it can be any type. It represents the element that we want to check for existence in the collection.
Returns boolean
a boolean value. It returns true if the element is found in the collection, and false otherwise.
Inherited from IterableElementBase.has
- Defined in base/iterable-element-base.ts:191

indexOf

indexOf(element): number
Time Complexity: O(n) Space Complexity: O(1)

The function "indexOf" returns the index of the first occurrence of a given element in an array, or -1 if the element is not found.
Parameters
- element: E
  The "element" parameter represents the element that you want to find the index of in the data structure.
Returns number
The indexOf function returns the index of the first occurrence of the specified element in the data structure. If the element is not found, it returns -1.
- Defined in queue/deque.ts:715

isEmpty

isEmpty(): boolean
Time Complexity: O(1) Space Complexity: O(1)

The function checks if the size of an object is equal to zero and returns a boolean value.

Returns boolean
A boolean value indicating whether the size of the object is 0 or not.
Overrides IterableElementBase.isEmpty
- Defined in queue/deque.ts:307

map

map<EM, RM>(callback, toElementFn?, thisArg?): Deque<EM, RM>
The map function takes a callback function and applies it to each element in the deque, returning a new deque with the results.
Type Parameters
- EM
- RM
Parameters
- callback: ElementCallback<E, R, EM, Deque<E, R>>
  The callback parameter is a function that will be called for each element in the deque. It takes three arguments: the current element, the index of the element, and the deque itself. It should return a value of type EM.
- Optional toElementFn: ((rawElement) => EM)
  The toElementFn parameter is an optional function that can be used to transform the raw element (RM) into a new element (EM) before adding it to the new deque. If provided, this function will be called for each raw element in the original deque.
  - - (rawElement): EM
    - Parameters
      rawElement: RM
      Returns EM
- Optional thisArg: any
  The thisArg parameter is an optional argument that allows you to specify the value of this within the callback function. It is used to set the context or scope in which the callback function will be executed. If thisArg is provided, it will be used as the value of
Returns Deque<EM, RM>
a new Deque object with elements of type EM and raw elements of type RM.
Overrides IterableElementBase.map
- Defined in queue/deque.ts:811

pop

pop(): undefined | E
Time Complexity: O(1) Space Complexity: O(1)

The pop() function removes and returns the last element from a data structure, updating the internal state variables accordingly.

Returns undefined | E
The element that was removed from the data structure is being returned.
- Defined in queue/deque.ts:212

print

print(): void
Time Complexity: O(n) Space Complexity: O(n)

The print function logs the elements of an array to the console.

Returns void
Inherited from IterableElementBase.print
- Defined in base/iterable-element-base.ts:235

push

push(element): boolean
Time Complexity - Amortized O(1) (possible reallocation), Space Complexity - O(n) (due to potential resizing).

The push function adds an element to a data structure and reallocates memory if necessary.
Parameters
- element: E
  The element parameter represents the value that you want to add to the data structure.
Returns boolean
The size of the data structure after the element has been pushed.
- Defined in queue/deque.ts:181

reduce

reduce<U>(callbackfn, initialValue): U
Time Complexity: O(n) Space Complexity: O(1)

The reduce function iterates over the elements of an array-like object and applies a callback function to reduce them into a single value.
Type Parameters
- U
Parameters
- callbackfn: ReduceElementCallback<E, R, U, Deque<E, R>>
  The callbackfn parameter is a function that will be called for each element in the array. It takes four arguments:
- initialValue: U
  The initialValue parameter is the initial value of the accumulator. It is the value that the accumulator starts with before the reduction operation begins.
Returns U
The reduce method is returning the final value of the accumulator after iterating over all the elements in the array and applying the callback function to each element.
Inherited from IterableElementBase.reduce
- Defined in base/iterable-element-base.ts:215

reverse

reverse(): Deque<E, R>
Time Complexity: O(n) Space Complexity: O(1)

The reverse() function reverses the order of the buckets and the elements within each bucket in a data structure.

Returns Deque<E, R>
The reverse() method is returning the object itself (this) after performing the reverse operation on the buckets and updating the relevant properties.
- Defined in queue/deque.ts:595

reverseBegin

reverseBegin(): Generator<E, any, unknown>
The function reverseBegin() is a generator that yields elements in reverse order starting from the last element.

Returns Generator<E, any, unknown>
- Defined in queue/deque.ts:345

setAt

setAt(pos, element): boolean
Time Complexity: O(1) Space Complexity: O(1)

The setAt function sets an element at a specific position in an array-like data structure.
Parameters
- pos: number
  The pos parameter represents the position at which the element needs to be set. It is of type number.
- element: E
  The element parameter is the value that you want to set at the specified position in the data structure.
Returns boolean
- Defined in queue/deque.ts:389

shift

shift(): undefined | E
Time Complexity: O(1) Space Complexity: O(1)

The shift() function removes and returns the first element from a data structure, updating the internal state variables accordingly.

Returns undefined | E
The element that is being removed from the beginning of the data structure is being returned.
- Defined in queue/deque.ts:277

shrinkToFit

shrinkToFit(): void
Time Complexity: O(n) Space Complexity: O(n)

The shrinkToFit function reorganizes the elements in an array-like data structure to minimize memory usage.

Returns void
Nothing is being returned. The function is using the return statement to exit early if this.size is 0, but it does not return any value.
- Defined in queue/deque.ts:678

some

some(predicate, thisArg?): boolean
Time Complexity: O(n) Space Complexity: O(1)

The "some" function checks if at least one element in a collection satisfies a given predicate.
Parameters
- predicate: ElementCallback<E, R, boolean, Deque<E, R>>
  The predicate parameter is a callback function that takes three arguments: value, index, and array. It should return a boolean value indicating whether the current element satisfies the condition.
- Optional thisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as the this value when executing the predicate function. If thisArg is provided, it will be passed as the this value to the predicate function. If `thisArg
Returns boolean
a boolean value. It returns true if the predicate function returns true for any element in the collection, and false otherwise.
Inherited from IterableElementBase.some
- Defined in base/iterable-element-base.ts:116

sort

sort(comparator?): Deque<E, R>
Time Complexity: O(n log n) Space Complexity: O(n)

The sort function sorts the elements in a data structure using a provided comparator function.
Parameters
- Optional comparator: ((x, y) => number)
  The comparator parameter is a function that takes in two elements x and y of type E and returns a number. The comparator function is used to determine the order of the elements in the sorted array.
  - - (x, y): number
    - Parameters
      x: E
      y: E
      Returns number
Returns Deque<E, R>
Deque
- Defined in queue/deque.ts:652

toArray

toArray(): E[]
Time Complexity: O(n) Space Complexity: O(n)

The toArray function converts the elements of a data structure into an array.

Returns E[]
The toArray() method is returning an array of elements of type E.
- Defined in queue/deque.ts:736

unique

unique(): Deque<E, R>
Time Complexity: O(n) Space Complexity: O(1)

The unique() function removes duplicate elements from an array-like data structure and returns the number of unique elements.

Returns Deque<E, R>
The size of the modified array is being returned.
- Defined in queue/deque.ts:620

unshift

unshift(element): boolean
Time Complexity: Amortized O(1) Space Complexity: O(n)

The unshift function adds an element to the beginning of an array-like data structure and returns the new size of the structure.
Parameters
- element: E
  The element parameter represents the element that you want to add to the beginning of the data structure.
Returns boolean
The size of the data structure after the element has been added.
- Defined in queue/deque.ts:245

values

values(): IterableIterator<E>
Time Complexity: O(n) Space Complexity: O(n)

The function returns an iterator that yields all the values in the object.

Returns IterableIterator<E>
Inherited from IterableElementBase.values
- Defined in base/iterable-element-base.ts:59

Class Deque<E, R>

Type Parameters

E = any

R = any

Hierarchy

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

E = any

R = any

Parameters

elements: IterableWithSizeOrLength<E> | IterableWithSizeOrLength<R> = []

Optional options: DequeOptions<E, R>

Returns Deque<E, R>

Accessors

bucketCount

Returns number

bucketFirst

Returns number

bucketLast

Returns number

bucketSize

Returns number

buckets

Returns E[][]

first

Returns undefined | E

firstInBucket

Returns number

last

Returns undefined | E

lastInBucket

Returns number

size

Returns number

toElementFn

Returns undefined | ((rawElement) => E)

Methods

[iterator]

Parameters

Rest ...args: any[]

Returns IterableIterator<E>

Protected _getBucketAndPosition

Parameters

pos: number

Returns { bucketIndex: number; indexInBucket: number; }

bucketIndex: number

indexInBucket: number

Protected _getIterator

Returns IterableIterator<E>

Protected _reallocate

Parameters

Optional needBucketNum: number

Returns void

addAt

Parameters

pos: number

element: E

Optional num: number = 1

Returns boolean

at

Parameters

pos: number

Returns E

begin

Returns Generator<E, any, unknown>

clear

Returns void

clone

Returns Deque<E, R>

cut

Parameters

pos: number

isCutSelf: boolean = false

Returns Deque<E, any>

cutRest

`Optional` options: DequeOptions<E, R>

`Rest` ...args: any[]

`Protected` _getBucketAndPosition

Returns {
bucketIndex: number;
indexInBucket: number;
}

`Protected` _getIterator

`Protected` _reallocate

`Optional` needBucketNum: number

`Optional` num: number = 1

`Optional` isCutSelf: boolean = false

`Optional` thisArg: any

`Optional` thisArg: any

`Optional` thisArg: any

`Optional` thisArg: any

`Optional` toElementFn: ((rawElement) => EM)

`Optional` thisArg: any