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 (view full)

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
- Optionaloptions: 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:136

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:94

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:115

buckets

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

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

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:73

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:165

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:105

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:174

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:126

maxLen

get maxLen(): number
The maxLen function returns the max length of the deque.

Returns number
The max length of the deque
- Defined in queue/deque.ts:84

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:156

toElementFn

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

Returns undefined | ((rawElement: R) => 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

`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:784

`Protected`_getIterator

_getIterator(): IterableIterator<E, any, any>
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, any, any>
Overrides IterableElementBase._getIterator
- Defined in queue/deque.ts:738

`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
- OptionalneedBucketNum: 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:753

[iterator]

[iterator](...args): IterableIterator<E, any, any>
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, any, any>
Inherited from IterableElementBase.[iterator]
- Defined in base/iterable-element-base.ts:41

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.
- Optionalnum: 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:385

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:347

begin

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

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

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:307

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:667

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:415

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.
- OptionalisCutSelf: 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:452

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:512

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:484

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.
- OptionalthisArg: 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:71

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.
- OptionalthisArg: 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:687

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.
- OptionalthisArg: 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:141

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.
- OptionalthisArg: 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:118

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:160

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:638

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:296

map

map<EM, RM>(callback, toElementFn?, thisArg?): Deque<EM, RM>
Time Complexity: O(n) Space Complexity: O(n)

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.
- OptionaltoElementFn: ((rawElement: RM) => 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
- OptionalthisArg: 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:717

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:215

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:205

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:188

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:180

reverse

reverse(): this
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 this
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:538

reverseBegin

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

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

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:363

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:271

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:606

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.
- OptionalthisArg: 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:95

sort

sort(comparator?): this
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
- Optionalcomparator: ((x: E, y: E) => 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 this
Deque
- Defined in queue/deque.ts:585

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:654

toVisual

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

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

Returns E[]
Inherited from IterableElementBase.toVisual
- Defined in base/iterable-element-base.ts:195

unique

unique(): this
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 this
The size of the modified array is being returned.
- Defined in queue/deque.ts:558

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:243

values

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

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

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

Class Deque<E, R>

Type Parameters

Hierarchy (view full)

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Deque<E, R>

Accessors

bucketCount

Returns number

bucketFirst

Returns number

bucketLast

Returns number

buckets

Returns E[][]

bucketSize

Returns number

first

Returns undefined | E

firstInBucket

Returns number

last

Returns undefined | E

lastInBucket

Returns number

maxLen

Returns number

size

Returns number

toElementFn

Returns undefined | ((rawElement: R) => E)

Methods

Protected_getBucketAndPosition

Parameters

Returns { bucketIndex: number; indexInBucket: number; }

bucketIndex: number

indexInBucket: number

Protected_getIterator

Returns IterableIterator<E, any, any>

Protected_reallocate

Parameters

Returns void

[iterator]

Parameters

Returns IterableIterator<E, any, any>

addAt

Parameters

Returns boolean

at

Parameters

Returns E

begin

Returns Generator<E, any, any>

clear

Returns void

clone

Returns Deque<E, R>

cut

Parameters

Returns Deque<E, any>

cutRest

Parameters

Returns Deque<E, any>

delete

Parameters

Returns boolean

deleteAt

Parameters

Returns boolean

every

Parameters

Returns boolean

filter

Parameters

`Protected`_getBucketAndPosition

Returns {
bucketIndex: number;
indexInBucket: number;
}

`Protected`_getIterator

`Protected`_reallocate