<?xml version="1.0"?>
<!DOCTYPE gsdoc PUBLIC "-//GNUstep//DTD gsdoc 1.0.4//EN" "http://www.gnustep.org/gsdoc-1_0_4.dtd">
<gsdoc base="GSLinkedList">
  <head>
    <title>GSLinkedList documentation</title>
    <author name="Richard Frith-Macdonald">
      <email address="rfm@gnu.org">
        rfm@gnu.org
      </email>
    </author>
    <copy>2010 Free Software Foundation, Inc.</copy>
  </head>
  <body>
    <front><contents /></front>
    <chapter>
      <heading>
        Software documentation for the GSLinkStore class
      </heading>
      <class name="GSLinkStore" super="GSLinkedList">
        <declared>GSLinkedList.h</declared>
        <desc>
          This class extends GSLinkedList by providing storage for
          unused links and re-using those links when a new link
          is needed. <br /> This avoids the overhead of
          allocating/deallocating links and
          provides an API more like a mutable array.
        </desc>
        <ivariable type="GSListLink*" name="free" validity="public">
          <desc>
            The unused links
          </desc>
        </ivariable>
        <ivariable type="Class" name="linkClass" validity="public">
          <desc>
            The class used for links
          </desc>
        </ivariable>
        <method type="GSLinkStore*" factory="yes">
          <sel>storeFor:</sel>
          <arg type="Class">theLinkClass</arg>
          <desc>
            Creates an instance of a store to be used to create
            links using the specified class (must be a subclass
            of GSListLink). If the class is <code>nil</code> then
            GSListLink is used.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>addObject:</sel>
          <arg type="id">anObject</arg>
          <desc>
            Adds an object at the tail of the list (calls
            -insertObject:after:), making it the
            last object in the list. <br /> Returns the list link
            that the object is stored in.
          </desc>
        </method>
        <method type="id">
          <sel>firstObject</sel>
          <desc>
            Returns the first (head) object in the list or
            <code>nil</code> if the list is empty.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>insertObject:</sel>
          <arg type="id">anObject</arg>
          <sel>after:</sel>
          <arg type="GSListLink*">at</arg>
          <desc>
            Inserts <var>anObject</var> immediately after the
            specified link. If <var>at</var> is
            <code>nil</code> the object is inserted
            <var>at</var> the end of the list (as tail). <br />
            Returns the list link that the object is stored in.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>insertObject:</sel>
          <arg type="id">anObject</arg>
          <sel>before:</sel>
          <arg type="GSListLink*">at</arg>
          <desc>
            Inserts <var>anObject</var> immediately before the
            specified link. If <var>at</var> is
            <code>nil</code> the object is inserted
            <var>at</var> the start of the list (as head). <br />
            Returns the list link that the object is stored in.
          </desc>
        </method>
        <method type="id">
          <sel>lastObject</sel>
          <desc>
            Returns the last (tail) object in the list or
            <code>nil</code> if the list is empty.
          </desc>
        </method>
        <method type="void">
          <sel>purge</sel>
          <desc>
            Removes any unused links from the list (to release
            the memory they occupied).
          </desc>
        </method>
        <method type="void">
          <sel>removeFirstObject</sel>
          <desc>
            Removes the first (head) object from the list (or
            does nothing if the list is empty).
          </desc>
        </method>
        <method type="void">
          <sel>removeLastObject</sel>
          <desc>
            Removes the last (tail) object from the list (or
            does nothing if the list is empty).
          </desc>
        </method>
        <method type="void">
          <sel>removeObjectAt:</sel>
          <arg type="GSListLink*">at</arg>
          <desc>
            Removes the object in the specified link.
          </desc>
        </method>
        <method type="void">
          <sel>removeObjectAtIndex:</sel>
          <arg type="NSUInteger">index</arg>
          <desc>
            Removes the object at the specified position.
          </desc>
        </method>
      </class>
    </chapter>
    <chapter>
      <heading>
        Software documentation for the GSLinkedList class
      </heading>
      <class name="GSLinkedList" super="NSObject">
        <declared>GSLinkedList.h</declared>
        <desc>
          GSLinkedList manages a list of GSListLink
          objects. <br /> The notional direction of the list
          is from head to tail. So the head is considered to be the
          first link in the list and tail is considered to be the
          last (head is before tail, tail is after head).
        </desc>
        <ivariable type="NSUInteger" name="count" validity="public">
          <desc>
            <em>Description forthcoming.</em>
          </desc>
        </ivariable>
        <ivariable type="GSListLink*" name="head" validity="public">
          <desc>
            <em>Description forthcoming.</em>
          </desc>
        </ivariable>
        <ivariable type="GSListLink*" name="tail" validity="public">
          <desc>
            <em>Description forthcoming.</em>
          </desc>
        </ivariable>
        <method type="void">
          <sel>append:</sel>
          <arg type="GSListLink*">link</arg>
          <desc>
            Appends <var>link</var> at the end of the linked
            list managed by the receiver. <br /> Retains the
            <var>link</var>.
          </desc>
        </method>
        <method type="NSUInteger">
          <sel>count</sel>
          <desc>
            Returns the number of links in the list.
          </desc>
        </method>
        <method type="void">
          <sel>empty</sel>
          <desc>
            Remove all links from the list and release them all.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>findEqual:</sel>
          <arg type="NSObject*">object</arg>
          <sel>from:</sel>
          <arg type="GSListLink*">start</arg>
          <sel>back:</sel>
          <arg type="BOOL">aFlag</arg>
          <desc>
            Searches the linked list returning the link
            containing <var>object</var> or <code>nil</code>
            if it is not found. <br /> The comparison is performed
            using the
            <ref type="method" id="-isEqual:" class="NSObject">
              [NSObject -isEqual:]
            </ref>
            method of <var>object</var>. <br /> If
            <var>start</var> is <code>nil</code> then the whole
            list is searched. <br /> This method will <em>not</em>
            find links containing <code>nil</code> items.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>findIdentical:</sel>
          <arg type="NSObject*">object</arg>
          <sel>from:</sel>
          <arg type="GSListLink*">start</arg>
          <sel>back:</sel>
          <arg type="BOOL">aFlag</arg>
          <desc>
            Searches the linked list returning the link
            containing <var>object</var> or <code>nil</code>
            if it is not found. <br /> If <var>start</var> is
            <code>nil</code> then the whole list is searched.
            <br /> A direct pointer comparison is used to
            determine equality.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>head</sel>
          <desc>
            Returns the first link in the list.
          </desc>
        </method>
        <method type="void">
          <sel>insert:</sel>
          <arg type="GSListLink*">link</arg>
          <sel>after:</sel>
          <arg type="GSListLink*">at</arg>
          <desc>
            Inserts other immediately after the receiver.
            <br /> Retains the <var>link</var>.
          </desc>
        </method>
        <method type="void">
          <sel>insert:</sel>
          <arg type="GSListLink*">link</arg>
          <sel>before:</sel>
          <arg type="GSListLink*">at</arg>
          <desc>
            Inserts other immediately before the receiver.
            <br /> Retains the <var>link</var>.
          </desc>
        </method>
        <method type="void">
          <sel>removeLink:</sel>
          <arg type="GSListLink*">link</arg>
          <desc>
            Removes the <var>link</var> from the receiver.
            <br /> releases the <var>link</var>.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>tail</sel>
          <desc>
            Returns the last link in the list.
          </desc>
        </method>
      </class>
    </chapter>
    <chapter>
      <heading>
        Software documentation for the GSListLink class
      </heading>
      <class name="GSListLink" super="NSObject">
        <declared>GSLinkedList.h</declared>
        <desc>
          GSListLink provides simple doubly linked list
          functionality to avoid the need to constantly
          re-invent it (as the OpenStep/Cocoa APIs do not
          provide this). The emphasis is on speed of operation
          so instance variables are directly accessible and inline
          functions are provided to manipulate them (without
          error cehcking), but you can/should avoid these direct
          access features unless speed is really critical.
          <br /> A list may either be 'normal'... (where the
          head/tail ends of the list have a <code>nil</code>
          pointer to the previous/next link) or 'circular' in
          which case the list is not terminated. <br /> The
          GSListLink item carries a minimal payload of a
          single item which is retained by the link. <br /> The
          GSListLink owner is an optional pointer to an
          object which 'owns' the link... a GSLinkedList
          instance may use this to check link ownership when
          manipulating links.
        </desc>
        <ivariable type="NSObject*" name="item" validity="public">
          <desc>
            <em>Description forthcoming.</em>
          </desc>
        </ivariable>
        <ivariable type="GSListLink*" name="next" validity="public">
          <desc>
            <em>Description forthcoming.</em>
          </desc>
        </ivariable>
        <ivariable type="GSLinkedList*" name="owner" validity="public">
          <desc>
            <em>Description forthcoming.</em>
          </desc>
        </ivariable>
        <ivariable type="GSListLink*" name="previous" validity="public">
          <desc>
            <em>Description forthcoming.</em>
          </desc>
        </ivariable>
        <method type="id">
          <sel>initCircular</sel>
          <desc>
            Initialise the receiver as a link for a circular
            linked list.
          </desc>
        </method>
        <method type="NSObject*">
          <sel>item</sel>
          <desc>
            Return the item in the link.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>next</sel>
          <desc>
            Return the next item in the list containing the
            receiver, or <code>nil</code> if there are no
            more items.
          </desc>
        </method>
        <method type="GSLinkedList*">
          <sel>owner</sel>
          <desc>
            Return the list which owns the receiver or
            <code>nil</code> if the receiver is not in a list.
          </desc>
        </method>
        <method type="GSListLink*">
          <sel>previous</sel>
          <desc>
            Return the previous item in the list containing the
            receiver, or <code>nil</code> if there are no
            more items.
          </desc>
        </method>
        <method type="void">
          <sel>setItem:</sel>
          <arg type="NSObject*">anItem</arg>
          <desc>
            Set an item value by retaining it and releasing any
            previous value.
          </desc>
        </method>
      </class>
    </chapter>
    <chapter>
      <heading>GSLinkedList types</heading>
      <p></p>
      <type type="unsigned int" name="NSUInteger">
        <desc>
          <em>Description forthcoming.</em>
        </desc>
      </type>
    </chapter>
    <chapter>
      <heading>GSLinkedList functions</heading>
      <p></p>
      <function type="void" name="GSLinkCircularInsertAfter">
        <arg type="GSListLink*">link</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Inserts <var>link</var> after <var>at</var> in a
          circular list. <br /> Arguments must not be
          <code>nil</code> and <var>link</var> must not be in a
          list (ie its next and previous pointers must point to
          itsself).
        </desc>
      </function>
      <function type="void" name="GSLinkCircularInsertBefore">
        <arg type="GSListLink*">link</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Inserts <var>link</var> before <var>at</var> in a
          circular list. <br /> Arguments must not be
          <code>nil</code> and <var>link</var> must not be in a
          list (ie its next and previous pointers must point to
          itsself).
        </desc>
      </function>
      <function type="void" name="GSLinkCircularRemove">
        <arg type="GSListLink*">link</arg>
        <desc>
          Removes <var>link</var> from any list it is in.
          <br /> The <var>link</var> argument must not be
          <code>nil</code>.
        </desc>
      </function>
      <function type="void" name="GSLinkInsertAfter">
        <arg type="GSListLink*">link</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Inserts <var>link</var> after <var>at</var> in a
          normal list. <br /> Arguments must not be
          <code>nil</code> and <var>link</var> must not be in a
          list (ie its next and previous pointers must both be
          <code>nil</code>).
        </desc>
      </function>
      <function type="void" name="GSLinkInsertBefore">
        <arg type="GSListLink*">link</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Inserts <var>link</var> before <var>at</var> in a
          normal list. <br /> Arguments must not be
          <code>nil</code> and <var>link</var> must not be in a
          list (ie its next and previous pointers must both be
          <code>nil</code>).
        </desc>
      </function>
      <function type="void" name="GSLinkRemove">
        <arg type="GSListLink*">link</arg>
        <desc>
          Removes <var>link</var> from the list it is in.
          <br /> The <var>link</var> argument must not be
          <code>nil</code>.
        </desc>
      </function>
      <function type="void" name="GSLinkStoreConsumeLink">
        <arg type="GSLinkStore*">list</arg>
        <arg type="GSListLink*">link</arg>
        <desc>
          <em>Description forthcoming.</em>
        </desc>
      </function>
      <function type="GSListLink*" name="GSLinkStoreInsertObjectAfter">
        <arg type="NSObject*">anObject</arg>
        <arg type="GSLinkStore*">list</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Adds the object to the <var>list</var> after the
          specified link. <br /> Calls
          <ref type="function" id="GSLinkedListInsertAfter">
            GSLinkedListInsertAfter()
          </ref>
          . <br /> Returns the <var>list</var> link that the object
          is stored in.
        </desc>
      </function>
      <function type="GSListLink*" name="GSLinkStoreInsertObjectBefore">
        <arg type="NSObject*">anObject</arg>
        <arg type="GSLinkStore*">list</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Adds the object to the <var>list</var> before the
          specified link. <br /> Calls
          <ref type="function" id="GSLinkedListInsertBefore">
            GSLinkedListInsertBefore()
          </ref>
          . <br /> Returns the <var>list</var> link that the object
          is stored in.
        </desc>
      </function>
      <function type="GSListLink*" name="GSLinkStoreProvideLink">
        <arg type="GSLinkStore*">list</arg>
        <desc>
          <em>Description forthcoming.</em>
        </desc>
      </function>
      <function type="void" name="GSLinkStoreRemoveObjectAt">
        <arg type="GSLinkStore*">list</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Removes the object held in the specified link. <br />
          If <var>at</var> is <code>nil</code> or is not owned by
          the <var>list</var>, this does nothing.
        </desc>
      </function>
      <function type="GSListLink*" name="GSLinkedListFindEqual">
        <arg type="NSObject*">object</arg>
        <arg type="GSLinkedList*">list</arg>
        <arg type="GSListLink*">from</arg>
        <arg type="BOOL">back</arg>
        <desc>
          Searches <var>from</var> <var>list</var> to the end
          looking for the first link containing
          <var>object</var> (as determined by using object's
          <ref type="method" id="-isEqual:" class="NSObject">
            [NSObject -isEqual:]
          </ref>
          method). <br /> If <var>back</var> is
          <code>YES</code>, the search is in the direction
          <var>from</var> tail to head rather than the normal
          search <var>from</var> head to tail. <br /> If
          <var>from</var> is <code>nil</code> the <var>list</var>
          is search <var>from</var> head or tail as appropriate to
          the direction in which it is searched.
        </desc>
      </function>
      <function type="GSListLink*" name="GSLinkedListFindIdentical">
        <arg type="NSObject*">object</arg>
        <arg type="GSLinkedList*">list</arg>
        <arg type="GSListLink*">from</arg>
        <arg type="BOOL">back</arg>
        <desc>
          Searches <var>from</var> <var>list</var> to the end
          looking for the first link containing
          <var>object</var> (as determined by direct pointer
          comparison). <br /> If <var>back</var> is
          <code>YES</code>, the search is in the direction
          <var>from</var> tail to head rather than the normal
          search <var>from</var> head to tail. <br /> If
          <var>from</var> is <code>nil</code> the <var>list</var>
          is search <var>from</var> head or tail as appropriate to
          the direction in which it is searched.
        </desc>
      </function>
      <function type="id" name="GSLinkedListFirstObject">
        <arg type="GSLinkedList*">list</arg>
        <desc>
          Returns the first (head) object in the
          <var>list</var>.
        </desc>
      </function>
      <function type="void" name="GSLinkedListInsertAfter">
        <arg type="GSListLink*">link</arg>
        <arg type="GSLinkedList*">list</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Inserts <var>link</var> immediately after
          <var>at</var>. <br /> If <var>at</var> is
          <code>nil</code>, inserts <var>at</var> the end of the
          <var>list</var> (<var>link</var> becomes tail). <br />
          Updates the head, tail and count variables of
          <var>list</var>. <br /> Does not retain <var>link</var>
          .
        </desc>
      </function>
      <function type="void" name="GSLinkedListInsertBefore">
        <arg type="GSListLink*">link</arg>
        <arg type="GSLinkedList*">list</arg>
        <arg type="GSListLink*">at</arg>
        <desc>
          Inserts <var>link</var> immediately before
          <var>at</var>. <br /> If <var>at</var> is
          <code>nil</code>, inserts <var>at</var> the start of
          the <var>list</var> (<var>link</var> becomes head).
          <br /> Updates the head, tail and count variables of
          <var>list</var>. <br /> Does not retain <var>link</var>
          .
        </desc>
      </function>
      <function type="id" name="GSLinkedListLastObject">
        <arg type="GSLinkedList*">list</arg>
        <desc>
          Returns the last (tail) object in the <var>list</var>
          .
        </desc>
      </function>
      <function type="void" name="GSLinkedListMoveToHead">
        <arg type="GSListLink*">link</arg>
        <arg type="GSLinkedList*">list</arg>
        <desc>
          Moves the <var>link</var> to the head of the
          <var>list</var> (makes it the first object) if it is
          not already there.
        </desc>
      </function>
      <function type="void" name="GSLinkedListMoveToTail">
        <arg type="GSListLink*">link</arg>
        <arg type="GSLinkedList*">list</arg>
        <desc>
          Moves the <var>link</var> to the tail of the
          <var>list</var> (makes it the last object) if it is not
          already there.
        </desc>
      </function>
      <function type="void" name="GSLinkedListRemove">
        <arg type="GSListLink*">link</arg>
        <arg type="GSLinkedList*">list</arg>
        <desc>
          Removes <var>link</var> from the <var>list</var>.
          <br /> Updates the head, tail and count variables of
          <var>list</var>. <br /> Does not release
          <var>link</var>.
        </desc>
      </function>
    </chapter>
  </body>
</gsdoc>
