Train

Train, a fast (FIFO) queue with rollback mechanism.

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

If you need a simple (LIFO) Stack, try Peela.

Install

1$ npm install train [-g]

require:

1var Train  = require( 'train' );

Run Tests

1$ cd train/
2$ npm test

Run Benchmarks

1$ cd train/
2$ npm run bench

Constructor

Create an instance, argument within [ ] is optional.

1Train( [ Object opt ] )
2// or
3new Train( [ Object opt ] )

#Options

Default options are listed.

1{
2    // init queue with some elements
3    head : []
4
5    // max limit for 'xpush', 'xconcat', 'x..' methods
6    , xlim : Infinity
7
8    // max size for the rollback queue
9    , rlim : Infinity
10}

Properties

Don't mess with these properties!

1/*
2 * Property to get the queue length.
3 *
4 * NOTE: Accessors are very slow,
5 * use size() method instead.
6 */
7Train.length : Number
8
9/*
10 * Property to set the queue size limit.
11 *
12 * NOTE: Only #xpush(), #xconcat() are affected by this limit.
13 */
14Train.xlim : Number
15
16/*
17 * Property to set the size limit for the rollback queue.
18 */
19Train.rlim : Number
20
21/*
22 * Property to get current iterator position in the queue.
23 *
24 * NOTE: manually changing this value directly affects the
25 * behaviour of iterator methods like #next() and #curr.
26 */
27Train.ipos : Number
28
29/*
30 * Property that indicates the current head element 
31 * position/index in the queue.
32 *
33 * WARNING: private property, don't mess with it.
34 */
35Train.hpos : Number
36
37/*
38 * Property that indicates the current roll position/index
39 * in the head queue.
40 *
41 * WARNING: private property, don't mess with it.
42 */
43Train.rpos : Number
44
45/*
46 * Property that indicates if the mechanism of rolling up
47 * is enabled or not. It is set by #rollUp() and unset by
48 * #rollBack() or #rollUp( false ).
49 *
50 * WARNING: private property, don't mess with it.
51 */
52Train.roll : Boolean
53
54/*
55 * An array that represents the current head of the queue.
56 *
57 * WARNING: private property, don't mess with it.
58 */
59Train.qhead : Array
60
61/*
62 * An array that represents the current tail of queue.
63 *
64 * NOTE: private property, don't mess with it.
65 */
66Train.qtail : Array
67
68/*
69 * An array for rollback mechanism.
70 *
71 * NOTE: private property, don't mess with it.
72 */
73Train.qroll : Array
74

Methods

Arguments within [ ] are optional.

1/*
2 * Get an element at a certain index.
3 */
4Train#get( [ Number index ] ) : Object
5
6/*
7 * Circular get.
8 */
9Train#cget( [ Number index ] ) : Object
10
11/*
12 * Return the index of an element in the queue, optionally
13 * starting the search from an offset index.
14 * If element was not found, it returns -1.
15 */
16Train#indexOf( Object el [, Number offset ] ) : Object
17
18/*
19 * Evict the first (head) element from the queue.
20 */
21Train#shift() : Object
22
23/* 
24 * Evict one or multiple elements, if a number k was specified,
25 * it returns an array of K elements, with K <= k.
26 * If k > # size(), all elements are returned.
27 *
28 * NOTE: #pop(k) elements is faster than executing #shift() * k times.
29 * NOTE: For popping all elements you could do Train#pop( Infinity )
30 */
31Train#pop( [ Number k ] ) : Array
32
33/*
34 * Slice a portion of train queue into a new array,
35 * from begin to end index.
36 *
37 * NOTE: Usage is the same as Array#slice method; it
38 * accepts negative indexes and numbers as strings.
39 */
40Train#slice( [ Number begin [, Number end ] ] ) : Array
41
42/*
43 * Start rolling up.
44 * From now, all items evicted from the queue could be
45 * restored, executing #rollBack().
46 * Disable rollUp passing false.
47 * It returns the current Train instance.
48 *
49 * NOTE: For now, there is no implemented mechanism, to
50 * directly limit the roll queue size.
51 */
52Train#rollUp( [ Boolean on ] ) : Train
53
54/*
55 * Do rollback; previously evicted items are restored
56 * to the head of queue. Optionally, it is possible to
57 * re-enable rollUp mechanism after the rollback, passing
58 * a true argument.
59 * It returns the current Train instance.
60 */
61Train#rollBack( [ Boolean rollUp ] ) : Train
62
63/*
64 * Return current element through the circular iterator.
65 */
66Train#curr() : Object
67
68/*
69* Get the current element through a circular iterator, also
70* incrementing the iterator counter/position by one; optionally,
71* it is possible to specify a number as the next iterator
72* position / index in the queue.
73*/
74Train#next( [ Number index ] ) : Object
75
76/*
77 * Push one or multiple objects into the queue. it uses
78 * the same signature as Array#push.
79 * It returns the current number of items.
80 */
81Train#push( [ Object obj1 [, Object obj2 .. ] ] ) : Number
82
83/*
84 * Push one or multiple objects into the queue,
85 * Unlike #push, if the addition of elements exceeds the
86 * xlim value, items aren't added but silently dropped.
87 * It returns the current number of items in the queue,
88 * or -1 if the current arguments/items were dropped.
89 */
90Train#xpush( [ Object obj1 [, Object obj2 .. ] ] ) : Number
91
92/*
93 * A slightly faster push, ~15% than #push.
94 * It is still possible to increase speed ( bypassing function call )
95 * pushing element(s) directly to the tail of the queue and to calculate
96 * current size, using:
97 *
98 * var t = Train()
99 *     , size = t.qtail.push( .. ) + t.qhead.length - me.hpos
100 *     // or for multiple arguments
101 *     , size = t.qtail.apply( t.qtail, [..] ) + t.qhead.length - me.hpos
102 *     ;
103 *
104 * See Benchmarks.
105 */
106Train#fpush( [ Object obj ] ) : Number
107
108/*
109 * Concatenate an Array to the queue.
110 * It returns the current Train instance.
111 *
112 * NOTE: It accepts a single argument, that could be also a generic element.
113 */
114Train#concat( [ Array array ] ) : Train
115
116/*
117 * Concatenate an Array to the queue.
118 * Unlike #concat, if the addition of elements, contained in the array,
119 * exceeds the xlim value, array is silently dropped.
120 * It returns the current number of items in the queue,
121 * or -1 if the current array was dropped.
122 *
123 * NOTE: It accepts a single argument, that could be also a generic element.
124 */
125Train#xconcat( [ Array array ] ) : Number
126
127/*
128 * Melt a list of Objects, preferably Train or Arrays to this queue;
129 * all Train queues will be emptied, all Arrays will be concatenated.
130 * Optionally, when boolean 'all' is true, it melts all items contained
131 * in the tlist argument.
132 * It returns the current queue size.
133 *
134 * NOTE: When 'all' is set to true, if an item in the tlist is not an
135 * instance of Train or Array, it will be added to the queue as is, 
136 * also null, NaN and undefined values.
137 */
138Train#melt( [ Array tlist [, Boolean all ] ] ) : Number
139
140/*
141 * Get the queue size.
142 */
143Train#size() : Number
144
145/*
146 * Empty the queue for default.
147 * If bool is set to false, no action will be done.
148 * It returns the number of elements evicted.
149 */
150Train#flush( [ Boolean bool ] ) : Number
151
152/*
153 * Apply a fn to every element of the queue, like Array#forEach;
154 * fn will get 3 arguments: ( Object element, Number index, Number qsize ).
155 *
156 * NOTE: on iteration, the size is fixed to the current queue size,
157 * then it is possible to push other elements to the tail, these
158 * added elements are not affected by iteration.
159 */
160Train#forEach( Function fn [, Object scope ] ) : Train
161
162/*
163 * Apply a fn to every element of the queue;
164 * fn will get 3 arguments: Object element, Number index, Function done.
165 * After that every fn will have called done(), the callback will be launched
166 * with an err argument ( if any has occurred ) and a number, representing
167 * the total processed / iterated elements in the queue.
168 *
169 * If boolean "evict" was set to true, after the last fn call to done(),
170 * the queue will be flushed.
171 *
172 * NOTE: when queue size is 0, the callback will be immediately executed
173 * with arguments: ( null, 0 ).
174 *
175 * NOTE: on iteration, the size is fixed to the current queue size,
176 * then it is possible to push other elements to the tail, these
177 * added elements are not affected by iteration.
178 */
179Train#iterate( Function fn [, Object scope [, Function cback [, Boolean evict ] ] ] ) : Train
180

MIT License

Copyright (c) 2012-present < 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.