Source Code Cross Referenced for LongRangeSet.java in  » Development » PCJ » bak » pcj » set » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Development » PCJ » bak.pcj.set 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


0001:        /*
0002:         *  Primitive Collections for Java.
0003:         *  Copyright (C) 2002  Søren Bak
0004:         *
0005:         *  This library is free software; you can redistribute it and/or
0006:         *  modify it under the terms of the GNU Lesser General Public
0007:         *  License as published by the Free Software Foundation; either
0008:         *  version 2.1 of the License, or (at your option) any later version.
0009:         *
0010:         *  This library is distributed in the hope that it will be useful,
0011:         *  but WITHOUT ANY WARRANTY; without even the implied warranty of
0012:         *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0013:         *  Lesser General Public License for more details.
0014:         *
0015:         *  You should have received a copy of the GNU Lesser General Public
0016:         *  License along with this library; if not, write to the Free Software
0017:         *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
0018:         */
0019:        package bak.pcj.set;
0020:
0021:        import bak.pcj.LongIterator;
0022:        import bak.pcj.LongCollection;
0023:        import bak.pcj.util.Exceptions;
0024:
0025:        import java.util.ArrayList;
0026:        import java.util.NoSuchElementException;
0027:        import java.io.Serializable;
0028:
0029:        /**
0030:         *  This class represents range based sets of long values.
0031:         *  The implementation is optimized for cases where most set elements
0032:         *  fall into ranges of consecutive long values.
0033:         *
0034:         *  <p>Implementation of
0035:         *  LongSortedSet is supported from PCJ 1.2. Prior to 1.2, only LongSet
0036:         *  was implemented.
0037:         *
0038:         *  @see        LongRange
0039:         *
0040:         *  @author     S&oslash;ren Bak
0041:         *  @version    1.3     20-08-2003 22:24
0042:         *  @since      1.0
0043:         */
0044:        public class LongRangeSet extends AbstractLongSet implements 
0045:                LongSortedSet, Cloneable, Serializable {
0046:
0047:            /**
0048:             *  The ranges of this set. Must always be sorted and normalized (non-adjacent and non-overlapping).
0049:             *  @serial
0050:             */
0051:            private ArrayList ranges;
0052:
0053:            /**
0054:             *  The size of this set.
0055:             *  @serial
0056:             */
0057:            private int size;
0058:
0059:            /**
0060:             *  Creates a new empty range set.
0061:             */
0062:            public LongRangeSet() {
0063:                ranges = new ArrayList();
0064:                size = 0;
0065:            }
0066:
0067:            /**
0068:             *  Creates a new empty range set containing specified values.
0069:             *
0070:             *  @param      a
0071:             *              the values that the new set should contain.
0072:             *
0073:             *  @throws     NullPointerException
0074:             *              if <tt>a</tt> is <tt>null</tt>.
0075:             */
0076:            public LongRangeSet(long[] a) {
0077:                this ();
0078:                addAll(a);
0079:            }
0080:
0081:            /**
0082:             *  Creates a new range set with the same elements as a specified
0083:             *  collection.
0084:             *
0085:             *  @param      c
0086:             *              the collection whose elements to add to the new
0087:             *              set.
0088:             *
0089:             *  @throws     NullPointerException
0090:             *              if <tt>c</tt> is <tt>null</tt>.
0091:             */
0092:            public LongRangeSet(LongCollection c) {
0093:                this ();
0094:                addAll(c);
0095:            }
0096:
0097:            // ---------------------------------------------------------------
0098:            //      Range management
0099:            // ---------------------------------------------------------------
0100:
0101:            /**
0102:             *  Returns a specified range.
0103:             *
0104:             *  @param      index
0105:             *              the index of the range to return.
0106:             *
0107:             *  @throws     IndexOutOfBoundsException
0108:             *              if <tt>index/tt> does not denote a valid range
0109:             *              number.
0110:             */
0111:            private LongRange range(int index) {
0112:                return (LongRange) ranges.get(index);
0113:            }
0114:
0115:            /**
0116:             *  Returns the range of a specified value.
0117:             *
0118:             *  @param      v
0119:             *              the value to search for.
0120:             *
0121:             *  @return     the range containing the specified value; returns
0122:             *              <tt>null</tt> if no range contains the specified
0123:             *              value.
0124:             */
0125:            private LongRange getRangeOf(long v) {
0126:                int index = getRangeIndexOf(v);
0127:                return index >= 0 ? range(index) : null;
0128:            }
0129:
0130:            /**
0131:             *  Returns the range index of a specified value.
0132:             *
0133:             *  @param      v
0134:             *              the value to search for.
0135:             *
0136:             *  @return     the index of the range containing the specified
0137:             *              value; returns <tt>(-(<i>insertion point</i>) - 1)</tt>
0138:             *              if no range contains the specified value.
0139:             */
0140:            private int getRangeIndexOf(long v) {
0141:                if (size == 0)
0142:                    return -1;
0143:                //  Binary search
0144:                LongRange r;
0145:                int lo = 0;
0146:                int hi = ranges.size() - 1;
0147:                int mid;
0148:                while (lo <= hi) {
0149:                    mid = (lo + hi) / 2;
0150:                    r = (LongRange) ranges.get(mid);
0151:                    if (r.contains(v))
0152:                        return mid;
0153:                    if (v < r.first()) {
0154:                        hi = mid - 1;
0155:                    } else { // v > r.last()
0156:                        lo = mid + 1;
0157:                    }
0158:                }
0159:                return -(lo + 1);
0160:            }
0161:
0162:            /**
0163:             *  Inserts a range at the sorted position in the ranges.
0164:             *
0165:             *  @param      range
0166:             *              the range to insert.
0167:             *
0168:             *  @return     the insertion index; returns <tt>-1</tt> if an
0169:             *              equal range existed in the ranges.
0170:             */
0171:            private int insertRange(LongRange range) {
0172:                //  Binary search
0173:                LongRange r;
0174:                int lo = 0;
0175:                int hi = ranges.size() - 1;
0176:                int mid;
0177:                while (lo <= hi) {
0178:                    mid = (lo + hi) / 2;
0179:                    r = range(mid);
0180:                    int compare = range.compareTo(r);
0181:                    if (compare == 0)
0182:                        return -1;
0183:                    if (compare < 0) {
0184:                        hi = mid - 1;
0185:                    } else { // compare > 0
0186:                        lo = mid + 1;
0187:                    }
0188:                }
0189:                ranges.add(lo, range);
0190:                return lo;
0191:            }
0192:
0193:            /**
0194:             *  Normalizes the ranges after the insertion of a new range and
0195:             *  recalculates the size of this set. The range list must be
0196:             *  sorted when this method is invoked.
0197:             *
0198:             *  @param      index
0199:             *              the index at which to start the normalization.
0200:             *              Usually the index before a new range was inserted.
0201:             */
0202:            private void normalize(int index) {
0203:                while (index < ranges.size() - 1) {
0204:                    LongRange r1 = range(index);
0205:                    LongRange r2 = range(index + 1);
0206:                    LongRange r3 = r1.tryMergeWith(r2);
0207:                    if (r3 == null)
0208:                        break;
0209:                    ranges.set(index, r3);
0210:                    ranges.remove(index + 1);
0211:                    size -= r1.intersectionLength(r2);
0212:                }
0213:            }
0214:
0215:            /**
0216:             *  Normalizes all ranges and recalculates the size of this set.
0217:             *  The method is usually called when the whole range list has
0218:             *  changed.  The range list must be sorted when this method is
0219:             *  invoked.
0220:             */
0221:            private void normalize() {
0222:                int index = 0;
0223:                size = 0;
0224:                LongRange r1, r2, r3;
0225:                while (index < ranges.size() - 1) {
0226:                    r1 = range(index);
0227:                    r2 = range(index + 1);
0228:                    r3 = r1.tryMergeWith(r2);
0229:                    if (r3 != null) {
0230:                        ranges.set(index, r3);
0231:                        ranges.remove(index + 1);
0232:                    } else {
0233:                        size += r1.length();
0234:                        index++;
0235:                    }
0236:                }
0237:                r3 = range(ranges.size() - 1);
0238:                size += r3.length();
0239:            }
0240:
0241:            // ---------------------------------------------------------------
0242:            //      Operations not supported by abstract implementation
0243:            // ---------------------------------------------------------------
0244:
0245:            public boolean add(long v) {
0246:                int index = getRangeIndexOf(v);
0247:                if (index >= 0)
0248:                    return false;
0249:                int insertionIndex = -index - 1;
0250:                ranges.add(insertionIndex, new LongRange(v, v));
0251:                if (insertionIndex > 0)
0252:                    insertionIndex--;
0253:                size++;
0254:                normalize(insertionIndex);
0255:                return true;
0256:            }
0257:
0258:            public LongIterator iterator() {
0259:                return new LongIterator() {
0260:                    int nextIndex = 0;
0261:                    int lastIndex = -1;
0262:                    int currRange = 0;
0263:                    int currOffset = 0;
0264:                    long lastValue;
0265:
0266:                    public boolean hasNext() {
0267:                        return nextIndex < size;
0268:                    }
0269:
0270:                    public long next() {
0271:                        if (nextIndex >= size)
0272:                            Exceptions.endOfIterator();
0273:                        lastIndex = nextIndex;
0274:                        lastValue = curr();
0275:                        nextIndex++;
0276:                        if (nextIndex < size) {
0277:                            if (currOffset == range(currRange).length() - 1) {
0278:                                currRange++;
0279:                                currOffset = 0;
0280:                            } else {
0281:                                currOffset++;
0282:                            }
0283:                        }
0284:                        return lastValue;
0285:                    }
0286:
0287:                    public void remove() {
0288:                        if (lastIndex == -1)
0289:                            Exceptions.noElementToRemove();
0290:                        LongRangeSet.this .remove(lastValue);
0291:                        nextIndex--;
0292:                        if (nextIndex < size)
0293:                            recalc();
0294:                        lastIndex = -1;
0295:                    }
0296:
0297:                    private long curr() {
0298:                        return (long) (range(currRange).first() + currOffset);
0299:                    }
0300:
0301:                    private void recalc() {
0302:                        currRange = 0;
0303:                        currOffset = nextIndex;
0304:                        for (;;) {
0305:                            int rs = range(currRange).length();
0306:                            if (currOffset < rs)
0307:                                break;
0308:                            currOffset -= rs;
0309:                            currRange++;
0310:                        }
0311:                    }
0312:
0313:                };
0314:            }
0315:
0316:            /**
0317:             *  @since      1.2
0318:             */
0319:            public long first() {
0320:                if (size == 0)
0321:                    Exceptions.setNoFirst();
0322:                return range(0).first();
0323:            }
0324:
0325:            private long firstFrom(long v) {
0326:                int index = getRangeIndexOf(v);
0327:                if (index >= 0)
0328:                    return v;
0329:                //  Get first range after calculated insertion point.
0330:                //  index is now (-(insertion point)-1), so the insertion point
0331:                //  is -index-1
0332:                index = -index - 1;
0333:                if (index >= ranges.size())
0334:                    Exceptions.setNoFirst();
0335:                return range(index).first();
0336:            }
0337:
0338:            /**
0339:             *  @since      1.2
0340:             */
0341:            public long last() {
0342:                if (size == 0)
0343:                    Exceptions.setNoLast();
0344:                return range(ranges.size() - 1).last();
0345:            }
0346:
0347:            private long lastFrom(long v) {
0348:                int index = getRangeIndexOf(v);
0349:                if (index >= 0)
0350:                    return v;
0351:                //  Get first range before calculated insertion point.
0352:                //  index is now (-(insertion point)-1), so the insertion point
0353:                //  is -index-1
0354:                index = -index - 1;
0355:                index--;
0356:                if (index < 0 || index >= ranges.size())
0357:                    Exceptions.setNoLast();
0358:                return range(index).last();
0359:            }
0360:
0361:            /**
0362:             *  @since      1.2
0363:             */
0364:            public LongSortedSet headSet(long to) {
0365:                return new SubSet(false, (long) 0, true, to);
0366:            }
0367:
0368:            /**
0369:             *  @since      1.2
0370:             */
0371:            public LongSortedSet tailSet(long from) {
0372:                return new SubSet(true, from, false, (long) 0);
0373:            }
0374:
0375:            /**
0376:             *  @since      1.2
0377:             */
0378:            public LongSortedSet subSet(long from, long to) {
0379:                return new SubSet(true, from, true, to);
0380:            }
0381:
0382:            private class SubSet extends AbstractLongSet implements 
0383:                    LongSortedSet, java.io.Serializable {
0384:
0385:                private boolean hasLowerBound;
0386:                private boolean hasUpperBound;
0387:                private long lowerBound;
0388:                private long upperBound;
0389:
0390:                SubSet(boolean hasLowerBound, long lowerBound,
0391:                        boolean hasUpperBound, long upperBound) {
0392:                    if (hasLowerBound) {
0393:                        if (lowerBound < 0)
0394:                            Exceptions.negativeArgument("lower bound", String
0395:                                    .valueOf(lowerBound));
0396:                        if (hasUpperBound)
0397:                            if (upperBound < lowerBound)
0398:                                Exceptions.invalidSetBounds(String
0399:                                        .valueOf(lowerBound), String
0400:                                        .valueOf(upperBound));
0401:                    }
0402:                    this .hasLowerBound = hasLowerBound;
0403:                    this .lowerBound = lowerBound;
0404:                    this .hasUpperBound = hasUpperBound;
0405:                    this .upperBound = upperBound;
0406:                }
0407:
0408:                public boolean add(long v) {
0409:                    if (!inSubRange(v))
0410:                        Exceptions.valueNotInSubRange(String.valueOf(v));
0411:                    return LongRangeSet.this .add(v);
0412:                }
0413:
0414:                public boolean remove(long v) {
0415:                    if (!inSubRange(v))
0416:                        Exceptions.valueNotInSubRange(String.valueOf(v));
0417:                    return LongRangeSet.this .remove(v);
0418:                }
0419:
0420:                public boolean contains(long v) {
0421:                    return inSubRange(v) && LongRangeSet.this .contains(v);
0422:                }
0423:
0424:                class EmptySubSetIterator implements  LongIterator {
0425:                    public boolean hasNext() {
0426:                        return false;
0427:                    }
0428:
0429:                    public long next() {
0430:                        Exceptions.endOfIterator();
0431:                        throw new RuntimeException();
0432:                    }
0433:
0434:                    public void remove() {
0435:                        Exceptions.noElementToRemove();
0436:                    }
0437:                }
0438:
0439:                class SimpleSubSetIterator implements  LongIterator {
0440:                    int nextIndex;
0441:                    int size;
0442:                    int lastIndex;
0443:                    long lastValue;
0444:                    long from;
0445:                    long to;
0446:
0447:                    SimpleSubSetIterator(long from, long to) {
0448:                        size = (int) (to - from + 1);
0449:                        nextIndex = 0;
0450:                        lastIndex = -1;
0451:                        this .from = from;
0452:                        this .to = to;
0453:                    }
0454:
0455:                    public boolean hasNext() {
0456:                        return nextIndex < size;
0457:                    }
0458:
0459:                    public long next() {
0460:                        if (!hasNext())
0461:                            Exceptions.endOfIterator();
0462:                        lastValue = (long) (from + nextIndex);
0463:                        lastIndex = nextIndex;
0464:                        nextIndex++;
0465:                        return lastValue;
0466:                    }
0467:
0468:                    public void remove() {
0469:                        if (lastIndex == -1)
0470:                            Exceptions.noElementToRemove();
0471:                        LongRangeSet.this .remove(lastValue);
0472:                        lastIndex = -1;
0473:                    }
0474:
0475:                }
0476:
0477:                class NonEmptySubSetIterator implements  LongIterator {
0478:                    long first;
0479:                    long last;
0480:                    int rangeIndexLow;
0481:                    int rangeIndexHigh;
0482:                    LongRange rangeLow;
0483:                    LongRange rangeHigh;
0484:                    long previousValue;
0485:                    LongRange currRange;
0486:                    int currRangeIndex;
0487:                    int currOffset;
0488:                    boolean valueAvailable;
0489:                    int nextIndex;
0490:
0491:                    NonEmptySubSetIterator(long first, long last,
0492:                            int rangeIndexLow, int rangeIndexHigh) {
0493:                        if (rangeIndexLow == rangeIndexHigh)
0494:                            throw new RuntimeException("Internal error");
0495:                        this .first = first;
0496:                        this .last = last;
0497:                        this .rangeIndexLow = rangeIndexLow;
0498:                        this .rangeIndexHigh = rangeIndexHigh;
0499:                        rangeLow = new LongRange(first, range(rangeIndexLow)
0500:                                .last());
0501:                        rangeHigh = new LongRange(
0502:                                range(rangeIndexHigh).first(), last);
0503:                        currRangeIndex = rangeIndexLow;
0504:                        currRange = rangeLow;
0505:                        currOffset = 0;
0506:                        previousValue = first;
0507:                        valueAvailable = false;
0508:                        nextIndex = 0;
0509:                    }
0510:
0511:                    private LongRange getRange(int rangeIndex) {
0512:                        if (rangeIndex == rangeIndexLow)
0513:                            return rangeLow;
0514:                        if (rangeIndex == rangeIndexHigh)
0515:                            return rangeHigh;
0516:                        return range(rangeIndex);
0517:                    }
0518:
0519:                    private void recalc() {
0520:                        first = first();
0521:                        last = last();
0522:
0523:                        rangeIndexLow = getRangeIndexOf(first);
0524:                        rangeIndexHigh = getRangeIndexOf(last);
0525:                        if (rangeIndexLow == rangeIndexHigh)
0526:                            rangeLow = rangeHigh = new LongRange(first, last);
0527:                        else {
0528:                            rangeLow = new LongRange(first,
0529:                                    range(rangeIndexLow).last());
0530:                            rangeHigh = new LongRange(range(rangeIndexHigh)
0531:                                    .first(), last);
0532:                        }
0533:                        currOffset = nextIndex;
0534:                        currRangeIndex = rangeIndexLow;
0535:                        currRange = rangeLow;
0536:                        for (;;) {
0537:                            int rs = currRange.length();
0538:                            if (currOffset < rs)
0539:                                break;
0540:                            currOffset -= rs;
0541:                            currRange = getRange(++currRangeIndex);
0542:                        }
0543:                    }
0544:
0545:                    public boolean hasNext() {
0546:                        return previousValue < last;
0547:                    }
0548:
0549:                    public long next() {
0550:                        if (!hasNext())
0551:                            Exceptions.endOfIterator();
0552:                        previousValue = (long) (currRange.first() + currOffset++);
0553:                        if (currOffset == currRange.length()
0554:                                && previousValue < last) {
0555:                            currOffset = 0;
0556:                            currRange = getRange(++currRangeIndex);
0557:                        }
0558:                        nextIndex++;
0559:                        valueAvailable = true;
0560:                        return previousValue;
0561:                    }
0562:
0563:                    public void remove() {
0564:                        if (!valueAvailable)
0565:                            Exceptions.noElementToRemove();
0566:                        LongRangeSet.this .remove(previousValue);
0567:                        nextIndex--;
0568:                        recalc();
0569:                        valueAvailable = false;
0570:                    }
0571:                }
0572:
0573:                public LongIterator iterator() {
0574:                    long first;
0575:                    long last;
0576:                    int rangeIndexLow;
0577:                    int rangeIndexHigh;
0578:
0579:                    try {
0580:                        first = first();
0581:                    } catch (NoSuchElementException e) {
0582:                        return new EmptySubSetIterator();
0583:                    }
0584:                    last = last();
0585:                    rangeIndexLow = getRangeIndexOf(first);
0586:                    rangeIndexHigh = getRangeIndexOf(last);
0587:                    if (rangeIndexLow == rangeIndexHigh)
0588:                        return new SimpleSubSetIterator(first, last);
0589:                    return new NonEmptySubSetIterator(first, last,
0590:                            rangeIndexLow, rangeIndexHigh);
0591:                }
0592:
0593:                public int size() {
0594:                    if (LongRangeSet.this .size() == 0)
0595:                        return 0;
0596:                    int size;
0597:                    long first;
0598:                    int rangeIndexLow;
0599:                    try {
0600:                        first = first();
0601:                        rangeIndexLow = getRangeIndexOf(first);
0602:                    } catch (NoSuchElementException e) {
0603:                        return 0;
0604:                    }
0605:                    long last = last();
0606:                    int rangeIndexHigh = getRangeIndexOf(last);
0607:                    if (rangeIndexLow == rangeIndexHigh) {
0608:                        size = (int) (last - first + 1);
0609:                    } else {
0610:                        LongRange rangeLow = range(rangeIndexLow);
0611:                        LongRange rangeHigh = range(rangeIndexHigh);
0612:                        int sizeLow = (int) (rangeLow.last() - first + 1);
0613:                        int sizeHigh = (int) (last - rangeHigh.first() + 1);
0614:
0615:                        size = sizeLow + sizeHigh;
0616:                        for (int i = rangeIndexLow + 1; i < rangeIndexHigh; i++)
0617:                            size += range(i).length();
0618:                    }
0619:                    return size;
0620:                }
0621:
0622:                public long first() {
0623:                    long first = firstFrom(hasLowerBound ? lowerBound : 0);
0624:                    if (hasUpperBound && first >= upperBound)
0625:                        Exceptions.setNoFirst();
0626:                    return first;
0627:                }
0628:
0629:                public long last() {
0630:                    long last = lastFrom(hasUpperBound ? (long) (upperBound - 1)
0631:                            : LongRangeSet.this .last());
0632:                    if (hasLowerBound && last < lowerBound)
0633:                        Exceptions.setNoLast();
0634:                    return last;
0635:                }
0636:
0637:                public LongSortedSet headSet(long to) {
0638:                    if (!inSubRange(to))
0639:                        Exceptions.invalidUpperBound(String.valueOf(to));
0640:                    return new SubSet(hasLowerBound, lowerBound, true, to);
0641:                }
0642:
0643:                public LongSortedSet tailSet(long from) {
0644:                    if (!inSubRange(from))
0645:                        Exceptions.invalidLowerBound(String.valueOf(from));
0646:                    return new SubSet(true, from, hasUpperBound, upperBound);
0647:                }
0648:
0649:                public LongSortedSet subSet(long from, long to) {
0650:                    if (!inSubRange(from))
0651:                        Exceptions.invalidLowerBound(String.valueOf(from));
0652:                    if (!inSubRange(to))
0653:                        Exceptions.invalidUpperBound(String.valueOf(to));
0654:                    return new SubSet(true, from, true, to);
0655:                }
0656:
0657:                private boolean inSubRange(long v) {
0658:                    if (hasLowerBound && v < lowerBound)
0659:                        return false;
0660:                    if (hasUpperBound && v >= upperBound)
0661:                        return false;
0662:                    return true;
0663:                }
0664:
0665:            }
0666:
0667:            public String toString() {
0668:                StringBuffer s = new StringBuffer();
0669:                s.append('[');
0670:                for (int i = 0, rsize = ranges.size(); i < rsize; i++) {
0671:                    if (i > 0)
0672:                        s.append(',');
0673:                    s.append(range(i));
0674:                }
0675:                s.append(']');
0676:                return s.toString();
0677:            }
0678:
0679:            public void trimToSize() {
0680:                //ranges.trimToSize();
0681:            }
0682:
0683:            /**
0684:             *  Returns a clone of this range set.
0685:             *
0686:             *  @return     a clone of this range set.
0687:             *
0688:             *  @since      1.1
0689:             */
0690:            public Object clone() {
0691:                try {
0692:                    LongRangeSet c = (LongRangeSet) super .clone();
0693:                    c.ranges = (ArrayList) ranges.clone();
0694:                    return c;
0695:                } catch (CloneNotSupportedException e) {
0696:                    Exceptions.cloning();
0697:                    throw new RuntimeException();
0698:                }
0699:            }
0700:
0701:            // ---------------------------------------------------------------
0702:            //      Operations overwritten for efficiency
0703:            // ---------------------------------------------------------------
0704:
0705:            public void clear() {
0706:                ranges.clear();
0707:                size = 0;
0708:            }
0709:
0710:            public boolean contains(long v) {
0711:                return getRangeIndexOf(v) >= 0;
0712:            }
0713:
0714:            public int hashCode() {
0715:                int h = 0;
0716:                for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) {
0717:                    LongRange r = range(i);
0718:                    for (long c = r.first(), last = r.last(); c <= last; c++)
0719:                        h += c;
0720:                }
0721:                return h;
0722:            }
0723:
0724:            public boolean isEmpty() {
0725:                return size == 0;
0726:            }
0727:
0728:            public int size() {
0729:                return size;
0730:            }
0731:
0732:            public boolean remove(long v) {
0733:                int index = getRangeIndexOf(v);
0734:                if (index < 0)
0735:                    return false;
0736:                //  Treat end points special since we can avoid splitting a range
0737:                LongRange r = range(index);
0738:                if (v == r.first()) {
0739:                    if (r.length() == 1)
0740:                        ranges.remove(index);
0741:                    else
0742:                        ranges.set(index, new LongRange((long) (r.first() + 1),
0743:                                r.last()));
0744:                } else if (v == r.last()) {
0745:                    //  r.length() > 1
0746:                    ranges.set(index, new LongRange(r.first(),
0747:                            (long) (r.last() - 1)));
0748:                } else {
0749:                    //  Split the range
0750:                    LongRange r1 = new LongRange(r.first(), (long) (v - 1));
0751:                    LongRange r2 = new LongRange((long) (v + 1), r.last());
0752:                    ranges.set(index, r1);
0753:                    ranges.add(index + 1, r2);
0754:                }
0755:                size--;
0756:                return true;
0757:            }
0758:
0759:            public long[] toArray(long[] a) {
0760:                if (a == null || a.length < size)
0761:                    a = new long[size];
0762:                for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) {
0763:                    LongRange r = range(i);
0764:                    for (long c = r.first(), last = r.last(); c <= last; c++)
0765:                        a[index++] = c;
0766:                }
0767:                return a;
0768:            }
0769:
0770:            // ---------------------------------------------------------------
0771:            //      Extra operations
0772:            // ---------------------------------------------------------------
0773:
0774:            /**
0775:             *  Indicates whether all elements of a specified
0776:             *  range is contained in this set.
0777:             *
0778:             *  @param      range
0779:             *              the range whose elements to test for
0780:             *              containment.
0781:             *
0782:             *  @return     <tt>true</tt> if all the elements of <tt>range</tt>
0783:             *              are contained in this collection; returns
0784:             *              <tt>false</tt> otherwise.
0785:             *
0786:             *  @throws     NullPointerException
0787:             *              if <tt>range</tt> is <tt>null</tt>.
0788:             *
0789:             *  @see        #containsAll(LongCollection)
0790:             */
0791:            public boolean containsAll(LongRange range) {
0792:                /*
0793:                    In order for the set to contain the whole range
0794:                    the two range ends must be represented by the same
0795:                    range in the range list.
0796:                 */
0797:                LongRange r = getRangeOf(range.first());
0798:                return r != null ? r.contains(range.last()) : false;
0799:            }
0800:
0801:            /**
0802:             *  Adds all the elements of a specified range set to
0803:             *  this set.
0804:             *
0805:             *  @param      c
0806:             *              the set whose elements to add to this
0807:             *              set.
0808:             *
0809:             *  @return     <tt>true</tt> if this set was modified
0810:             *              as a result of adding the elements of <tt>c</tt>;
0811:             *              returns <tt>false</tt> otherwise.
0812:             *
0813:             *  @throws     NullPointerException
0814:             *              if <tt>c</tt> is <tt>null</tt>.
0815:             *
0816:             *  @see        #add(long)
0817:             *  @see        #addAll(LongRange)
0818:             *  @see        #addAll(LongCollection)
0819:             *  @see        #addAll(long, long)
0820:             *  @see        #addAll(long[])
0821:             */
0822:            public boolean addAll(LongRangeSet c) {
0823:                int oldSize = size;
0824:                for (int i = 0, rsize = c.ranges.size(); i < rsize; i++)
0825:                    addAll(c.range(i));
0826:                return size != oldSize;
0827:            }
0828:
0829:            /**
0830:             *  Adds a specified range to this set.
0831:             *
0832:             *  @param      range
0833:             *              the range to add to this set.
0834:             *
0835:             *  @return     <tt>true</tt> if this set was modified
0836:             *              as a result of adding the elements of
0837:             *              <tt>range</tt>; returns <tt>false</tt> otherwise.
0838:             *
0839:             *  @throws     NullPointerException
0840:             *              if <tt>range</tt> is <tt>null</tt>.
0841:             *
0842:             *  @see        #add(long)
0843:             *  @see        #addAll(LongRangeSet)
0844:             *  @see        #addAll(LongCollection)
0845:             *  @see        #addAll(long, long)
0846:             *  @see        #addAll(long[])
0847:             */
0848:            public boolean addAll(LongRange range) {
0849:                int oldSize = size;
0850:                int index = insertRange(range);
0851:                if (index != -1) {
0852:                    int nindex = index;
0853:                    if (nindex > 0)
0854:                        nindex--;
0855:                    size += range.length();
0856:                    normalize(nindex);
0857:                }
0858:                return size != oldSize;
0859:            }
0860:
0861:            /**
0862:             *  Adds a specified range to this set.
0863:             *
0864:             *  @param      first
0865:             *              the first value of the range to add to this set.
0866:             *
0867:             *  @param      last
0868:             *              the last value of the range to add to this set.
0869:             *
0870:             *  @return     <tt>true</tt> if this set was modified
0871:             *              as a result of adding the values <tt>first</tt>
0872:             *              to <tt>last</tt>; returns <tt>false</tt>
0873:             *              otherwise.
0874:             *
0875:             *  @throws     IllegalArgumentException
0876:             *              if <tt>first &gt; last</tt>.
0877:             */
0878:            public boolean addAll(long first, long last) {
0879:                return addAll(new LongRange(first, last));
0880:            }
0881:
0882:            /**
0883:             *  Adds an array of long values to this set.
0884:             *
0885:             *  @param      a
0886:             *              the array of long values to add to this set.
0887:             *
0888:             *  @throws     NullPointerException
0889:             *              if <tt>a</tt> is <tt>null</tt>.
0890:             *
0891:             *  @see        #add(long)
0892:             *  @see        #addAll(LongRange)
0893:             *  @see        #addAll(LongRangeSet)
0894:             *  @see        #addAll(LongCollection)
0895:             *  @see        #addAll(long, long)
0896:             */
0897:            public boolean addAll(long[] a) {
0898:                if (a.length == 0)
0899:                    return false;
0900:
0901:                //  Sort a
0902:                /*
0903:                    We can decide if the array is sorted in at most n steps
0904:                    (n being the length of chars).
0905:                    If it is not sorted, it is probably much less than n steps,
0906:                    and if it is sorted, we can skip the sorting operation
0907:                    and cloning of chars (thus effectively having sorted in
0908:                    linear time).
0909:                 */
0910:                int oldSize = size;
0911:                long[] sa;
0912:                if (!isSorted(a)) {
0913:                    sa = (long[]) a.clone();
0914:                    java.util.Arrays.sort(sa);
0915:                } else {
0916:                    sa = a;
0917:                }
0918:
0919:                //  Add ranges of a to range list
0920:                int index = 0;
0921:                long c0, c1;
0922:                while (index < sa.length) {
0923:                    c0 = sa[index];
0924:                    index = range(sa, index);
0925:                    c1 = sa[index];
0926:                    ranges.add(new LongRange(c0, c1));
0927:                    index++;
0928:                }
0929:
0930:                //  Sort and normalize range list
0931:                /*
0932:                    Is it better to sort and normalize once instead
0933:                    of inserting sorted and performing normalization at each step?
0934:                 */
0935:                java.util.Collections.sort(ranges);
0936:                normalize();
0937:                return size != oldSize;
0938:            }
0939:
0940:            /**
0941:             *  Finds a range in an ordered array which may
0942:             *  contain duplicates.
0943:             *
0944:             *  @param      a
0945:             *              the array of values to search.
0946:             *
0947:             *  @param      index
0948:             *              the index from which to start the search.
0949:             *
0950:             *  @return     the index of the last value in the found
0951:             *              range.
0952:             */
0953:            private int range(long[] a, int index) {
0954:                long c0 = a[index++];
0955:                //  Skip duplicates
0956:                while (index < a.length && a[index] == c0)
0957:                    index++;
0958:                //  While in sequence
0959:                while (index < a.length && a[index] == (long) (c0 + 1)) {
0960:                    c0 = a[index++];
0961:                    //  Skip duplicates
0962:                    while (index < a.length && a[index] == c0)
0963:                        index++;
0964:                }
0965:                return index - 1;
0966:            }
0967:
0968:            /**
0969:             *  Indicates whether the specified array is sorted in
0970:             *  ascending order.
0971:             *
0972:             *  @param      a
0973:             *              the array to examine.
0974:             *
0975:             *  @return     <tt>true</tt> if <tt>s</tt> is sorted; returns
0976:             *              <tt>false</tt> otherwise.
0977:             *
0978:             *  @throws     NullPointerException
0979:             *              if <tt>a</tt> is <tt>null</tt>.
0980:             */
0981:            private boolean isSorted(long[] a) {
0982:                for (int i = 1; i < a.length; i++)
0983:                    if (a[i] < a[i - 1])
0984:                        return false;
0985:                return true;
0986:            }
0987:
0988:            /**
0989:             *  Returns the ranges of this set. None of the ranges returned
0990:             *  will overlap or be adjacent.
0991:             *
0992:             *  @return     the ranges of this set. The returned array is
0993:             *              a fresh copy that can be modified without
0994:             *              modifying this set.
0995:             */
0996:            public LongRange[] ranges() {
0997:                LongRange[] a = new LongRange[ranges.size()];
0998:                ranges.toArray(a);
0999:                return a;
1000:            }
1001:
1002:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.