hashtables: 1st version; parseutils additions

5 files changed, 175 insertions, 6 deletions

diff --git a/lib/pure/collections/hashtables.nim b/lib/pure/collections/hashtables.nim
new file mode 100644
index 000000000..1a78586ab
--- /dev/null
+++ b/lib/pure/collections/hashtables.nim
@@ -0,0 +1,146 @@
+#
+#
+#            Nimrod's Runtime Library
+#        (c) Copyright 2011 Andreas Rumpf, Dominik Picheta
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+## The ``hashtables`` module implements an efficient hash table that is
+## a mapping from keys to values.
+
+import
+  os, hashes, strutils
+
+type
+  TKeyValuePair[A, B] = tuple[key: A, val: B]
+  TKeyValuePairSeq[A, B] = seq[TKeyValuePair[A, B]]
+  THashTable*[A, B] = object of TObject
+    counter: int
+    data: TKeyValuePairSeq[A, B]
+
+  PHashTable*[A, B] = ref THashTable[A, B] ## use this type to declare tables
+
+proc len*[A, B](t: PHashTable[A, B]): int =
+  ## returns the number of keys in `t`.
+  result = t.counter
+
+iterator pairs*[A, B](t: PHashTable[A, B]): tuple[key: A, val: B] =
+  ## iterates over any (key, value) pair in the table `t`.
+  for h in 0..high(t.data):
+    if not isNil(t.data[h].key) and not isNil(t.data[h].val):
+      yield (t.data[h].key, t.data[h].val)
+
+const
+  growthFactor = 2
+  startSize = 64
+
+proc myhash[A](key: A): THash =
+  result = hashes.hash(key)
+
+proc myCmp[A](key: A, key2: A): bool =
+  result = cmp(key, key2) == 0
+
+proc mustRehash(length, counter: int): bool =
+  assert(length > counter)
+  result = (length * 2 < counter * 3) or (length - counter < 4)
+
+proc nextTry(h, maxHash: THash): THash {.inline.} =
+  result = ((5 * h) + 1) and maxHash
+
+proc RawGet[A, B](t: PHashTable[A, B], key: A): int =
+  var h: THash = myhash(key) and high(t.data) # start with real hash value
+  while not isNil(t.data[h].key) and not isNil(t.data[h].val):
+    if mycmp(t.data[h].key, key):
+      return h
+    h = nextTry(h, high(t.data))
+  result = -1
+
+proc `[]`*[A, B](t: PHashTable[A, B], key: A): B =
+  ## retrieves the value at ``t[key]``. If `key` is not in `t`,
+  ## default empty value for the type `B` is returned
+  ## and no exception is raised. One can check with ``hasKey`` whether the key
+  ## exists.
+  var index = RawGet(t, key)
+  if index >= 0: result = t.data[index].val
+
+proc hasKey*[A, B](t: PHashTable[A, B], key: A): bool =
+  ## returns true iff `key` is in the table `t`.
+  result = rawGet(t, key) >= 0
+
+proc RawInsert[A, B](t: PHashTable[A, B], data: var TKeyValuePairSeq[A, B],
+                     key: A, val: B) =
+  var h: THash = myhash(key) and high(data)
+  while not isNil(data[h].key):
+    h = nextTry(h, high(data))
+  data[h].key = key
+  data[h].val = val
+
+proc Enlarge[A, B](t: PHashTable[A, B]) =
+  var n: TKeyValuePairSeq[A, B]
+  newSeq(n, len(t.data) * growthFactor)
+  for i in countup(0, high(t.data)):
+    if not isNil(t.data[i].key): RawInsert(t, n, t.data[i].key, t.data[i].val)
+  swap(t.data, n)
+
+proc `[]=`*[A, B](t: PHashTable[A, B], key: A, val: B) =
+  ## puts a (key, value)-pair into `t`.
+  var index = RawGet(t, key)
+  if index >= 0:
+    t.data[index].val = val
+  else:
+    if mustRehash(len(t.data), t.counter): Enlarge(t)
+    RawInsert(t, t.data, key, val)
+    inc(t.counter)
+
+proc default[T](): T = nil
+
+proc del*[A, B](t: PHashTable[A, B], key: A) =
+  ## deletes `key` from hash table `t`.
+  var index = RawGet(t, key)
+  if index >= 0:
+    t.data[index].key = default[A]()
+  else:
+    raise newException(EInvalidIndex, "Key not found.")
+
+proc newHashTable*[A, B](): PHashTable[A, B] =
+  ## creates a new string table that is empty.
+  new(result)
+  result.counter = 0
+  newSeq(result.data, startSize)
+
+proc `$`*[A, B](t: PHashTable[A, B]): string =
+  ## The `$` operator for string tables.
+  if t.len == 0:
+    result = "{:}"
+  else:
+    result = "{"
+    for key, val in pairs(t):
+      if result.len > 1: result.add(", ")
+      result.add($key)
+      result.add(": ")
+      result.add($val)
+    result.add("}")
+
+when isMainModule:
+  var table = newHashTable[string, float]()
+  table["test"] = 1.2345
+  table["111"] = 1.000043
+  echo table
+  table.del("111")
+  echo table
+  echo repr(table["111"])
+  echo(repr(table["1212"]))
+  table["111"] = 1.5
+  table["011"] = 67.9
+  echo table
+  table.del("test")
+  table.del("111")
+  echo table
+
+
+  echo hash("test")
+  echo hash("test")
+
+
diff --git a/lib/pure/parseutils.nim b/lib/pure/parseutils.nim
index 07c54f88c..90bb5d79f 100755
--- a/lib/pure/parseutils.nim
+++ b/lib/pure/parseutils.nim
@@ -77,10 +77,12 @@ proc parseIdent*(s: string, ident: var string, start = 0): int =
     result = i-start
 
 proc parseToken*(s: string, token: var string, validChars: set[char],
-                 start = 0): int {.inline.} =
+                 start = 0): int {.inline, deprecated.} =
   ## parses a token and stores it in ``token``. Returns
   ## the number of the parsed characters or 0 in case of an error. A token
   ## consists of the characters in `validChars`. 
+  ##
+  ## **Deprecated since version 0.8.12**: Use ``parseWhile`` instead.
   var i = start
   while s[i] in validChars: inc(i)
   result = i-start
@@ -110,6 +112,26 @@ proc skipWhile*(s: string, toSkip: set[char], start = 0): int {.inline.} =
   ## Returns number of characters skipped.
   while s[result+start] in toSkip and s[result+start] != '\0': inc(result)
 
+proc parseUntil*(s: string, token: var string, until: set[char],
+                 start = 0): int {.inline.} =
+  ## parses a token and stores it in ``token``. Returns
+  ## the number of the parsed characters or 0 in case of an error. A token
+  ## consists of the characters notin `until`. 
+  var i = start
+  while s[i] notin until: inc(i)
+  result = i-start
+  token = copy(s, start, i-1)
+
+proc parseWhile*(s: string, token: var string, validChars: set[char],
+                 start = 0): int {.inline.} =
+  ## parses a token and stores it in ``token``. Returns
+  ## the number of the parsed characters or 0 in case of an error. A token
+  ## consists of the characters in `validChars`. 
+  var i = start
+  while s[i] in validChars: inc(i)
+  result = i-start
+  token = copy(s, start, i-1)
+
 {.push overflowChecks: on.}
 # this must be compiled with overflow checking turned on:
 proc rawParseInt(s: string, b: var biggestInt, start = 0): int =
diff --git a/lib/system.nim b/lib/system.nim
index 6490ce416..46ca5b61d 100755
--- a/lib/system.nim
+++ b/lib/system.nim
@@ -1717,10 +1717,10 @@ elif defined(ecmaScript) or defined(NimrodVM):
       if x < y: return -1
       return 1
 
-proc quit*(errormsg: string) {.noReturn.} =
-  ## a shorthand for ``echo(errormsg); quit(quitFailure)``.
+proc quit*(errormsg: string, errorcode = QuitFailure) {.noReturn.} =
+  ## a shorthand for ``echo(errormsg); quit(errorcode)``.
   echo(errormsg)
-  quit(quitFailure)
+  quit(errorcode)
 
 {.pop.} # checks
 {.pop.} # hints
diff --git a/tests/accept/compile/ttempl4.nim b/tests/accept/compile/ttempl4.nim
index 273605669..a5ad2000f 100644
--- a/tests/accept/compile/ttempl4.nim
+++ b/tests/accept/compile/ttempl4.nim
@@ -2,7 +2,7 @@
 template `:=`(name, val: expr): stmt =
   var name = val
     
-ha := 1
-hu := "ta-da" 
+ha := 1 * 4
+hu := "ta-da" == "ta-da"
 echo ha, hu
 
diff --git a/web/news.txt b/web/news.txt
index 3a35a9f21..ce48b4e90 100755
--- a/web/news.txt
+++ b/web/news.txt
@@ -49,6 +49,7 @@ Additions
 - Added ``smtp`` module.
 - Added ``re.findAll``, ``pegs.findAll``.
 - Added ``os.findExe``.
+- Added ``parseutils.parseUntil`` and ``parseutils.parseWhile``.
 - Added ``strutils.align``, ``strutils.tokenize``, ``strutils.wordWrap``. 
 - Pegs support a *captured search loop operator* ``{@}``.
 - Pegs support new built-ins: ``\letter``, ``\upper``, ``\lower``,