sortedtopiclist.java

一乐LIST 能够返回你的Topic值

/*
 * /home/grant/Teaching/COMP213/New/Slides/Code/SortedTopicList.java
 *
 * Created: Tue Oct  7 15:09:21 2008
 *
 * copyright Grant Malcolm
 *
 *   This source code may be freely used, modified, or distributed
 *   provided due credit is given.
 *
 * Version 1.1 fixes a bug in remove(int).
 */

// package Comp213.MessageBoard.V1;


/**
 * List of topics for a simple Message Board server.
 * This class represents a list of {@link Topic Topics} that might
 * be stored by a Message Board server.  Topics are stored in the order
 * of their most-recent update; the most-recently updated topics being
 * at the start of the list.  Topics are {@link #addNewTopic(Message) created}
 * by providing a {@link Message Message} to initiate the topic;
 * the topic is given a unique identifier (the length of the list),
 * and stored at the start of the list.
 * Topics may be updated by {@link #addMsgToTopic(Message,int) adding}
 * a message to a given topic
 * (specified by its {@link Topic#getID() identifier});
 * the updated topic is moved to the start of the list.
 *
 *
 * @author <a href="mailto:[e-mail]">Grant Malcolm</a>
 * @version 1.1
 */
public class SortedTopicList 
{

    /**
     * The number of topics in the list.
     *
     */
    private int length = 0;

    /**
     * A linked list of {@link Topic Topics}.
     *
     */
    private TopicList topics = null;

    /**
     * Creates a new <code>SortedTopicList</code> instance.
     * The new instance has an empty list of topics.
     *
     */
    public SortedTopicList()
    {
        // do nothing; topics is null, which is the empty list
    }

    /**
     * The length of the list; i.e., the number of {@link Topic topics}
     * in the list.
     *
     * @return the number of topics in the list
     */
    public int getLength()
    {
        return length;
    }

    /**
     * Add a new Topic to the list.  The {@link Topic Topic} contains
     * the given {@link Message message}, and is assigned a unique identifier
     * (the {@link #getLength() length} of the list).  The new topic is
     * placed at thestart of the list.
     *
     * @param m the first message in the topic
     */
    public void addNewTopic(Message m)
    {
        // the new topic to add to the start of the list
        Topic t = new Topic(length, m);

        if (length == 0)
        {  // list was empty; start a new list:
           topics = new TopicList(t);
        }
        else
        {  // add to start of list
           topics = new TopicList(t,topics);
        }
        // list is one topic longer
        length++;
    }

    /**
     * Add a message to a topic.  The given {@link Message message} will be
     * added to the {@link Topic topic} with the given ID;
     * this topic will be moved to the start of the list,
     * as it is the most-recently updated.
     * If there is no topic in the list with the given ID,
     * this method has no effect.
     *
     * @param m the message to be added
     * @param i the id of the topic to add the message to
     */
    public void addMsgToTopic(Message m, int i)
    {
        /*
         * We could do this with
         *
         *   Topic t = getTopic(i);
         *   removeTopic(i);
         *   t.addMessage(m);
         *   add(t);
         *
         * But getTopic() and removeTopic() both loop through the list
         * in a similar way; the following code combines these loops into
         * one loop that has the same effect as the code above,
         * but is more efficient.
         *
         */

        // if list is empty, do nothing
        if (topics == null)
        {
           return;
        }
        /*
         *  else:
         *  if the first element has the requested id, add the message
         */
        if (topics.head().getID() == i)
        {
           topics.head().addMsg(m);
           return;
        }
        /*
         *  else:
         *  (the list is not empty and the first topic is not the one we want):
         *  traverse through the list to find the topic with ID i
         */
        TopicList tl = topics.next();  // the next topic to look at
        TopicList tlPrev = topics;  // the previous node; when we find the
                                   // node to remove, we'll set the next
                                  // field of this node to the node
                                 // after tl
        Topic ti;  // will hold the topic of the current node
        while (tl != null) // stop at end of list
        {
           ti = tl.head();  // the topic at the current node
           if (ti.getID() == i)
           {
              /*
               * found topic with ID i:
               * add the message and move to start of list
               *
               */
              ti.addMsg(m);
              /*
               * remove tl from list:
               */
              // tlPrev should point to node after tl (can be null):
              tlPrev.next = tl.next();
              // tl should be first;
              // it should point to what was the start of the list
              tl.next = topics;
              // start of the list should be tl
              topics = tl;
              return;  // done
           }
           // else (haven't found the topic): move on to tail of list
           tlPrev = tl;
           tl = tl.next();
        }
        // got through without finding i: do nothing
    }

    /**
     * Put a topic at the start of the list.
     *
     * @param t the topic to be placed at the start of the list
     */
    private void add(Topic t)
    {
        topics = new TopicList(t,topics);
    }

    /**
     * Get the topic with the given ID.  This method is only required
     * for paedogogic reasons; the code that implements this method is
     * incorporated in the implementation of
     * {@link #addMsgToTopic addMsgToTopic}.
     *
     * @param id the ID of the topic to find
     * @return the topic with the given ID
     */
    public Topic getTopic(int id)
    {
        // traverse through this copy of the list
        TopicList tl = topics;

        // stop when found, or at end of list
        while (tl != null)
        {
           if (tl.head().getID() == id)
           {
              return tl.head();
           }
           tl = tl.next();
        }
        return null;
    }

    /**
     * Remove the topic with the given ID.  This method is only required
     * for paedogogic reasons; the code that implements this method is
     * incorporated in the implementation of
     * {@link #addMsgToTopic addMsgToTopic}.
     *
     * @param id the ID of the topic to remove
     */
    public void removeTopic(int id)
    {
        // if list is empty, do nothing
        if (length == 0) return;

        // if the first element has the requested id, remove it
        if (topics.head().getID() == id)
        {
            /*
             * remove it by setting the pointer to the start of the list
             * to the next node
             */
             topics = topics.next();
             return;
        }
        /*
         *  else:
         *  (the list is not empty and the first topic is not the one we want):
         *  traverse through the list to find the topic with ID i
         */
        TopicList tl = topics.next();  // the next topic to look at
        TopicList tlPrev = topics;  // the previous node; when we find the
                                   // node to remove, we'll set the next
                                  // field of this node to the node
                                 // after tl
        Topic ti;  // will hold the topic of the current node
        while (tl != null) // stop at end of list
        {
           ti = tl.head();  // the topic at the current node
           if (ti.getID() == id)
           {
              /*
               * found topic with ID i: remove it
               *
               */

              // tlPrev should point to node after tl (can be null):
              tlPrev.next = tl.next();
              // tl should be first;
              // it should point to what was the start of the list
              tl.next = topics;
              // start of the list should be tl
              topics = tl;
              return;  // done
           }
           // else: (haven't found the topic) move on to tail of list
           tlPrev = tl;
           tl = tl.next();
        }
        // got through without finding i: do nothing
    }


    /**
     * A linked list of Topics.
     *
     * @author <a href="mailto:[e-mail]">Grant Malcolm</a>
     * @version 1.0
     */
    class TopicList
    {
        /**
         * The topic at the start of the list.
         *
         */
        private Topic head = null;

        /**
         * pointer to the tail of the list.
         *
         */
        private TopicList next = null;

        /**
         * Creates a new <code>TopicList</code> instance with the given Topic.
         *
         * @param n the topic to store at the current node
         */
        TopicList(Topic n)
        {
            head = n;
        }


        /**
         * Creates a new <code>TopicList</code> instance with the given head
         * and tail.
         *
         * @param n the topic to store
         * @param l the tail of the list
         */
        TopicList(Topic n, TopicList l)
        {
            head = n;
            next = l;
        }


        /**
         * Get the topic at the current node.
         *
         * @return the topic at the current node
         */
        public Topic head()
        {
            return head;
        }

        /**
         * Get the tail of the list.
         *
         * @return the next node.
         */
        public TopicList next()
        {
            return next;
        }

    }

}