mirror of
https://github.com/gnustep/libs-performance.git
synced 2025-02-14 15:41:22 +00:00
dd83044cad
git-svn-id: svn+ssh://svn.gna.org/svn/gnustep/libs/performance/trunk@25488 72102866-910b-0410-8b05-ffd578937521
79 lines
3 KiB
Objective-C
79 lines
3 KiB
Objective-C
/**
|
|
Copyright (C) 2006 Free Software Foundation, Inc.
|
|
|
|
Written by: Matt Rice <ratmice@yahoo.com>
|
|
Date: 2006
|
|
|
|
This file is part of the Performance Library.
|
|
|
|
This library is free software; you can redistribute it and/or
|
|
modify it under the terms of the GNU Lesser General Public
|
|
License as published by the Free Software Foundation; either
|
|
version 3 of the License, or (at your option) any later version.
|
|
|
|
This library is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Lesser General Public License for more details.
|
|
|
|
You should have received a copy of the GNU Lesser General Public
|
|
License along with this library; if not, write to the Free
|
|
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA.
|
|
*/
|
|
#import <Foundation/NSArray.h>
|
|
|
|
/**
|
|
<p>An NSMutableArray category to provide an NSMutableArray instance
|
|
which uses a skip list variant for it's underlying data structure.
|
|
</p>
|
|
<p>While a skip list is typically sorted and represents a dictionary.
|
|
the indexed skip list is sorted by index and maintains deltas to represent
|
|
the distance between linked nodes.
|
|
</p>
|
|
<p>The underlying data structure looks much like the figure below:
|
|
</p>
|
|
<example>
|
|
index -> HEAD 1 2 3 4 5 6 TAIL
|
|
5| ---------------------> # ------> #
|
|
3| -----------> 2 ------> # ------> #
|
|
1| -> 1 -> 1 -> 1 -> 1 -> 1 -> # -> #
|
|
</example>
|
|
|
|
<p>Where the numbers represent how many indexes it is to the next node
|
|
of the appropriate level. The bottom level always points to the next node.</p>
|
|
|
|
<p>Finding a specific index starts at the top level, until the current
|
|
depth + the next nodes delta is larger than wanted index, then it goes down
|
|
1 level, and repeats until it finds the wanted index.
|
|
</p>
|
|
|
|
<p>Addition and removal of indexes requires an update of the deltas of nodes
|
|
which begin before, and end after the wanted index,
|
|
these are the places where it goes down a level.
|
|
</p>
|
|
|
|
<p>The rationale behind it was where a linked list based mutable array will
|
|
quickly add and remove elements, it may perform poorly at accessing any
|
|
random index (because it must traverse the entire list to get to the index).
|
|
</p>
|
|
|
|
<p>While a C array based mutable array will perform good at random index
|
|
access it may perform poorly at adding and removing indexes
|
|
(because it must move all items after the altered index).
|
|
</p>
|
|
|
|
<p>While a GSSkipMutableArray may not outperform a linked list or a
|
|
C array based mutable array at their specific strengths, it attempts
|
|
to not suffer from either of their weaknesses, at the cost of additional
|
|
memory overhead.
|
|
</p>
|
|
*/
|
|
|
|
@interface NSMutableArray (GSSkipMutableArray)
|
|
/**
|
|
* Creates and returns an autoreleased NSMutableArray implemented as a
|
|
* skip list for rapid insertion/deletion within very large arrays.
|
|
*/
|
|
+ (NSMutableArray*) skipArray;
|
|
@end
|
|
|