dotgnu-pnet-commits
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Dotgnu-pnet-commits] CVS: pnetlib/Generics SinglyLinkedList.cs,NONE,1.1


From: Rhys Weatherley <address@hidden>
Subject: [Dotgnu-pnet-commits] CVS: pnetlib/Generics SinglyLinkedList.cs,NONE,1.1 Generics.html,1.4,1.5 LinkedList.cs,1.8,1.9
Date: Sat, 01 Mar 2003 05:49:28 -0500

Update of /cvsroot/dotgnu-pnet/pnetlib/Generics
In directory subversions:/tmp/cvs-serv8780/Generics

Modified Files:
        Generics.html LinkedList.cs 
Added Files:
        SinglyLinkedList.cs 
Log Message:


Implement SinglyLinkedList; fix a bug in the iterator for LinkedList.


--- NEW FILE ---
/*
 * SinglyLinkedList.cs - Generic singly-linked list class.
 *
 * Copyright (c) 2003  Southern Storm Software, Pty Ltd
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

namespace Generics
{

using System;

public sealed class SinglyLinkedList<T>
                : IQueue<T>, IStack<T>, IList<T>, ICloneable
{
        // Structure of a list node.
        private class Node<T>
        {
                public T       data;
                public Node<T> next;

                public Node(T data)
                                {
                                        this.data = data;
                                        this.next = null;
                                }

        }; // class Node

        // Internal state.
        private Node<T> first;
        private Node<T> last;
        private int     count;

        // Constructor.
        public SinglyLinkedList()
                        {
                                first = null;
                                last = null;
                                count = 0;
                        }

        // Get a particular node in the list by index.
        private Node<T> Get(int index)
                        {
                                Node<T> current;
                                if(index < 0 || index >= count)
                                {
                                        throw new ArgumentOutOfRangeException
                                                ("index", 
S._("ArgRange_Array"));
                                }
                                current = first;
                                while(index > 0)
                                {
                                        current = current.next;
                                        --index;
                                }
                                return current;
                        }

        // Get the predecessor of a particular node in the list by index.
        private Node<T> GetPrev(int index)
                        {
                                Node<T> current;
                                Node<T> prev;
                                if(index < 0 || index >= count)
                                {
                                        throw new ArgumentOutOfRangeException
                                                ("index", 
S._("ArgRange_Array"));
                                }
                                current = first;
                                prev = null;
                                while(index > 0)
                                {
                                        prev = current;
                                        current = current.next;
                                        --index;
                                }
                                return prev;
                        }

        // Remove a node from this list.
        private void Remove(Node<T> prev, Node<T> node)
                        {
                                if(node.next == null)
                                {
                                        last = prev;
                                }
                                if(prev != null)
                                {
                                        prev.next = node.next;
                                }
                                else
                                {
                                        first = node.next;
                                }
                                --count;
                        }

        // Implement the IQueue<T> interface.
        void IQueue<T>.Clear()
                        {
                                Clear();
                        }
        bool IQueue<T>.Contains(T value)
                        {
                                return Contains(value);
                        }
        public void Enqueue(T value)
                        {
                                Add(value);
                        }
        public T Dequeue()
                        {
                                if(first != null)
                                {
                                        Node<T> node = first;
                                        if(node.next == null)
                                        {
                                                last = null;
                                        }
                                        first = node.next;
                                        --count;
                                        return node.data;
                                }
                                else
                                {
                                        throw new InvalidOperationException
                                                (S._("Invalid_EmptyList"));
                                }
                        }
        public T Peek()
                        {
                                if(first != null)
                                {
                                        return first.data;
                                }
                                else
                                {
                                        throw new InvalidOperationException
                                                (S._("Invalid_EmptyList"));
                                }
                        }
        public T[] ToArray()
                        {
                                T[] array = new T [count];
                                CopyTo(array, 0);
                                return array;
                        }

        // Implement the IStack<T> interface privately.
        void IStack<T>.Clear()
                        {
                                Clear();
                        }
        bool IStack<T>.Contains(T value)
                        {
                                return Contains(value);
                        }
        void IStack<T>.Push(T value)
                        {
                                Insert(0, value);
                        }
        T IStack<T>.Pop()
                        {
                                return Dequeue();
                        }
        T IStack<T>.Peek()
                        {
                                return Peek();
                        }
        T[] IStack<T>.ToArray()
                        {
                                return ToArray();
                        }

        // Implement the ICollection<T> interface.
        public void CopyTo(T[] array, int index)
                        {
                                IIterator<T> iterator = GetIterator();
                                while(iterator.MoveNext())
                                {
                                        array[index++] = iterator.Current;
                                }
                        }
        public int Count
                        {
                                get
                                {
                                        return count;
                                }
                        }
        public bool IsFixedSize
                        {
                                get
                                {
                                        return false;
                                }
                        }
        public bool IsReadOnly
                        {
                                get
                                {
                                        return false;
                                }
                        }
        public bool IsSynchronized
                        {
                                get
                                {
                                        return false;
                                }
                        }
        public Object SyncRoot
                        {
                                get
                                {
                                        return this;
                                }
                        }

        // Implement the IList<T> interface.
        public int Add(T value)
                        {
                                int index = count;
                                Node<T> node = new Node<T>(value);
                                if(last != null)
                                {
                                        last.next = node;
                                }
                                else
                                {
                                        first = node;
                                }
                                last = node;
                                return index;
                        }
        public void Clear()
                        {
                                first = null;
                                last = null;
                                count = 0;
                        }
        public bool Contains(T value)
                        {
                                Node<T> current = first;
                                if(typeof(T).IsValueType)
                                {
                                        while(current != null)
                                        {
                                                if(value.Equals(current.data))
                                                {
                                                        return true;
                                                }
                                                current = current.next;
                                        }
                                        return false;
                                }
                                else
                                {
                                        if(((Object)value) != null)
                                        {
                                                while(current != null)
                                                {
                                                        
if(value.Equals(current.data))
                                                        {
                                                                return true;
                                                        }
                                                        current = current.next;
                                                }
                                                return false;
                                        }
                                        else
                                        {
                                                while(current != null)
                                                {
                                                        
if(((Object)(current.data)) == null)
                                                        {
                                                                return true;
                                                        }
                                                        current = current.next;
                                                }
                                                return false;
                                        }
                                }
                        }
        public IListIterator<T> GetIterator()
                        {
                                return new ListIterator<T>(this);
                        }
        public int IndexOf(T value)
                        {
                                int index = 0;
                                Node<T> current = first;
                                if(typeof(T).IsValueType)
                                {
                                        while(current != null)
                                        {
                                                if(value.Equals(current.data))
                                                {
                                                        return index;
                                                }
                                                ++index;
                                                current = current.next;
                                        }
                                        return -1;
                                }
                                else
                                {
                                        if(((Object)value) != null)
                                        {
                                                while(current != null)
                                                {
                                                        
if(value.Equals(current.data))
                                                        {
                                                                return index;
                                                        }
                                                        ++index;
                                                        current = current.next;
                                                }
                                                return -1;
                                        }
                                        else
                                        {
                                                while(current != null)
                                                {
                                                        
if(((Object)(current.data)) == null)
                                                        {
                                                                return index;
                                                        }
                                                        ++index;
                                                        current = current.next;
                                                }
                                                return -1;
                                        }
                                }
                        }
        public void Insert(int index, T value)
                        {
                                if(index == count)
                                {
                                        Add(value);
                                }
                                else
                                {
                                        Node<T> prev = GetPrev(index);
                                        Node<T> node = new Node<T>(value);
                                        if(prev != null)
                                        {
                                                if(prev.next == null)
                                                {
                                                        last = node;
                                                }
                                                node.next = prev.next;
                                                prev.next = node;
                                        }
                                        else if(first != null)
                                        {
                                                node.next = first;
                                                first = node;
                                        }
                                        else
                                        {
                                                first = node;
                                                last = node;
                                        }
                                }
                        }
        public void Remove(T value)
                        {
                                Node<T> current = first;
                                Node<T> prev = null;
                                if(typeof(T).IsValueType)
                                {
                                        while(current != null)
                                        {
                                                if(value.Equals(current.data))
                                                {
                                                        Remove(prev, current);
                                                        return;
                                                }
                                                prev = current;
                                                current = current.next;
                                        }
                                }
                                else
                                {
                                        if(((Object)value) != null)
                                        {
                                                while(current != null)
                                                {
                                                        
if(value.Equals(current.data))
                                                        {
                                                                Remove(prev, 
current);
                                                                return;
                                                        }
                                                        prev = current;
                                                        current = current.next;
                                                }
                                        }
                                        else
                                        {
                                                while(current != null)
                                                {
                                                        
if(((Object)(current.data)) == null)
                                                        {
                                                                Remove(prev, 
current);
                                                                return;
                                                        }
                                                        prev = current;
                                                        current = current.next;
                                                }
                                        }
                                }
                        }
        public void RemoveAt(int index)
                        {
                                Node<T> prev = GetPrev(index);
                                if(prev != null)
                                {
                                        Remove(prev, prev.next);
                                }
                                else
                                {
                                        Remove(null, first);
                                }
                        }
        public bool IsRandomAccess
                        {
                                get
                                {
                                        return false;
                                }
                        }
        public T this[int index]
                        {
                                get
                                {
                                        return Get(index).data;
                                }
                                set
                                {
                                        Get(index).data = value;
                                }
                        }

        // Implement the IIterable<T> interface.
        IIterator<T> IIterator<T>.GetIterator()
                        {
                                return GetIterator();
                        }

        // Implement the ICloneable interface.
        public Object Clone()
                        {
                                SinglyLinkedList<T> clone = new 
SinglyLinkedList<T>();
                                IIterator<T> e = GetIterator();
                                while(e.MoveNext())
                                {
                                        clone.Add(e.Current);
                                }
                                return clone;
                        }

        // Iterator class for lists.
        private class ListIterator<T> : IListIterator<T>
        {
                // Internal state, accessible to "LinkedList<T>".
                public LinkedList<T> list;
                public Node<T> posn;
                public Node<T> prev;
                public int     index;
                public bool    reset;
                public bool    removed;

                // Constructor.
                public ListIterator(LinkedList<T> list)
                                {
                                        this.list = list;
                                        this.posn = null;
                                        this.prev = null;
                                        this.index = -1;
                                        this.reset = true;
                                        this.removed = false;
                                }

                // Implement the IIterator<T> interface.
                public bool MoveNext()
                                {
                                        if(reset)
                                        {
                                                posn = list.first;
                                                prev = null;
                                                index = 0;
                                                reset = false;
                                        }
                                        else if(removed)
                                        {
                                                if(prev != null)
                                                {
                                                        posn = prev.next;
                                                }
                                                else
                                                {
                                                        posn = list.first;
                                                }
                                        }
                                        else if(posn != null)
                                        {
                                                prev = posn;
                                                posn = posn.next;
                                                ++index;
                                        }
                                        removed = false;
                                        return (posn != null);
                                }
                public void Reset()
                                {
                                        posn = null;
                                        prev = null;
                                        index = -1;
                                        reset = true;
                                        removed = false;
                                }
                public void Remove()
                                {
                                        if(posn == null || removed)
                                        {
                                                throw new 
InvalidOperationException
                                                        
(S._("Invalid_BadIteratorPosition"));
                                        }
                                        list.Remove(prev, posn);
                                        removed = true;
                                }
                T IIterator<T>.Current
                                {
                                        get
                                        {
                                                if(posn == null || removed)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_BadIteratorPosition"));
                                                }
                                                return posn.data;
                                        }
                                }

                // Implement the IListIterator<T> interface.
                public bool MovePrev()
                                {
                                        if(reset)
                                        {
                                                posn = list.last;
                                                index = list.count - 1;
                                                if(index >= 0)
                                                {
                                                        prev = 
list.GetPrev(index);
                                                }
                                                else
                                                {
                                                        prev = null;
                                                }
                                                reset = false;
                                        }
                                        else if(posn != null)
                                        {
                                                posn = prev;
                                                --index;
                                                if(index >= 0)
                                                {
                                                        prev = 
list.GetPrev(index);
                                                }
                                                else
                                                {
                                                        prev = null;
                                                }
                                        }
                                        removed = false;
                                        return (posn != null);
                                }
                public int Position
                                {
                                        get
                                        {
                                                if(posn == null || removed)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_BadIteratorPosition"));
                                                }
                                                return index;
                                        }
                                }
                public T Current
                                {
                                        get
                                        {
                                                if(posn == null || removed)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_BadIteratorPosition"));
                                                }
                                                return posn.data;
                                        }
                                        set
                                        {
                                                if(posn == null || removed)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_BadIteratorPosition"));
                                                }
                                                posn.data = value;
                                        }
                                }

        }; // class ListIterator<T>

}; // class SinglyLinkedList<T>

}; // namespace Generics

Index: Generics.html
===================================================================
RCS file: /cvsroot/dotgnu-pnet/pnetlib/Generics/Generics.html,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -r1.4 -r1.5
*** Generics.html       1 Mar 2003 07:58:33 -0000       1.4
--- Generics.html       1 Mar 2003 10:49:19 -0000       1.5
***************
*** 220,223 ****
--- 220,228 ----
                a <code>LinkedList&lt;T&gt;</code> object is used.</dd>
  
+ <dt><code>SinglyLinkedList&lt;T&gt;</code></dt>
+       <dd>Implementation of an <code>IList&lt;T&gt;</code>, organised
+               as a singly-linked list.  This class also implements
+               <code>IQueue&lt;T&gt;</code> and 
<code>IStack&lt;T&gt;</code>.</dd>
+ 
  <dt><code>TreeSet&lt;T&gt;</code></dt>
        <dd>Implementation of an <code>ISet&lt;T&gt;</code> as a

Index: LinkedList.cs
===================================================================
RCS file: /cvsroot/dotgnu-pnet/pnetlib/Generics/LinkedList.cs,v
retrieving revision 1.8
retrieving revision 1.9
diff -C2 -r1.8 -r1.9
*** LinkedList.cs       25 Feb 2003 01:43:47 -0000      1.8
--- LinkedList.cs       1 Mar 2003 10:49:19 -0000       1.9
***************
*** 622,625 ****
--- 622,626 ----
                                                --index;
                                        }
+                                       removed = false;
                                        return (posn != null);
                                }





reply via email to

[Prev in Thread] Current Thread [Next in Thread]