train

Train, an implementation of a ( FIFO ) Queue data structure. Behind the scenes, it uses 2 arrays, to simulate and perform fast shifting and popping operations, without using the Array#shift() method..

npm install train
34 downloads in the last day
124 downloads in the last week
165 downloads in the last month

Train

build status NPM version

NPM

NPM

Train, an implementation of a (FIFO) Queue data structure.

Behind the scenes, it uses 2 arrays, to simulate and perform fast shifting and popping operations, without using the Array#shift() method.

Note:

Array#shift method shows an high loss of performances when the array is very long; for example, on my cheap laptop the bottleneck occurs when I fill an array with more than 2^17 items. It implies that for shorter array lengths, is still possible to use Array#shift.

Test by yourself launching benchmarks or manually tuning the power value p in this bench file.

Install

$ npm install train [-g]

require:

var Train  = require( 'train' );

Run Tests

$ cd train/
$ npm test

Run Benchmarks

$ cd train/
$ npm run-script bench

Constructor

Create an instance, optionally with an Array of elements and a limit value for the queue size.

Train( [ Array elements [, Number xlim ] ] )
// or
new Train( [ Array elements [, Number xlim ] ] )

Properties

/*
 * Property to get the queue length.
 *
 * NOTE: Accessors are very slow,
 * use size() method instead.
 */
Train.length : Number

/*
 * Property to set the queue size limit.
 *
 * NOTE: Only #xpush(), #xconcat() are affected by this limit.
 */
Train.xlim : Number

/*
 * Property to get current iterator position in the queue.
 *
 * NOTE: manually changing this value directly affects the
 * behaviour of iterator methods like #next() and #curr.
 */
Train.ipos : Number

/*
 * Property that indicates the current head element 
 * position/index in the queue.
 *
 * WARNING: private property, don't change it manually.
 */
Train.hpos : Number

/*
 * An array that represents the current head of the queue.
 *
 * WARNING: private property, don't change it manually.
 */
Train.qhead : Number

/*
 * An array that represents the current tail of queue.
 *
 * NOTE: private property, don't change it manually.
 */
Train.qtail : Number

Methods

Arguments within [ ] are optional.

/*
 * Get an element at certain index.
 */
Train#get( [ Number index ] ) : Object

/*
 * Circular get.
 */
Train#cget( [ Number index ] ) : Object

/*
 * Evict the first (head) element from the queue.
 */
Train#shift() : Object

/* 
 * Evict multiple elements; if a number k was specified, it returns
 * an array of K elements, with K <= k. If k > size(), all elements
 * are returned.
 *
 * NOTE: #pop() k elements is faster than executing #shift() * k times.
 * For popping all elements you could do: Train#pop( Infinity )
 */
Train#pop( [ Number k ] ) : Array

/*
 * Slice a portion of train queue into a new array,
 * from begin to end index.
 *
 * NOTE: Usage is the same as Array#slice method; it
 * accepts negative indexes and numbers as strings.
 */
Train#slice( [ begin [, end ] ] ) : Array

/*
 * Return current element through the circular iterator.
 */
Train#curr() : Object

/*
* Get the current element through a circular iterator, also
* incrementing the iterator counter/position by one; optionally,
* it is possible to specify a number as the next iterator
* position / index in the queue.
*/
Train#next( [ Number index ] ) : Object

/*
 * Push one or multiple objects into the queue. it uses
 * the same signature as Array#push.
 * It returns the current number of items in the queue.
 */
Train#push( [ Object obj1 [, Object obj2 .. ] ] ) : Number

/*
 * Push one or multiple objects into the queue,
 * Unlike #push, if the addition of elements exceeds the
 * xlim value, items aren't added but silently dropped.
 * It returns the current number of items in the queue,
 * or -1 if the current arguments/items were dropped.
 */
Train#xpush( [ Object obj1 [, Object obj2 .. ] ] ) : Number

/*
 * A slightly faster push, ~15% than #push.
 * It is still possible to increase speed ( bypassing function call )
 * pushing element(s) directly to the tail of the queue and to calculate
 * current size, using:
 *
 * var t = Train()
 *     , size = t.qtail.push( .. ) + t.qhead.length - me.hpos
 *     // or for multiple arguments
 *     , size = t.qtail.apply( t.qtail, [..] ) + t.qhead.length - me.hpos
 *     ;
 *
 * See Benchmarks.
 */
Train#fpush( [ Object obj ] ) : Number

/*
 * Concatenate an Array to the queue.
 * It returns the current Train instance.
 *
 * NOTE: It accepts a single argument, that could be also a generic element.
 */
Train#concat( [ Array array ] ) : Train

/*
 * Concatenate an Array to the queue.
 * Unlike #concat, if the addition of elements, contained in the array,
 * exceeds the xlim value, array is silently dropped.
 * It returns the current number of items in the queue,
 * or -1 if the current array was dropped.
 *
 * NOTE: It accepts a single argument, that could be also a generic element.
 */
Train#xconcat( [ Array array ] ) : Number

/*
 * Melt a list of Objects, preferably Train or Arrays to this queue;
 * all Train queues will be emptied, all Arrays will be concatenated.
 * Optionally, when boolean 'all' is true, it melts all items contained
 * in the tlist argument.
 * It returns the current queue size.
 *
 * NOTE: When 'all' is set to true, if an item in the tlist is not an
 * instance of Train or Array, it will be added to the queue as is, 
 * also null, NaN and undefined values.
 */
Train#melt( [ Array tlist [, Boolean all ] ] ) : Number

/*
 * Get the queue size.
 */
Train#size() : Number

/*
 * Empty the queue for default.
 * If bool is set to false, no action will be done.
 * It returns the number of elements evicted.
 */
Train#flush( [ Boolean bool ]) : Number

/*
 * Apply a fn to every element of the queue, like Array#forEach;
 * fn will get 3 arguments: ( Object element, Number index, Number qsize ).
 *
 * NOTE: on iteration, the size is fixed to the current queue size,
 * then it is possible to push other elements to the tail, these
 * added elements are not affected by iteration.
 */
Train#forEach( Function fn [, Object scope ] ) : Train

/*
 * Apply a fn to every element of the queue;
 * fn will get 3 arguments: Object element, Number index, Function done.
 * After that every fn will have called done(), the callback will be launched
 * with an err argument ( if any has occurred ) and a number, representing
 * the total processed / iterated elements in the queue.
 *
 * If boolean "evict" was set to true, after the last fn call to done(),
 * the queue will be flushed.
 *
 * NOTE: when queue size is 0, the callback will be immediately executed
 * with arguments: ( null, 0 ).
 *
 * NOTE: on iteration, the size is fixed to the current queue size,
 * then it is possible to push other elements to the tail, these
 * added elements are not affected by iteration.
 */
Train#iterate( Function fn [, Object scope, [, Function cback [, Boolean evict ] ] ] ) : Train

MIT License

Copyright (c) 2013 < Guglielmo Ferri : 44gatti@gmail.com >

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the 'Software'), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

npm loves you