ArrayQueue.m

   1 /************************
   2 A Cocoa DataStructuresFramework
   3 Copyright (C) 2002  Phillip Morelock in the United States
   4 http://www.phillipmorelock.com
   5 Other copyrights for this specific file as acknowledged herein.
   6
   7 This library is free software; you can redistribute it and/or
   8 modify it under the terms of the GNU Lesser General Public
   9 License as published by the Free Software Foundation; either
  10 version 2.1 of the License, or (at your option) any later version.
  11
  12 This library is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 Lesser General Public License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public
  18 License along with this library; if not, write to the Free Software
  19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20 *******************************/
  21
  22 /////SEE LICENSE FILE FOR LICENSE INFORMATION///////
  23
  24 #import "ArrayQueue.h"
  25
  26 @implementation ArrayQueue
  27
  28 - init
  29 {
  30     return [self initWithCapacity:10];
  31 }
  32
  33 -initWithCapacity:(unsigned)capacity
  34 {
  35     self = [super init];
  36
  37     theQ = [[NSMutableArray alloc] initWithCapacity:capacity];
  38
  39     backIndex = -1;
  40     frontIndex = 0;
  41     qSize = 0;
  42
  43     niller = [[NSString stringWithFormat:@"nothing"] retain];
  44
  45     return self;
  46 }
  47
  48 -(void) dealloc
  49 {
  50     [theQ release];
  51     [niller release];
  52     [super dealloc];
  53 }
  54
  55 -(BOOL) enqueue: (id)enqueuedObj
  56 {
  57     if ( enqueuedObj == nil )
  58         return NO;
  59
  60     ++backIndex;
  61     [theQ insertObject:enqueuedObj atIndex:backIndex];
  62     ++qSize;
  63     return YES;
  64 }
  65
  66 - dequeue
  67 {
  68     id theObj;
  69
  70     if ( qSize < 1 )
  71         return nil;
  72
  73     //decrement the size of the Q
  74     --qSize;
  75
  76     //get it and retain it
  77     theObj = [[theQ objectAtIndex:frontIndex] retain];
  78     [theQ replaceObjectAtIndex:frontIndex withObject:niller];
  79
  80     //now increment front -- if we have large array and we've "caught up" with
  81     //the back, then let's dealloc and start over.
  82     ++frontIndex;
  83     if (frontIndex > 25 && qSize < 0)
  84     {
  85         [self removeAllObjects];
  86     }
  87
  88     return [theObj autorelease];
  89 }
  90
  91 -(unsigned) count
  92 {
  93     return qSize;
  94 }
  95
  96 //simple BOOL for whether the queue is empty or not.
  97 -(BOOL) isEmpty
  98 {
  99     if ( qSize < 1)
 100         return YES;
 101     else
 102         return NO;
 103 }
 104
 105 -(void) removeAllObjects
 106 {
 107     if (theQ)
 108         [theQ release];
 109
 110     theQ = [[NSMutableArray alloc] initWithCapacity:10];
 111     backIndex = -1;
 112     frontIndex = 0;
 113     qSize = 0;
 114
 115 }
 116
 117 +(ArrayQueue *)queueWithArray:(NSArray *)array
 118                   ofOrder:(BOOL)direction
 119 {
 120     ArrayQueue *q;
 121     int i,s;
 122
 123     q = [[ArrayQueue alloc] init];
 124     s = [array count];
 125     i = 0;
 126
 127     if (!array || !s)
 128     {}//nada
 129     else if (direction)//so the order to dequeue will be from 0...n
 130     {
 131         while (i < s)
 132             [q enqueue: [array objectAtIndex: i++]];
 133     }
 134     else //order to dequeue will be n...0
 135     {
 136         while (s > i)
 137             [q enqueue: [array objectAtIndex: --s]];
 138     }
 139
 140     return [q autorelease];
 141 }
 142
 143
 144 @end