aboutsummaryrefslogtreecommitdiff
path: root/src/old/linkedlist.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2007-07-03 00:28:59 +0000
committerMike Buland <eichlan@xagasoft.com>2007-07-03 00:28:59 +0000
commitac517a2b7625e0aa0862679e961c6349f859ea3b (patch)
treee3e27a6b9bd5e2be6150088495c91fc91786ad9d /src/old/linkedlist.h
parentf8d4301e9fa4f3709258505941e37fab2eadadc6 (diff)
parentbd865cee5f89116c1f054cd0e5c275e97c2d0a9b (diff)
downloadlibbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.tar.gz
libbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.tar.bz2
libbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.tar.xz
libbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.zip
The reorg is being put in trunk, I think it's ready. Now we just get to find
out how many applications won't work anymore :)
Diffstat (limited to 'src/old/linkedlist.h')
-rw-r--r--src/old/linkedlist.h87
1 files changed, 87 insertions, 0 deletions
diff --git a/src/old/linkedlist.h b/src/old/linkedlist.h
new file mode 100644
index 0000000..e430108
--- /dev/null
+++ b/src/old/linkedlist.h
@@ -0,0 +1,87 @@
1/**@file
2 * Describes the LinkedList implementation of the List ADT.
3 *@author Mike Buland
4 */
5
6#ifndef LINKEDLIST_H
7#define LINKEDLIST_H
8
9#include <stdio.h>
10#include "list.h"
11
12/** A linked-item implementation of the List ADT. Since the data is linked
13 * sequentially this is a great choice for lists that will grow and shrink
14 * a lot, but don't require as much random access. This implementation
15 * includes optomizations that make iterating through data, and appending
16 * items to the list take O(1) time.
17 *@author Mike Buland
18 */
19class LinkedList : public List
20{
21public:
22 /**
23 * Construct a blank LinkedList.
24 */
25 LinkedList();
26
27 /**
28 * Delete all list data, but do not delete any of the contained elements.
29 */
30 virtual ~LinkedList();
31
32 void *getAt( int nIndex );
33 void append( void *pData );
34 void insertBefore( void *pData, int nPos = 0 );
35 int getSize( );
36 bool isEmpty( );
37 void deleteAt( int nIndex );
38 void empty();
39 void setSize( int nNewSize );
40 void setAt( int nIndex, void *pData );
41
42private:
43 /**
44 * A link in the linked list.
45 */
46 class Link
47 {
48 public:
49 /**
50 * Construct an empty link.
51 */
52 Link()
53 {
54 pData = NULL;
55 pNext = NULL;
56 }
57 /**
58 * Construct a link filled in with useful data.
59 *@param newData The data this link should hold.
60 *@param newNext The next link that this link should point to.
61 */
62 Link( void *newData = NULL, Link * newNext = NULL )
63 {
64 pData = newData;
65 pNext = newNext;
66 }
67 void *pData; /**< A pointer to the contained data. */
68 Link *pNext; /**< A pointer to the next link in the chain */
69 };
70
71 /**
72 * Finds a pointer to the link at index index. This is the core function
73 * called for all seek operations, and has been optimized as heavily as
74 * possible.
75 *@param index The zero-based index of the desired element.
76 *@returns A pointer to the requested Link, or NULL if it isn't found.
77 */
78 Link *getPtrTo( int index );
79 Link *pBase; /**< The first link in the list. */
80 Link *pTop; /**< The Last link in the list. */
81 Link *pLast; /**< The previously requested link. */
82 int nSize; /**< The number of contained links. */
83 int nLast; /**< The index of the previously requested link. */
84};
85
86#endif
87