Core/Castle.Core/Internal/LinkedList.cs

   1 // Copyright 2004-2008 Castle Project - http://www.castleproject.org/
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 namespace Castle.Core.Internal
  16 {
  17         using System;
  18         using System.Collections;
  19
  20         [Serializable]
  21         public class LinkedList : IList
  22         {
  23                 private LinkNode internalhead;
  24                 private LinkNode internaltail;
  25                 private int internalcount;
  26
  27                 public LinkedList()
  28                 {
  29                 }
  30
  31                 public object Head
  32                 {
  33                         get
  34                         {
  35                                 if (internalhead == null) return null;
  36                                 return internalhead.Value;
  37                         }
  38                 }
  39
  40                 public virtual void AddFirst(object value)
  41                 {
  42                         if (internalhead == null)
  43                         {
  44                                 internalhead = new LinkNode(value);
  45                         }
  46                         else
  47                         {
  48                                 internalhead = new LinkNode(value, internalhead, null);
  49                         }
  50
  51                         internalcount++;
  52                 }
  53
  54                 public virtual int AddLast(object value)
  55                 {
  56                         if (internalhead == null)
  57                         {
  58                                 internalhead = new LinkNode(value);
  59                         }
  60                         else
  61                         {
  62                                 LinkNode p, q;
  63                                 for(p = internalhead; (q = p.Next) != null; p = q) ;
  64                                 p.Next = new LinkNode(value, null, p);
  65                         }
  66
  67                         return internalcount++;
  68                 }
  69
  70                 public virtual int Add(object value)
  71                 {
  72                         if (internalhead == null)
  73                         {
  74                                 internalhead = new LinkNode(value);
  75
  76                                 internaltail = internalhead;
  77                         }
  78                         else
  79                         {
  80                                 // Added this code because internaltail seems to be null in come cases
  81                                 if (internaltail == null)
  82                                 {
  83                                         internaltail = internalhead;
  84
  85                                         while(internaltail.Next != null)
  86                                                 internaltail = internaltail.Next;
  87                                 }
  88
  89                                 internaltail.Next = new LinkNode(value, null, internaltail);
  90
  91                                 internaltail = internaltail.Next;
  92                         }
  93
  94                         return internalcount++;
  95                 }
  96
  97                 public bool Contains(object value)
  98                 {
  99                         if (value == null) throw new ArgumentNullException("value");
 100
 101                         foreach(object item in this)
 102                         {
 103                                 if (value.Equals(item))
 104                                 {
 105                                         return true;
 106                                 }
 107                         }
 108
 109                         return false;
 110                 }
 111
 112                 public void Clear()
 113                 {
 114                         internalhead = internaltail = null;
 115                         internalcount = 0;
 116                 }
 117
 118                 public virtual bool Replace(object old, object value)
 119                 {
 120                         LinkNode node = internalhead;
 121
 122                         while(node != null)
 123                         {
 124                                 if (node.Value.Equals(old))
 125                                 {
 126                                         node.Value = value;
 127                                         return true;
 128                                 }
 129
 130                                 node = node.Next;
 131                         }
 132
 133                         return false;
 134                 }
 135
 136                 public int IndexOf(object value)
 137                 {
 138                         if (value == null) throw new ArgumentNullException("value");
 139
 140                         int index = -1;
 141
 142                         foreach(object item in this)
 143                         {
 144                                 index++;
 145
 146                                 if (value.Equals(item))
 147                                 {
 148                                         return index;
 149                                 }
 150                         }
 151
 152                         return -1;
 153                 }
 154
 155                 public virtual void Insert(int index, object value)
 156                 {
 157                         if (index == 0)
 158                         {
 159                                 AddFirst(value);
 160                         }
 161                         else if (index == internalcount)
 162                         {
 163                                 AddLast(value);
 164                         }
 165                         else
 166                         {
 167                                 LinkNode insert = GetNode(index);
 168                                 LinkNode node = new LinkNode(value, insert, insert.Previous);
 169                                 insert.Previous.Next = node;
 170                                 insert.Previous = node;
 171                                 internalcount++;
 172                         }
 173                 }
 174
 175                 /// <summary>
 176                 /// Returns the node at the specified index.
 177                 /// </summary>
 178                 /// <param name="index">The lookup index.</param>
 179                 /// <returns>The node at the specified index.</returns>
 180                 /// <exception cref="System.ArgumentOutOfRangeException">
 181                 /// If the specified <paramref name="index"/> is greater than the
 182                 /// number of objects within the list.
 183                 /// </exception>
 184                 private LinkNode GetNode(int index)
 185                 {
 186                         ValidateIndex(index);
 187                         LinkNode node = internalhead;
 188                         for(int i = 0; i < index; i++)
 189                         {
 190                                 node = node.Next;
 191                         }
 192                         return node;
 193                 }
 194
 195                 /// <summary>
 196                 /// Validates the specified index.
 197                 /// </summary>
 198                 /// <param name="index">The lookup index.</param>
 199                 /// <exception cref="System.ArgumentOutOfRangeException">
 200                 /// If the index is invalid.
 201                 /// </exception>
 202                 private void ValidateIndex(int index)
 203                 {
 204                         if (index < 0 || index >= internalcount)
 205                         {
 206                                 throw new ArgumentOutOfRangeException("index");
 207                         }
 208                 }
 209
 210                 public virtual void Remove(object value)
 211                 {
 212                         if (internalhead != null)
 213                         {
 214                                 if (internalhead.Value.Equals(value))
 215                                 {
 216                                         if (internalhead == internaltail) internaltail = null;
 217
 218                                         internalhead = internalhead.Next;
 219
 220                                         internalcount--;
 221                                 }
 222                                 else if (internaltail.Value.Equals(value))
 223                                 {
 224                                         internaltail.Previous.Next = null;
 225                                         internaltail = internaltail.Previous;
 226
 227                                         internalcount--;
 228                                 }
 229                                 else
 230                                 {
 231                                         LinkNode node = internalhead.Next;
 232
 233                                         while(node != null)
 234                                         {
 235                                                 if (node.Value.Equals(value))
 236                                                 {
 237                                                         node.Previous.Next = node.Next;
 238                                                         node.Next.Previous = node.Previous;
 239                                                         internalcount--;
 240                                                         break;
 241                                                 }
 242
 243                                                 node = node.Next;
 244                                         }
 245                                 }
 246                         }
 247                 }
 248
 249                 public virtual void RemoveAt(int index)
 250                 {
 251                         throw new NotImplementedException();
 252                 }
 253
 254                 public bool IsReadOnly
 255                 {
 256                         get { return false; }
 257                 }
 258
 259                 public bool IsFixedSize
 260                 {
 261                         get { return false; }
 262                 }
 263
 264                 public object this[int index]
 265                 {
 266                         get { throw new NotImplementedException(); }
 267                         set { throw new NotImplementedException(); }
 268                 }
 269
 270                 public int Count
 271                 {
 272                         get { return internalcount; }
 273                 }
 274
 275                 public Array ToArray(Type type)
 276                 {
 277                         Array array = Array.CreateInstance(type, Count);
 278
 279                         int index = 0;
 280
 281                         foreach(Object value in this)
 282                         {
 283                                 array.SetValue(value, index++);
 284                         }
 285
 286                         return array;
 287                 }
 288
 289                 #region IEnumerable Members
 290
 291                 public IEnumerator GetEnumerator()
 292                 {
 293                         return new LinkedListEnumerator(internalhead);
 294                 }
 295
 296                 #endregion
 297
 298                 public void CopyTo(Array array, int index)
 299                 {
 300                         throw new NotImplementedException();
 301                 }
 302
 303                 public object SyncRoot
 304                 {
 305                         get { return this; }
 306                 }
 307
 308                 public bool IsSynchronized
 309                 {
 310                         get { return false; }
 311                 }
 312         }
 313
 314         [Serializable]
 315         internal class LinkNode
 316         {
 317                 private object _value;
 318                 private LinkNode _next;
 319                 private LinkNode _prev;
 320
 321                 public LinkNode(object value) : this(value, null, null)
 322                 {
 323                 }
 324
 325                 public LinkNode(object value, LinkNode next, LinkNode prev)
 326                 {
 327                         _value = value;
 328                         _next = next;
 329                         _prev = prev;
 330                 }
 331
 332                 public LinkNode Next
 333                 {
 334                         get { return _next; }
 335                         set { _next = value; }
 336                 }
 337
 338                 public LinkNode Previous
 339                 {
 340                         get { return _prev; }
 341                         set { _prev = value; }
 342                 }
 343
 344                 public object Value
 345                 {
 346                         get { return _value; }
 347                         set { _value = value; }
 348                 }
 349         }
 350
 351         internal class LinkedListEnumerator : IEnumerator
 352         {
 353                 private LinkNode internalhead;
 354                 private LinkNode _current;
 355                 private bool _isFirst;
 356
 357                 public LinkedListEnumerator(LinkNode node)
 358                 {
 359                         internalhead = node;
 360                         Reset();
 361                 }
 362
 363                 public void Reset()
 364                 {
 365                         _current = internalhead;
 366                         _isFirst = true;
 367                 }
 368
 369                 public object Current
 370                 {
 371                         get { return _current.Value; }
 372                 }
 373
 374                 public bool MoveNext()
 375                 {
 376                         if (_current == null) return false;
 377
 378                         if (!_isFirst)
 379                         {
 380                                 _current = _current.Next;
 381                         }
 382                         else
 383                         {
 384                                 _isFirst = false;
 385                         }
 386
 387                         return _current != null;
 388                 }
 389         }
 390 }