diff options
author | Adrian Thurston <thurston@complang.org> | 2008-11-01 17:35:50 +0000 |
---|---|---|
committer | Adrian Thurston <thurston@complang.org> | 2008-11-01 17:35:50 +0000 |
commit | 10ff0e06801af15050848c701f606ac5de3ebc06 (patch) | |
tree | 21e08beb963d6208ef236afe8c9ca16469895547 /aapl | |
download | colm-10ff0e06801af15050848c701f606ac5de3ebc06.tar.gz |
Moved from private repository.
Diffstat (limited to 'aapl')
38 files changed, 10269 insertions, 0 deletions
diff --git a/aapl/COPYING b/aapl/COPYING new file mode 100644 index 00000000..c6ed510b --- /dev/null +++ b/aapl/COPYING @@ -0,0 +1,502 @@ + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + <one line to give the library's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + 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 2.1 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-1307 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + <signature of Ty Coon>, 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! diff --git a/aapl/README b/aapl/README new file mode 100644 index 00000000..a2fa5e65 --- /dev/null +++ b/aapl/README @@ -0,0 +1,6 @@ +This directory contains the Aapl source distribution. For the +documentation, build scripts, test programs, ChangeLog, etc. get the +aapldev package. + +AaplDev and other information about Aapl is available from +http://www.elude.ca/aapl/ diff --git a/aapl/astring.h b/aapl/astring.h new file mode 100644 index 00000000..37cc0cc4 --- /dev/null +++ b/aapl/astring.h @@ -0,0 +1,808 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_ASTRING_H +#define _AAPL_ASTRING_H + +#include <new> +#include <stdlib.h> +#include <stdarg.h> +#include <stdio.h> +#include <iostream> +#include <assert.h> + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +#ifdef AAPL_DOCUMENTATION + +/** + * \defgroup astring String + * \brief Implicitly shared copy-on-write string. + * + * @{ + */ + +/** + * \class String + * \brief Implicitly shared copy-on-write string. + */ + +/*@}*/ + +class String +{ +public: + /** + * \brief Create a null string. Data points to NULL. + */ + String(); + + /** + * \brief Construct a string from a c-style string. + * + * A new buffer is allocated for the c string. Initially, this string will + * be the only String class referencing the data. + */ + String( const char *s ); + + /** + * \brief Construct a string from a c-style string of specific length. + * + * A new buffer is allocated for the c string. Initially, this string will + * be the only String class referencing the data. + */ + String( const char *s, long len ); + + /** + * \brief Construct a string from another String. + * + * A refernce to the buffer allocated for s is taken. A new buffer is + * not allocated. + */ + String( const String &s ); + + /** + * \brief Construct a string using snprintf. + * + * Requires a maximum length for the resulting string. If the formatting + * (not including trailing null) requires more space than maxLen, the + * result will be truncated to maxLen long. Only the length actually + * written will be used by the new string. This string will be the only + * String class referencing the data. + */ + String( long maxLen, const char *format, ... ) + + /** + * \brief Clean up the string. + * + * If the string is not null, the referenced data is detached. If no other + * string refernces the detached data, it is deleted. + */ + ~String(); + + /** + * \brief Set the string from a c-style string. + * + * If this string is not null, the current buffer is dereferenced and + * possibly deleted. A new buffer is allocated (or possibly the old buffer + * reused) for the string. Initially, this string will be the only String + * class referencing the data. + * + * If s is null, then this string becomes a null ptr. + * + * \returns A reference to this. + */ + String &operator=( const char *s ); + + /** + * \brief Set the string from a c-style of specific length. + * + * If this string is not null, the current buffer is dereferenced and + * possibly deleted. A new buffer is allocated (or possibly the old buffer + * reused) for the string. Initially, this string will be the only String + * class referencing the data. + * + * If s is null, then this string becomes a null ptr. + * + * \returns A reference to this. + */ + void setAs( const char *s, long len ); + + /** + * \brief Set the string from a single char. + * + * The current buffer is dereferenced and possibly deleted. A new buffer + * is allocated (or possibly the old buffer reused) for the string. + * Initially, this string will be the only String class referencing the + * data. + * + * If s is null, then this string becomes a null ptr. + * + * \returns A reference to this. + */ + String &operator=( const char c ); + + + /** + * \brief Set the string from another String. + * + * If this string is not null, the current buffer is dereferenced and + * possibly deleted. A reference to the buffer allocated for s is taken. + * A new buffer is not allocated. + * + * If s is null, then this string becomes a null ptr. + * + * \returns a reference to this. + */ + String &operator=( const String &s ); + + /** + * \brief Append a c string to the end of this string. + * + * If this string shares its allocation with another, a copy is first + * taken. The buffer for this string is grown and s is appended to the + * end. + * + * If s is null nothing happens. + * + * \returns a reference to this. + */ + String &operator+=( const char *s ); + + /** + * \brief Append a c string of specific length to the end of this string. + * + * If this string shares its allocation with another, a copy is first + * taken. The buffer for this string is grown and s is appended to the + * end. + * + * If s is null nothing happens. + * + * \returns a reference to this. + */ + void append( const char *s, long len ); + + /** + * \brief Append a single char to the end of this string. + * + * If this string shares its allocation with another, a copy is first + * taken. The buffer for this string is grown and s is appended to the + * end. + * + * \returns a reference to this. + */ + String &operator+=( const char c ); + + /** + * \brief Append a String to the end of this string. + * + * If this string shares its allocation with another, a copy is first + * taken. The buffer for this string is grown and the data of s is + * appeneded to the end. + * + * If s is null nothing happens. + * + * returns a reference to this. + */ + String &operator+=( const String &s ); + + /** + * \brief Cast to a char star. + * + * \returns the string data. A null string returns 0. + */ + operator char*() const; + + /** + * \brief Get a pointer to the data. + * + * \returns the string Data + */ + char *get() const; + + /** + * \brief Get the length of the string + * + * If the string is null, then undefined behaviour results. + * + * \returns the length of the string. + */ + long length() const; + + /** + * \brief Pointer to the data. + * + * Publically accessible pointer to the data. Immediately in front of the + * string data block is the string header which stores the refcount and + * length. Consequently, care should be taken if modifying this pointer. + */ + char *data; +}; + +/** + * \relates String + * \brief Concatenate a c-style string and a String. + * + * \returns The concatenation of the two strings in a String. + */ +String operator+( const String &s1, const char *s2 ); + +/** + * \relates String + * \brief Concatenate a String and a c-style string. + * + * \returns The concatenation of the two strings in a String. + */ +String operator+( const char *s1, const String &s2 ); + +/** + * \relates String + * \brief Concatenate two String classes. + * + * \returns The concatenation of the two strings in a String. + */ +String operator+( const String &s1, const String &s2 ); + +#endif + +template<class T> class StrTmpl +{ +public: + class Fresh {}; + + /* Header located just before string data. Keeps the length and a refcount on + * the data. */ + struct Head + { + long refCount; + long length; + }; + + /** + * \brief Create a null string. + */ + StrTmpl() : data(0) { } + + /* Clean up the string. */ + ~StrTmpl(); + + /* Construct a string from a c-style string. */ + StrTmpl( const char *s ); + + /* Construct a string from a c-style string of specific len. */ + StrTmpl( const char *s, long len ); + + /* Allocate len spaces. */ + StrTmpl( const Fresh &, long len ); + + /* Construct a string from another StrTmpl. */ + StrTmpl( const StrTmpl &s ); + + /* Construct a string from with, sprintf. */ + StrTmpl( long lenGuess, const char *format, ... ); + + /* Set the string from a c-style string. */ + StrTmpl &operator=( const char *s ); + + /* Set the string from a c-style string of specific len. */ + void setAs( const char *s, long len ); + + /* Allocate len spaces. */ + void setAs( const Fresh &, long len ); + + void chop( long len ); + + /* Construct a string from with, sprintf. */ + void setAs( long lenGuess, const char *format, ... ); + + /* Set the string from a single char. */ + StrTmpl &operator=( const char c ); + + /* Set the string from another StrTmpl. */ + StrTmpl &operator=( const StrTmpl &s ); + + /* Append a c string to the end of this string. */ + StrTmpl &operator+=( const char *s ); + + /* Append a c string to the end of this string of specifi len. */ + void append( const char *s, long len ); + + /* Append a single char to the end of this string. */ + StrTmpl &operator+=( const char c ); + + /* Append an StrTmpl to the end of this string. */ + StrTmpl &operator+=( const StrTmpl &s ); + + /* Cast to a char star. */ + operator char*() const { return data; } + + /* Get a pointer to the data. */ + char *get() const { return data; } + + /* Return the length of the string. Must check for null data pointer. */ + long length() const { return data ? (((Head*)data)-1)->length : 0; } + + /** + * \brief Pointer to the data. + */ + char *data; + +protected: + /* Make space for a string of length len to be appended. */ + char *appendSpace( long len ); + void initSpace( long length ); + void setSpace( long length ); + + template <class FT> friend StrTmpl<FT> operator+( + const StrTmpl<FT> &s1, const char *s2 ); + template <class FT> friend StrTmpl<FT> operator+( + const char *s1, const StrTmpl<FT> &s2 ); + template <class FT> friend StrTmpl<FT> operator+( + const StrTmpl<FT> &s1, const StrTmpl<FT> &s2 ); + +private: + /* A dummy struct solely to make a constructor that will never be + * ambiguous with the public constructors. */ + struct DisAmbig { }; + StrTmpl( char *data, const DisAmbig & ) : data(data) { } +}; + +/* Free all mem used by the string. */ +template<class T> StrTmpl<T>::~StrTmpl() +{ + if ( data != 0 ) { + /* If we are the only ones referencing the string, then delete it. */ + Head *head = ((Head*) data) - 1; + head->refCount -= 1; + if ( head->refCount == 0 ) + free( head ); + } +} + +/* Create from a c-style string. */ +template<class T> StrTmpl<T>::StrTmpl( const char *s ) +{ + if ( s == 0 ) + data = 0; + else { + /* Find the length and allocate the space for the shared string. */ + long length = strlen( s ); + + /* Init space for the data. */ + initSpace( length ); + + /* Copy in the data. */ + memcpy( data, s, length+1 ); + } +} + +/* Create from a c-style string. */ +template<class T> StrTmpl<T>::StrTmpl( const char *s, long length ) +{ + if ( s == 0 ) + data = 0; + else { + /* Init space for the data. */ + initSpace( length ); + + /* Copy in the data. */ + memcpy( data, s, length ); + data[length] = 0; + } +} + +/* Create from a c-style string. */ +template<class T> StrTmpl<T>::StrTmpl( const Fresh &, long length ) +{ + /* Init space for the data. */ + initSpace( length ); + data[length] = 0; +} + +/* Create from another string class. */ +template<class T> StrTmpl<T>::StrTmpl( const StrTmpl &s ) +{ + if ( s.data == 0 ) + data = 0; + else { + /* Take a reference to the string. */ + Head *strHead = ((Head*)s.data) - 1; + strHead->refCount += 1; + data = (char*) (strHead+1); + } +} + +/* Construct a string from with, sprintf. */ +template<class T> StrTmpl<T>::StrTmpl( long lenGuess, const char *format, ... ) +{ + /* Set the string for len. */ + initSpace( lenGuess ); + + va_list args; + + /* Write to the temporary buffer. */ + va_start( args, format ); + + long written = vsnprintf( data, lenGuess+1, format, args ); + if ( written > lenGuess ) { + setSpace( written ); + written = vsnprintf( data, written+1, format, args ); + } + chop( written ); + + va_end( args ); +} + +/* Construct a string from with, sprintf. */ +template<class T> void StrTmpl<T>::setAs( long lenGuess, const char *format, ... ) +{ + /* Set the string for len. */ + setSpace( lenGuess ); + + va_list args; + + /* Write to the temporary buffer. */ + va_start( args, format ); + + long written = vsnprintf( data, lenGuess+1, format, args ); + if ( written > lenGuess ) { + setSpace( written ); + written = vsnprintf( data, written+1, format, args ); + } + chop( written ); + + va_end( args ); +} + +template<class T> void StrTmpl<T>::initSpace( long length ) +{ + /* Find the length and allocate the space for the shared string. */ + Head *head = (Head*) malloc( sizeof(Head) + length+1 ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Init the header. */ + head->refCount = 1; + head->length = length; + + /* Save the pointer to the data. */ + data = (char*) (head+1); +} + + +/* Set this string to be the c string exactly. The old string is discarded. + * Returns a reference to this. */ +template<class T> StrTmpl<T> &StrTmpl<T>::operator=( const char *s ) +{ + if ( s == 0 ) { + /* Just free the data, we are being set to null. */ + if ( data != 0 ) { + Head *head = ((Head*)data) - 1; + head->refCount -= 1; + if ( head->refCount == 0 ) + free(head); + data = 0; + } + } + else { + /* Find the length of the string we are setting. */ + long length = strlen( s ); + + /* Set the string for len. */ + setSpace( length ); + + /* Copy in the data. */ + memcpy( data, s, length+1 ); + } + return *this; +} + +/* Set this string to be the c string exactly. The old string is discarded. + * Returns a reference to this. */ +template<class T> void StrTmpl<T>::setAs( const char *s, long length ) +{ + if ( s == 0 ) { + /* Just free the data, we are being set to null. */ + if ( data != 0 ) { + Head *head = ((Head*)data) - 1; + head->refCount -= 1; + if ( head->refCount == 0 ) + free(head); + data = 0; + } + } + else { + /* Set the string for len. */ + setSpace( length ); + + /* Copy in the data. */ + memcpy( data, s, length ); + data[length] = 0; + } +} + +template<class T> void StrTmpl<T>::chop( long length ) +{ + /* Detach from the existing string. */ + Head *head = ((Head*)data) - 1; + assert( head->refCount == 1 ); + assert( length <= head->length ); + head->length = length; + data[length] = 0; +} + +/* Set this string to be the c string exactly. The old string is discarded. + * Returns a reference to this. */ +template<class T> void StrTmpl<T>::setAs( const Fresh &, long length ) +{ + setSpace( length ); + data[length] = 0; +} + +/* Set this string to be the single char exactly. The old string is discarded. + * Returns a reference to this. */ +template<class T> StrTmpl<T> &StrTmpl<T>::operator=( const char c ) +{ + /* Set to length 1. */ + setSpace( 1 ); + + /* Copy in the data. */ + data[0] = c; + data[1] = 0; + + /* Return ourselves. */ + return *this; +} + +/* Set this string to be the StrTmpl s exactly. The old string is + * discarded. */ +template<class T> StrTmpl<T> &StrTmpl<T>::operator=( const StrTmpl &s ) +{ + /* Detach from the existing string. */ + if ( data != 0 ) { + Head *head = ((Head*)data) - 1; + head->refCount -= 1; + if ( head->refCount == 0 ) + free( head ); + } + + if ( s.data != 0 ) { + /* Take a reference to the string. */ + Head *strHead = ((Head*)s.data) - 1; + strHead->refCount += 1; + data = (char*)(strHead+1); + } + else { + /* Setting from a null string, just null our pointer. */ + data = 0; + } + return *this; +} + +/* Prepare the string to be set to something else of the given length. */ +template<class T> void StrTmpl<T>::setSpace( long length ) +{ + /* Detach from the existing string. */ + Head *head = ((Head*)data) - 1; + if ( data != 0 && --head->refCount == 0 ) { + /* Resuse the space. */ + head = (Head*) realloc( head, sizeof(Head) + length+1 ); + } + else { + /* Need to make new space, there is no usable old space. */ + head = (Head*) malloc( sizeof(Head) + length+1 ); + } + if ( head == 0 ) + throw std::bad_alloc(); + + /* Init the header. */ + head->refCount = 1; + head->length = length; + + /* Copy in the data and save the pointer to it. */ + data = (char*) (head+1); +} + + +/* Append a c-style string to the end of this string. Returns a reference to + * this */ +template<class T> StrTmpl<T> &StrTmpl<T>::operator+=( const char *s ) +{ + /* Find the length of the string appended. */ + if ( s != 0 ) { + /* Get the string length and make space on the end. */ + long addedLen = strlen( s ); + char *dest = appendSpace( addedLen ); + + /* Copy the data in. Plus one for the null. */ + memcpy( dest, s, addedLen+1 ); + } + return *this; +} + +/* Append a c-style string of specific length to the end of this string. + * Returns a reference to this */ +template<class T> void StrTmpl<T>::append( const char *s, long length ) +{ + /* Find the length of the string appended. */ + if ( s != 0 ) { + /* Make space on the end. */ + char *dest = appendSpace( length ); + + /* Copy the data in. Plus one for the null. */ + memcpy( dest, s, length ); + dest[length] = 0; + } +} + +/* Append a single char to the end of this string. Returns a reference to + * this */ +template<class T> StrTmpl<T> &StrTmpl<T>::operator+=( const char c ) +{ + /* Grow on the end. */ + char *dst = appendSpace( 1 ); + + /* Append a single charachter. */ + dst[0] = c; + dst[1] = 0; + return *this; +} + + +/* Append an StrTmpl string to the end of this string. Returns a reference + * to this */ +template<class T> StrTmpl<T> &StrTmpl<T>::operator+=( const StrTmpl &s ) +{ + /* Find the length of the string appended. */ + if ( s.data != 0 ) { + /* Find the length to append. */ + long addedLen = (((Head*)s.data) - 1)->length; + + /* Make space on the end to put the string. */ + char *dest = appendSpace( addedLen ); + + /* Append the data, add one for the null. */ + memcpy( dest, s.data, addedLen+1 ); + } + return *this; +} + +/* Make space for a string of length len to be appended. */ +template<class T> char *StrTmpl<T>::appendSpace( long len ) +{ + /* Find the length of this and the string appended. */ + Head *head = (((Head*)data) - 1); + long thisLen = head->length; + + if ( head->refCount == 1 ) { + /* No other string is using the space, grow this space. */ + head = (Head*) realloc( head, + sizeof(Head) + thisLen + len + 1 ); + if ( head == 0 ) + throw std::bad_alloc(); + data = (char*) (head+1); + + /* Adjust the length. */ + head->length += len; + } + else { + /* Another string is using this space, make new space. */ + head->refCount -= 1; + Head *newHead = (Head*) malloc( + sizeof(Head) + thisLen + len + 1 ); + if ( newHead == 0 ) + throw std::bad_alloc(); + data = (char*) (newHead+1); + + /* Set the new header and data from this. */ + newHead->refCount = 1; + newHead->length = thisLen + len; + memcpy( data, head+1, thisLen ); + } + + /* Return writing position. */ + return data + thisLen; +} + +/* Concatenate a String and a c-style string. */ +template<class T> StrTmpl<T> operator+( const StrTmpl<T> &s1, const char *s2 ) +{ + /* Find s2 length and alloc the space for the result. */ + long str1Len = (((typename StrTmpl<T>::Head*)(s1.data)) - 1)->length; + long str2Len = strlen( s2 ); + + typename StrTmpl<T>::Head *head = (typename StrTmpl<T>::Head*) + malloc( sizeof(typename StrTmpl<T>::Head) + str1Len + str2Len + 1 ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Set up the header. */ + head->refCount = 1; + head->length = str1Len + str2Len; + + /* Save the pointer to data and copy the data in. */ + char *data = (char*) (head+1); + memcpy( data, s1.data, str1Len ); + memcpy( data + str1Len, s2, str2Len + 1 ); + return StrTmpl<T>( data, typename StrTmpl<T>::DisAmbig() ); +} + +/* Concatenate a c-style string and a String. */ +template<class T> StrTmpl<T> operator+( const char *s1, const StrTmpl<T> &s2 ) +{ + /* Find s2 length and alloc the space for the result. */ + long str1Len = strlen( s1 ); + long str2Len = (((typename StrTmpl<T>::Head*)(s2.data)) - 1)->length; + + typename StrTmpl<T>::Head *head = (typename StrTmpl<T>::Head*) + malloc( sizeof(typename StrTmpl<T>::Head) + str1Len + str2Len + 1 ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Set up the header. */ + head->refCount = 1; + head->length = str1Len + str2Len; + + /* Save the pointer to data and copy the data in. */ + char *data = (char*) (head+1); + memcpy( data, s1, str1Len ); + memcpy( data + str1Len, s2.data, str2Len + 1 ); + return StrTmpl<T>( data, typename StrTmpl<T>::DisAmbig() ); +} + +/* Add two StrTmpl strings. */ +template<class T> StrTmpl<T> operator+( const StrTmpl<T> &s1, const StrTmpl<T> &s2 ) +{ + /* Find s2 length and alloc the space for the result. */ + long str1Len = (((typename StrTmpl<T>::Head*)(s1.data)) - 1)->length; + long str2Len = (((typename StrTmpl<T>::Head*)(s2.data)) - 1)->length; + typename StrTmpl<T>::Head *head = (typename StrTmpl<T>::Head*) + malloc( sizeof(typename StrTmpl<T>::Head) + str1Len + str2Len + 1 ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Set up the header. */ + head->refCount = 1; + head->length = str1Len + str2Len; + + /* Save the pointer to data and copy the data in. */ + char *data = (char*) (head+1); + memcpy( data, s1.data, str1Len ); + memcpy( data + str1Len, s2.data, str2Len + 1 ); + return StrTmpl<T>( data, typename StrTmpl<T>::DisAmbig() ); +} + +/* Operator used in case the compiler does not support the conversion. */ +template <class T> inline std::ostream &operator<<( std::ostream &o, const StrTmpl<T> &s ) +{ + return o.write( s.data, s.length() ); +} + +typedef StrTmpl<char> String; + + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_ASTRING_H */ diff --git a/aapl/avlbasic.h b/aapl/avlbasic.h new file mode 100644 index 00000000..780ef07a --- /dev/null +++ b/aapl/avlbasic.h @@ -0,0 +1,65 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLBASIC_H +#define _AAPL_AVLBASIC_H + +#include "compare.h" + +/** + * \addtogroup avltree + * @{ + */ + +/** + * \class AvlBasic + * \brief AVL Tree in which the entire element structure is the key. + * + * AvlBasic is an AVL tree that does not distinguish between the element that + * it contains and the key. The entire element structure is the key that is + * used to compare the relative ordering of elements. This is similar to the + * BstSet structure. + * + * AvlBasic does not assume ownership of elements in the tree. Items must be + * explicitly de-allocated. + */ + +/*@}*/ + +#define BASE_EL(name) name +#define BASEKEY(name) name +#define AVLMEL_CLASSDEF class Element, class Compare +#define AVLMEL_TEMPDEF class Element, class Compare +#define AVLMEL_TEMPUSE Element, Compare +#define AvlTree AvlBasic +#define AVL_BASIC + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef AVL_BASIC + +#endif /* _AAPL_AVLBASIC_H */ diff --git a/aapl/avlcommon.h b/aapl/avlcommon.h new file mode 100644 index 00000000..fca4ea4f --- /dev/null +++ b/aapl/avlcommon.h @@ -0,0 +1,1630 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* This header is not wrapped in ifndef becuase it is not intended to + * be included by the user. */ + +#include <assert.h> + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +#ifdef WALKABLE +/* This is used by AvlTree, AvlMel and AvlMelKey so it + * must be protected by global ifdefs. */ +#ifndef __AAPL_AVLI_EL__ +#define __AAPL_AVLI_EL__ + +/** + * \brief Tree element properties for linked AVL trees. + * + * AvliTreeEl needs to be inherited by classes that intend to be element in an + * AvliTree. + */ +template<class SubClassEl> struct AvliTreeEl +{ + /** + * \brief Tree pointers connecting element in a tree. + */ + SubClassEl *left, *right, *parent; + + /** + * \brief Linked list pointers. + */ + SubClassEl *prev, *next; + + /** + * \brief Height of the tree rooted at this element. + * + * Height is required by the AVL balancing algorithm. + */ + long height; +}; +#endif /* __AAPL_AVLI_EL__ */ + +#else /* not WALKABLE */ + +/* This is used by All the non walkable trees so it must be + * protected by a global ifdef. */ +#ifndef __AAPL_AVL_EL__ +#define __AAPL_AVL_EL__ +/** + * \brief Tree element properties for linked AVL trees. + * + * AvlTreeEl needs to be inherited by classes that intend to be element in an + * AvlTree. + */ +template<class SubClassEl> struct AvlTreeEl +{ + /** + * \brief Tree pointers connecting element in a tree. + */ + SubClassEl *left, *right, *parent; + + /** + * \brief Height of the tree rooted at this element. + * + * Height is required by the AVL balancing algorithm. + */ + long height; +}; +#endif /* __AAPL_AVL_EL__ */ +#endif /* def WALKABLE */ + + +#if defined( AVLTREE_MAP ) + +#ifdef WALKABLE + +/** + * \brief Tree element for AvliMap + * + * Stores the key and value pair. + */ +template <class Key, class Value> struct AvliMapEl : + public AvliTreeEl< AvliMapEl<Key, Value> > +{ + AvliMapEl(const Key &key) + : key(key) { } + AvliMapEl(const Key &key, const Value &value) + : key(key), value(value) { } + + const Key &getKey() const { return key; } + + /** \brief The key. */ + Key key; + + /** \brief The value. */ + Value value; +}; +#else /* not WALKABLE */ + +/** + * \brief Tree element for AvlMap + * + * Stores the key and value pair. + */ +template <class Key, class Value> struct AvlMapEl : + public AvlTreeEl< AvlMapEl<Key, Value> > +{ + AvlMapEl(const Key &key) + : key(key) { } + AvlMapEl(const Key &key, const Value &value) + : key(key), value(value) { } + + const Key &getKey() const { return key; } + + /** \brief The key. */ + Key key; + + /** \brief The value. */ + Value value; +}; +#endif /* def WALKABLE */ + +#elif defined( AVLTREE_SET ) + +#ifdef WALKABLE +/** + * \brief Tree element for AvliSet + * + * Stores the key. + */ +template <class Key> struct AvliSetEl : + public AvliTreeEl< AvliSetEl<Key> > +{ + AvliSetEl(const Key &key) : key(key) { } + + const Key &getKey() const { return key; } + + /** \brief The key. */ + Key key; +}; +#else /* not WALKABLE */ +/** + * \brief Tree element for AvlSet + * + * Stores the key. + */ +template <class Key> struct AvlSetEl : + public AvlTreeEl< AvlSetEl<Key> > +{ + AvlSetEl(const Key &key) : key(key) { } + + const Key &getKey() const { return key; } + + /** \brief The key. */ + Key key; +}; +#endif /* def WALKABLE */ + +#endif /* AVLTREE_SET */ + +/* Common AvlTree Class */ +template < AVLMEL_CLASSDEF > class AvlTree +#if !defined( AVL_KEYLESS ) && defined ( WALKABLE ) + : public Compare, public BASELIST +#elif !defined( AVL_KEYLESS ) + : public Compare +#elif defined( WALKABLE ) + : public BASELIST +#endif +{ +public: + /** + * \brief Create an empty tree. + */ +#ifdef WALKABLE + AvlTree() : root(0), treeSize(0) { } +#else + AvlTree() : root(0), head(0), tail(0), treeSize(0) { } +#endif + + /** + * \brief Perform a deep copy of the tree. + * + * Each element is duplicated for the new tree. Copy constructors are used + * to create the new elements. + */ + AvlTree(const AvlTree &other); + +#if defined( AVLTREE_MAP ) || defined( AVLTREE_SET ) + /** + * \brief Clear the contents of the tree. + * + * All element are deleted. + */ + ~AvlTree() { empty(); } + + /** + * \brief Perform a deep copy of the tree. + * + * Each element is duplicated for the new tree. Copy constructors are used + * to create the new element. If this tree contains items, they are first + * deleted. + * + * \returns A reference to this. + */ + AvlTree &operator=( const AvlTree &tree ); + + /** + * \brief Transfer the elements of another tree into this. + * + * First deletes all elements in this tree. + */ + void transfer( AvlTree &tree ); +#else + /** + * \brief Abandon all elements in the tree. + * + * Tree elements are not deleted. + */ + ~AvlTree() {} + + /** + * \brief Perform a deep copy of the tree. + * + * Each element is duplicated for the new tree. Copy constructors are used + * to create the new element. If this tree contains items, they are + * abandoned. + * + * \returns A reference to this. + */ + AvlTree &operator=( const AvlTree &tree ); + + /** + * \brief Transfer the elements of another tree into this. + * + * All elements in this tree are abandoned first. + */ + void transfer( AvlTree &tree ); +#endif + +#ifndef AVL_KEYLESS + /* Insert a element into the tree. */ + Element *insert( Element *element, Element **lastFound = 0 ); + +#ifdef AVL_BASIC + /* Find a element in the tree. Returns the element if + * element exists, false otherwise. */ + Element *find( const Element *element ) const; + +#else + Element *insert( const Key &key, Element **lastFound = 0 ); + +#ifdef AVLTREE_MAP + Element *insert( const Key &key, const Value &val, + Element **lastFound = 0 ); +#endif + + /* Find a element in the tree. Returns the element if + * key exists, false otherwise. */ + Element *find( const Key &key ) const; + + /* Detach a element from the tree. */ + Element *detach( const Key &key ); + + /* Detach and delete a element from the tree. */ + bool remove( const Key &key ); +#endif /* AVL_BASIC */ +#endif /* AVL_KEYLESS */ + + /* Detach a element from the tree. */ + Element *detach( Element *element ); + + /* Detach and delete a element from the tree. */ + void remove( Element *element ); + + /* Free all memory used by tree. */ + void empty(); + + /* Abandon all element in the tree. Does not delete element. */ + void abandon(); + + /** Root element of the tree. */ + Element *root; + +#ifndef WALKABLE + Element *head, *tail; +#endif + + /** The number of element in the tree. */ + long treeSize; + + /** \brief Return the number of elements in the tree. */ + long length() const { return treeSize; } + + /** \brief Return the number of elements in the tree. */ + long size() const { return treeSize; } + + /* Various classes for setting the iterator */ + struct Iter; + struct IterFirst { IterFirst( const AvlTree &t ) : t(t) { } const AvlTree &t; }; + struct IterLast { IterLast( const AvlTree &t ) : t(t) { } const AvlTree &t; }; + struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; }; + struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; }; + +#ifdef WALKABLE + /** + * \brief Avl Tree Iterator. + * \ingroup iterators + */ + struct Iter + { + /* Default construct. */ + Iter() : ptr(0) { } + + /* Construct from an avl tree and iterator-setting classes. */ + Iter( const AvlTree &t ) : ptr(t.head) { } + Iter( const IterFirst &af ) : ptr(af.t.head) { } + Iter( const IterLast &al ) : ptr(al.t.tail) { } + Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)) { } + Iter( const IterPrev &ap ) : ptr(findPrev(ap.i.ptr)) { } + + /* Assign from a tree and iterator-setting classes. */ + Iter &operator=( const AvlTree &tree ) { ptr = tree.head; return *this; } + Iter &operator=( const IterFirst &af ) { ptr = af.t.head; return *this; } + Iter &operator=( const IterLast &al ) { ptr = al.t.tail; return *this; } + Iter &operator=( const IterNext &an ) { ptr = findNext(an.i.ptr); return *this; } + Iter &operator=( const IterPrev &ap ) { ptr = findPrev(ap.i.ptr); return *this; } + + /** \brief Less than end? */ + bool lte() const { return ptr != 0; } + + /** \brief At end? */ + bool end() const { return ptr == 0; } + + /** \brief Greater than beginning? */ + bool gtb() const { return ptr != 0; } + + /** \brief At beginning? */ + bool beg() const { return ptr == 0; } + + /** \brief At first element? */ + bool first() const { return ptr && ptr->BASE_EL(prev) == 0; } + + /** \brief At last element? */ + bool last() const { return ptr && ptr->BASE_EL(next) == 0; } + + /** \brief Implicit cast to Element*. */ + operator Element*() const { return ptr; } + + /** \brief Dereference operator returns Element&. */ + Element &operator *() const { return *ptr; } + + /** \brief Arrow operator returns Element*. */ + Element *operator->() const { return ptr; } + + /** \brief Move to next item. */ + inline Element *operator++(); + + /** \brief Move to next item. */ + inline Element *operator++(int); + + /** \brief Move to next item. */ + inline Element *increment(); + + /** \brief Move to previous item. */ + inline Element *operator--(); + + /** \brief Move to previous item. */ + inline Element *operator--(int); + + /** \brief Move to previous item. */ + inline Element *decrement(); + + /** \brief Return the next item. Does not modify this. */ + IterNext next() const { return IterNext( *this ); } + + /** \brief Return the previous item. Does not modify this. */ + IterPrev prev() const { return IterPrev( *this ); } + + private: + static Element *findPrev( Element *element ) { return element->BASE_EL(prev); } + static Element *findNext( Element *element ) { return element->BASE_EL(next); } + + public: + + /** \brief The iterator is simply a pointer. */ + Element *ptr; + }; + +#else + + /** + * \brief Avl Tree Iterator. + * \ingroup iterators + */ + struct Iter + { + /* Default construct. */ + Iter() : ptr(0), tree(0) { } + + /* Construct from a tree and iterator-setting classes. */ + Iter( const AvlTree &t ) : ptr(t.head), tree(&t) { } + Iter( const IterFirst &af ) : ptr(af.t.head), tree(&af.t) { } + Iter( const IterLast &al ) : ptr(al.t.tail), tree(&al.t) { } + Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)), tree(an.i.tree) { } + Iter( const IterPrev &ap ) : ptr(findPrev(ap.i.ptr)), tree(ap.i.tree) { } + + /* Assign from a tree and iterator-setting classes. */ + Iter &operator=( const AvlTree &t ) + { ptr = t.head; tree = &t; return *this; } + Iter &operator=( const IterFirst &af ) + { ptr = af.t.head; tree = &af.t; return *this; } + Iter &operator=( const IterLast &al ) + { ptr = al.t.tail; tree = &al.t; return *this; } + Iter &operator=( const IterNext &an ) + { ptr = findNext(an.i.ptr); tree = an.i.tree; return *this; } + Iter &operator=( const IterPrev &ap ) + { ptr = findPrev(ap.i.ptr); tree = ap.i.tree; return *this; } + + /** \brief Less than end? */ + bool lte() const { return ptr != 0; } + + /** \brief At end? */ + bool end() const { return ptr == 0; } + + /** \brief Greater than beginning? */ + bool gtb() const { return ptr != 0; } + + /** \brief At beginning? */ + bool beg() const { return ptr == 0; } + + /** \brief At first element? */ + bool first() const { return ptr && ptr == tree->head; } + + /** \brief At last element? */ + bool last() const { return ptr && ptr == tree->tail; } + + /** \brief Implicit cast to Element*. */ + operator Element*() const { return ptr; } + + /** \brief Dereference operator returns Element&. */ + Element &operator *() const { return *ptr; } + + /** \brief Arrow operator returns Element*. */ + Element *operator->() const { return ptr; } + + /** \brief Move to next item. */ + inline Element *operator++(); + + /** \brief Move to next item. */ + inline Element *operator++(int); + + /** \brief Move to next item. */ + inline Element *increment(); + + /** \brief Move to previous item. */ + inline Element *operator--(); + + /** \brief Move to previous item. */ + inline Element *operator--(int); + + /** \brief Move to previous item. */ + inline Element *decrement(); + + /** \brief Return the next item. Does not modify this. */ + IterNext next() const { return IterNext( *this ); } + + /** \brief Return the previous item. Does not modify this. */ + IterPrev prev() const { return IterPrev( *this ); } + + private: + static Element *findPrev( Element *element ); + static Element *findNext( Element *element ); + + public: + /** \brief The iterator is simply a pointer. */ + Element *ptr; + + /* The list is not walkable so we need to keep a pointerto the tree + * so we can test against head and tail in O(1) time. */ + const AvlTree *tree; + }; +#endif + + /** \brief Return first element. */ + IterFirst first() { return IterFirst( *this ); } + + /** \brief Return last element. */ + IterLast last() { return IterLast( *this ); } + +protected: + /* Recursive worker for the copy constructor. */ + Element *copyBranch( Element *element ); + + /* Recursively delete element in the tree. */ + void deleteChildrenOf(Element *n); + + /* rebalance the tree beginning at the leaf whose + * grandparent is unbalanced. */ + Element *rebalance(Element *start); + + /* Move up the tree from a given element, recalculating the heights. */ + void recalcHeights(Element *start); + + /* Move up the tree and find the first element whose + * grand-parent is unbalanced. */ + Element *findFirstUnbalGP(Element *start); + + /* Move up the tree and find the first element which is unbalanced. */ + Element *findFirstUnbalEl(Element *start); + + /* Replace a element in the tree with another element not in the tree. */ + void replaceEl(Element *element, Element *replacement); + + /* Remove a element from the tree and put another (normally a child of element) + * in its place. */ + void removeEl(Element *element, Element *filler); + + /* Once an insertion point is found at a leaf then do the insert. */ + void attachRebal( Element *element, Element *parentEl, Element *lastLess ); +}; + +/* Copy constructor. New up each item. */ +template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE>:: + AvlTree(const AvlTree<AVLMEL_TEMPUSE> &other) +#if !defined( AVL_KEYLESS ) && defined ( WALKABLE ) + /* BASELIST should be made empty. The copyBranch function + * will fill in the details for us. */ + : Compare( other ), BASELIST() +#elif !defined( AVL_KEYLESS ) + : Compare( other ) +#elif defined( WALKABLE ) + : BASELIST( ) +#endif +{ + treeSize = other.treeSize; + root = other.root; + +#ifndef WALKABLE + head = 0; + tail = 0; +#endif + + /* If there is a root, copy the tree. */ + if ( other.root != 0 ) + root = copyBranch( other.root ); +} + +#if defined( AVLTREE_MAP ) || defined( AVLTREE_SET ) + +/* Assignment does deep copy. */ +template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE> &AvlTree<AVLMEL_TEMPUSE>:: + operator=( const AvlTree &other ) +{ + /* Clear the tree first. */ + empty(); + + /* Reset the list pointers, the tree copy will fill in the list for us. */ +#ifdef WALKABLE + BASELIST::abandon(); +#else + head = 0; + tail = 0; +#endif + + /* Copy the entire tree. */ + treeSize = other.treeSize; + root = other.root; + if ( other.root != 0 ) + root = copyBranch( other.root ); + return *this; +} + +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + transfer(AvlTree<AVLMEL_TEMPUSE> &other) +{ + /* Clear the tree first. */ + empty(); + + treeSize = other.treeSize; + root = other.root; + +#ifdef WALKABLE + BASELIST::head = other.BASELIST::head; + BASELIST::tail = other.BASELIST::tail; + BASELIST::listLen = other.BASELIST::listLen; +#else + head = other.head; + tail = other.tail; +#endif + + other.abandon(); +} + +#else /* ! AVLTREE_MAP && ! AVLTREE_SET */ + +/* Assignment does deep copy. This version does not clear the tree first. */ +template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE> &AvlTree<AVLMEL_TEMPUSE>:: + operator=( const AvlTree &other ) +{ + /* Reset the list pointers, the tree copy will fill in the list for us. */ +#ifdef WALKABLE + BASELIST::abandon(); +#else + head = 0; + tail = 0; +#endif + + /* Copy the entire tree. */ + treeSize = other.treeSize; + root = other.root; + if ( other.root != 0 ) + root = copyBranch( other.root ); + return *this; +} + +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + transfer(AvlTree<AVLMEL_TEMPUSE> &other) +{ + treeSize = other.treeSize; + root = other.root; + +#ifdef WALKABLE + BASELIST::head = other.BASELIST::head; + BASELIST::tail = other.BASELIST::tail; + BASELIST::listLen = other.BASELIST::listLen; +#else + head = other.head; + tail = other.tail; +#endif + + other.abandon(); +} + +#endif + +/* + * Iterator operators. + */ + +/* Prefix ++ */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + operator++() +{ + return ptr = findNext( ptr ); +} + +/* Postfix ++ */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + operator++(int) +{ + Element *rtn = ptr; + ptr = findNext( ptr ); + return rtn; +} + +/* increment */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + increment() +{ + return ptr = findNext( ptr ); +} + +/* Prefix -- */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + operator--() +{ + return ptr = findPrev( ptr ); +} + +/* Postfix -- */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + operator--(int) +{ + Element *rtn = ptr; + ptr = findPrev( ptr ); + return rtn; +} + +/* decrement */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + decrement() +{ + return ptr = findPrev( ptr ); +} + +#ifndef WALKABLE + +/* Move ahead one. */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + findNext( Element *element ) +{ + /* Try to go right once then infinite left. */ + if ( element->BASE_EL(right) != 0 ) { + element = element->BASE_EL(right); + while ( element->BASE_EL(left) != 0 ) + element = element->BASE_EL(left); + } + else { + /* Go up to parent until we were just a left child. */ + while ( true ) { + Element *last = element; + element = element->BASE_EL(parent); + if ( element == 0 || element->BASE_EL(left) == last ) + break; + } + } + return element; +} + +/* Move back one. */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter:: + findPrev( Element *element ) +{ + /* Try to go left once then infinite right. */ + if ( element->BASE_EL(left) != 0 ) { + element = element->BASE_EL(left); + while ( element->BASE_EL(right) != 0 ) + element = element->BASE_EL(right); + } + else { + /* Go up to parent until we were just a left child. */ + while ( true ) { + Element *last = element; + element = element->BASE_EL(parent); + if ( element == 0 || element->BASE_EL(right) == last ) + break; + } + } + return element; +} + +#endif + + +/* Recursive worker for tree copying. */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + copyBranch( Element *element ) +{ + /* Duplicate element. Either the base element's copy constructor or defaul + * constructor will get called. Both will suffice for initting the + * pointers to null when they need to be. */ + Element *retVal = new Element(*element); + + /* If the left tree is there, copy it. */ + if ( retVal->BASE_EL(left) ) { + retVal->BASE_EL(left) = copyBranch(retVal->BASE_EL(left)); + retVal->BASE_EL(left)->BASE_EL(parent) = retVal; + } + +#ifdef WALKABLE + BASELIST::addAfter( BASELIST::tail, retVal ); +#else + if ( head == 0 ) + head = retVal; + tail = retVal; +#endif + + /* If the right tree is there, copy it. */ + if ( retVal->BASE_EL(right) ) { + retVal->BASE_EL(right) = copyBranch(retVal->BASE_EL(right)); + retVal->BASE_EL(right)->BASE_EL(parent) = retVal; + } + return retVal; +} + +/* Once an insertion position is found, attach a element to the tree. */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + attachRebal( Element *element, Element *parentEl, Element *lastLess ) +{ + /* Increment the number of element in the tree. */ + treeSize += 1; + + /* Set element's parent. */ + element->BASE_EL(parent) = parentEl; + + /* New element always starts as a leaf with height 1. */ + element->BASE_EL(left) = 0; + element->BASE_EL(right) = 0; + element->BASE_EL(height) = 1; + + /* Are we inserting in the tree somewhere? */ + if ( parentEl != 0 ) { + /* We have a parent so we are somewhere in the tree. If the parent + * equals lastLess, then the last traversal in the insertion went + * left, otherwise it went right. */ + if ( lastLess == parentEl ) { + parentEl->BASE_EL(left) = element; +#ifdef WALKABLE + BASELIST::addBefore( parentEl, element ); +#endif + } + else { + parentEl->BASE_EL(right) = element; +#ifdef WALKABLE + BASELIST::addAfter( parentEl, element ); +#endif + } + +#ifndef WALKABLE + /* Maintain the first and last pointers. */ + if ( head->BASE_EL(left) == element ) + head = element; + + /* Maintain the first and last pointers. */ + if ( tail->BASE_EL(right) == element ) + tail = element; +#endif + } + else { + /* No parent element so we are inserting the root. */ + root = element; +#ifdef WALKABLE + BASELIST::addAfter( BASELIST::tail, element ); +#else + head = tail = element; +#endif + } + + + /* Recalculate the heights. */ + recalcHeights(parentEl); + + /* Find the first unbalance. */ + Element *ub = findFirstUnbalGP(element); + + /* rebalance. */ + if ( ub != 0 ) + { + /* We assert that after this single rotation the + * tree is now properly balanced. */ + rebalance(ub); + } +} + +#ifndef AVL_KEYLESS + +/** + * \brief Insert an existing element into the tree. + * + * If the insert succeeds and lastFound is given then it is set to the element + * inserted. If the insert fails then lastFound is set to the existing element in + * the tree that has the same key as element. If the element's avl pointers are + * already in use then undefined behaviour results. + * + * \returns The element inserted upon success, null upon failure. + */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + insert( Element *element, Element **lastFound ) +{ + long keyRelation; + Element *curEl = root, *parentEl = 0; + Element *lastLess = 0; + + while (true) { + if ( curEl == 0 ) { + /* We are at an external element and did not find the key we were + * looking for. Attach underneath the leaf and rebalance. */ + attachRebal( element, parentEl, lastLess ); + + if ( lastFound != 0 ) + *lastFound = element; + return element; + } + +#ifdef AVL_BASIC + keyRelation = compare( *element, *curEl ); +#else + keyRelation = compare( element->BASEKEY(getKey()), + curEl->BASEKEY(getKey()) ); +#endif + + /* Do we go left? */ + if ( keyRelation < 0 ) { + parentEl = lastLess = curEl; + curEl = curEl->BASE_EL(left); + } + /* Do we go right? */ + else if ( keyRelation > 0 ) { + parentEl = curEl; + curEl = curEl->BASE_EL(right); + } + /* We have hit the target. */ + else { + if ( lastFound != 0 ) + *lastFound = curEl; + return 0; + } + } +} + +#ifdef AVL_BASIC + +/** + * \brief Find a element in the tree with the given key. + * + * \returns The element if key exists, null if the key does not exist. + */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + find( const Element *element ) const +{ + Element *curEl = root; + long keyRelation; + + while (curEl) { + keyRelation = compare( *element, *curEl ); + + /* Do we go left? */ + if ( keyRelation < 0 ) + curEl = curEl->BASE_EL(left); + /* Do we go right? */ + else if ( keyRelation > 0 ) + curEl = curEl->BASE_EL(right); + /* We have hit the target. */ + else { + return curEl; + } + } + return 0; +} + +#else + +/** + * \brief Insert a new element into the tree with given key. + * + * If the key is not already in the tree then a new element is made using the + * Element(const Key &key) constructor and the insert succeeds. If lastFound is + * given then it is set to the element inserted. If the insert fails then + * lastFound is set to the existing element in the tree that has the same key as + * element. + * + * \returns The new element upon success, null upon failure. + */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + insert( const Key &key, Element **lastFound ) +{ + long keyRelation; + Element *curEl = root, *parentEl = 0; + Element *lastLess = 0; + + while (true) { + if ( curEl == 0 ) { + /* We are at an external element and did not find the key we were + * looking for. Create the new element, attach it underneath the leaf + * and rebalance. */ + Element *element = new Element( key ); + attachRebal( element, parentEl, lastLess ); + + if ( lastFound != 0 ) + *lastFound = element; + return element; + } + + keyRelation = compare( key, curEl->BASEKEY(getKey()) ); + + /* Do we go left? */ + if ( keyRelation < 0 ) { + parentEl = lastLess = curEl; + curEl = curEl->BASE_EL(left); + } + /* Do we go right? */ + else if ( keyRelation > 0 ) { + parentEl = curEl; + curEl = curEl->BASE_EL(right); + } + /* We have hit the target. */ + else { + if ( lastFound != 0 ) + *lastFound = curEl; + return 0; + } + } +} + +#ifdef AVLTREE_MAP +/** + * \brief Insert a new element into the tree with key and value. + * + * If the key is not already in the tree then a new element is constructed and + * the insert succeeds. If lastFound is given then it is set to the element + * inserted. If the insert fails then lastFound is set to the existing element in + * the tree that has the same key as element. This insert routine is only + * available in AvlMap because it is the only class that knows about a Value + * type. + * + * \returns The new element upon success, null upon failure. + */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + insert( const Key &key, const Value &val, Element **lastFound ) +{ + long keyRelation; + Element *curEl = root, *parentEl = 0; + Element *lastLess = 0; + + while (true) { + if ( curEl == 0 ) { + /* We are at an external element and did not find the key we were + * looking for. Create the new element, attach it underneath the leaf + * and rebalance. */ + Element *element = new Element( key, val ); + attachRebal( element, parentEl, lastLess ); + + if ( lastFound != 0 ) + *lastFound = element; + return element; + } + + keyRelation = compare(key, curEl->getKey()); + + /* Do we go left? */ + if ( keyRelation < 0 ) { + parentEl = lastLess = curEl; + curEl = curEl->BASE_EL(left); + } + /* Do we go right? */ + else if ( keyRelation > 0 ) { + parentEl = curEl; + curEl = curEl->BASE_EL(right); + } + /* We have hit the target. */ + else { + if ( lastFound != 0 ) + *lastFound = curEl; + return 0; + } + } +} +#endif /* AVLTREE_MAP */ + + +/** + * \brief Find a element in the tree with the given key. + * + * \returns The element if key exists, null if the key does not exist. + */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + find( const Key &key ) const +{ + Element *curEl = root; + long keyRelation; + + while (curEl) { + keyRelation = compare( key, curEl->BASEKEY(getKey()) ); + + /* Do we go left? */ + if ( keyRelation < 0 ) + curEl = curEl->BASE_EL(left); + /* Do we go right? */ + else if ( keyRelation > 0 ) + curEl = curEl->BASE_EL(right); + /* We have hit the target. */ + else { + return curEl; + } + } + return 0; +} + + +/** + * \brief Find a element, then detach it from the tree. + * + * The element is not deleted. + * + * \returns The element detached if the key is found, othewise returns null. + */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + detach(const Key &key) +{ + Element *element = find( key ); + if ( element ) { + detach(element); + } + + return element; +} + +/** + * \brief Find, detach and delete a element from the tree. + * + * \returns True if the element was found and deleted, false otherwise. + */ +template <AVLMEL_TEMPDEF> bool AvlTree<AVLMEL_TEMPUSE>:: + remove(const Key &key) +{ + /* Assume not found. */ + bool retVal = false; + + /* Look for the key. */ + Element *element = find( key ); + if ( element != 0 ) { + /* If found, detach the element and delete. */ + detach( element ); + delete element; + retVal = true; + } + + return retVal; +} + +#endif /* AVL_BASIC */ +#endif /* AVL_KEYLESS */ + + +/** + * \brief Detach and delete a element from the tree. + * + * If the element is not in the tree then undefined behaviour results. + */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + remove(Element *element) +{ + /* Detach and delete. */ + detach(element); + delete element; +} + +/** + * \brief Detach a element from the tree. + * + * If the element is not in the tree then undefined behaviour results. + * + * \returns The element given. + */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + detach(Element *element) +{ + Element *replacement, *fixfrom; + long lheight, rheight; + +#ifdef WALKABLE + /* Remove the element from the ordered list. */ + BASELIST::detach( element ); +#endif + + /* Update treeSize. */ + treeSize--; + + /* Find a replacement element. */ + if (element->BASE_EL(right)) + { + /* Find the leftmost element of the right subtree. */ + replacement = element->BASE_EL(right); + while (replacement->BASE_EL(left)) + replacement = replacement->BASE_EL(left); + + /* If replacing the element the with its child then we need to start + * fixing at the replacement, otherwise we start fixing at the + * parent of the replacement. */ + if (replacement->BASE_EL(parent) == element) + fixfrom = replacement; + else + fixfrom = replacement->BASE_EL(parent); + +#ifndef WALKABLE + if ( element == head ) + head = replacement; +#endif + + removeEl(replacement, replacement->BASE_EL(right)); + replaceEl(element, replacement); + } + else if (element->BASE_EL(left)) + { + /* Find the rightmost element of the left subtree. */ + replacement = element->BASE_EL(left); + while (replacement->BASE_EL(right)) + replacement = replacement->BASE_EL(right); + + /* If replacing the element the with its child then we need to start + * fixing at the replacement, otherwise we start fixing at the + * parent of the replacement. */ + if (replacement->BASE_EL(parent) == element) + fixfrom = replacement; + else + fixfrom = replacement->BASE_EL(parent); + +#ifndef WALKABLE + if ( element == tail ) + tail = replacement; +#endif + + removeEl(replacement, replacement->BASE_EL(left)); + replaceEl(element, replacement); + } + else + { + /* We need to start fixing at the parent of the element. */ + fixfrom = element->BASE_EL(parent); + +#ifndef WALKABLE + if ( element == head ) + head = element->BASE_EL(parent); + if ( element == tail ) + tail = element->BASE_EL(parent); +#endif + + /* The element we are deleting is a leaf element. */ + removeEl(element, 0); + } + + /* If fixfrom is null it means we just deleted + * the root of the tree. */ + if ( fixfrom == 0 ) + return element; + + /* Fix the heights after the deletion. */ + recalcHeights(fixfrom); + + /* Fix every unbalanced element going up in the tree. */ + Element *ub = findFirstUnbalEl(fixfrom); + while ( ub ) + { + /* Find the element to rebalance by moving down from the first unbalanced + * element 2 levels in the direction of the greatest heights. On the + * second move down, the heights may be equal ( but not on the first ). + * In which case go in the direction of the first move. */ + lheight = ub->BASE_EL(left) ? ub->BASE_EL(left)->BASE_EL(height) : 0; + rheight = ub->BASE_EL(right) ? ub->BASE_EL(right)->BASE_EL(height) : 0; + assert( lheight != rheight ); + if (rheight > lheight) + { + ub = ub->BASE_EL(right); + lheight = ub->BASE_EL(left) ? + ub->BASE_EL(left)->BASE_EL(height) : 0; + rheight = ub->BASE_EL(right) ? + ub->BASE_EL(right)->BASE_EL(height) : 0; + if (rheight > lheight) + ub = ub->BASE_EL(right); + else if (rheight < lheight) + ub = ub->BASE_EL(left); + else + ub = ub->BASE_EL(right); + } + else + { + ub = ub->BASE_EL(left); + lheight = ub->BASE_EL(left) ? + ub->BASE_EL(left)->BASE_EL(height) : 0; + rheight = ub->BASE_EL(right) ? + ub->BASE_EL(right)->BASE_EL(height) : 0; + if (rheight > lheight) + ub = ub->BASE_EL(right); + else if (rheight < lheight) + ub = ub->BASE_EL(left); + else + ub = ub->BASE_EL(left); + } + + + /* rebalance returns the grandparant of the subtree formed + * by the element that were rebalanced. + * We must continue upward from there rebalancing. */ + fixfrom = rebalance(ub); + + /* Find the next unbalaced element. */ + ub = findFirstUnbalEl(fixfrom); + } + + return element; +} + + +/** + * \brief Empty the tree and delete all the element. + * + * Resets the tree to its initial state. + */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::empty() +{ + if ( root ) { + /* Recursively delete from the tree structure. */ + deleteChildrenOf(root); + delete root; + root = 0; + treeSize = 0; + +#ifdef WALKABLE + BASELIST::abandon(); +#endif + } +} + +/** + * \brief Forget all element in the tree. + * + * Does not delete element. Resets the the tree to it's initial state. + */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::abandon() +{ + root = 0; + treeSize = 0; + +#ifdef WALKABLE + BASELIST::abandon(); +#endif +} + +/* Recursively delete all the children of a element. */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + deleteChildrenOf( Element *element ) +{ + /* Recurse left. */ + if (element->BASE_EL(left)) { + deleteChildrenOf(element->BASE_EL(left)); + + /* Delete left element. */ + delete element->BASE_EL(left); + element->BASE_EL(left) = 0; + } + + /* Recurse right. */ + if (element->BASE_EL(right)) { + deleteChildrenOf(element->BASE_EL(right)); + + /* Delete right element. */ + delete element->BASE_EL(right); + element->BASE_EL(left) = 0; + } +} + +/* rebalance from a element whose gradparent is unbalanced. Only + * call on a element that has a grandparent. */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + rebalance(Element *n) +{ + long lheight, rheight; + Element *a, *b, *c; + Element *t1, *t2, *t3, *t4; + + Element *p = n->BASE_EL(parent); /* parent (Non-NUL). L*/ + Element *gp = p->BASE_EL(parent); /* Grand-parent (Non-NULL). */ + Element *ggp = gp->BASE_EL(parent); /* Great grand-parent (may be NULL). */ + + if (gp->BASE_EL(right) == p) + { + /* gp + * \ + * p + */ + if (p->BASE_EL(right) == n) + { + /* gp + * \ + * p + * \ + * n + */ + a = gp; + b = p; + c = n; + t1 = gp->BASE_EL(left); + t2 = p->BASE_EL(left); + t3 = n->BASE_EL(left); + t4 = n->BASE_EL(right); + } + else + { + /* gp + * \ + * p + * / + * n + */ + a = gp; + b = n; + c = p; + t1 = gp->BASE_EL(left); + t2 = n->BASE_EL(left); + t3 = n->BASE_EL(right); + t4 = p->BASE_EL(right); + } + } + else + { + /* gp + * / + * p + */ + if (p->BASE_EL(right) == n) + { + /* gp + * / + * p + * \ + * n + */ + a = p; + b = n; + c = gp; + t1 = p->BASE_EL(left); + t2 = n->BASE_EL(left); + t3 = n->BASE_EL(right); + t4 = gp->BASE_EL(right); + } + else + { + /* gp + * / + * p + * / + * n + */ + a = n; + b = p; + c = gp; + t1 = n->BASE_EL(left); + t2 = n->BASE_EL(right); + t3 = p->BASE_EL(right); + t4 = gp->BASE_EL(right); + } + } + + /* Perform rotation. + */ + + /* Tie b to the great grandparent. */ + if ( ggp == 0 ) + root = b; + else if ( ggp->BASE_EL(left) == gp ) + ggp->BASE_EL(left) = b; + else + ggp->BASE_EL(right) = b; + b->BASE_EL(parent) = ggp; + + /* Tie a as a leftchild of b. */ + b->BASE_EL(left) = a; + a->BASE_EL(parent) = b; + + /* Tie c as a rightchild of b. */ + b->BASE_EL(right) = c; + c->BASE_EL(parent) = b; + + /* Tie t1 as a leftchild of a. */ + a->BASE_EL(left) = t1; + if ( t1 != 0 ) t1->BASE_EL(parent) = a; + + /* Tie t2 as a rightchild of a. */ + a->BASE_EL(right) = t2; + if ( t2 != 0 ) t2->BASE_EL(parent) = a; + + /* Tie t3 as a leftchild of c. */ + c->BASE_EL(left) = t3; + if ( t3 != 0 ) t3->BASE_EL(parent) = c; + + /* Tie t4 as a rightchild of c. */ + c->BASE_EL(right) = t4; + if ( t4 != 0 ) t4->BASE_EL(parent) = c; + + /* The heights are all recalculated manualy and the great + * grand-parent is passed to recalcHeights() to ensure + * the heights are correct up the tree. + * + * Note that recalcHeights() cuts out when it comes across + * a height that hasn't changed. + */ + + /* Fix height of a. */ + lheight = a->BASE_EL(left) ? a->BASE_EL(left)->BASE_EL(height) : 0; + rheight = a->BASE_EL(right) ? a->BASE_EL(right)->BASE_EL(height) : 0; + a->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1; + + /* Fix height of c. */ + lheight = c->BASE_EL(left) ? c->BASE_EL(left)->BASE_EL(height) : 0; + rheight = c->BASE_EL(right) ? c->BASE_EL(right)->BASE_EL(height) : 0; + c->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1; + + /* Fix height of b. */ + lheight = a->BASE_EL(height); + rheight = c->BASE_EL(height); + b->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1; + + /* Fix height of b's parents. */ + recalcHeights(ggp); + return ggp; +} + +/* Recalculates the heights of all the ancestors of element. */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + recalcHeights(Element *element) +{ + long lheight, rheight, new_height; + while ( element != 0 ) + { + lheight = element->BASE_EL(left) ? element->BASE_EL(left)->BASE_EL(height) : 0; + rheight = element->BASE_EL(right) ? element->BASE_EL(right)->BASE_EL(height) : 0; + + new_height = (lheight > rheight ? lheight : rheight) + 1; + + /* If there is no chage in the height, then there will be no + * change in any of the ancestor's height. We can stop going up. + * If there was a change, continue upward. */ + if (new_height == element->BASE_EL(height)) + return; + else + element->BASE_EL(height) = new_height; + + element = element->BASE_EL(parent); + } +} + +/* Finds the first element whose grandparent is unbalanced. */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + findFirstUnbalGP(Element *element) +{ + long lheight, rheight, balanceProp; + Element *gp; + + if ( element == 0 || element->BASE_EL(parent) == 0 || + element->BASE_EL(parent)->BASE_EL(parent) == 0 ) + return 0; + + /* Don't do anything if we we have no grandparent. */ + gp = element->BASE_EL(parent)->BASE_EL(parent); + while ( gp != 0 ) + { + lheight = gp->BASE_EL(left) ? gp->BASE_EL(left)->BASE_EL(height) : 0; + rheight = gp->BASE_EL(right) ? gp->BASE_EL(right)->BASE_EL(height) : 0; + balanceProp = lheight - rheight; + + if ( balanceProp < -1 || balanceProp > 1 ) + return element; + + element = element->BASE_EL(parent); + gp = gp->BASE_EL(parent); + } + return 0; +} + + +/* Finds the first element that is unbalanced. */ +template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>:: + findFirstUnbalEl(Element *element) +{ + if ( element == 0 ) + return 0; + + while ( element != 0 ) + { + long lheight = element->BASE_EL(left) ? + element->BASE_EL(left)->BASE_EL(height) : 0; + long rheight = element->BASE_EL(right) ? + element->BASE_EL(right)->BASE_EL(height) : 0; + long balanceProp = lheight - rheight; + + if ( balanceProp < -1 || balanceProp > 1 ) + return element; + + element = element->BASE_EL(parent); + } + return 0; +} + +/* Replace a element in the tree with another element not in the tree. */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + replaceEl(Element *element, Element *replacement) +{ + Element *parent = element->BASE_EL(parent), + *left = element->BASE_EL(left), + *right = element->BASE_EL(right); + + replacement->BASE_EL(left) = left; + if (left) + left->BASE_EL(parent) = replacement; + replacement->BASE_EL(right) = right; + if (right) + right->BASE_EL(parent) = replacement; + + replacement->BASE_EL(parent) = parent; + if (parent) + { + if (parent->BASE_EL(left) == element) + parent->BASE_EL(left) = replacement; + else + parent->BASE_EL(right) = replacement; + } + else + root = replacement; + + replacement->BASE_EL(height) = element->BASE_EL(height); +} + +/* Removes a element from a tree and puts filler in it's place. + * Filler should be null or a child of element. */ +template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>:: + removeEl(Element *element, Element *filler) +{ + Element *parent = element->BASE_EL(parent); + + if (parent) + { + if (parent->BASE_EL(left) == element) + parent->BASE_EL(left) = filler; + else + parent->BASE_EL(right) = filler; + } + else + root = filler; + + if (filler) + filler->BASE_EL(parent) = parent; + + return; +} + +#ifdef AAPL_NAMESPACE +} +#endif diff --git a/aapl/avlibasic.h b/aapl/avlibasic.h new file mode 100644 index 00000000..a48faaa8 --- /dev/null +++ b/aapl/avlibasic.h @@ -0,0 +1,67 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLIBASIC_H +#define _AAPL_AVLIBASIC_H + +#include "compare.h" + +/** + * \addtogroup avlitree + * @{ + */ + +/** + * \class AvliBasic + * \brief Linked AVL Tree in which the entire element structure is the key. + * + * AvliBasic is a linked AVL tree that does not distinguish between the + * element that it contains and the key. The entire element structure is the + * key that is used to compare the relative ordering of elements. This is + * similar to the BstSet structure. + * + * AvliBasic does not assume ownership of elements in the tree. Items must be + * explicitly de-allocated. + */ + +/*@}*/ + +#define BASE_EL(name) name +#define BASEKEY(name) name +#define AVLMEL_CLASSDEF class Element, class Compare +#define AVLMEL_TEMPDEF class Element, class Compare +#define AVLMEL_TEMPUSE Element, Compare +#define AvlTree AvliBasic +#define AVL_BASIC +#define WALKABLE + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef AVL_BASIC +#undef WALKABLE + +#endif /* _AAPL_AVLIBASIC_H */ diff --git a/aapl/avlikeyless.h b/aapl/avlikeyless.h new file mode 100644 index 00000000..559b75af --- /dev/null +++ b/aapl/avlikeyless.h @@ -0,0 +1,64 @@ +/* + * Copyright 2002, 2003 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLIKEYLESS_H +#define _AAPL_AVLIKEYLESS_H + +#include "compare.h" +#include "dlistmel.h" + +/** + * \addtogroup avlitree + * @{ + */ + +/** + * \class AvliKeyless + * \brief Linked AVL tree that has no insert/find/remove functions that take a + * key. + * + * AvliKeyless is an implementation of the AVL tree rebalancing functionality + * only. It provides the common code for the tiny AVL tree implementations. + */ + +/*@}*/ + +#define BASE_EL(name) name +#define BASELIST DListMel< Element, AvliTreeEl<Element> > +#define AVLMEL_CLASSDEF class Element +#define AVLMEL_TEMPDEF class Element +#define AVLMEL_TEMPUSE Element +#define AvlTree AvliKeyless +#define WALKABLE +#define AVL_KEYLESS + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASELIST +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef WALKABLE +#undef AVL_KEYLESS + +#endif /* _AAPL_AVLIKEYLESS_H */ diff --git a/aapl/avlimap.h b/aapl/avlimap.h new file mode 100644 index 00000000..38bfff75 --- /dev/null +++ b/aapl/avlimap.h @@ -0,0 +1,77 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLIMAP_H +#define _AAPL_AVLIMAP_H + +#include "compare.h" +#include "dlist.h" + +/** + * \addtogroup avlitree + * @{ + */ + +/** + * \class AvliMap + * \brief Linked key and value oriented AVL tree. + * + * AvliMap stores key and value pairs in elements that managed by the tree. It + * is intendend to be similar to map template found in the STL. AvliMap + * requires that a Key type, a Value type, and a class containing a compare() + * routine for Key be given. Items can be inserted with just a key or with a + * key and value pair. + * + * AvliMap assumes all elements in the tree are allocated on the heap and are + * to be managed by the tree. This means that the class destructor will delete + * the contents of the tree. A deep copy will cause existing elements to be + * deleted first. + * + * \include ex_avlimap.cpp + */ + +/*@}*/ + +#define AVLTREE_MAP +#define BASE_EL(name) name +#define BASEKEY(name) name +#define BASELIST DList< AvliMapEl<Key,Value> > +#define AVLMEL_CLASSDEF class Key, class Value, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Key, class Value, class Compare +#define AVLMEL_TEMPUSE Key, Value, Compare +#define AvlTree AvliMap +#define Element AvliMapEl<Key,Value> +#define WALKABLE + +#include "avlcommon.h" + +#undef AVLTREE_MAP +#undef BASE_EL +#undef BASEKEY +#undef BASELIST +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef Element +#undef WALKABLE + +#endif /* _AAPL_AVLIMAP_H */ diff --git a/aapl/avlimel.h b/aapl/avlimel.h new file mode 100644 index 00000000..9442a997 --- /dev/null +++ b/aapl/avlimel.h @@ -0,0 +1,79 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLIMEL_H +#define _AAPL_AVLIMEL_H + +#include "compare.h" +#include "dlistmel.h" + +/** + * \addtogroup avlitree + * @{ + */ + +/** + * \class AvliMel + * \brief Linked AVL tree for element appearing in multiple trees. + * + * AvliMel allows for an element to simultaneously be in multiple trees without + * the trees interferring with one another. For each tree that the element is + * to appear in, there must be a distinct set of AVL Tree management data that + * can be unambiguously referenced with some base class name. This name + * is passed to the tree as a template parameter and is used in the tree + * algorithms. + * + * The element must use the same key type and value in each tree that it + * appears in. If distinct keys are required, the AvliMelKey structure is + * available. + * + * AvliMel does not assume ownership of elements in the tree. The destructor + * will not delete the elements. If the user wishes to explicitly deallocate + * all the items in the tree the empty() routine is available. + * + * \include ex_avlimel.cpp + */ + +/*@}*/ + +#define BASE_EL(name) BaseEl::name +#define BASEKEY(name) name +#define BASELIST DListMel< Element, BaseEl > +#define AVLMEL_CLASSDEF class Element, class Key, \ + class BaseEl, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Element, class Key, \ + class BaseEl, class Compare +#define AVLMEL_TEMPUSE Element, Key, BaseEl, Compare +#define AvlTree AvliMel +#define WALKABLE + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef BASELIST +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef WALKABLE + +#endif /* _AAPL_AVLIMEL_H */ diff --git a/aapl/avlimelkey.h b/aapl/avlimelkey.h new file mode 100644 index 00000000..faa56e83 --- /dev/null +++ b/aapl/avlimelkey.h @@ -0,0 +1,76 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLIMELKEY_H +#define _AAPL_AVLIMELKEY_H + +#include "compare.h" +#include "dlistmel.h" + +/** + * \addtogroup avlitree + * @{ + */ + +/** + * \class AvliMelKey + * \brief Linked AVL tree for element appearing in multiple trees with different keys. + * + * AvliMelKey is similar to AvliMel, except that an additional template + * parameter, BaseKey, is provided for resolving ambiguous references to + * getKey(). This means that if an element is stored in multiple trees, each + * tree can use a different key for ordering the elements in it. Using + * AvliMelKey an array of data structures can be indexed with an O(log(n)) + * search on two or more of the values contained within it and without + * allocating any additional data. + * + * AvliMelKey does not assume ownership of elements in the tree. The destructor + * will not delete the elements. If the user wishes to explicitly deallocate + * all the items in the tree the empty() routine is available. + * + * \include ex_avlimelkey.cpp + */ + +/*@}*/ + +#define BASE_EL(name) BaseEl::name +#define BASEKEY(name) BaseKey::name +#define BASELIST DListMel< Element, BaseEl > +#define AVLMEL_CLASSDEF class Element, class Key, class BaseEl, \ + class BaseKey, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Element, class Key, class BaseEl, \ + class BaseKey, class Compare +#define AVLMEL_TEMPUSE Element, Key, BaseEl, BaseKey, Compare +#define AvlTree AvliMelKey +#define WALKABLE + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef BASELIST +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef WALKABLE + +#endif /* _AAPL_AVLIMELKEY_H */ diff --git a/aapl/avliset.h b/aapl/avliset.h new file mode 100644 index 00000000..cf5be365 --- /dev/null +++ b/aapl/avliset.h @@ -0,0 +1,75 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLISET_H +#define _AAPL_AVLISET_H + +#include "compare.h" +#include "dlist.h" + +/** + * \addtogroup avlitree + * @{ + */ + +/** + * \class AvliSet + * \brief Linked Key-only oriented tree. + * + * AvliSet stores only keys in elements that are managed by the tree. AvliSet + * requires that a Key type and a class containing a compare() routine + * for Key be given. Items are inserted with just a key value. + * + * AvliSet assumes all elements in the tree are allocated on the heap and are + * to be managed by the tree. This means that the class destructor will delete + * the contents of the tree. A deep copy will cause existing elements to be + * deleted first. + * + * \include ex_avliset.cpp + */ + +/*@}*/ + +#define AVLTREE_SET +#define BASE_EL(name) name +#define BASEKEY(name) name +#define BASELIST DList< AvliSetEl<Key> > +#define AVLMEL_CLASSDEF class Key, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Key, class Compare +#define AVLMEL_TEMPUSE Key, Compare +#define AvlTree AvliSet +#define Element AvliSetEl<Key> +#define WALKABLE + +#include "avlcommon.h" + +#undef AVLTREE_SET +#undef BASE_EL +#undef BASEKEY +#undef BASELIST +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef Element +#undef WALKABLE + +#endif /* _AAPL_AVLISET_H */ diff --git a/aapl/avlitree.h b/aapl/avlitree.h new file mode 100644 index 00000000..b053c96f --- /dev/null +++ b/aapl/avlitree.h @@ -0,0 +1,78 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLITREE_H +#define _AAPL_AVLITREE_H + +#include "compare.h" +#include "dlistmel.h" + +/** + * \addtogroup avlitree + * @{ + */ + +/** + * \class AvliTree + * \brief Linked AVL tree. + * + * AvliTree is the standard linked by-structure AVL tree. To use this + * structure the user must define an element type and give it the necessary + * properties. At the very least it must have a getKey() function that will be + * used to compare the relative ordering of elements and tree management data + * necessary for the AVL algorithm. An element type can acquire the management + * data by inheriting the AvliTreeEl class. + * + * AvliTree does not presume to manage the allocation of elements in the tree. + * The destructor will not delete the items in the tree, instead the elements + * must be explicitly de-allocated by the user if necessary and when it is + * safe to do so. The empty() routine will traverse the tree and delete all + * items. + * + * Since the tree does not manage the elements, it can contain elements that + * are allocated statically or that are part of another data structure. + * + * \include ex_avlitree.cpp + */ + +/*@}*/ + +#define BASE_EL(name) name +#define BASEKEY(name) name +#define BASELIST DListMel< Element, AvliTreeEl<Element> > +#define AVLMEL_CLASSDEF class Element, class Key, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Element, class Key, class Compare +#define AVLMEL_TEMPUSE Element, Key, Compare +#define AvlTree AvliTree +#define WALKABLE + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef BASELIST +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef WALKABLE + +#endif /* _AAPL_AVLITREE_H */ diff --git a/aapl/avlkeyless.h b/aapl/avlkeyless.h new file mode 100644 index 00000000..30805136 --- /dev/null +++ b/aapl/avlkeyless.h @@ -0,0 +1,58 @@ +/* + * Copyright 2002, 2003 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLKEYLESS_H +#define _AAPL_AVLKEYLESS_H + +#include "compare.h" + +/** + * \addtogroup avltree + * @{ + */ + +/** + * \class AvlKeyless + * \brief AVL tree that has no insert/find/remove functions that take a key. + * + * AvlKeyless is an implementation of the AVL tree rebalancing functionality + * only. It provides the common code for the tiny AVL tree implementations. + */ + +/*@}*/ + +#define BASE_EL(name) name +#define AVLMEL_CLASSDEF class Element +#define AVLMEL_TEMPDEF class Element +#define AVLMEL_TEMPUSE Element +#define AvlTree AvlKeyless +#define AVL_KEYLESS + +#include "avlcommon.h" + +#undef BASE_EL +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef AVL_KEYLESS + +#endif /* _AAPL_AVLKEYLESS_H */ diff --git a/aapl/avlmap.h b/aapl/avlmap.h new file mode 100644 index 00000000..e4e15662 --- /dev/null +++ b/aapl/avlmap.h @@ -0,0 +1,74 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLMAP_H +#define _AAPL_AVLMAP_H + +#include "compare.h" + +/** + * \addtogroup avltree + * @{ + */ + +/** + * \class AvlMap + * \brief Key and value oriented AVL tree. + * + * AvlMap stores key and value pairs in elements that managed by the tree. It + * is intendend to be similar to map template found in the STL. AvlMap + * requires that a Key type, a Value type, and a class containing a compare() + * routine for Key be given. Items can be inserted with just a key or with a + * key and value pair. + * + * AvlMap assumes all elements in the tree are allocated on the heap and are + * to be managed by the tree. This means that the class destructor will delete + * the contents of the tree. A deep copy will cause existing elements to be + * deleted first. + * + * \include ex_avlmap.cpp + */ + +/*@}*/ + +#define AVLTREE_MAP +#define BASE_EL(name) name +#define BASEKEY(name) name +#define AVLMEL_CLASSDEF class Key, class Value, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Key, class Value, class Compare +#define AVLMEL_TEMPUSE Key, Value, Compare +#define AvlTree AvlMap +#define Element AvlMapEl<Key,Value> + +#include "avlcommon.h" + +#undef AVLTREE_MAP +#undef BASE_EL +#undef BASEKEY +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef Element + + + +#endif /* _AAPL_AVLMAP_H */ diff --git a/aapl/avlmel.h b/aapl/avlmel.h new file mode 100644 index 00000000..7bfad3b7 --- /dev/null +++ b/aapl/avlmel.h @@ -0,0 +1,74 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLMEL_H +#define _AAPL_AVLMEL_H + +#include "compare.h" + +/** + * \addtogroup avltree + * @{ + */ + +/** + * \class AvlMel + * \brief AVL tree for elements appearing in multiple trees. + * + * AvlMel allows for an element to simultaneously be in multiple trees without + * the trees interferring with one another. For each tree that the element is + * to appear in, there must be a distinct set of AVL Tree management data that + * can be unambiguously referenced with some base class name. This name + * is passed to the tree as a template parameter and is used in the tree + * algorithms. + * + * The element must use the same key type and value in each tree that it + * appears in. If distinct keys are required, the AvlMelKey structure is + * available. + * + * AvlMel does not assume ownership of elements in the tree. The destructor + * will not delete the elements. If the user wishes to explicitly deallocate + * all the items in the tree the empty() routine is available. + * + * \include ex_avlmel.cpp + */ + +/*@}*/ + +#define BASE_EL(name) BaseEl::name +#define BASEKEY(name) name +#define AVLMEL_CLASSDEF class Element, class Key, \ + class BaseEl, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Element, class Key, \ + class BaseEl, class Compare +#define AVLMEL_TEMPUSE Element, Key, BaseEl, Compare +#define AvlTree AvlMel + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree + +#endif /* _AAPL_AVLMEL_H */ diff --git a/aapl/avlmelkey.h b/aapl/avlmelkey.h new file mode 100644 index 00000000..9261cc83 --- /dev/null +++ b/aapl/avlmelkey.h @@ -0,0 +1,71 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLMELKEY_H +#define _AAPL_AVLMELKEY_H + +#include "compare.h" + +/** + * \addtogroup avltree + * @{ + */ + +/** + * \class AvlMelKey + * \brief AVL tree for elements appearing in multiple trees with different keys. + * + * AvlMelKey is similar to AvlMel, except that an additional template + * parameter, BaseKey, is provided for resolving ambiguous references to + * getKey(). This means that if an element is stored in multiple trees, each + * tree can use a different key for ordering the elements in it. Using + * AvlMelKey an array of data structures can be indexed with an O(log(n)) + * search on two or more of the values contained within it and without + * allocating any additional data. + * + * AvlMelKey does not assume ownership of elements in the tree. The destructor + * will not delete the elements. If the user wishes to explicitly deallocate + * all the items in the tree the empty() routine is available. + * + * \include ex_avlmelkey.cpp + */ + +/*@}*/ + +#define BASE_EL(name) BaseEl::name +#define BASEKEY(name) BaseKey::name +#define AVLMEL_CLASSDEF class Element, class Key, class BaseEl, \ + class BaseKey, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Element, class Key, class BaseEl, \ + class BaseKey, class Compare +#define AVLMEL_TEMPUSE Element, Key, BaseEl, BaseKey, Compare +#define AvlTree AvlMelKey + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree + +#endif /* _AAPL_AVLMELKEY_H */ diff --git a/aapl/avlset.h b/aapl/avlset.h new file mode 100644 index 00000000..224ee59f --- /dev/null +++ b/aapl/avlset.h @@ -0,0 +1,70 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLSET_H +#define _AAPL_AVLSET_H + +#include "compare.h" + +/** + * \addtogroup avltree + * @{ + */ + +/** + * \class AvlSet + * \brief Key-only oriented tree. + * + * AvlSet stores only keys in elements that are managed by the tree. AvlSet + * requires that a Key type and a class containing a compare() routine + * for Key be given. Items are inserted with just a key value. + * + * AvlSet assumes all elements in the tree are allocated on the heap and are + * to be managed by the tree. This means that the class destructor will delete + * the contents of the tree. A deep copy will cause existing elements to be + * deleted first. + * + * \include ex_avlset.cpp + */ + +/*@}*/ + +#define AVLTREE_SET +#define BASE_EL(name) name +#define BASEKEY(name) name +#define AVLMEL_CLASSDEF class Key, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Key, class Compare +#define AVLMEL_TEMPUSE Key, Compare +#define AvlTree AvlSet +#define Element AvlSetEl<Key> + +#include "avlcommon.h" + +#undef AVLTREE_SET +#undef BASE_EL +#undef BASEKEY +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree +#undef Element + +#endif /* _AAPL_AVLSET_H */ diff --git a/aapl/avltree.h b/aapl/avltree.h new file mode 100644 index 00000000..cf153595 --- /dev/null +++ b/aapl/avltree.h @@ -0,0 +1,73 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_AVLTREE_H +#define _AAPL_AVLTREE_H + +#include "compare.h" + +/** + * \addtogroup avltree + * @{ + */ + +/** + * \class AvlTree + * \brief Basic AVL tree. + * + * AvlTree is the standard by-structure AVL tree. To use this structure the + * user must define an element type and give it the necessary properties. At + * the very least it must have a getKey() function that will be used to + * compare the relative ordering of elements and tree management data + * necessary for the AVL algorithm. An element type can acquire the management + * data by inheriting the AvlTreeEl class. + * + * AvlTree does not presume to manage the allocation of elements in the tree. + * The destructor will not delete the items in the tree, instead the elements + * must be explicitly de-allocated by the user if necessary and when it is + * safe to do so. The empty() routine will traverse the tree and delete all + * items. + * + * Since the tree does not manage the elements, it can contain elements that + * are allocated statically or that are part of another data structure. + * + * \include ex_avltree.cpp + */ + +/*@}*/ + +#define BASE_EL(name) name +#define BASEKEY(name) name +#define AVLMEL_CLASSDEF class Element, class Key, class Compare = CmpOrd<Key> +#define AVLMEL_TEMPDEF class Element, class Key, class Compare +#define AVLMEL_TEMPUSE Element, Key, Compare +#define AvlTree AvlTree + +#include "avlcommon.h" + +#undef BASE_EL +#undef BASEKEY +#undef AVLMEL_CLASSDEF +#undef AVLMEL_TEMPDEF +#undef AVLMEL_TEMPUSE +#undef AvlTree + +#endif /* _AAPL_AVLTREE_H */ diff --git a/aapl/bstcommon.h b/aapl/bstcommon.h new file mode 100644 index 00000000..bd390cdc --- /dev/null +++ b/aapl/bstcommon.h @@ -0,0 +1,814 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* This header is not wrapped in ifndefs because it is + * not intended to be included by users directly. */ + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/* Binary Search Table */ +template < BST_TEMPL_DECLARE > class BstTable : + public Compare, + public Vector< Element, Resize > +{ + typedef Vector<Element, Resize> BaseVector; + typedef Table<Element> BaseTable; + +public: + /** + * \brief Default constructor. + * + * Create an empty binary search table. + */ + BstTable() { } + + /** + * \brief Construct with initial value. + * + * Constructs a binary search table with an initial item. Uses the default + * constructor for initializing Value. + */ + BstTable(const Key &key) + { insert(key); } + +#if defined( BSTMAP ) + /** + * \brief Construct with initial value. + * + * Constructs a binary search table with an initial key/value pair. + */ + BstTable(const Key &key, const Value &val) + { insert(key, val); } +#endif + +#if ! defined( BSTSET ) + /** + * \brief Construct with initial value. + * + * Constructs a binary search table with an initial Element. + */ + BstTable(const Element &el) + { insert(el); } +#endif + + Element *insert(const Key &key, Element **lastFound = 0); + Element *insertMulti(const Key &key); + + bool insert(const BstTable &other); + void insertMulti(const BstTable &other); + +#if defined( BSTMAP ) + Element *insert(const Key &key, const Value &val, + Element **lastFound = 0); + Element *insertMulti(const Key &key, const Value &val ); +#endif + +#if ! defined( BSTSET ) + Element *insert(const Element &el, Element **lastFound = 0); + Element *insertMulti(const Element &el); +#endif + + Element *find(const Key &key, Element **lastFound = 0) const; + bool findMulti( const Key &key, Element *&lower, + Element *&upper ) const; + + bool remove(const Key &key); + bool remove(Element *item); + long removeMulti(const Key &key); + long removeMulti(Element *lower, Element *upper); + + /* The following provide access to the underlying insert and remove + * functions that my be hidden by the BST insert and remove. The insertDup + * and insertNew functions will never be hidden. They are provided for + * consistency. The difference between the non-shared and the shared + * tables is the documentation reference to the invoked function. */ + +#if !defined( SHARED_BST ) + /*@{*/ + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes Vector::insert( long pos, const T &val ). + */ + void vinsert(long pos, const Element &val) + { Vector< Element, Resize >::insert( pos, &val, 1 ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes Vector::insert( long pos, const T *val, long len ). + */ + void vinsert(long pos, const Element *val, long len) + { Vector< Element, Resize >::insert( pos, val, len ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes Vector::insert( long pos, const Vector &v ). + */ + void vinsert(long pos, const BstTable &v) + { Vector< Element, Resize >::insert( pos, v.data, v.tabLen ); } + + /*@}*/ + + /*@{*/ + + /** \brief Call the remove of the underlying vector. + * + * Provides access to the vector remove, which may become hidden. + * Invokes Vector::remove( long pos ). + */ + void vremove(long pos) + { Vector< Element, Resize >::remove( pos, 1 ); } + + /** \brief Call the remove of the underlying vector. + * + * Proves access to the vector remove, which may become hidden. + * Invokes Vector::remove( long pos, long len ). + */ + void vremove(long pos, long len) + { Vector< Element, Resize >::remove( pos, len ); } + + /*@}*/ +#else /* SHARED_BST */ + /*@{*/ + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes SVector::insert( long pos, const T &val ). + */ + void vinsert(long pos, const Element &val) + { Vector< Element, Resize >::insert( pos, &val, 1 ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes SVector::insert( long pos, const T *val, long len ). + */ + void vinsert(long pos, const Element *val, long len) + { Vector< Element, Resize >::insert( pos, val, len ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes SVector::insert( long pos, const SVector &v ). + */ + void vinsert(long pos, const BstTable &v) + { Vector< Element, Resize >::insert( pos, v.data, v.length() ); } + + /*@}*/ + + /*@{*/ + + /** \brief Call the remove of the underlying vector. + * + * Provides access to the vector remove, which may become hidden. + * Invokes SVector::remove( long pos ). + */ + void vremove(long pos) + { Vector< Element, Resize >::remove( pos, 1 ); } + + /** \brief Call the remove of the underlying vector. + * + * Proves access to the vector remove, which may become hidden. + * Invokes SVector::remove( long pos, long len ). + */ + void vremove(long pos, long len) + { Vector< Element, Resize >::remove( pos, len ); } + + /*@}*/ + +#endif /* SHARED_BST */ +}; + + +#if 0 +#if defined( SHARED_BST ) +/** + * \brief Construct a binary search table with an initial amount of + * allocation. + * + * The table is initialized to have room for allocLength elements. The + * table starts empty. + */ +template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>:: + BstTable( long allocLen ) +{ + /* Allocate the space if we are given a positive allocLen. */ + if ( allocLen > 0 ) { + /* Allocate the data needed. */ + STabHead *head = (STabHead*) + malloc( sizeof(STabHead) + sizeof(Element) * allocLen ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Set up the header and save the data pointer. */ + head->refCount = 1; + head->allocLen = allocLen; + head->tabLen = 0; + BaseTable::data = (Element*) (head + 1); + } +} +#else +/** + * \brief Construct a binary search table with an initial amount of + * allocation. + * + * The table is initialized to have room for allocLength elements. The + * table starts empty. + */ +template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>:: + BstTable( long allocLen ) +{ + /* Allocate the space if we are given a positive allocLen. */ + BaseTable::allocLen = allocLen; + if ( BaseTable::allocLen > 0 ) { + BaseTable::data = (Element*) malloc(sizeof(Element) * BaseTable::allocLen); + if ( BaseTable::data == NULL ) + throw std::bad_alloc(); + } +} + +#endif +#endif + +/** + * \brief Find the element with the given key and remove it. + * + * If multiple elements with the given key exist, then it is unspecified which + * element will be removed. + * + * \returns True if an element is found and consequently removed, false + * otherwise. + */ +template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>:: + remove(const Key &key) +{ + Element *el = find(key); + if ( el != 0 ) { + Vector< Element >::remove(el - BaseTable::data); + return true; + } + return false; +} + +/** + * \brief Remove the element pointed to by item. + * + * If item does not point to an element in the tree, then undefined behaviour + * results. If item is null, then remove has no effect. + * + * \returns True if item is not null, false otherwise. + */ +template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>:: + remove( Element *item ) +{ + if ( item != 0 ) { + Vector< Element >::remove(item - BaseTable::data); + return true; + } + return false; +} + +/** + * \brief Find and remove the entire range of elements with the given key. + * + * \returns The number of elements removed. + */ +template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>:: + removeMulti(const Key &key) +{ + Element *low, *high; + if ( findMulti(key, low, high) ) { + /* Get the length of the range. */ + long num = high - low + 1; + Vector< Element >::remove(low - BaseTable::data, num); + return num; + } + + return 0; +} + +template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>:: + removeMulti(Element *lower, Element *upper) +{ + /* Get the length of the range. */ + long num = upper - lower + 1; + Vector< Element >::remove(lower - BaseTable::data, num); + return num; +} + + +/** + * \brief Find a range of elements with the given key. + * + * If any elements with the given key exist then lower and upper are set to + * the low and high ends of the continous range of elements with the key. + * Lower and upper will point to the first and last elements with the key. + * + * \returns True if any elements are found, false otherwise. + */ +template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>:: + findMulti(const Key &key, Element *&low, Element *&high ) const +{ + const Element *lower, *mid, *upper; + long keyRelation; + const long tblLen = BaseTable::length(); + + if ( BaseTable::data == 0 ) + return false; + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the fd in the array. */ + return false; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = compare(key, GET_KEY(*mid)); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + Element *lowEnd = BaseTable::data - 1; + Element *highEnd = BaseTable::data + tblLen; + + lower = mid - 1; + while ( lower != lowEnd && + compare(key, GET_KEY(*lower)) == 0 ) + lower--; + + upper = mid + 1; + while ( upper != highEnd && + compare(key, GET_KEY(*upper)) == 0 ) + upper++; + + low = (Element*)lower + 1; + high = (Element*)upper - 1; + return true; + } + } +} + +/** + * \brief Find an element with the given key. + * + * If the find succeeds then lastFound is set to the element found. If the + * find fails then lastFound is set the location where the key would be + * inserted. If there is more than one element in the tree with the given key, + * then it is unspecified which element is returned as the match. + * + * \returns The element found on success, null on failure. + */ +template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>:: + find( const Key &key, Element **lastFound ) const +{ + const Element *lower, *mid, *upper; + long keyRelation; + const long tblLen = BaseTable::length(); + + if ( BaseTable::data == 0 ) + return 0; + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the key. Last found gets the insert location. */ + if ( lastFound != 0 ) + *lastFound = (Element*)lower; + return 0; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = compare(key, GET_KEY(*mid)); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + /* Key is found. Last found gets the found record. */ + if ( lastFound != 0 ) + *lastFound = (Element*)mid; + return (Element*)mid; + } + } +} + +template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>:: + insert(const Key &key, Element **lastFound) +{ + const Element *lower, *mid, *upper; + long keyRelation, insertPos; + const long tblLen = BaseTable::length(); + + if ( tblLen == 0 ) { + /* If the table is empty then go straight to insert. */ + lower = BaseTable::data; + goto insert; + } + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the key in the array. + * Place to insert at is lower. */ + goto insert; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = compare(key, GET_KEY(*mid)); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + if ( lastFound != 0 ) + *lastFound = (Element*)mid; + return 0; + } + } + +insert: + /* Get the insert pos. */ + insertPos = lower - BaseTable::data; + + /* Do the insert. After makeRawSpaceFor, lower pointer is no good. */ + BaseVector::makeRawSpaceFor(insertPos, 1); + new(BaseTable::data + insertPos) Element(key); + + /* Set lastFound */ + if ( lastFound != 0 ) + *lastFound = BaseTable::data + insertPos; + return BaseTable::data + insertPos; +} + + +template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>:: + insertMulti(const Key &key) +{ + const Element *lower, *mid, *upper; + long keyRelation, insertPos; + const long tblLen = BaseTable::length(); + + if ( tblLen == 0 ) { + /* If the table is empty then go straight to insert. */ + lower = BaseTable::data; + goto insert; + } + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the key in the array. + * Place to insert at is lower. */ + goto insert; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = compare(key, GET_KEY(*mid)); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + lower = mid; + goto insert; + } + } + +insert: + /* Get the insert pos. */ + insertPos = lower - BaseTable::data; + + /* Do the insert. */ + BaseVector::makeRawSpaceFor(insertPos, 1); + new(BaseTable::data + insertPos) Element(key); + + /* Return the element inserted. */ + return BaseTable::data + insertPos; +} + +/** + * \brief Insert each element from other. + * + * Always attempts to insert all elements even if the insert of some item from + * other fails. + * + * \returns True if all items inserted successfully, false if any insert + * failed. + */ +template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>:: + insert(const BstTable &other) +{ + bool allSuccess = true; + long otherLen = other.length(); + for ( long i = 0; i < otherLen; i++ ) { + Element *el = insert( other.data[i] ); + if ( el == 0 ) + allSuccess = false; + } + return allSuccess; +} + +/** + * \brief Insert each element from other even if the elements exist already. + * + * No individual insertMulti can fail. + */ +template <BST_TEMPL_DEF> void BstTable<BST_TEMPL_USE>:: + insertMulti(const BstTable &other) +{ + long otherLen = other.length(); + for ( long i = 0; i < otherLen; i++ ) + insertMulti( other.data[i] ); +} + +#if ! defined( BSTSET ) + +/** + * \brief Insert the given element. + * + * If the key in the given element does not already exist in the table then a + * new element is inserted. They element copy constructor is used to place the + * element into the table. If lastFound is given, it is set to the new element + * created. If the insert fails then lastFound is set to the existing element + * of the same key. + * + * \returns The new element created upon success, null upon failure. + */ +template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>:: + insert(const Element &el, Element **lastFound ) +{ + const Element *lower, *mid, *upper; + long keyRelation, insertPos; + const long tblLen = BaseTable::length(); + + if ( tblLen == 0 ) { + /* If the table is empty then go straight to insert. */ + lower = BaseTable::data; + goto insert; + } + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the key in the array. + * Place to insert at is lower. */ + goto insert; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = compare(GET_KEY(el), GET_KEY(*mid)); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + if ( lastFound != 0 ) + *lastFound = (Element*)mid; + return 0; + } + } + +insert: + /* Get the insert pos. */ + insertPos = lower - BaseTable::data; + + /* Do the insert. After makeRawSpaceFor, lower pointer is no good. */ + BaseVector::makeRawSpaceFor(insertPos, 1); + new(BaseTable::data + insertPos) Element(el); + + /* Set lastFound */ + if ( lastFound != 0 ) + *lastFound = BaseTable::data + insertPos; + return BaseTable::data + insertPos; +} + +/** + * \brief Insert the given element even if it exists already. + * + * If the key in the given element exists already then the new element is + * placed next to some other element of the same key. InsertMulti cannot fail. + * The element copy constructor is used to place the element in the table. + * + * \returns The new element created. + */ +template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>:: + insertMulti(const Element &el) +{ + const Element *lower, *mid, *upper; + long keyRelation, insertPos; + const long tblLen = BaseTable::length(); + + if ( tblLen == 0 ) { + /* If the table is empty then go straight to insert. */ + lower = BaseTable::data; + goto insert; + } + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the fd in the array. + * Place to insert at is lower. */ + goto insert; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = compare(GET_KEY(el), GET_KEY(*mid)); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + lower = mid; + goto insert; + } + } + +insert: + /* Get the insert pos. */ + insertPos = lower - BaseTable::data; + + /* Do the insert. */ + BaseVector::makeRawSpaceFor(insertPos, 1); + new(BaseTable::data + insertPos) Element(el); + + /* Return the element inserted. */ + return BaseTable::data + insertPos; +} +#endif + + +#if defined( BSTMAP ) + +/** + * \brief Insert the given key-value pair. + * + * If the given key does not already exist in the table then the key-value + * pair is inserted. Copy constructors are used to place the pair in the + * table. If lastFound is given, it is set to the new entry created. If the + * insert fails then lastFound is set to the existing pair of the same key. + * + * \returns The new element created upon success, null upon failure. + */ +template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>:: + insert(const Key &key, const Value &val, Element **lastFound) +{ + const Element *lower, *mid, *upper; + long keyRelation, insertPos; + const long tblLen = BaseTable::length(); + + if ( tblLen == 0 ) { + /* If the table is empty then go straight to insert. */ + lower = BaseTable::data; + goto insert; + } + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the fd in the array. + * Place to insert at is lower. */ + goto insert; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = Compare::compare(key, mid->key); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + if ( lastFound != NULL ) + *lastFound = (Element*)mid; + return 0; + } + } + +insert: + /* Get the insert pos. */ + insertPos = lower - BaseTable::data; + + /* Do the insert. */ + BaseVector::makeRawSpaceFor(insertPos, 1); + new(BaseTable::data + insertPos) Element(key, val); + + /* Set lastFound */ + if ( lastFound != NULL ) + *lastFound = BaseTable::data + insertPos; + return BaseTable::data + insertPos; +} + + +/** + * \brief Insert the given key-value pair even if the key exists already. + * + * If the key exists already then the key-value pair is placed next to some + * other pair of the same key. InsertMulti cannot fail. Copy constructors are + * used to place the pair in the table. + * + * \returns The new element created. + */ +template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>:: + insertMulti(const Key &key, const Value &val) +{ + const Element *lower, *mid, *upper; + long keyRelation, insertPos; + const long tblLen = BaseTable::length(); + + if ( tblLen == 0 ) { + /* If the table is empty then go straight to insert. */ + lower = BaseTable::data; + goto insert; + } + + lower = BaseTable::data; + upper = BaseTable::data + tblLen - 1; + while ( true ) { + if ( upper < lower ) { + /* Did not find the key in the array. + * Place to insert at is lower. */ + goto insert; + } + + mid = lower + ((upper-lower)>>1); + keyRelation = Compare::compare(key, mid->key); + + if ( keyRelation < 0 ) + upper = mid - 1; + else if ( keyRelation > 0 ) + lower = mid + 1; + else { + lower = mid; + goto insert; + } + } + +insert: + /* Get the insert pos. */ + insertPos = lower - BaseTable::data; + + /* Do the insert. */ + BaseVector::makeRawSpaceFor(insertPos, 1); + new(BaseTable::data + insertPos) Element(key, val); + + /* Return the element inserted. */ + return BaseTable::data + insertPos; +} + +#endif + +#ifdef AAPL_NAMESPACE +} +#endif diff --git a/aapl/bstmap.h b/aapl/bstmap.h new file mode 100644 index 00000000..5154b86c --- /dev/null +++ b/aapl/bstmap.h @@ -0,0 +1,113 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_BSTMAP_H +#define _AAPL_BSTMAP_H + +#include "compare.h" +#include "vector.h" + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \brief Element for BstMap. + * + * Stores the key and value pair. + */ +template <class Key, class Value> struct BstMapEl +{ + BstMapEl() {} + BstMapEl(const Key &key) : key(key) {} + BstMapEl(const Key &key, const Value &val) : key(key), value(val) {} + + /** \brief The key */ + Key key; + + /** \brief The value. */ + Value value; +}; + +#ifdef AAPL_NAMESPACE +} +#endif + +/** + * \addtogroup bst + * @{ + */ + +/** + * \class BstMap + * \brief Binary search table for key and value pairs. + * + * BstMap stores key and value pairs in each element. The key and value can be + * any type. A compare class for the key must be supplied. + */ + +/*@}*/ + +#define BST_TEMPL_DECLARE class Key, class Value, \ + class Compare = CmpOrd<Key>, class Resize = ResizeExpn +#define BST_TEMPL_DEF class Key, class Value, class Compare, class Resize +#define BST_TEMPL_USE Key, Value, Compare, Resize +#define GET_KEY(el) ((el).key) +#define BstTable BstMap +#define Element BstMapEl<Key, Value> +#define BSTMAP + +#include "bstcommon.h" + +#undef BST_TEMPL_DECLARE +#undef BST_TEMPL_DEF +#undef BST_TEMPL_USE +#undef GET_KEY +#undef BstTable +#undef Element +#undef BSTMAP + +/** + * \fn BstMap::insert(const Key &key, BstMapEl<Key, Value> **lastFound) + * \brief Insert the given key. + * + * If the given key does not already exist in the table then a new element + * having key is inserted. They key copy constructor and value default + * constructor are used to place the pair in the table. If lastFound is given, + * it is set to the new entry created. If the insert fails then lastFound is + * set to the existing pair of the same key. + * + * \returns The new element created upon success, null upon failure. + */ + +/** + * \fn BstMap::insertMulti(const Key &key) + * \brief Insert the given key even if it exists already. + * + * If the key exists already then the new element having key is placed next + * to some other pair of the same key. InsertMulti cannot fail. The key copy + * constructor and the value default constructor are used to place the pair in + * the table. + * + * \returns The new element created. + */ + +#endif /* _AAPL_BSTMAP_H */ diff --git a/aapl/bstset.h b/aapl/bstset.h new file mode 100644 index 00000000..ce710ee0 --- /dev/null +++ b/aapl/bstset.h @@ -0,0 +1,86 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_BSTSET_H +#define _AAPL_BSTSET_H + +/** + * \addtogroup bst + * @{ + */ + +/** + * \class BstSet + * \brief Binary search table for types that are the key. + * + * BstSet is suitable for types that comprise the entire key. Rather than look + * into the element to retrieve the key, the element is the key. A class that + * contains a comparison routine for the key must be given. + */ + +/*@}*/ + +#include "compare.h" +#include "vector.h" + +#define BST_TEMPL_DECLARE class Key, class Compare = CmpOrd<Key>, \ + class Resize = ResizeExpn +#define BST_TEMPL_DEF class Key, class Compare, class Resize +#define BST_TEMPL_USE Key, Compare, Resize +#define GET_KEY(el) (el) +#define BstTable BstSet +#define Element Key +#define BSTSET + +#include "bstcommon.h" + +#undef BST_TEMPL_DECLARE +#undef BST_TEMPL_DEF +#undef BST_TEMPL_USE +#undef GET_KEY +#undef BstTable +#undef Element +#undef BSTSET + +/** + * \fn BstSet::insert(const Key &key, Key **lastFound) + * \brief Insert the given key. + * + * If the given key does not already exist in the table then it is inserted. + * The key's copy constructor is used to place the item in the table. If + * lastFound is given, it is set to the new entry created. If the insert fails + * then lastFound is set to the existing key of the same value. + * + * \returns The new element created upon success, null upon failure. + */ + +/** + * \fn BstSet::insertMulti(const Key &key) + * \brief Insert the given key even if it exists already. + * + * If the key exists already then it is placed next to some other key of the + * same value. InsertMulti cannot fail. The key's copy constructor is used to + * place the item in the table. + * + * \returns The new element created. + */ + +#endif /* _AAPL_BSTSET_H */ diff --git a/aapl/bsttable.h b/aapl/bsttable.h new file mode 100644 index 00000000..9898ebff --- /dev/null +++ b/aapl/bsttable.h @@ -0,0 +1,84 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_BSTTABLE_H +#define _AAPL_BSTTABLE_H + +#include "compare.h" +#include "vector.h" + +/** + * \addtogroup bst + * @{ + */ + +/** + * \class BstTable + * \brief Binary search table for structures that contain a key. + * + * This is the basic binary search table. It can be used to contain a + * structure that has a key and possibly some data. The key should be a member + * of the element class and accessible with getKey(). A class containing the + * compare routine must be supplied. + */ + +/*@}*/ + +#define BST_TEMPL_DECLARE class Element, class Key, \ + class Compare = CmpOrd<Key>, class Resize = ResizeExpn +#define BST_TEMPL_DEF class Element, class Key, class Compare, class Resize +#define BST_TEMPL_USE Element, Key, Compare, Resize +#define GET_KEY(el) ((el).getKey()) +#define BSTTABLE + +#include "bstcommon.h" + +#undef BST_TEMPL_DECLARE +#undef BST_TEMPL_DEF +#undef BST_TEMPL_USE +#undef GET_KEY +#undef BSTTABLE + +/** + * \fn BstTable::insert(const Key &key, Element **lastFound) + * \brief Insert a new element with the given key. + * + * If the given key does not already exist in the table a new element is + * inserted with the given key. A constructor taking only const Key& is used + * to initialize the new element. If lastFound is given, it is set to the new + * element created. If the insert fails then lastFound is set to the existing + * element with the same key. + * + * \returns The new element created upon success, null upon failure. + */ + +/** + * \fn BstTable::insertMulti(const Key &key) + * \brief Insert a new element even if the key exists already. + * + * If the key exists already then the new element is placed next to some + * element with the same key. InsertMulti cannot fail. A constructor taking + * only const Key& is used to initialize the new element. + * + * \returns The new element created. + */ + +#endif /* _AAPL_BSTTABLE_H */ diff --git a/aapl/bubblesort.h b/aapl/bubblesort.h new file mode 100644 index 00000000..20e0f6f4 --- /dev/null +++ b/aapl/bubblesort.h @@ -0,0 +1,94 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_BUBBLESORT_H +#define _AAPL_BUBBLESORT_H + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \addtogroup sort + * @{ + */ + +/** + * \class BubbleSort + * \brief Bubble sort an array of data. + * + * BubbleSort can be used to sort any array of objects of type T provided a + * compare class is given. BubbleSort is in-place. It does not require any + * temporary storage. + * + * Objects are not made aware that they are being moved around in memory. + * Assignment operators, constructors and destructors are never invoked by the + * sort. + * + * BubbleSort runs in O(n^2) time. It is most useful when sorting arrays that + * are nearly sorted. It is best when neighbouring pairs are out of place. + * BubbleSort is a stable sort, meaning that objects with the same key have + * their relative ordering preserved. + */ + +/*@}*/ + +/* BubbleSort. */ +template <class T, class Compare> class BubbleSort + : public Compare +{ +public: + /* Sorting interface routine. */ + void sort(T *data, long len); +}; + + +/** + * \brief Bubble sort an array of data. + */ +template <class T, class Compare> void BubbleSort<T,Compare>:: + sort(T *data, long len) +{ + bool changed = true; + for ( long pass = 1; changed && pass < len; pass ++ ) { + changed = false; + for ( long i = 0; i < len-pass; i++ ) { + /* Do we swap pos with the next one? */ + if ( compare( data[i], data[i+1] ) > 0 ) { + char tmp[sizeof(T)]; + + /* Swap the two items. */ + memcpy( tmp, data+i, sizeof(T) ); + memcpy( data+i, data+i+1, sizeof(T) ); + memcpy( data+i+1, tmp, sizeof(T) ); + + /* Note that we made a change. */ + changed = true; + } + } + } +} + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_BUBBLESORT_H */ diff --git a/aapl/compare.h b/aapl/compare.h new file mode 100644 index 00000000..3d547b51 --- /dev/null +++ b/aapl/compare.h @@ -0,0 +1,273 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_COMPARE_H +#define _AAPL_COMPARE_H + +#include <string.h> +#include "astring.h" +#include "table.h" + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \defgroup compare Compare + * \brief Basic compare clases. + * + * Compare classes are used by data structures that need to know the relative + * ordering of elemets. To become a compare class, a class must imlement a + * routine long compare(const T &key1, const T &key2) that behaves just like + * strcmp. + * + * Compare classes are passed to the template data structure as a template + * parameter and are inherited. In most cases the compare routine will base + * the key comparision only on the two keys and the compare routine can + * therefore be static. Though sometimes it is useful to include data in the + * compare class and use this data in the comparison. For example the compare + * class may contain a pointer to some other data structure to which the + * comparison is delegated. + * + * @{ + */ + +/** + * \brief Compare two null terminated character sequences. + * + * This comparision class is a wrapper for strcmp. + */ +template<class T> struct CmpStrTmpl +{ + /** + * \brief Compare two null terminated string types. + */ + static inline long compare( const char *k1, const char *k2 ) + { return strcmp(k1, k2); } + + static int compare( const StrTmpl<T> &s1, const StrTmpl<T> &s2 ) + { + if ( s1.length() < s2.length() ) + return -1; + else if ( s1.length() > s2.length() ) + return 1; + else + return memcmp( s1.data, s2.data, s1.length() ); + } +}; + +typedef CmpStrTmpl<char> CmpStr; + +/** + * \brief Compare a type for which < and > are implemented. + * + * CmpOrd is suitable for simple types such as integers and pointers that by + * default have the less-than and greater-than operators defined. + */ +template <class T> struct CmpOrd +{ + /** + * \brief Compare two ordinal types. + * + * This compare routine copies its arguements in by value. + */ + static inline long compare(const T k1, const T k2) + { + if (k1 < k2) + return -1; + else if (k1 > k2) + return 1; + else + return 0; + } +}; + +/** + * \brief Compare two tables of type T + * + * Table comparison is useful for keying a data structure on a vector or + * binary search table. T is the element type stored in the table. + * CompareT is the comparison structure used to compare the individual values + * in the table. + */ +template < class T, class CompareT = CmpOrd<T> > struct CmpTable + : public CompareT +{ + /** + * \brief Compare two tables storing type T. + */ + static inline long compare(const Table<T> &t1, const Table<T> &t2) + { + if ( t1.tabLen < t2.tabLen ) + return -1; + else if ( t1.tabLen > t2.tabLen ) + return 1; + else + { + T *i1 = t1.data, *i2 = t2.data; + long len = t1.tabLen, cmpResult; + for ( long pos = 0; pos < len; + pos += 1, i1 += 1, i2 += 1 ) + { + cmpResult = CompareT::compare(*i1, *i2); + if ( cmpResult != 0 ) + return cmpResult; + } + return 0; + } + } +}; + +/** + * \brief Compare two tables of type T -- non-static version. + * + * CmpTableNs is identical to CmpTable, however the compare routine is + * non-static. If the CompareT class contains a non-static compare, then this + * version must be used because a static member cannot invoke a non-static + * member. + * + * Table comparison is useful for keying a data structure on a vector or binary + * search table. T is the element type stored in the table. CompareT + * is the comparison structure used to compare the individual values in the + * table. + */ +template < class T, class CompareT = CmpOrd<T> > struct CmpTableNs + : public CompareT +{ + /** + * \brief Compare two tables storing type T. + */ + inline long compare(const Table<T> &t1, const Table<T> &t2) + { + if ( t1.tabLen < t2.tabLen ) + return -1; + else if ( t1.tabLen > t2.tabLen ) + return 1; + else + { + T *i1 = t1.data, *i2 = t2.data; + long len = t1.tabLen, cmpResult; + for ( long pos = 0; pos < len; + pos += 1, i1 += 1, i2 += 1 ) + { + cmpResult = CompareT::compare(*i1, *i2); + if ( cmpResult != 0 ) + return cmpResult; + } + return 0; + } + } +}; + +/** + * \brief Compare two implicitly shared tables of type T + * + * This table comparison is for data structures based on implicitly + * shared tables. + * + * Table comparison is useful for keying a data structure on a vector or + * binary search table. T is the element type stored in the table. + * CompareT is the comparison structure used to compare the individual values + * in the table. + */ +template < class T, class CompareT = CmpOrd<T> > struct CmpSTable : public CompareT +{ + /** + * \brief Compare two tables storing type T. + */ + static inline long compare(const STable<T> &t1, const STable<T> &t2) + { + long t1Length = t1.length(); + long t2Length = t2.length(); + + /* Compare lengths. */ + if ( t1Length < t2Length ) + return -1; + else if ( t1Length > t2Length ) + return 1; + else { + /* Compare the table data. */ + T *i1 = t1.data, *i2 = t2.data; + for ( long pos = 0; pos < t1Length; + pos += 1, i1 += 1, i2 += 1 ) + { + long cmpResult = CompareT::compare(*i1, *i2); + if ( cmpResult != 0 ) + return cmpResult; + } + return 0; + } + } +}; + +/** + * \brief Compare two implicitly shared tables of type T -- non-static + * version. + * + * This is a non-static table comparison for data structures based on + * implicitly shared tables. If the CompareT class contains a non-static + * compare, then this version must be used because a static member cannot + * invoke a non-static member. + * + * Table comparison is useful for keying a data structure on a vector or + * binary search table. T is the element type stored in the table. + * CompareT is the comparison structure used to compare the individual values + * in the table. + */ +template < class T, class CompareT = CmpOrd<T> > struct CmpSTableNs + : public CompareT +{ + /** + * \brief Compare two tables storing type T. + */ + inline long compare(const STable<T> &t1, const STable<T> &t2) + { + long t1Length = t1.length(); + long t2Length = t2.length(); + + /* Compare lengths. */ + if ( t1Length < t2Length ) + return -1; + else if ( t1Length > t2Length ) + return 1; + else { + /* Compare the table data. */ + T *i1 = t1.data, *i2 = t2.data; + for ( long pos = 0; pos < t1Length; + pos += 1, i1 += 1, i2 += 1 ) + { + long cmpResult = CompareT::compare(*i1, *i2); + if ( cmpResult != 0 ) + return cmpResult; + } + return 0; + } + } +}; + + +/*@}*/ + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_COMPARE_H */ diff --git a/aapl/dlcommon.h b/aapl/dlcommon.h new file mode 100644 index 00000000..5ce9bd30 --- /dev/null +++ b/aapl/dlcommon.h @@ -0,0 +1,790 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* This header is not wrapped in ifndef becuase it is not intended to + * be included by the user. */ + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +#if defined( DOUBLELIST_VALUE ) +/** + * \brief Double list element for DListVal. + * + * DListValEl stores the type T of DListVal by value. + */ +template <class T> struct DListValEl +{ + /** + * \brief Construct a DListValEl with a given value. + * + * The only constructor available initializes the value element. This + * enforces that DListVal elements are never created without having their + * value intialzed by the user. T's copy constructor is used to copy the + * value in. + */ + DListValEl( const T &val ) : value(val) { } + + /** + * \brief Value stored by the list element. + * + * Value is always copied into new list elements using the copy + * constructor. + */ + T value; + + /** + * \brief List previous pointer. + * + * Points to the previous item in the list. If this is the first item in + * the list, then prev is NULL. If this element is not in a list then + * prev is undefined. + */ + DListValEl<T> *prev; + + /** + * \brief List next pointer. + * + * Points to the next item in the list. If this is the list item in the + * list, then next is NULL. If this element is not in a list then next is + * undefined. + */ + DListValEl<T> *next; +}; +#else + +#ifndef __AAPL_DOUBLE_LIST_EL +#define __AAPL_DOUBLE_LIST_EL +/** + * \brief Double list element properties. + * + * This class can be inherited to make a class suitable to be a double list + * element. It simply provides the next and previous pointers. An alternative + * is to put the next and previous pointers in the class directly. + */ +template <class Element> struct DListEl +{ + /** + * \brief List previous pointer. + * + * Points to the previous item in the list. If this is the first item in + * the list, then prev is NULL. If this element is not in a list then + * prev is undefined. + */ + Element *prev; + + /** + * \brief List next pointer. + * + * Points to the next item in the list. If this is the list item in the + * list, then next is NULL. If this element is not in a list then next is + * undefined. + */ + Element *next; +}; +#endif /* __AAPL_DOUBLE_LIST_EL */ + +#endif + +/* Doubly Linked List */ +template <DLMEL_TEMPDEF> class DList +{ +public: + /** \brief Initialize an empty list. */ + DList() : head(0), tail(0), listLen(0) {} + + /** + * \brief Perform a deep copy of the list. + * + * The elements of the other list are duplicated and put into this list. + * Elements are copied using the copy constructor. + */ + DList(const DList &other); + +#ifdef DOUBLELIST_VALUE + /** + * \brief Clear the double list contents. + * + * All elements are deleted. + */ + ~DList() { empty(); } + + /** + * \brief Assign another list into this list using a deep copy. + * + * The elements of the other list are duplicated and put into this list. + * Each list item is created using the copy constructor. If this list + * contains any elements before the copy, they are deleted first. + * + * \returns A reference to this. + */ + DList &operator=(const DList &other); + + /** + * \brief Transfer the contents of another list into this list. + * + * The elements of the other list moved in. The other list will be empty + * afterwards. If this list contains any elements before the copy, then + * they are deleted. + */ + void transfer(DList &other); +#else + /** + * \brief Abandon all elements in the list. + * + * List elements are not deleted. + */ + ~DList() {} + + /** + * \brief Perform a deep copy of the list. + * + * The elements of the other list are duplicated and put into this list. + * Each list item is created using the copy constructor. If this list + * contains any elements before the copy, they are abandoned. + * + * \returns A reference to this. + */ + DList &operator=(const DList &other); + + /** + * \brief Transfer the contents of another list into this list. + * + * The elements of the other list moved in. The other list will be empty + * afterwards. If this list contains any elements before the copy, they + * are abandoned. + */ + void transfer(DList &other); +#endif + + +#ifdef DOUBLELIST_VALUE + /** + * \brief Make a new element and prepend it to the front of the list. + * + * The item is copied into the new element using the copy constructor. + * Equivalent to list.addBefore(list.head, item). + */ + void prepend(const T &item); + + /** + * \brief Make a new element and append it to the end of the list. + * + * The item is copied into the new element using the copy constructor. + * Equivalent to list.addAfter(list.tail, item). + */ + void append(const T &item); + + /** + * \brief Make a new element and insert it immediately after an element in + * the list. + * + * The item is copied into the new element using the copy constructor. If + * prev_el is NULL then the new element is prepended to the front of the + * list. If prev_el is not already in the list then undefined behaviour + * results. Equivalent to list.addAfter(prev_el, new DListValEl(item)). + */ + void addAfter(Element *prev_el, const T &item); + + /** + * \brief Make a new element and insert it immediately before an element + * in the list. + * + * The item is copied into the new element using the copy construcotor. If + * next_el is NULL then the new element is appended to the end of the + * list. If next_el is not already in the list then undefined behaviour + * results. Equivalent to list.addBefore(next_el, new DListValEl(item)). + */ + void addBefore(Element *next_el, const T &item); +#endif + + /** + * \brief Prepend a single element to the front of the list. + * + * If new_el is already an element of some list, then undefined behaviour + * results. Equivalent to list.addBefore(list.head, new_el). + */ + void prepend(Element *new_el) { addBefore(head, new_el); } + + /** + * \brief Append a single element to the end of the list. + * + * If new_el is alreay an element of some list, then undefined behaviour + * results. Equivalent to list.addAfter(list.tail, new_el). + */ + void append(Element *new_el) { addAfter(tail, new_el); } + + /** + * \brief Prepend an entire list to the beginning of this list. + * + * All items are moved, not copied. Afterwards, the other list is emtpy. + * All items are prepended at once, so this is an O(1) operation. + * Equivalent to list.addBefore(list.head, dl). + */ + void prepend(DList &dl) { addBefore(head, dl); } + + /** + * \brief Append an entire list to the end of the list. + * + * All items are moved, not copied. Afterwards, the other list is empty. + * All items are appened at once, so this is an O(1) operation. + * Equivalent to list.addAfter(list.tail, dl). + */ + void append(DList &dl) { addAfter(tail, dl); } + + void addAfter(Element *prev_el, Element *new_el); + void addBefore(Element *next_el, Element *new_el); + + void addAfter(Element *prev_el, DList &dl); + void addBefore(Element *next_el, DList &dl); + + /** + * \brief Detach the head of the list + * + * The element detached is not deleted. If there is no head of the list + * (the list is empty) then undefined behaviour results. Equivalent to + * list.detach(list.head). + * + * \returns The element detached. + */ + Element *detachFirst() { return detach(head); } + + /** + * \brief Detach the tail of the list + * + * The element detached is not deleted. If there is no tail of the list + * (the list is empty) then undefined behaviour results. Equivalent to + * list.detach(list.tail). + * + * \returns The element detached. + */ + Element *detachLast() { return detach(tail); } + + /* Detaches an element from the list. Does not free any memory. */ + Element *detach(Element *el); + + /** + * \brief Detach and delete the first element in the list. + * + * If there is no first element (the list is empty) then undefined + * behaviour results. Equivalent to delete list.detach(list.head); + */ + void removeFirst() { delete detach( head ); } + + /** + * \brief Detach and delete the last element in the list. + * + * If there is no last element (the list is emtpy) then undefined + * behaviour results. Equivalent to delete list.detach(list.tail); + */ + void removeLast() { delete detach( tail ); } + + /** + * \brief Detach and delete an element from the list. + * + * If the element is not in the list, then undefined behaviour results. + * Equivalent to delete list.detach(el); + */ + void remove(Element *el) { delete detach( el ); } + + void empty(); + void abandon(); + + /** \brief The number of elements in the list. */ + long length() const { return listLen; } + + /** \brief Head and tail of the linked list. */ + Element *head, *tail; + + /** \brief The number of element in the list. */ + long listLen; + + /* Convenience access. */ + long size() const { return listLen; } + + /* Forward this so a ref can be used. */ + struct Iter; + + /* Class for setting the iterator. */ + struct IterFirst { IterFirst( const DList &l ) : l(l) { } const DList &l; }; + struct IterLast { IterLast( const DList &l ) : l(l) { } const DList &l; }; + struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; }; + struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; }; + + /** + * \brief Double List Iterator. + * \ingroup iterators + */ + struct Iter + { + /* Default construct. */ + Iter() : ptr(0) { } + + /* Construct from a double list. */ + Iter( const DList &dl ) : ptr(dl.head) { } + Iter( Element *el ) : ptr(el) { } + Iter( const IterFirst &dlf ) : ptr(dlf.l.head) { } + Iter( const IterLast &dll ) : ptr(dll.l.tail) { } + Iter( const IterNext &dln ) : ptr(dln.i.ptr->BASE_EL(next)) { } + Iter( const IterPrev &dlp ) : ptr(dlp.i.ptr->BASE_EL(prev)) { } + + /* Assign from a double list. */ + Iter &operator=( const DList &dl ) { ptr = dl.head; return *this; } + Iter &operator=( Element *el ) { ptr = el; return *this; } + Iter &operator=( const IterFirst &af ) { ptr = af.l.head; return *this; } + Iter &operator=( const IterLast &al ) { ptr = al.l.tail; return *this; } + Iter &operator=( const IterNext &an ) { ptr = an.i.ptr->BASE_EL(next); return *this; } + Iter &operator=( const IterPrev &ap ) { ptr = ap.i.ptr->BASE_EL(prev); return *this; } + + /** \brief Less than end? */ + bool lte() const { return ptr != 0; } + + /** \brief At end? */ + bool end() const { return ptr == 0; } + + /** \brief Greater than beginning? */ + bool gtb() const { return ptr != 0; } + + /** \brief At beginning? */ + bool beg() const { return ptr == 0; } + + /** \brief At first element? */ + bool first() const { return ptr && ptr->BASE_EL(prev) == 0; } + + /** \brief At last element? */ + bool last() const { return ptr && ptr->BASE_EL(next) == 0; } + + /** \brief Implicit cast to Element*. */ + operator Element*() const { return ptr; } + + /** \brief Dereference operator returns Element&. */ + Element &operator *() const { return *ptr; } + + /** \brief Arrow operator returns Element*. */ + Element *operator->() const { return ptr; } + + /** \brief Move to next item. */ + inline Element *operator++() { return ptr = ptr->BASE_EL(next); } + + /** \brief Move to next item. */ + inline Element *increment() { return ptr = ptr->BASE_EL(next); } + + /** \brief Move to next item. */ + inline Element *operator++(int); + + /** \brief Move to previous item. */ + inline Element *operator--() { return ptr = ptr->BASE_EL(prev); } + + /** \brief Move to previous item. */ + inline Element *decrement() { return ptr = ptr->BASE_EL(prev); } + + /** \brief Move to previous item. */ + inline Element *operator--(int); + + /** \brief Return the next item. Does not modify this. */ + inline IterNext next() const { return IterNext(*this); } + + /** \brief Return the prev item. Does not modify this. */ + inline IterPrev prev() const { return IterPrev(*this); } + + /** \brief The iterator is simply a pointer. */ + Element *ptr; + }; + + /** \brief Return first element. */ + IterFirst first() { return IterFirst(*this); } + + /** \brief Return last element. */ + IterLast last() { return IterLast(*this); } +}; + +/* Copy constructor, does a deep copy of other. */ +template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE>:: + DList(const DList<DLMEL_TEMPUSE> &other) : + head(0), tail(0), listLen(0) +{ + Element *el = other.head; + while( el != 0 ) { + append( new Element(*el) ); + el = el->BASE_EL(next); + } +} + +#ifdef DOUBLELIST_VALUE + +/* Assignement operator does deep copy. */ +template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>:: + operator=(const DList &other) +{ + /* Free the old list. The value list assumes items were allocated on the + * heap by itself. */ + empty(); + + Element *el = other.head; + while( el != 0 ) { + append( new Element(*el) ); + el = el->BASE_EL(next); + } + return *this; +} + +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + transfer(DList &other) +{ + /* Free the old list. The value list assumes items were allocated on the + * heap by itself. */ + empty(); + + head = other.head; + tail = other.tail; + listLen = other.listLen; + + other.abandon(); +} + +#else + +/* Assignement operator does deep copy. */ +template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>:: + operator=(const DList &other) +{ + Element *el = other.head; + while( el != 0 ) { + append( new Element(*el) ); + el = el->BASE_EL(next); + } + return *this; +} + +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + transfer(DList &other) +{ + head = other.head; + tail = other.tail; + listLen = other.listLen; + + other.abandon(); +} + +#endif + +#ifdef DOUBLELIST_VALUE + +/* Prepend a new item. Inlining this bloats the caller with new overhead. */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + prepend(const T &item) +{ + addBefore(head, new Element(item)); +} + +/* Append a new item. Inlining this bloats the caller with the new overhead. */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + append(const T &item) +{ + addAfter(tail, new Element(item)); +} + +/* Add a new item after a prev element. Inlining this bloats the caller with + * the new overhead. */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + addAfter(Element *prev_el, const T &item) +{ + addAfter(prev_el, new Element(item)); +} + +/* Add a new item before a next element. Inlining this bloats the caller with + * the new overhead. */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + addBefore(Element *next_el, const T &item) +{ + addBefore(next_el, new Element(item)); +} + +#endif + +/* + * The larger iterator operators. + */ + +/* Postfix ++ */ +template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter:: + operator++(int) +{ + Element *rtn = ptr; + ptr = ptr->BASE_EL(next); + return rtn; +} + +/* Postfix -- */ +template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter:: + operator--(int) +{ + Element *rtn = ptr; + ptr = ptr->BASE_EL(prev); + return rtn; +} + +/** + * \brief Insert an element immediately after an element in the list. + * + * If prev_el is NULL then new_el is prepended to the front of the list. If + * prev_el is not in the list or if new_el is already in a list, then + * undefined behaviour results. + */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + addAfter(Element *prev_el, Element *new_el) +{ + /* Set the previous pointer of new_el to prev_el. We do + * this regardless of the state of the list. */ + new_el->BASE_EL(prev) = prev_el; + + /* Set forward pointers. */ + if (prev_el == 0) { + /* There was no prev_el, we are inserting at the head. */ + new_el->BASE_EL(next) = head; + head = new_el; + } + else { + /* There was a prev_el, we can access previous next. */ + new_el->BASE_EL(next) = prev_el->BASE_EL(next); + prev_el->BASE_EL(next) = new_el; + } + + /* Set reverse pointers. */ + if (new_el->BASE_EL(next) == 0) { + /* There is no next element. Set the tail pointer. */ + tail = new_el; + } + else { + /* There is a next element. Set it's prev pointer. */ + new_el->BASE_EL(next)->BASE_EL(prev) = new_el; + } + + /* Update list length. */ + listLen++; +} + +/** + * \brief Insert an element immediatly before an element in the list. + * + * If next_el is NULL then new_el is appended to the end of the list. If + * next_el is not in the list or if new_el is already in a list, then + * undefined behaviour results. + */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + addBefore(Element *next_el, Element *new_el) +{ + /* Set the next pointer of the new element to next_el. We do + * this regardless of the state of the list. */ + new_el->BASE_EL(next) = next_el; + + /* Set reverse pointers. */ + if (next_el == 0) { + /* There is no next elememnt. We are inserting at the tail. */ + new_el->BASE_EL(prev) = tail; + tail = new_el; + } + else { + /* There is a next element and we can access next's previous. */ + new_el->BASE_EL(prev) = next_el->BASE_EL(prev); + next_el->BASE_EL(prev) = new_el; + } + + /* Set forward pointers. */ + if (new_el->BASE_EL(prev) == 0) { + /* There is no previous element. Set the head pointer.*/ + head = new_el; + } + else { + /* There is a previous element, set it's next pointer to new_el. */ + new_el->BASE_EL(prev)->BASE_EL(next) = new_el; + } + + /* Update list length. */ + listLen++; +} + +/** + * \brief Insert an entire list immediatly after an element in this list. + * + * Elements are moved, not copied. Afterwards, the other list is empty. If + * prev_el is NULL then the elements are prepended to the front of the list. + * If prev_el is not in the list then undefined behaviour results. All + * elements are inserted into the list at once, so this is an O(1) operation. + */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + addAfter( Element *prev_el, DList<DLMEL_TEMPUSE> &dl ) +{ + /* Do not bother if dl has no elements. */ + if ( dl.listLen == 0 ) + return; + + /* Set the previous pointer of dl.head to prev_el. We do + * this regardless of the state of the list. */ + dl.head->BASE_EL(prev) = prev_el; + + /* Set forward pointers. */ + if (prev_el == 0) { + /* There was no prev_el, we are inserting at the head. */ + dl.tail->BASE_EL(next) = head; + head = dl.head; + } + else { + /* There was a prev_el, we can access previous next. */ + dl.tail->BASE_EL(next) = prev_el->BASE_EL(next); + prev_el->BASE_EL(next) = dl.head; + } + + /* Set reverse pointers. */ + if (dl.tail->BASE_EL(next) == 0) { + /* There is no next element. Set the tail pointer. */ + tail = dl.tail; + } + else { + /* There is a next element. Set it's prev pointer. */ + dl.tail->BASE_EL(next)->BASE_EL(prev) = dl.tail; + } + + /* Update the list length. */ + listLen += dl.listLen; + + /* Empty out dl. */ + dl.head = dl.tail = 0; + dl.listLen = 0; +} + +/** + * \brief Insert an entire list immediately before an element in this list. + * + * Elements are moved, not copied. Afterwards, the other list is empty. If + * next_el is NULL then the elements are appended to the end of the list. If + * next_el is not in the list then undefined behaviour results. All elements + * are inserted at once, so this is an O(1) operation. + */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + addBefore( Element *next_el, DList<DLMEL_TEMPUSE> &dl ) +{ + /* Do not bother if dl has no elements. */ + if ( dl.listLen == 0 ) + return; + + /* Set the next pointer of dl.tail to next_el. We do + * this regardless of the state of the list. */ + dl.tail->BASE_EL(next) = next_el; + + /* Set reverse pointers. */ + if (next_el == 0) { + /* There is no next elememnt. We are inserting at the tail. */ + dl.head->BASE_EL(prev) = tail; + tail = dl.tail; + } + else { + /* There is a next element and we can access next's previous. */ + dl.head->BASE_EL(prev) = next_el->BASE_EL(prev); + next_el->BASE_EL(prev) = dl.tail; + } + + /* Set forward pointers. */ + if (dl.head->BASE_EL(prev) == 0) { + /* There is no previous element. Set the head pointer.*/ + head = dl.head; + } + else { + /* There is a previous element, set it's next pointer to new_el. */ + dl.head->BASE_EL(prev)->BASE_EL(next) = dl.head; + } + + /* Update list length. */ + listLen += dl.listLen; + + /* Empty out dl. */ + dl.head = dl.tail = 0; + dl.listLen = 0; +} + + +/** + * \brief Detach an element from the list. + * + * The element is not deleted. If the element is not in the list, then + * undefined behaviour results. + * + * \returns The element detached. + */ +template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>:: + detach(Element *el) +{ + /* Set forward pointers to skip over el. */ + if (el->BASE_EL(prev) == 0) + head = el->BASE_EL(next); + else { + el->BASE_EL(prev)->BASE_EL(next) = + el->BASE_EL(next); + } + + /* Set reverse pointers to skip over el. */ + if (el->BASE_EL(next) == 0) + tail = el->BASE_EL(prev); + else { + el->BASE_EL(next)->BASE_EL(prev) = + el->BASE_EL(prev); + } + + /* Update List length and return element we detached. */ + listLen--; + return el; +} + +/** + * \brief Clear the list by deleting all elements. + * + * Each item in the list is deleted. The list is reset to its initial state. + */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::empty() +{ + Element *nextToGo = 0, *cur = head; + + while (cur != 0) + { + nextToGo = cur->BASE_EL(next); + delete cur; + cur = nextToGo; + } + head = tail = 0; + listLen = 0; +} + +/** + * \brief Clear the list by forgetting all elements. + * + * All elements are abandoned, not deleted. The list is reset to it's initial + * state. + */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::abandon() +{ + head = tail = 0; + listLen = 0; +} + +#ifdef AAPL_NAMESPACE +} +#endif diff --git a/aapl/dlist.h b/aapl/dlist.h new file mode 100644 index 00000000..eaf3e5d5 --- /dev/null +++ b/aapl/dlist.h @@ -0,0 +1,64 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_DLIST_H +#define _AAPL_DLIST_H + +#define BASE_EL(name) name +#define DLMEL_TEMPDEF class Element +#define DLMEL_TEMPUSE Element +#define DList DList + +/** + * \addtogroup dlist + * @{ + */ + +/** + * \class DList + * \brief Basic doubly linked list. + * + * DList is the standard by-structure list type. This class requires the + * programmer to declare a list element type that has the necessary next and + * previous pointers in it. This can be achieved by inheriting from the + * DListEl class or by simply adding next and previous pointers directly into + * the list element class. + * + * DList does not assume ownership of elements in the list. If the elements + * are known to reside on the heap, the provided empty() routine can be used to + * delete all elements, however the destructor will not call this routine, it + * will simply abandon all the elements. It is up to the programmer to + * explicitly de-allocate items when necessary. + * + * \include ex_dlist.cpp + */ + +/*@}*/ + +#include "dlcommon.h" + +#undef BASE_EL +#undef DLMEL_TEMPDEF +#undef DLMEL_TEMPUSE +#undef DList + +#endif /* _AAPL_DLIST_H */ + diff --git a/aapl/dlistmel.h b/aapl/dlistmel.h new file mode 100644 index 00000000..34331393 --- /dev/null +++ b/aapl/dlistmel.h @@ -0,0 +1,71 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_DLISTMEL_H +#define _AAPL_DLISTMEL_H + +/** + * \addtogroup dlist + * @{ + */ + +/** + * \class DListMel + * \brief Doubly linked list for elements that may appear in multiple lists. + * + * This class is similar to DList, except that the user defined list element + * can inherit from multple DListEl classes and consequently be an element in + * multiple lists. In other words, DListMel allows a single instance of a data + * structure to be an element in multiple lists without the lists interfereing + * with one another. + * + * For each list that an element class is to appear in, the element must have + * unique next and previous pointers that can be unambiguously refered to with + * some base class name. This name is given to DListMel as a template argument + * so it can use the correct next and previous pointers in its list + * operations. + * + * DListMel does not assume ownership of elements in the list. If the elements + * are known to reside on the heap and are not contained in any other list or + * data structure, the provided empty() routine can be used to delete all + * elements, however the destructor will not call this routine, it will simply + * abandon all the elements. It is up to the programmer to explicitly + * de-allocate items when it is safe to do so. + * + * \include ex_dlistmel.cpp + */ + +/*@}*/ + +#define BASE_EL(name) BaseEl::name +#define DLMEL_TEMPDEF class Element, class BaseEl +#define DLMEL_TEMPUSE Element, BaseEl +#define DList DListMel + +#include "dlcommon.h" + +#undef BASE_EL +#undef DLMEL_TEMPDEF +#undef DLMEL_TEMPUSE +#undef DList + +#endif /* _AAPL_DLISTMEL_H */ + diff --git a/aapl/dlistval.h b/aapl/dlistval.h new file mode 100644 index 00000000..6f249995 --- /dev/null +++ b/aapl/dlistval.h @@ -0,0 +1,71 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_DLISTVAL_H +#define _AAPL_DLISTVAL_H + +/** + * \addtogroup dlist + * @{ + */ + +/** + * \class DListVal + * \brief By-value doubly linked list. + * + * This class is a doubly linked list that does not require a list element + * type to be declared. The user instead gives a type that is to be stored in + * the list element. When inserting a new data item, the value is copied into + * a newly allocated element. This list is inteded to behave and be utilized + * like the list template found in the STL. + * + * DListVal is different from the other lists in that it allocates elements + * itself. The raw element insert interface is still exposed for convenience, + * however, the list assumes all elements in the list are allocated on the + * heap and are to be managed by the list. The destructor WILL delete the + * contents of the list. If the list is ever copied in from another list, the + * existing contents are deleted first. This is in contrast to DList and + * DListMel, which will never delete their contents to allow for statically + * allocated elements. + * + * \include ex_dlistval.cpp + */ + +/*@}*/ + +#define BASE_EL(name) name +#define DLMEL_TEMPDEF class T +#define DLMEL_TEMPUSE T +#define DList DListVal +#define Element DListValEl<T> +#define DOUBLELIST_VALUE + +#include "dlcommon.h" + +#undef BASE_EL +#undef DLMEL_TEMPDEF +#undef DLMEL_TEMPUSE +#undef DList +#undef Element +#undef DOUBLELIST_VALUE + +#endif /* _AAPL_DLISTVAL_H */ + diff --git a/aapl/insertsort.h b/aapl/insertsort.h new file mode 100644 index 00000000..eb3e2649 --- /dev/null +++ b/aapl/insertsort.h @@ -0,0 +1,94 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_INSERTSORT_H +#define _AAPL_INSERTSORT_H + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \addtogroup sort + * @{ + */ + +/** + * \class InsertSort + * \brief Insertion sort an array of data. + * + * InsertSort can be used to sort any array of objects of type T provided a + * compare class is given. InsertSort is in-place. It does not require any + * temporary storage. + * + * Objects are not made aware that they are being moved around in memory. + * Assignment operators, constructors and destructors are never invoked by the + * sort. + * + * InsertSort runs in O(n^2) time. It is most useful when sorting small arrays. + * where it can outperform the O(n*log(n)) sorters due to its simplicity. + * InsertSort is a not a stable sort. Elements with the same key will not have + * their relative ordering preserved. + */ + +/*@}*/ + +/* InsertSort. */ +template <class T, class Compare> class InsertSort + : public Compare +{ +public: + /* Sorting interface routine. */ + void sort(T *data, long len); +}; + + +/** + * \brief Insertion sort an array of data. + */ +template <class T, class Compare> + void InsertSort<T,Compare>::sort(T *data, long len) +{ + /* For each next largest spot in the sorted array... */ + for ( T *dest = data; dest < data+len-1; dest++ ) { + /* Find the next smallest element in the unsorted array. */ + T *smallest = dest; + for ( T *src = dest+1; src < data+len; src++ ) { + /* If src is smaller than the current src, then use it. */ + if ( compare( *src, *smallest ) < 0 ) + smallest = src; + } + + if ( smallest != dest ) { + /* Swap dest, smallest. */ + char tmp[sizeof(T)]; + memcpy( tmp, dest, sizeof(T) ); + memcpy( dest, smallest, sizeof(T) ); + memcpy( smallest, tmp, sizeof(T) ); + } + } +} + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_INSERTSORT_H */ diff --git a/aapl/mergesort.h b/aapl/mergesort.h new file mode 100644 index 00000000..d017511f --- /dev/null +++ b/aapl/mergesort.h @@ -0,0 +1,140 @@ +/* + * Copyright 2001, 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_MERGESORT_H +#define _AAPL_MERGESORT_H + +#include "bubblesort.h" + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \addtogroup sort + * @{ + */ + +/** + * \class MergeSort + * \brief Merge sort an array of data. + * + * MergeSort can be used to sort any array of objects of type T provided a + * compare class is given. MergeSort is not in-place, it requires temporary + * storage equal to the size of the array. The temporary storage is allocated + * on the heap. + * + * Objects are not made aware that they are being moved around in memory. + * Assignment operators, constructors and destructors are never invoked by the + * sort. + * + * MergeSort runs in worst case O(n*log(n)) time. In most cases it is slower + * than QuickSort because more copying is neccessary. But on the other hand, + * it is a stable sort, meaning that objects with the same key have their + * relative ordering preserved. Also, its worst case is better. MergeSort + * switches to a BubbleSort when the size of the array being sorted is small. + * This happens when directly sorting a small array or when MergeSort calls + * itself recursively on a small portion of a larger array. + */ + +/*@}*/ + + +/* MergeSort. */ +template <class T, class Compare> class MergeSort + : public BubbleSort<T, Compare> +{ +public: + /* Sorting interface routine. */ + void sort(T *data, long len); + +private: + /* Recursive worker. */ + void doSort(T *tmpStor, T *data, long len); +}; + +#define _MS_BUBBLE_THRESH 16 + +/* Recursive mergesort worker. Split data, make recursive calls, merge + * results. */ +template< class T, class Compare> void MergeSort<T,Compare>:: + doSort(T *tmpStor, T *data, long len) +{ + if ( len <= 1 ) + return; + + if ( len <= _MS_BUBBLE_THRESH ) { + BubbleSort<T, Compare>::sort( data, len ); + return; + } + + long mid = len / 2; + + doSort( tmpStor, data, mid ); + doSort( tmpStor + mid, data + mid, len - mid ); + + /* Merge the data. */ + T *endLower = data + mid, *lower = data; + T *endUpper = data + len, *upper = data + mid; + T *dest = tmpStor; + while ( true ) { + if ( lower == endLower ) { + /* Possibly upper left. */ + if ( upper != endUpper ) + memcpy( dest, upper, (endUpper - upper) * sizeof(T) ); + break; + } + else if ( upper == endUpper ) { + /* Only lower left. */ + if ( lower != endLower ) + memcpy( dest, lower, (endLower - lower) * sizeof(T) ); + break; + } + else { + /* Both upper and lower left. */ + if ( compare(*lower, *upper) <= 0 ) + memcpy( dest++, lower++, sizeof(T) ); + else + memcpy( dest++, upper++, sizeof(T) ); + } + } + + /* Copy back from the tmpStor array. */ + memcpy( data, tmpStor, sizeof( T ) * len ); +} + +/** + * \brief Merge sort an array of data. + */ +template< class T, class Compare> + void MergeSort<T,Compare>::sort(T *data, long len) +{ + /* Allocate the tmp space needed by merge sort, sort and free. */ + T *tmpStor = (T*) new char[sizeof(T) * len]; + doSort( tmpStor, data, len ); + delete[] (char*) tmpStor; +} + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_MERGESORT_H */ diff --git a/aapl/quicksort.h b/aapl/quicksort.h new file mode 100644 index 00000000..9bb96efd --- /dev/null +++ b/aapl/quicksort.h @@ -0,0 +1,185 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_QUICKSORT_H +#define _AAPL_QUICKSORT_H + +#include "insertsort.h" + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \addtogroup sort + * @{ + */ + +/** + * \class QuickSort + * \brief Quick sort an array of data. + * + * QuickSort can be used to sort any array of objects of type T provided a + * compare class is given. QuickSort is in-place. It does not require any + * temporary storage. + * + * Objects are not made aware that they are being moved around in memory. + * Assignment operators, constructors and destructors are never invoked by the + * sort. + * + * QuickSort runs in O(n*log(n)) time in the average case. It is faster than + * mergsort in the average case because it does less moving of data. The + * performance of quicksort depends mostly on the choice of pivot. This + * implementation picks the pivot as the median of first, middle, last. This + * choice of pivot avoids the O(n^2) worst case for input already sorted, but + * it is still possible to encounter the O(n^2) worst case. For example an + * array of identical elements will run in O(n^2) + * + * QuickSort is not a stable sort. Elements with the same key will not have + * their relative ordering preserved. QuickSort switches to an InsertSort + * when the size of the array being sorted is small. This happens when + * directly sorting a small array or when QuickSort calls iteself recursively + * on a small portion of a larger array. + */ + +/*@}*/ + +/* QuickSort. */ +template <class T, class Compare> class QuickSort : + public InsertSort<T, Compare> +{ +public: + /* Sorting interface routine. */ + void sort(T *data, long len); + +private: + /* Recursive worker. */ + void doSort(T *start, T *end); + T *partition(T *start, T *end); + inline T *median(T *start, T *end); +}; + +#define _QS_INSERTION_THRESH 16 + +/* Finds the median of start, middle, end. */ +template <class T, class Compare> T *QuickSort<T,Compare>:: + median(T *start, T *end) +{ + T *pivot, *mid = start + (end-start)/2; + + /* CChoose the pivot. */ + if ( compare(*start, *mid) < 0 ) { + if ( compare(*mid, *end) < 0 ) + pivot = mid; + else if ( compare(*start, *end) < 0 ) + pivot = end; + else + pivot = start; + } + else if ( compare(*start, *end) < 0 ) + pivot = start; + else if ( compare(*mid, *end) < 0 ) + pivot = end; + else + pivot = mid; + + return pivot; +} + +template <class T, class Compare> T *QuickSort<T,Compare>:: + partition(T *start, T *end) +{ + /* Use the median of start, middle, end as the pivot. First save + * it off then move the last element to the free spot. */ + char pcPivot[sizeof(T)]; + T *pivot = median(start, end); + + memcpy( pcPivot, pivot, sizeof(T) ); + if ( pivot != end ) + memcpy( pivot, end, sizeof(T) ); + + T *first = start-1; + T *last = end; + pivot = (T*) pcPivot; + + /* Shuffle element to the correct side of the pivot, ending + * up with the free spot where the pivot will go. */ + while ( true ) { + /* Throw one element ahead to the free spot at last. */ + while ( true ) { + first += 1; + if ( first == last ) + goto done; + if ( compare( *first, *pivot ) > 0 ) { + memcpy(last, first, sizeof(T)); + break; + } + } + + /* Throw one element back to the free spot at first. */ + while ( true ) { + last -= 1; + if ( last == first ) + goto done; + if ( compare( *last, *pivot ) < 0 ) { + memcpy(first, last, sizeof(T)); + break; + } + } + } +done: + /* Put the pivot into the middle spot for it. */ + memcpy( first, pivot, sizeof(T) ); + return first; +} + + +template< class T, class Compare> void QuickSort<T,Compare>:: + doSort(T *start, T *end) +{ + long len = end - start + 1; + if ( len > _QS_INSERTION_THRESH ) { + /* Use quicksort. */ + T *pivot = partition( start, end ); + doSort(start, pivot-1); + doSort(pivot+1, end); + } + else if ( len > 1 ) { + /* Array is small, use insertion sort. */ + InsertSort<T, Compare>::sort( start, len ); + } +} + +/** + * \brief Quick sort an array of data. + */ +template< class T, class Compare> + void QuickSort<T,Compare>::sort(T *data, long len) +{ + /* Call recursive worker. */ + doSort(data, data+len-1); +} + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_QUICKSORT_H */ diff --git a/aapl/resize.h b/aapl/resize.h new file mode 100644 index 00000000..24edc16e --- /dev/null +++ b/aapl/resize.h @@ -0,0 +1,344 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_RESIZE_H +#define _AAPL_RESIZE_H + +#include <assert.h> + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/* This step is expressed in units of T. Changing this requires changes to + * docs in ResizeLin constructor. */ +#define LIN_DEFAULT_STEP 256 + +/* + * Resizing macros giving different resize methods. + */ + +/* If needed is greater than existing, give twice needed. */ +#define EXPN_UP( existing, needed ) \ + needed > existing ? (needed<<1) : existing + +/* If needed is less than 1 quarter existing, give twice needed. */ +#define EXPN_DOWN( existing, needed ) \ + needed < (existing>>2) ? (needed<<1) : existing + +/* If needed is greater than existing, give needed plus step. */ +#define LIN_UP( existing, needed ) \ + needed > existing ? (needed+step) : existing + +/* If needed is less than existing - 2 * step then give needed plus step. */ +#define LIN_DOWN( existing, needed ) \ + needed < (existing-(step<<1)) ? (needed+step) : existing + +/* Return existing. */ +#define CONST_UP( existing, needed ) existing + +/* Return existing. */ +#define CONST_DOWN( existing, needed ) existing + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeLin + * \brief Linear table resizer. + * + * When an up resize or a down resize is needed, ResizeLin allocates the space + * needed plus some user defined step. The result is that when growing the + * vector in a linear fashion, the number of resizes is also linear. + * + * If only up resizing is done, then there will never be more than step unused + * spaces in the vector. If down resizing is done as well, there will never be + * more than 2*step unused spaces in the vector. The up resizing and down + * resizing policies are offset to improve performance when repeatedly + * inserting and removing a small number of elements relative to the step. + * This scheme guarantees that repetitive inserting and removing of a small + * number of elements will never result in repetative reallocation. + * + * The vectors pass sizes to the resizer in units of T, so the step gets + * interpreted as units of T. + */ + +/*@}*/ + +/* Linear resizing. */ +class ResizeLin +{ +protected: + /** + * \brief Default constructor. + * + * Intializes resize step to 256 units of the table type T. + */ + ResizeLin() : step(LIN_DEFAULT_STEP) { } + + /** + * \brief Determine the new table size when up resizing. + * + * If the existing size is insufficient for the space needed, then allocate + * the space needed plus the step. The step is in units of T. + */ + inline long upResize( long existing, long needed ) + { return LIN_UP(existing, needed); } + + /** + * \brief Determine the new table size when down resizing. + * + * If space needed is less than the existing - 2*step, then allocate the + * space needed space plus the step. The step is in units of T. + */ + inline long downResize( long existing, long needed ) + { return LIN_DOWN(existing, needed); } + +public: + /** + * \brief Step for linear resize. + * + * Amount of extra space in units of T added each time a resize must take + * place. This may be changed at any time. The step should be >= 0. + */ + long step; +}; + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeCtLin + * \brief Linear table resizer with compile time step. + * + * When an up resize or a down resize is needed, ResizeCtLin allocates the + * space needed plus some compile time defined step. The result is that when + * growing the vector in a linear fashion, the number of resizes is also + * linear. + * + * If only up resizing is done, then there will never be more than step unused + * spaces in the vector. If down resizing is done as well, there will never be + * more than 2*step unused spaces in the vector. The up resizing and down + * resizing policies are offset to improve performance when repeatedly + * inserting and removing a small number of elements relative to the step. + * This scheme guarantees that repetitive inserting and removing of a small + * number of elements will never result in repetative reallocation. + * + * The vectors pass sizes to the resizer in units of T, so the step gets + * interpreted as units of T. + */ + +/*@}*/ + +/* Linear resizing. */ +template <long step> class ResizeCtLin +{ +protected: + /** + * \brief Determine the new table size when up resizing. + * + * If the existing size is insufficient for the space needed, then allocate + * the space needed plus the step. The step is in units of T. + */ + inline long upResize( long existing, long needed ) + { return LIN_UP(existing, needed); } + + /** + * \brief Determine the new table size when down resizing. + * + * If space needed is less than the existing - 2*step, then allocate the + * space needed space plus the step. The step is in units of T. + */ + inline long downResize( long existing, long needed ) + { return LIN_DOWN(existing, needed); } +}; + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeConst + * \brief Constant table resizer. + * + * When an up resize is needed the existing size is always used. ResizeConst + * does not allow dynamic resizing. To use ResizeConst, the vector needs to be + * constructed with and initial allocation amount otherwise it will be + * unusable. + */ + +/*@}*/ + +/* Constant table resizing. */ +class ResizeConst +{ +protected: + /* Assert don't need more than exists. Return existing. */ + static inline long upResize( long existing, long needed ); + + /** + * \brief Determine the new table size when down resizing. + * + * Always returns the existing table size. + */ + static inline long downResize( long existing, long needed ) + { return CONST_DOWN(existing, needed); } +}; + +/** + * \brief Determine the new table size when up resizing. + * + * If the existing size is insufficient for the space needed, then an assertion + * will fail. Otherwise returns the existing size. + */ +inline long ResizeConst::upResize( long existing, long needed ) +{ + assert( needed <= existing ); + return CONST_UP(existing, needed); +} + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeRunTime + * \brief Run time settable table resizer. + * + * ResizeRunTime can have it's up and down resizing policies set at run time. + * Both up and down policies can be set independently to one of Exponential, + * Linear, or Constant. See the documentation for ResizeExpn, ResizeLin, and + * ResizeConst for the details of the resizing policies. + * + * The policies may be changed at any time. The default policies are + * both Exponential. + */ + +/*@}*/ + +/* Run time resizing. */ +class ResizeRunTime +{ +protected: + /** + * \brief Default constuctor. + * + * The up and down resizing it initialized to Exponetial. The step + * defaults to 256 units of T. + */ + inline ResizeRunTime(); + + /** + * \brief Resizing policies. + */ + enum ResizeType { + Exponential, /*!< Exponential resizing. */ + Linear, /*!< Linear resizing. */ + Constant /*!< Constant table size. */ + }; + + inline long upResize( long existing, long needed ); + inline long downResize( long existing, long needed ); + +public: + /** + * \brief Step for linear resize. + * + * Amount of extra space in units of T added each time a resize must take + * place. This may be changed at any time. The step should be >= 0. + */ + long step; + + /** + * \brief Up resizing policy. + */ + ResizeType upResizeType; + + /** + * \brief Down resizing policy. + */ + ResizeType downResizeType; +}; + +inline ResizeRunTime::ResizeRunTime() +: + step( LIN_DEFAULT_STEP ), + upResizeType( Exponential ), + downResizeType( Exponential ) +{ +} + +/** + * \brief Determine the new table size when up resizing. + * + * Type of up resizing is determined by upResizeType. Exponential, Linear and + * Constant resizing is the same as that of ResizeExpn, ResizeLin and + * ResizeConst. + */ +inline long ResizeRunTime::upResize( long existing, long needed ) +{ + switch ( upResizeType ) { + case Exponential: + return EXPN_UP(existing, needed); + case Linear: + return LIN_UP(existing, needed); + case Constant: + assert( needed <= existing ); + return CONST_UP(existing, needed); + } + return 0; +}; + +/** + * \brief Determine the new table size when down resizing. + * + * Type of down resizing is determined by downResiizeType. Exponential, Linear + * and Constant resizing is the same as that of ResizeExpn, ResizeLin and + * ResizeConst. + */ +inline long ResizeRunTime::downResize( long existing, long needed ) +{ + switch ( downResizeType ) { + case Exponential: + return EXPN_DOWN(existing, needed); + case Linear: + return LIN_DOWN(existing, needed); + case Constant: + return CONST_DOWN(existing, needed); + } + return 0; +} + +/* Don't need these anymore. */ +#undef EXPN_UP +#undef EXPN_DOWN +#undef LIN_UP +#undef LIN_DOWN +#undef CONST_UP +#undef CONST_DOWN + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_RESIZE_H */ diff --git a/aapl/sbstmap.h b/aapl/sbstmap.h new file mode 100644 index 00000000..9436a472 --- /dev/null +++ b/aapl/sbstmap.h @@ -0,0 +1,121 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_SBSTMAP_H +#define _AAPL_SBSTMAP_H + +#include "compare.h" +#include "svector.h" + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \brief Element for BstMap. + * + * Stores the key and value pair. + */ +template <class Key, class Value> struct SBstMapEl +{ + SBstMapEl() {} + SBstMapEl(const Key &key) : key(key) {} + SBstMapEl(const Key &key, const Value &val) : key(key), value(val) {} + + /** \brief The key */ + Key key; + + /** \brief The value. */ + Value value; +}; + +#ifdef AAPL_NAMESPACE +} +#endif + +/** + * \addtogroup bst + * @{ + */ + +/** + * \class SBstMap + * \brief Copy-on-write binary search table for key and value pairs. + * + * This is a map style binary search table that employs the copy-on-write + * mechanism for table data. BstMap stores key and value pairs in each + * element. The key and value can be any type. A compare class for the key + * must be supplied. + */ + +/*@}*/ + +#define BST_TEMPL_DECLARE class Key, class Value, \ + class Compare = CmpOrd<Key>, class Resize = ResizeExpn +#define BST_TEMPL_DEF class Key, class Value, class Compare, class Resize +#define BST_TEMPL_USE Key, Value, Compare, Resize +#define GET_KEY(el) ((el).key) +#define BstTable SBstMap +#define Vector SVector +#define Table STable +#define Element SBstMapEl<Key, Value> +#define BSTMAP +#define SHARED_BST + +#include "bstcommon.h" + +#undef BST_TEMPL_DECLARE +#undef BST_TEMPL_DEF +#undef BST_TEMPL_USE +#undef GET_KEY +#undef BstTable +#undef Vector +#undef Table +#undef Element +#undef BSTMAP +#undef SHARED_BST + +/** + * \fn SBstMap::insert(const Key &key, BstMapEl<Key, Value> **lastFound) + * \brief Insert the given key. + * + * If the given key does not already exist in the table then a new element + * having key is inserted. They key copy constructor and value default + * constructor are used to place the pair in the table. If lastFound is given, + * it is set to the new entry created. If the insert fails then lastFound is + * set to the existing pair of the same key. + * + * \returns The new element created upon success, null upon failure. + */ + +/** + * \fn SBstMap::insertMulti(const Key &key) + * \brief Insert the given key even if it exists already. + * + * If the key exists already then the new element having key is placed next + * to some other pair of the same key. InsertMulti cannot fail. The key copy + * constructor and the value default constructor are used to place the pair in + * the table. + * + * \returns The new element created. + */ + +#endif /* _AAPL_SBSTMAP_H */ diff --git a/aapl/sbstset.h b/aapl/sbstset.h new file mode 100644 index 00000000..fe8ddf6c --- /dev/null +++ b/aapl/sbstset.h @@ -0,0 +1,94 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_SBSTSET_H +#define _AAPL_SBSTSET_H + +/** + * \addtogroup bst + * @{ + */ + +/** + * \class SBstSet + * \brief Copy-on-write binary search table for types that are the key. + * + * This is a set style binary search table that employs the copy-on-write + * mechanism for storing table data. BstSet is suitable for types that + * comprise the entire key. Rather than look into the element to retrieve the + * key, the element is the key. A class that contains a comparison routine + * for the key must be given. + */ + +/*@}*/ + +#include "compare.h" +#include "svector.h" + +#define BST_TEMPL_DECLARE class Key, class Compare = CmpOrd<Key>, \ + class Resize = ResizeExpn +#define BST_TEMPL_DEF class Key, class Compare, class Resize +#define BST_TEMPL_USE Key, Compare, Resize +#define GET_KEY(el) (el) +#define BstTable SBstSet +#define Vector SVector +#define Table STable +#define Element Key +#define BSTSET +#define SHARED_BST + +#include "bstcommon.h" + +#undef BST_TEMPL_DECLARE +#undef BST_TEMPL_DEF +#undef BST_TEMPL_USE +#undef GET_KEY +#undef BstTable +#undef Vector +#undef Table +#undef Element +#undef BSTSET +#undef SHARED_BST + +/** + * \fn SBstSet::insert(const Key &key, Key **lastFound) + * \brief Insert the given key. + * + * If the given key does not already exist in the table then it is inserted. + * The key's copy constructor is used to place the item in the table. If + * lastFound is given, it is set to the new entry created. If the insert fails + * then lastFound is set to the existing key of the same value. + * + * \returns The new element created upon success, null upon failure. + */ + +/** + * \fn SBstSet::insertMulti(const Key &key) + * \brief Insert the given key even if it exists already. + * + * If the key exists already then it is placed next to some other key of the + * same value. InsertMulti cannot fail. The key's copy constructor is used to + * place the item in the table. + * + * \returns The new element created. + */ + +#endif /* _AAPL_SBSTSET_H */ diff --git a/aapl/sbsttable.h b/aapl/sbsttable.h new file mode 100644 index 00000000..100b87ec --- /dev/null +++ b/aapl/sbsttable.h @@ -0,0 +1,93 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_SBSTTABLE_H +#define _AAPL_SBSTTABLE_H + +#include "compare.h" +#include "svector.h" + +/** + * \addtogroup bst + * @{ + */ + +/** + * \class SBstTable + * \brief Copy-on-write binary search table for structures that contain a key. + * + * This is a basic binary search table that employs a copy-on-write data + * storage mechanism. It can be used to contain a structure that has a key and + * possibly some data. The key should be a member of the element class and + * accessible with getKey(). A class containing the compare routine must be + * supplied. + */ + +/*@}*/ + +#define BST_TEMPL_DECLARE class Element, class Key, \ + class Compare = CmpOrd<Key>, class Resize = ResizeExpn +#define BST_TEMPL_DEF class Element, class Key, class Compare, class Resize +#define BST_TEMPL_USE Element, Key, Compare, Resize +#define GET_KEY(el) ((el).getKey()) +#define BstTable SBstTable +#define Vector SVector +#define Table STable +#define BSTTABLE +#define SHARED_BST + +#include "bstcommon.h" + +#undef BST_TEMPL_DECLARE +#undef BST_TEMPL_DEF +#undef BST_TEMPL_USE +#undef GET_KEY +#undef BstTable +#undef Vector +#undef Table +#undef BSTTABLE +#undef SHARED_BST + +/** + * \fn SBstTable::insert(const Key &key, Element **lastFound) + * \brief Insert a new element with the given key. + * + * If the given key does not already exist in the table a new element is + * inserted with the given key. A constructor taking only const Key& is used + * to initialize the new element. If lastFound is given, it is set to the new + * element created. If the insert fails then lastFound is set to the existing + * element with the same key. + * + * \returns The new element created upon success, null upon failure. + */ + +/** + * \fn SBstTable::insertMulti(const Key &key) + * \brief Insert a new element even if the key exists already. + * + * If the key exists already then the new element is placed next to some + * element with the same key. InsertMulti cannot fail. A constructor taking + * only const Key& is used to initialize the new element. + * + * \returns The new element created. + */ + +#endif /* _AAPL_SBSTTABLE_H */ diff --git a/aapl/svector.h b/aapl/svector.h new file mode 100644 index 00000000..db3a5656 --- /dev/null +++ b/aapl/svector.h @@ -0,0 +1,1350 @@ +/* + * Copyright 2002, 2006 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_SVECTOR_H +#define _AAPL_SVECTOR_H + +#include <new> +#include <string.h> +#include <stdlib.h> +#include <assert.h> +#include "table.h" + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \addtogroup vector + * @{ + */ + +/** \class SVector + * \brief Copy-on-write dynamic array. + * + * SVector is a variant of Vector that employs copy-on-write behaviour. The + * SVector copy constructor and = operator make shallow copies. If a vector + * that references shared data is modified with insert, replace, append, + * prepend, setAs or remove, a new copy is made so as not to interfere with + * the shared data. However, shared individual elements may be modified by + * bypassing the SVector interface. + * + * SVector is a dynamic array that can be used to contain complex data + * structures that have constructors and destructors as well as simple types + * such as integers and pointers. + * + * SVector supports inserting, overwriting, and removing single or multiple + * elements at once. Constructors and destructors are called wherever + * appropriate. For example, before an element is overwritten, it's + * destructor is called. + * + * SVector provides automatic resizing of allocated memory as needed and + * offers different allocation schemes for controlling how the automatic + * allocation is done. Two senses of the the length of the data is + * maintained: the amount of raw memory allocated to the vector and the number + * of actual elements in the vector. The various allocation schemes control + * how the allocated space is changed in relation to the number of elements in + * the vector. + */ + +/*@}*/ + +/* SVector */ +template < class T, class Resize = ResizeExpn > class SVector : + public STable<T>, public Resize +{ +private: + typedef STable<T> BaseTable; + +public: + /** + * \brief Initialize an empty vector with no space allocated. + * + * If a linear resizer is used, the step defaults to 256 units of T. For a + * runtime vector both up and down allocation schemes default to + * Exponential. + */ + SVector() { } + + /** + * \brief Create a vector that contains an initial element. + * + * The vector becomes one element in length. The element's copy + * constructor is used to place the value in the vector. + */ + SVector(const T &val) { setAs(&val, 1); } + + /** + * \brief Create a vector that contains an array of elements. + * + * The vector becomes len elements in length. Copy constructors are used + * to place the new elements in the vector. + */ + SVector(const T *val, long len) { setAs(val, len); } + + /* Shallow copy. */ + SVector( const SVector &v ); + + /** + * \brief Free all memory used by the vector. + * + * The vector is reset to zero elements. Destructors are called on all + * elements in the vector. The space allocated for the vector is freed. + */ + ~SVector() { empty(); } + + /* Delete all items. */ + void empty(); + + /** + * \brief Deep copy another vector into this vector. + * + * Copies the entire contents of the other vector into this vector. Any + * existing contents are first deleted. Equivalent to setAs. + */ + void deepCopy( const SVector &v ) { setAs(v.data, v.length()); } + + /* Perform a shallow copy of another vector. */ + SVector &operator=( const SVector &v ); + + + /*@{*/ + /** + * \brief Insert one element at position pos. + * + * Elements in the vector from pos onward are shifted one space to the + * right. The copy constructor is used to place the element into this + * vector. If pos is greater than the length of the vector then undefined + * behaviour results. If pos is negative then it is treated as an offset + * relative to the length of the vector. + */ + void insert(long pos, const T &val) { insert(pos, &val, 1); } + + /* Insert an array of values. */ + void insert(long pos, const T *val, long len); + + /** + * \brief Insert all the elements from another vector at position pos. + * + * Elements in this vector from pos onward are shifted v.length() spaces + * to the right. The element's copy constructor is used to copy the items + * into this vector. The other vector is left unchanged. If pos is off the + * end of the vector, then undefined behaviour results. If pos is negative + * then it is treated as an offset relative to the length of the vector. + * Equivalent to vector.insert(pos, other.data, other.length()). + */ + void insert(long pos, const SVector &v) { insert(pos, v.data, v.length()); } + + /* Insert len copies of val into the vector. */ + void insertDup(long pos, const T &val, long len); + + /** + * \brief Insert one new element using the default constrcutor. + * + * Elements in the vector from pos onward are shifted one space to the right. + * The default constructor is used to init the new element. If pos is greater + * than the length of the vector then undefined behaviour results. If pos is + * negative then it is treated as an offset relative to the length of the + * vector. + */ + void insertNew(long pos) { insertNew(pos, 1); } + + /* Insert len new items using default constructor. */ + void insertNew(long pos, long len); + /*@}*/ + + /*@{*/ + /** + * \brief Remove one element at position pos. + * + * The element's destructor is called. Elements to the right of pos are + * shifted one space to the left to take up the free space. If pos is greater + * than or equal to the length of the vector then undefined behavior results. + * If pos is negative then it is treated as an offset relative to the length + * of the vector. + */ + void remove(long pos) { remove(pos, 1); } + + /* Delete a number of elements. */ + void remove(long pos, long len); + /*@}*/ + + /*@{*/ + /** + * \brief Replace one element at position pos. + * + * If there is an existing element at position pos (if pos is less than the + * length of the vector) then its destructor is called before the space is + * used. The copy constructor is used to place the element into the vector. + * If pos is greater than the length of the vector then undefined behaviour + * results. If pos is negative then it is treated as an offset relative to + * the length of the vector. + */ + void replace(long pos, const T &val) { replace(pos, &val, 1); } + + /* Replace with an array of values. */ + void replace(long pos, const T *val, long len); + + /** + * \brief Replace at position pos with all the elements of another vector. + * + * Replace at position pos with all the elements of another vector. The other + * vector is left unchanged. If there are existing elements at the positions + * to be replaced, then destructors are called before the space is used. Copy + * constructors are used to place the elements into this vector. It is + * allowable for the pos and length of the other vector to specify a + * replacement that overwrites existing elements and creates new ones. If pos + * is greater than the length of the vector then undefined behaviour results. + * If pos is negative, then it is treated as an offset relative to the length + * of the vector. + */ + void replace(long pos, const SVector &v) { replace(pos, v.data, v.length()); } + + /* Replace len items with len copies of val. */ + void replaceDup(long pos, const T &val, long len); + + /** + * \brief Replace at position pos with one new element. + * + * If there is an existing element at the position to be replaced (pos is + * less than the length of the vector) then the element's destructor is + * called before the space is used. The default constructor is used to + * initialize the new element. If pos is greater than the length of the + * vector then undefined behaviour results. If pos is negative, then it is + * treated as an offset relative to the length of the vector. + */ + void replaceNew(long pos) { replaceNew(pos, 1); } + + /* Replace len items at pos with newly constructed objects. */ + void replaceNew(long pos, long len); + /*@}*/ + + /*@{*/ + + /** + * \brief Set the contents of the vector to be val exactly. + * + * The vector becomes one element in length. Destructors are called on any + * existing elements in the vector. The element's copy constructor is used to + * place the val in the vector. + */ + void setAs(const T &val) { setAs(&val, 1); } + + /* Set to the contents of an array. */ + void setAs(const T *val, long len); + + /** + * \brief Set the vector to exactly the contents of another vector. + * + * The vector becomes v.length() elements in length. Destructors are called + * on any existing elements. Copy constructors are used to place the new + * elements in the vector. + */ + void setAs(const SVector &v) { setAs(v.data, v.length()); } + + /* Set as len copies of item. */ + void setAsDup(const T &item, long len); + + /** + * \brief Set the vector to exactly one new item. + * + * The vector becomes one element in length. Destructors are called on any + * existing elements in the vector. The default constructor is used to + * init the new item. + */ + void setAsNew() { setAsNew(1); } + + /* Set as newly constructed objects using the default constructor. */ + void setAsNew(long len); + /*@}*/ + + /*@{*/ + /** + * \brief Append one elment to the end of the vector. + * + * Copy constructor is used to place the element in the vector. + */ + void append(const T &val) { replace(BaseTable::length(), &val, 1); } + + /** + * \brief Append len elements to the end of the vector. + * + * Copy constructors are used to place the elements in the vector. + */ + void append(const T *val, long len) { replace(BaseTable::length(), val, len); } + + /** + * \brief Append the contents of another vector. + * + * The other vector is left unchanged. Copy constructors are used to place + * the elements in the vector. + */ + void append(const SVector &v) + { replace(BaseTable::length(), v.data, v.length()); } + + /** + * \brief Append len copies of item. + * + * The copy constructor is used to place the item in the vector. + */ + void appendDup(const T &item, long len) { replaceDup(BaseTable::length(), item, len); } + + /** + * \brief Append a single newly created item. + * + * The new element is initialized with the default constructor. + */ + void appendNew() { replaceNew(BaseTable::length(), 1); } + + /** + * \brief Append len newly created items. + * + * The new elements are initialized with the default constructor. + */ + void appendNew(long len) { replaceNew(BaseTable::length(), len); } + /*@}*/ + + + /*@{*/ + /** + * \brief Prepend one elment to the front of the vector. + * + * Copy constructor is used to place the element in the vector. + */ + void prepend(const T &val) { insert(0, &val, 1); } + + /** + * \brief Prepend len elements to the front of the vector. + * + * Copy constructors are used to place the elements in the vector. + */ + void prepend(const T *val, long len) { insert(0, val, len); } + + /** + * \brief Prepend the contents of another vector. + * + * The other vector is left unchanged. Copy constructors are used to place + * the elements in the vector. + */ + void prepend(const SVector &v) { insert(0, v.data, v.length()); } + + /** + * \brief Prepend len copies of item. + * + * The copy constructor is used to place the item in the vector. + */ + void prependDup(const T &item, long len) { insertDup(0, item, len); } + + /** + * \brief Prepend a single newly created item. + * + * The new element is initialized with the default constructor. + */ + void prependNew() { insertNew(0, 1); } + + /** + * \brief Prepend len newly created items. + * + * The new elements are initialized with the default constructor. + */ + void prependNew(long len) { insertNew(0, len); } + /*@}*/ + + /* Convenience access. */ + T &operator[](int i) const { return BaseTable::data[i]; } + long size() const { return BaseTable::length(); } + + /* Various classes for setting the iterator */ + struct Iter; + struct IterFirst { IterFirst( const SVector &v ) : v(v) { } const SVector &v; }; + struct IterLast { IterLast( const SVector &v ) : v(v) { } const SVector &v; }; + struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; }; + struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; }; + + /** + * \brief Shared Vector Iterator. + * \ingroup iterators + */ + struct Iter + { + /* Construct, assign. */ + Iter() : ptr(0), ptrBeg(0), ptrEnd(0) { } + + /* Construct. */ + Iter( const SVector &v ); + Iter( const IterFirst &vf ); + Iter( const IterLast &vl ); + inline Iter( const IterNext &vn ); + inline Iter( const IterPrev &vp ); + + /* Assign. */ + Iter &operator=( const SVector &v ); + Iter &operator=( const IterFirst &vf ); + Iter &operator=( const IterLast &vl ); + inline Iter &operator=( const IterNext &vf ); + inline Iter &operator=( const IterPrev &vl ); + + /** \brief Less than end? */ + bool lte() const { return ptr != ptrEnd; } + + /** \brief At end? */ + bool end() const { return ptr == ptrEnd; } + + /** \brief Greater than beginning? */ + bool gtb() const { return ptr != ptrBeg; } + + /** \brief At beginning? */ + bool beg() const { return ptr == ptrBeg; } + + /** \brief At first element? */ + bool first() const { return ptr == ptrBeg+1; } + + /** \brief At last element? */ + bool last() const { return ptr == ptrEnd-1; } + + /* Return the position. */ + long pos() const { return ptr - ptrBeg - 1; } + T &operator[](int i) const { return ptr[i]; } + + /** \brief Implicit cast to T*. */ + operator T*() const { return ptr; } + + /** \brief Dereference operator returns T&. */ + T &operator *() const { return *ptr; } + + /** \brief Arrow operator returns T*. */ + T *operator->() const { return ptr; } + + /** \brief Move to next item. */ + T *operator++() { return ++ptr; } + + /** \brief Move to next item. */ + T *operator++(int) { return ptr++; } + + /** \brief Move to next item. */ + T *increment() { return ++ptr; } + + /** \brief Move to previous item. */ + T *operator--() { return --ptr; } + + /** \brief Move to previous item. */ + T *operator--(int) { return ptr--; } + + /** \brief Move to previous item. */ + T *decrement() { return --ptr; } + + /** \brief Return the next item. Does not modify this. */ + inline IterNext next() const { return IterNext(*this); } + + /** \brief Return the previous item. Does not modify this. */ + inline IterPrev prev() const { return IterPrev(*this); } + + /** \brief The iterator is simply a pointer. */ + T *ptr; + + /* For testing endpoints. */ + T *ptrBeg, *ptrEnd; + }; + + /** \brief Return first element. */ + IterFirst first() { return IterFirst( *this ); } + + /** \brief Return last element. */ + IterLast last() { return IterLast( *this ); } + +protected: + void makeRawSpaceFor(long pos, long len); + + void setAsCommon(long len); + long replaceCommon(long pos, long len); + long insertCommon(long pos, long len); + + void upResize(long len); + void upResizeDup(long len); + void upResizeFromEmpty(long len); + void downResize(long len); + void downResizeDup(long len); +}; + +/** + * \brief Perform a shallow copy of the vector. + * + * Takes a reference to the contents of the other vector. + */ +template <class T, class Resize> SVector<T, Resize>:: + SVector(const SVector<T, Resize> &v) +{ + /* Take a reference to other, if any data is allocated. */ + if ( v.data == 0 ) + BaseTable::data = 0; + else { + /* Get the source header, up the refcount and ref it. */ + STabHead *srcHead = ((STabHead*) v.data) - 1; + srcHead->refCount += 1; + BaseTable::data = (T*) (srcHead + 1); + } +} + +/** + * \brief Shallow copy another vector into this vector. + * + * Takes a reference to the other vector. The contents of this vector are + * first emptied. + * + * \returns A reference to this. + */ +template <class T, class Resize> SVector<T, Resize> & + SVector<T, Resize>:: operator=( const SVector &v ) +{ + /* First clean out the current contents. */ + empty(); + + /* Take a reference to other, if any data is allocated. */ + if ( v.data == 0 ) + BaseTable::data = 0; + else { + /* Get the source header, up the refcount and ref it. */ + STabHead *srcHead = ((STabHead*) v.data) - 1; + srcHead->refCount += 1; + BaseTable::data = (T*) (srcHead + 1); + } + return *this; +} + +/* Init a vector iterator with just a vector. */ +template <class T, class Resize> SVector<T, Resize>:: + Iter::Iter( const SVector &v ) +{ + long length; + if ( v.data == 0 || (length=(((STabHead*)v.data)-1)->tabLen) == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = v.data; + ptrBeg = v.data-1; + ptrEnd = v.data+length; + } +} + +/* Init a vector iterator with the first of a vector. */ +template <class T, class Resize> SVector<T, Resize>:: + Iter::Iter( const IterFirst &vf ) +{ + long length; + if ( vf.v.data == 0 || (length=(((STabHead*)vf.v.data)-1)->tabLen) == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vf.v.data; + ptrBeg = vf.v.data-1; + ptrEnd = vf.v.data+length; + } +} + +/* Init a vector iterator with the last of a vector. */ +template <class T, class Resize> SVector<T, Resize>:: + Iter::Iter( const IterLast &vl ) +{ + long length; + if ( vl.v.data == 0 || (length=(((STabHead*)vl.v.data)-1)->tabLen) == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vl.v.data+length-1; + ptrBeg = vl.v.data-1; + ptrEnd = vl.v.data+length; + } +} + +/* Init a vector iterator with the next of some other iterator. */ +template <class T, class Resize> SVector<T, Resize>:: + Iter::Iter( const IterNext &vn ) +: + ptr(vn.i.ptr+1), + ptrBeg(vn.i.ptrBeg), + ptrEnd(vn.i.ptrEnd) +{ +} + +/* Init a vector iterator with the prev of some other iterator. */ +template <class T, class Resize> SVector<T, Resize>:: + Iter::Iter( const IterPrev &vp ) +: + ptr(vp.i.ptr-1), + ptrBeg(vp.i.ptrBeg), + ptrEnd(vp.i.ptrEnd) +{ +} + +/* Set a vector iterator with some vector. */ +template <class T, class Resize> typename SVector<T, Resize>::Iter & + SVector<T, Resize>::Iter::operator=( const SVector &v ) +{ + long length; + if ( v.data == 0 || (length=(((STabHead*)v.data)-1)->tabLen) == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = v.data; + ptrBeg = v.data-1; + ptrEnd = v.data+length; + } + return *this; +} + +/* Set a vector iterator with the first element in a vector. */ +template <class T, class Resize> typename SVector<T, Resize>::Iter & + SVector<T, Resize>::Iter::operator=( const IterFirst &vf ) +{ + long length; + if ( vf.v.data == 0 || (length=(((STabHead*)vf.v.data)-1)->tabLen) == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vf.v.data; + ptrBeg = vf.v.data-1; + ptrEnd = vf.v.data+length; + } + return *this; +} + +/* Set a vector iterator with the last element in a vector. */ +template <class T, class Resize> typename SVector<T, Resize>::Iter & + SVector<T, Resize>::Iter::operator=( const IterLast &vl ) +{ + long length; + if ( vl.v.data == 0 || (length=(((STabHead*)vl.v.data)-1)->tabLen) == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vl.v.data+length-1; + ptrBeg = vl.v.data-1; + ptrEnd = vl.v.data+length; + } + return *this; +} + +/* Set a vector iterator with the next of some other iterator. */ +template <class T, class Resize> typename SVector<T, Resize>::Iter & + SVector<T, Resize>::Iter::operator=( const IterNext &vn ) +{ + ptr = vn.i.ptr+1; + ptrBeg = vn.i.ptrBeg; + ptrEnd = vn.i.ptrEnd; + return *this; +} + +/* Set a vector iterator with the prev of some other iterator. */ +template <class T, class Resize> typename SVector<T, Resize>::Iter & + SVector<T, Resize>::Iter::operator=( const IterPrev &vp ) +{ + ptr = vp.i.ptr-1; + ptrBeg = vp.i.ptrBeg; + ptrEnd = vp.i.ptrEnd; + return *this; +} + +/* Up resize the data for len elements using Resize::upResize to tell us the + * new length. Reads and writes allocLen. Does not read or write length. + * Assumes that there is some data allocated already. */ +template <class T, class Resize> void SVector<T, Resize>:: + upResize(long len) +{ + /* Get the current header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* Ask the resizer what the new length will be. */ + long newLen = Resize::upResize(head->allocLen, len); + + /* Did the data grow? */ + if ( newLen > head->allocLen ) { + head->allocLen = newLen; + + /* Table exists already, resize it up. */ + head = (STabHead*) realloc( head, sizeof(STabHead) + + sizeof(T) * newLen ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Save the data pointer. */ + BaseTable::data = (T*) (head + 1); + } +} + +/* Allocates a new buffer for an up resize that requires a duplication of the + * data. Uses Resize::upResize to get the allocation length. Reads and writes + * allocLen. This upResize does write the new length. Assumes that there is + * some data allocated already. */ +template <class T, class Resize> void SVector<T, Resize>:: + upResizeDup(long len) +{ + /* Get the current header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* Ask the resizer what the new length will be. */ + long newLen = Resize::upResize(head->allocLen, len); + + /* Dereferencing the existing data, decrement the refcount. */ + head->refCount -= 1; + + /* Table exists already, resize it up. */ + head = (STabHead*) malloc( sizeof(STabHead) + sizeof(T) * newLen ); + if ( head == 0 ) + throw std::bad_alloc(); + + head->refCount = 1; + head->allocLen = newLen; + head->tabLen = len; + + /* Save the data pointer. */ + BaseTable::data = (T*) (head + 1); +} + +/* Up resize the data for len elements using Resize::upResize to tell us the + * new length. Reads and writes allocLen. This upresize DOES write length. + * Assumes that no data is allocated. */ +template <class T, class Resize> void SVector<T, Resize>:: + upResizeFromEmpty(long len) +{ + /* There is no table yet. If the len is zero, then there is no need to + * create a table. */ + if ( len > 0 ) { + /* Ask the resizer what the new length will be. */ + long newLen = Resize::upResize(0, len); + + /* If len is greater than zero then we are always allocating the table. */ + STabHead *head = (STabHead*) malloc( sizeof(STabHead) + + sizeof(T) * newLen ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Set up the header and save the data pointer. Note that we set the + * length here. This differs from the other upResizes. */ + head->refCount = 1; + head->allocLen = newLen; + head->tabLen = len; + BaseTable::data = (T*) (head + 1); + } +} + +/* Down resize the data for len elements using Resize::downResize to determine + * the new length. Reads and writes allocLen. Does not read or write length. */ +template <class T, class Resize> void SVector<T, Resize>:: + downResize(long len) +{ + /* If there is already no length, then there is nothing we can do. */ + if ( BaseTable::data != 0 ) { + /* Get the current header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* Ask the resizer what the new length will be. */ + long newLen = Resize::downResize( head->allocLen, len ); + + /* Did the data shrink? */ + if ( newLen < head->allocLen ) { + if ( newLen == 0 ) { + /* Simply free the data. */ + free( head ); + BaseTable::data = 0; + } + else { + /* Save the new allocated length. */ + head->allocLen = newLen; + + /* Not shrinking to size zero, realloc it to the smaller size. */ + head = (STabHead*) realloc( head, sizeof(STabHead) + + sizeof(T) * newLen ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Save the new data ptr. */ + BaseTable::data = (T*) (head + 1); + } + } + } +} + +/* Allocate a new buffer for a down resize and duplication of the array. The + * new array will be len long and allocation size will be determined using + * Resize::downResize with the old array's allocLen. Does not actually copy + * any data. Reads and writes allocLen and writes the new len. */ +template <class T, class Resize> void SVector<T, Resize>:: + downResizeDup(long len) +{ + /* If there is already no length, then there is nothing we can do. */ + if ( BaseTable::data != 0 ) { + /* Get the current header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* Ask the resizer what the new length will be. */ + long newLen = Resize::downResize( head->allocLen, len ); + + /* Detaching from the existing head, decrement the refcount. */ + head->refCount -= 1; + + /* Not shrinking to size zero, malloc it to the smaller size. */ + head = (STabHead*) malloc( sizeof(STabHead) + sizeof(T) * newLen ); + if ( head == 0 ) + throw std::bad_alloc(); + + /* Save the new allocated length. */ + head->refCount = 1; + head->allocLen = newLen; + head->tabLen = len; + + /* Save the data pointer. */ + BaseTable::data = (T*) (head + 1); + } +} + +/** + * \brief Free all memory used by the vector. + * + * The vector is reset to zero elements. Destructors are called on all + * elements in the vector. The space allocated for the vector is freed. + */ +template <class T, class Resize> void SVector<T, Resize>:: + empty() +{ + if ( BaseTable::data != 0 ) { + /* Get the header and drop the refcount on the data. */ + STabHead *head = ((STabHead*) BaseTable::data) - 1; + head->refCount -= 1; + + /* If the refcount just went down to zero nobody else is referencing + * the data. */ + if ( head->refCount == 0 ) { + /* Call All destructors. */ + T *pos = BaseTable::data; + for ( long i = 0; i < head->tabLen; pos++, i++ ) + pos->~T(); + + /* Free the data space. */ + free( head ); + } + + /* Clear the pointer. */ + BaseTable::data = 0; + } +} + +/* Prepare for setting the contents of the vector to some array len long. + * Handles reusing the existing space, detaching from a common space or + * growing from zero length automatically. */ +template <class T, class Resize> void SVector<T, Resize>:: + setAsCommon(long len) +{ + if ( BaseTable::data != 0 ) { + /* Get the header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* If the refCount is one, then we can reuse the space. Otherwise we + * must detach from the referenced data create new space. */ + if ( head->refCount == 1 ) { + /* Call All destructors. */ + T *pos = BaseTable::data; + for ( long i = 0; i < head->tabLen; pos++, i++ ) + pos->~T(); + + /* Adjust the allocated length. */ + if ( len < head->tabLen ) + downResize( len ); + else if ( len > head->tabLen ) + upResize( len ); + + if ( BaseTable::data != 0 ) { + /* Get the header again and set the length. */ + head = ((STabHead*)BaseTable::data) - 1; + head->tabLen = len; + } + } + else { + /* Just detach from the data. */ + head->refCount -= 1; + BaseTable::data = 0; + + /* Make enough space. This will set the length. */ + upResizeFromEmpty( len ); + } + } + else { + /* The table is currently empty. Make enough space. This will set the + * length. */ + upResizeFromEmpty( len ); + } +} + +/** + * \brief Set the contents of the vector to be len elements exactly. + * + * The vector becomes len elements in length. Destructors are called on any + * existing elements in the vector. Copy constructors are used to place the + * new elements in the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + setAs(const T *val, long len) +{ + /* Common stuff for setting the array to len long. */ + setAsCommon( len ); + + /* Copy data in. */ + T *dst = BaseTable::data; + const T *src = val; + for ( long i = 0; i < len; i++, dst++, src++ ) + new(dst) T(*src); +} + + +/** + * \brief Set the vector to len copies of item. + * + * The vector becomes len elements in length. Destructors are called on any + * existing elements in the vector. The element's copy constructor is used to + * copy the item into the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + setAsDup(const T &item, long len) +{ + /* Do the common stuff for setting the array to len long. */ + setAsCommon( len ); + + /* Copy item in one spot at a time. */ + T *dst = BaseTable::data; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(item); +} + +/** + * \brief Set the vector to exactly len new items. + * + * The vector becomes len elements in length. Destructors are called on any + * existing elements in the vector. Default constructors are used to init the + * new items. + */ +template <class T, class Resize> void SVector<T, Resize>:: + setAsNew(long len) +{ + /* Do the common stuff for setting the array to len long. */ + setAsCommon( len ); + + /* Create items using default constructor. */ + T *dst = BaseTable::data; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(); +} + +/* Make space in vector for a replacement at pos of len items. Handles reusing + * existing space, detaching or growing from zero space. */ +template <class T, class Resize> long SVector<T, Resize>:: + replaceCommon(long pos, long len) +{ + if ( BaseTable::data != 0 ) { + /* Get the header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* If we are given a negative position to replace at then treat it as + * a position relative to the length. This doesn't have any meaning + * unless the length is at least one. */ + if ( pos < 0 ) + pos = head->tabLen + pos; + + /* The end is the one past the last item that we want to write to. */ + long i, endPos = pos + len; + + if ( head->refCount == 1 ) { + /* We can reuse the space. Make sure we have enough space. */ + if ( endPos > head->tabLen ) { + upResize( endPos ); + + /* Get the header again, whose addr may have changed after + * resizing. */ + head = ((STabHead*)BaseTable::data) - 1; + + /* Delete any objects we need to delete. */ + T *item = BaseTable::data + pos; + for ( i = pos; i < head->tabLen; i++, item++ ) + item->~T(); + + /* We are extending the vector, set the new data length. */ + head->tabLen = endPos; + } + else { + /* Delete any objects we need to delete. */ + T *item = BaseTable::data + pos; + for ( i = pos; i < endPos; i++, item++ ) + item->~T(); + } + } + else { + /* Use endPos to calc the end of the vector. */ + long newLen = endPos; + if ( newLen < head->tabLen ) + newLen = head->tabLen; + + /* Duplicate and grow up to endPos. This will set the length. */ + upResizeDup( newLen ); + + /* Copy from src up to pos. */ + const T *src = (T*) (head + 1); + T *dst = BaseTable::data; + for ( i = 0; i < pos; i++, dst++, src++) + new(dst) T(*src); + + /* Copy any items after the replace range. */ + for ( i += len, src += len, dst += len; + i < head->tabLen; i++, dst++, src++ ) + new(dst) T(*src); + } + } + else { + /* There is no data initially, must grow from zero. This will set the + * new length. */ + upResizeFromEmpty( len ); + } + + return pos; +} + + +/** + * \brief Replace len elements at position pos. + * + * If there are existing elements at the positions to be replaced, then + * destructors are called before the space is used. Copy constructors are used + * to place the elements into the vector. It is allowable for the pos and + * length to specify a replacement that overwrites existing elements and + * creates new ones. If pos is greater than the length of the vector then + * undefined behaviour results. If pos is negative, then it is treated as an + * offset relative to the length of the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + replace(long pos, const T *val, long len) +{ + /* Common work for replacing in the vector. */ + pos = replaceCommon( pos, len ); + + /* Copy data in using copy constructor. */ + T *dst = BaseTable::data + pos; + const T *src = val; + for ( long i = 0; i < len; i++, dst++, src++ ) + new(dst) T(*src); +} + +/** + * \brief Replace at position pos with len copies of an item. + * + * If there are existing elements at the positions to be replaced, then + * destructors are called before the space is used. The copy constructor is + * used to place the element into this vector. It is allowable for the pos and + * length to specify a replacement that overwrites existing elements and + * creates new ones. If pos is greater than the length of the vector then + * undefined behaviour results. If pos is negative, then it is treated as an + * offset relative to the length of the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + replaceDup(long pos, const T &val, long len) +{ + /* Common replacement stuff. */ + pos = replaceCommon( pos, len ); + + /* Copy data in using copy constructor. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(val); +} + +/** + * \brief Replace at position pos with len new elements. + * + * If there are existing elements at the positions to be replaced, then + * destructors are called before the space is used. The default constructor is + * used to initialize the new elements. It is allowable for the pos and length + * to specify a replacement that overwrites existing elements and creates new + * ones. If pos is greater than the length of the vector then undefined + * behaviour results. If pos is negative, then it is treated as an offset + * relative to the length of the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + replaceNew(long pos, long len) +{ + /* Do the common replacement stuff. */ + pos = replaceCommon( pos, len ); + + /* Copy data in using copy constructor. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(); +} + +/** + * \brief Remove len elements at position pos. + * + * Destructor is called on all elements removed. Elements to the right of pos + * are shifted len spaces to the left to take up the free space. If pos is + * greater than or equal to the length of the vector then undefined behavior + * results. If pos is negative then it is treated as an offset relative to the + * length of the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + remove(long pos, long len) +{ + /* If there is no data, we can't delete anything anyways. */ + if ( BaseTable::data != 0 ) { + /* Get the header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* If we are given a negative position to remove at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = head->tabLen + pos; + + /* The first position after the last item deleted. */ + long endPos = pos + len; + + /* The New data length. */ + long i, newLen = head->tabLen - len; + + if ( head->refCount == 1 ) { + /* We are the only ones using the data. We can reuse + * the existing space. */ + + /* The place in the data we are deleting at. */ + T *dst = BaseTable::data + pos; + + /* Call Destructors. */ + T *item = BaseTable::data + pos; + for ( i = 0; i < len; i += 1, item += 1 ) + item->~T(); + + /* Shift data over if necessary. */ + long lenToSlideOver = head->tabLen - endPos; + if ( len > 0 && lenToSlideOver > 0 ) + memmove(BaseTable::data + pos, dst + len, sizeof(T)*lenToSlideOver); + + /* Shrink the data if necessary. */ + downResize( newLen ); + + if ( BaseTable::data != 0 ) { + /* Get the header again (because of the resize) and set the + * new data length. */ + head = ((STabHead*)BaseTable::data) - 1; + head->tabLen = newLen; + } + } + else { + /* Must detach from the common data. Just copy the non-deleted + * items from the common data. */ + + /* Duplicate and grow down to newLen. This will set the length. */ + downResizeDup( newLen ); + + /* Copy over just the non-deleted parts. */ + const T *src = (T*) (head + 1); + T *dst = BaseTable::data; + for ( i = 0; i < pos; i++, dst++, src++ ) + new(dst) T(*src); + + /* ... and the second half. */ + for ( i += len, src += len; i < head->tabLen; i++, src++, dst++ ) + new(dst) T(*src); + } + } +} + +/* Shift over existing data. Handles reusing existing space, detaching or + * growing from zero space. */ +template <class T, class Resize> long SVector<T, Resize>:: + insertCommon(long pos, long len) +{ + if ( BaseTable::data != 0 ) { + /* Get the header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* If we are given a negative position to insert at then treat it as a + * position relative to the length. This only has meaning if there is + * existing data. */ + if ( pos < 0 ) + pos = head->tabLen + pos; + + /* Calculate the new length. */ + long i, newLen = head->tabLen + len; + + if ( head->refCount == 1 ) { + /* Up resize, we are growing. */ + upResize( newLen ); + + /* Get the header again, (the addr may have changed after + * resizing). */ + head = ((STabHead*)BaseTable::data) - 1; + + /* Shift over data at insert spot if needed. */ + if ( len > 0 && pos < head->tabLen ) { + memmove( BaseTable::data + pos + len, BaseTable::data + pos, + sizeof(T)*(head->tabLen - pos) ); + } + + /* Grow the length by the len inserted. */ + head->tabLen += len; + } + else { + /* Need to detach from the existing array. Copy over the other + * parts. This will set the length. */ + upResizeDup( newLen ); + + /* Copy over the parts around the insert. */ + const T *src = (T*) (head + 1); + T *dst = BaseTable::data; + for ( i = 0; i < pos; i++, dst++, src++ ) + new(dst) T(*src); + + /* ... and the second half. */ + for ( dst += len; i < head->tabLen; i++, src++, dst++ ) + new(dst) T(*src); + } + } + else { + /* There is no existing data. Start from zero. This will set the + * length. */ + upResizeFromEmpty( len ); + } + + return pos; +} + + +/** + * \brief Insert len elements at position pos. + * + * Elements in the vector from pos onward are shifted len spaces to the right. + * The copy constructor is used to place the elements into this vector. If pos + * is greater than the length of the vector then undefined behaviour results. + * If pos is negative then it is treated as an offset relative to the length + * of the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + insert(long pos, const T *val, long len) +{ + /* Do the common insertion stuff. */ + pos = insertCommon( pos, len ); + + /* Copy data in element by element. */ + T *dst = BaseTable::data + pos; + const T *src = val; + for ( long i = 0; i < len; i++, dst++, src++ ) + new(dst) T(*src); +} + +/** + * \brief Insert len copies of item at position pos. + * + * Elements in the vector from pos onward are shifted len spaces to the right. + * The copy constructor is used to place the element into this vector. If pos + * is greater than the length of the vector then undefined behaviour results. + * If pos is negative then it is treated as an offset relative to the length + * of the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + insertDup(long pos, const T &item, long len) +{ + /* Do the common insertion stuff. */ + pos = insertCommon( pos, len ); + + /* Copy the data item in one at a time. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(item); +} + + +/** + * \brief Insert len new elements using the default constructor. + * + * Elements in the vector from pos onward are shifted len spaces to the right. + * Default constructors are used to init the new elements. If pos is off the + * end of the vector then undefined behaviour results. If pos is negative then + * it is treated as an offset relative to the length of the vector. + */ +template <class T, class Resize> void SVector<T, Resize>:: + insertNew(long pos, long len) +{ + /* Do the common insertion stuff. */ + pos = insertCommon( pos, len ); + + /* Init new data with default constructors. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(); +} + +/* Makes space for len items, Does not init the items in any way. If pos is + * greater than the length of the vector then undefined behaviour results. + * Updates the length of the vector. */ +template <class T, class Resize> void SVector<T, Resize>:: + makeRawSpaceFor(long pos, long len) +{ + if ( BaseTable::data != 0 ) { + /* Get the header. */ + STabHead *head = ((STabHead*)BaseTable::data) - 1; + + /* Calculate the new length. */ + long i, newLen = head->tabLen + len; + + if ( head->refCount == 1 ) { + /* Up resize, we are growing. */ + upResize( newLen ); + + /* Get the header again, (the addr may have changed after + * resizing). */ + head = ((STabHead*)BaseTable::data) - 1; + + /* Shift over data at insert spot if needed. */ + if ( len > 0 && pos < head->tabLen ) { + memmove( BaseTable::data + pos + len, BaseTable::data + pos, + sizeof(T)*(head->tabLen - pos) ); + } + + /* Grow the length by the len inserted. */ + head->tabLen += len; + } + else { + /* Need to detach from the existing array. Copy over the other + * parts. This will set the length. */ + upResizeDup( newLen ); + + /* Copy over the parts around the insert. */ + const T *src = (T*) (head + 1); + T *dst = BaseTable::data; + for ( i = 0; i < pos; i++, dst++, src++ ) + new(dst) T(*src); + + /* ... and the second half. */ + for ( dst += len; i < head->tabLen; i++, src++, dst++ ) + new(dst) T(*src); + } + } + else { + /* There is no existing data. Start from zero. This will set the + * length. */ + upResizeFromEmpty( len ); + } +} + + +#ifdef AAPL_NAMESPACE +} +#endif + + +#endif /* _AAPL_SVECTOR_H */ diff --git a/aapl/table.h b/aapl/table.h new file mode 100644 index 00000000..c1f2b7bd --- /dev/null +++ b/aapl/table.h @@ -0,0 +1,252 @@ +/* + * Copyright 2001, 2002 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_TABLE_H +#define _AAPL_TABLE_H + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \addtogroup vector + * @{ + */ + +/** \class Table + * \brief Base class for dynamic arrays. + * + * Table is used as the common data storage class for vectors. It does not + * provide any methods to operate on the data and as such it is not intended + * to be used directly. It exists so that algorithms that operatate on dynamic + * arrays can be written without knowing about the various vector classes that + * my exist. + */ + +/*@}*/ + +/* Table class. */ +template <class T> class Table +{ +public: + /* Default Constructor. */ + inline Table(); + + /** + * \brief Get the length of the vector. + * + * \returns the length of the vector. + */ + long length() const + { return tabLen; } + + /** + * \brief Table data. + * + * The pointer to the elements in the vector. Modifying the vector may + * cause this pointer to change. + */ + T *data; + + /** + * \brief Table length. + * + * The number of items of type T in the table. + */ + long tabLen; + + /** + * \brief Allocated length. + * + * The number of items for which there is room in the current allocation. + */ + long allocLen; +}; + +/** + * \brief Default constructor + * + * Initialize table data to empty. + */ +template <class T> inline Table<T>::Table() +: + data(0), + tabLen(0), + allocLen(0) +{ +} + +/* Default shared table header class. */ +struct STabHead +{ + /** + * \brief Table length. + * + * The number of items of type T in the table. + */ + long tabLen; + + /** + * \brief Allocated length. + * + * The number of items for which there is room in the current allocation. + */ + long allocLen; + + /** + * \brief Ref Count. + * + * The number of shared vectors referencing this data. + */ + long refCount; +}; + +/** + * \addtogroup vector + * @{ + */ + +/** \class STable + * \brief Base class for implicitly shared dynamic arrays. + * + * STable is used as the common data storage class for shared vectors. It does + * not provide any methods to operate on the data and as such it is not + * intended to be used directly. It exists so that algorithms that operatate + * on dynamic arrays can be written without knowing about the various shared + * vector classes that my exist. + */ + +/*@}*/ + +/* STable class. */ +template <class T> class STable +{ +public: + /* Default Constructor. */ + inline STable(); + + /** + * \brief Get the length of the shared vector. + * + * \returns the length of the shared vector. + */ + long length() const + { return data == 0 ? 0 : (((STabHead*)data) - 1)->tabLen; } + + /** + * \brief Get header of the shared vector. + * + * \returns the header of the shared vector. + */ + STabHead *header() const + { return data == 0 ? 0 : (((STabHead*)data) - 1); } + + /** + * \brief Table data. + * + * The pointer to the elements in the vector. The shared table header is + * located just behind the data. Modifying the vector may cause this + * pointer to change. + */ + T *data; +}; + +/** + * \brief Default constructor + * + * Initialize shared table data to empty. + */ +template <class T> inline STable<T>::STable() +: + data(0) +{ +} + +/* If needed is greater than existing, give twice needed. */ +#define EXPN_UP( existing, needed ) \ + needed > existing ? (needed<<1) : existing + +/* If needed is less than 1 quarter existing, give twice needed. */ +#define EXPN_DOWN( existing, needed ) \ + needed < (existing>>2) ? (needed<<1) : existing + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeExpn + * \brief Exponential table resizer. + * + * ResizeExpn is the default table resizer. When an up resize is needed, space + * is doubled. When a down resize is needed, space is halved. The result is + * that when growing the vector in a linear fashion, the number of resizes of + * the allocated space behaves logarithmically. + * + * If only up resizes are done, there will never be more than 2 times the + * needed space allocated. If down resizes are done as well, there will never + * be more than 4 times the needed space allocated. ResizeExpn uses this 50% + * usage policy on up resizing and 25% usage policy on down resizing to + * improve performance when repeatedly inserting and removing a small number + * of elements relative to the size of the array. This scheme guarantees that + * repetitive inserting and removing of a small number of elements will never + * result in repetative reallocation. + * + * The sizes passed to the resizer from the vectors are in units of T. + */ + +/*@}*/ + +/* Exponential resizer. */ +class ResizeExpn +{ +protected: + /** + * \brief Determine the new table size when up resizing. + * + * If the existing size is insufficient for the space needed then allocate + * twice the space needed. Otherwise use the existing size. + * + * \returns The new table size. + */ + static inline long upResize( long existing, long needed ) + { return EXPN_UP( existing, needed ); } + + /** + * \brief Determine the new table size when down resizing. + * + * If the space needed is less than one quarter of the existing size then + * allocate twice the space needed. Otherwise use the exitsing size. + * + * \returns The new table size. + */ + static inline long downResize( long existing, long needed ) + { return EXPN_DOWN( existing, needed ); } +}; + +#undef EXPN_UP +#undef EXPN_DOWN + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_TABLE_H */ diff --git a/aapl/vector.h b/aapl/vector.h new file mode 100644 index 00000000..835607b1 --- /dev/null +++ b/aapl/vector.h @@ -0,0 +1,1189 @@ +/* + * Copyright 2002, 2006 Adrian Thurston <thurston@cs.queensu.ca> + */ + +/* This file is part of Aapl. + * + * Aapl 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 2.1 of the License, or (at your option) + * any later version. + * + * Aapl 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 Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_VECTOR_H +#define _AAPL_VECTOR_H + +#include <new> +#include <string.h> +#include <stdlib.h> +#include <assert.h> +#include "table.h" + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/** + * \addtogroup vector + * @{ + */ + +/** \class Vector + * \brief Dynamic array. + * + * This is typical vector implementation. It is a dynamic array that can be + * used to contain complex data structures that have constructors and + * destructors as well as simple types such as integers and pointers. + * + * Vector supports inserting, overwriting, and removing single or multiple + * elements at once. Constructors and destructors are called wherever + * appropriate. For example, before an element is overwritten, it's + * destructor is called. + * + * Vector provides automatic resizing of allocated memory as needed and offers + * different allocation schemes for controlling how the automatic allocation + * is done. Two senses of the the length of the data is maintained: the + * amount of raw memory allocated to the vector and the number of actual + * elements in the vector. The various allocation schemes control how the + * allocated space is changed in relation to the number of elements in the + * vector. + * + * \include ex_vector.cpp + */ + +/*@}*/ + +template < class T, class Resize = ResizeExpn > class Vector + : public Table<T>, public Resize +{ +private: + typedef Table<T> BaseTable; + +public: + /** + * \brief Initialize an empty vector with no space allocated. + * + * If a linear resizer is used, the step defaults to 256 units of T. For a + * runtime vector both up and down allocation schemes default to + * Exponential. + */ + Vector() { } + + /** + * \brief Create a vector that contains an initial element. + * + * The vector becomes one element in length. The element's copy + * constructor is used to place the value in the vector. + */ + Vector(const T &val) { setAs(&val, 1); } + + /** + * \brief Create a vector that contains an array of elements. + * + * The vector becomes len elements in length. Copy constructors are used + * to place the new elements in the vector. + */ + Vector(const T *val, long len) { setAs(val, len); } + + /* Deep copy. */ + Vector( const Vector &v ); + + /* Free all mem used by the vector. */ + ~Vector() { empty(); } + + /* Delete all items. */ + void empty(); + + /* Abandon the contents of the vector without deleteing. */ + void abandon(); + + /* Transfers the elements of another vector into this vector. First emptys + * the current vector. */ + void transfer( Vector &v ); + + /* Perform a deep copy of another vector into this vector. */ + Vector &operator=( const Vector &v ); + + /* Stack operations. */ + void push( const T &t ) { append( t ); } + void pop() { remove( BaseTable::tabLen - 1 ); } + T &top() { return BaseTable::data[BaseTable::tabLen - 1]; } + + /*@{*/ + /** + * \brief Insert one element at position pos. + * + * Elements in the vector from pos onward are shifted one space to the + * right. The copy constructor is used to place the element into this + * vector. If pos is greater than the length of the vector then undefined + * behaviour results. If pos is negative then it is treated as an offset + * relative to the length of the vector. + */ + void insert(long pos, const T &val) { insert(pos, &val, 1); } + + /* Insert an array of values. */ + void insert(long pos, const T *val, long len); + + /** + * \brief Insert all the elements from another vector at position pos. + * + * Elements in this vector from pos onward are shifted v.tabLen spaces to + * the right. The element's copy constructor is used to copy the items + * into this vector. The other vector is left unchanged. If pos is off the + * end of the vector, then undefined behaviour results. If pos is negative + * then it is treated as an offset relative to the length of the vector. + * Equivalent to vector.insert(pos, other.data, other.tabLen). + */ + void insert(long pos, const Vector &v) { insert(pos, v.data, v.tabLen); } + + /* Insert len copies of val into the vector. */ + void insertDup(long pos, const T &val, long len); + + /** + * \brief Insert one new element using the default constrcutor. + * + * Elements in the vector from pos onward are shifted one space to the + * right. The default constructor is used to init the new element. If pos + * is greater than the length of the vector then undefined behaviour + * results. If pos is negative then it is treated as an offset relative to + * the length of the vector. + */ + void insertNew(long pos) { insertNew(pos, 1); } + + /* Insert len new items using default constructor. */ + void insertNew(long pos, long len); + /*@}*/ + + /*@{*/ + /** + * \brief Remove one element at position pos. + * + * The element's destructor is called. Elements to the right of pos are + * shifted one space to the left to take up the free space. If pos is greater + * than or equal to the length of the vector then undefined behavior results. + * If pos is negative then it is treated as an offset relative to the length + * of the vector. + */ + void remove(long pos) { remove(pos, 1); } + + /* Delete a number of elements. */ + void remove(long pos, long len); + /*@}*/ + + /*@{*/ + /** + * \brief Replace one element at position pos. + * + * If there is an existing element at position pos (if pos is less than + * the length of the vector) then its destructor is called before the + * space is used. The copy constructor is used to place the element into + * the vector. If pos is greater than the length of the vector then + * undefined behaviour results. If pos is negative then it is treated as + * an offset relative to the length of the vector. + */ + void replace(long pos, const T &val) { replace(pos, &val, 1); } + + /* Replace with an array of values. */ + void replace(long pos, const T *val, long len); + + /** + * \brief Replace at position pos with all the elements of another vector. + * + * Replace at position pos with all the elements of another vector. The + * other vector is left unchanged. If there are existing elements at the + * positions to be replaced, then destructors are called before the space + * is used. Copy constructors are used to place the elements into this + * vector. It is allowable for the pos and length of the other vector to + * specify a replacement that overwrites existing elements and creates new + * ones. If pos is greater than the length of the vector then undefined + * behaviour results. If pos is negative, then it is treated as an offset + * relative to the length of the vector. + */ + void replace(long pos, const Vector &v) { replace(pos, v.data, v.tabLen); } + + /* Replace len items with len copies of val. */ + void replaceDup(long pos, const T &val, long len); + + /** + * \brief Replace at position pos with one new element. + * + * If there is an existing element at the position to be replaced (pos is + * less than the length of the vector) then the element's destructor is + * called before the space is used. The default constructor is used to + * initialize the new element. If pos is greater than the length of the + * vector then undefined behaviour results. If pos is negative, then it is + * treated as an offset relative to the length of the vector. + */ + void replaceNew(long pos) { replaceNew(pos, 1); } + + /* Replace len items at pos with newly constructed objects. */ + void replaceNew(long pos, long len); + /*@}*/ + + /*@{*/ + /** + * \brief Set the contents of the vector to be val exactly. + * + * The vector becomes one element in length. Destructors are called on any + * existing elements in the vector. The element's copy constructor is used + * to place the val in the vector. + */ + void setAs(const T &val) { setAs(&val, 1); } + + /* Set to the contents of an array. */ + void setAs(const T *val, long len); + + /** + * \brief Set the vector to exactly the contents of another vector. + * + * The vector becomes v.tabLen elements in length. Destructors are called + * on any existing elements. Copy constructors are used to place the new + * elements in the vector. + */ + void setAs(const Vector &v) { setAs(v.data, v.tabLen); } + + /* Set as len copies of item. */ + void setAsDup(const T &item, long len); + + /** + * \brief Set the vector to exactly one new item. + * + * The vector becomes one element in length. Destructors are called on any + * existing elements in the vector. The default constructor is used to + * init the new item. + */ + void setAsNew() { setAsNew(1); } + + /* Set as newly constructed objects using the default constructor. */ + void setAsNew(long len); + /*@}*/ + + /*@{*/ + /** + * \brief Append one elment to the end of the vector. + * + * Copy constructor is used to place the element in the vector. + */ + void append(const T &val) { replace(BaseTable::tabLen, &val, 1); } + + /** + * \brief Append len elements to the end of the vector. + * + * Copy constructors are used to place the elements in the vector. + */ + void append(const T *val, long len) { replace(BaseTable::tabLen, val, len); } + + /** + * \brief Append the contents of another vector. + * + * The other vector is left unchanged. Copy constructors are used to place the + * elements in the vector. + */ + void append(const Vector &v) { replace(BaseTable::tabLen, v.data, v.tabLen); } + + /** + * \brief Append len copies of item. + * + * The copy constructor is used to place the item in the vector. + */ + void appendDup(const T &item, long len) { replaceDup(BaseTable::tabLen, item, len); } + + /** + * \brief Append a single newly created item. + * + * The new element is initialized with the default constructor. + */ + void appendNew() { replaceNew(BaseTable::tabLen, 1); } + + /** + * \brief Append len newly created items. + * + * The new elements are initialized with the default constructor. + */ + void appendNew(long len) { replaceNew(BaseTable::tabLen, len); } + /*@}*/ + + /*@{*/ + /** \fn Vector::prepend(const T &val) + * \brief Prepend one elment to the front of the vector. + * + * Copy constructor is used to place the element in the vector. + */ + void prepend(const T &val) { insert(0, &val, 1); } + + /** + * \brief Prepend len elements to the front of the vector. + * + * Copy constructors are used to place the elements in the vector. + */ + void prepend(const T *val, long len) { insert(0, val, len); } + + /** + * \brief Prepend the contents of another vector. + * + * The other vector is left unchanged. Copy constructors are used to place the + * elements in the vector. + */ + void prepend(const Vector &v) { insert(0, v.data, v.tabLen); } + + /** + * \brief Prepend len copies of item. + * + * The copy constructor is used to place the item in the vector. + */ + void prependDup(const T &item, long len) { insertDup(0, item, len); } + + /** + * \brief Prepend a single newly created item. + * + * The new element is initialized with the default constructor. + */ + void prependNew() { insertNew(0, 1); } + + /** + * \brief Prepend len newly created items. + * + * The new elements are initialized with the default constructor. + */ + void prependNew(long len) { insertNew(0, len); } + /*@}*/ + + /* Convenience access. */ + T &operator[](int i) const { return BaseTable::data[i]; } + long size() const { return BaseTable::tabLen; } + + /* Forward this so a ref can be used. */ + struct Iter; + + /* Various classes for setting the iterator */ + struct IterFirst { IterFirst( const Vector &v ) : v(v) { } const Vector &v; }; + struct IterLast { IterLast( const Vector &v ) : v(v) { } const Vector &v; }; + struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; }; + struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; }; + + /** + * \brief Vector Iterator. + * \ingroup iterators + */ + struct Iter + { + /* Construct, assign. */ + Iter() : ptr(0), ptrBeg(0), ptrEnd(0) { } + + /* Construct. */ + Iter( const Vector &v ); + Iter( const IterFirst &vf ); + Iter( const IterLast &vl ); + inline Iter( const IterNext &vn ); + inline Iter( const IterPrev &vp ); + + /* Assign. */ + Iter &operator=( const Vector &v ); + Iter &operator=( const IterFirst &vf ); + Iter &operator=( const IterLast &vl ); + inline Iter &operator=( const IterNext &vf ); + inline Iter &operator=( const IterPrev &vl ); + + /** \brief Less than end? */ + bool lte() const { return ptr != ptrEnd; } + + /** \brief At end? */ + bool end() const { return ptr == ptrEnd; } + + /** \brief Greater than beginning? */ + bool gtb() const { return ptr != ptrBeg; } + + /** \brief At beginning? */ + bool beg() const { return ptr == ptrBeg; } + + /** \brief At first element? */ + bool first() const { return ptr == ptrBeg+1; } + + /** \brief At last element? */ + bool last() const { return ptr == ptrEnd-1; } + + /* Return the position. */ + long pos() const { return ptr - ptrBeg - 1; } + T &operator[](int i) const { return ptr[i]; } + + /** \brief Implicit cast to T*. */ + operator T*() const { return ptr; } + + /** \brief Dereference operator returns T&. */ + T &operator *() const { return *ptr; } + + /** \brief Arrow operator returns T*. */ + T *operator->() const { return ptr; } + + /** \brief Move to next item. */ + T *operator++() { return ++ptr; } + + /** \brief Move to next item. */ + T *operator++(int) { return ptr++; } + + /** \brief Move to next item. */ + T *increment() { return ++ptr; } + + /** \brief Move n items forward. */ + T *operator+=(long n) { return ptr+=n; } + + /** \brief Move to previous item. */ + T *operator--() { return --ptr; } + + /** \brief Move to previous item. */ + T *operator--(int) { return ptr--; } + + /** \brief Move to previous item. */ + T *decrement() { return --ptr; } + + /** \brief Move n items back. */ + T *operator-=(long n) { return ptr-=n; } + + /** \brief Return the next item. Does not modify this. */ + inline IterNext next() const { return IterNext(*this); } + + /** \brief Return the previous item. Does not modify this. */ + inline IterPrev prev() const { return IterPrev(*this); } + + /** \brief The iterator is simply a pointer. */ + T *ptr; + + /* For testing endpoints. */ + T *ptrBeg, *ptrEnd; + }; + + /** \brief Return first element. */ + IterFirst first() { return IterFirst( *this ); } + + /** \brief Return last element. */ + IterLast last() { return IterLast( *this ); } + +protected: + void makeRawSpaceFor(long pos, long len); + + void upResize(long len); + void downResize(long len); +}; + +/* Init a vector iterator with just a vector. */ +template <class T, class Resize> Vector<T, Resize>::Iter::Iter( const Vector &v ) +{ + if ( v.tabLen == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = v.data; + ptrBeg = v.data-1; + ptrEnd = v.data+v.tabLen; + } +} + +/* Init a vector iterator with the first of a vector. */ +template <class T, class Resize> Vector<T, Resize>::Iter::Iter( + const IterFirst &vf ) +{ + if ( vf.v.tabLen == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vf.v.data; + ptrBeg = vf.v.data-1; + ptrEnd = vf.v.data+vf.v.tabLen; + } +} + +/* Init a vector iterator with the last of a vector. */ +template <class T, class Resize> Vector<T, Resize>::Iter::Iter( + const IterLast &vl ) +{ + if ( vl.v.tabLen == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vl.v.data+vl.v.tabLen-1; + ptrBeg = vl.v.data-1; + ptrEnd = vl.v.data+vl.v.tabLen; + } +} + +/* Init a vector iterator with the next of some other iterator. */ +template <class T, class Resize> Vector<T, Resize>::Iter::Iter( + const IterNext &vn ) +: + ptr(vn.i.ptr+1), + ptrBeg(vn.i.ptrBeg), + ptrEnd(vn.i.ptrEnd) +{ +} + +/* Init a vector iterator with the prev of some other iterator. */ +template <class T, class Resize> Vector<T, Resize>::Iter::Iter( + const IterPrev &vp ) +: + ptr(vp.i.ptr-1), + ptrBeg(vp.i.ptrBeg), + ptrEnd(vp.i.ptrEnd) +{ +} + +/* Set a vector iterator with some vector. */ +template <class T, class Resize> typename Vector<T, Resize>::Iter & + Vector<T, Resize>::Iter::operator=( const Vector &v ) +{ + if ( v.tabLen == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = v.data; + ptrBeg = v.data-1; + ptrEnd = v.data+v.tabLen; + } + return *this; +} + +/* Set a vector iterator with the first element in a vector. */ +template <class T, class Resize> typename Vector<T, Resize>::Iter & + Vector<T, Resize>::Iter::operator=( const IterFirst &vf ) +{ + if ( vf.v.tabLen == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vf.v.data; + ptrBeg = vf.v.data-1; + ptrEnd = vf.v.data+vf.v.tabLen; + } + return *this; +} + +/* Set a vector iterator with the last element in a vector. */ +template <class T, class Resize> typename Vector<T, Resize>::Iter & + Vector<T, Resize>::Iter::operator=( const IterLast &vl ) +{ + if ( vl.v.tabLen == 0 ) + ptr = ptrBeg = ptrEnd = 0; + else { + ptr = vl.v.data+vl.v.tabLen-1; + ptrBeg = vl.v.data-1; + ptrEnd = vl.v.data+vl.v.tabLen; + } + return *this; +} + +/* Set a vector iterator with the next of some other iterator. */ +template <class T, class Resize> typename Vector<T, Resize>::Iter & + Vector<T, Resize>::Iter::operator=( const IterNext &vn ) +{ + ptr = vn.i.ptr+1; + ptrBeg = vn.i.ptrBeg; + ptrEnd = vn.i.ptrEnd; + return *this; +} + +/* Set a vector iterator with the prev of some other iterator. */ +template <class T, class Resize> typename Vector<T, Resize>::Iter & + Vector<T, Resize>::Iter::operator=( const IterPrev &vp ) +{ + ptr = vp.i.ptr-1; + ptrBeg = vp.i.ptrBeg; + ptrEnd = vp.i.ptrEnd; + return *this; +} + +/** + * \brief Forget all elements in the vector. + * + * The contents of the vector are reset to null without without the space + * being freed. + */ +template<class T, class Resize> void Vector<T, Resize>:: + abandon() +{ + BaseTable::data = 0; + BaseTable::tabLen = 0; + BaseTable::allocLen = 0; +} + +/** + * \brief Transfer the contents of another vector into this vector. + * + * The dynamic array of the other vector is moved into this vector by + * reference. If this vector is non-empty then its contents are first deleted. + * Afterward the other vector will be empty. + */ +template<class T, class Resize> void Vector<T, Resize>:: + transfer( Vector &v ) +{ + empty(); + + BaseTable::data = v.data; + BaseTable::tabLen = v.tabLen; + BaseTable::allocLen = v.allocLen; + + v.abandon(); +} + +/** + * \brief Deep copy another vector into this vector. + * + * Copies the entire contents of the other vector into this vector. Any + * existing contents are first deleted. Equivalent to setAs. + * + * \returns A reference to this. + */ +template<class T, class Resize> Vector<T, Resize> &Vector<T, Resize>:: + operator=( const Vector &v ) +{ + setAs(v.data, v.tabLen); + return *this; +} + +/* Up resize the data for len elements using Resize::upResize to tell us the + * new tabLen. Reads and writes allocLen. Does not read or write tabLen. */ +template<class T, class Resize> void Vector<T, Resize>:: + upResize(long len) +{ + /* Ask the resizer what the new tabLen will be. */ + long newLen = Resize::upResize(BaseTable::allocLen, len); + + /* Did the data grow? */ + if ( newLen > BaseTable::allocLen ) { + BaseTable::allocLen = newLen; + if ( BaseTable::data != 0 ) { + /* Table exists already, resize it up. */ + BaseTable::data = (T*) realloc( BaseTable::data, sizeof(T) * newLen ); + if ( BaseTable::data == 0 ) + throw std::bad_alloc(); + } + else { + /* Create the data. */ + BaseTable::data = (T*) malloc( sizeof(T) * newLen ); + if ( BaseTable::data == 0 ) + throw std::bad_alloc(); + } + } +} + +/* Down resize the data for len elements using Resize::downResize to determine + * the new tabLen. Reads and writes allocLen. Does not read or write tabLen. */ +template<class T, class Resize> void Vector<T, Resize>:: + downResize(long len) +{ + /* Ask the resizer what the new tabLen will be. */ + long newLen = Resize::downResize( BaseTable::allocLen, len ); + + /* Did the data shrink? */ + if ( newLen < BaseTable::allocLen ) { + BaseTable::allocLen = newLen; + if ( newLen == 0 ) { + /* Simply free the data. */ + free( BaseTable::data ); + BaseTable::data = 0; + } + else { + /* Not shrinking to size zero, realloc it to the smaller size. */ + BaseTable::data = (T*) realloc( BaseTable::data, sizeof(T) * newLen ); + if ( BaseTable::data == 0 ) + throw std::bad_alloc(); + } + } +} + +/** + * \brief Perform a deep copy of the vector. + * + * The contents of the other vector are copied into this vector. This vector + * gets the same allocation size as the other vector. All items are copied + * using the element's copy constructor. + */ +template<class T, class Resize> Vector<T, Resize>:: + Vector(const Vector<T, Resize> &v) +{ + BaseTable::tabLen = v.tabLen; + BaseTable::allocLen = v.allocLen; + + if ( BaseTable::allocLen > 0 ) { + /* Allocate needed space. */ + BaseTable::data = (T*) malloc(sizeof(T) * BaseTable::allocLen); + if ( BaseTable::data == 0 ) + throw std::bad_alloc(); + + /* If there are any items in the src data, copy them in. */ + T *dst = BaseTable::data, *src = v.data; + for (long pos = 0; pos < BaseTable::tabLen; pos++, dst++, src++ ) + new(dst) T(*src); + } + else { + /* Nothing allocated. */ + BaseTable::data = 0; + } +} + +/** \fn Vector::~Vector() + * \brief Free all memory used by the vector. + * + * The vector is reset to zero elements. Destructors are called on all + * elements in the vector. The space allocated for the vector is freed. + */ + + +/** + * \brief Free all memory used by the vector. + * + * The vector is reset to zero elements. Destructors are called on all + * elements in the vector. The space allocated for the vector is freed. + */ +template<class T, class Resize> void Vector<T, Resize>:: + empty() +{ + if ( BaseTable::data != 0 ) { + /* Call All destructors. */ + T *pos = BaseTable::data; + for ( long i = 0; i < BaseTable::tabLen; pos++, i++ ) + pos->~T(); + + /* Free the data space. */ + free( BaseTable::data ); + BaseTable::data = 0; + BaseTable::tabLen = BaseTable::allocLen = 0; + } +} + +/** + * \brief Set the contents of the vector to be len elements exactly. + * + * The vector becomes len elements in length. Destructors are called on any + * existing elements in the vector. Copy constructors are used to place the + * new elements in the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + setAs(const T *val, long len) +{ + /* Call All destructors. */ + long i; + T *pos = BaseTable::data; + for ( i = 0; i < BaseTable::tabLen; pos++, i++ ) + pos->~T(); + + /* Adjust the allocated length. */ + if ( len < BaseTable::tabLen ) + downResize( len ); + else if ( len > BaseTable::tabLen ) + upResize( len ); + + /* Set the new data length to exactly len. */ + BaseTable::tabLen = len; + + /* Copy data in. */ + T *dst = BaseTable::data; + const T *src = val; + for ( i = 0; i < len; i++, dst++, src++ ) + new(dst) T(*src); +} + +/** + * \brief Set the vector to len copies of item. + * + * The vector becomes len elements in length. Destructors are called on any + * existing elements in the vector. The element's copy constructor is used to + * copy the item into the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + setAsDup(const T &item, long len) +{ + /* Call All destructors. */ + T *pos = BaseTable::data; + for ( long i = 0; i < BaseTable::tabLen; pos++, i++ ) + pos->~T(); + + /* Adjust the allocated length. */ + if ( len < BaseTable::tabLen ) + downResize( len ); + else if ( len > BaseTable::tabLen ) + upResize( len ); + + /* Set the new data length to exactly len. */ + BaseTable::tabLen = len; + + /* Copy item in one spot at a time. */ + T *dst = BaseTable::data; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(item); +} + +/** + * \brief Set the vector to exactly len new items. + * + * The vector becomes len elements in length. Destructors are called on any + * existing elements in the vector. Default constructors are used to init the + * new items. + */ +template<class T, class Resize> void Vector<T, Resize>:: + setAsNew(long len) +{ + /* Call All destructors. */ + T *pos = BaseTable::data; + for ( long i = 0; i < BaseTable::tabLen; pos++, i++ ) + pos->~T(); + + /* Adjust the allocated length. */ + if ( len < BaseTable::tabLen ) + downResize( len ); + else if ( len > BaseTable::tabLen ) + upResize( len ); + + /* Set the new data length to exactly len. */ + BaseTable::tabLen = len; + + /* Create items using default constructor. */ + T *dst = BaseTable::data; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(); +} + + +/** + * \brief Replace len elements at position pos. + * + * If there are existing elements at the positions to be replaced, then + * destructors are called before the space is used. Copy constructors are used + * to place the elements into the vector. It is allowable for the pos and + * length to specify a replacement that overwrites existing elements and + * creates new ones. If pos is greater than the length of the vector then + * undefined behaviour results. If pos is negative, then it is treated as an + * offset relative to the length of the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + replace(long pos, const T *val, long len) +{ + long endPos, i; + T *item; + + /* If we are given a negative position to replace at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = BaseTable::tabLen + pos; + + /* The end is the one past the last item that we want + * to write to. */ + endPos = pos + len; + + /* Make sure we have enough space. */ + if ( endPos > BaseTable::tabLen ) { + upResize( endPos ); + + /* Delete any objects we need to delete. */ + item = BaseTable::data + pos; + for ( i = pos; i < BaseTable::tabLen; i++, item++ ) + item->~T(); + + /* We are extending the vector, set the new data length. */ + BaseTable::tabLen = endPos; + } + else { + /* Delete any objects we need to delete. */ + item = BaseTable::data + pos; + for ( i = pos; i < endPos; i++, item++ ) + item->~T(); + } + + /* Copy data in using copy constructor. */ + T *dst = BaseTable::data + pos; + const T *src = val; + for ( i = 0; i < len; i++, dst++, src++ ) + new(dst) T(*src); +} + +/** + * \brief Replace at position pos with len copies of an item. + * + * If there are existing elements at the positions to be replaced, then + * destructors are called before the space is used. The copy constructor is + * used to place the element into this vector. It is allowable for the pos and + * length to specify a replacement that overwrites existing elements and + * creates new ones. If pos is greater than the length of the vector then + * undefined behaviour results. If pos is negative, then it is treated as an + * offset relative to the length of the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + replaceDup(long pos, const T &val, long len) +{ + long endPos, i; + T *item; + + /* If we are given a negative position to replace at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = BaseTable::tabLen + pos; + + /* The end is the one past the last item that we want + * to write to. */ + endPos = pos + len; + + /* Make sure we have enough space. */ + if ( endPos > BaseTable::tabLen ) { + upResize( endPos ); + + /* Delete any objects we need to delete. */ + item = BaseTable::data + pos; + for ( i = pos; i < BaseTable::tabLen; i++, item++ ) + item->~T(); + + /* We are extending the vector, set the new data length. */ + BaseTable::tabLen = endPos; + } + else { + /* Delete any objects we need to delete. */ + item = BaseTable::data + pos; + for ( i = pos; i < endPos; i++, item++ ) + item->~T(); + } + + /* Copy data in using copy constructor. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(val); +} + +/** + * \brief Replace at position pos with len new elements. + * + * If there are existing elements at the positions to be replaced, then + * destructors are called before the space is used. The default constructor is + * used to initialize the new elements. It is allowable for the pos and length + * to specify a replacement that overwrites existing elements and creates new + * ones. If pos is greater than the length of the vector then undefined + * behaviour results. If pos is negative, then it is treated as an offset + * relative to the length of the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + replaceNew(long pos, long len) +{ + long endPos, i; + T *item; + + /* If we are given a negative position to replace at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = BaseTable::tabLen + pos; + + /* The end is the one past the last item that we want + * to write to. */ + endPos = pos + len; + + /* Make sure we have enough space. */ + if ( endPos > BaseTable::tabLen ) { + upResize( endPos ); + + /* Delete any objects we need to delete. */ + item = BaseTable::data + pos; + for ( i = pos; i < BaseTable::tabLen; i++, item++ ) + item->~T(); + + /* We are extending the vector, set the new data length. */ + BaseTable::tabLen = endPos; + } + else { + /* Delete any objects we need to delete. */ + item = BaseTable::data + pos; + for ( i = pos; i < endPos; i++, item++ ) + item->~T(); + } + + /* Copy data in using copy constructor. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(); +} + +/** + * \brief Remove len elements at position pos. + * + * Destructor is called on all elements removed. Elements to the right of pos + * are shifted len spaces to the left to take up the free space. If pos is + * greater than or equal to the length of the vector then undefined behavior + * results. If pos is negative then it is treated as an offset relative to the + * length of the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + remove(long pos, long len) +{ + long newLen, lenToSlideOver, endPos; + T *dst, *item; + + /* If we are given a negative position to remove at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = BaseTable::tabLen + pos; + + /* The first position after the last item deleted. */ + endPos = pos + len; + + /* The new data length. */ + newLen = BaseTable::tabLen - len; + + /* The place in the data we are deleting at. */ + dst = BaseTable::data + pos; + + /* Call Destructors. */ + item = dst; + for ( long i = 0; i < len; i += 1, item += 1 ) + item->~T(); + + /* Shift data over if necessary. */ + lenToSlideOver = BaseTable::tabLen - endPos; + if ( len > 0 && lenToSlideOver > 0 ) + memmove(dst, dst + len, sizeof(T)*lenToSlideOver); + + /* Shrink the data if necessary. */ + downResize( newLen ); + + /* Set the new data length. */ + BaseTable::tabLen = newLen; +} + +/** + * \brief Insert len elements at position pos. + * + * Elements in the vector from pos onward are shifted len spaces to the right. + * The copy constructor is used to place the elements into this vector. If pos + * is greater than the length of the vector then undefined behaviour results. + * If pos is negative then it is treated as an offset relative to the length + * of the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + insert(long pos, const T *val, long len) +{ + /* If we are given a negative position to insert at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = BaseTable::tabLen + pos; + + /* Calculate the new length. */ + long newLen = BaseTable::tabLen + len; + + /* Up resize, we are growing. */ + upResize( newLen ); + + /* Shift over data at insert spot if needed. */ + if ( len > 0 && pos < BaseTable::tabLen ) { + memmove(BaseTable::data + pos + len, BaseTable::data + pos, + sizeof(T)*(BaseTable::tabLen-pos)); + } + + /* Copy data in element by element. */ + T *dst = BaseTable::data + pos; + const T *src = val; + for ( long i = 0; i < len; i++, dst++, src++ ) + new(dst) T(*src); + + /* Set the new length. */ + BaseTable::tabLen = newLen; +} + +/** + * \brief Insert len copies of item at position pos. + * + * Elements in the vector from pos onward are shifted len spaces to the right. + * The copy constructor is used to place the element into this vector. If pos + * is greater than the length of the vector then undefined behaviour results. + * If pos is negative then it is treated as an offset relative to the length + * of the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + insertDup(long pos, const T &item, long len) +{ + /* If we are given a negative position to insert at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = BaseTable::tabLen + pos; + + /* Calculate the new length. */ + long newLen = BaseTable::tabLen + len; + + /* Up resize, we are growing. */ + upResize( newLen ); + + /* Shift over data at insert spot if needed. */ + if ( len > 0 && pos < BaseTable::tabLen ) { + memmove(BaseTable::data + pos + len, BaseTable::data + pos, + sizeof(T)*(BaseTable::tabLen-pos)); + } + + /* Copy the data item in one at a time. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(item); + + /* Set the new length. */ + BaseTable::tabLen = newLen; +} + +/** + * \brief Insert len new elements using the default constructor. + * + * Elements in the vector from pos onward are shifted len spaces to the right. + * Default constructors are used to init the new elements. If pos is off the + * end of the vector then undefined behaviour results. If pos is negative then + * it is treated as an offset relative to the length of the vector. + */ +template<class T, class Resize> void Vector<T, Resize>:: + insertNew(long pos, long len) +{ + /* If we are given a negative position to insert at then + * treat it as a position relative to the length. */ + if ( pos < 0 ) + pos = BaseTable::tabLen + pos; + + /* Calculate the new length. */ + long newLen = BaseTable::tabLen + len; + + /* Up resize, we are growing. */ + upResize( newLen ); + + /* Shift over data at insert spot if needed. */ + if ( len > 0 && pos < BaseTable::tabLen ) { + memmove(BaseTable::data + pos + len, BaseTable::data + pos, + sizeof(T)*(BaseTable::tabLen-pos)); + } + + /* Init new data with default constructors. */ + T *dst = BaseTable::data + pos; + for ( long i = 0; i < len; i++, dst++ ) + new(dst) T(); + + /* Set the new length. */ + BaseTable::tabLen = newLen; +} + +/* Makes space for len items, Does not init the items in any way. If pos is + * greater than the length of the vector then undefined behaviour results. + * Updates the length of the vector. */ +template<class T, class Resize> void Vector<T, Resize>:: + makeRawSpaceFor(long pos, long len) +{ + /* Calculate the new length. */ + long newLen = BaseTable::tabLen + len; + + /* Up resize, we are growing. */ + upResize( newLen ); + + /* Shift over data at insert spot if needed. */ + if ( len > 0 && pos < BaseTable::tabLen ) { + memmove(BaseTable::data + pos + len, BaseTable::data + pos, + sizeof(T)*(BaseTable::tabLen-pos)); + } + + /* Save the new length. */ + BaseTable::tabLen = newLen; +} + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_VECTOR_H */ |