123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478 |
|
/*******************************************************************************
copyright: Copyright (c) 2008 Kris Bell. All rights reserved
license: BSD style: $(LICENSE)
version: Apr 2008: Initial release
authors: Kris
Since: 0.99.7
Based upon Doug Lea's Java collection package
*******************************************************************************/
module tango.util.container.Slink;
import tango.util.container.model.IContainer;
/*******************************************************************************
Slink instances provide standard linked list next-fields, and
support standard operations upon them. Slink structures are pure
implementation tools, and perform no argument checking, no result
screening, and no synchronization. They rely on user-level classes
(see HashSet, for example) to do such things.
Still, Slink is made `public' so that you can use it to build other
kinds of containers
Note that when K is specified, support for keys are enabled. When
Identity is stipulated as 'true', those keys are compared using an
identity-comparison instead of equality (using 'is'). Similarly, if
HashCache is set true, an additional attribute is create in order to
retain the hash of K
*******************************************************************************/
alias int KeyDummy;
struct Slink (V, K=KeyDummy, bool Identity = false, bool HashCache = false)
{
alias Slink!(V, K, Identity, HashCache) Type;
alias Type *Ref;
alias Compare!(V) Comparator;
Ref next; // pointer to next
V value; // element value
static if (HashCache == true)
{
hash_t cache; // retain hash value?
}
/***********************************************************************
add support for keys also?
***********************************************************************/
static if (!is(typeof(K) == KeyDummy))
{
K key;
final Ref set (K k, V v, Ref n)
{
key = k;
return set (v, n);
}
final hash_t hash()
{
return typeid(K).getHash(&key);
}
final Ref findKey (K key)
{
static if (Identity == true)
{
for (auto p=&this; p; p = p.next)
if (key is p.key)
return p;
}
else
{
for (auto p=&this; p; p = p.next)
if (key == p.key)
return p;
}
return null;
}
final Ref findPair (K key, V value)
{
static if (Identity == true)
{
for (auto p=&this; p; p = p.next)
if (key is p.key && value == p.value)
return p;
}
else
{
for (auto p=&this; p; p = p.next)
if (key == p.key && value == p.value)
return p;
}
return null;
}
final const int indexKey (K key)
{
int i = 0;
static if (Identity == true)
{
for (auto p=&this; p; p = p.next, ++i)
if (key is p.key)
return i;
}
else
{
for (auto p=&this; p; p = p.next, ++i)
if (key == p.key)
return i;
}
return -1;
}
final const int indexPair (K key, V value)
{
int i = 0;
static if (Identity == true)
{
for (auto p=&this; p; p = p.next, ++i)
if (key is p.key && value == p.value)
return i;
}
else
{
for (auto p=&this; p; p = p.next, ++i)
if (key == p.key && value == p.value)
return i;
}
return -1;
}
final int countKey (K key)
{
int c = 0;
static if (Identity == true)
{
for (auto p=&this; p; p = p.next)
if (key is p.key)
++c;
}
else
{
for (auto p=&this; p; p = p.next)
if (key == p.key)
++c;
}
return c;
}
final int countPair (K key, V value)
{
int c = 0;
static if (Identity == true)
{
for (auto p=&this; p; p = p.next)
if (key is p.key && value == p.value)
++c;
}
else
{
for (auto p=&this; p; p = p.next)
if (key == p.key && value == p.value)
++c;
}
return c;
}
}
/***********************************************************************
Set to point to n as next cell
param: n, the new next cell
***********************************************************************/
final Ref set (V v, Ref n)
{
next = n;
value = v;
return &this;
}
/***********************************************************************
Splice in p between current cell and whatever it was
previously pointing to
param: p, the cell to splice
***********************************************************************/
final void attach (Ref p)
{
if (p)
p.next = next;
next = p;
}
/***********************************************************************
Cause current cell to skip over the current next() one,
effectively removing the next element from the list
***********************************************************************/
final void detachNext()
{
if (next)
next = next.next;
}
/***********************************************************************
Linear search down the list looking for element
param: element to look for
Returns: the cell containing element, or null if no such
***********************************************************************/
final Ref find (V element)
{
for (auto p = &this; p; p = p.next)
if (element == p.value)
return p;
return null;
}
/***********************************************************************
Return the number of cells traversed to find first occurrence
of a cell with element() element, or -1 if not present
***********************************************************************/
final const int index (V element)
{
int i;
for (auto p = &this; p; p = p.next, ++i)
if (element == p.value)
return i;
return -1;
}
/***********************************************************************
Count the number of occurrences of element in list
***********************************************************************/
final const int count (V element)
{
int c;
for (auto p = &this; p; p = p.next)
if (element == p.value)
++c;
return c;
}
/***********************************************************************
Return the number of cells in the list
***********************************************************************/
final const int count ()
{
int c;
for (auto p = &this; p; p = p.next)
++c;
return c;
}
/***********************************************************************
Return the cell representing the last element of the list
(i.e., the one whose next() is null
***********************************************************************/
final Ref tail ()
{
auto p = &this;
while (p.next)
p = p.next;
return p;
}
/***********************************************************************
Return the nth cell of the list, or null if no such
***********************************************************************/
final Ref nth (int n)
{
auto p = &this;
for (int i; i < n; ++i)
p = p.next;
return p;
}
/***********************************************************************
Make a copy of the list; i.e., a new list containing new cells
but including the same elements in the same order
***********************************************************************/
final Ref copy (scope Ref delegate() alloc)
{
auto newlist = dup (alloc);
auto current = newlist;
for (auto p = next; p; p = p.next)
{
current.next = p.dup (alloc);
current = current.next;
}
current.next = null;
return newlist;
}
/***********************************************************************
dup is shallow; i.e., just makes a copy of the current cell
***********************************************************************/
Ref dup (scope Ref delegate() alloc)
{
auto ret = alloc();
static if (is(typeof(K) == KeyDummy))
ret.set (value, next);
else
ret.set (key, value, next);
return ret;
}
/***********************************************************************
Basic linkedlist merge algorithm.
Merges the lists head by fst and snd with respect to cmp
param: fst head of the first list
param: snd head of the second list
param: cmp a Comparator used to compare elements
Returns: the merged ordered list
***********************************************************************/
static Ref merge (Ref fst, Ref snd, Comparator cmp)
{
auto a = fst;
auto b = snd;
Ref hd = null;
Ref current = null;
for (;;)
{
if (a is null)
{
if (hd is null)
hd = b;
else
current.next = b;
return hd;
}
else
if (b is null)
{
if (hd is null)
hd = a;
else
current.next = a;
return hd;
}
int diff = cmp (a.value, b.value);
if (diff <= 0)
{
if (hd is null)
hd = a;
else
current.next = a;
current = a;
a = a.next;
}
else
{
if (hd is null)
hd = b;
else
current.next = b;
current = b;
b = b.next;
}
}
}
/***********************************************************************
Standard list splitter, used by sort.
Splits the list in half. Returns the head of the second half
param: s the head of the list
Returns: the head of the second half
***********************************************************************/
static Ref split (Ref s)
{
auto fast = s;
auto slow = s;
if (fast is null || fast.next is null)
return null;
while (fast)
{
fast = fast.next;
if (fast && fast.next)
{
fast = fast.next;
slow = slow.next;
}
}
auto r = slow.next;
slow.next = null;
return r;
}
/***********************************************************************
Standard merge sort algorithm
param: s the list to sort
param: cmp, the comparator to use for ordering
Returns: the head of the sorted list
***********************************************************************/
static Ref sort (Ref s, Comparator cmp)
{
if (s is null || s.next is null)
return s;
else
{
auto right = split (s);
auto left = s;
left = sort (left, cmp);
right = sort (right, cmp);
return merge (left, right, cmp);
}
}
}
|