aboutsummaryrefslogtreecommitdiff
path: root/src/linkedlist.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/linkedlist.cpp')
-rw-r--r--src/linkedlist.cpp227
1 files changed, 227 insertions, 0 deletions
diff --git a/src/linkedlist.cpp b/src/linkedlist.cpp
new file mode 100644
index 0000000..78a615a
--- /dev/null
+++ b/src/linkedlist.cpp
@@ -0,0 +1,227 @@
1/***************************************************************************
2 linkedlist.cpp - description
3 -------------------
4 begin : Sun Oct 19 2003
5 copyright : (C) 2003 by Mike Buland
6 email : eichlan@yf-soft.com
7 ***************************************************************************/
8
9/***************************************************************************
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 ***************************************************************************/
17
18#include "linkedlist.h"
19
20LinkedList::LinkedList( )
21{
22 pBase = NULL;
23 pTop = NULL;
24 pLast = NULL;
25 nSize = 0;
26 nLast = -1;
27}
28
29LinkedList::~LinkedList( )
30{
31/*
32 Link *pCur = pBase;
33 while( pCur )
34 {
35 Link *pLast = pCur;
36 pCur = pCur->pNext;
37 delete pLast;
38 }
39*/
40 empty();
41}
42
43void *LinkedList::getAt( int index )
44{
45 if( index < 0 || index >= nSize )
46 return NULL;
47
48 return getPtrTo( index )->pData;
49}
50
51void LinkedList::append( void *data )
52{
53 if( pBase == NULL )
54 {
55 pBase = new Link( data );
56 pTop = pBase;
57 nSize++;
58 }
59 else
60 {
61 pTop->pNext = new Link( data );
62 pTop = pTop->pNext;
63 nSize++;
64 }
65}
66
67void LinkedList::insertBefore( void *data, int pos )
68{
69 if( pos < 0 || pos > nSize )
70 return;
71
72 if( pos == 0 )
73 {
74 Link *pTmp = new Link( data, pBase );
75 if( pBase == NULL )
76 {
77 pTop = pTmp;
78 }
79 pBase = pTmp;
80 if( nLast >= 0 ) nLast++;
81 nSize++;
82 }
83 else
84 {
85 Link *pCur;
86 if( (pCur = getPtrTo( pos-1 )) == NULL )
87 {
88 return;
89 }
90 Link *pNew = new Link( data, pCur->pNext );
91 pCur->pNext = pNew;
92 if( pNew->pNext == NULL )
93 {
94 pTop = pNew;
95 }
96 if( nLast >= pos ) nLast++;
97 nSize++;
98 }
99}
100
101int LinkedList::getSize( )
102{
103 return nSize;
104}
105
106bool LinkedList::isEmpty( )
107{
108 if( nSize == 0 )
109 return true;
110 return false;
111}
112
113void LinkedList::deleteAt( int index )
114{
115 if( index >= nSize ||
116 pBase == NULL )
117 return;
118
119 if( index == 0 )
120 {
121 Link *pTmp = pBase->pNext;
122 delete pBase;
123 pBase = pTmp;
124 if( nLast >= 0 ) nLast--;
125 nSize--;
126 if( pBase == NULL )
127 {
128 pTop = NULL;
129 }
130 else if( pBase->pNext == NULL )
131 {
132 pTop = pBase;
133 }
134 }
135 else
136 {
137 Link *pCur = getPtrTo( index-1 );
138 if( pCur->pNext == pTop )
139 {
140 pTop = pCur;
141 }
142 Link *pTmp;
143 if( pCur->pNext == NULL )
144 {
145 pTmp = NULL;
146 }
147 else
148 {
149 pTmp = pCur->pNext->pNext;
150 }
151 delete pCur->pNext;
152 pCur->pNext = pTmp;
153 if( nLast == index ) nLast = -1;
154 else if( index < nLast ) nLast--;
155 nSize--;
156 }
157}
158
159void LinkedList::empty()
160{
161 while( nSize > 0 )
162 {
163 deleteAt( 0 );
164 }
165}
166
167void LinkedList::setSize( int newSize )
168{
169 if( newSize < nSize )
170 {
171 // Delete items off of the end of the list.
172 while( nSize > newSize )
173 {
174 deleteAt( nSize-1 );
175 }
176 }
177 else
178 {
179 // Add null items to the end of the list.
180 while( nSize < newSize )
181 {
182 append( NULL );
183 }
184 }
185}
186
187void LinkedList::setAt( int index, void *data )
188{
189 if( index >= nSize || index < 0 )
190 return;
191
192 getPtrTo( index )->pData = data;
193}
194
195LinkedList::Link *LinkedList::getPtrTo( int index )
196{
197 if( index < 0 || index >= nSize )
198 return NULL;
199 if( index == nLast )
200 {
201 return pLast;
202 }
203 if( index == 0 )
204 {
205 pLast = pBase;
206 nLast = 0;
207 return pBase;
208 }
209 else
210 {
211 Link *pCur = pBase;
212 int nCur = 0;
213 if( nLast < index && nLast >= 0 )
214 {
215 pCur = pLast;
216 nCur = nLast;
217 }
218 while( nCur != index )
219 {
220 pCur = pCur->pNext;
221 nCur++;
222 }
223 nLast = index;
224 pLast = pCur;
225 return pCur;
226 }
227}