/* * /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:grant@liverpool.ac.uk">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:grant@liverpool.ac.uk">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;        }    }}