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