Linked Lists

If you’ve ever had to visit a hospital emergency room, you’ll know that waiting in a
queue is one of the defining features of the experience unless you were either very lucky
or very unlucky. If you were lucky, the queue will have been empty and you will not
have had to wait. Alternatively, if you were unlucky, your condition may have been
sufficiently perilous that you got to jump to the head of the queue.
In medical emergencies, a triage system will be in place to work out where each arriving
patient should go in the queue. A similar pattern crops up in other scenarios—frequent
fliers with gold cards may be allocated standby seats at the last minute even though
others have been waiting for hours; celebrities might be able to walk right into a res-
taurant for which the rest of us have to book a table weeks in advance.
The LinkList class is able to model these sorts of scenarios. At its simplest, you
could use it like a Queue—call AddLast to add an item to the back of the queue (as
Enqueue would), and RemoveFirst to take the item off the head of the queue (like
Dequeue would). But you can also add an item to the front of the queue with
AddFirst. Or you can add items anywhere you like in the queue with the AddBefore and
AddAfter methods. Example 9-13 uses this to place new patients into the queue.

Example 9-13. Triage in action

private LinkedList waitingPatients = new LinkedList();
...
LinkedListNode current = waitingPatients.First;
312 | Chapter 9: Collection Classeswhile (current != null)
{
if (current.Value.AtImminentRiskOfDeath)
{
current = current.Next;
}
else
{
break;
}
}
if (current == null)
{
waitingPatients.AddLast(newPatient);
}
else
{
waitingPatients.AddBefore(current, newPatient);
}

This code adds the new patient after all those patients in the queue whose lives appear
to be at immediate risk, but ahead of all other patients—the patient is presumably either
quite unwell or a generous hospital benefactor. (Real triage is a little more complex, of
course, but you still insert items into the list in the same way, no matter how you go
about choosing the insertion point.)
Note the use of LinkedListNode—this is how LinkedList presents the queue’s
contents. It allows us not only to see the item in the queue, but also to navigate back
and forth through the queue with the Next and Previous properties.

Dictionaries and LINQ

Because all IDictionary implementations are also enumerable, we can
run LINQ queries against them. Given the RecordCache class in Example 9-5, we might
choose to implement the cache item removal policy as shown in Example 9-10.
Example 9-10. LINQ query with dictionary source

private void DiscardAnyOldCacheEntries()
{
// Calling ToList() on source in order to query a copy
// of the enumeration, to avoid exceptions due to calling
// Remove in the foreach loop that follows.
var staleKeys = from entry in cachedRecords.ToList()
where IsStale(entry.Value)
select entry.Key;
foreach (int staleKey in staleKeys)
{
cachedRecords.Remove(staleKey);
}
}

But it’s also possible to create new dictionaries with LINQ queries. Example 9-11 il-
lustrates how to use the standard ToDictionary LINQ operator.
Example 9-11. LINQ’s ToDictionary operator

IDictionary buildingIdToNameMap =
MyDataSource.Buildings.ToDictionary(
building => building.ID,
building => building.Name);

This example presumes that MyDataSource is some data source class that provides a
queryable collection containing a list of buildings. Since this information would typi-
cally be stored in a database, you would probably use a database LINQ provider such
as LINQ to Entities or LINQ to SQL. The nature of the source doesn’t greatly matter,
though—the mechanism for extracting the resources into a dictionary object are the
same in any case. The ToDictionary operator needs to be told how to extract the key
from each item in the sequence. Here we’ve provided a lambda expression that retrieves
the ID property—again, this property would probably be generated by a database map-
ping tool such as the ones provided by the Entity Framework or LINQ to SQL. (We
will be looking at data access technologies in a later chapter.) This example supplies a
second lambda, which chooses the value—here we pick the Name property. This second
lambda is optional—if you don’t provide it, ToDictionary will just use the entire source
item from the stream as the value—so in this example, leaving out the second lambda
would cause ToDictionary to return an IDictionary (where Building is
whatever type of object MyDataSource.Buildings provides).
The code in Example 9-11 produces the same result as this:

var buildingIdToNameMap = new Dictionary();
foreach (var building in MyDataSource.Buildings)
{
buildingIdToNameMap.Add(building.ID, building.Name);
}

HashQueue

HashQueue

 public class HashQueue
    {
        Hashtable ht = new Hashtable();
        public void AddHashIndex(string index)
        {
            Queue q = new Queue();
            ht.Add(index, q);
        }
        public void AddHashQ(object o, string index)
        {
            ((Queue)ht[index]).Enqueue(o);
        }
        public object GetHashQ(string index)
        {
            return ((Queue)ht[index]).Dequeue();
        }
        public ICollection GetKeys()
        {
            return ht.Keys;
        }
        public int AllCount
        {
            get
            {
                int c = 0;
                foreach (Queue q in ht.Values) { c += q.Count; }
                return c;
            }
        }
    }

SequenceArray

using System;
using System.Collections.Generic;
using System.Collections.Specialized;

public class SequenceArray : System.Collections.ArrayList
    {
        int _index = 0;
        public int index
        {
            get
            {
                int _r = _index % Count;
                _index++;
                return _r;
            }
            set
            {
                _index = value;
            }
        }
        public object GetS()
        {
            return this[index];
        }
        public void Add(string value1, string value2)
        {
            NameValueCollection nv = new NameValueCollection();
            nv.Add(value1, value2);
            Add(nv);
        }
       
    }