Pawel Chmielowski - List.Prioritized-0.01
NAME
List.Prioritized - List which sorts elements by prirority
SYNOPSIS
// Import List.Prioritized module.
JSAN.use('List.Prioritized');
var list = new List.Prioritized();
list.insert("B", 2);
list.insert("A", 1);
list.insert("C", 3);
for (var i = 0; i < list.length; i++)
alerty(list[i]) // gives A, B and C
list.remove("A");
list.removeAt(1);
alert(list[0]+", "+list.length); // gives "B, 1"
var list2 = new List.Prioritized();
list.insert("A", 1);
list.insert("D", 4);
list2.insert("C", 3);
list2.insert("0", 0);
var i = new List.Prioritized.Iterator(list, list2);
while (i.hasNext())
alert(i.getNext()) // gives 0, A, B, C, D
i.reset();
alert(i.getNext()) // gives 0
DESCRIPTION
This module defines class which adds list with elements sorted by priority.
CLASSES
List.Prioritized class
This class implements list which keeps its elements sorted by priority value. It has interface simmilar to standard Array, but it only allows to add elements by insert() method (standard Array methods which can be used for this purpose like push() or unshift() throws exceptions in this class).
new List.Prioritized()
Create new object. It takes no arguments.
list.insert(ITEM, PRIORITY)
Add new element ITEM with priority PRIORITY to this list.
Returns ITEM
list.remove(ITEM)
Remove ITEM from list.
Returns index of removed element or null when none elements was removed.
list.push()
This operation cannot be used in this class, it throws exception.
list.unshift()
This operation cannot be used in this class, it throws exception.
list.pop()
It works like Array.pop() but also change internal structure.
list.shift()
It works like Array.pop() but also change internal structure.
list.splice()
Works simmilar to Array.splice() but only two argument version is supported. When called with > 2 arguments this method throws exception.
List.Prioritized.Iterator class
Define List.Prioritized iteratior class. It can be used to iterate List.Iterator lists in priority order.
It can iterate one or more list simultaneously.
new List.Prioritized.Iterator([LIST1, [LIST2, ...]])
Create new iterator which will process all elements of LIST1, LIST2... in priority order.
iterator.hasNext()
Checks that next element is avaialble. Returns false when all elements was already processed, true otherwise.
iterator.getNext()
Return next element and increment internal index counter.
When all elements was already processed returns undefined.
iterator.reset()
Reset internal index counter to initial value. All further getNext() operations will be processed from start of the list.
CAVEATS and NOTES
- Only iterators for 1, 2 or 3 lists are implemented
AUTHOR
Pawel Chmielowski <prefiks@aviary.pl>
COPYRIGHT
Copyright (c) 2005 Pawel Chmielowski. All rights reserved.
This module is free software; you can redistribute it and/or modify it
under the terms of the LGPL license.
/*
=head1 NAME
List.Prioritized - List which sorts elements by prirority
=head1 SYNOPSIS
// Import List.Prioritized module.
JSAN.use('List.Prioritized');
var list = new List.Prioritized();
list.insert("B", 2);
list.insert("A", 1);
list.insert("C", 3);
for (var i = 0; i < list.length; i++)
alerty(list[i]) // gives A, B and C
list.remove("A");
list.removeAt(1);
alert(list[0]+", "+list.length); // gives "B, 1"
var list2 = new List.Prioritized();
list.insert("A", 1);
list.insert("D", 4);
list2.insert("C", 3);
list2.insert("0", 0);
var i = new List.Prioritized.Iterator(list, list2);
while (i.hasNext())
alert(i.getNext()) // gives 0, A, B, C, D
i.reset();
alert(i.getNext()) // gives 0
=head1 DESCRIPTION
This module defines class which adds list with elements sorted by priority.
=cut
*/
if (!this.List) List = {};
if (!List.Prioritized) {
/*
=head1 CLASSES
=head2 List.Prioritized class
This class implements list which keeps its elements sorted by priority value. It
has interface simmilar to standard Array, but it only allows to add elements by
insert() method (standard Array methods which can be used for this purpose like
push() or unshift() throws exceptions in this class).
=head3 new List.Prioritized()
Create new object. It takes no arguments.
=cut
*/
List.Prioritized = function() {
this._priorities = [];
}
List.Prioritized.prototype =
{
VERSION: "0.01",
__proto__: Array.prototype,
/*
=head3 list.insert(ITEM, PRIORITY)
Add new element ITEM with priority PRIORITY to this list.
Returns ITEM
=cut
*/
insert: function(item, priority)
{
var a = 0;
var b = this.length-1;
var mid, val;
priority = priority || 0;
if (b < 0 || priority > this._priorities[b])
a = this.length;
else {
do {
mid = a + ((b-a)>>1);
if (priority < this._priorities[mid])
b = mid-1;
else if (priority > this._priorities[mid])
a = mid+1;
else {
a = mid;
break;
}
} while (a <= b);
}
Array.prototype.splice.call(this, a, 0, item);
this._priorities.splice(a, 0, priority);
return item;
},
/*
=head3 list.remove(ITEM)
Remove ITEM from list.
Returns index of removed element or C<null> when none elements was removed.
=cut
*/
remove: function(item)
{
var i;
for (i = 0; i < this.length; i++)
if (this[i] == item) {
Array.prototype.splice.call(this, i, 1);
this._priorities.splice(i, 1);
return i;
}
return null;
},
/*
=head3 list.push()
This operation cannot be used in this class, it throws exception.
=cut
*/
push: function()
{
throw "You cannot use push() on List.Prioritized"
},
/*
=head3 list.unshift()
This operation cannot be used in this class, it throws exception.
=cut
*/
unshift: function()
{
throw "You cannot use unshift() on List.Prioritized"
},
/*
=head3 list.pop()
It works like Array.pop() but also change internal structure.
=cut
*/
pop: function()
{
this._priorities.pop();
return Array.prototype.pop.call(this)
},
/*
=head3 list.shift()
It works like Array.pop() but also change internal structure.
=cut
*/
shift: function()
{
this._priorities.shift();
return Array.prototype.shift.call(this)
},
/*
=head3 list.splice()
Works simmilar to Array.splice() but only two argument version is supported.
When called with > 2 arguments this method throws exception.
=cut
*/
splice: function(index, howMany)
{
if (arguments.length > 2)
throw "You cannot use splice() on List.Prioritized to change some elements";
this._priorities.splice(index, howMany);
return Array.prototype.splice.call(this, index, howMany);
},
}
/*
=head2 List.Prioritized.Iterator class
Define List.Prioritized iteratior class. It can be used to iterate
List.Iterator lists in priority order.
It can iterate one or more list simultaneously.
=head3 new List.Prioritized.Iterator([LIST1, [LIST2, ...]])
Create new iterator which will process all elements of LIST1, LIST2...
in priority order.
=cut
*/
List.Prioritized.Iterator = function()
{
var i, r = [];
for (i = 0; i < arguments.length; i++)
if (arguments[i] && arguments[i].length)
r.push(arguments[i]);
switch (r.length) {
case 0:
return List.Prioritized._emptyIterator;
case 1:
break;
case 2:
return new List.Prioritized._Iterator2(r[0], r[1]);
case 3:
return new List.Prioritized._Iterator3(r[0], r[1], r[2]);
default:
return new List.Prioritized._IteratorMulti(r);
}
this.plist = r[0];
this.i = 0;
}
List.Prioritized.Iterator.prototype =
{
/*
=head3 iterator.hasNext()
Checks that next element is avaialble. Returns C<false> when all elements was
already processed, C<true> otherwise.
=cut
*/
hasNext: function()
{
return this.plist.length > this.i;
},
/*
=head3 iterator.getNext()
Return next element and increment internal index counter.
When all elements was already processed returns C<undefined>.
=cut
*/
getNext: function()
{
return this.plist[this.i++];
},
/*
=head3 iterator.reset()
Reset internal index counter to initial value. All further getNext()
operations will be processed from start of the list.
=cut
*/
reset: function()
{
this.i = 0;
}
}
List.Prioritized._emptyIterator =
{
hasNext: function()
{
return false;
},
getNext: function()
{
return null
},
reset: function()
{
}
}
List.Prioritized._Iterator2 = function(plist1, plist2)
{
if (arguments.length > 2)
return new PlistCompositeIteratorMulti(arguments);
this.p1 = plist1;
this.p2 = plist2;
this.i1 = 0;
this.i2 = 0;
}
List.Prioritized._Iterator2.prototype =
{
hasNext: function()
{
return this.p1.length > this.i1 || this.p2.length > this.i2;
},
getNext: function()
{
if (this.p1.length <= this.i1)
return this.p2[this.i2++];
if (this.p2.length <= this.i2)
return this.p1[this.i1++];
if (this.p1._priorities[this.i1] > this.p2._priorities[this.i2])
return this.p2[this.i2++];
return this.p1[this.i1++];
},
reset: function()
{
this.i1 = this.i2 = 0;
}
}
List.Prioritized._Iterator3 = function(plist1, plist2, plist3)
{
this.p1 = plist1;
this.p2 = plist2;
this.p3 = plist3;
this.i1 = 0;
this.i2 = 0;
this.i3 = 0;
}
List.Prioritized._Iterator3.prototype =
{
hasNext: function()
{
return this.p1.length > this.i1 || this.p2.length > this.i2 ||
this.p3.length > this.i3;
},
getNext: function()
{
if (this.p1.length <= this.i1)
if (this.p2.length <= this.i2)
return this.p3[this.i3++];
else
if (this.p3.length <= this.i3)
return this.p2[this.i2++];
else
if (this.p2._priorities[this.i2] > this.p3._priorities[this.i3])
return this.p3[this.i3++];
else
return this.p2[this.i2++];
else
if (this.p2.length <= this.i2)
if (this.p3.length <= this.i3)
return this.p1[this.i1++];
else
if (this.p1._priorities[this.i1] > this.p3._priorities[this.i3])
return this.p3[this.i3++];
else
return this.p1[this.i1++];
else
if (this.p3.length <= this.i3)
if (this.p1._priorities[this.i1] > this.p2._priorities[this.i2])
return this.p2[this.i2++];
else
return this.p1[this.i1++];
else
if (this.p1._priorities[this.i1] > this.p2._priorities[this.i2])
if (this.p2._priorities[this.i2] > this.p3._priorities[this.i3])
return this.p3[this.i3++];
else
return this.p2[this.i2++];
else
if (this.p1._priorities[this.i1] > this.p3._priorities[this.i3])
return this.p3[this.i3++];
else
return this.p1[this.i1++];
},
reset: function()
{
this.i1 = this.i2 = this.i3 = 0;
}
}
List.Prioritized._IteratorMulti = function(args)
{
throw "Multi argument iterator not implemented.";
}
}
/*
=head1 CAVEATS and NOTES
=over 2
=item * Only iterators for 1, 2 or 3 lists are implemented
=back
=head1 AUTHOR
Pawel Chmielowski <F<prefiks@aviary.pl>>
=head1 COPYRIGHT
Copyright (c) 2005 Pawel Chmielowski. All rights reserved.
This module is free software; you can redistribute it and/or modify it
under the terms of the LGPL license.
=cut
*/