ADT:LinkedList

Import List

    ADT:Storable
    IO
    Object
    Object
    RT0
 
Class List
EntryDesc
LinkedListDescLinked-list implementation of a list.
Class Summary: EntryDesc [Detail]
  +---RT0.Object
       |
       +---Object.Object
            |
            +--ADT:LinkedList.EntryDesc
Inherited Methods

From RT0.Object:

          Finalize

From Object.Object:

          Equals, HashCode, ToString

 
Class Summary: LinkedListDesc [Detail]
  +---RT0.Object
       |
       +---Object.Object
            |
            +---ADT:Storable.Object
                 |
                 +--ADT:LinkedList.LinkedListDesc

Linked-list implementation of a list. Objects may be efficiently added to or removed from the start or end of the list, making it useful for implementing queues.

Field Summary
size-: LONGINT

          Number of elements in the list.
Inherited Methods

From RT0.Object:

          Finalize

From Object.Object:

          Equals, HashCode, ToString

From ADT:Storable.Object:

          Load, Store

 
Type Summary
[Entry] = POINTER TO EntryDescE

          
Iterator = POINTER TO IteratorDescE

          
[IteratorDesc] = RECORD ... END

          
LinkedList = POINTER TO LinkedListDescE

          
Procedure Summary
[AddBefore](E, EntryE)

          
Append(E)

          Appends the specified element obj to the end of this list.
Clear()

          Removes all of the elements from this list.
Contains(E): BOOLEAN

          Returns TRUE if this list contains the specified element.
Copy(): LinkedListE

          Returns a shallow copy of l.
Destroy()

          
Equals(Object): BOOLEAN

          Test if an object is equal to this list.
[FindEntry](LONGINT): EntryE

          
Get(LONGINT): E

          Returns the element at the specified position index in this list.
GetFirst(): E

          Returns the first element in this list
GetIterator(IteratorE): IteratorE

          Return an iterator positioned at the start of this list.
GetLast(): E

          Returns the last element in this list
HasNext(): BOOLEAN

          
HashCode(): LONGINT

          Returns a hash code value for the object.
INIT()

          Initializes an emtpy list
IndexOf(E): LONGINT

          Searches for the first occurence of the given argument, testing for equality using the Object.Object.Equals method.
Insert(LONGINT, E)

          Inserts the specified element obj at the specified position index in this list.
Insert(E)

          
IsEmpty(): BOOLEAN

          Tests if this list has no elements.
LastIndexOf(E): LONGINT

          Searches for the last occurence of the given argument, testing for equality using the Object.Object.Equals method.
Load(Reader)

          Loads data of l from r.
New(): LinkedList

          Creates a new list
[NewEntry](E, EntryE, EntryE): EntryE

          
Next(): E

          
NextIndex(): LONGINT

          
Prepend(E)

          Appends the specified element obj to the beginning of this list.
Remove(LONGINT): E

          Removes the element at the specified position index in this list.
Remove()

          
[RemoveEntry](EntryE)

          
RemoveFirst(): E

          Removes the first element in this list.
RemoveLast(): E

          Removes the last element in this list.
RemoveRange(LONGINT, LONGINT)

          Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.
Set(LONGINT, E)

          Replaces the element at the specified position index in this list with the specified element obj.
Set(E)

          
Size(): LONGINT

          Returns the number of elements in this list.
Store(Writer)

          Stores data of l to w.

Class Detail: EntryDesc
 
Class Detail: LinkedListDesc
Field Detail

size

FIELD size-: LONGINT

Number of elements in the list.

 
Type Detail

Entry

TYPE [Entry] = POINTER TO EntryDescE

Iterator

TYPE Iterator = POINTER TO IteratorDescE

IteratorDesc

TYPE [IteratorDesc] = RECORD
                    END

LinkedList

TYPE LinkedList = POINTER TO LinkedListDescE
Procedure Detail

AddBefore

PROCEDURE (l: LinkedList) [AddBefore](element: E; 
                    e: EntryE)

Append

PROCEDURE (l: LinkedList) Append(obj: E)

Appends the specified element obj to the end of this list.


Clear

PROCEDURE (l: LinkedList) Clear()

Removes all of the elements from this list. The list will be empty after this call returns.


Contains

PROCEDURE (l: LinkedList) Contains(obj: E): BOOLEAN

Returns TRUE if this list contains the specified element.


Copy

PROCEDURE (l: LinkedList) Copy(): LinkedListE

Returns a shallow copy of l. The elements themselves are not copied.


Destroy

PROCEDURE (l: LinkedList) Destroy()

Equals

PROCEDURE (l: LinkedList) Equals(obj: Object): BOOLEAN

Test if an object is equal to this list. To be equal, a list must contain the same sequence of objects. In this context, "same" means that the Equals test returns true for pairs of objects at equivalent ordinal positions in the source lists.


FindEntry

PROCEDURE (l: LinkedList) [FindEntry](index: LONGINT): EntryE

Get

PROCEDURE (l: LinkedList) Get(index: LONGINT): E

Returns the element at the specified position index in this list.

Pre-condition: `0 <= index' and `index < l.Size()'


GetFirst

PROCEDURE (l: LinkedList) GetFirst(): E

Returns the first element in this list


GetIterator

PROCEDURE (l: LinkedList) GetIterator(i: IteratorE): IteratorE

Return an iterator positioned at the start of this list. If an iterator i is supplied (ie. not NIL), it will be initialised and returned as the result. Otherwise (i is NIL), a new iterator is allocated.


GetLast

PROCEDURE (l: LinkedList) GetLast(): E

Returns the last element in this list


HasNext

PROCEDURE (i: Iterator) HasNext(): BOOLEAN

HashCode

PROCEDURE (l: LinkedList) HashCode(): LONGINT

Returns a hash code value for the object. This method is supported for the benefit of dictionaries such as those provided by ADT:Dictionary.

The general contract of Object.HashCode is:

As much as is reasonably practical, the Object.HashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required.)

[Description inherited from HashCode]


INIT

PROCEDURE (l: LinkedList) INIT()

Initializes an emtpy list


IndexOf

PROCEDURE (l: LinkedList) IndexOf(obj: E): LONGINT

Searches for the first occurence of the given argument, testing for equality using the Object.Object.Equals method. Returns -1 if the object is not found.


Insert

PROCEDURE (l: LinkedList) Insert(index: LONGINT; 
                 obj: E)

Inserts the specified element obj at the specified position index in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Pre-condition: `0 <= index' and `index <= l.Size()'


Insert

PROCEDURE (i: Iterator) Insert(obj: E)

IsEmpty

PROCEDURE (l: LinkedList) IsEmpty(): BOOLEAN

Tests if this list has no elements.


LastIndexOf

PROCEDURE (l: LinkedList) LastIndexOf(obj: E): LONGINT

Searches for the last occurence of the given argument, testing for equality using the Object.Object.Equals method. Returns -1 if the object is not found.


Load

PROCEDURE (l: LinkedList) Load(r: Reader)
  RAISES Error;

Loads data of l from r. Nested record pointers are loaded by calling the type-bound procecdure Reader.ReadObject. This procedure must be symmetric to Object.Store, or data internalization will break, causing undefined object state or program termination.

Note: When internalizing a file with alien objects, it is possible that the type-bound procedure Object.Load is invoked more than once for a single object. Except for the results of the last call, all duplicates are discarded. Because of this, all changes by this procedure to any program state that is not part of the object l are deprecated.

Pre-condition: This procedure is either activated by a super call, or from the procedure Reader.ReadObject.

[Description inherited from Load]


New

PROCEDURE New(): LinkedList

Creates a new list


NewEntry

PROCEDURE (l: LinkedList) [NewEntry](element: E; 
                   next: EntryE; 
                   previous: EntryE): EntryE

Next

PROCEDURE (i: Iterator) Next(): E

NextIndex

PROCEDURE (i: Iterator) NextIndex(): LONGINT

Prepend

PROCEDURE (l: LinkedList) Prepend(obj: E)

Appends the specified element obj to the beginning of this list.


Remove

PROCEDURE (l: LinkedList) Remove(index: LONGINT): E

Removes the element at the specified position index in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

Pre-condition: `0 <= index' and `index < l.Size()'


Remove

PROCEDURE (i: Iterator) Remove()

RemoveEntry

PROCEDURE (l: LinkedList) [RemoveEntry](e: EntryE)

RemoveFirst

PROCEDURE (l: LinkedList) RemoveFirst(): E

Removes the first element in this list. Shifts any subsequent elements to the left (subtracts one from their indices).


RemoveLast

PROCEDURE (l: LinkedList) RemoveLast(): E

Removes the last element in this list.


RemoveRange

PROCEDURE (l: LinkedList) RemoveRange(fromIndex: LONGINT; 
                      toIndex: LONGINT)

Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index). This call shortens the list by `toIndex - fromIndex' elements. (If `toIndex = fromIndex', this operation has no effect.)


Set

PROCEDURE (l: LinkedList) Set(index: LONGINT; 
              obj: E)

Replaces the element at the specified position index in this list with the specified element obj.

Pre-condition: `0 <= index' and `index < l.Size()'


Set

PROCEDURE (i: Iterator) Set(obj: E)

Size

PROCEDURE (l: LinkedList) Size(): LONGINT

Returns the number of elements in this list.


Store

PROCEDURE (l: LinkedList) Store(w: Writer)
  RAISES Error;

Stores data of l to w. Nested record pointers are stored by calling the type-bound procedure Writer.WriteObject. The procedure is not allowed to make any changes to the global state of the program, except for calling the `Write' methods of the writer w. Any redefinition of this procedure must include a super call, preferably as the first statement of the procedure body.

Pre-condition: This procedure is either activated by a super call, or from the procedure Writer.WriteObject.

[Description inherited from Store]